Journal of South China University of Technology(Natural Science) >

2024 , Vol. 52 >Issue 10: 51 - 63

DOI: https://doi.org/10.12141/j.issn.1000-565X.230722

Computer Science & Technology

A Batch Scheduling Method of Flexible Job-Shop with Partially Out-of-Ordered Execute Operation

  • LIU Ning ,
  • HUA Tianbiao ,
  • WANG Gao ,
  • CHEN Faming
Expand
  • 1.College of Information Science and Technology, Jinan University, Guangzhou 510632, Guangdong, China
    2.School of Intelligent Systems Science and Engineering, Jinan University, Zhuhai 519070, Guangdong, China

Received date: 2023-11-22

  Online published: 2024-02-12

Supported by

the General Program of the National Natural Science Foundation of China(62172188)

Fold

Abstract

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.

Key words： out-of-order execute operation; batch scheduling; flexible job-shop; multi-objective optimization; NSGA-Ⅱ

Cite this article

LIU Ning , HUA Tianbiao , WANG Gao , CHEN Faming . A Batch Scheduling Method of Flexible Job-Shop with Partially Out-of-Ordered Execute Operation[J]. Journal of South China University of Technology(Natural Science), 2024 , 52(10) : 51 -63 . DOI: 10.12141/j.issn.1000-565X.230722

References

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．
Options
Outlines

/

〈 〉