IDEAS home Printed from
   My bibliography  Save this article

A survey of scheduling problems with late work criteria


  • Sterna, Malgorzata


The paper presents the first complete survey of scheduling problems with the late work criteria. Late work objective functions estimate the quality of a schedule based on durations of late parts of jobs, not taking into account the amount of delay for fully late jobs. The paper provides a formal definition of the late work parameter and compares the criteria based on it with other classical performance measures. It shows the relationship between the late work model and the imprecise computation model known from the hard real-time literature. Moreover, the paper presents a few real world applications of the late work objective function. The paper lists results obtained for nearly forty problems of scheduling jobs on a single machine, parallel (identical and uniform) machines and dedicated machines, investigated in the literature since 1984.

Suggested Citation

  • Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
  • Handle: RePEc:eee:jomega:v:39:y:2011:i:2:p:120-129

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "Complexity results for scheduling chains on a single machine," European Journal of Operational Research, Elsevier, vol. 4(4), pages 270-275, April.
    2. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    3. Lee, Wen-Chiung & Wu, Chin-Chia & Hsu, Peng-Hsiang, 2010. "A single-machine learning effect scheduling problem with release times," Omega, Elsevier, vol. 38(1-2), pages 3-11, February.
    4. Rad, Shahriar Farahmand & Ruiz, Rubén & Boroojerdian, Naser, 2009. "New high performing heuristics for minimizing makespan in permutation flowshops," Omega, Elsevier, vol. 37(2), pages 331-345, April.
    5. Yang, Suh-Jenq & Yang, Dar-Li, 2010. "Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities," Omega, Elsevier, vol. 38(6), pages 528-533, December.
    6. Fagerholt, Kjetil & Christiansen, Marielle & Magnus Hvattum, Lars & Johnsen, Trond A.V. & Vabø, Thor J., 2010. "A decision support methodology for strategic planning in maritime transportation," Omega, Elsevier, vol. 38(6), pages 465-474, December.
    7. Ronconi, Débora P. & Henriques, Luís R.S., 2009. "Some heuristic algorithms for total tardiness minimization in a flowshop with blocking," Omega, Elsevier, vol. 37(2), pages 272-281, April.
    8. Gribkovskaia, Irina V. & Kovalev, Sergey & Werner, Frank, 2010. "Batching for work and rework processes on dedicated facilities to minimize the makespan," Omega, Elsevier, vol. 38(6), pages 522-527, December.
    9. Carlier, J. & Pinson, E., 1994. "Adjustment of heads and tails for the job-shop problem," European Journal of Operational Research, Elsevier, vol. 78(2), pages 146-161, October.
    10. Sun Lee, Ik & Yoon, S.H., 2010. "Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs," Omega, Elsevier, vol. 38(6), pages 509-521, December.
    11. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    12. Almiñana, M. & Escudero, L.F. & Landete, M. & Monge, J.F. & Rabasa, A. & Sánchez-Soriano, J., 2010. "WISCHE: A DSS for water irrigation scheduling," Omega, Elsevier, vol. 38(6), pages 492-500, December.
    13. Blazewicz, Jacek & Pesch, Erwin & Sterna, Malgorzata & Werner, Frank, 2005. "The two-machine flow-shop problem with weighted late work criterion and common due date," European Journal of Operational Research, Elsevier, vol. 165(2), pages 408-415, September.
    14. Janiak, Adam & Rudek, RadosLaw, 2010. "A note on a makespan minimization problem with a multi-ability learning effect," Omega, Elsevier, vol. 38(3-4), pages 213-217, June.
    Full references (including those not matched with items on IDEAS)


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

    Cited by:

    1. Pan, Quan-Ke & Ruiz, Rubén, 2012. "An estimation of distribution algorithm for lot-streaming flow shop problems with setup times," Omega, Elsevier, vol. 40(2), pages 166-180, April.
    2. Xin Chen & Malgorzata Sterna & Xin Han & Jacek Blazewicz, 2016. "Scheduling on parallel identical machines with late work criterion: Offline and online cases," Journal of Scheduling, Springer, vol. 19(6), pages 729-736, December.
    3. repec:eee:ejores:v:266:y:2018:i:3:p:795-818 is not listed on IDEAS
    4. Lai, Peng-Jen & Lee, Wen-Chiung, 2011. "Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects," Omega, Elsevier, vol. 39(5), pages 467-471, October.
    5. Shi, Yuhui & Reich, Daniel & Epelman, Marina & Klampfl, Erica & Cohn, Amy, 2017. "An analytical approach to prototype vehicle test scheduling," Omega, Elsevier, vol. 67(C), pages 168-176.
    6. Karapetyan, Daniel & Mitrovic Minic, Snezana & Malladi, Krishna T. & Punnen, Abraham P., 2015. "Satellite downlink scheduling problem: A case study," Omega, Elsevier, vol. 53(C), pages 115-123.
    7. Yin, Yunqiang & Cheng, Shuenn-Ren & Cheng, T.C.E. & Wang, Du-Juan & Wu, Chin-Chia, 2016. "Just-in-time scheduling with two competing agents on unrelated parallel machines," Omega, Elsevier, vol. 63(C), pages 41-47.
    8. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.


    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:jomega:v:39:y:2011:i:2:p:120-129. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: .

    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 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.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.