A Fast Method for Heuristics in Large-Scale Flow Shop Scheduling |
| |
Authors: | Xiaoping Li, Ï , Lianchen Liu, ,Cheng Wu, |
| |
Affiliation: | 1. Department of Automation, Tsinghua University, Beijing 100084, China; 2. Department of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China |
| |
Abstract: | 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. |
| |
Keywords: | scheduling heuristic flow shop total completion-time |
本文献已被 CNKI 维普 万方数据 ScienceDirect 等数据库收录! |
|