IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v59y2008i10d10.1057_palgrave.jors.2602455.html
   My bibliography  Save this article

New MILP models for the permutation flowshop problem

Author

Listed:
  • F T Tseng

    (University of Alabama in Huntsville)

  • E F Stafford

    (University of Alabama in Huntsville)

Abstract

Two new mixed-integer linear programming (MILP) models for the regular permutation flowshop problem, called TBA and TS3, are derived using a combination of JAML (job-adjacency, machine-linkage) diagrams and variable substitution techniques. These new models are then compared to the incumbent best MILP models (Wilson, WST2, and TS2) for this problem found in the flowshop sequencing literature. We define the term best to mean that a particular model or set of models can solve a common set of test flowshop problems in significantly less time than other competing models. In other words, the two new MILP models (TBA and TS3) become the challengers to the current incumbent best models (Wilson, WST2, TS2.). Both new models are shown to require less time, on average, than the current best models for solving this set of problems; and the TS3 model is shown to solve these problems in statistically significantly less time than the other four models combined.

Suggested Citation

  • F T Tseng & E F Stafford, 2008. "New MILP models for the permutation flowshop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1373-1386, October.
    • Handle: RePEc:pal:jorsoc:v:59:y:2008:i:10:d:10.1057_palgrave.jors.2602455
    DOI: 10.1057/palgrave.jors.2602455
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2602455
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2602455?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. Richard A. Dudek & Ottis Foy Teuton, 1964. "Development of M -Stage Decision Rule for Scheduling N Jobs Through M Machines," Operations Research, INFORMS, vol. 12(3), pages 471-497, June.
    2. E F Stafford & F T Tseng & J N D Gupta, 2005. "Comparative evaluation of MILP flowshop models," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(1), pages 88-101, January.
    3. Alan S. Manne, 1960. "On the Job-Shop Scheduling Problem," Operations Research, INFORMS, vol. 8(2), pages 219-223, April.
    4. Gupta, Jatinder N.D. & Stafford, Edward Jr., 2006. "Flowshop scheduling research after five decades," European Journal of Operational Research, Elsevier, vol. 169(3), pages 699-711, March.
    5. Stafford, Edward F. & Tseng, Fan T., 2002. "Two models for a family of flowshop sequencing problems," European Journal of Operational Research, Elsevier, vol. 142(2), pages 282-293, October.
    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. Roshanaei, Vahid & Naderi, Bahman, 2021. "Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut," European Journal of Operational Research, Elsevier, vol. 293(1), pages 65-78.
    2. Tamás Hajba & Zoltán Horváth, 2015. "MILP models for the optimization of real production lines," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(4), pages 899-912, December.
    3. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, 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. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    2. Tamás Hajba & Zoltán Horváth, 2013. "New effective MILP models for PFSPs arising from real applications," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(4), pages 729-744, December.
    3. Fernando Luis Rossi & Marcelo Seido Nagano, 2022. "Beam search-based heuristics for the mixed no-idle flowshop with total flowtime criterion," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(4), pages 1311-1346, December.
    4. Tseng, Fan T. & Stafford, Edward F. & Gupta, Jatinder N. D., 2004. "An empirical analysis of integer programming formulations for the permutation flowshop," Omega, Elsevier, vol. 32(4), pages 285-293, August.
    5. 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.
    6. Kan Fang & Nelson Uhan & Fu Zhao & John Sutherland, 2013. "Flow shop scheduling with peak power consumption constraints," Annals of Operations Research, Springer, vol. 206(1), pages 115-145, July.
    7. Gupta, Jatinder N.D. & Stafford, Edward Jr., 2006. "Flowshop scheduling research after five decades," European Journal of Operational Research, Elsevier, vol. 169(3), pages 699-711, March.
    8. Tamás Hajba & Zoltán Horváth, 2015. "MILP models for the optimization of real production lines," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(4), pages 899-912, December.
    9. E F Stafford & F T Tseng & J N D Gupta, 2005. "Comparative evaluation of MILP flowshop models," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(1), pages 88-101, January.
    10. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    11. Taejong Joo & Hyunyoung Jun & Dongmin Shin, 2022. "Task Allocation in Human–Machine Manufacturing Systems Using Deep Reinforcement Learning," Sustainability, MDPI, vol. 14(4), pages 1-18, February.
    12. 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.
    13. Matthias Bultmann & Sigrid Knust & Stefan Waldherr, 2018. "Flow shop scheduling with flexible processing times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 809-829, July.
    14. Jinliang Cheng & Hiroshi Kise & Hironori Matsumoto, 1997. "A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 96(3), pages 578-590, February.
    15. Alfaro-Fernández, Pedro & Ruiz, Rubén & Pagnozzi, Federico & Stützle, Thomas, 2020. "Automatic Algorithm Design for Hybrid Flowshop Scheduling Problems," European Journal of Operational Research, Elsevier, vol. 282(3), pages 835-845.
    16. Hatami, Sara & Ruiz, Rubén & Andrés-Romano, Carlos, 2015. "Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times," International Journal of Production Economics, Elsevier, vol. 169(C), pages 76-88.
    17. 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.
    18. Liji Shen & Jatinder N. D. Gupta, 2018. "Family scheduling with batch availability in flow shops to minimize makespan," Journal of Scheduling, Springer, vol. 21(2), pages 235-249, April.
    19. 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.
    20. Shiuan Wan & Yi-Ping Wang, 2020. "The Comparison of Density-Based Clustering Approach among Different Machine Learning Models on Paddy Rice Image Classification of Multispectral and Hyperspectral Image Data," Agriculture, MDPI, vol. 10(10), pages 1-17, 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:pal:jorsoc:v:59:y:2008:i:10:d:10.1057_palgrave.jors.2602455. 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.