Solving Multi-Ffactory Intelligent Network Scheduling Problem in Job Shop Production Environment Using Improved Lagrangian Relaxation Algorithm

Document Type : Research Paper

Authors

1 PhD student in Industrial Engineering, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamadan, Iran

2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

Abstract

In this paper, the problem of real-time scheduling of multi-factury production network in the smart manufacturing system with job shop environment is studied. In this smart manufacturing system, a number of independently owned factories are joined together to form a multi-agent production network, which is also called a virtual production network. In such a network, each factory focuses on its interests and communicates with each other by sharing information such as machine breakdowns and job transfers. Therefore, it can be stated that studying the problem of distributed scheduling in the environment of smart factories is important and will have a significant effect on obtaining desirable and ideal results. At first, a bi-objective mixed integer linear programming model is presented; then an approach to solve the dynamic real-time scheduling problem is proposed. Considering the successful applications of the Lagrangian relaxation algorithm in solving scheduling problems, in this research, the improved Lagrangian relaxation algorithm is used to solve the problem. To examine the performance of the proposed algorithm, its results were compared with solving the original model that was solved by the augmented epsilon constraint method. The obtained results showed that the proposed Lagrangian relaxation algorithm has a better performance than the augmented epsilon constraint method

Keywords

Main Subjects

