摘要
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 completiontime 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
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 completiontime 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
基金
Supported by the National Key Basic Research and Development Program (973) of China (No. 2002CB312205), the China Postdoctoral Science Foundation (No. 2003033150), the Natural Science Foundation of Heilongjiang Province (No. F0207), the Youth Foundation of Harbin City (No. 2002AFQXJ033), and the Science and Technology Foundation of Heilongjiang Education Bureau (No. 10531056)
