Skip to main content

2019 | OriginalPaper | Buchkapitel

Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing

verfasst von : Klaus Jansen, Malin Rau

Erschienen in: Euro-Par 2019: Parallel Processing

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the Multiple Cluster Scheduling problem and the Multiple Strip Packing problem. For both problems, there is no algorithm with approximation ratio better than 2 unless \(\mathrm {P}= \mathrm {NP}\). In this paper, we present an algorithm with approximation ratio 2 and running time \(\mathcal {O}(n)\) for both problems for \(N >2\) (and running time \(\mathcal {O}(n\log (n)^2)\) for \(N=2\)). While a 2 approximation was known before, the running time of the algorithm is at least \(\varOmega (n^{256})\) in the worst case. Therefore, an \(\mathcal {O}(n)\) algorithm is surprising and the best possible.
While the above result is strong from a theoretical point of view, it might not be very practical due to a large hidden constant caused by calling an AEPTAS with a constant \(\varepsilon \ge 1/8\) as subroutine. Nevertheless, we point out that the general approach of finding first a schedule on one cluster and then distributing it onto the other clusters might come in handy in practical approaches. We demonstrate this by presenting a practical algorithm with running time \(\mathcal {O}(n\log (n))\), without hidden constants, that is an approximation algorithm with ratio 9/4 if the number N of clusters is dividable by 3 and bounded by \(9/4 + \frac{3}{4N}\) otherwise.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
2.
Zurück zum Zitat Bougeret, M., Dutot, P., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math. Alg. Appl. 3(4), 553–586 (2011)MathSciNetCrossRef Bougeret, M., Dutot, P., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math. Alg. Appl. 3(4), 553–586 (2011)MathSciNetCrossRef
3.
Zurück zum Zitat Bougeret, M., Dutot, P., Trystram, D., Jansen, K., Robenek, C.: Improved approximation algorithms for scheduling parallel jobs on identical clusters. Theor. Comput. Sci. 600, 70–85 (2015)MathSciNetCrossRef Bougeret, M., Dutot, P., Trystram, D., Jansen, K., Robenek, C.: Improved approximation algorithms for scheduling parallel jobs on identical clusters. Theor. Comput. Sci. 600, 70–85 (2015)MathSciNetCrossRef
4.
Zurück zum Zitat Dutot, P., Jansen, K., Robenek, C., Trystram, D.: A (2 + \(\epsilon \))-approximation for scheduling parallel jobs in platforms. In: Proceedings of the 19th Euro-Par, Aachen, Germany, August 26–30, 2013, pp. 78–89 (2013) Dutot, P., Jansen, K., Robenek, C., Trystram, D.: A (2 + \(\epsilon \))-approximation for scheduling parallel jobs in platforms. In: Proceedings of the 19th Euro-Par, Aachen, Germany, August 26–30, 2013, pp. 78–89 (2013)
5.
Zurück zum Zitat Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187–200 (1975)MathSciNetCrossRef Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187–200 (1975)MathSciNetCrossRef
6.
Zurück zum Zitat Jansen, K.: A \((3/2+ \varepsilon )\) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: Proceedings of the 24th ACM SPAA, Pittsburgh, PA, USA, June 25–27, pp. 224–235 (2012) Jansen, K.: A \((3/2+ \varepsilon )\) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: Proceedings of the 24th ACM SPAA, Pittsburgh, PA, USA, June 25–27, pp. 224–235 (2012)
7.
Zurück zum Zitat Jansen, K., Rau, M.: Linear time algorithms for multiple cluster scheduling and multiple strip packing. CoRR, abs/1902.03428 (2019) Jansen, K., Rau, M.: Linear time algorithms for multiple cluster scheduling and multiple strip packing. CoRR, abs/1902.03428 (2019)
8.
Zurück zum Zitat Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discrete Optim. 6(3), 310–323 (2009)MathSciNetCrossRef Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discrete Optim. 6(3), 310–323 (2009)MathSciNetCrossRef
9.
Zurück zum Zitat Jansen, K., Trystram, D.: Scheduling parallel jobs on heterogeneous platforms. Electron. Notes Discrete Math. 55, 9–12 (2016)CrossRef Jansen, K., Trystram, D.: Scheduling parallel jobs on heterogeneous platforms. Electron. Notes Discrete Math. 55, 9–12 (2016)CrossRef
10.
Zurück zum Zitat Marty, M.R., Hill, M.D.: Virtual hierarchies to support server consolidation. In: Proceedings of the 34th ISCA, June 9–13, San Diego, California, USA, pp. 46–56 (2007) Marty, M.R., Hill, M.D.: Virtual hierarchies to support server consolidation. In: Proceedings of the 34th ISCA, June 9–13, San Diego, California, USA, pp. 46–56 (2007)
11.
Zurück zum Zitat Schwiegelshohn, U., Tchernykh, A., Yahyapour, R.: Online scheduling in grids. In: Proceedings of the 22nd IEEE IPDPS, Miami, Florida USA, April 14–18, 2008, pp. 1–10 (2008) Schwiegelshohn, U., Tchernykh, A., Yahyapour, R.: Online scheduling in grids. In: Proceedings of the 22nd IEEE IPDPS, Miami, Florida USA, April 14–18, 2008, pp. 1–10 (2008)
12.
Zurück zum Zitat Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401–409 (1997)MathSciNetCrossRef Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401–409 (1997)MathSciNetCrossRef
13.
Zurück zum Zitat Tchernykh, A., Ramírez, J.M., Avetisyan, A., Kuzjurin, N., Grushin, D., Zhuk, S.: Two level job-scheduling strategies for a computational grid. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Waśniewski, J. (eds.) PPAM 2005. LNCS, vol. 3911, pp. 774–781. Springer, Heidelberg (2006). https://doi.org/10.1007/11752578_93CrossRef Tchernykh, A., Ramírez, J.M., Avetisyan, A., Kuzjurin, N., Grushin, D., Zhuk, S.: Two level job-scheduling strategies for a computational grid. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Waśniewski, J. (eds.) PPAM 2005. LNCS, vol. 3911, pp. 774–781. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​11752578_​93CrossRef
14.
Zurück zum Zitat Tchernykh, A., Schwiegelshohn, U., Yahyapour, R., Kuzjurin, N.: On-line hierarchical job scheduling on grids with admissible allocation. J. Scheduling 13(5), 545–552 (2010)MathSciNetCrossRef Tchernykh, A., Schwiegelshohn, U., Yahyapour, R., Kuzjurin, N.: On-line hierarchical job scheduling on grids with admissible allocation. J. Scheduling 13(5), 545–552 (2010)MathSciNetCrossRef
15.
Zurück zum Zitat Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms scheduling parallelizable tasks. In: Proceedings of the 4th (SPAA), pp. 323–332 (1992) Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms scheduling parallelizable tasks. In: Proceedings of the 4th (SPAA), pp. 323–332 (1992)
16.
17.
Zurück zum Zitat Zhuk, S.: Approximate algorithms to pack rectangles into several strips. Discrete Math. Appl. DMA 16(1), 73–85 (2006)CrossRef Zhuk, S.: Approximate algorithms to pack rectangles into several strips. Discrete Math. Appl. DMA 16(1), 73–85 (2006)CrossRef
Metadaten
Titel
Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing
verfasst von
Klaus Jansen
Malin Rau
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-29400-7_8