[1]李亚志,朱夏.基于插入-分段的无等待流水作业调度复合启发式算法[J].东南大学学报(自然科学版),2013,43(3):483-488.[doi:10.3969/j.issn.1001-0505.2013.03.007]
 Li Yazhi,Zhu Xia.Insertion-segment based composite heuristic algorithm for no-wait flow shop scheduling problems[J].Journal of Southeast University (Natural Science Edition),2013,43(3):483-488.[doi:10.3969/j.issn.1001-0505.2013.03.007]
点击复制

基于插入-分段的无等待流水作业调度复合启发式算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
43
期数:
2013年第3期
页码:
483-488
栏目:
计算机科学与工程
出版日期:
2013-05-20

文章信息/Info

Title:
Insertion-segment based composite heuristic algorithm for no-wait flow shop scheduling problems
作者:
李亚志朱夏
东南大学计算机科学与工程学院, 南京 211189; 东南大学计算机网络与信息集成教育部重点实验室, 南京 211189
Author(s):
Li Yazhi Zhu Xia
School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China
关键词:
无等待流水作业 总完工时间 邻域结构 启发式算法
Keywords:
no-wait flow shop total completion time neighborhood structure heuristic algorithm
分类号:
TP391.7
DOI:
10.3969/j.issn.1001-0505.2013.03.007
摘要:
为求解NP-难的总完工时间最小化的无等待流水作业调度问题,提出一种有效复合启发式算法.通过分析基本操作的目标增量性质,构造基于插入-分段(I-S)的邻域结构和操作,提出了基于I-S的复合启发式算法(ISCH).ISCH算法与基于比较的启发式算法(BE)、基于置换的复合启发式算法(PH1(p))、Framinan等提出的复合启发式算法(FNM)和基于可变邻域搜索的混合遗传算法(GA-VNS)的比较结果表明,ISCH算法性能最佳,其平均相对偏差的均值较BE算法降低2.04%,平均运行时间为FNM算法的18.43%. 当存在时间约束时,ISCH算法的平均相对偏差较GA-VNS算法降低0.99%.该算法中,目标增量方法的选用降低了运行时间,基于I-S邻域结构的方法则提高了算法性能.
Abstract:
To solve the NP-hard(no-deterministic polynomial-time hard)no-wait flow shop scheduling problem with total completion time minimization, an effective composite heuristic algorithm is presented. By analyzing the increment properties of fundamental operators and constructing an insertion-segment(I-S)based neighborhood structure and its operation, an insertion-segment based composite heuristic algorithm(ISCH)is proposed. The comparison results of the ISCH algorithm, the heuristic algorithm based on comparison(BE), the heuristic algorithm based on pair-wise exchange(PH1(p)), the heuristic algorithm presented by Framinan et al.(FNM)and the hybrid genetic algorithm with variable neighborhood search(GA-VNS)show that the ISCH algorithm outperforms the other algorithms. The average value of the average relative percent deviation(ARPD)of the ISCH algorithm is less than that of BE algorithm by 2.04%. And the average computation time of the ISCH algorithm is 18.43% of that of the FNM algorithm. When time is limited, the ARPD of the ISCH algorithm is lower than that of the GA-VNS algorithm by 0.99%. In this algorithm, the increment-properties-based method can decrease the computation time, and the method based on I-S neighborhood structure can enhance the efficiency.

参考文献/References:

[1] Laha D, Chakraborty U K. A constructive heuristic for minimizing makespan in no-wait flow shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2009, 41(1/2): 97-109.
[2] Li X P, Wu C. Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments[J]. Science in China Series F: Information Sciences, 2008, 51(7): 896-909.
[3] Rahimi-Vahed A R, Javadi B, Rabbani M. A multi-objective scatter search for a bi-criteria no-wait flow shop scheduling problem[J]. Engineering Optimization, 2008, 40(4): 331-346.
[4] Aldowaisan T, Allahverdi A. New heuristics for m-machine no-wait flowshop to minimize total completion time[J]. Omega, 2004, 32(5):345-352.
[5] Framinan J M, Nageno M S, Moccellin J V. An efficient heuristic for total flowtime minimization in no-wait flowshops[J]. International Journal of Advanced Manufacturing Technology, 2010, 46(9/10/11/12): 1049-1057.
[6] Gao K Z, Pan Q K, Li J Q. Discrete harmony search algorithm for the no-wait flow shop scheduling problem with total flow time criterion[J]. International Journal of Advanced Manufacturing Technology, 2011, 56(5/6/7/8): 683-692.
[7] Pan Q K. Tasgetiren M F, Liang Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J]. Computers & Operations Research, 2008, 35(9): 2807-2839.
[8] Jarboui B, Eddaly M, Siarry P. A hybrid genetic algorithm for solving no-wait flow shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 54(9/10/11/12):1129-1143.
[9] Rajendran C, Chaudhuri D. Heuristic algorithms for continuous flow-shop problem[J]. Naval Research Logistics, 1990, 37(5): 695-705.
[10] Bertolissi E. Heuristic algorithm for scheduling in the no-wait flow-shop[J]. Journal of Materials Technology, 2000, 107(1/2/3):459-465.
[11] Nawaz M, Enscore E E, Ham I. A heuristic algorithm for m-machine n-job flow-shop sequencing problem[J]. Omega, 1983, 11(1):91-95.
[12] Taillard E. Benchmarks for basic scheduling problems[J].European Journal of Operational Research, 1993, 64(2): 278-285.

相似文献/References:

[1]齐学梅,李小平,王茜.最小化总完工时间的流水作业调度混合算法[J].东南大学学报(自然科学版),2008,38(6):960.[doi:10.3969/j.issn.1001-0505.2008.06.005]
 Qi Xuemei,Li Xiaoping,Wang Qian.Hybrid tabu search algorithms for permutation flow shops to minimize total flowtime[J].Journal of Southeast University (Natural Science Edition),2008,38(3):960.[doi:10.3969/j.issn.1001-0505.2008.06.005]

备注/Memo

备注/Memo:
作者简介: 李亚志(1976—),男,博士生;朱夏(联系人),女,博士,讲师,zhuxia@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(61003158).
引文格式: 李亚志,朱夏.基于插入-分段的无等待流水作业调度复合启发式算法[J].东南大学学报:自然科学版,2013,43(3):483-488. [doi:10.3969/j.issn.1001-0505.2013.03.007]
更新日期/Last Update: 2013-05-20