IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v62y2011i2d10.1057_jors.2010.132.html
   My bibliography  Save this article

On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming

Author

Listed:
  • J A Vázquez-Rodríguez

    (University of Nottingham)

  • G Ochoa

    (University of Nottingham)

Abstract

We use genetic programming to find variants of the well-known Nawaz, En-score and Ham (NEH) heuristic for the permutation flow shop problem. Each variant uses a different ranking function to prioritize operations during schedule construction. We have tested our ideas on problems where jobs have release times, due dates, and weights and have considered five objective functions: makespan, sum of tardiness, sum of weighted tardiness, sum of completion times and sum of weighted completion times. The implemented genetic programming system has been carefully tuned and used to generate one variant of NEH for each objective function. The new NEHs, obtained with genetic programming, have been compared with the original NEH and randomized NEH versions on a large set of benchmark problems. Our results indicate that the NEH variants discovered by genetic programming are superior to the original NEH and its stochastic version on most of the problems investigated.

Suggested Citation

  • J A Vázquez-Rodríguez & G Ochoa, 2011. "On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 381-396, February.
    • Handle: RePEc:pal:jorsoc:v:62:y:2011:i:2:d:10.1057_jors.2010.132
    DOI: 10.1057/jors.2010.132
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/jors.2010.132
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/jors.2010.132?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. E K Burke & B L MacCarthy & S Petrovic & R Qu, 2006. "Multiple-retrieval case-based reasoning for course timetabling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(2), pages 148-162, February.
    2. Uwe Aickelin & Jingpeng Li, 2007. "An estimation of distribution algorithm for nurse scheduling," Annals of Operations Research, Springer, vol. 155(1), pages 289-309, November.
    3. Ruiz, Ruben & Maroto, Concepcion, 2005. "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, Elsevier, vol. 165(2), pages 479-494, September.
    4. Sanja Petrovic & Carole Fayad & Dobrila Petrovic & Edmund Burke & Graham Kendall, 2008. "Fuzzy job shop scheduling with lot-sizing," Annals of Operations Research, Springer, vol. 159(1), pages 275-292, March.
    5. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    6. Burke, Edmund K. & McCollum, Barry & Meisels, Amnon & Petrovic, Sanja & Qu, Rong, 2007. "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, Elsevier, vol. 176(1), pages 177-192, January.
    7. Nawaz, Muhammad & Enscore Jr, E Emory & Ham, Inyong, 1983. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Elsevier, vol. 11(1), pages 91-95.
    8. R Bai & E K Burke & G Kendall, 2008. "Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1387-1397, October.
    9. Ruiz, Ruben & Maroto, Concepcion, 2006. "A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility," European Journal of Operational Research, Elsevier, vol. 169(3), pages 781-800, March.
    10. Taillard, E., 1990. "Some efficient heuristic methods for the flow shop sequencing problem," European Journal of Operational Research, Elsevier, vol. 47(1), pages 65-74, July.
    11. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    12. J M Framinan & J N D Gupta & R Leisten, 2004. "A review and classification of heuristics for permutation flow-shop scheduling with makespan objective," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1243-1255, December.
    13. Kalczynski, Pawel Jan & Kamburowski, Jerzy, 2007. "On the NEH heuristic for minimizing the makespan in permutation flow shops," Omega, Elsevier, vol. 35(1), pages 53-60, 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. Pickardt, Christoph W. & Hildebrandt, Torsten & Branke, Jürgen & Heger, Jens & Scholz-Reiter, Bernd, 2013. "Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems," International Journal of Production Economics, Elsevier, vol. 145(1), pages 67-77.
    2. Fernandez-Viagas, Victor & Talens, Carla & Framinan, Jose M., 2022. "Assembly flowshop scheduling problem: Speed-up procedure and computational evaluation," European Journal of Operational Research, Elsevier, vol. 299(3), pages 869-882.

    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. Fernandez-Viagas, Victor & Ruiz, Rubén & Framinan, Jose M., 2017. "A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation," European Journal of Operational Research, Elsevier, vol. 257(3), pages 707-721.
    2. Kalczynski, Pawel J. & Kamburowski, Jerzy, 2009. "An empirical analysis of the optimality rate of flow shop heuristics," European Journal of Operational Research, Elsevier, vol. 198(1), pages 93-101, October.
    3. Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
    4. Sioud, A. & Gagné, C., 2018. "Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 264(1), pages 66-73.
    5. Li, Wei & Nault, Barrie R. & Ye, Honghan, 2019. "Trade-off balancing in scheduling for flow shop production and perioperative processes," European Journal of Operational Research, Elsevier, vol. 273(3), pages 817-830.
    6. Benavides, Alexander J. & Vera, Antony, 2022. "The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(2), pages 407-421.
    7. Rad, Shahriar Farahmand & Ruiz, Rubén & Boroojerdian, Naser, 2009. "New high performing heuristics for minimizing makespan in permutation flowshops," Omega, Elsevier, vol. 37(2), pages 331-345, April.
    8. Naderi, Bahman & Ruiz, Rubén, 2014. "A scatter search algorithm for the distributed permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 323-334.
    9. K Sheibani, 2010. "A fuzzy greedy heuristic for permutation flow-shop scheduling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 813-818, May.
    10. Ruiz, Rubén & Pan, Quan-Ke & Naderi, Bahman, 2019. "Iterated Greedy methods for the distributed permutation flowshop scheduling problem," Omega, Elsevier, vol. 83(C), pages 213-222.
    11. 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.
    12. Perez-Gonzalez, Paz & Framinan, Jose M., 2024. "A review and classification on distributed permutation flowshop scheduling problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 1-21.
    13. Ruiz, Ruben & Stutzle, Thomas, 2008. "An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1143-1159, June.
    14. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    15. Vallada, Eva & Ruiz, Rubén, 2010. "Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem," Omega, Elsevier, vol. 38(1-2), pages 57-67, February.
    16. Pan, Quan-Ke & Wang, Ling, 2012. "Effective heuristics for the blocking flowshop scheduling problem with makespan minimization," Omega, Elsevier, vol. 40(2), pages 218-229, April.
    17. Pagnozzi, Federico & Stützle, Thomas, 2021. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems with additional constraints," Operations Research Perspectives, Elsevier, vol. 8(C).
    18. Vallada, Eva & Ruiz, Rubén & Framinan, Jose M., 2015. "New hard benchmark for flowshop scheduling problems minimising makespan," European Journal of Operational Research, Elsevier, vol. 240(3), pages 666-677.
    19. Yenisey, Mehmet Mutlu & Yagmahan, Betul, 2014. "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, Elsevier, vol. 45(C), pages 119-135.
    20. Lobo, Fernando G. & Bazargani, Mosab & Burke, Edmund K., 2020. "A cutoff time strategy based on the coupon collector’s problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 101-114.

    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:pal:jorsoc:v:62:y:2011:i:2:d:10.1057_jors.2010.132. 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.palgrave-journals.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.