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

被引：2
作者：
李小平 [1 ,2 ]
刘连臣 [1 ]
吴澄 [1 ]
机构：
[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
来源：
TsinghuaScienceandTechnology | 2006年 / 01期
基金：
中国博士后科学基金;
关键词：
scheduling; heuristic; flow shop; total completion-time;
D O I：
暂无
中图分类号：
TB114 [概率论、数理统计的应用];
学科分类号：
1201 ;
摘要：
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.
引用
收藏
页码：12 / 18
页数：7
相关论文
共 9 条
  • [1] Different initial se- quences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. Framinan J M,Leisten R,Rajendran C. International Journal of Production Research . 2003
  • [2] Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. French S. . 1982
  • [3] Efficient heuris- tics for flowshop sequencing with the objectives of makespan and flowtime minimization. Framinan J M,Leisten R,Ruiz-Usano R. European Journal of Operational Research . 2002
  • [4] An efficient heuristic approach to the scheduling of jobs in a flowshop. Rajendran C,Chaudhuri D. European Journal of Operational Research . 1991
  • [5] Benchmarks for basic scheduling problems. Tailard E. European Journal of Operational Research . 1993
  • [6] A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. Nawaz M,Enscore E E,Ham I. Omega . 1983
  • [7] Introduction to Sequencing and Scheduling. Baker K R. . 1974
  • [8] An efficient heuristic for schedul- ing in a flowshop to minimize total weighted flowtime of jobs. Rajendran C,Ziegler H. European Journal of Operational Research . 1997
  • [9] An efficient constructive heuris- tic for flowtime minimisation in permutation flow shops. Framinan J M,Leisten R. Omega . 2003
1