IDEAS home Printed from https://ideas.repec.org/a/aae/journl/v8y2012i2p26-43.html
   My bibliography  Save this article

A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems

Author

Listed:
  • Chia-Shin Chung

    (Department of Operations and Supply Chain Management, Cleveland State Univesity)

  • James Flynn

    (Department of Operations and Supply Chain Management, Cleveland State Univesity)

  • Walter Rom

    (Department of Operations and Supply Chain Management, Cleveland State Univesity)

  • Piotr Staliński

    (Department of Quantitative Methods in Management, Wyższa Szkoła Biznesu-National Louis University)

Abstract

The m-machine, n-job, permutation flowshop problem with the total tardiness objective is a common scheduling problem, known to be NP-hard. Branch and bound, the usual approach to finding an optimal solution, experiences difficulty when n exceeds 20. Here, we develop a genetic algorithm, GA, which can handle problems with larger n. We also undertake a numerical study comparing GA with an optimal branch and bound algorithm, and various heuristic algorithms including the well known NEH algorithm and a local search heuristic LH. Extensive computational experiments indicate that LH is an effective heuristic and GA can produce noticeable improvements over LH.

Suggested Citation

  • Chia-Shin Chung & James Flynn & Walter Rom & Piotr Staliński, 2012. "A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems," Journal of Entrepreneurship, Management and Innovation, Fundacja Upowszechniająca Wiedzę i Naukę "Cognitione", vol. 8(2), pages 26-43.
    • Handle: RePEc:aae:journl:v:8:y:2012:i:2:p:26-43
    DOI: 10.7341/2012822
    as

    Download full text from publisher

    File URL: http://jemi.edu.pl/uploadedFiles/file/all-issues/vol8/issue2/JEMI_Vol_8_Issue_2_2012_Article_2.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.7341/2012822?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
    ---><---

    References listed on IDEAS

    as
    1. Chung, Chia-Shin & Flynn, James & Kirca, Omer, 2006. "A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 174(1), pages 1-10, October.
    2. Colin R. Reeves, 1997. "Feature Article---Genetic Algorithms for the Operations Researcher," INFORMS Journal on Computing, INFORMS, vol. 9(3), pages 231-250, August.
    3. Chung, Chia-Shin & Flynn, James & Kirca, Omer, 2002. "A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems," International Journal of Production Economics, Elsevier, vol. 79(3), pages 185-196, October.
    4. 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.
    5. Kim, Yeong-Dae, 1995. "Minimizing total tardiness in permutation flowshops," European Journal of Operational Research, Elsevier, vol. 85(3), pages 541-555, September.
    6. 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.
    7. Christos Koulamas, 1994. "The Total Tardiness Problem: Review and Extensions," Operations Research, INFORMS, vol. 42(6), pages 1025-1041, December.
    8. O Etiler & B Toklu & M Atak & J Wilson, 2004. "A genetic algorithm for flow shop scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(8), pages 830-835, August.
    9. Arroyo, Jose Elias Claudio & Armentano, Vinicius Amaral, 2005. "Genetic local search for multi-objective flowshop scheduling problems," European Journal of Operational Research, Elsevier, vol. 167(3), pages 717-738, December.
    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. 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.
    2. 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.
    3. N Madhushini & C Rajendran & Y Deepa, 2009. "Branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted f," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 991-1004, July.
    4. Lee, Wen-Chiung & Chung, Yu-Hsiang, 2013. "Permutation flowshop scheduling to minimize the total tardiness with learning effects," International Journal of Production Economics, Elsevier, vol. 141(1), pages 327-334.
    5. Chung, Chia-Shin & Flynn, James & Kirca, Omer, 2006. "A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 174(1), pages 1-10, October.
    6. Gerardo Minella & Rubén Ruiz & Michele Ciavotta, 2008. "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 451-471, August.
    7. Choi, Seong-Woo & Kim, Yeong-Dae, 2009. "Minimizing total tardiness on a two-machine re-entrant flowshop," European Journal of Operational Research, Elsevier, vol. 199(2), pages 375-384, December.
    8. 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.
    9. Tirupati Devanath & Peeyush Mehta & Chandra, Pankaj, 2004. "Permutation Flowshop Scheduling with Earliness and Tardiness Penalties," IIMA Working Papers WP2004-07-06, Indian Institute of Management Ahmedabad, Research and Publication Department.
    10. 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.
    11. Pan, Quan-Ke & Ruiz, Rubén, 2012. "An estimation of distribution algorithm for lot-streaming flow shop problems with setup times," Omega, Elsevier, vol. 40(2), pages 166-180, April.
    12. 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.
    13. Allahverdi, Ali & Aldowaisan, Tariq, 2004. "No-wait flowshops with bicriteria of makespan and maximum lateness," European Journal of Operational Research, Elsevier, vol. 152(1), pages 132-147, January.
    14. Framinan, Jose M. & Perez-Gonzalez, Paz, 2015. "On heuristic solutions for the stochastic flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 246(2), pages 413-420.
    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. Tadashi Yamada & Bona Frazila Russ & Jun Castro & Eiichi Taniguchi, 2009. "Designing Multimodal Freight Transport Networks: A Heuristic Approach and Applications," Transportation Science, INFORMS, vol. 43(2), pages 129-143, May.
    17. Theodor Freiheit & Wei Li, 2017. "The effect of work content imbalance and its interaction with scheduling method on sequential flow line performance," International Journal of Production Research, Taylor & Francis Journals, vol. 55(10), pages 2791-2805, May.
    18. Mostafa Khatami & Seyed Hessameddin Zegordi, 2017. "Coordinative production and maintenance scheduling problem with flexible maintenance time intervals," Journal of Intelligent Manufacturing, Springer, vol. 28(4), pages 857-867, April.
    19. Mohamed Ali Rakrouki & Anis Kooli & Sabrine Chalghoumi & Talel Ladhari, 2020. "A branch-and-bound algorithm for the two-machine total completion time flowshop problem subject to release dates," Operational Research, Springer, vol. 20(1), pages 21-35, March.
    20. B-J Joo & Y-D Kim, 2009. "A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(4), pages 572-582, April.

    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:aae:journl:v:8:y:2012:i:2:p:26-43. 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: Anna Ujwary-Gil (email available below). General contact details of provider: https://fundacjacognitione.org .

    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.