Single machine scheduling with decreasing linear deterioration under precedence constraints. (English) Zbl 1189.90069

Summary: This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan, polynomial algorithms exist.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Alidaee, B.; Womer, N. K., Scheduling with time dependent processing processing times: Review and extensions, Journal of the Operational Research Society, 50, 711-720 (1999) · Zbl 1054.90542
[2] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[3] Ho, K. I-J.; Leung, J. Y-T.; Wei, W.-D., Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters, 48, 315-320 (1993) · Zbl 0942.68508
[4] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051
[5] Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Operations Research, 39, 979-991 (1991) · Zbl 0748.90033
[6] Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074
[7] Cheng, T. C.E.; Ding, Q., The complexity of scheduling starting time dependent task with release dates, Information Processing Letters, 65, 75-79 (1998) · Zbl 1338.68096
[8] Bachman, A.; Janiak, A., Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126, 557-566 (2000) · Zbl 0976.90039
[9] Bachman, A.; Janiak, A.; Kovalyov, M. Y., Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81, 81-84 (2002) · Zbl 1032.68019
[10] Hsu, Y. S.; Lin, B. M.T., Minimization of maximum lateness under linear deterioration, Omega, 31, 459-469 (2003)
[11] Chen, Z.-L., Parallel machine scheduling with time dependent processing times, Discrete Applied Mathematics, 70, 81-94 (1996) · Zbl 0855.68032
[12] Mosheiov, G., Multi-machine scheduling with linear deterioration, INFOR, 36, 205-214 (1998) · Zbl 07677568
[13] Mosheiov, G., Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics, 117, 195-209 (2002) · Zbl 1004.68031
[14] Wang, J.-B.; Xia, Z.-Q., Flow shop scheduling with deteriorating jobs under dominating machines, Omega, 34, 327-336 (2006) · Zbl 1090.90095
[15] Wang, J.-B.; Ng, C. T.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Computers and Operations Research, 35, 2684-2693 (2008) · Zbl 1180.90143
[16] Ng, C. T.; Cheng, T. C.E.; Bachman, A.; Janiak, A., Three scheduling problems with deteriorating jobs to minimize the total completion time, Information Processing Letters, 81, 327-333 (2002) · Zbl 1059.90063
[17] Bachman, A.; Cheng, T. C.E.; Janiak, A.; Ng, C. T., Scheduling start time dependent jobs to minimize the total weighted completion time, Journal of the Operational Research Society, 53, 688-693 (2002) · Zbl 1059.90063
[18] Wang, J.-B.; Xia, Z.-Q., Scheduling jobs under decreasing linear deterioration, Information Processing Letters, 94, 63-69 (2005) · Zbl 1182.68359
[19] Brucker, P., Scheduling Algorithms (2001), Springer · Zbl 1051.90011
[20] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice Hall · Zbl 1145.90394
[21] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[22] Sidney, J. B., Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, Operations Research, 22, 283-298 (1975) · Zbl 0304.90058
[23] Lawler, E. L., Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Annals of Discrete Mathematics, 2, 75-90 (1978) · Zbl 0374.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.