IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i7p1035-d1367304.html
   My bibliography  Save this article

Novel Approaches to the Formulation of Scheduling Problems

Author

Listed:
  • José Manuel García-Sánchez

    (Department of Industrial Management I, University of Seville, E41092 Seville, Spain)

  • Plácido Moreno

    (Department of Industrial Management I, University of Seville, E41092 Seville, Spain)

Abstract

This paper presents two novel formulations for scheduling problems, namely order-position hybrid formulation (OPH) and order-disjunctive hybrid formulation (ODH), which extend and combine parts of existing formulation strategies. The first strategy (OPH) is based on sequence position and linear ordering formulations, adding relationships between constraints that allow relaxing some decision variables. The second approach (ODH) is based on linear ordering and disjunctive formulations. In this work, we prove ODH to be the most efficient formulation known so far. The experiments have been carried out with a large set of problems, which consider single machines and identical parallel machines. Computational results show that OPH is better than the rest of the existing formulations for the case of weighted completion objectives, while ODH turns out to be the best approach for most scenarios studied.

Suggested Citation

  • José Manuel García-Sánchez & Plácido Moreno, 2024. "Novel Approaches to the Formulation of Scheduling Problems," Mathematics, MDPI, vol. 12(7), pages 1-15, March.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:7:p:1035-:d:1367304
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/7/1035/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/7/1035/
    Download Restriction: no
    ---><---

    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. 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.
    3. 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).
    4. 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).
    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. 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.
    2. 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.
    3. Soric, Kristina, 2000. "A cutting plane algorithm for a single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 383-393, December.
    4. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Pereira, Jordi & Vásquez, Óscar C., 2017. "The single machine weighted mean squared deviation problem," European Journal of Operational Research, Elsevier, vol. 261(2), pages 515-529.
    12. 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.
    13. 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.
    14. 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).
    15. 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.
    16. 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.
    17. 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.
    18. Fabio D'Andreagiovanni & Carlo Mannino & Antonio Sassano, 2010. "GUB Covers and Power-Indexed Formulations for Wireless Network Design," DIS Technical Reports 2010-14, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    19. 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.
    20. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.

    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:gam:jmathe:v:12:y:2024:i:7:p:1035-:d:1367304. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.