×

Scheduling of deteriorating jobs with release dates to minimize the maximum lateness. (English) Zbl 1252.90027

Summary: We consider the problem of scheduling \(n\) deteriorating jobs with release dates on a single (batching) machine. Each job’s processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. When the machine can process only one job at a time, we first show that the problem is NP-hard even if there are only two distinct release dates. Then we present a 2-approximation algorithm for the case where all jobs have negative due dates. Furthermore, we prove that the earliest due date (EDD) rule provides an optimal solution to the case where all jobs have agreeable release dates, due dates and deteriorating rates, and that the EDD rule gives the worst order for the general case, respectively. When the machine can process up to \(b\) (\(b=\infty\)) jobs simultaneously as a batch, i.e., the unbounded parallel-batch scheduling model, we show that the problem is NP-hard and present one property of the optimal schedule for the case where all jobs have agreeable release dates and due dates.

MSC:

90B35 Deterministic scheduling theory in operations research
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brucker, P.; Gladky, A.; Hoogeveen, H.; Kovalyov, M. Y.; Potts, C. N.; Tautenhahn, T.; van de Velde, S. L., Scheduling a batching, Journal of Scheduling, 1, 31-54 (1998) · Zbl 0909.90172
[2] A. Bachman, A. Janiak, Scheduling Jobs with Special Type of Start Time Dependent Processing Time. Report no. 34/97, Institute of Engineering Cybernetics, Wroclaw University of Technology, Wroclaw, 1997.; A. Bachman, A. Janiak, Scheduling Jobs with Special Type of Start Time Dependent Processing Time. Report no. 34/97, Institute of Engineering Cybernetics, Wroclaw University of Technology, Wroclaw, 1997.
[3] Bachman, A.; Janiak, A., Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126, 557-566 (2000) · Zbl 0976.90039
[4] Chen, Z. L., Parallel machine scheduling with time-dependent processing times, Discrete Applied Mathematics, 70, 81-93 (1996) · Zbl 0855.68032
[5] Cheng, T. C.E.; Ding, Q., Single machine scheduling with deadlines and increasing rates of processing times, Acta Informatica, 36, 9-10, 673-692 (2000) · Zbl 0958.68018
[6] Cheng, T. C.E.; Ding, Q., Single machine scheduling with step-dependent processing times, European Journal of Operational Research, 134, 623-630 (2001) · Zbl 0984.90014
[7] Cheng, T. C.E.; Liu, Z. H.; Yu, W. C., Scheduling jobs with release dates and deadline on a batch processing machine, IIE Transactions, 33, 685-690 (2001)
[8] M.R. Garey, D.S. Johnsonm, Computers and intractability: a guide to the theory of NP-Completeness, Freeman, New York, 1979.; M.R. Garey, D.S. Johnsonm, Computers and intractability: a guide to the theory of NP-Completeness, Freeman, New York, 1979.
[9] Graham, R. L.; Lawle; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann Disc Math, 5, 287-326 (1979) · Zbl 0411.90044
[10] Hsu, Y. S.; Lin, B. M.T., Minimization of maximum lateness under linear deterioration, Omeg, 31, 6, 459-469 (2003)
[11] Ji, M.; Cheng, T. C.E., Parallel-machine scheduling with simple linear deterioration to minimize total completion time, European Journal of Operational Research, 188, 342-347 (2008) · Zbl 1149.90343
[12] Ji, M.; Cheng, T. C.E., Parallel machine scheduling of single linear deteriorating jobs, Theoretical Computer Science, 410, 3761-3768 (2009) · Zbl 1171.68003
[13] Kunnathur, A. S.; Gupta, S. K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problems, European Journal of Operational Research, 47, 56-64 (1990) · Zbl 0717.90034
[14] Kovalyov, M. Y.; Kubiak, W., A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3, 4, 287-297 (1998) · Zbl 0903.90100
[15] Lee, C. Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, 764-775 (1992) · Zbl 0759.90046
[16] Liu, Z. H.; Yu, W. C., Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics, 70, 81-93 (2000) · Zbl 0969.90046
[17] Lu, L. F.; Cheng, T. C.E.; Yuan, J. J.; Zhang, L. Q., Bounded single-machine parallel-batch scheduling with release dates and rejection, Computer and Operations Research, 36, 2748-2751 (2009) · Zbl 1160.90477
[18] Li, S. S.; Ng, C. T.; Cheng, T. C.E.; Yuan, J. J., Parallel-batch scheduling of deteriorating jobs with release date to minimize the makespan, European Journal of Operational Research, 210, 482-488 (2011) · Zbl 1213.90121
[19] Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074
[20] Mosheiov, G., Multi-machine scheduling with linear deterioration, INFOR, 36, 205-214 (1998) · Zbl 07677568
[21] Miao, C. X.; Zhang, Z. Y.; Cao, Z. G., Parallel-batch scheduling of deteriorating jobs with release date to minimize the makespan, Information Processing Letters, 111, 798-803 (2011)
[22] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: a review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028
[23] Qi, X. L.; Zhou, S. G.; Yuan, J. J., Single machine parallel-batch scheduling with deteriorating jobs, Theoretical Computer Science, 410, 830-836 (2009) · Zbl 1162.90015
[24] Sundararaghavan, P. S.; Kunnathur, A. S., Single machine scheduling with start time-dependent processing times: some solvable cases, European Journal of Operational Research, 78, 393-403 (1994) · Zbl 0816.90088
[25] Webster; Baker, K. R., Scheduling groups of jobs on a single machine, Operations Research, 43, 692-7039 (1995) · Zbl 0857.90062
[26] Zhang, Y. Z.; Cao, Z. G., Parallel batch scheduling: a survey, Advances of mathematics, 37, 392-408 (2008) · Zbl 1482.90096
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.