×

Minimizing the total weighted completion time of deteriorating jobs. (English) Zbl 1032.68019

Summary: The paper deals with a single machine problem of scheduling jobs with start time dependent processing times to minimize the total weighted completion time. The computational complexity of this problem was unknown for ten years. We prove that the problem is NP-hard.

MSC:

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

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] Bachman, A.; Ng, C. T.; Cheng, T. C.E.; Janiak, A., Scheduling deteriorating jobs to minimize the total weighted completion time, Working paper (2000), The Hong Kong Polytechnic University, (sent for possible publication in European J. Oper. Res.)
[3] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Oper. Res., 38, 3, 495-498 (1990) · Zbl 0703.90051
[4] 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
[5] 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. of Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[6] Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Oper. Res., 39, 6, 979-991 (1991) · Zbl 0748.90033
[7] Mosheiov, G., Scheduling jobs under simple linear deterioration, Comput. Oper. Res., 21, 6, 653-659 (1994) · Zbl 0810.90074
[8] Mosheiov, G., \(Λ\)-shaped policies to schedule deteriorating jobs, J. Oper. Res. Soc., 47, 1184-1191 (1996) · Zbl 0869.90039
[9] Smith, W. E., Various optimizers for single-stage production, Naval Res. Logistics Quarterly, 3, 59-66 (1956)
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.