双资源约束的柔性作业车间鲁棒调度方法

doi:10.3901/JME.2024.06.114

摘要/Abstract

摘要： 针对考虑工人技能水平差异和加工时间随机性的设备、工人双资源约束的柔性作业车间调度问题(Flexible job shop scheduling problem, FJSP)，构建双资源约束的柔性作业车间鲁棒调度模型(Dual resource constraint flexible job shop robust scheduling problem, DRC-FJRSP)。将粒子群算法(Particle swarm optimization, PSO)的学习机制引入差分算法(Differential evolution, DE)的交叉部分，设计PSO-DE混合求解算法，实现问题的加速求解并有效避免搜索停滞的窘境。选取DE算法、遗传算法(Genetic algorithm, GA)、PSO算法作为对比算法进行仿真试验，试验结果显示，所提出的PSO-DE混合求解算法平均鲁棒性为5.331，在三个仿真算例调度makespan求解中表现最好。验证了DRC-FJRSP模型的合理性以及PSO-DE混合求解算法的鲁棒性。最后，以一个制造企业的FJSP为例进行求解，给出调度甘特图。研究解决了设备、工人资源不足给FJSP带来的加工冲突，降低了加工时间的随机扰动，优化了调度的makespan。

关键词: 双资源约束, 柔性作业车间, 鲁棒调度, PSO-DE混合求解算法

Abstract: Aiming at the flexible job shop scheduling problem(FJSP) considering the difference in workers' skill level and the randomness of processing time, the dual resource constraint flexible job shop robust scheduling problem(DRC-FJRSP) model is constructed. The learning mechanism of particle swarm optimization(PSO) is introduced into the cross part of differential evolution (DE), and a PSO-DE hybrid solution algorithm is designed to realize the accelerated solution of the problem and effectively avoid the dilemma of search stagnation. DE, genetic algorithm(GA) and PSO are selected as comparison algorithms for simulation experiments. The experimental results show that the average robustness of the proposed PSO-DE hybrid solution algorithm is 5.331, which performs best in scheduling makespan solutions of three simulation examples. The rationality of DRC-FJRSP model and the robustness of PSO-DE hybrid solution algorithm are verified. Finally, taking the FJSP of a manufacturing enterprise as an example to solve the problem, the scheduling Gantt chart is given. The research solves the processing conflict caused by the shortage of equipment and worker resources to FJSP, reduces the random disturbance of processing time, and optimizes the makespan of scheduling.

Key words: dual resource constrains, flexible job shop, robust scheduling, PSO-DE hybrid solution algorithm

中图分类号:

TG156

梁志珍, 王晓佳. 双资源约束的柔性作业车间鲁棒调度方法[J]. 机械工程学报, 2024, 60(6): 114-126.

LIANG Zhizhen, WANG Xiaojia. Dual Resource Constraints Flexible Job Shop Robust Scheduling Method[J]. Journal of Mechanical Engineering, 2024, 60(6): 114-126.

参考文献

