Flexible Job Shop Scheduling: Comparison
View Latest Version
Please note this is a comparison between Version 2 by Rita Xu and Version 1 by Zhengying Cai.

In many flexible job shop scheduling problems, transportation scheduling problems are involved, increasing the difficulty in problem-solving.

  • flexible job shop scheduling
  • transportation scheduling
  • state transition diagram

1. Introduction

At present, the flexible job shop scheduling (FJSS) problem with transportation constraints is gaining more and more attention [1[1][2],2], with it comprising many machines and vehicles, where a series of jobs have to be arranged and a series of transportation tasks have to be handled. This kind of system is very popular in modern industry and smart logistics systems [3]. Until now, all kinds of vehicles, especially automated guided vehicles (AGVs) [4] and mobile robots (MRs) [5], have been widely applied to support flexible job shop scheduling systems and are integrated with them. Such vehicles can help transport raw materials or products from a dock to a storage facility or help transport all kinds of materials between different areas in a warehouse or on the production line [6]. In this environment, jobs are kept for transporting between different areas to be handled until all transportations are finished. Due to the deep involvement of vehicles, the flexible job shop scheduling problem with transportation constraints has become increasingly important.
In a flexible job shop scheduling problem with transportation constraints, there are two subproblems, namely, the job shop scheduling problem (JSSP) and the transportation scheduling problem (TSP) [7]. These two problems are interrelated and inseparable, and in studying one of them in isolation, one cannot obtain the optimal solution to the entire problem [8]. Some scholars choose to divide this complex problem into two simpler subproblems to solve them separately, thereby reducing the difficulty of solving the problem. For example, the job shop scheduling task is solved first without transportation constraints, and then, the vehicle transportation tasks are sequentially addressed [9]. However, this also leads to the loss of reference value in the solution results since a separate solution to this problem involves two kinds of scheduling operations where the separated scheduling tasks are closely interrelated.
The flexible job shop scheduling problem with transportation constraints is NP-hard since its two subproblems are NP-hard, i.e., the job shop scheduling problem (JSSP) and the vehicle scheduling problem (VSP) [10]. The latter is also called a transportation scheduling problem or a load/unload problem. Many researchers have proposed all kinds of artificial intelligence algorithms to solve these kinds of complex problems, i.e., genetic algorithms (GAs) [2[2][4],4], particle swarm optimization (PSO) [6], simulated annealing (SA) [6], ant colony optimization (ACO) [8], fuzzy logic (FL) [11], deep learning (DL), artificial neural networks (ANNs) [12], artificial bee colony (ABC) [13], and adaptive memetic algorithms (AMAs) [14]. The experimental results of these studies revealed that these artificial intelligence algorithms can obtain satisfactory results in job shop scheduling problems. In recent years, a unicellular organism has given us great inspiration, Physarum polycephalum [15]. It can generate thousands of mycelia to search for food and shrink into the most refined mycelium structure after finding food.

2. Flexible Job Shop Scheduling

