基于问题特征知识的迭代贪心算法求解多目标零等待流水车间调度问题

doi:10.3901/JME.2025.04.344

机械工程学报 ›› 2025, Vol. 61 ›› Issue (4): 344-354.doi: 10.3901/JME.2025.04.344

• 交叉与前沿 • 上一篇

扫码分享

基于问题特征知识的迭代贪心算法求解多目标零等待流水车间调度问题

何轩^1,2, 潘全科¹, 高亮³

1. 上海大学机电工程与自动化学院上海 200072;
2. 上海海事大学物流工程学院上海 201306;
3. 华中科技大学智能制造装备与技术全国重点实验室武汉 430074

收稿日期:2024-03-14 修回日期:2024-09-14 发布日期:2025-04-14
作者简介:何轩，男，1993年出生，博士，讲师。主要研究方向为智能优化与调度算法。E-mail：hexuan@shu.edu.cn
潘全科(通信作者)，男，1971年出生，博士，教授，博士研究生导师。主要研究方向为智能优化与调度算法、运筹学、供应链管理。E-mail：panquanke@shu.edu.cn
高亮，男，1974年出生，博士，教授，博士研究生导师。主要研究方向为智能优化与调度算法、运筹学、供应链管理。E-mail：gaoliang@mail.hust.edu.cn
基金资助:
国家自然科学基金(61973203，61873328)、国家重点研发计划(2020YFB1708200)、国家杰出青年基金(51825502)和上海市学术/技术计划(21XD1401000)资助项目。

Iterated Greedy Algorithm with Problem-specific Knowledge for Multi-objective No-wait Flowshop Scheduling Problem

HE Xuan^1,2, PAN Quanke¹, GAO Liang³

1. School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072;
2. School of Logistics Engineering, Shanghai Maritime University, Shanghai 201306;
3. State Key Lab of Intelligent Manufacturing Equipment & Technology in Huazhong University of Science & Technology, Wuhan 430074

Received:2024-03-14 Revised:2024-09-14 Published:2025-04-14

摘要/Abstract

摘要： 零等待流水车间调度问题在现实生活中有广泛的应用，研究其求解方法是非常有必要的。现有文献大多仅考虑一个生产调度指标。然而，实际问题往往是多目标的。因此，以同时优化最大完工时间和总流经时间为目标，提出一种问题特征知识指导搜索的迭代贪心调度算法。首先，使用混合整数规划模型中目标转化为约束的方法验证两个目标的冲突性。然后，分析并提取问题特征知识，设计极值搜索过程估计参考点。针对最大完工时间目标，将其转化为非对称旅行商问题，使用动态规划局部优化调度序列。针对总流经时间指标，利用支配准则指导的局部搜索进行确定性的优化。最后，为有效执行具有问题特征指导的局部搜索，使用锥形标量加权方法将两个优化目标转化为一个优化目标。大量仿真试验表明了所提方法的有效性。

关键词: 零等待流水车间调度, 多目标优化, 动态规划, 支配准则, 迭代贪心

Abstract: The no-waiting flowshop scheduling problem(NWFSP) has a wide range of applications in the manufacturing industry. It is very necessary to develop efficient algorithms for solving NWFSP. Most of the existing literature only considers optimizing one production scheduling objective, but multiple objectives in actual production scenarios often need to be optimized simultaneously. Therefore, we focus on optimizing both the makespan and total flow time simultaneously, and propose an iterated greedy algorithm with problem-specific knowledge(KIG). First, the conflict relationship between the two objectives is verified by converting the total flow time objective in the mixed integer programming model into a constraint. Then, the problem-specific knowledge in each objective is analyzed and obtained. For the makepan objective, NWFSP is transformed into an asymmetric traveling salesman problem, and a dynamic programming algorithm is used to locally optimize the search solution. For the total flow time objective, a dominance criterion guided local search is used to deterministically optimize the partial sequence of the search solution. Finally, the conical scalar weighting method transforms the two optimization objectives into one optimization objective to perform local search efficiently. Extensive experimental results demonstrate the effectiveness of the KIG.

Key words: no-wait flowshop scheduling problem, multi-objective optimization, dynamic programming, domination criterion, iterated greedy

中图分类号:

TP301

何轩, 潘全科, 高亮. 基于问题特征知识的迭代贪心算法求解多目标零等待流水车间调度问题[J]. 机械工程学报, 2025, 61(4): 344-354.

HE Xuan, PAN Quanke, GAO Liang. Iterated Greedy Algorithm with Problem-specific Knowledge for Multi-objective No-wait Flowshop Scheduling Problem[J]. Journal of Mechanical Engineering, 2025, 61(4): 344-354.

参考文献

