Abstract
We address a scheduling problem that arises in highly parallelized environments like modern multi-core CPU/GPU computer architectures where simultaneously active jobs share a common limited resource, e.g., memory cache. The scheduler must ensure that the demand for the common resource never exceeds the available capacity. This introduces an orthogonal constraint to the classical minimum makespan scheduling problem. Such a constraint also arises in other contexts where a common resource is shared across machines.
We study the non-preemptive case of this problem and present a (2+ϵ)-approximation algorithm which relies on the interplay of several classical and modern techniques in scheduling like grouping, job-classification, and the use of configuration-LPs. This improves upon previous bound of 3 that can be obtained by list scheduling approaches, and gets close to the (3/2−ϵ) inapproximability bound. If the number of machines or the number of different resource requirements are bounded by a constant we obtain a polynomial time approximation scheme.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Artigues, C., Demassey, S., Néron, E.: Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications (ISTE). Wiley, New York (2010)
Blazewicz, J., Lenstra, J., Kan, A.: Scheduling subject to resource constraints: classification and complexity. Discrete Appl. Math. 5(1), 11–24 (1983)
Garey, M.R., Grahams, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4, 187–200 (1975)
Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4, 397–411 (1975)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freemann, New York (1979)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 263–269 (1969)
Grigoriev, A., Sviridenko, M., Uetz, M.: Machine scheduling with resource dependent processing times. Math. Program. 110, 209–228 (2007)
Hartmann, S., Briskorn, D.: A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207, 1–14 (2010)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144–162 (1987)
Jansen, K., Porkolab, L.: On preemptive resource constrained scheduling: polynomial-time approximation schemes. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 2337, pp. 329–349. Springer, Berlin (2006)
Sahni, S.: Algorithms for scheduling independent tasks. J. ACM 23, 116–127 (1976)
Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+ε in linear time. Combinatorica 1, 349–355 (1981)
Acknowledgements
We would like to thank Marco Di Summa, Friedrich Eisenbrand, Thomas Rothvoß, and José Verschae for helpful discussions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Niemeier, M., Wiese, A. Scheduling with an Orthogonal Resource Constraint. Algorithmica 71, 837–858 (2015). https://doi.org/10.1007/s00453-013-9829-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-013-9829-5