收稿日期: 2023-11-22
网络出版日期: 2024-02-12
基金资助
国家自然科学基金面上项目(62172188);珠海市科技计划项目(2220004002542)
A Batch Scheduling Method of Flexible Job-Shop with Partially Out-of-Ordered Execute Operation
Received date: 2023-11-22
Online published: 2024-02-12
Supported by
the General Program of the National Natural Science Foundation of China(62172188)
实际的车间调度问题往往具有更高的复杂度,调度算法需要考虑更多的约束条件,因此增加了问题的求解难度。为解决柔性作业车间批量调度场景中不同批次、不同工序之间可以无序加工的难题,进而突破现有车间机器使用率低、同类型机器负载不均衡的难点,文中构建了一种面向部分工序无序加工的柔性作业车间等量分批调度模型。首先,基于广泛使用的快速非支配排序遗传算法(NSGA-Ⅱ),提出了一种融合批次、批量和工序排序信息的两段编码结构,采用优先级规则方法获得初始种群,并以最小化完工时间、机器负载均衡率、机器总负荷为优化目标,采用贪心算法求解模型最优值,进而动态构建不同批次的加工路径;然后,对优化目标函数进行排序,再逐步加入非支配排序过程,以解决多个优化目标函数之间难以同时优化的问题,提高求解效率;最后,以某印刷包装企业的木制品加工车间为例,面向现场作业信息,采用仿真手段实现调度过程。结果表明,与优先级调度规则相比,文中所提方法的完工时间平均缩短了6.6%、机器负载均衡方差平均减小了10.7%,文中所提方法的机器负载均衡方差比遗传算法平均减小了53.3%,从而验证了文中方法的可行性,且该方法可以满足印刷包装企业柔性作业车间的高性能调度需求。
柳宁 , 华天标 , 王高 , 陈法明 . 面向部分工序无序加工的柔性作业车间批量调度方法[J]. 华南理工大学学报(自然科学版), 2024 , 52(10) : 51 -63 . DOI: 10.12141/j.issn.1000-565X.230722
Actual job-shop scheduling problems often exhibit high complexity, and the scheduling algorithm needs to consider more constraints, so it increases the difficulty of solving the problem. To address the challenge of out-of-order processing for different batches and processes in the flexible job shop’s batch scheduling scenario, it is necessary to overcome the issues related to low utilization rates of existing job shop machines and unbalanced workload distribution among machines of the same type. Therefore, this paper constructed a flexible job shop equal batch scheduling model that incorporates partially out-of-order execution of processes. Firstly, based on the widely adopted fast non-dominated sorting genetic algorithm (NSGA-Ⅱ), this paper introduced a novel two-stage coding structure that integrates batch information and process sorting information. The priority rule method was used to obtain the initial population, and with minimizing the completion time, machine load equilibrium rate and total machine load as the optimization goal, the greedy algorithm was used to obtain the optimal value of the model, and then the processing path of different batches was dynamically constructed.Then, the optimized objective functions were sorted, and the non-dominant sorting process was added step by step to solve the problem that multiple optimized objective functions are difficult to optimize at the same time and improve the solving efficiency. Finally, taking the wood products processing workshop of a printing and packaging enterprise as an example, the scheduling process was realized according to the field operation information. The results show that, compared with the priority scheduling rules, the completion time of the proposed method is shortened by 6.6%, the average machine load balancing variance is reduced by 10.7%, and the average of the proposed method is reduced by 53.3% compared with the genetic algorithm, thus verifying the feasibility of the method. This method can meet the high performance scheduling requirements of the flexible workshop of printing and packaging enterprises.
| 1 | YI H, QU T, ZHANG K,et al .Production logistics in industry 3.x:bibliometric analysis,frontier case study,and future directions[J].Systems,2023,11(7):371/1-30. |
| 2 | LI M, LI M, GUO D,et al .Real-time data-driven out-of-order synchronization for production and intralogistics in multiresource-constrained assembly systems[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2023,53(12):7513-7525. |
| 3 | BRUCKER P, SCHLIE R .Job-shop scheduling with multi-purpose machines[J].Computing,1990,45:369-375. |
| 4 | 徐本柱,费晓璐,章兴玲 .柔性作业车间批量划分与并行调度优化[J].计算机集成制造系统,2016,22(8):1953-1964. |
| XU Benzhu, FEI Xiaolu, ZHANG Xingling .Batch division and parallel scheduling optimization of flexible job shop[J].Computer Integrated Manufacturing System,2016,22(8):1953-1964. | |
| 5 | ZHAO B, GAO J, CHEN K,et al .Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines[J].Journal of Intelligent Manufacturing,2018,29(1):93-108. |
| 6 | JAMRUS T, CHIEN C F,GEN M,et al .Hybrid particle swarm optimization combined with genetic operators for flexible job-shop scheduling under uncertain processing time for semiconductor manufacturing[J].IEEE Transactions on Semiconductor Manufacturing,2017,31(1):32-41. |
| 7 | SUN K, ZHENG D, SONG H,et al .Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system[J].Expert Systems with Applications,2023,215:119359/1-18. |
| 8 | LI Y, CHEN X, AN Y,et al .Integrating machine layout,transporter allocation and worker assignment into job-shop scheduling solved by an improved non-dominated sorting genetic algorithm[J].Computers & Industrial Engineering,2023,179:109169/1-19. |
| 9 | ZHANG F, MEI Y, NGUYEN S,et al .Multitask multiobjective genetic programming for automated scheduling heuristic learning in dynamic flexible job-shop scheduling[J].IEEE Transactions on Cybernetics,2023,53(7):4473-4486. |
| 10 | BRAUNE R, BENDA F, DOERNER K F,et al .A genetic programming learning approach to generate dispatching rules for flexible shop scheduling problems[J].International Journal of Production Economics,2022,243:108342/1-13. |
| 11 | SONG W, CHEN X, LI Q,et al .Flexible job-shop scheduling via graph neural network and deep reinforcement learning[J].IEEE Transactions on Industrial Informatics,2022,19(2):1600-1610. |
| 12 | 张凯,毕利,焦小刚 .集成强化学习算法的柔性作业车间调度问题研究[J].中国机械工程,2023,34(2):201-207. |
| ZHANG Kai, BI Li, JIAO Xiaogang .Research on flexible job-shop scheduling problems with integrated reinforcement learning algorithm[J].China Mechanical Engineering,2023,34(2):201-207. | |
| 13 | LI Y, WANG A, ZHANG S .A batch scheduling technique of flexible job-shop based on improved genetic algorithm[C]∥ Proceedings of 2022 IEEE International Conference on Mechatronics and Automation.Guilin:IEEE,2022:1463-1467. |
| 14 | 刘雪红,段程,王磊 .基于改进候鸟算法的柔性作业车间分批调度问题[J].计算机集成制造系统,2021,27(11):3185-3195. |
| LIU Xuehong, DUAN Cheng, WANG Lei .Flexible job shop scheduling with lot streaming based on improved migrating birds optimizetion algorithm[J].Computer Integrated Manufacturing System,2021,27(11):3185-3195. | |
| 15 | 闫富乾,陈浩杰,丁国富,等 .求解柔性分批调度问题的双层搜索框架入侵杂草算法[J].计算机集成制造系统,2023,29(2):556-567. |
| YAN Fuqian, CHEN Haojie, DING Guofu,et al . Improved invasive weed algorithm based on double layer search framework for flexible batch scheduling problem[J].Computer Integrated Manufacturing System,2023,29(2):556-567. | |
| 16 | DEB K, PRATAP A, AGARWAL S,et al .A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197. |
| 17 | 李树勋,胡迎港,李成,等 .基于代理模型的轴流式调节阀阀体型线优化[J].华南理工大学学报(自然科学版),2023,51(3):41-52. |
| LI Shuxun, HU Yinggang, LI Cheng,et al .Optimization of body profile line of axial flow control valve based on surrogate model[J].Journal of South China University of Technology (Natural Science Edition),2023,51(3):41-52. | |
| 18 | VERMA S, PANT M, SNASEL V .A comprehensive review on NSGA-Ⅱ for multi-objective combinatorial optimization problems[J].IEEE Access,2021,9:57757-57791. |
| 19 | 郑锦灿,邵立珍,雷雪梅 .一种基于改进NSGA-Ⅱ的多目标绿色柔性作业车间调度方法[J].制造技术与机床,2023(1):145-152. |
| ZHENG Jincan, SHAO Lizhen, LEI Xuemei .A multi-objective green flexible job shop scheduling method based on improved NSGA-Ⅱ algorithm[J].Manufacturing Technology & Machine Tool,2023(1):145-152. | |
| 20 | 尹爱军,闫文涛,张厚望 .面向多目标柔性作业车间调度的强化学习NSGA-Ⅱ算法[J].重庆大学学报, 2022,45(10):113-123. |
| YIN Aijun, YAN Wentao, ZHANG Houwang . Reinforcement learning NSGA-Ⅱ for multi-objective flexible job shop scheduling[J].Journal of Chongqing University,2022,45(10):113-123. | |
| 21 | 王亚昆,刘应波,吴永明,等 .改进NSGA-Ⅱ算法求解考虑运输约束的柔性作业车间节能调度问题[J].计算机集成制造系统,2023,29(9):3028-3040. |
| WANG Yakun, LIU Yingbo, WU Yongming,et al .Improved NSGA-Ⅱ algorithm to solve energy-saving sche-duling problem of flexible job shop considering transpor-tation constraints[J].Computer Integrated Manufactu-ring System,2023,29(9):3028-3040. | |
| 22 | MA H, ZHANG Y, SUN S,et al .A comprehensive survey on NSGA-Ⅱ for multi-objective optimization and applications[J].Artificial Intelligence Review,2023,56:15217-15270. |
| 23 | 吴秀丽,李雨馨,匡源,等 .改进迭代贪婪算法求解可重入流水车间调度问题[J].计算机集成制造系统,2024,30(7):2364-2380. |
| WU Xiuli, LI Yuxin, KUANG Yuan,et al .Improved iterative greedy algorithm for reentrant flow shop scheduling problem[J].Computer Integrated Manufacturing Systems,2024,30(7):2364-2380. |
/
| 〈 |
|
〉 |