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 practical manufacturing environments. This paper describes a generalized flow shop model, which is an extension 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 classical 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 analyzed with and without the TCG method. The results show that TCG considerably reduces the CPU time.