[1] ALLAHVERDI A. A survey of scheduling problems with no-wait in process[J]. European Journal of Operational Research，2016，255(3):665-686.
[2] NAGANO M S，JUNQUEIRA V S V，ROSSI F L. An objective review and perspectives on the permutation flowshop scheduling with no-wait constraint and setup times[J]. IFAC Journal of Systems and Control，2024，29:100279.
[3] UTAMA D M，UMAMY S Z，AL-IMRON C N J R-O R. No-wait flow shop scheduling problem:A systematic literature review and bibliometric analysis[J]. RAIRO-Operations Research，2024，58(2):1281-1313.
[4] LIN S W，YING K C. Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics[J]. Omega，2016，64:115-125.
[5] LEE T E，LEE H Y，LEE S J. Scheduling a wet station for wafer cleaning with multiple job flows and multiple wafer-handling robots[J]. Recent Developments in Modelling and Analysis of Semiconductor Manufacturing，2007，45(3):487-507.
[6] PAN Quanke，FATIH TASGETIREN M，LIANG Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J]. Computers and Operations Research，2008，35(9):2807-2839.
[7] PAN Quanke，WANG Ling，QIAN Bin. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers and Operations Research，2009，36(8):2498-2511.
[8] ZHAO Fuqing，HE Xuan，WANG Ling. A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem[J]. IEEE Transactions on Cybernetics，2021，51(11):5291-5303.
[9] HE Xuan，PAN Quanke，GAO Liang，et al. A greedy cooperative co-evolution ary algorithm with problem-specific knowledge for multi-objective flowshop group scheduling problems[J]. IEEE Transactions on Evolutionary Computation，2021，27(3):430-444.
[10] HE Xuan，PAN Quanke，GAO Liang，et al. Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times[J]. Omega，2024，123:102997.
[11] GAREY M R，JOHNSON D S. Computers and intractability:A guide to the theory of NP completeness[M]. San Francisco:W. H. Freeman and Company，1979.
[12] 苏建涛，董绍华，朱诗敏. 多目标混合流水车间机器故障重调度问题研究[J]. 机械工程学报，2024，60(4):438-448. SU Jiantao，DONG Shaohua，ZHU Shimin. Research on machine fault rescheduling problem of multi objective hybrid flow shop based on intelligent manufacturing[J]. Journal of Mechanical Engineering，2024，60(4):438-448.
[13] 吴秀丽，闫晓燕. 基于改进Q学习的可重入混合流水车间绿色动态调度[J]. 机械工程学报，2023，59(13):246-259. WU Xiuli，YAN Xiaoyan. An improved Q learning algorithm to optimize green dynamic scheduling problem in a reentrant hybrid flow shop[J]. Journal of Mechanical Engineering，2023，59(13):246-259.
[14] 牟健慧，段培永，高亮，等. 基于混合遗传算法求解分布式流水车间逆调度问题[J]. 机械工程学报，2022，58(6):295-308. MU Jianhui，DUAN Peiyong，GAO Liang，et al. Hybrid genetic algorithm for distributed flow shop inverse scheduling problem[J]. Journal of Mechanical Engineering，2022，58(6):295-308.
[15] MUCHA M，SVIRIDENKO M. No-wait flowshop scheduling is as hard as asymmetric traveling salesman problem[J]. Mathematics of Operations Research，2016，41(1):247-254.
[16] NAWAZ M，ENSCORE E E，HAM I. A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J]. Omega，1983，11(1):91-95.
[17] YE H，LI W，MIAO E. An effective heuristic for no-wait flow shop production to minimize makespan[J]. Journal of Manufacturing Systems，2016，40:2-7.
[18] YE H，LI W，ABEDINI A. An improved heuristic for no-wait flow shop to minimize makespan[J]. Journal of Manufacturing Systems，2017，44:273-279.
[19] ZHAO Fuqing，HE Xuan，ZHANG Yi，et al. A jigsaw puzzle inspired algorithm for solving large-scale no-wait flow shop scheduling problems[J]. Applied Intelligence，2020，50(1):87-100.
[20] 郭伟飞，雷琦，宋豫川，等. 基于虚拟零部件的零等待约束复杂产品综合调度算法[J]. 机械工程学报，2020，56(4):246-257. GUO Weifei，LEI Qi，SONG Yuchuan，et al. Integrated scheduling algorithm of complex product with no-wait constraint based on virtual component[J]. Journal of Mechanical Engineering，2020，56(4):246-257.
[21] AVCI M. An effective iterated local search algorithm for the distributed no-wait flowshop scheduling problem[J]. Engineering Applications of Artificial Intelligence，2023，120:105921.
[22] 李浩然，高亮，李新宇. 基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J].机械工程学报，2023，59(2):291-306. LI Haoran，GAO Liang，LI Xinyu. Discrete artificial bee colony algorithm for multi-objective distributed heterogeneous no-wait flowshop scheduling problem[J]. Journal of Mechanical Engineering，2023，59(2):291-306.
[23] ZHANG Ziqi，XU Yanxuan，QIAN Bin，et al. An enhanced estimation of distribution algorithm with problem-specific knowledge for distributed no-wait flowshop group scheduling problems[J]. Swarm and Evolutionary Computation，2024，87:101559.
[24] 魏鑫，张泽群，唐敦兵，等. 面向节能的导弹结构件混线生产作业车间多目标调度研究[J]. 机械工程学报，2018，54(9):45-54. WEI Xin，ZHANG Zequn，TANG Dunbing，et al. Energy-saving oriented multi-objective shop floor scheduling for mixed-line production of missile components[J]. Journal of Mechanical Engineering，2018，54(9):45-54.
[25] DU Songlin，ZHOU Wenju，FEI Minrui，et al. Bi-objective scheduling for energy-efficient distributed assembly blocking flow shop[J]. CIRP Annals，2024，73(1):357-360.
[26] ABELEDO H，FUKASAWA R，PESSOA A，et al. The time dependent traveling salesman problem:Polyhedra and algorithm[J]. Mathematical Programming Computation，2013，5(1):27-55.
[27] FISCHETTI M，TOTH P. A polyhedral approach to the asymmetric traveling salesman problem[J]. Management Science，1997，43(11):1520-1536.
[28] CHUNG C S，FLYNN J，KIRCA O. A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems[J]. International Journal of Production Economics，2002，79(3):185-196.
[29] DING J Y，SONG S，ZHANG R，et al. A novel block-shifting simulated annealing algorithm for the no-wait flowshop scheduling problem[C]//Proceedings of the IEEE Congress on Evolutionary Computation(CEC)，May 25-28，2015，Sendai，Japan，NewYork:IEEE，2015:2768-2774.
[30] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research，1993，64(2):278-285.
[31] DEB K，PRATAP A，AGARWAL S，et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation，2002，6(2):182-197.
[32] WANG Jingjing，WANG Ling. A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop[J]. IEEE Transactions on Systems，Man，and Cybernetics:Systems，2020，50(5):1805-1819.

