×

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, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Janiak, A., One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints, Kybernetika, 23, 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, 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, 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, 2, 413-420 (1995) · Zbl 0821.90069
[9] Armstrong, R.; Gu, S.; Lei, L., An \(O(N log(1/ε))\) 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.; 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.; 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.; Kuhn HW, Tucker AW. Nonlinear programming. Proceedings of the Second Symposium. Berkeley: University of California Press, 1951. p. 481-92.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.