References

  • E. Mouayni, G. Demesure, H. B.-E. Haouzi, P. Charpentier, and A. Siadat, “Jobs scheduling within Industry 4.0 with consideration of worker’s fatigue and reliability using Greedy Randomized Adaptive Search Procedure,” IFAC-PapersOnLine, vol. 52, no. 19, pp. 85–90, 2019. https://doi.org/10.1016/j.ifacol.2019.12.114.
  • Sokolov, D. Ivanov, and A. Dolgui, Eds., Scheduling in Industry 4.0 and Cloud Manufacturing. Springer International Publishing, 2020. https://doi.org/10.1007/978-3-030-43177-8.
  • Ivanov, A. Dolgui, B. Sokolov, F. Werner, and M. Ivanova, “A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory industry 4.0,” International Journal of Production Research, vol. 54, no. 2, pp. 386–402, 2016. https://doi.org/10.1080/00207543.2014.999958.
  • H. Chung, H. C. W. Lau, G. T. S. Ho, and W. H. Ip, “Optimization of system reliability in multi-factory production networks by maintenance approach,” Expert Systems with Applications, vol. 36, no. 6, pp. 10188–10196, 2009. https://doi.org/10.1016/j.eswa.2008.12.014.
  • Shen and D. H. Norrie, “Agent-Based Systems for Intelligent Manufacturing: A State-of-the-Art Survey,” Knowledge and Information Systems, vol. 1, no. 2, pp. 129–156, 1999. https://doi.org/10.1007/BF03325096.
  • Dhaenens-Flipo and G. Finke, “An Integrated Model for an Industrial Production–Distribution Problem,” IIE Transactions, vol. 33, no. 9, pp. 705–715, 2001. https://doi.org/10.1080/07408170108936867.
  • -Y. Lee, “Two-machine flowshop scheduling with availability constraints,” European Journal of Operational Research, vol. 114, no. 2, pp. 420–429, 1999. https://doi.org/10.1016/S0377-2217(97)00452-9.
  • Wang and J. Yu, “An effective heuristic for flexible job-shop scheduling problem with maintenance activities,” Computers & Industrial Engineering, vol. 59, no. 3, pp. 436–447, 2010. https://doi.org/10.1016/j.cie.2010.05.016.
  • Allaoui and A. Artiba, “Scheduling two-stage hybrid flow shop with availability constraints,” Computers & Operations Research, vol. 33, no. 5, pp. 1399–1419, May 2006, https://doi.org/10.1016/j.cor.2004.09.034.
  • G. Hall and C. N. Potts, “Rescheduling for New Orders,” Operations Research, vol. 52, no. 3, pp. 440–453, 2004. https://doi.org/10.1287/opre.1030.0101.
  • Cakici, S. J. Mason, J. W. Fowler, and H. N. Geismar, “Batch scheduling on parallel machines with dynamic job arrivals and incompatible job families,” International Journal of Production Research, vol. 51, no. 8, pp. 2462–2477, 2013. https://doi.org/10.1080/00207543.2012.748227.
  • A. Holloway and R. T. Nelson, “Job Shop Scheduling with Due Dates and Variable Processing Times,” Management Science, vol. 20, no. 9, pp. 1264–1275, 1974. https://doi.org/10.1287/mnsc.20.9.1264.
  • Fang and Y. Xi, “A rolling horizon job shop rescheduling strategy in the dynamic environment,” The International Journal of Advanced Manufacturing Technology, vol. 13, no. 3, pp. 227–232, 1997. https://doi.org/10.1007/BF01305874.
  • A. Adibi, M. Zandieh, and M. Amiri, “Multi-objective scheduling of dynamic job shop using variable neighborhood search,” Expert Systems with Applications, vol. 37, no. 1, pp. 282–287, 2010. https://doi.org/10.1016/j.eswa.2009.05.001.
  • B. S. Sreekara Reddy, Ch. Ratnam, G. Rajyalakshmi, and V. K. Manupati, “An effective hybrid multi objective evolutionary algorithm for solving real time event in flexible job shop scheduling problem,” Measurement, vol. 114, pp. 78–90, 2018. https://doi.org/10.1016/j.measurement.2017.09.022.
  • Zhang and T. N. Wong, “Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach,” International Journal of Production Research, vol. 55, no. 11, pp. 3173–3196, 2017. https://doi.org/10.1080/00207543.2016.1267414.
  • Wang, C. Luo, and J. Cai, “A Variable Interval Rescheduling Strategy for Dynamic Flexible Job Shop Scheduling Problem by Improved Genetic Algorithm,” Journal of Advanced Transportation, 2017. https://doi.org/10.1155/2017/1527858.
  • -N. Shen and X. Yao, “Mathematical modeling and multi-objective evolutionary algorithms applied to dynamic flexible job shop scheduling problems,” Information Sciences, vol. 298, pp. 198–224, 2015. https://doi.org/10.1016/j.ins.2014.11.036.
  • Zhang, J. Wang, and Y. Liu, “Game theory based real-time multi-objective flexible job shop scheduling considering environmental impact,” Journal of Cleaner Production, vol. 167, pp. 665–679, 2017. https://doi.org/10.1016/j.jclepro.2017.08.068.
  • Zhang, L. Gao, and X. Li, “A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problems with disruptions,” The International Journal of Advanced Manufacturing Technology, vol. 65, 2012. https://doi.org/10.1007/s00170-012-4245-6.
  • Gao, F. Yang, M. Zhou, Q. Pan, and P. N. Suganthan, “Flexible Job-Shop Rescheduling for New Job Insertion by Using Discrete Jaya Algorithm,” IEEE Transactions on Cybernetics, vol. 49, no. 5, pp. 1944–1955, 2019. https://doi.org/10.1109/TCYB.2018.2817240.
  • Wen and W. Cao, “Real-time job-shop scheduling model based on RFID,” 2017, pp. 204–208. https://doi.org/10.1109/CIAPP.2017.8167208.
  • Kundakcı and O. Kulak, “Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem,” Computers and Industrial Engineering, vol. 96, no. C, pp. 31–51, 2016. https://doi.org/10.1016/j.cie.2016.03.011.
  • Wang, J. Yang, Y. Zhang, S. Ren, and Y. Liu, “Infinitely repeated game based real-time scheduling for low-carbon flexible job shop considering multi-time periods,” Journal of Cleaner Production, vol. 247, p. 119093, 2020. https://doi.org/10.1016/j.jclepro.2019.119093.
  • Wang, J. Zhang, and S. Yang, “An improved particle swarm optimization algorithm for dynamic job shop scheduling problems with random job arrivals,” Swarm and Evolutionary Computation, vol. 51, p. 100594, 2019. https://doi.org/10.1016/j.swevo.2019.100594.
  • Wang, Y. Liu, S. Ren, C. Wang, and W. Wang, “Evolutionary game based real-time scheduling for energy-efficient distributed and flexible job shop,” Journal of Cleaner Production, vol. 293, p. 126093, 2021. https://doi.org/10.1016/j.jclepro.2021.126093.
  • Wang et al., “Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning,” Computer Networks, vol. 190, p. 107969, 2021. https://doi.org/10.1016/j.comnet.2021.107969.
  • Luo, S. Wang, B. Yang, and L. Yi, “An improved deep reinforcement learning approach for the dynamic job shop scheduling problem with random job arrivals,” Journal of Physics: Conference Series, vol. 1848, no. 1, p. 012029, 2021. https://doi.org/10.1088/1742-6596/1848/1/012029.
  • Soleimani, P. Chhetri, A. M. Fathollahi-Fard, S. M. J. Mirzapour Al-e-Hashem, and S. Shahparvari, “Sustainable closed-loop supply chain with energy efficiency: Lagrangian relaxation, reformulations and heuristics,” Ann Oper Res, vol. 318, no. 1, pp. 531–556, 2022. https://doi.org/10.1007/s10479-022-04661-z.
  • Huang, Y. Wang, S. Jia, Z. Liu, and S. Wang, “A Lagrangian relaxation approach for the electric bus charging scheduling optimisation problem,” Transportmetrica A: Transport Science, vol. 0, no. 0, pp. 1–24, 2022. https://doi.org/10.1080/23249935.2021.2023690.
  • Song, W. Luo, P. Xu, J. Wei, and X. Qi, “An improved Lagrangian relaxation algorithm based SDN framework for industrial internet hybrid service flow scheduling,” Sci Rep, vol. 12, no. 1, Art. no. 1, 2022. https://doi.org/10.1038/s41598-022-07125-3.
  • Keshavarz-Ghorbani and S. H. R. Pasandideh, “A Lagrangian relaxation algorithm for optimizing a bi-objective agro-supply chain model considering CO2 emissions,” Ann Oper Res, vol. 314, no. 2, pp. 497–527, 2022. https://doi.org/10.1007/s10479-021-03936-1.
  • Hendalianpour, M. Fakhrabadi, M. S. Sangari, and J. Razmi, “A combined benders decomposition and Lagrangian relaxation algorithm for optimizing a multi-product, multi-level omni-channel distribution system,” Scientia Iranica, vol. 29, no. 1, pp. 355–371, 2022. https://doi.org/10.24200/sci.2020.53644.3349.
  • Held and R. M. Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees,” Operations Research, vol. 18, no. 6, pp. 1138–1162, 1970. https://doi.org/10.1287/opre.18.6.1138.
  • Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees: Part II,” Mathematical Programming, vol. 1, no. 1, pp. 6–25, 1971. https://doi.org/10.1007/BF01584070.
  • Alkaabneh, A. Diabat, and S. Elhedhli, “A Lagrangian heuristic and GRASP for the hub-and-spoke network system with economies-of-scale and congestion,” Transportation Research Part C: Emerging Technologies, vol. 102, pp. 249–273, 2019. https://doi.org/10.1016/j.trc.2018.12.011.
  • Guta, “Subgradient Optimization Methods in Integer Programming with an Application to a Radiation Therapy Problem,” Technische Universität Kaiserslautern. Accessed: 2023.
Journal of Industrial Engineering Research in Production Systems
Volume 11, Issue 22
September 2023
Pages 31-43

Files

Share

How to cite

Statistics