带有顺序相关调整时间的多目标流水车间调度问题

doi:10.13196/j.cims.2013.12.xujianyou.3170.7.20131230

摘要/Abstract

摘要： 针对带有顺序相关调整时间的多目标流水车间调度问题,将传统的迭代局域搜索算法扩展到多目标领域,提出一种基于Pareto最优的多目标迭代局域搜索算法。在局域搜索中设计了一个基于动态邻域的变深度搜索方法,其搜索深度能够在算法的运行中动态变化,从而保证搜索深度和广度的平衡,提高算法的搜索性能。通过对标准测试问题和实际问题的测试,以及与其他进化算法的比较,验证了所提算法的有效性。

关键词: 流水车间调度, 多目标优化, 调整时间, 迭代局域搜索

Abstract: To deal with the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times,a Pareto-based iterated local search was developed by incorporating Pareto concept into the conventional iterated local search.In this algorithm,a variable depth search method based on dynamic neiborhood was desinged,and the search depth could be dynamically adjusted during the search process so as to achieve the balance of exploration and exploitation.The proposed multi-objective iterated local search algorithm was compared to several multi-objective evolutionary algorithms in the literature on some benchmark problems and a practical problem,and the computatioal results demonstrated the effectiveness of the proposed algorithm.

Key words: permutation flowshop scheduling, multi-objective optimization, setup time, iterated local search

中图分类号:

TP18

徐建有,董乃群,顾树生. 带有顺序相关调整时间的多目标流水车间调度问题[J]. , DOI: 10.13196/j.cims.2013.12.xujianyou.3170.7.20131230.

XU Jian-you,DONG Nai-qun,GU Shu-sheng. Multi-objective permutation flowshop scheduling with sequence-dependent setup times[J]. , DOI: 10.13196/j.cims.2013.12.xujianyou.3170.7.20131230.

参考文献

［1］RUIZ R,MAROTO C.A comprehensive review and evaluation of permutation flowshop heuristics［J］.European Journal of Operational Research,2005,165(2):479-494.
[2]RIOS-MERCADO R Z,BARD J F.The flow shop scheduling polyhedron with setup times［J］.Journal of Combinatorial Optimization,2003,7(3):291-318.
[3]RUIZ R,MAROTO C,ALCARAZ J.Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics［J］.European Journal of Operational Research,2005,165(1):34-54.
[4]ALLAHVERDI A,NG C T,CHENG T C E,et al.A survey of scheduling problems with setup times or costs［J］.European Journal of Operational Research,2008,187(3):985-1032.
[5]MINELLA G,RUIZ R,CIAVOTTA M.A review and evaluation of multiobjective algorithms for the flowshop scheduling problem［J］.INFORMS Journals on Computing,2008,20(3):451-471.
[7]ARROYO J E C,ARMENTANO V A.Genetic local search for multi-objective flowshop scheduling problems［J］.European Journal of Operational Research,2005,167(3):717-738.
[8]YANDA,TAMURA H.A new multiobjective genetic algorithm with heterogeneous population for solving flowshop scheduling problems［J］.International Journal of Computer Integrated Manufacturing,2007,20(5):465-477.
[9]DEB K,AGRAWAL S,PRATAP A,et al.A fast and elitist multi-objective genetic algorithm:NSGA-II［J］.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[10]KOLLAT J B,REED P M.The value of online adaptive search:a performance comparison of NSGA,NSGAII and MOEA［EB/OL］.［2013-06-01］.http://delta.cs.cinvestav.mx/~ccoello/EMOO/kollat05.pdf.gz.
[11]PASUPATHY T,RAJENDRAN C,SURESH RK.A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs［J］.The International Journal of Advanced Manufacturing Technology,2006,27(7/8):804-815.
[12]FRAMINAN J M,LEISTEN R.A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria［J］.OR Spectrum,2008,30(4):787-804.
[13]YANG Kaibing,LIU Xiaobing.Optimization algorithm for multi-objective flow shop scheduling with setup times［J］.Industrial Engineering and Management,2008,13(5):1-5(in Chinese).［杨开兵,刘晓冰.带调整时间的多目标流水车间调度的优化算法［J］.工业工程与管理,2008,13(5):1-5.］
[14]YANG Kaibing,LIU Xiaobing.Multi-objective optimization for flow shop scheduling with the group technology assumption removed［J］.Computer Integrated Manufacturing Systems,2009,15(2):348-361(in Chinese).［杨开兵,刘晓冰.无成组技术条件下流水车间调度的多目标优化［J］.计算机集成制造系统,2009,15(2):348-361.］
[15]CONGRAM R K,POTTS C N,VAND DE VELDE S L.An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem［J］.INFORMS Journal on Computing,2002,14(1):52-67.
[16]DONG X Y,HUANG H K,CHEN P.An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion［J］.Computers & Operations Research,2009,36(5):1664-1669.
[17]WEI Zhong,XU Xiaofei,DENG Shenchun.Hybrid particle swarm optimization for multi-ojbective sequencing problem in mixed model assembly line［J］.Computer Integrated Manufacturing Systems,2006,12(8):1227-1234(in Chinese).［卫忠,徐晓飞,邓胜春.多目标混合流水车间作业调度的演化算法［J］.计算机集成制造系统,2006,12(8):1227-1234.］
[18]LIU Weiqi,LIU Qiong,ZHANG Chaoyong,et al.Hybrid particle swarm optimization for multi-ojbective sequencing problem in mixed model assembly line［J］.Computer Integrated Manufacturing Systems,2011,17(12):2590-2598(in Chinese).［刘炜琪,刘琼,张超勇,等.基于混合粒子群算法求解多目标混流装配线排序［J］.计算机集成制造系统,2011,17(12):2590-2598.］［19］TANG Haibo,YE Chunming,LIU Changping,et al.Knowledge evolution particle swarm optimization for solving flow shop scheduling problem with fuzzy due date［J］.Computer Integrated Manufacturing Systems,2012,18(4):808-812(in Chinese).［唐海波,叶春明,刘长平,等.基于知识进化粒子群算法的模糊交货期流水车间调度问题［J］.计算机集成制造系统,2012,18(4):808-812.］［20］NAWAZ M,ENSCORE EE,HAM I.A heuristic algorithm for the m-machine,n-job sequencing problem［J］.Omega,1983,11(1):91-95. ［21］RUIZ R,STUZLE T.An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives［J］.European Journal of Operational Research,2008,187(3):1143-1159. ［22］TAILLARD E.Benchmarks for basic scheduling problems［J］.European Journal of Operational Research,1993,64(2):278-285. ［23］ZITZLER E,THIELE L,LAUMANNS M,et al.Performance assessment of multiobjective optimizers:an analysis and review［J］.IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

