##
**A concise survey of scheduling with time-dependent processing times.**
*(English)*
Zbl 1030.90023

Summary: We consider a class of machine scheduling problems in which the processing time of a task is dependent on its starting time in a schedule. On reviewing the literature on this topic, we provide a framework to illustrate how models for this class of problems have been generalized from the classical scheduling theory. A complexity boundary is presented for each model and related existing results are consolidated. We also introduce some enumerative solution algorithms and heuristics and analyze their performance. Finally, we suggest a few interesting areas for future research.

### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C60 | Abstract computational complexity for mathematical programming problems |

90C59 | Approximation methods and heuristics in mathematical programming |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |

PDF
BibTeX
XML
Cite

\textit{T. C. E. Cheng} et al., Eur. J. Oper. Res. 152, No. 1, 1--13 (2004; Zbl 1030.90023)

Full Text:
DOI

### References:

[1] | Alidaee, B., Single machine scheduling with nonlinear cost functions, Computers and operations research, 18, 3, 317-322, (1991) · Zbl 0724.90030 |

[2] | Alidaee, B.; Womer, N.K., Scheduling with time dependent processing times: review and extensions, Journal of the operational research society, 50, 711-720, (1999) · Zbl 1054.90542 |

[3] | Bachman, A., Janiak, A., 1997. Scheduling Jobs with Special Type of Start Time Dependent Processing Time, Report no. 34/97, Institute of Engineering Cybernetics, Wroclaw University of Technology, Wroclaw |

[4] | Bachman, A.; Janiak, A., Minimizing maximum lateness under linear deterioration, European journal of operational research, 126, 3, 557-566, (2000) · Zbl 0976.90039 |

[5] | 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, 6, 688-693, (2002) · Zbl 1059.90063 |

[6] | Bachman, A.; Janiak, A.; Kovalyov, M.Y., Minimizing the total weighted completion time of deteriorating jobs, Information processing letters, 81, 2, 81-84, (2002) · Zbl 1032.68019 |

[7] | Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 1, 173-178, (1999) · Zbl 0946.90025 |

[8] | Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations research, 38, 495-498, (1990) · Zbl 0703.90051 |

[9] | Cai, J-Y.; Cai, P.; Zhu, Y., On a scheduling problem of time deteriorating jobs, Journal of complexity, 14, 190-209, (1998) · Zbl 0910.68019 |

[10] | Chen, Z.-L., A note on single-processor scheduling with time-dependent execution times, Operations research letters, 17, 3, 127-129, (1995) · Zbl 0841.90072 |

[11] | Chen, Z.-L., Parallel machine scheduling with time-dependent processing times, Discrete applied mathematics, 70, 1, 81-93, (1996) · Zbl 0855.68032 |

[12] | Chen, Z.-L., Erratum: parallel machine scheduling with time-dependent processing times, Discrete applied mathematics, 75, 1, 103, (1997) |

[13] | Cheng, T.C.E.; Ding, Q., The complexity of single machine scheduling with two distinct deadlines and identical decreasing rates of processing times, Computers and mathematics with applications, 35, 12, 95-100, (1998) · Zbl 0992.90027 |

[14] | Cheng, T.C.E.; Ding, Q., The complexity of single machine scheduling with release time, Information processing letters, 65, 2, 75-79, (1998) · Zbl 1338.68096 |

[15] | Cheng, T.C.E.; Ding, Q., The time dependent machine makespan problem is strongly NP-complete, Computers and operations research, 26, 8, 749-754, (1999) · Zbl 0932.90013 |

[16] | 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 |

[17] | Cheng, T.C.E.; Ding, Q., Single machine scheduling with step-deteriorating processing times, European journal of operational research, 134, 3, 623-630, (2001) · Zbl 0984.90014 |

[18] | Cheng, T.C.E.; Ding, Q., Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine, Computers and operations research, 30, 1, 51-62, (2003) · Zbl 1029.90028 |

[19] | Cheng, T.C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of operations research, 98, 273-290, (2000) · Zbl 0967.68019 |

[20] | Cheng, T.C.E., Ding, Q., Kovalyov, M.Y., Bachman, A., Janiak, A., 2003. Scheduling jobs with linearly decreasing processing times. Naval Research Logistics · Zbl 1043.90027 |

[21] | Finke, G.; Jiang, H., A variant of the permutation flow shop model with variable processing times, Discrete applied mathematics, 76, 1-3, 123-140, (1997) · Zbl 0882.90067 |

[22] | Garey, M.R.; Johnson, D.S., Computers and intractability–A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco · Zbl 0411.68039 |

[23] | Gawiejnowicz, S., A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information processing letters, 57, 1, 297-300, (1996) · Zbl 0875.68080 |

[24] | Gawiejnowicz, S.; Pankowska, L., Scheduling jobs with varying processing times, Information processing letters, 54, 3, 175-178, (1995) · Zbl 0875.68421 |

[25] | Gawiejnowicz, S.; Kurc, W.; Pankowska, L., A greedy approach for a time-dependent scheduling problem, (), 79-86 · Zbl 1057.68547 |

[26] | Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Bicriterion approach to a single machine time-dependent scheduling problem, (), 199-206 |

[27] | 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, (1976) · Zbl 0411.90044 |

[28] | Gupta, S.K.; Kunnathur, A.S.; Dandapani, K., Optimal repayment policies for multiple loans, Omega, 15, 4, 323-330, (1987) |

[29] | Gupta, J.N.D.; Gupta, S.K., Single facility scheduling with nonlinear processing times, Computers and industrial engineering, 14, 387-393, (1988) |

