IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v242y2016i2d10.1007_s10479-013-1332-5.html
   My bibliography  Save this article

A hybrid evolutionary algorithm to solve the job shop scheduling problem

Author

Listed:
  • T. C. E. Cheng

    (The Hong Kong Polytechnic University)

  • Bo Peng

    (Huazhong University of Science and Technology)

  • Zhipeng Lü

    (Huazhong University of Science and Technology)

Abstract

This paper presents a Hybrid Evolutionary Algorithm (HEA) to solve the Job Shop Scheduling Problem (JSP). Incorporating a tabu search procedure into the framework of an evolutionary algorithm, the HEA embraces several distinguishing features such as a longest common sequence based recombination operator and a similarity-and-quality based replacement criterion for population updating. The HEA is able to easily generate the best-known solutions for 90 % of the tested difficult instances widely used in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, the HEA identifies a better upper bound for two of these difficult instances.

Suggested Citation

  • T. C. E. Cheng & Bo Peng & Zhipeng Lü, 2016. "A hybrid evolutionary algorithm to solve the job shop scheduling problem," Annals of Operations Research, Springer, vol. 242(2), pages 223-237, July.
    • Handle: RePEc:spr:annopr:v:242:y:2016:i:2:d:10.1007_s10479-013-1332-5
    DOI: 10.1007/s10479-013-1332-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-013-1332-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-013-1332-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    2. 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.
    3. Robert H. Storer & S. David Wu & Renzo Vaccari, 1992. "New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling," Management Science, INFORMS, vol. 38(10), pages 1495-1509, October.
    4. Lourenco, Helena Ramalhinho, 1995. "Job-shop scheduling: Computational study of local search and large-step optimization methods," European Journal of Operational Research, Elsevier, vol. 83(2), pages 347-364, June.
    5. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    6. Éric D. Taillard, 1994. "Parallel Taboo Search Techniques for the Job Shop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 108-117, May.
    7. Eugeniusz Nowicki & Czeslaw Smutnicki, 1996. "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science, INFORMS, vol. 42(6), pages 797-813, June.
    8. Giuseppe Lancia & Franca Rinaldi & Paolo Serafini, 2011. "A time-indexed LP-based approach for min-sum job-shop problems," Annals of Operations Research, Springer, vol. 186(1), pages 175-198, June.
    9. Egon Balas & Alkis Vazacopoulos, 1998. "Guided Local Search with Shifting Bottleneck for Job Shop Scheduling," Management Science, INFORMS, vol. 44(2), pages 262-275, February.
    10. Kolonko, M., 1999. "Some new results on simulated annealing applied to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 113(1), pages 123-136, February.
    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. Bo Peng & Lifan Wu & Yuxin Yi & Xiding Chen, 2020. "Solving the Multi-Depot Green Vehicle Routing Problem by a Hybrid Evolutionary Algorithm," Sustainability, MDPI, vol. 12(5), pages 1-19, March.
    2. Lin, Geng & Guan, Jian & Feng, Huibin, 2018. "An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 500(C), pages 199-209.
    3. 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.
    4. Bo Peng & Yuan Zhang & Yuvraj Gajpal & Xiding Chen, 2019. "A Memetic Algorithm for the Green Vehicle Routing Problem," Sustainability, MDPI, vol. 11(21), pages 1-20, October.
    5. 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.
    6. Mohamed Habib Zahmani & Baghdad Atmani, 2021. "Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation," Journal of Scheduling, Springer, vol. 24(2), pages 175-196, April.
    7. Kannan Govindan, 2016. "Evolutionary algorithms for supply chain management," Annals of Operations Research, Springer, vol. 242(2), pages 195-206, July.
    8. Gabriel Mauricio Zambrano-Rey & Eliana María González-Neira & Gabriel Fernando Forero-Ortiz & María José Ocampo-Monsalve & Andrea Rivera-Torres, 2024. "Minimizing the expected maximum lateness for a job shop subject to stochastic machine breakdowns," Annals of Operations Research, Springer, vol. 338(1), pages 801-833, July.

    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. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    2. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    3. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    4. G I Zobolas & C D Tarantilis & G Ioannou, 2009. "A hybrid evolutionary algorithm for the job shop scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 221-235, February.
    5. Susana Fernandes & Helena Ramalhinho-Lourenço, 2007. "A simple optimised search heuristic for the job-shop scheduling problem," Economics Working Papers 1050, Department of Economics and Business, Universitat Pompeu Fabra.
    6. 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.
    7. Tamssaouet, Karim & Dauzère-Pérès, Stéphane, 2023. "A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 311(2), pages 455-471.
    8. Z C Zhu & K M Ng & H L Ong, 2010. "A modified tabu search algorithm for cost-based job shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(4), pages 611-619, April.
    9. Murovec, Boštjan, 2015. "Job-shop local-search move evaluation without direct consideration of the criterion’s value," European Journal of Operational Research, Elsevier, vol. 241(2), pages 320-329.
    10. 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.
    11. Bürgy, Reinhard & Bülbül, Kerem, 2018. "The job shop scheduling problem with convex costs," European Journal of Operational Research, Elsevier, vol. 268(1), pages 82-100.
    12. 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.
    13. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    14. 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.
    15. Bierwirth, C. & Kuhpfahl, J., 2017. "Extended GRASP for the job shop scheduling problem with total weighted tardiness objective," European Journal of Operational Research, Elsevier, vol. 261(3), pages 835-848.
    16. 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.
    17. Selcuk Goren & Ihsan Sabuncuoglu & Utku Koc, 2012. "Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(1), pages 26-38, February.
    18. 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.
    19. Ramesh Bollapragada & Norman M. Sadeh, 2004. "Proactive release procedures for just‐in‐time job shop environments, subject to machine failures," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(7), pages 1018-1044, October.
    20. Ganesan, Viswanath Kumar & Sivakumar, Appa Iyer, 2006. "Scheduling in static jobshops for minimizing mean flowtime subject to minimum total deviation of job completion times," International Journal of Production Economics, Elsevier, vol. 103(2), pages 633-647, October.

    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:spr:annopr:v:242:y:2016:i:2:d:10.1007_s10479-013-1332-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.