IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v189y2008i3p1284-1304.html
   My bibliography  Save this article

A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates

Author

Listed:
  • Sadykov, Ruslan

Abstract

In this paper we consider the scheduling problem of minimizing the weighted number of late jobs on a single machine (1rj[summation operator]wjUj). A branch-and-check algorithm is proposed, where a relaxed integer programming formulation is solved by branch-and-bound and infeasible solutions are cut off using infeasibility cuts. We suggest two ways to generate cuts. First, tightened "no-good" cuts are derived using a modification of the algorithm by Carlier (1982, EJOR, v.11, 42-47) which was developed for the problem of minimizing maximum lateness on a single machine. Secondly we show how to create cuts by using constraint propagation. The proposed algorithm is implemented in the Mosel modelling and optimization language. Computational experiments on instances with up to 140 jobs are reported. A comparison is presented with the exact approach of Péridy at al. (2003, EJOR, v.148, 591-603).

Suggested Citation

  • Sadykov, Ruslan, 2008. "A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1284-1304, September.
    • Handle: RePEc:eee:ejores:v:189:y:2008:i:3:p:1284-1304
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00599-1
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. E. L. Lawler & J. M. Moore, 1969. "A Functional Equation and its Application to Resource Allocation and Sequencing Problems," Management Science, INFORMS, vol. 16(1), pages 77-84, September.
    2. Baptiste, Philippe & Peridy, Laurent & Pinson, Eric, 2003. "A branch and bound to minimize the number of late jobs on a single machine with release time constraints," European Journal of Operational Research, Elsevier, vol. 144(1), pages 1-11, January.
    3. Ruslan Sadykov & Laurence A. Wolsey, 2006. "Integer Programming and Constraint Programming in Solving a Multimachine Assignment Scheduling Problem with Deadlines and Release Dates," INFORMS Journal on Computing, INFORMS, vol. 18(2), pages 209-217, May.
    4. Linus Schrage, 1970. "Solving Resource-Constrained Network Problems by Implicit Enumeration—Nonpreemptive Case," Operations Research, INFORMS, vol. 18(2), pages 263-278, April.
    5. Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
    6. Peridy, Laurent & Pinson, Eric & Rivreau, David, 2003. "Using short-term memory to minimize the weighted number of late jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 148(3), pages 591-603, August.
    7. Sevaux, Marc & Dauzere-Peres, Stephane, 2003. "Genetic algorithms to minimize the weighted number of late jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 151(2), pages 296-306, December.
    8. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    9. Hiroshi Kise & Toshihide Ibaraki & Hisashi Mine, 1978. "A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times," Operations Research, INFORMS, vol. 26(1), pages 121-126, February.
    10. J. Michael Moore, 1968. "An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs," Management Science, INFORMS, vol. 15(1), pages 102-109, September.
    11. SADYKOV, Ruslan & WOLSEY, Laurence A., 2006. "Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates," LIDAM Reprints CORE 1854, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Aigerim Saken & Emil Karlsson & Stephen J. Maher & Elina Rönnberg, 2023. "Computational Evaluation of Cut-Strengthening Techniques in Logic-Based Benders’ Decomposition," SN Operations Research Forum, Springer, vol. 4(3), pages 1-53, September.
    2. François Clautiaux & Boris Detienne & Henri Lefebvre, 2023. "A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty," Journal of Scheduling, Springer, vol. 26(2), pages 169-191, April.
    3. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    4. Detienne, Boris, 2014. "A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints," European Journal of Operational Research, Elsevier, vol. 235(3), pages 540-552.
    5. Aliza Heching & J. N. Hooker & Ryo Kimura, 2019. "A Logic-Based Benders Approach to Home Healthcare Delivery," Transportation Science, INFORMS, vol. 53(2), pages 510-522, March.
    6. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    7. Naderi, Bahman & Roshanaei, Vahid, 2020. "Branch-Relax-and-Check: A tractable decomposition method for order acceptance and identical parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 286(3), pages 811-827.

    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. Detienne, Boris, 2014. "A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints," European Journal of Operational Research, Elsevier, vol. 235(3), pages 540-552.
    2. M'Hallah, Rym & Bulfin, R.L., 2007. "Minimizing the weighted number of tardy jobs on a single machine with release dates," European Journal of Operational Research, Elsevier, vol. 176(2), pages 727-744, January.
    3. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    4. Gedik, Ridvan & Rainwater, Chase & Nachtmann, Heather & Pohl, Ed A., 2016. "Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals," European Journal of Operational Research, Elsevier, vol. 251(2), pages 640-650.
    5. Baptiste, Philippe & Peridy, Laurent & Pinson, Eric, 2003. "A branch and bound to minimize the number of late jobs on a single machine with release time constraints," European Journal of Operational Research, Elsevier, vol. 144(1), pages 1-11, January.
    6. Gio Kao & Edward Sewell & Sheldon Jacobson & Shane Hall, 2012. "New dominance rules and exploration strategies for the 1|r i |∑U i scheduling problem," Computational Optimization and Applications, Springer, vol. 51(3), pages 1253-1274, April.
    7. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    8. Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
    9. Peridy, Laurent & Pinson, Eric & Rivreau, David, 2003. "Using short-term memory to minimize the weighted number of late jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 148(3), pages 591-603, August.
    10. François Clautiaux & Boris Detienne & Henri Lefebvre, 2023. "A two-stage robust approach for minimizing the weighted number of tardy jobs with objective uncertainty," Journal of Scheduling, Springer, vol. 26(2), pages 169-191, April.
    11. Gupta, Jatinder N. D. & Ho, Johnny C., 1996. "Scheduling with two job classes and setup times to minimize the number of tardy jobs," International Journal of Production Economics, Elsevier, vol. 42(3), pages 205-216, April.
    12. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    13. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    14. Cai, X. & Lum, V. Y. S. & Chan, J. M. T., 1997. "Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties," European Journal of Operational Research, Elsevier, vol. 98(1), pages 154-168, April.
    15. Luca Benini & Michele Lombardi & Michela Milano & Martino Ruggiero, 2011. "Optimal resource allocation and scheduling for the CELL BE platform," Annals of Operations Research, Springer, vol. 184(1), pages 51-77, April.
    16. 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.
    17. Berghman, Lotte & Leus, Roel, 2015. "Practical solutions for a dock assignment problem with trailer transportation," European Journal of Operational Research, Elsevier, vol. 246(3), pages 787-799.
    18. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David, 2017. "Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling," European Journal of Operational Research, Elsevier, vol. 257(2), pages 439-455.
    19. Velez, Sara & Dong, Yachao & Maravelias, Christos T., 2017. "Changeover formulations for discrete-time mixed-integer programming scheduling models," European Journal of Operational Research, Elsevier, vol. 260(3), pages 949-963.
    20. Danny Hermelin & Matthias Mnich & Simon Omlor, 2024. "Serial batching to minimize the weighted number of tardy jobs," Journal of Scheduling, Springer, vol. 27(6), pages 545-556, December.

    More about this item

    Statistics

    Access and download statistics

    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:eee:ejores:v:189:y:2008:i:3:p:1284-1304. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.