An evaluation of flow-shop scheduling algorithms for makespan reduction in a stochastic environment

Abstract

This paper addresses the problem of makespan reduction and improvement in related performance measures in the stochastic flow shop. The experimental design addresses the issues of the problem size in terms of the number of jobs and machines, the bottleneck location within the production facility, and the processing time distribution and sensitivity to variance. In other words, many of the assumptions that are typically made in the published literature are violated in favour of a more realistic production basis. Experiments are performed via simulation to examine the performance of several well known flow-shop scheduling algorithms and one new algorithm in this challenging environment. The authors conclude that distributional effects and bottleneck considerations can play a role in the performance of the various algorithms considered. This paper further indicates that the problem size also tends to drive the effectiveness of the scheduling strategies examined, and presents information regarding interesting interaction effects between the problem size and the other elements of experimental concern.

Keywords:

• scheduling
• Johnson's reduction
• WIP reduction