A simheuristic algorithm for solving the permutation flow shop problem with stochastic processing times

Ángel A. Juan

doi:10.1016/j.simpat.2014.02.005

2014-08-01

PRE

DOI：10.1016/j.simpat.2014.02.005

原文链接

原文求助

摘要

En 中文

This paper describes a simulation-optimization algorithm for the Permutation Flow shop Problem with Stochastic processing Times (PFSPST). The proposed algorithm combines Monte Carlo simulation with an Iterated Local Search metaheuristic in order to deal with the stochastic behavior of the problem. Using the expected makespan as initial minimization criterion, our simheuristic approach is based on the assumption that high-quality solutions (permutations of jobs) for the deterministic version of the problem are likely to be high-quality solutions for the stochastic version - i.e., a correlation will exist between both sets of solutions, at least for moderate levels of variability in the stochastic processing times. No particular assumption is made on the probability distributions modeling each job-machine processing times. Our approach is able to solve, in just a few minutes or even less, PFSPST instances with hundreds of jobs and dozens of machines. Also, the paper proposes the use of reliability analysis techniques to analyze simulation outcomes or historical observations on the random variable representing the makespan associated with a given solution. This way, criteria other than the expected makespan can be considered by the decision maker when comparing different alternative solutions. A set of classical benchmarks for the deterministic version of the problem are adapted and tested under several scenarios, each of them characterized by a different level of uncertainty - variance level of job-machine processing times. (C) 2014 Elsevier B.V. All rights reserved.

Keyword:

Permutation flow shop problem

Simulation-optimization

Stochastic times

Randomized algorithms

Iterated local search

Monte-Carlo simulation

Reliability analysis