求解作业车间调度问题的混合帝国主义竞争算法

doi:10.11772/j.issn.1001-9081.2017.02.0517

计算机应用 ›› 2017, Vol. 37 ›› Issue (2): 517-522.DOI: 10.11772/j.issn.1001-9081.2017.02.0517

求解作业车间调度问题的混合帝国主义竞争算法

杨小东¹, 康雁^1,2, 柳青^1,2, 孙金文¹

1. 云南大学软件学院, 昆明 650091;
2. 云南省软件工程重点实验室(云南大学), 昆明 650091

收稿日期:2016-08-20 修回日期:2016-09-25 出版日期:2017-02-10 发布日期:2017-02-11
通讯作者: 康雁,kangyan@ynu.edu.cn
作者简介:杨小东(1991-),男,福建连城人,硕士研究生,CCF会员,主要研究方向:智能车间调度;康雁(1972-),女,四川绵阳人,副教授,博士,主要研究方向:智能车间调度、数据挖掘;柳青(1963-),男,云南祥云人,教授,硕士,主要研究方向:软件体系结构、海量数据处理和分析;孙金文(1989-),男,山西朔州人,硕士研究生,主要研究方向:模糊决策。
基金资助:
国家自然科学基金资助项目（61462095）；云南省软件工程重点实验室开放基金资助项目（2015SE103）。

Hybrid imperialist competitive algorithm for solving job-shop scheduling problem

YANG Xiaodong¹, KANG Yan^1,2, LIU Qing^1,2, SUN Jinwen¹

1. College of Software, Yunnan University, Kunming Yunnan 650091, China;
2. Key Laboratory in Software Engineering of Yunnan Province(Yunnan University), Kunming Yunnan 650091, China

Received:2016-08-20 Revised:2016-09-25 Online:2017-02-10 Published:2017-02-11
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61462095), the Open Foundation of Key Laboratory in Software Engineering of Yunnan Province (2015SE103).

摘要/Abstract

摘要： 针对最小化最大完工时间的作业车间调度问题（JSP），提出一种结合帝国主义竞争算法（ICA）和禁忌搜索（TS）算法的混合算法。混合算法以帝国主义竞争算法为基础，在同化操作中融入遗传算法中的杂交算子和变异算子，使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点，引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略，使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力，通过对13个经典的Benchmark调度问题进行仿真测试，并与近年4种新型混合算法进行对比分析，实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。

关键词: Job Shop调度问题, 帝国主义竞争算法, 遗传算法, 禁忌搜索, 混合优化算法

Abstract: For the Job-shop Scheduling Problem (JSP) with the objective of minimizing the makespan, a hybrid algorithm combining with Imperialist Competitive Algorithm (ICA) and Tabu Search (TS) was proposed. Based on imperialist competitive algorithm, crossover operator and mutation operator of Genetic Algorithm (GA) were applied in the hybrid algorithm as assimilation to strengthen its global search ability. To overcome the weakness of imperialist competitive algorithm in local search, TS algorithm was used to improve the offspring of assimilation. The hybrid neighborhood structure and a novel selection strategy were used by TS to make the search more efficient. By combining with the ability of global search and local search, testing on the 13 classic benchmark scheduling problems and comparing with other four hybrid algorithms in recent years, the experimental results show that the proposed hybrid algorithm is effective and stable.

Key words: Job-shop Scheduling Problem (JSP), Imperialist Competitive Algorithm (ICA), Genetic Algorithm (GA), Tabu Search (TS), hybrid optimization algorithm

中图分类号:

TP301.6
TP18

杨小东, 康雁, 柳青, 孙金文. 求解作业车间调度问题的混合帝国主义竞争算法[J]. 计算机应用, 2017, 37(2): 517-522.

YANG Xiaodong, KANG Yan, LIU Qing, SUN Jinwen. Hybrid imperialist competitive algorithm for solving job-shop scheduling problem[J]. Journal of Computer Applications, 2017, 37(2): 517-522.

参考文献

