Skip to main content
SpringerLink
Log in

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

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

Abstract

In this note, we study a single-machine scheduling problem with deteriorating jobs whose processing times are an increasing function of their start times. The objective is to determine the optimal due-date and schedule simultaneously to minimize the total of due-date, earliness and tardiness penalties. We give a concise analysis of the problem and provide a polynomial time algorithm to solve the problem. Moreover, the algorithm can be easily applied to the ‘mirror’ scheduling problem in which the actual processing time of a job is a decreasing function of its starting time.

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

  • 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: 81–84.

    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, Kang L and Ng CT (2004). Due-date assignment and single machine scheduling with deteriorating jobs. Opl Res Soc 55: 198–203.

    Article  Google Scholar 

  • Cheng TCE, Kang L and Ng CT (2005). Single machine due-date scheduling of jobs with decreasing start-time dependent processing times. Int Trans Opns Res 12: 355–366.

    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 

  • Hardy GH, Littlewood JE and Polya G (1967). Inequalities. Cambridge University Press: London p. 261.

    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 Opnl Res 47: 56–64.

    Article  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 to schedule deteriorating jobs. Opnl Res Soc 47: 1184–1191.

    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 

  • Zhao CL and Tang HY (2005). Single machine scheduling problems with deteriorating jobs. Appl Math Comput 161: 865–874.

    Google Scholar 

Download references

Acknowledgements

We are grateful to two anonymous referees for their helpful comments on an earlier version of the paper. This research is supported in part by the National Science Council of Taiwan, Republic of China, under grant number NSC-94-2213-E-150-016.

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. J Oper Res Soc 59, 857–859 (2008). https://doi.org/10.1057/palgrave.jors.2602396

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2602396

Keywords

Search

Navigation