IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v285y2020i1d10.1007_s10479-019-03212-3.html
   My bibliography  Save this article

A cutting plane approach for the multi-machine precedence-constrained scheduling problem

Author

Listed:
  • Prahalad Venkateshan

    (Indian Institute of Management)

  • Joseph Szmerekovsky

    (North Dakota State University)

  • George Vairaktarakis

    (Case Western Reserve University)

Abstract

A cutting-plane approach is developed for the problem of optimally scheduling jobs with arbitrary precedence constraints on unrelated parallel machines to minimize weighted completion time. While the single machine version of this problem has attracted much research efforts, enabling solving problems with up to 100 jobs, not much has been done on the multiple machines case. A novel mixed-integer programming model is presented for the problem with multiple machines. For this model, many classes of valid inequalities that cut off fractional linear programming solutions are developed. This leads to an increase of the linear programming lower bound from 89.3 to 94.6% of the corresponding optimal solution, and a substantial reduction in the computational time of an optimal branch-and-bound algorithm for this problem. This enables us to report optimal solutions for problem instances with up to 25 jobs and 5 machines, which is more than twice the size of problems for which optimal solutions have been reported in the literature thus far. For a special case of the problem—that of minimizing makespan—application of our model helps solve 18 of 27 previously unsolved problem instances to optimality.

Suggested Citation

  • Prahalad Venkateshan & Joseph Szmerekovsky & George Vairaktarakis, 2020. "A cutting plane approach for the multi-machine precedence-constrained scheduling problem," Annals of Operations Research, Springer, vol. 285(1), pages 247-271, February.
    • Handle: RePEc:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03212-3
    DOI: 10.1007/s10479-019-03212-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03212-3
    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-019-03212-3?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. DYER, Martin E. & WOLSEY, Laurence A., 1990. "Formulating the single machine sequencing problem with release dates as a mixed integer program," LIDAM Reprints CORE 878, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Olaguibel, Ramon Alvarez-Valdes & Goerlich, JoseManuel Tamarit, 1993. "The project scheduling polyhedron: Dimension, facets and lifting theorems," European Journal of Operational Research, Elsevier, vol. 67(2), pages 204-220, June.
    3. Herrmann, Jeffrey & Proth, Jean-Marie & Sauer, Nathalie, 1997. "Heuristics for unrelated machine scheduling with precedence constraints," European Journal of Operational Research, Elsevier, vol. 102(3), pages 528-537, November.
    4. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    5. C. N. Potts, 1985. "A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time," Management Science, INFORMS, vol. 31(10), pages 1300-1311, October.
    6. E. DYER, Martin & WOLSEY, Laurence A., 1990. "Formulating the single machine sequencing problem with release dates as a mixed integer program," LIDAM Reprints CORE 917, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Mokotoff, E. & Chretienne, P., 2002. "A cutting plane algorithm for the unrelated parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 141(3), pages 515-525, September.
    8. Mokotoff, Ethel, 2004. "An exact algorithm for the identical parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 152(3), pages 758-769, February.
    9. Zhi-Long Chen & Warren B. Powell, 1999. "Solving Parallel Machine Scheduling Problems by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 78-94, February.
    10. Fanjul-Peyro, Luis & Perea, Federico & Ruiz, Rubén, 2017. "Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources," European Journal of Operational Research, Elsevier, vol. 260(2), pages 482-493.
    11. Maurice Queyranne & Yaoguang Wang, 1991. "Single-Machine Scheduling Polyhedra with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 1-20, February.
    12. Kolisch, Rainer & Sprecher, Arno, 1997. "PSPLIB - A project scheduling problem library : OR Software - ORSEP Operations Research Software Exchange Program," European Journal of Operational Research, Elsevier, vol. 96(1), pages 205-216, January.
    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. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    2. Philippe Baptiste & Ruslan Sadykov, 2009. "On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(6), pages 487-502, September.
    3. Hui Liu & Maurice Queyranne & David Simchi‐Levi, 2005. "On the asymptotic optimality of algorithms for the flow shop problem with release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 232-242, April.
    4. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    5. Stéphane Dauzère-Pérès & Sigrid Lise Nonås, 2023. "An improved decision support model for scheduling production in an engineer-to-order manufacturer," 4OR, Springer, vol. 21(2), pages 247-300, June.
    6. van den Akker, J.M. & Savelsbergh, M.W.P. & van Hoesel, C.P.M., 1997. "A polyhedral approach to single-machine scheduling problems," Research Memorandum 002, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    7. José R. Correa & Andreas S. Schulz, 2005. "Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 1005-1021, November.
    8. Farbod Farhadi & Sina Ansari & Francisco Jara-Moroni, 2023. "Optimization models for patient and technician scheduling in hemodialysis centers," Health Care Management Science, Springer, vol. 26(3), pages 558-582, September.
    9. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    10. Kerem Bülbül & Philip Kaminsky & Candace Yano, 2004. "Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(3), pages 407-445, April.
    11. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    12. Maria Fleischer Fauske & Carlo Mannino & Paolo Ventura, 2020. "Generalized Periodic Vehicle Routing and Maritime Surveillance," Transportation Science, INFORMS, vol. 54(1), pages 164-183, January.
    13. 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.
    14. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    15. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    16. Pasquale Avella & Maurizio Boccia & Bernardo D’Auria, 2005. "Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 183-191, May.
    17. P. Detti & D. Pacciarelli, 2001. "A branch and bound algorithm for the minimum storage‐time sequencing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(4), pages 313-331, June.
    18. Bentao Su & Naiming Xie & Yingjie Yang, 2021. "Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 32(4), pages 957-969, April.
    19. Fabio D'Andreagiovanni & Carlo Mannino & Antonio Sassano, 2009. "A Power-Indexed Formulation for Wireless Network Design," DIS Technical Reports 2009-14, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    20. Natashia Boland & Riley Clement & Hamish Waterer, 2016. "A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 14-30, February.

    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:285:y:2020:i:1:d:10.1007_s10479-019-03212-3. 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.