Flexible flow shop scheduling with stochastic processing times: A decomposition-based approach |
| |
Authors: | SH Choi K Wang |
| |
Affiliation: | 1. Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong;2. Department of Management Science and Engineering, Economics and Management School, Wuhan University, Wuhan, China |
| |
Abstract: | Flexible flow shop scheduling problems are NP-hard and tend to become more complex when stochastic uncertainties are taken into consideration. Although some methods have been developed to address such problems, they remain inherently difficult to solve by any single approach. This paper presents a novel decomposition-based approach (DBA), which combines both the shortest processing time (SPT) and the genetic algorithm (GA), to minimizing the makespan of a flexible flow shop (FFS) with stochastic processing times. In the proposed DBA, 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 their stochastic nature. Two optimal back propagation networks (BPN), corresponding to the scenarios of simultaneous and non-simultaneous job arrivals, are then selectively adopted to assign either SPT or GA to each machine cluster for sub-schedule generation. Finally, an overall schedule is generated by integrating the sub-schedules of machine clusters. Computation results show that the DBA outperforms SPT and GA alone for FFS scheduling with stochastic processing times. |
| |
Keywords: | Flexible flow shop Scheduling Stochastic processing times Decomposition Neighbouring K-means clustering Back propagation network |
本文献已被 ScienceDirect 等数据库收录! |
|