Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization

被引:0
作者
Kaizhou Gao
Quanke Pan
P. N. Suganthan
Junqing Li
机构
[1] Liaocheng University,College of Computer Science
[2] Nanyang Technology University,School of Electrical and Electronic Engineering
来源
The International Journal of Advanced Manufacturing Technology | 2013年 / 66卷
关键词
Flow shop scheduling; No-wait; Total flow time; Constructive heuristics; Composite heuristics;
D O I
暂无
中图分类号
学科分类号
摘要
The no-wait flow shop scheduling problem with total flow time criterion has important applications in industrial systems. Heuristics that explore specific characteristics of the problem are essential to find good solutions in limited computational time for many practical applications. This paper first presents two constructive heuristics, namely improved standard deviation heuristic (ISDH) and improved Bertolissi heuristic (IBH), by combining the standard deviation heuristic (Gao et al., Int J Adv Manf Technol 56:683–692, 2011) and Bertolliso heuristic (Bertolissi, J Mater Process Technol 107:459–465, 2000) with the procedure of the constructive heuristic of Laha (Int J Adv Manf Technol 41:97–109, 2009). Then, four composite heuristics, i.e., ISDH with local search, IBH with local search, ISDH with iteration, and IBH with iteration, are separately proposed using the insertion-based local search method and iteration operator to improve the solutions of the ISDH and IBH. Extensive computational experiments are carried out based on a set of well-known flow shop benchmark instances that are considered as no-wait flow shop instances. Computational results and comparisons show that the proposed composite heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics for the no-wait flow shop scheduling problem with total flow time criterion.
引用
收藏
页码:1563 / 1572
页数:9
相关论文
共 80 条
[1]  
Rajendran C(1994)A no-wait flowshop scheduling heuristic to minimize makespan J Oper Res Soc 45 472-478
[2]  
Hall NG(1996)A survey of machine scheduling problems with blocking and no-wait in process Oper Res 44 510-525
[3]  
Sriskandarayah C(2000)Sequencing of jobs in some production system Eur J Oper Res 125 535-550
[4]  
Grabowski J(2000)Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing Eur J Oper Res 126 131-151
[5]  
Pempera J(19778)Flow shop and job shop scheduling: complexity and approximation Oper Res 26 36-52
[6]  
Raaymakers W(1990)Heuristic algorithm for no-wait flow shop problem Nav Res Logist 37 695-705
[7]  
Hoogeveen J(2003)Solving the continuous flow shop scheduling problem by metaheuristics Eur J Oper Res 151 400-414
[8]  
Gonzalez T(2001)A new heuristic and dominance relations for no-wait flow shops with setups Comput Oper Res 28 563-584
[9]  
Sahni S(1998)Total flow time in no-wait flow shops with setup times Comput Oper Res 25 757-765
[10]  
Rajendran C(2004)New heuristic for m-machine no-wait flow shop to minimize total completion time Omega 32 345-352