[1]	秦旋,房子涵,张赵鑫. 考虑资源约束的预制构件多目标生产调度优化[J]. 计算机集成制造系统, 2021, 27(8): 2248-2259.
[2]	刘晶,张喆语,董志红,季海鹏. 基于工业物联网的区块链多目标优化[J]. 计算机集成制造系统, 2021, 27(8): 2382-2392.
[3]	赵芮,顾幸生. 基于引力搜索算法的混合零空闲置换流水车间调度[J]. 计算机集成制造系统, 2021, 27(7): 1909-1917.
[4]	李林林,刘东梅,王显鹏. 基于改进MOEA/D的多目标置换流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(7): 1929-1940.
[5]	张建侠,宋明顺,方兴华,邓钰佳. 基于Kriging模型的多目标代理优化算法及其收敛性评估[J]. 计算机集成制造系统, 2021, 27(7): 2035-2044.
[6]	蒋晋,张则强,谢梦柯,蔡宁. 空间约束下多目标拆卸线平衡问题的改进狼群算法[J]. 计算机集成制造系统, 2021, 27(6): 1569-1581.
[7]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[8]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[9]	吴暖,王诺,于安琪,吴迪. 基于柔性靠泊的港口疏船调度多目标优化及最优解选择[J]. 计算机集成制造系统, 2021, 27(5): 1531-1540.
[10]	李敬花,陈俊宗,杨博歆. 海工产品分段建造中日程计划优化[J]. 计算机集成制造系统, 2021, 27(3): 770-786.
[11]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[12]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
[13]	蹇洁,郭雨,姜林,苏加福. 基于多目标优化的绿色供应链博弈模型及利润共享契约[J]. 计算机集成制造系统, 2021, 27(3): 943-953.
[14]	巩超光,胡天亮,叶瑛歆. 基于数字孪生的铣削参数动态多目标优化策略[J]. 计算机集成制造系统, 2021, 27(2): 478-486.
[15]	詹欣隆,张超勇,孟磊磊,连裕翔,薛燕社. 面向高效低碳的切削参数与柔性作业车间调度集成建模与优化[J]. 计算机集成制造系统, 2021, 27(12): 3519-3535.