Abstract
Scheduling on Unrelated Machines is a classical optimization problem where n jobs have to be distributed to m machines. Each of the jobs \(j \in \{1, \ldots , n\}\) has on machine \(i \in \{1, \ldots , m\}\) a processing time \(p_{ij} \ge 0\). The goal is to minimize the makespan, i.e. the maximum completion time of the longest-running machine. Unless \(\mathrm {P}= \mathrm {NP}\), this problem does not allow for a polynomial-time approximation algorithm with a ratio better than \(\frac{3}{2}\). A natural scenario is however that many machines are of the same type, like a CPU and GPU cluster: for each of the K machine types, the machines \(i \ne i'\) of the same type k satisfy \(p_{ij} = p_{i'j}\) for all jobs j. For the case where the number K of machine types is constant, this paper presents an approximation scheme, i.e. an algorithm of approximation ratio \(1+\varepsilon \) for \(\varepsilon > 0\), with an improved running time only single exponential in \(\frac{1}{\varepsilon }\).
Research supported by DFG project JA612/14-2, “Entwicklung und Analyse von effizienten polynomiellen Approximationsschemata für Scheduling- und verwandte Optimierungsprobleme”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arad, D., Mordechai, Y., Shachnai, H.: Tighter Bounds for Makespan Minimization on Unrelated Machines (2014). arXiv:1405.2530
Bhaskara, A., Krishnaswamy, R., Talwar, K., Wieder, U.: Minimum makespan scheduling with low rank processing times. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 937–947. SIAM (2013)
Bleuse, R., Kedad-Sidhoum, S., Monna, F., Mounié, G., Trystram, D.: Scheduling independent tasks on multi-cores with GPU accelerators. Concurr. Comput. 27(6), 1625–1638 (2015)
Bonifaci, V., Wiese, A.: Scheduling Unrelated Machines of Few Different Types (2012). arXiv:1205.0974
Chakrabarty, D., Khanna, S., Li, S.: On \((1,\varepsilon )\)-restricted assignment makespan minimization. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1087–1101. SIAM (2015)
Chen, L., Ye, D., Zhang, G.: An improved lower bound for rank four scheduling. Oper. Res. Lett. 42(5), 348–350 (2014)
Fishkin, A.V., Jansen, K., Mastrolilli, M.: Grouping techniques for scheduling problems: simpler and faster. Algorithmica 51(2), 183–199 (2008)
Gairing, M., Monien, B., Woclaw, A.: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theor. Comput. Sci. 380(1–2), 87–99 (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Gehrke, J.C., Jansen, K., Kraft, S.E.J., Schikowski, J.: A PTAS for Scheduling Unrelated Machines of Few Different Types. Technical report, No. 1506, Christian-Albrechts-Universität zu Kiel (2015). ISSN 2192-6247
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer, P.L., Johnson, E.L., Korte, B.H. (eds.) Discrete Optimization II: Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Annals of Discrete Mathematics, vol. 5, pp. 287–326. Elsevier (1979)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34(1), 144–162 (1987)
Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539–551 (1988)
Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317–327 (1976)
Imreh, C.: Scheduling problems on two sets of identical machines. Computing 70(4), 277–294 (2003)
Jansen, K., Porkolab, L.: Improved approximation schemes for scheduling unrelated parallel machines. Math. Oper. Res. 26(2), 324–338 (2001)
Jansen, K., Robenek, C.: Scheduling jobs on identical and uniform processors revisited. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 109–122. Springer, Heidelberg (2012)
Jansen, K., Mastrolilli, M.: Scheduling unrelated parallel machines: linear rogramming strikes back. Christian-Albrechts-Universität zu Kiel (2010). ISSN: 2192-6247, No. 1004
Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990)
Raravi, G., Nélis, V.: A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors. In: Proceedings of the 33rd IEEE Real-Time Systems Symposium, RTSS 2012, pp. 117–126. IEEE Computer Society (2012)
Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33(2), 127–133 (2005)
Shmoys, D.B., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461–474 (1993)
Svensson, O.: Santa claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318–1341 (2012)
Wiese, A., Bonifaci, V., Baruah, S.K.: Partitioned EDF scheduling on a few types of unrelated multiprocessors. Real-Time Syst. 49(2), 219–238 (2013)
Acknowledgements
We would like to thank the anonymous reviewers for their comments, especially for the reference to the algorithm by Raravi and Nélis [20]. The bibliography contains information from the DBLP database (www.dblp.org), which is made available under the ODC Attribution License.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gehrke, J.C., Jansen, K., Kraft, S.E.J., Schikowski, J. (2016). A PTAS for Scheduling Unrelated Machines of Few Different Types. In: Freivalds, R., Engels, G., Catania, B. (eds) SOFSEM 2016: Theory and Practice of Computer Science. SOFSEM 2016. Lecture Notes in Computer Science(), vol 9587. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49192-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-49192-8_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49191-1
Online ISBN: 978-3-662-49192-8
eBook Packages: Computer ScienceComputer Science (R0)