Solving stochastic flexible flow shop scheduling problems with a decomposition-based approach

Abstract

Real manufacturing is dynamic and tends to suffer a lot of uncertainties. Research on production scheduling under uncertainty has recently received much attention. Although various approaches have been developed for scheduling under uncertainty, this problem is still difficult to tackle by any single approach, because of its inherent difficulties. This chapter describes a decomposition-based approach (DBA) for makespan minimisation of a flexible flow shop (FFS) scheduling problem with stochastic processing times. The DBA decomposes an FFS into several machine clusters which can be solved more easily by different approaches. A neighbouring K-means clustering algorithm is developed to firstly group the machines of an FFS into an appropriate number of machine clusters, based on a weighted cluster validity index. A back propagation network (BPN) is then adopted to assign either the Shortest Processing Time (SPT) Algorithm or the Genetic Algorithm (GA) to generate a sub-schedule for each machine cluster. After machine grouping and approach assignment, an overall schedule is generated by integrating the sub-schedules of the machine clusters. Computation results reveal that the DBA is superior to SPT and GA alone for FFS scheduling under stochastic processing times, and that it can be easily adapted to schedule FFS under other uncertainties. © 2010 American Institute of Physics.