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)
Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs. (English) Zbl 1077.90025
Summary: we study a scheduling problem of minimizing the total completion time on a single machine where the processing time of a job is a step function of its starting time and a due date that is common to all jobs. This problem has been shown to be NP-hard in the literature. To derive optimal solutions from a practical aspect, we develop a lower bound and two elimination rules to design branch-and-bound algorithms. Through computational experiments, we show that the proposed properties are effective in curtailing unnecessary explorations during the solution-finding process, and that the synergy of these properties can solve problems with up to 100 jobs in a few seconds.

90B35Scheduling theory, deterministic
68M20Performance evaluation of computer systems; queueing; scheduling
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI
[1] Cheng, T. C. E.; Ding, Q.: Single machine scheduling with step-deteriorating processing times. European journal of operational research 134, 623-630 (2001) · Zbl 0984.90014
[2] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinooy: Optimization and approximation in deterministic sequencing and schedulinga survey. Annals of discrete mathematics 5, 287-326 (1976) · Zbl 0411.90044
[3] Gupta, S. K.; Kunnathur, A. S.; Dandapai, K.: Optimal repayment policies for multiple loans. Omega 15, 323-330 (1987)
[4] Tanaev, V. S.; Gordon, V. S.; Shafransky, Y. M.: Schedule theory, single-stage systems. (1994) · Zbl 0827.90079
[5] Gupta, J. N. D.; Gupta, S. K.: Single facility scheduling with nonlinear processing time. Computers and industrial engineering 14, 387-393 (1988)
[6] Chen, Z. L.: A note on single-processor scheduling with time-dependent execution times. Operations research letters 17, 127-129 (1995) · Zbl 0841.90072
[7] Cheng, T. C. E.; Ding, Q.: Single machine scheduling with deadlines and increasing rate of processing times. Acta informatica 36, 673-692 (2000) · Zbl 0958.68018
[8] Mosheiov, G.: Scheduling jobs under simple linear deterioration. Computers and operations research 21, 653-659 (1994) · Zbl 0810.90074
[9] 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, 56-64 (1990) · Zbl 0717.90034
[10] Kubiak, W.; Van De Velde, S. L.: Scheduling deteriorating jobs to minimize makespan. Naval research logistics 45, 511-523 (1998) · Zbl 0936.90026
[11] Mosheiov, G.: Scheduling jobs with step-deterioration; minimizing makespan on a single and multi-machine. Computers and industrial engineering 28, 869-879 (1995)
[12] Sundararaghavan, P. S.; Kunnathur, A. S.: Single machine scheduling with start time dependent processing timessome solvable cases. European journal of operational research 79, 394-403 (1994) · Zbl 0816.90088
[13] Jeng AAK, Lin BMT. Makespan minimization in single-machine scheduling with step-deterioration of processing times. Journal of the Operational Research Society 2002, manuscript submitted for publication.
[14] Garey, M. R.; Johnson, D. S.: Computers and intractability: a guide to the theory of NP-completeness. (1979) · Zbl 0411.68039
[15] Alidaee, B.; Womer, N. K.: Scheduling with time dependent processing timesreview and extensions. Journal of the operational research society 50, 711-720 (1999) · Zbl 1054.90542
[16] Cheng, T. C. E.; Ding, Q.; Lin, B. M. T.: A concise survey of scheduling with time-dependent processing times. European journal of operational research 152, 1-13 (2003) · Zbl 1030.90023