Abstract
Recently, deteriorating job scheduling problems have received increasing attention. However, the majority of the research assumes that the actual job processing time is a function of its starting time. In this note, we develop a new deterioration model where the actual job processing time is a function of jobs already processed. We show that the single-machine makespan problem remains polynomially solvable under the proposed model.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Williams TJ (ed) (1986) Analysis and design of hierarchical control systems: With Special reference to steel plant operations. North-Holland, Amsterdam
Gupta JND, Gupta SK (1988) Single facility scheduling with nonlinear processing times. Comput Ind Eng 14:387–393
Janiak A (1998) Single machine sequencing with linear models of release dates. Nav Res Logist 45:99–113
Kunnathur AS, Gupta SK (1990) Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. Eur J Oper Res 47(1):56–64
Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38:495–498
Mosheiov G (1994) Scheduling jobs under simple linear deterioration. Comput Oper Res 21(6):653–659
Sundararaghavan PS, Kunnathur A (1994) Single machine scheduling with start time dependent processing time: Some solvable cases. Eur J Oper Res 78(3):394–403
Chen ZL (1995) A note on single-processor scheduling with time-dependent execution times. Oper Res Lett 17:127–129
Cheng TCE, Ding Q (1998) The complexity of single machine scheduling with release times. Inf Process Lett 65(2):75–79
Bachman A, Cheng TCE, Janiak A, Ng CT (2002) Scheduling start time dependent jobs to minimize the total weighted completion time. J Oper Res Soc 53(6):688–693
Ng CT, Cheng TCE, Bachman A (2002) Three scheduling problems with deteriorating jobs to minimize the total completion time. Inf Process Lett 81(6):327–333
Cheng TCE, Ding Q (2001) Single machine scheduling with step-deteriorating processing times. Eur J Oper Res 134:623–630
Cheng TCE, Ding Q, Kovalyov MY, Bachman A, Janiak A (2003) Scheduling jobs with piecewise linear decreasing processing times. Nav Res Logist 50(6):531–554
Cheng TCE, Ding Q (2003) Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine. Comput Oper Res 30(1):51–62
Wu CC, Lee WC, Shiau YR (2007) Minimizing the total weighted completion time on a single machine under linear deterioration. Int J Adv Manuf Technol 33:1237–1243
Shiau YR, Lee WC, Wu CC, Chang CM (2007) Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration. Int J Adv Manuf Technol 34:774–782
Guo AX, Wang JB (2005) Single machine scheduling with deteriorating jobs under the group technology assumption. Int J Pure Appl Math 18(2):225–231
Xu F, Guo AX, Wang JB, Shan F (2006) Single machine scheduling problem with linear deterioration under group technology. Int J Pure Appl Math 28:401–406
Wang JB, Guo AX, Shan F, Jiang B, Wang LY (2007) Single machine group scheduling under decreasing linear deterioration. J Appl Math Comput 24:283–293
Alidaee B, Womer NK (1999) Scheduling with time dependent processing times: Review and extensions. J Oper Res Soc 50:711–720
Cheng TCE, Ding Q, Lin BMT (2004) A concise survey of scheduling with time-dependent processing times. Eur J Oper Res 152:1–13
Toksari MD, Güner E (2007) Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach. The International Journal of Advanced Manufacturing Technology DOI 10.1007/s00170-007-1128-3
Wang JB, Lin L, Shan F (2007) Single-machine group scheduling problems with deteriorating jobs. The International Journal of Advanced Manufacturing Technology DOI 10.1007/s00170-007-1255-x
Koulamas C, Kyparisis GJ (2007) Single-machine and two-machine flowshop scheduling with general learning functions. Eur J Oper Res 178(2):402–407
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lee, WC., Wu, CC. & Liu, HC. A note on single-machine makespan problem with general deteriorating function. Int J Adv Manuf Technol 40, 1053–1056 (2009). https://doi.org/10.1007/s00170-008-1421-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-008-1421-9