zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

90B35Scheduling theory, deterministic
90C60Abstract computational complexity for mathematical programming problems
90C59Approximation methods and heuristics
90-02Research monographs (optimization)
Full Text: DOI
[1] Alidaee, B.: Single machine scheduling with nonlinear cost functions. Computers and operations research 18, No. 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, No. 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, No. 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, No. 2, 81-84 (2002) · Zbl 1032.68019
[7] Biskup, D.: Single-machine scheduling with learning considerations. European journal of operational research 115, No. 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, No. 3, 127-129 (1995) · Zbl 0841.90072
[11] Chen, Z. -L.: Parallel machine scheduling with time-dependent processing times. Discrete applied mathematics 70, No. 1, 81-93 (1996) · Zbl 0855.68032
[12] Chen, Z. -L.: Erratum: parallel machine scheduling with time-dependent processing times. Discrete applied mathematics 75, No. 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, No. 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, No. 2, 75-79 (1998)
[15] Cheng, T. C. E.; Ding, Q.: The time dependent machine makespan problem is strongly NP-complete. Computers and operations research 26, No. 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, No. 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, No. 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, No. 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, No. 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) · 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, No. 1, 297-300 (1996) · Zbl 0875.68080
[24] Gawiejnowicz, S.; Pankowska, L.: Scheduling jobs with varying processing times. Information processing letters 54, No. 3, 175-178 (1995) · Zbl 0875.68421
[25] Gawiejnowicz, S.; Kurc, W.; Pankowska, L.: A greedy approach for a time-dependent scheduling problem. Lecture notes on computer science 2328, 79-86 (2002) · Zbl 1057.68547
[26] Gawiejnowicz, S.; Kurc, W.; Pankowska, L.: Bicriterion approach to a single machine time-dependent scheduling problem. Operations research Proceedings, 199-206 (2002) · Zbl 1057.68547
[27] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: 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, No. 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, No. 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, No. 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, No. 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, No. 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, No. 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, No. 1, 56-64 (1990) · Zbl 0717.90034
[41] Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy; Shmoys, D. B.: Sequencing and scheduling: algorithms and complexity. Logistics of production and inventory 4, 445-522 (1993)
[42] Mohring, R. H.; Rademacher, F. J.: An introduction to stochastic scheduling problems. Contributions to operations research, 72-130 (1985)
[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, No. 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, No. 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.: \wedge-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, No. 4, 205-214 (1998)
[49] Mosheiov, G.: Scheduling problems with a learning effect. European journal of operational research 132, No. 3, 687-693 (2001) · Zbl 1017.90051
[50] Mosheiov, G.: Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete applied mathematics 117, No. 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, No. 6, 327-333 (2002)
[52] Pinedo, M.: Scheduling, theory, algorithms and systems. (1995) · Zbl 1145.90393
[53] Righter, R.: Stochastic scheduling. Stochastic orders (1994) · Zbl 0833.90067
[54] Kan, A. H. G. Rinnooy: Machine scheduling problems: classification, complexity and computations. (1976) · 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, No. 3, 394-403 (1994) · Zbl 0816.90088
[59] Tanaev, V. S.; Gordon, V. S.; Shafransky, Y. M.: Scheduling theory, single-stage systems. (1994) · 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, No. 3, 155-156 (1995) · Zbl 0875.68422