IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i1p90-100.html
   My bibliography  Save this article

An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems

Author

Listed:
  • Daniel Oliveira

    (Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada)

  • Artur Pessoa

    (Departamento de Engenharia de Produção, Universidade Federal Fluminense, 24210-240 Rio de Janeiro, Brazil)

Abstract

This work presents an improved branch-cut-and-price algorithm for the identical parallel machine scheduling problem minimizing a generic function of the job completion times. A new family of cuts is proposed to strengthen the arc-time-indexed formulation, along with an efficient separation algorithm. Also, the projection of the arc-time-indexed into a time-indexed formulation is introduced to take advantage of the variable fixings performed in the larger variable space. The improved algorithm was capable of solving 146 out of 150 instances in the literature, with 12 being solved for the first time. Also, the running time for the 134 previously solved instances decreased by 95.7% on the average.

Suggested Citation

  • Daniel Oliveira & Artur Pessoa, 2020. "An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 90-100, January.
    • Handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:90-100
    DOI: 10.1287/ijoc.2018.0854
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0854
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0854?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. A. Alan B. Pritsker & Lawrence J. Waiters & Philip M. Wolfe, 1969. "Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach," Management Science, INFORMS, vol. 16(1), pages 93-108, September.
    2. Chris N. Potts & Luk N. Van Wassenhove, 1985. "A Branch and Bound Algorithm for the Total Weighted Tardiness Problem," Operations Research, INFORMS, vol. 33(2), pages 363-377, April.
    3. J.M. van den Akker & C.A.J. Hurkens & M.W.P. Savelsbergh, 2000. "Time-Indexed Formulations for Machine Scheduling Problems: Column Generation," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 111-124, May.
    4. Ibaraki, Toshihide & Nakamura, Yuichi, 1994. "A dynamic programming method for single machine scheduling," European Journal of Operational Research, Elsevier, vol. 76(1), pages 72-82, July.
    5. SOUSA, Jorge P. & WOLSEY, Laurence A., 1992. "A time indexed formulation of non-preemptive single machine scheduling problems," LIDAM Reprints CORE 984, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, 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. João Luiz Marques Andrade & Gustavo Campos Menezes, 2023. "A column generation-based heuristic to solve the integrated planning, scheduling, yard allocation and berth allocation problem in bulk ports," Journal of Heuristics, Springer, vol. 29(1), pages 39-76, February.

    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 & Christopher Hojny & Stefan Røpke, 2024. "A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1696-1714, December.
    2. 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.
    3. Yunpeng Pan & Zhe Liang, 2017. "Dual relaxations of the time-indexed ILP formulation for min–sum scheduling problems," Annals of Operations Research, Springer, vol. 249(1), pages 197-213, February.
    4. Zhang, Hanxiao & Li, Yan-Fu, 2022. "Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers," European Journal of Operational Research, Elsevier, vol. 299(1), pages 183-194.
    5. Alidaee, Bahram & Li, Haitao & Wang, Haibo & Womer, Keith, 2021. "Integer programming formulations in sequencing with total earliness and tardiness penalties, arbitrary due dates, and no idle time: A concise review and extension," Omega, Elsevier, vol. 103(C).
    6. Louis-Philippe Bigras & Michel Gamache & Gilles Savard, 2008. "Time-Indexed Formulations and the Total Weighted Tardiness Problem," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 133-142, February.
    7. Rachid Benmansour & Oliver Braun & Saïd Hanafi, 2019. "The single-processor scheduling problem with time restrictions: complexity and related problems," Journal of Scheduling, Springer, vol. 22(4), pages 465-471, August.
    8. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    9. Baptiste, Philippe & Sadykov, Ruslan, 2010. "Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars," European Journal of Operational Research, Elsevier, vol. 203(2), pages 476-483, June.
    10. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    11. Yagiura, Mutsunori & Ibaraki, Toshihide, 1996. "The use of dynamic programming in genetic algorithms for permutation problems," European Journal of Operational Research, Elsevier, vol. 92(2), pages 387-401, July.
    12. Laureano Escudero & Javier Salmeron, 2005. "On a Fix-and-Relax Framework for a Class of Project Scheduling Problems," Annals of Operations Research, Springer, vol. 140(1), pages 163-188, November.
    13. 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.
    14. Kaouthar Deghdak & Vincent T’kindt & Jean-Louis Bouquard, 2016. "Scheduling evacuation operations," Journal of Scheduling, Springer, vol. 19(4), pages 467-478, August.
    15. Chatterjee A K & Mukherjee, Saral, 2006. "Unified Concept of Bottleneck," IIMA Working Papers WP2006-05-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    16. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    17. 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.
    18. Lotte Berghman & Roel Leus & Frits Spieksma, 2014. "Optimal solutions for a dock assignment problem with trailer transportation," Annals of Operations Research, Springer, vol. 213(1), pages 3-25, February.
    19. Martin W. P. Savelsbergh & R. N. Uma & Joel Wein, 2005. "An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 123-136, February.
    20. Silva, Marco & Poss, Michael & Maculan, Nelson, 2020. "Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty," European Journal of Operational Research, Elsevier, vol. 283(1), pages 70-82.

    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:inm:orijoc:v:32:y:2020:i:1:p:90-100. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.