Skip to main content
SpringerLink
Log in

A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects

  • Technical Note
  • Published:
Journal of the Operational Research Society

Abstract

The concepts of deteriorating jobs and learning effects have been individually studied in many scheduling problems. This note considers a single-machine scheduling problem with deteriorating jobs and learning effects. All of the jobs have a common (but unknown) due date. The objective is to minimize the sum of the weighted earliness, tardiness and due-date penalties. An O(n 3) algorithm is proposed to optimally solve the problem with deteriorating jobs and job-dependent learning effect. Besides, an O(n log n) algorithm is provided to solve the problem with deteriorating jobs and job-independent learning effect.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alidaee B and Womer NK (1999). Scheduling with time dependent processing times: Review and extensions . Opl Res Soc 50: 711–729.

    Article  Google Scholar 

  • Bachman A and Janiak A (2000). Minimizing maximum lateness under linear deterioration . Eur J Opl Res 126: 557–566.

    Article  Google Scholar 

  • Bachman A, Janiak A and Kovalyov MY (2002). Minimizing the total weighted completion time of deteriorating jobs . Inform Process Lett 81: 8184.

    Article  Google Scholar 

  • Biskup D (1999). Single-machine scheduling with learning considerations . Eur J Opl Res 115: 173–178.

    Article  Google Scholar 

  • Biskup D (2008). A state-of-the-art review on scheduling with learning effects . Eur J Opl Res 188: 315–329.

    Article  Google Scholar 

  • Browne S and Yechiali U (1990). Scheduling deteriorating jobs on a single processor . Opns Res 38: 495–498.

    Article  Google Scholar 

  • Cheng TCE, Ding Q and Lin BMT (2004a). A concise survey of scheduling with time-dependent processing times . Eur J Opl Res 152: 1–13.

    Article  Google Scholar 

  • Cheng TCE, Kang L and Ng CT (2004b). Due-date assignment and single machine scheduling with deteriorating jobs . Opl Res Soc 55: 198–203.

    Article  Google Scholar 

  • Cheng TCE, Wu CC and Lee WC (2008). Some scheduling problems with deteriorating jobs and learning effects . Comput Ind Eng 54: 972–982.

    Article  Google Scholar 

  • Gordon V, Proth JM and Chu C (2002). A survey of the state-of-the-art of common due date assignment and scheduling research . Eur J Opl Res 135: 1–25.

    Article  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey . Ann Discrete Math 5: 287–326.

    Article  Google Scholar 

  • Kunnathur AS and Gupta SK (1990). Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem . Eur J Opl Res 47: 56–64.

    Article  Google Scholar 

  • Kuo WH and Yang DL (2006a). Single-machine group scheduling with a time-dependent learning effect . Comput Opns Res 33: 2099–2112.

    Article  Google Scholar 

  • Kuo WH and Yang DL (2006b). Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect . Eur J Opl Res 174: 1184–1190.

    Article  Google Scholar 

  • Lee WC (2004). A note on deteriorating jobs and learning in single-machine scheduling problems . Int J Bus Econ 3: 83–89.

    Google Scholar 

  • Mosheiov G (1991). V-shaped policies for scheduling deteriorating jobs . Opns Res 39: 979–991.

    Article  Google Scholar 

  • Mosheiov G (1994). Scheduling jobs under simple linear deterioration . Comput Opns Res 21: 653–659.

    Article  Google Scholar 

  • Mosheiov G (1995). Scheduling jobs with step-deterioration: Minimizing makespan on a single- and multi-machine . Comput Indust Eng 28: 869–879.

    Article  Google Scholar 

  • Mosheiov G (1996). Λ-shaped policies for schedule deteriorating jobs . Opl Res Soc 47: 1184–1191.

    Article  Google Scholar 

  • Mosheiov G (2001). Scheduling problems with a learning effect . Eur J Opl Res 132: 687–693.

    Article  Google Scholar 

  • Mosheiov G and Sidney JB (2003). Scheduling with general job-dependent learning curves . Eur J Opl Res 147: 665–670.

    Article  Google Scholar 

  • Panwalkar SS, Smith ML and Seidmann A (1982). Common due date assignment to minimize total penalty for the one machine scheduling problem . Opns Res 30: 391–399.

    Article  Google Scholar 

  • Wang JB (2007). Single-machine scheduling problems with the effects of learning and deterioration . Omega 35: 397–402.

    Article  Google Scholar 

  • Wang JB and Cheng TCE (2007a). Scheduling problems with the effects of deterioration and learning . Asia Pac J Opl Res 24: 245–261.

    Article  Google Scholar 

  • Wang X and Cheng TCE (2007b). Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan . Eur J Opl Res 178: 57–70.

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to the editor and the referees for their helpful comments and suggestions on an early version of this paper. This research is supported in part by the National Science Council of Taiwan, Republic of China, under grant number NSC-97-2221-E-150-056-MY2.

Author information

Authors and Affiliations

  1. National Formosa University, Yun-Lin, ROC, Taiwan

    W-H Kuo & D-L Yang

Authors
  1. W-H Kuo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D-L Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D-L Yang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kuo, WH., Yang, DL. A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects. J Oper Res Soc 62, 206–210 (2011). https://doi.org/10.1057/jors.2009.155

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.155

Keywords

Search

Navigation