| A Fast Method for Heuristics in Large-Scale Flow Shop Scheduling |
| |
| 作者姓名： | 李小平 刘连臣 昊澄 |
| |
| 作者单位： | Department of Automation Tsinghua University，Beijing 100084 China，Department of Computer Science and Technology Harbin University of Science and Technology Harbin 150080 China，Department of Automation Tsinghua University，Beijing 100084 China，Department of Automation Tsinghua University，Beijing 100084 China |
| |
| 基金项目： | 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) |
| |
| 摘 要： | Introduction A flow shop is a manufacturing system where n jobs are processed on m machines and each job has the same machine-order1]. If the job-order on each ma- chine is also the same, it is a permutation flow shop, in which some job-sequences can be …
|
| 关 键 词： | 大规模流动商店规划问题 启发式方法 总完成时间 快速计算方法 |
| 收稿时间： | 2004-04-01 |
| 修稿时间： | 2004-04-012005-01-05 |
A Fast Method for Heuristics in Large-Scale Flow Shop Scheduling |
| |
| Xiaoping Li, Ï , Lianchen Liu, &#x; ,Cheng Wu, &#x; .A Fast Method for Heuristics in Large-Scale Flow Shop Scheduling[J].Tsinghua Science and Technology,2006,11(1):12-18. |
| |
| Authors: | Xiaoping Li Ï Lianchen Liu &#x; Cheng Wu &#x; |
| |
| Institution: | 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 等数据库收录！ |
