# 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)
Convex resource allocation for minimizing the makespan in a single machine with job release dates. (English) Zbl 1076.68018
Summary: We consider the problem of scheduling jobs on a single machine where job-processing times are controllable through the allocation of a common limited resource. The release dates are known and the job-processing time is described by a convex decreasing resource consumption function. Our objective is to simultaneously determine the optimal job permutation and the resource allocation,such that the maximal completion time is minimized. We provide an $O(n)$ time optimization algorithm for the case of identical job release dates, and an $O(n^2)$ time optimization algorithm for the case of non-identical job release dates.

##### MSC:
 68M20 Performance evaluation of computer systems; queueing; scheduling 90B35 Scheduling theory, deterministic
Full Text:
##### References:
 [1] Janiak, A.: One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints. Kybernetika 23, No. 4, 289-293 (1987) · Zbl 0635.90048 [2] Van Wassenhove, L.; Baker, K. R.: A bicriterion approach to time/cost trade-offs in sequencing. European journal of operational research 11, 48-54 (1982) · Zbl 0482.90043 [3] Daniels, R. L.; Sarin, R. K.: Single machine scheduling with controllable processing times and number of jobs tardy. Operations research 37, No. 6, 981-984 (1989) · Zbl 0686.90023 [4] Daniels, R. L.: A multi-objective approach to resource allocation in single machine scheduling. European journal of operational research 48, 226-241 (1990) · Zbl 0825.90535 [5] 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 [6] Cheng, T. C. E.; Janiak, A.; Kovalyov, M. Y.: Bicriterion single machine scheduling with resource dependent processing times. SIAM journal on optimization 8, No. 2, 617-630 (1998) · Zbl 0907.68113 [7] Monma, Cl.; Schrijver, A.; Todd, M. J.; Wei, V. K.: Convex resource allocation problems on directed acyclic graphsduality, complexity, special cases and extensions. Mathematics of operations research 15, 736-748 (1990) · Zbl 0717.90080 [8] Scott, S. C.; Jefferson, T. R.: Allocation of resources in project management. International journal of systems science 26, No. 2, 413-420 (1995) · Zbl 0821.90069 [9] Armstrong, R.; Gu, S.; Lei, L.: An O(N $log(1/{\epsilon}))$ algorithm for the two-resource allocation problem with a non-differentiable convex objective function. Journal of the operational research society 46, 116-122 (1995) · Zbl 0835.90064 [10] Armstrong, R.; Gu, S.; Lei, L.: Solving a class of two-resource allocation problem by equivalent load method. Journal of the operational research society 48, 818-825 (1997) · Zbl 0890.90088 [11] Jackson JR. Scheduling a production line to minimize maximum tardiness. Management Sciences Research Project, Research Report 43, UCLA, 1995. [12] Karush W. Minima of functions of several variables with inequalities as side conditions. MS thesis, Department of Mathematics, University of Chicago, 1939. [13] Kuhn HW, Tucker AW. Nonlinear programming. Proceedings of the Second Symposium. Berkeley: University of California Press, 1951. p. 481--92.