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

A Self-Adaptive Memetic Algorithm for Distributed Job Shop Scheduling Problem

Author

Listed:
  • Guangchen Wang

    (College of Weaponry Engineering, Naval University of Engineering, Wuhan 430033, China)

  • Peng Wang

    (College of Weaponry Engineering, Naval University of Engineering, Wuhan 430033, China)

  • Honggang Zhang

    (College of Weaponry Engineering, Naval University of Engineering, Wuhan 430033, China)

Abstract

Distributed scheduling has become a common manufacturing mode, and the distributed job scheduling problem (DJSP) has attracted more manufacturers and researchers in the field of operation research. For the distributed scheduling problem, it emphasizes the flexibility of factory assignment and determines the sequence of operation related to each machine in related factories. In this paper, a mixed-integer linear programming model for the DJSP is formulated to be optimized by an SMA. Also in this paper, a self-adaptive memetic algorithm (SMA) is proposed to obtain a near-optimal solution in a limited time for the DJSP. To strengthen the effectiveness of the SMA, an independent encoding is designed with jobs assigned to factories and the sequence of operation. In the proposed algorithm, various local search strategies related to the critical path in the critical factory are designed to enhance the quality of the solution. Moreover, the self-adaptive scheme for solution improvement is formulated to reduce the search time and avoid prematurity effectively. To demonstrate the performance of the proposed algorithm, numerical experiments are carried out on 120 different instances extended from the well-known job shop scheduling benchmarks. The proposed SMA has updated 30 instance records in 120 instances and it has obtained the 91 best records in 120 instances. According to the comparison, an SMA is a more effective algorithm that could update several records of benchmarks.

Suggested Citation

  • Guangchen Wang & Peng Wang & Honggang Zhang, 2024. "A Self-Adaptive Memetic Algorithm for Distributed Job Shop Scheduling Problem," Mathematics, MDPI, vol. 12(5), pages 1-16, February.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:5:p:683-:d:1346428
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/5/683/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/5/683/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Peter J. M. van Laarhoven & Emile H. L. Aarts & Jan Karel Lenstra, 1992. "Job Shop Scheduling by Simulated Annealing," Operations Research, INFORMS, vol. 40(1), pages 113-125, February.
    2. Po-Hsiang Lu & Muh-Cherng Wu & Hao Tan & Yong-Han Peng & Chen-Fu Chen, 2018. "A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 29(1), pages 19-34, January.
    3. Chen, Lu & Bostel, Nathalie & Dejax, Pierre & Cai, Jianguo & Xi, Lifeng, 2007. "A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal," European Journal of Operational Research, Elsevier, vol. 181(1), pages 40-58, August.
    4. Pezzella, Ferdinando & Merelli, Emanuela, 2000. "A tabu search method guided by shifting bottleneck for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 297-310, January.
    5. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    Full references (including those not matched with items on IDEAS)

    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. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    2. Edzard Weber & Anselm Tiefenbacher & Norbert Gronau, 2019. "Need for Standardization and Systematization of Test Data for Job-Shop Scheduling," Data, MDPI, vol. 4(1), pages 1-21, February.
    3. Paul M E Shutler, 2004. "A priority list based heuristic for the job shop problem: part 2 tabu search," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 780-784, July.
    4. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    5. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    6. P M E Shutler, 2003. "A priority list based heuristic for the job shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(6), pages 571-584, June.
    7. Carlos Mencía & María Sierra & Ramiro Varela, 2013. "Depth-first heuristic search for the job shop scheduling problem," Annals of Operations Research, Springer, vol. 206(1), pages 265-296, July.
    8. Shahed Mahmud & Ripon K. Chakrabortty & Alireza Abbasi & Michael J. Ryan, 2022. "Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 33(7), pages 1939-1966, October.
    9. Mati, Yazid & Dauzère-Pérès, Stèphane & Lahlou, Chams, 2011. "A general approach for optimizing regular criteria in the job-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 212(1), pages 33-42, July.
    10. Chong Peng & Guanglin Wu & T Warren Liao & Hedong Wang, 2019. "Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem," PLOS ONE, Public Library of Science, vol. 14(9), pages 1-19, September.
    11. 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.
    12. Tao Ren & Yan Zhang & Shuenn-Ren Cheng & Chin-Chia Wu & Meng Zhang & Bo-yu Chang & Xin-yue Wang & Peng Zhao, 2020. "Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates," Mathematics, MDPI, vol. 8(8), pages 1-25, July.
    13. Gueret, Christelle & Jussien, Narendra & Prins, Christian, 2000. "Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems," European Journal of Operational Research, Elsevier, vol. 127(2), pages 344-354, December.
    14. Barry B. & Quim Castellà & Angel A. & Helena Ramalhinho Lourenco & Manuel Mateo, 2012. "ILS-ESP: An Efficient, Simple, and Parameter-Free Algorithm for Solving the Permutation Flow-Shop Problem," Working Papers 636, Barcelona School of Economics.
    15. Brammer, Janis & Lutz, Bernhard & Neumann, Dirk, 2022. "Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning," European Journal of Operational Research, Elsevier, vol. 299(1), pages 75-86.
    16. Pan, Quan-Ke & Ruiz, Rubén, 2012. "Local search methods for the flowshop scheduling problem with flowtime minimization," European Journal of Operational Research, Elsevier, vol. 222(1), pages 31-43.
    17. Jianjun Jiao & Lansun Chen, 2007. "Global Attractivity And Permanence Of A Stage-Structured Pest Managementsimodel With Time Delay And Diseased Pests Impulsive Transmission," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 10(04), pages 479-494.
    18. Buscher, Udo & Shen, Liji, 2009. "An integrated tabu search algorithm for the lot streaming problem in job shops," European Journal of Operational Research, Elsevier, vol. 199(2), pages 385-399, December.
    19. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R & M. Calle, 2020. "Scheduling a dual-resource flexible job shop with makespan and due date-related criteria," Annals of Operations Research, Springer, vol. 291(1), pages 5-35, August.
    20. Naderi, B. & Zandieh, M., 2014. "Modeling and scheduling no-wait open shop problems," International Journal of Production Economics, Elsevier, vol. 158(C), pages 256-266.

    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:12:y:2024:i:5:p:683-:d:1346428. 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.