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

Abstract

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.