IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i8p909-d539118.html
   My bibliography  Save this article

Advanced Metaheuristic Method for Decision-Making in a Dynamic Job Shop Scheduling Environment

Author

Listed:
  • Hankun Zhang

    (School of E-Business and Logistics, Beijing Technology and Business University, Beijing 100048, China)

  • Borut Buchmeister

    (Faculty of Mechanical Engineering, University of Maribor, 2000 Maribor, Slovenia)

  • Xueyan Li

    (School of Management, Beijing Union University, Beijing 100101, China)

  • Robert Ojstersek

    (Faculty of Mechanical Engineering, University of Maribor, 2000 Maribor, Slovenia)

Abstract

As a well-known NP-hard problem, the dynamic job shop scheduling problem has significant practical value, so this paper proposes an Improved Heuristic Kalman Algorithm to solve this problem. In Improved Heuristic Kalman Algorithm, the cellular neighbor network is introduced, together with the boundary handling function, and the best position of each individual is recorded for constructing the cellular neighbor network. The encoding method is introduced based on the relative position index so that the Improved Heuristic Kalman Algorithm can be applied to solve the dynamic job shop scheduling problem. Solving the benchmark example of dynamic job shop scheduling problem and comparing it with the original Heuristic Kalman Algorithm and Genetic Algorithm-Mixed, the results show that Improved Heuristic Kalman Algorithm is effective for solving the dynamic job shop scheduling problem. The convergence rate of the Improved Heuristic Kalman Algorithm is reduced significantly, which is beneficial to avoid the algorithm from falling into the local optimum. For all 15 benchmark instances, Improved Heuristic Kalman Algorithm and Heuristic Kalman Algorithm have obtained the best solution obtained by Genetic Algorithm-Mixed. Moreover, for 9 out of 15 benchmark instances, they achieved significantly better solutions than Genetic Algorithm-Mixed. They have better robustness and reasonable running time (less than 30 s even for large size problems), which means that they are very suitable for solving the dynamic job shop scheduling problem. According to the dynamic job shop scheduling problem applicability, the integration-communication protocol was presented, which enables the transfer and use of the Improved Heuristic Kalman Algorithm optimization results in the conventional Simio simulation environment. The results of the integration-communication protocol proved the numerical and graphical matching of the optimization results and, thus, the correctness of the data transfer, ensuring high-level usability of the decision-making method in a real-world environment.