[1] 任杉，张映锋，黄彬彬. 生命周期大数据驱动的复杂产品智能制造服务新模式研究[J]. 机械工程学报，2018，54(22)：194-203. REN Shan，ZHANG Yingfeng，HUANG Binbin. New pattern of lifecycle big-data-driven smart manufacturing service for complex product[J]. Journal of Mechanical Engineering，2018，54(22)：194-203.
[2] 张映锋，郭振刚，钱成，等. 基于过程感知的底层制造资源智能化建模及其自适应协同优化方法研究[J]. 机械工程学报，2018，54(16)：1-10. ZHANG Yingfeng，GUO Zhengang，QIAN Cheng，et al. Investigation on process-aware based intelligent modeling of bottom layer manufacturing resources and self-adaptive collaborative optimization methodology[J]. Journal of Mechanical Engineering，2018，54(16)：1-10.
[3] GAO K Z，SUGANTHAN P N，PAN Q K，et al. Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion[J]. Knowledge-Based Systems，2016，109(10)：1-16.
[4] LUO X，QIAN Q，FU Y F. Improved genetic algorithm for solving flexible job shop scheduling problem[J]. Procedia Computer Science，2020，166(5)：480-485.
[5] 苑明海，张理志，周开俊，等. 基于混合遗传算法的柔性车间调度问题研究[J]. 工业工程与管理，2022，27(1)：1-17. YUAN Minghai，ZHANG Lizhi，ZHOU Kaijun，et al. Research on flexible shop scheduling based on improved hybrid genetic[J]. Industrial Engineering and Management，2022，27(1)：1-17.
[6] MENG L，ZHANG C，ZHANG B，et al. Mathematical modeling and optimization of energy-conscious flexible job shop scheduling problem with worker flexibility[J]. IEEE Access，2019，7(13)：68043-68059.
[7] ZAMISKA J R，JABER M Y，KHER H V. Worker deployment in dual resource constrained systems with a task-type factor[J]. European Journal of Operational Research，2007，177(3)：1507-1519.
[8] NELSON R T. Labor and machine limited production system[J]. Management Science，1967，13(9)：648-671.
[9] XU J，XU X，XIE S Q. Recent developments in dual resource constrained (DRC) system research[J]. European Journal of Operational Research，2011，215(2)：309-318.
[10] 李兢尧，孙树栋，黄媛，等. 求解双资源约束车间调度问题的继承式双目标遗传算法[J]. 控制与决策，2011，26(12)：1761-1767. LI Jingyao，SUN Shudong，HUANG Yuan，et al. Double-objective inherited genetic algorithm for dual resource constrained job shop[J]. Control and Decision，2011，26(12)：1761-1767.
[11] LI J Y，HUANG Y，NIU X W. A branch population genetic algorithm for dual-resource constrained job shop scheduling problem[J]. Computers & Industrial Engineering，2016，102(12)：113-131.
[12] TAN W H，YUAN X F，WANG J L，et al. A fatigue-conscious dual resource constrained flexible job shop scheduling problem by enhanced NSGA-II：An application from casting workshop[J]. Computers & Industrial Engineering，2021，160(10)：1-17.
[13] HOPP W J，TEKIN E，VAN OYEN M P. Benefits of skill chaining in serial production lines with cross-trained workers[J]. Management Science，2004，50(1)：83-98.
[14] BRUCKER P，SCHLIE R. Job-shop scheduling with multi-purpose machines[J]. Computing，1990，45(4)：369-375.
[15] PEZZELLA F，MORGANTI G，CIASCHETTI G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers and Operations Research，2008，35(10)：3202-3212.
[16] GAO K，CAO Z，ZHANG L，et al. A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems[J]. IEEE/CAA Journal of Automatica Sinica，2019，6(4)：904-916.
[17] 李红亚，彭昱忠，邓楚燕，等. GA与PSO的混合研究综述[J]. 计算机工程与应用，2018，54(2)：20-28，39. LI Hongya，PENG Yuzhong，DENG Chuyan，et al. Review of hybrids of GA and PSO[J]. Computer Engineering and Applications，2018，54(2)：20-28，39.
[18] MUDJIHARTONO P，JIAMTHAPTHAKSIN R，TANPRASERT T. Parallelized GA-PSO algorithm for solving job shop scheduling problem[C]//20162nd International Conference on Science in Information Technology (ICSITech). Balikpapan：IEEE，2016，103-108.
[19] MENG Q，ZHANG L，FAN Y. A hybrid particle swarm optimization algorithm for solving job shop scheduling problems[J]. Communications in Computer and Information Science，2016，644(10)：71-78.
[20] SUN L，LIN L，LI H J，et al. Large scale flexible scheduling optimization by a distributed evolutionary algorithm[J]. Computers & Industrial Engineering，2019，128(2)：894-904.
[21] SU X，HAN W，WU Y，et al. A robust scheduling optimization method for flight deck operations of air craft carrier with ternary interval durations[J]. IEEE Access，2018，6(11)：69918-69936.
[22] 冀凌博. 改进差分进化算法在柔性作业车间调度的应用与研究[D]. 大连：大连交通大学，2020. JI Lingbo. Application and research of improved differential evolution algorithm in flexible job shop scheduling[D]. Dalian：Dalian Jiaotong University，2020.
[23] 张源，陶翼飞，王加冕. 改进差分进化算法求解混合流水车间调度问题[J]. 中国机械工程，2021，32(6)：714-720. ZHANG Yuan，TAO Yifei，WANG Jiamian. An improved DE algorithm for solving hybrid flow-shop scheduling problems[J]. China Mechanical Engineering，2021，32(6)：714-720.
[24] VAN DE VONDER S，DEMEULEMEESTER E，HERROELEN W. A classification of predictive-reactive project scheduling procedures[J]. Journal of Scheduling，2007，10(3)：195-207.
[25] YUAN P，HAN W，SU X，et al. A dynamic scheduling method for carrier aircraft support operation under uncertain conditions based on rolling horizon strategy[J]. Applied Sciences，2018，8(9)：1-23.
[26] HAUDER V A，BEHAM A，RAGGL S，et al. Resource constrained multi-project scheduling with activity and time flexibility[J]. Computers & Industrial Engineering，2020，150(12)：106857-106870.
[27] BALOUKA N，COHEN I. A robust optimization approach for the multi-mode resource-constrained project scheduling problem[J]. European Journal of Operational Research，2021，291(2)：457-470.
[28] GU J，GU M，CAO C，et al. A novel competitive co-evolutionary quantum genetic algorithm for stochastic Job shop scheduling problem[J]. Computers & Operations Research，2010，37(5)：927-937.
[29] HORNG S C，LIN S，YANG F Y. Evolutionary algorithm for stochastic job shop scheduling with random processing time[J]. Expert Systems with Applications，2012，39(3)：3603-3610.
[30] LEI D. Simplified multi-objective genetic algorithms for stochastic Job shop scheduling[J]. Applied Soft Computing，2011，11(8)：4991-4996.
[31] JAMILI A. Robust job shop scheduling problem： Mathematical models，exact and heuristic algorithms[J]. Expert Systems with Applications，2016，55(12)：341-350.
[32] 肖世昌，吴自高，孙树栋，等. 双资源约束的鲁棒Job Shop调度问题研究[J]. 机械工程学报，2021，57(4)：227-239. XIAO Shichang，WU Zigao，SUN Shudong，et al. Research on the dual-resource constrained robust job shop scheduling problems[J]. Journal of Mechanical Engineering，2021，57(4)：227-239.
[33] 汪俊亮，张洁，秦威，等. 加工时间不确定的柔性作业车间鲁棒调度方法[J]. 中国机械工程，2015，26(5)：627-632. WANG Junliang，ZHANG Jie，QIN Wei，et al. Roubust scheduling of flexible job shop with uncertain processing time[J]. China Mechanical Engineering，2015，26(5)：627-632.
[34] 万兵，苏析超，郭放，等. 不确定性工时下甲板作业的前摄性鲁棒调度[J]. 航空学报，2022，43(1)：1-18. WANG Bing，SU Xichao，GUO Fang，et al. A study for proactive robust scheduling of aircraft carrier flight deck operations with uncertain activity durations[J]. Acta Aeronautica et Astronautica Sinica，2022，43(1)：1-18.
[35] 魏鑫，张泽群，唐敦兵，等. 面向节能的导弹结构件混线生产作业车间多目标调度研究[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.
[36] KACEM I，HAMMADI S，BORNE P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Trans. Systems，Man，and Cybernetics，Part C，2002，32(1)：1-13.
[37] 陈强，王宇嘉，林炜星，等. 改进粒子群算法求解分布式柔性车间调度问题[J]. 电子科技，2021，34(10)：63-68. CHEN Qiang，WANG Yujia，LIN Weixing，et al. An improve particle swarm optimization algorithm for distribution and flexible job-shop scheduling problem[J]. Electronic Science and Technology，2021，34(10)：63-68.