Traditional job shop scheduling problems often neglect the travel times or assume that unlimited transport resources are available. These cases are often inconsistent with engineering practice because vehicle transportation tasks are very common in the FJSS problem. If the vehicle transportation problem cannot be fully considered, the optimal solution to the job scheduling problem will not be obtained. The job shop scheduling problem with transportation constraints needs to decide the machine scheduling, vehicle scheduling, and transportation assignment. Ref. [2] designed a multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation. Solving these interrelated problems is helpful in improving the operational performance of the job scheduling system. Refs. [4,16][4][16] proposed an integrated scheduling method of machines and automated guided vehicles in a flexible job shop environment based on genetic algorithms. The use of mobile robots also brings transportation issues. The authors of [5] modeled the job shop scheduling problem as a mixed integer linear programming (MILP) model and considered the routing problem of mobile robots. A mixture of job shop scheduling systems and transportation scheduling systems also increases the factors considered during scheduling. Ref. [7] produced a job shop scheduling joint consideration of production, transport, and storage/retrieval systems. Ref. [9] addressed the energy-efficient job shop scheduling problem with transport resources, considering speed-adjustable resources. These works revealed that the benefits of integrating job shop scheduling and transportation scheduling can greatly improve the job completion time and operational performance. Many research works often independently study job shop scheduling problems and vehicle transportation problems, such as dynamic job shop scheduling [12[12][17],17], interval job shop [13], energy-efficient distributed flexible job shop scheduling [14], limited waiting time constraint on a hybrid flowshop [18], embedded environment [19], and flexible job shop scheduling [20]. Ref. [21] presented a dynamic configuration method of flexible workshop resources based on an imperialist competitive algorithm hybrid neighborhood search (IICA-NS). Although doing so can reduce the difficulty of solving a problem, it leads to a lack of coordination since sub-optimal solutions and cannot reach global optimization. Recent research progress indicates that neglecting transportation scheduling in job shop scheduling may result in serious consequences [22], such as low resource utilization, unexpected bottlenecks, high intermediate inventories and operational costs, and low user satisfaction. The integration of job shop scheduling and vehicle scheduling makes the scheduling problem more challenging since the multi-objective decisions and constraints become more complex [17]. Ref. [23] employed a multi-agent system simulation-based approach for collision avoidance in an integrated job shop scheduling problem with transportation tasks. Many researchers have demonstrated that there are a lot of conflicting factors in coordinating job shop scheduling and transportation scheduling. For example, ref. [24] introduced an approach to the integrated scheduling of flexible job shop scheduling, considering conflict-free routing problems. In engineering practice, a flexible job shop scheduling task often transports materials from one workstation to another or from a load/unload area to another, which are inevitably involved in vehicle transportation scheduling [25]. Now, current mainstream scientists consider this kind of FJSS problem to be multi-objective with many conflicting factors and NP-hard, so traditional, exact approaches can only be applied to solve small-sized cases [1]. It is very important and challenging to design efficient algorithms to address it in large-sized cases, such as simulated annealing (SA) [6] and fuzzy logic (FL) [11]. Among them, swarm intelligence (SI) algorithms have received great attention [23[23][26],26], i.e., genetic algorithms (GAs) [2[2][4][16],4,16], particle swarm optimization (PSO) [6[6][19],19], ant colony optimization (ACO) [8], deep learning (DL), artificial neural networks (ANNs) [12,27][12][27], artificial bee colony (ABC) [13], adaptive memetic algorithms (AMAs) [14], migrating birds optimization [17], grey wolf optimization (GWO) [20], quantum cat swarm optimization [22], artificial slime mold [28], artificial Physarum swarm [29], coronavirus herd immunity [30], artificial plant community [31[31][32],32], whale optimization [33], artificial algae [34], and the Jaya algorithm [35]. However, these swarm intelligence algorithms are also prone to fall into local optimization prematurely, and some scholars have tried to improve algorithm performance using hybrid algorithms [6,36][6][36]. In recent years, a unique creature has given us new inspiration. Natural Physarum polycephalum can generate countless mycelia for expansion and then shrink into the optimal network structure after finding food [15]. Some researchers have tried to simulate their search behavior [28,29][28][29], but the current research works have not fully explored the core functions of the Physarum polycephalum colony, i.e., swarm learning, expanding the population size to increase the search ability, and shrinking the population size to optimize solution results.

