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

Comparative evaluation of MILP flowshop models

Author

Listed:
  • E F Stafford

    (University of Alabama in Huntsville)

  • F T Tseng

    (University of Alabama in Huntsville)

  • J N D Gupta

    (University of Alabama in Huntsville)

Abstract

This paper investigates the performance of two families of mixed-integer linear programing (MILP) models for solving the regular permutation flowshop problem to minimize makespan. The three models of the Wagner family incorporate the assignment problem while the five members of the Manne family use pairs of dichotomous constraints, or their mathematical equivalents, to assign jobs to sequence positions. For both families, the problem size complexity and computational time required to optimally solve a common set of problems are investigated. In so doing, this paper extends the application of MILP approaches to larger problem sizes than those found in the existing literature. The Wagner models require more than twice the binary variables and more real variables than do the Manne models, while Manne models require more constraints for the same sized problems. All Wagner models require much less computational time than any of the Manne models for solving the common set of problems, and these differences increase dramatically with increasing number of jobs and machines. Wagner models can solve problems containing larger numbers of machines and jobs than the Manne models, and hence are preferable for finding optimal solutions to the permutation flowshop problem with makespan objective.

Suggested Citation

  • 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.
  • Handle: RePEc:pal:jorsoc:v:56:y:2005:i:1:d:10.1057_palgrave.jors.2601805
    DOI: 10.1057/palgrave.jors.2601805
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601805
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1057/palgrave.jors.2601805?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 F Stafford & F T Tseng, 2003. "On ‘redundant’ constraints in Stafford's MILP model for the flowshop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(10), pages 1102-1105, October.
    2. 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.
    3. Herbert G. Campbell & Richard A. Dudek & Milton L. Smith, 1970. "A Heuristic Algorithm for the n Job, m Machine Sequencing Problem," Management Science, INFORMS, vol. 16(10), pages 630-637, June.
    4. B. J. Lageweg & J. K. Lenstra & A. H. G. Rinnooy Kan, 1978. "A General Bounding Scheme for the Permutation Flow-Shop Problem," Operations Research, INFORMS, vol. 26(1), pages 53-67, February.
    5. Alan S. Manne, 1960. "On the Job-Shop Scheduling Problem," Operations Research, INFORMS, vol. 8(2), pages 219-223, April.
    6. Edward H. Bowman, 1959. "The Schedule-Sequencing Problem," Operations Research, INFORMS, vol. 7(5), pages 621-624, 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. Victor Fernandez-Viagas & Luis Sanchez-Mediano & Alvaro Angulo-Cortes & David Gomez-Medina & Jose Manuel Molina-Pariente, 2022. "The Permutation Flow Shop Scheduling Problem with Human Resources: MILP Models, Decoding Procedures, NEH-Based Heuristics, and an Iterated Greedy Algorithm," Mathematics, MDPI, vol. 10(19), pages 1-32, September.
    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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Srinivas R. Chakravarthy & Alexander N. Dudin & Valentina I. Klimenok, 2010. "A Retrial Queueing Model With Map Arrivals, Catastrophic Failures With Repairs, And Customer Impatience," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 27(06), pages 727-752.
    9. 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.

    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. 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.
    2. JC-H Pan & J-S Chen, 2003. "Minimizing makespan in re-entrant permutation flow-shops," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(6), pages 642-653, June.
    3. Sündüz Dağ, 2013. "An Application On Flowshop Scheduling," Alphanumeric Journal, Bahadir Fatih Yildirim, vol. 1(1), pages 47-56, December.
    4. 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.
    5. 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.
    6. M Haouari & T Ladhari, 2003. "A branch-and-bound-based local search method for the flow shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(10), pages 1076-1084, October.
    7. 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.
    8. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    9. 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.
    10. 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.
    11. 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.
    12. Bertsimas, Dimitris & Gupta, Shubham & Lulli, Guglielmo, 2014. "Dynamic resource allocation: A flexible and tractable modeling framework," European Journal of Operational Research, Elsevier, vol. 236(1), pages 14-26.
    13. 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.
    14. Liangliang Jin & Qiuhua Tang & Chaoyong Zhang & Xinyu Shao & Guangdong Tian, 2016. "More MILP models for integrated process planning and scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(14), pages 4387-4402, July.
    15. Park, Myoung-Ju & Ham, Andy, 2022. "Energy-aware flexible job shop scheduling under time-of-use pricing," International Journal of Production Economics, Elsevier, vol. 248(C).
    16. Masmoudi, Oussama & Delorme, Xavier & Gianessi, Paolo, 2019. "Job-shop scheduling problem with energy consideration," International Journal of Production Economics, Elsevier, vol. 216(C), pages 12-22.
    17. Russell, Arya & Taghipour, Sharareh, 2019. "Multi-objective optimization of complex scheduling problems in low-volume low-variety production systems," International Journal of Production Economics, Elsevier, vol. 208(C), pages 1-16.
    18. Solimanpur, M. & Vrat, Prem & Shankar, Ravi, 2004. "A heuristic to minimize makespan of cell scheduling problem," International Journal of Production Economics, Elsevier, vol. 88(3), pages 231-241, April.
    19. Jens Brunner & Jonathan Bard & Rainer Kolisch, 2009. "Flexible shift scheduling of physicians," Health Care Management Science, Springer, vol. 12(3), pages 285-305, September.
    20. 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.

    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:56:y:2005:i:1:d:10.1057_palgrave.jors.2601805. 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.