Suggested Citation

  • Hankun Zhang & Borut Buchmeister & Xueyan Li & Robert Ojstersek, 2021. "Advanced Metaheuristic Method for Decision-Making in a Dynamic Job Shop Scheduling Environment," Mathematics, MDPI, vol. 9(8), pages 1-22, April.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:8:p:909-:d:539118
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/8/909/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/8/909/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Li, Xue-yan & Li, Xue-mei & Yang, Lingrun & Li, Jing, 2018. "Dynamic route and departure time choice model based on self-adaptive reference point and reinforcement learning," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 502(C), pages 77-92.
    2. Ali Hosseinabadi & Hajar Siar & Shahaboddin Shamshirband & Mohammad Shojafar & Mohd Nasir, 2015. "Using the gravitational emulation local search algorithm to solve the multi-objective flexible dynamic job shop scheduling problem in Small and Medium Enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 451-474, June.
    3. Xiong, Hegen & Fan, Huali & Jiang, Guozhang & Li, Gongfa, 2017. "A simulation-based study of dispatching rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints," European Journal of Operational Research, Elsevier, vol. 257(1), pages 13-24.
    4. Vinod, V. & Sridharan, R., 2011. "Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system," International Journal of Production Economics, Elsevier, vol. 129(1), pages 127-146, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fabian Riquelme & Elizabeth Montero & Leslie Pérez-Cáceres & Nicolás Rojas-Morales, 2022. "A Track-Based Conference Scheduling Problem," Mathematics, MDPI, vol. 10(21), pages 1-25, October.
    2. Hankun Zhang & Borut Buchmeister & Xueyan Li & Robert Ojstersek, 2023. "An Efficient Metaheuristic Algorithm for Job Shop Scheduling in a Dynamic Environment," Mathematics, MDPI, vol. 11(10), pages 1-24, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hankun Zhang & Borut Buchmeister & Xueyan Li & Robert Ojstersek, 2023. "An Efficient Metaheuristic Algorithm for Job Shop Scheduling in a Dynamic Environment," Mathematics, MDPI, vol. 11(10), pages 1-24, May.
    2. Schaller, Jeffrey & Valente, Jorge M.S., 2020. "Minimizing total earliness and tardiness in a nowait flow shop," International Journal of Production Economics, Elsevier, vol. 224(C).
    3. Shahaboddin Shamshirband & Mohammad Shojafar & A. Hosseinabadi & Maryam Kardgar & M. Nasir & Rodina Ahmad, 2015. "OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 743-758, June.
    4. Li, Xueyan & Qiu, Heting & Yang, Yanni & Zhang, Hankun, 2022. "Differentiated fares depend on bus line and time for urban public transport network based on travelers’ day-to-day group behavior," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    5. Chuang Wang & Pingyu Jiang, 2019. "Deep neural networks based order completion time prediction by using real-time job shop RFID data," Journal of Intelligent Manufacturing, Springer, vol. 30(3), pages 1303-1318, March.
    6. Zigao Wu & Shaohua Yu & Tiancheng Li, 2019. "A Meta-Model-Based Multi-Objective Evolutionary Approach to Robust Job Shop Scheduling," Mathematics, MDPI, vol. 7(6), pages 1-19, June.
    7. Tanja Mlinar & Philippe Chevalier, 2016. "Pooling heterogeneous products for manufacturing environments," 4OR, Springer, vol. 14(2), pages 173-200, June.
    8. Xin Yang & Zhenxiang Zeng & Ruidong Wang & Xueshan Sun, 2016. "Bi-Objective Flexible Job-Shop Scheduling Problem Considering Energy Consumption under Stochastic Processing Times," PLOS ONE, Public Library of Science, vol. 11(12), pages 1-13, December.
    9. Al-Hinai, Nasr & ElMekkawy, T.Y., 2011. "Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm," International Journal of Production Economics, Elsevier, vol. 132(2), pages 279-291, August.
    10. Zhang, Rui & Song, Shiji & Wu, Cheng, 2013. "A hybrid artificial bee colony algorithm for the job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 141(1), pages 167-178.
    11. Zhang, Ke & Lin, Xi & Li, Meng, 2023. "Graph attention reinforcement learning with flexible matching policies for multi-depot vehicle routing problems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 611(C).
    12. A. S. Xanthopoulos & D. E. Koulouriotis, 2018. "Cluster analysis and neural network-based metamodeling of priority rules for dynamic sequencing," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 69-91, January.
    13. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2022. "Effective and interpretable dispatching rules for dynamic job shops via guided empirical learning," Omega, Elsevier, vol. 111(C).
    14. Xu, Junxiang & Zhang, Jin & Guo, Jingni, 2021. "Contribution to the field of traffic assignment: A boundedly rational user equilibrium model with uncertain supply and demand," Socio-Economic Planning Sciences, Elsevier, vol. 74(C).
    15. Yao, Shiqing & Jiang, Zhibin & Li, Na & Zhang, Huai & Geng, Na, 2011. "A multi-objective dynamic scheduling approach using multiple attribute decision making in semiconductor manufacturing," International Journal of Production Economics, Elsevier, vol. 130(1), pages 125-133, March.
    16. Adil Baykasoğlu & Fatma S. Karaslan, 2017. "Solving comprehensive dynamic job shop scheduling problem by using a GRASP-based approach," International Journal of Production Research, Taylor & Francis Journals, vol. 55(11), pages 3308-3325, June.
    17. Yu-Fang Wang, 2020. "Adaptive job shop scheduling strategy based on weighted Q-learning algorithm," Journal of Intelligent Manufacturing, Springer, vol. 31(2), pages 417-432, February.
    18. Aijun Liu & John Fowler & Michele Pfund, 2016. "Dynamic co-ordinated scheduling in the supply chain considering flexible routes," International Journal of Production Research, Taylor & Francis Journals, vol. 54(1), pages 322-335, January.
    19. Toly Chen & Li-Chih Wang & Min-Chi Chiu, 2018. "A multi-granularity approach for estimating the sustainability of a factory simulation model: semiconductor packaging as an example," Operational Research, Springer, vol. 18(3), pages 711-729, October.
    20. Jürgen Strohhecker & Michael Hamann & Jörn-Henrik Thun, 2016. "Loading and sequencing heuristics for job scheduling on two unrelated parallel machines with long, sequence-dependent set-up times," International Journal of Production Research, Taylor & Francis Journals, vol. 54(22), pages 6747-6767, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:8:p:909-:d:539118. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.