[30] | 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 |

[31] | Hsieh, Y.C.; Bricker, D.L., Scheduling linearly deteriorating jobs on multiple machines, Computers and industrial engineering, 32, 4, 727-734, (1997) |

[32] | Hsu, Y.H., Lin, B.M.T., 2002. Minimization of maximum lateness under linear deterioration (submitted) |

[33] | Janiak, A.; Kovalyov, M.Y., Single machine scheduling subject to deadlines and resource dependent processing times, European journal of operational research, 94, 2, 284-291, (1996) · Zbl 0947.90584 |

[34] | Jeng, A.A.K., Lin, B.M.T., 2002. Makespan minimization in single-machine scheduling with step-deterioration of processing times (submitted) · Zbl 1095.90038 |

[35] | Johnson, D.S., The NP-completeness column: an ongoing guide, Journal of algorithms, 4, 393-405, (1981) · Zbl 0494.68047 |

[36] | Kononov, A., 1997. Scheduling problems with linear increasing processing times. In: Operations Research Proceedings 1996. Springer, Berlin, pp. 199-206 |

[37] | Kononov, A.; Gawiejnowicz, S., NP-hard cases in scheduling deteriorating jobs on dedicated machines, Journal of the operational research society, 52, 6, 708-717, (2001) · Zbl 1181.90120 |

[38] | 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 |

[39] | Kubiak, W.; van de Velde, S.L., Scheduling deteriorating jobs to minimize makespan, Naval research logistics, 45, 5, 511-523, (1998) · Zbl 0936.90026 |

[40] | Kunnathur, A.S.; Gupta, S.K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European journal of operational research, 47, 1, 56-64, (1990) · Zbl 0717.90034 |

[41] | Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., Sequencing and scheduling: algorithms and complexity, (), 445-522 |

[42] | Mohring, R.H.; Rademacher, F.J., An introduction to stochastic scheduling problems, (), 72-130 |

[43] | Mosheiov, G., V-shaped policies for scheduling jobs, Operations research, 39, 979-991, (1991) · Zbl 0748.90033 |

[44] | Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and operations research, 21, 6, 653-659, (1994) · Zbl 0810.90074 |

[45] | Mosheiov, G., Scheduling jobs with step-deterioration: minimizing makespan on a single and multi-machine, Computers and industrial engineering, 28, 4, 869-879, (1995) |

[46] | Mosheiov, G., 1996a. On flow shop scheduling with deteriorating jobs. Working Paper, School of Business Administration, Hebrew University, Jerusalem |

[47] | Mosheiov, G., ∧-shaped polices to schedule deteriorating jobs, Journal of the operation al research society, 47, 1184-1191, (1996) · Zbl 0869.90039 |

[48] | Mosheiov, G., Multi-machine scheduling with linear deterioration, Infor, 36, 4, 205-214, (1998) |

[49] | Mosheiov, G., Scheduling problems with a learning effect, European journal of operational research, 132, 3, 687-693, (2001) · Zbl 1017.90051 |

[50] | Mosheiov, G., Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete applied mathematics, 117, 1-3, 195-209, (2002) · Zbl 1004.68031 |

[51] | Ng, C.T.; Cheng, T.C.E.; Bachman, A., Three scheduling problems with deteriorating jobs to minimize the total completion time, Information processing letters, 81, 6, 327-333, (2002) |

[52] | Pinedo, M., Scheduling, theory, algorithms and systems, (1995), Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393 |

[53] | Righter, R., Stochastic scheduling, () |

[54] | Rinnooy Kan, A.H.G., Machine scheduling problems: classification, complexity and computations, (1976), Martinus Nijhoff The Hague · Zbl 0366.90092 |

[55] | Sriskandarajah, C.; Goyal, S.K., Scheduling of a two machine flow-shop with processing time linearly dependent on job waiting-time, Journal of the operational research society, 40, 907-921, (1989) · Zbl 0682.90049 |

[56] | Sriskandarajah, C.; Wagneur, E., Hierarchical control of the two processor flow-shop with state-dependent processing times: complexity analysis and approximate algorithms, Infor, 29, 193-205, (1991) · Zbl 0778.90032 |

[57] | Sundararaghavan, P.S., Kunnathur, A.S., 1990. Single machine scheduling with due dates and processing time penalties. Proceedings of the National Meeting of the Decision Sciences Institute, Louisiana, USA · Zbl 0816.90088 |

[58] | Sundararaghavan, P.S.; Kunnathur, A.S., Single machine scheduling with start time-dependent processing times: some solvable cases, European journal of operational research, 78, 3, 394-403, (1994) · Zbl 0816.90088 |

[59] | Tanaev, V.S.; Gordon, V.S.; Shafransky, Y.M., Scheduling theory, single-stage systems, (1994), Kluwer Dordrecht · Zbl 0827.90079 |

[60] | Wagneur, E.; Sriskandarajah, C., The two-machine permutation flow shop with state-dependent processing times, Naval research logistics, 40, 697-717, (1993) · Zbl 0781.90057 |

[61] | Wagneur, E.; Sriskandarajah, C., Optimal control of a class of DEDS: flow-shops with state-dependent processing times, Discrete event dynamic systems: theory applications, 3, 397-425, (1993) · Zbl 0790.90046 |

[62] | Woeginger, G.J., Scheduling with time-dependent execution times, Information processing letters, 54, 3, 155-156, (1995) · Zbl 0875.68422 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.