Abstract
We address a scheduling problem that arises in highly parallelized environments like modern multi-core CPU/GPU computer architectures. Here 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 many other contexts where a common resource is shared across the machines.
We study the non-preemptive case of this problem and give 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 have a polynomial time approximation scheme.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Artigues, C., Demassey, S., Néron, E.: Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. In: ISTE (2010)
Blazewicz, J., Lenstra, J.K., Rinnooy Kan, A.H.G.: Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics 5(1), 11–24 (1983)
Chekuri, C., Khanna, S.: On multi-dimensional packing problems. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 185–194. SIAM (1999)
Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing 7, 1–17 (1978)
Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1 + ε in linear time. Combinatorica 1, 349–355 (1981)
Friesen, D.K.: Tighter bounds for the multifit processor scheduling algorithm. SIAM Journal on Computing 13, 170–181 (1984)
Garey, M.R., Grahams, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing 4, 187–200 (1975)
Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing (1975)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45, 1563–1581 (1966)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics 17, 263–269 (1969)
Grigoriev, A., Sviridenko, M., Uetz, M.: Machine scheduling with resource dependent processing times. Mathematical Programming 110, 209–228 (2007)
Hartmann, S., Briskorn, D.: A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of OR 207, 1–14 (2010)
Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. Thomson (1996)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM 34, 144–162 (1987)
Jansen, K., Porkolab, L.: On preemptive resource constrained scheduling: Polynomial-time approximation schemes. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 329–349. Springer, Heidelberg (2002)
Kellerer, H.: An approximation algorithm for identical parallel machine scheduling with resource dependent processing times. OR Letters 36, 157–159 (2008)
Kenyon, C., Rémila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research 25, 645–656 (2000)
Langston, M.A.: Processor scheduling with improved heuristic algorithms. PhD thesis, Texas A&M University (1981)
Lodi, A., Martello, S., Monaci, M.: Two-dimensional packing problems: A survey. European Journal of Operational Research 141, 241–252 (2002)
Sahni, S.: Algorithms for scheduling independent tasks. Journal of the ACM 23, 116–127 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niemeier, M., Wiese, A. (2013). Scheduling with an Orthogonal Resource Constraint. In: Erlebach, T., Persiano, G. (eds) Approximation and Online Algorithms. WAOA 2012. Lecture Notes in Computer Science, vol 7846. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38016-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-38016-7_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38015-0
Online ISBN: 978-3-642-38016-7
eBook Packages: Computer ScienceComputer Science (R0)