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 resource dependent release times and processing times. (English) Zbl 1065.90045
Summary: We consider the single machine scheduling problem with resource dependent release times and processing times, in which both the release times and processing times are strictly linear decreasing functions of the amount of resources consumed. The objective is to minimize the makespan plus the total resource consumption costs. We propose a heuristic algorithm for the general problem by utilizing some derived optimal properties and analyze its performance bound. For some special cases, we propose another heuristic algorithm that achieves a tighter performance bound.

MSC:
90B35Scheduling theory, deterministic
90C59Approximation methods and heuristics
WorldCat.org
Full Text: DOI
References:
[1] Alidaee, B.; Ahmadian, A.: Two parallel machine sequencing problems involving controllable job processing times. European journal of operational research 70, 335-341 (1993) · Zbl 0791.90028
[2] Chen, Z. L.; Lu, Q.; Tang, G.: Single machine scheduling with discretely controllable processing times. Operations research letters 21, 69-76 (1997) · Zbl 0888.90088
[3] Cheng, T. C. E.; Chen, Z. L.; Li, C. -L.: Parallel-machine scheduling with controllable processing times. IIE transactions 28, 177-180 (1996)
[4] Cheng, T. C. E.; Janiak, A.: Resource optimal control in some single-machine scheduling problems. IEEE transactions on automatic control 39, 1243-1246 (1994) · Zbl 0816.90080
[5] Cheng, T. C. E.; Janiak, A.; Kovalyov, M. Y.: Single machine batch scheduling with resource dependent setup and processing times. European journal of operational research 135, 177-183 (2001) · Zbl 1077.90525
[6] Cheng, T. C. E.; Kovalyov, M. Y.: Single machine batch scheduling with deadlines and resource dependent processing times. Operations research letters 17, 243-249 (1995) · Zbl 0858.90073
[7] Janiak, A.: Time-optimal control in a single machine problem with resource constraints. Automatica 22, 745-747 (1986) · Zbl 0608.90044
[8] Janiak, A.: Single machine scheduling problem with a common deadline and resource dependent release dates. European journal of operational research 53, 317-325 (1991) · Zbl 0743.90066
[9] Janiak, A.; Kovalyov, M. Y.: Single machine scheduling subject to deadlines and resource dependent processing times. European journal of operational research 94, 284-291 (1996) · Zbl 0947.90584
[10] Li, C. -L.; Sewell, E. C.; Cheng, T. C. E.: Scheduling to minimize release-time resource consumption and tardiness penalties. Naval research logistics 42, 949-966 (1995) · Zbl 0845.90074
[11] Nowicki, E.; Zdrzalka, S.: A survey of results for sequencing problems with controllable processing times. Discrete applied mathematics 26, 271-287 (1990) · Zbl 0693.90056
[12] Nowicki, E.; Zdrzalka, S.: A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times. Discrete applied mathematics 63, 237-256 (1995) · Zbl 0854.68007
[13] Panwalkar, S. S.; Rajagopalan, R.: Single-machine sequencing with controllable processing times. European journal of operational research 59, 298-302 (1992) · Zbl 0760.90058
[14] Van Wassenhove, L. N.; Baker, K. R.: A bicriterion approach to time/cost trade-offs in sequence. European journal of operational research 11, 48-54 (1982) · Zbl 0482.90043
[15] Vickson, R. G.: Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Operations research 28, 1155-1167 (1980) · Zbl 0449.90054
[16] Vickson, R. G.: Two single machine sequencing problems involving controllable job processing times. AIIE transactions 12, 258-262 (1980)
[17] Zdrzalka, S.: Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis. Operations research letters 10, 519-523 (1991) · Zbl 0744.90045
[18] Zhang, F.; Tang, G.; Chen, Z. L.: A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times. Operations research letters 29, 41-47 (2001) · Zbl 0981.90027