基于问题特征知识的迭代贪心算法求解多目标零等待流水车间调度问题

Iterated Greedy Algorithm with Problem-specific Knowledge for Multi-objective No-wait Flowshop Scheduling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	廖茂林, 李智, 朱佳鹏, 王泽旭, JOSEPH Páez Chávez. 自推进胶囊在小肠中移动时的优化控制[J]. 机械工程学报, 2025, 61(3): 299-313.
[2]	王蔚, 李晓旭, 刘伟军, 卞宏友, 邢飞, 王静. 激光清洗7075铝合金清洗质量建模及多目标优化研究[J]. 机械工程学报, 2025, 61(3): 422-439.
[3]	周晨, 徐飞翔. 四轮独立转向车辆转向模式切换轨迹多目标优化方法研究[J]. 机械工程学报, 2024, 60(6): 306-320.
[4]	柴依扬, 张乐乐, 窦伟元, 张海峰. 基于并行NSGA-III算法的高速列车车体侧墙结构高维多目标优化[J]. 机械工程学报, 2024, 60(6): 321-333.
[5]	苏建涛, 董绍华, 朱诗敏. 多目标混合流水车间机器故障重调度问题研究[J]. 机械工程学报, 2024, 60(4): 438-448.
[6]	唐红涛, 魏书鹏, 李西兴, 雷德明, 汪开普. 考虑排队因素的多车型车辆配置与路径协同优化[J]. 机械工程学报, 2024, 60(4): 458-472.
[7]	吕利叶, 鲁玉军, 王硕, 刘印, 李昆鹏, 宋学官. 代理模型技术及其应用：现状与展望[J]. 机械工程学报, 2024, 60(3): 254-281.
[8]	卢超, 田禾子, 李新宇, 张彪. 基于多目标海鸥算法的分布式焊接节能调度[J]. 机械工程学报, 2024, 60(22): 192-203.
[9]	王旭, 姜兴宇, 杨国哲, 孙猛, 于沈弘, 毕凯航, 赵日铮, 刘伟军. 基于PSO-SSA的激光清洗装备人机界面布局优化研究[J]. 机械工程学报, 2024, 60(20): 372-387.
[10]	熊瑞, 李正阳, 燕润博, 杨瑞鑫. 全气候自热锂离子电池及低温极速加热策略研究[J]. 机械工程学报, 2024, 60(18): 247-257.
[11]	梁旭, 张建勇, 李国涛, 苏婷婷, 何广平, 侯增广. 面向骨折复位手术的冗余并联机构：设计、建模与性能分析[J]. 机械工程学报, 2024, 60(17): 133-146.
[12]	王洪亮, 雍健羽, 皮大伟, 谢伯元, 王尔烈, 王显会. 基于贝塞尔曲线和多目标优化方法的多车队形切换轨迹规划[J]. 机械工程学报, 2024, 60(16): 270-279.
[13]	赵峰, 胡伟飞, 李光, 邓晓豫, 刘振宇, 郭云飞, 谭建荣. 基于混合指标自适应采样代理模型的多目标优化设计方法[J]. 机械工程学报, 2024, 60(13): 81-91.
[14]	胡林, 杨冬兆, 张新, 章杰, 廖家才. 基于DQP-LMPC的智能车超车换道动态路径规划[J]. 机械工程学报, 2024, 60(10): 171-181.
[15]	王娟, 刘美红, 祝世兴, 陈文博, 李遇贤, 孙军锋. 指尖密封结构参数的多目标混合教与学优化方法[J]. 机械工程学报, 2023, 59(9): 157-170.