A Fast Method for Heuristics in Large-Scale Flow Shop Scheduling

Fast computation methods are needed for the heuristics of flow shop scheduling problems in prac- tical manufacturing environments. This paper describes a generalized flow shop model, which is an exten- sion of the classical model, in which not all machines are available at time zero. The general completion- time computing method is used to compute completion time of generalized flow shops. The transform clas- sical flow shop to generalized shop (TCG) method is used to transform classical schedules into generalized schedules with less jobs. INSERT and SWAP, extended from job-insertion and pair-wise exchange which are fundamental procedures used in most heuristics for classical flow shops, reduce the CPU time by 1/2 and 1/3, respectively. The CPU time of 14 job-insertion and pair-wise exchange-based heuristics are ana- lyzed with and without the TCG method. The results show that TCG considerably reduces the CPU time.