[1]齐学梅,李小平,王茜.最小化总完工时间的流水作业调度混合算法[J].东南大学学报(自然科学版),2008,38(6):960-964.[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(6):960-964.[doi:10.3969/j.issn.1001-0505.2008.06.005]
点击复制

最小化总完工时间的流水作业调度混合算法()
分享到:

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

卷:
38
期数:
2008年第6期
页码:
960-964
栏目:
计算机科学与工程
出版日期:
2008-11-20

文章信息/Info

Title:
Hybrid tabu search algorithms for permutation flow shops to minimize total flowtime
作者:
齐学梅12 李小平13 王茜13
1 东南大学计算机科学与工程学院, 南京 210096; 2 安徽师范大学数学计算机科学学院, 芜湖 241003; 3 东南大学计算机网络和信息集成教育部重点实验室,南京 210096
Author(s):
Qi Xuemei12 Li Xiaoping13 Wang Qian13
1 School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 School of Mathematics and Computer Science, Anhui Normal University, Wuhu 241003, China
3 Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China
关键词:
流水作业调度 启发式算法 禁忌搜索 总完工时间
Keywords:
permutation flow shops heuristic algorithm tabu search total flowtime
分类号:
TP301.6
DOI:
10.3969/j.issn.1001-0505.2008.06.005
摘要:
针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架. 基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1, HA2和HA3. 使用Taillard’s基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法. 与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%, 最优解所占比例皆有显著提高.
Abstract:
The well known NP-hard permutation flow shops problem with total flowtime minimization is considered in this paper. An algorithm framework is presented in which an initial solution is generated by an efficient hybrid heuristic algorithm and improved by a tabu search algorithm. Based on characteristics of different heuristics, three hybrid tabu search algorithms HA1, HA2, and HA3 are proposed. Taillard’s benchmark program is used to generate a large number of random instances. Experiment results show that the quality of solutions is improved using three algorithms with a bigger searching scope. The performance of three proposed methods are all superior to the most efficient heuristics currently used. Comparing with the result from the best existing heuristics, the average relative percentage deviation from the best-known solution is reduced about 30% and the percent of optimal solutions increases obviously.

参考文献/References:

[1] Garey M R,Johnson D S,Sethi R.The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research,1976,1(2):117-129.
[2] Kalczynski P J,Kamburowski J.On the NEH heuristic for minimizing the makespan in permutation flow shops[J]. Omega,2007,35(1):53-60.
[3] Framinan J M,Leisten R,Rajendran C.Different initial sequences for the heuristic of Nawaz,Enscore and Ham to minimize makespan,idle time or flowtime in the static permutation flowshop sequencing problem[J]. International Journal of production Research,2003,41(1):121-148.
[4] Framinan J M,Leisten R.An efficient constructive heuristic for flowtime minimisation in permutation flow shops[J]. Omega,2003,31(4):311-317.
[5] Woo H S,Yim D S.A heuristic algorithm for mean flowtime objective in flowshop scheduling[J]. Computers & Operations Research,1998, 25(3):175-182.
[6] Rajendran C,Ziegler H.An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs[J]. European Journal of Operational Research,1997,103(1):129-138.
[7] Allahverdi A,Aldowaisan T.New heuristics to minimize total completion in m-machine flowshops[J]. International Journal of Production Economics,2002,77(1):71-83.
[8] Framinan J M,Leisten R,Ruiz-Usano R.Comparison of heuristics for flowtime minimisation in permutation flowshops[J]. Computers & Operations Research,2005,32(5):1237-1254.
[9] Ben-Daya M,Al-Fawzan M.A tabu search approach for the flow shop scheduling problem[J]. European Journal of Operational Research,1998,109(1):88-95.
[10] Liu J,Reeves C R.Constructive and composite heuristic solutions to the P//∑Ci scheduling problem[J]. European Journal of Operational Research,2001,132(2):439-452.
[11] Taillard E.Benchmarks for basic scheduling programs[J]. European Journal of Operational Research,1993,64(2):278-285.
[12] Li X P,Wang Q,Wu C.Efficient composite heuristics for total flowtime minimization in permutation flow shops[J]. Omega,2009,37(1):155-164.(to appear)

相似文献/References:

[1]周海刚,汪泽焱,肖军模.一种基于多条件约束的路由优化启发式算法[J].东南大学学报(自然科学版),2003,33(3):275.[doi:10.3969/j.issn.1001-0505.2003.03.007]
 Zhou Haigang,Wang Zeyan,Xiao Junmo.Heuristic algorithm for optimizing routing with multiple constraints[J].Journal of Southeast University (Natural Science Edition),2003,33(6):275.[doi:10.3969/j.issn.1001-0505.2003.03.007]
[2]曹文明,胡克定,宋文忠.模糊集值产生式系统的启发式图搜索算法[J].东南大学学报(自然科学版),1996,26(4):39.[doi:10.3969/j.issn.1001-0505.1996.04.008]
 Cao Wenming,Hu Keding,Song Wenzhong.Heuristic Graph Search Algorithm on Fuzzy Interval Production System[J].Journal of Southeast University (Natural Science Edition),1996,26(6):39.[doi:10.3969/j.issn.1001-0505.1996.04.008]
[3]李亚志,朱夏.基于插入-分段的无等待流水作业调度复合启发式算法[J].东南大学学报(自然科学版),2013,43(3):483.[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(6):483.[doi:10.3969/j.issn.1001-0505.2013.03.007]
[4]金杉,刘林峰,吴家皋.一种新的自适应覆盖多播路由协议[J].东南大学学报(自然科学版),2007,37(3):374.[doi:10.3969/j.issn.1001-0505.2007.03.004]
 Jin Shan,Liu Linfeng,Wu Jiagao.Novel adaptive overlay multicast routing protocol[J].Journal of Southeast University (Natural Science Edition),2007,37(6):374.[doi:10.3969/j.issn.1001-0505.2007.03.004]
[5]周晶,盛昭瀚,何建敏,等.交通检测点分布规则及其数学模型[J].东南大学学报(自然科学版),1998,28(6):59.[doi:10.3969/j.issn.1001-0505.1998.06.012]
 Zhou Jing Sheng Zhaohan He Jianmin,Location Rule and Modeling of Traffic Counting Points[J].Journal of Southeast University (Natural Science Edition),1998,28(6):59.[doi:10.3969/j.issn.1001-0505.1998.06.012]
[6]张帅,汪芸,李凯.基于拓扑感知的TSP快速求解算法[J].东南大学学报(自然科学版),2014,44(3):522.[doi:10.3969/j.issn.1001-0505.2014.03.013]
 Zhang Shuai,Wang Yun,Li Kai.Fast TSP algorithm based on topological perception[J].Journal of Southeast University (Natural Science Edition),2014,44(6):522.[doi:10.3969/j.issn.1001-0505.2014.03.013]
[7]曹玖新,闵绘宇,徐顺,等.基于启发式和贪心策略的社交网络影响最大化算法[J].东南大学学报(自然科学版),2016,46(5):950.[doi:10.3969/j.issn.1001-0505.2016.05.009]
 Cao Jiuxin,Min Huiyu,Xu Shun,et al.Mixed heuristic and greedy strategies based algorithm for influence maximization in social networks[J].Journal of Southeast University (Natural Science Edition),2016,46(6):950.[doi:10.3969/j.issn.1001-0505.2016.05.009]
[8]韩飞,程琳,孙超,等.考虑路票发放方式和交易成本的UE模型及算法[J].东南大学学报(自然科学版),2018,48(3):576.[doi:10.3969/j.issn.1001-0505.2018.03.029]
 Han Fei,Cheng Lin,Sun Chao,et al.User equilibrium model and algorithm considering credit distribution scheme and transaction cost[J].Journal of Southeast University (Natural Science Edition),2018,48(6):576.[doi:10.3969/j.issn.1001-0505.2018.03.029]

备注/Memo

备注/Memo:
作者简介: 齐学梅(1963—),女,副教授,qxmhj@mail.ahnu.edu.cn.
基金项目: 国家自然科学基金资助项目(60672092, 60504029)、国家高技术研究发展计划(863计划)资助项目(2008AA04Z103).
引文格式: 齐学梅,李小平,王茜.最小化总完工时间的流水作业调度混合算法[J].东南大学学报:自然科学版,2008,38(6):960-964.
更新日期/Last Update: 2008-11-20