[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] BALAS E. Machine sequencing via disjunctive graphs:an implicit enumeration algorithm[J]. Operations Research, 1968, 17(6):941-957.
[3] VAN HULLE M M. A goal programming network for mixed integer linear programming:a case study for the job-shop scheduling problem[J]. International Journal of Neural Systems, 1991, 2(3):201-209.
[4] LUH P B, HOITOMT D J. Scheduling of manufacturing systems using the Lagrangian relaxation technique[J]. IEEE Transactions on Automatic Control, 1993, 38(7):1066-1079.
[5] GIFFLER B, THOMPSON G L. Algorithms for solving production scheduling problems[J]. Operations Research, 1960, 8(4):487-503.
[6] ADAMS J, BALAS E, ZAWACK D. The shifting bottleneck procedure for job shop scheduling[J]. Management Science, 1988, 34(3):391-401.
[7] SIMON F Y-P, TAKEFUJI Y. Stochastic neural networks for solving job-shop scheduling. Ⅰ. problem representation[C]//Proceedings of the 1988 IEEE International Conference on Neural Networks. Piscataway, NJ:IEEE, 1988:275-282.
[8] SIMON F Y-P, TAKEFUJI Y. Stochastic neural networks for solving job-shop scheduling. Ⅱ. architecture and simulations[C]//Proceedings of the 1988 IEEE International Conference on Neural Networks. Piscataway, NJ:IEEE, 1988:283-290.
[9] SIMON F Y-P, TAKEFUJI Y. Integer linear programming neural networks for job-shop scheduling[C]//Proceedings of the 1988 IEEE International Conference on Neural Networks. Piscataway, NJ:IEEE, 1988:341-348.
[10] REMUS W. Neural network models of managerial judgment[C]//Proceedings of the 23rd Annual Hawaii International Conference on System Sciences. Piscataway, NJ:IEEE, 1990:340-344.
[11] GLOVER F. New approaches for heuristic search:a bilateral linkage with artificial intelligence[J]. European Journal of Operational Research, 1989, 39(2):119-130.
[12] ATASHPAZ-GARGARI E, LUCAS C. Imperialist competitive algorithm:an algorithm for optimization inspired by imperialistic competition[C]//CEC 2007:Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2007:4661-4667.
[13] GLOVER F. Future paths for integer programming and links to artificial intelligence[J]. Computers & Operations Research, 1986, 13(5):533-549.
[14] ZHANG R, SONG S, WU C. A hybrid artificial bee colony algorithm for the job shop scheduling problem[J]. International Journal of Production Economics, 2013, 141(1):167-178.
[15] GAO L, ZHANG G, ZHANG L, et al. An efficient memetic algorithm for solving the job shop scheduling problem[J]. Computers & Industrial Engineering, 2011, 60(4):699-705.
[16] ZUO X, WANG C, TAN W. Two heads are better than one:an AIS-and TS-based hybrid strategy for job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2012, 63(1):155-168.
[17] REN Q-D-E-J, WANG Y. A new hybrid genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research, 2012, 39(10):2291-2299.
[18] 赵诗奎,方水良,顾新建.作业车间调度的空闲时间邻域搜索遗传算法[J].计算机集成制造系统,2014,20(8):1930-1940.(ZHAO S K, FANG S L, GU X J. Idle time neighborhood search genetic algorithm for job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2014, 20(8):1930-1940.).
[19] ZHANG C, RAO Y, LI P. An effective hybrid genetic algorithm for the job shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(9):965-974.
[20] DELL'AMICO M, TRUBIAN M. Applying tabu-search to the job shop scheduling problem[J]. Annals of Operations Research, 1993, 41(3):231-252.
[21] NOWICKI E, SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science, 1996, 42(6):797-813.
[22] BALAS E, VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science, 1998, 44(2):262-275.

求解作业车间调度问题的混合帝国主义竞争算法

Hybrid imperialist competitive algorithm for solving job-shop scheduling problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[4]	周烁, 仇润鹤, 唐旻俊. 基于禁忌搜索和Q-learning的CR-NOMA系统的功率分配算法[J]. 计算机应用, 2021, 41(7): 2026-2032.
[5]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[6]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[7]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[8]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[9]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[10]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[11]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[12]	杨华龙, 王美玉, 辛禹辰. 横向整合战略下异质车辆库存路径优化模型[J]. 计算机应用, 2021, 41(10): 3040-3048.
[13]	黄晓祥, 胡咏梅, 吴丹, 任力杰. 基于变分自编码器的异常颈动脉早期识别和预测[J]. 计算机应用, 2021, 41(10): 3082-3088.
[14]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.
[15]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.