IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v34y1988i7p843-858.html
   My bibliography  Save this article

Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs

Author

Listed:
  • C. N. Potts

    (Faculty of Mathematical Studies, University of Southampton, Southampton, England)

  • L. N. Van Wassenhove

    (Afdeling Industrieel Beleid, Katholieke Universiteit Leuven, Belgium)

Abstract

This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given.

Suggested Citation

  • C. N. Potts & L. N. Van Wassenhove, 1988. "Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs," Management Science, INFORMS, vol. 34(7), pages 843-858, July.
    • Handle: RePEc:inm:ormnsc:v:34:y:1988:i:7:p:843-858
    DOI: 10.1287/mnsc.34.7.843
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.34.7.843
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.34.7.843?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.
    2. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    3. Hejl, Lukáš & Šůcha, Přemysl & Novák, Antonín & Hanzálek, Zdeněk, 2022. "Minimizing the weighted number of tardy jobs on a single machine: Strongly correlated instances," European Journal of Operational Research, Elsevier, vol. 298(2), pages 413-424.
    4. Gaia Nicosia & Andrea Pacifici & Ulrich Pferschy & Julia Resch & Giovanni Righini, 2021. "Optimally rescheduling jobs with a Last-In-First-Out buffer," Journal of Scheduling, Springer, vol. 24(6), pages 663-680, December.
    5. Tzafestas, Spyros & Triantafyllakis, Alekos, 1993. "Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 35(5), pages 397-434.
    6. Jinliang Cheng & Hiroshi Kise & Hironori Matsumoto, 1997. "A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 96(3), pages 578-590, February.
    7. M'Hallah, Rym & Bulfin, R. L., 2003. "Minimizing the weighted number of tardy jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 145(1), pages 45-56, February.
    8. 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.
    9. Akturk, M. Selim & Ozdemir, Deniz, 2001. "A new dominance rule to minimize total weighted tardiness with unequal release dates," European Journal of Operational Research, Elsevier, vol. 135(2), pages 394-412, December.
    10. Charles H. Reilly, 2009. "Synthetic Optimization Problem Generation: Show Us the Correlations!," INFORMS Journal on Computing, INFORMS, vol. 21(3), pages 458-467, August.
    11. 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.
    12. Hill, Raymond R. & Reilly, Charles H., 2000. "Multivariate composite distributions for coefficients in synthetic optimization problems," European Journal of Operational Research, Elsevier, vol. 121(1), pages 64-77, February.
    13. Dauzere-Peres, Stephane, 1995. "Minimizing late jobs in the general one machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 81(1), pages 134-142, February.
    14. 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.
    15. J. M. van den Akker & J. A. Hoogeveen & S. L. van de Velde, 1999. "Parallel Machine Scheduling by Column Generation," Operations Research, INFORMS, vol. 47(6), pages 862-872, December.
    16. Stéphane Dauzère‐Pérès & Marc Sevaux, 2003. "Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(3), pages 273-288, April.
    17. Nicholas G. Hall & Marc E. Posner, 2001. "Generating Experimental Data for Computational Testing with Machine Scheduling Applications," Operations Research, INFORMS, vol. 49(6), pages 854-865, December.
    18. Raymond R. Hill & Charles H. Reilly, 2000. "The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance," Management Science, INFORMS, vol. 46(2), pages 302-317, February.
    19. Reilly, Charles H. & Sapkota, Nabin, 2015. "A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances," European Journal of Operational Research, Elsevier, vol. 241(3), pages 642-652.
    20. Vincent T’kindt & Federico Della Croce & Jean-Louis Bouquard, 2007. "Enumeration of Pareto Optima for a Flowshop Scheduling Problem with Two Criteria," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 64-72, February.
    21. Nicholas G. Hall & Marc E. Posner, 2007. "Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures," Operations Research, INFORMS, vol. 55(4), pages 703-716, August.
    22. Ulrich Pferschy & Julia Resch & Giovanni Righini, 2023. "Algorithms for rescheduling jobs with a LIFO buffer to minimize the weighted number of late jobs," Journal of Scheduling, Springer, vol. 26(3), pages 267-287, June.

    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:ormnsc:v:34:y:1988:i:7:p:843-858. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.