A comparison of dispatching rules hybridised with Monte Carlo Simulation in stochastic permutation flow shop problem

Abstract

This paper presents a comparison of several well-known dispatching rules hybridised with Monte Carlo simulation to solve the Permutation Flow Shop Scheduling Problem with stochastic processing times. The aim of the paper is to show the importance of making an accurate probability distribution fitting of the uncertain parameter for adequate decision-making, especially if a robust schedule is desired. An experimental design was carried out to test the performance of 13 dispatching rules with three probability distributions and different coefficients of variation for the processing times. Experimental results were obtained for the expected mean and the standard deviation of five objective functions: makespan, flowtime, tardiness, maximum tardiness and tardy jobs. Results show that dispatching rules behave differently for mean and standard deviation regardless of the objective function. Hence, selected dispatching rules must be different if the goal is obtaining a robust schedule or to minimise the expected mean of a specific objective. Additionally, performance of dispatching rules depends on the coefficients of variation of processing times. These results demonstrate the importance of collecting enough and precise information of uncertain parameters to determine the probability distribution that fits the best.

Keywords:

• Stochastic permutation flow shop
• stochastic processing times
• dispatching rules
• Monte Carlo simulation