Abstract
In the classical problem of scheduling on unrelated parallel machines, a set of jobs has to be assigned to a set of machines. The jobs have a processing time depending on the machine and the goal is to minimize the makespan, that is, the maximum machine load. It is well known that this problem is NP-hard and does not allow polynomial time approximation algorithms with approximation guarantees smaller than 1.5, unless P\(=\)NP. We consider the case that there is only a constant number K of machine types. Two machines have the same type, if all jobs have the same processing time for them. We present an efficient polynomial time approximation scheme (EPTAS) for this problem, that is, for any \(\varepsilon > 0\) an assignment with makespan of length at most \((1+\varepsilon )\) times the optimum can be found in polynomial time in the input length and the exponent is independent of \(1/\varepsilon \). In particular we achieve a running time of , where |I| denotes the input length. Furthermore, we study the case where the minimum machine load has to be maximized and achieve a similar result.
This work was partially supported by the German Research Foundation (DFG) project JA 612/16-1.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing 39(7), 2970–2989 (2010)
Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 543–552. ACM (2009)
Bezáková, I., Dani, V.: Allocating indivisible goods. ACM SIGecom Exchanges 5(3), 11–18 (2005)
Bleuse, R., Kedad-Sidhoum, S., Monna, F., Mounié, G., Trystram, D.: Scheduling independent tasks on multi-cores with gpu accelerators. Concurrency and Computation: Practice and Experience 27(6), 1625–1638 (2015)
Bonifaci, V., Wiese, A.: Scheduling unrelated machines of few different types (2012). arXiv preprint arxiv:1205.0974
Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 107–116. IEEE (2009)
Chen, L., Jansen, K., Zhang, G.: On the optimality of approximation schemes for the classical scheduling problem. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 657–668. SIAM (2014)
Chen, L., Ye, D., Zhang, G.: An improved lower bound for rank four scheduling. Operations Research Letters 42(5), 348–350 (2014)
Eisenbrand, F., Shmonin, G.: Carathéodory bounds for integer cones. Operations Research Letters 34(5), 564–568 (2006)
Gehrke, J.C., Jansen, K., Kraft, S.E.J., Schikowski, J.: A ptas for scheduling unrelated machines of few different types. In: Freivalds, R., Engels, G., Catania, B. (eds.) SOFSEM 2016. LNCS, vol. 9587, pp. 290–301. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49192-8_24
Goemans, M.X., Rothvoß, T.: Polynomiality for bin packing with a constant number of item types. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 830–839. Society for Industrial and Applied Mathematics (2014)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM (JACM) 34(1), 144–162 (1987)
Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM (JACM) 23(2), 317–327 (1976)
Imreh, C.: Scheduling problems on two sets of identical machines. Computing 70(4), 277–294 (2003)
Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics 24(2), 457–485 (2010)
Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11–15, 2016, Rome, Italy, pp. 72:1–72:13 (2016)
Jansen, K., Maack, M.: An EPTAS for scheduling on unrelated machines of few different types (2017). arXiv preprint arXiv:1701.03263v1
Kannan, R.: Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research 12(3), 415–440 (1987)
Knop, D., Kouteckỳ, M.: Scheduling meets n-fold integer programming (2016). arXiv preprint arxiv:1603.02611
Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming 46(1–3), 259–271 (1990)
Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8(4), 538–548 (1983)
Raravi, G., Nélis, V.: A ptas for assigning sporadic tasks on two-type heterogeneous multiprocessors. In: 2012 IEEE 33rd Real-Time Systems Symposium (RTSS), pp. 117–126. IEEE (2012)
Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridge University Press (2011)
Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing 12(1), 57–74 (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jansen, K., Maack, M. (2017). An EPTAS for Scheduling on Unrelated Machines of Few Different Types. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_42
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)