An improved procedure for solving minimum makespan on a flowshop

被引:0
作者
Freud, David [1 ]
Elalouf, Amir [1 ]
机构
[1] Bar Ilan Univ, Dept Management, Ramat Gan, Israel
来源
2022 8TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT'22) | 2022年
关键词
Scheduling; Flowshop; Processing time; Makespan; Heuristics; PERMUTATION; ALGORITHM;
D O I
10.1109/CODIT55151.2022.9804143
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper presents numerous heuristics, derived from the NEH heuristic, aimed at minimizing the classical permutation flowshop scheduling problem. We compare the solution, based on Taillard's benchmark problems. We propose a better schedule by comparing these heuristics and identifying common partial sequences of consecutive jobs. We identify the closest heuristic to our result by using a standard distance measure used in the literature. We use this heuristic as an initial solution for a further standard improvement procedure. The obtained average relative percentage deviation values of our procedure is within a reasonable computational effort and appears to improve the published results on these problem sets.
引用
收藏
页码:1630 / 1634
页数:5
相关论文
共 18 条
[1]  
Baskar A., 2016, International Journal of Industrial Engineering Computations, V7, P353
[2]   IMPLEMENTING SOBOLS QUASIRANDOM SEQUENCE GENERATOR [J].
BRATLEY, P ;
FOX, BL .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1988, 14 (01) :88-100
[3]   An improved NEH-based heuristic for the permutation flowshop problem [J].
Dong, Xingye ;
Huang, Houkuan ;
Chen, Ping .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (12) :3962-3968
[4]  
Emmons H., 2012, FLOW SHOP SCHEDULING
[5]   On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem [J].
Fernandez-Viagas, Victor ;
Framinan, Jose M. .
COMPUTERS & OPERATIONS RESEARCH, 2014, 45 :60-67
[6]  
Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117
[7]  
Gengcheng Liu, 2011, Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence. 7th International Conference, ICIC 2011. Revised Selected Papers, P41, DOI 10.1007/978-3-642-25944-9_6
[8]   An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems [J].
Jarboui, Bassem ;
Eddaly, Mansour ;
Siarry, Patrick .
COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (09) :2638-2646
[9]  
Jian Xie, 2013, Intelligent Computing Theories and Technology. 9th International Conference, ICIC 2013. Proceedings. LNCS 7996, P179, DOI 10.1007/978-3-642-39482-9_21
[10]   An improved NEH heuristic to minimize makespan in permutation flow shops [J].
Kalczynski, Pawel J. ;
Kamburowski, Jerzy .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (09) :3001-3008