zbMATH — the first resource for mathematics

Examples
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.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
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)
Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint. (English) Zbl 1180.90143
Summary: This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that, for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.
MSC:
90B35Scheduling theory, deterministic
References:
[1]Alidaee, B.; Womer, N. K.: Scheduling with time dependent processing processing times: review and extensions, Journal of the operational research society 50, 711-720 (1999) · Zbl 1054.90542
[2]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 (2004) · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[3]Browne, S.; Yechiali, U.: Scheduling deteriorating jobs on a single processor, Operations research 38, 495-498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495
[4]Mosheiov, G.: V-shaped policies for scheduling deteriorating jobs, Operations research 39, 979-991 (1991) · Zbl 0748.90033 · doi:10.1287/opre.39.6.979
[5]Mosheiov, G.: Scheduling jobs under simple linear deterioration, Computers and operations research 21, 653-659 (1994) · Zbl 0810.90074 · doi:10.1016/0305-0548(94)90080-9
[6]Sundararaghavan, P. S.; Kunnathur, A. S.: Single machine scheduling with start time dependent processing times: some solvable cases, European journal of operational research 78, 394-403 (1994) · Zbl 0816.90088 · doi:10.1016/0377-2217(94)90048-5
[7]Cheng, T. C. E.; Ding, Q.: The complexity of scheduling starting time dependent task with release dates, Information processing letters 65, 75-79 (1998)
[8]Bachman, A.; Janiak, A.: Minimizing maximum lateness under linear deterioration, European journal of operational research 126, 557-566 (2000) · Zbl 0976.90039 · doi:10.1016/S0377-2217(99)00310-0
[9]Bachman, A.; Janiak, A.; Kovalyov, M. Y.: Minimizing the total weighted completion time of deteriorating jobs, Information processing letters 81, 81-84 (2002) · Zbl 1032.68019 · doi:10.1016/S0020-0190(01)00196-X
[10]Wu, C. -C.; Lee, W. -C.: Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Information processing letters 87, 89-93 (2003) · Zbl 1161.68367 · doi:10.1016/S0020-0190(03)00262-X
[11]Hsu, Y. S.; Lin, B. M. T.: Minimization of maximum lateness under linear deterioration, Omega 31, 459-469 (2003)
[12]Chen, Z. -L.: Parallel machine scheduling with time dependent processing times, Discrete applied mathematics 70, 81-94 (1996) · Zbl 0855.68032 · doi:10.1016/0166-218X(96)00102-3
[13]Mosheiov, G.: Multi-machine scheduling with linear deterioration, Infor 36, 205-214 (1998)
[14]Mosheiov, G.: Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete applied mathematics 117, 195-209 (2002) · Zbl 1004.68031 · doi:10.1016/S0166-218X(00)00385-1 · doi:http://www.elsevier.com/gej-ng/10/16/23/128/27/41/abstract.html
[15]Wang, J. -B.; Xia, Z. -Q.: Flow shop scheduling with deteriorating jobs under dominating machines, Omega 34, 327-336 (2006)
[16]Wang, J. -B.; Xia, Z. -Q.: Flow shop scheduling problems with deteriorating jobs under dominating machines, Journal of the operational research society 57, 220-226 (2006) · Zbl 1090.90095 · doi:10.1057/palgrave.jors.2601959
[17]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 (1979) · Zbl 0411.90044
[18]Lawler, E. L.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Annals of discrete mathematics 2, 75-90 (1978) · Zbl 0374.68033
[19]Sidney, J. B.: Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, Operations research 22, 283-298 (1975) · Zbl 0304.90058 · doi:10.1287/opre.23.2.283
[20]Zhao C. Algorithms for some new classes of scheduling problems. PhD thesis, Northeastern University, China; 2003 [in Chinese].
[21]Pinedo, M.: Scheduling: theory, algorithms, and systems, (2002)
[22]Brucker, P.: Scheduling algorithms, (2001)