×

Scheduling linear deteriorating jobs with an availability constraint on a single machine. (English) Zbl 1100.68009

Summary: We consider a single machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time and the machine is subject to an availability constraint. We consider the non-resumable case. The objectives are to minimize the makespan and the total completion time. We show that both problems are NP-hard and present pseudo-polynomial time optimal algorithms to solve them. Furthermore, for the makespan problem, we present an optimal approximation algorithm for the on-line case, and a fully polynomial time approximation scheme for the off-line case. For the total completion time problem, we provide a heuristic and evaluate its efficiency by computational experiments.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alidaee, B.; Womer, N. K., Scheduling with time dependent processing times: review and extensions, J. Oper. Res. Soc., 50, 711-720 (1999) · Zbl 1054.90542
[2] Babat, L. G., Linear functions on the \(n\)-dimensional unit cube, Dokl. Akad. Nauk SSSR, 221, 761-762 (1975), (in Russian) · Zbl 0325.90037
[3] Brown, S.; Yechiali, U., Scheduling deteriorating jobs on a single process, Oper. Res., 38, 495-498 (1990) · Zbl 0703.90051
[4] Chen, Z. L., Parallel machine scheduling with time dependent processing times, Discrete Appl. Math., 70, 81-93 (1996) · Zbl 0855.68032
[5] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European J. Oper. Res., 152, 1-13 (2004) · Zbl 1030.90023
[6] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[7] Gens, G. V.; Levner, E. V., Approximate algorithms for certain universal problems in scheduling theory, Eng. Cybernet., 6, 38-43 (1978), (in Russian) · Zbl 0446.90041
[8] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[9] Graves, G. H.; Lee, C. Y., Scheduling maintenance and semi-resumable jobs on a single machine, Naval Res. Logist., 46, 845-863 (1999) · Zbl 0931.90015
[10] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Comput. Industr. Eng., 14, 387-393 (1988)
[11] Johnson, D. S., The NP-complete columns: an ongoing guide, J. Algorithms, 2, 402 (1981)
[12] Kunnathur, A. S.; Gupta, S. K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European J. Oper. Res., 47, 56-64 (1990) · Zbl 0717.90034
[13] Lee, C. Y., Machine scheduling with an availability constraint, J. Global Optim., 8, 395-417 (1996) · Zbl 0870.90071
[14] Lee, C. Y.; Lei, L.; Pinedo, M., Current trend in deterministic scheduling, Ann. Oper. Res., 70, 1-42 (1997)
[15] Mosheiov, G., Scheduling jobs under simple linear deterioration, Comput. Oper. Res., 21, 653-659 (1994) · Zbl 0810.90074
[16] Mosheiov, G., Scheduling jobs with step-deterioration: minimizing makespan on single and multi-machine, Comput. Industr. Eng., 28, 869-879 (1995)
[17] Pinedo, M., Scheduling: theory, algorithms, and systems (2002), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ · Zbl 1145.90394
[18] Wu, C. C.; Lee, W. C., Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Inform. Process. Lett., 87, 89-93 (2003) · Zbl 1161.68367
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.