References

  1. Abderrahim, M.; Bekrar, A.; Trentesaux, D.; Aissani, N.; Bouamrane, K. Bi-local search based variable neighborhood search for job-shop scheduling problem with transport constraints. Optim. Lett. 2022, 16, 255–280.
  2. Homayouni, S.M.; Fontes, D.B.M.M.; Goncalves, J.F. A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation. Int. Trans. Oper. Res. 2023, 30, 688–716.
  3. Homayouni, S.M.; Fontes, D.B.M.M. Production and transport scheduling in flexible job shop manufacturing systems. J. Glob. Optim. 2021, 79, 463–502.
  4. Meng, L.L.; Cheng, W.Y.; Zhang, B.; Zou, W.Q.; Fang, W.K.; Duan, P. An improved genetic algorithm for solving the multi-AGV flexible job shop scheduling problem. Sensors 2023, 23, 3815.
  5. Yao, Y.J.; Liu, Q.H.; Li, X.Y.; Gao, L. A novel MILP model for job shop scheduling problem with mobile robots. Robot. Comput. Integr. Manuf. 2023, 81, 102506.
  6. Fontes, D.B.M.M.; Homayouni, S.M.; Goncalves, J.F. A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources. Eur. J. Oper. Res. 2023, 306, 1140–1157.
  7. Fontes, D.B.M.M.; Homayouni, S.M.; Resende, M.G.C. Job-shop scheduling-joint consideration of production, transport, and storage/retrieval systems. J. Comb. Optim. 2022, 44, 1284–1322.
  8. Thiruvady, D.; Nguyen, S.; Shiri, F.; Zaidi, N.; Li, X.D. Surrogate-assisted population based ACO for resource constrained job scheduling with uncertainty. Swarm Evol. Comput. 2022, 69, 101029.
  9. Fontes, D.B.M.M.; Homayouni, S.M.; Fernandes, J.C. Energy-efficient job shop scheduling problem with transport resources considering speed adjustable resources. Int. J. Prod. Res. 2023.
  10. Yunusoglu, P.; Yildiz, S.T. Solving the flexible job shop scheduling and lot streaming problem with setup and transport resource constraints. Int. J. Syst. Sci. Oper. Logist. 2023, 10, 2221072.
  11. Hajibabaei, M.; Behnamian, J. Fuzzy cleaner production in assembly flexible job-shop scheduling with machine breakdown and batch transportation: Lagrangian relaxation. J. Comb. Optim. 2023, 45, 112.
  12. Yang, Z.; Bi, L.; Jiao, X.G. Combining reinforcement learning algorithms with graph neural networks to solve dynamic job shop scheduling problems. Processes 2023, 11, 1571.
  13. Diaz, H.; Palacios, J.J.; Gonzalez-Rodriguez, I.; Vela, C.R. An elitist seasonal artificial bee colony algorithm for the interval job shop. Integr. Comput. Aided Eng. 2023, 30, 223–242.
  14. Li, R.; Gong, W.Y.; Wang, L.; Lu, C.; Zhuang, X.Y. Surprisingly popular-based adaptive memetic algorithm for energy-efficient distributed flexible job shop scheduling. IEEE Trans. Cybern. 2023. early access.
  15. Kippenberger, S.; Pipa, G.; Steinhorst, K.; Zoller, N.; Kleemann, J.; Ozistanbullu, D.; Ozistanbullu, D.; Scheller, B. Learning in the single-cell organism Physarum polycephalum: Effect of propofol. Int. J. Mol. Sci. 2023, 24, 6287.
  16. Chaudhry, I.A.; Rafique, A.F.; Boudjemline, A. Integrated scheduling of machines and automated guided vehicles (AGVs) in flexible job shop environment using genetic algorithms. Int. J. Ind. Eng. Comput. 2022, 13, 343–362.
  17. Wei, L.X.; He, J.X.; Guo, Z.Y.; Hu, Z.Y. A multi-objective migrating birds optimization algorithm based on game theory for dynamic flexible job shop scheduling problem. Expert Syst. Appl. 2023, 227, 120268.
  18. Shim, S.O.; Jeong, B.; Bang, J.Y.; Park, J. Scheduling jobs with a limited waiting time constraint on a hybrid flowshop. Processes 2023, 11, 1846.
  19. Zarrouk, R.; Ben Daoud, W.; Mahfoudhi, S.; Jemai, A. Embedded PSO for Solving FJSP on embedded environment (Industry 4.0 Era). Appl. Sci. 2022, 12, 2829.
  20. Kong, X.H.; Yao, Y.H.; Yang, W.Q.; Yang, Z.L.; Su, J.Z. Solving the flexible job shop scheduling problem using a discrete improved grey wolf optimization algorithm. Machines 2022, 10, 1100.
  21. Su, X.; Zhang, C.Y.; Ji, W.X. Dynamic configuration method of flexible workshop resources based on IICA-NS algorithm. Processes 2022, 10, 2394.
  22. Song, H.C.; Liu, P. A study on the optimal flexible job-shop scheduling with sequence-dependent setup time based on a hybrid algorithm of improved quantum cat swarm optimization. Sustainability 2022, 14, 9547.
  23. Sanogo, K.; Benhafssa, A.M.; Sahnoun, M.; Bettayeb, B.; Abderrahim, M.; Bekrar, A. A multi-agent system simulation based approach for collision avoidance in integrated job-shop scheduling problem with transportation tasks. J. Manuf. Syst. 2023, 68, 209–226.
  24. Sun, J.C.; Xu, Z.F.; Yan, Z.H.; Liu, L.L.; Zhang, Y.X. An approach to integrated scheduling of flexible job-shop considering conflict-free routing problems. Sensors 2023, 23, 4526.
  25. Liu, Q.H.; Wang, N.J.; Li, J.; Ma, T.T.; Li, F.P.; Gao, Z.J. Research on flexible job shop scheduling optimization based on segmented AGV. CMES-Comput. Model. Eng. Sci. 2023, 134, 2073–2091.
  26. Cai, Z.; Zhang, Y.; Wu, M.; Cai, D. An entropy-robust optimization of mobile commerce system based on multi-agent system. Arab. J. Sci. Eng. 2016, 41, 3703–3715.
  27. Inal, A.F.; Sel, C.; Aktepe, A.; Turker, A.K.; Ersoz, S. A multi-agent reinforcement learning approach to the dynamic job shop scheduling problem. Sustainability 2023, 15, 8262.
  28. Cai, Z.; Xiong, Z.; Wan, K.; Xu, Y.; Xu, F. A node selecting approach for traffic network based on artificial slime mold. IEEE Access 2020, 8, 8436–8448.
  29. Cai, Z.; Yang, Y.; Zhang, X.; Zhou, Y. Design a robust logistics network with an artificial Physarum swarm algorithm. Sustainability 2022, 14, 14930.
  30. Ma, X.D.; Bi, L.; Jiao, X.G.; Wang, J.J. An efficient and improved coronavirus herd immunity algorithm using knowledge-driven variable neighborhood search for flexible job-shop scheduling problems. Processes 2023, 11, 1826.
  31. Cai, Z.; Jiang, S.; Dong, J.; Tang, S. An artificial plant community algorithm for the accurate range-free positioning of wireless sensor networks. Sensors 2023, 23, 2804.
  32. Cai, Z.; Ma, Z.; Zuo, Z.; Xiang, Y.; Wang, M. An image edge detection algorithm based on an artificial plant community. Appl. Sci. 2023, 13, 4159.
  33. Zhang, S.J.; Gu, X.S. A discrete whale optimization algorithm for the no-wait flow shop scheduling problem. Meas. Control 2023.
  34. Sahman, M.A.; Korkmaz, S. Discrete artificial algae algorithm for solving job-shop scheduling problems. Knowl. Based Syst. 2022, 256, 109711.
  35. Xie, F.W.; Li, L.L.; Li, L.; Huang, Y.P.; He, Z.X. A decomposition-based multi-objective Jaya algorithm for lot-streaming job shop scheduling with variable sublots and intermingling setting. Expert Syst. Appl. 2023, 228, 120402.
  36. Wen, X.Y.; Fu, Y.Z.; Yang, W.C.; Wang, H.Q.; Zhang, Y.Y.; Sun, C.Y. An effective hybrid algorithm for joint scheduling of machines and AGVs in flexible job shop. Meas. Control 2023.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
Video Production Service
Feedback