Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Analysis of Reordering Algorithms to Reduce the Computational Cost of the Jacobi-Preconditioned CG Solver Using High-Precision Arithmetic Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

A Hybrid CPU-GPU Scatter Search for Large-Sized Generalized Assignment Problems

verfasst von : Danilo S. Souza, Haroldo G. Santos, Igor M. Coelho, Janniele A. S. Araujo

Erschienen in: Computational Science and Its Applications – ICCSA 2017

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In the Generalized Assignment Problem, tasks must be allocated to machines with limited resources, in order to minimize processing costs. This problem has several industrial applications and often appears as substructure of other combinatorial optimization problems. By harnessing the massive computational power of Graphics Processing Units in a Scatter Search metaheuristic framework, we propose a method that efficiently generates a solution pool using a Tabu list criteria and an Ejection Chain mechanism. Common characteristics are extracted from the pool and solutions are combined by exploring a restricted search space, as a Binary Programming model. Classic instances vary from 100–1600 jobs and 5–80 agents, but due to the big amount of optimal and near-optimal solutions found by our method, we propose novel large-sized instances up to 9000 jobs and 600 agents. Results indicate that the method is competitive with state-of-the-art algorithms in literature.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Solving Sparse Differential Riccati Equations on Hybrid CPU-GPU Platforms
Nächstes Kapitel Vector Field Second Order Derivative Approximation and Geometrical Characteristics
Fußnoten
1
 
Literatur
1.
Avella, P., Boccia, M., Vasilyev, I.: A computational study of exact knapsack separation for the generalized assignment problem. Comput. Optim. Appl. 45(3), 543–555 (2010). Springer, HeidelbergMathSciNetCrossRefMATH
2.
Cattrysse, D.G., Van Wassenhove, L.N.: A survey of algorithms for the generalized assignment problem. Eur. J. Oper. Res. 60(3), 260–272 (1992). Elsevier, AmsterdamCrossRefMATH
3.
Chu, P.C., Beasley, J.E.: A genetic algorithm for the generalised assignment problem. Comput. Oper. Res. 24(1), 17–23 (1997). Elsevier, AmsterdamMathSciNetCrossRefMATH
4.
Czapiński, M., Barnes, S.: Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform. J. Parallel Distrib. Comput. 71(6), 802–811 (2011). Elsevier, AmsterdamCrossRef
5.
Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71–90 (2005). Springer, HeidelbergMathSciNetCrossRefMATH
6.
Diaz, J.A., Fernández, E.: A Tabu search heuristic for the generalized assignment problem. Eur. J. Oper. Res. 132(1), 22–38 (2001). Elsevier, AmsterdamMathSciNetCrossRefMATH
7.
Feltl, H., Raidl, G.R.: An improved hybrid genetic algorithm for the generalized assignment problem. In: Proceedings of the 2004 ACM Symposium on Applied Computing, pp. 990–995. ACM, New York (2004)
8.
Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977). Wiley Online Library, New JerseyCrossRef
9.
Glover, F.: Tabu search-part I. ORSA J. Comput. 1(3), 190–206 (1989). INFORMS, CatonsvilleCrossRefMATH
10.
Glover, F.: Tabu search-part II. ORSA J. Comput. 2(1), 4–32 (1990). INFORMS, CatonsvilleCrossRefMATH
11.
Glover, F., Laguna, M.: Tabu Search. Springer, New York (2013)MATH
12.
Glover, F., Rego, C.: Ejection chain and filter-and-fan methods in combinatorial optimization. 4OR: Q. J. Oper. Res. 4(4), 263–296 (2006). Springer, HeidelbergMathSciNetCrossRefMATH
13.
Higgins, A.J.: A dynamic Tabu search for large-scale generalised assignment problems. Comput. Oper. Res. 28(10), 1039–1048 (2001). Elsevier, AmsterdamMathSciNetCrossRefMATH
14.
Kirk, D.B., Wen-Mei, W.H.: Programming Massively Parallel Processors: A Hands-on Approach, vol. 2, pp. 10–14. Morgan Kaufmann, San Francisco (2012)
15.
Laguna, M., Kelly, J.P., Gonzlez-Velarde, J., Glover, F.: Tabu search for the multilevel generalized assignment problem. Eur. J. Oper. Res. 82(1), 176–189 (1995). Elsevier, AmsterdamCrossRefMATH
16.
Martí, R., Duarte, A., Laguna, M.: Advanced scatter search for the max-cut problem. INFORMS J. Comput. 21(1), 26–38 (2009). INFORMS, CatonsvilleMathSciNetCrossRefMATH
17.
Martí, R., Laguna, M., Glover, F.: Principles of scatter search. Eur. J. Oper. Res. 169(2), 359–372 (2006). Elsevier, AmsterdamMathSciNetCrossRefMATH
18.
Nauss, R.M.: Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J. Comput. 15(3), 249–266 (2003). INFORMS, CatonsvilleMathSciNetCrossRefMATH
19.
Öncan, T.: A survey of the generalized assignment problem and its applications. INFOR: Inf. Syst. Oper. Res. 45(3), 123–141 (2007). Canadian Operational Research Society, OttawaMathSciNet
20.
Osman, I.H.: Heuristics for the generalised assignment problem: simulated annealing and Tabu search approaches. Oper.-Res.-Spektrum 17(4), 211–225 (1995). Springer, HeidelbergCrossRefMATH
21.
Pigatti, A., De Aragao, M.P., Uchoa, E.: Stabilized branch-and-cut-and-price for the generalized assignment problem. Electron. Notes Discret. Math. 19, 389–395 (2005). Optimization Online, North-HollandMathSciNetCrossRefMATH
22.
Posta, M., Ferland, J.A., Michelon, P.: An exact method with variable fixing for solving the generalized assignment problem. Comput. Optim. Appl. 52(3), 629–644 (2012). Springer, HeidelbergMathSciNetCrossRefMATH
23.
Resende, M.G., Ribeiro, C.C., Glover, F., Martí, R.: Scatter search and path-relinking: fundamentals, advances, and applications. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of metaheuristics, pp. 87–107. Springer, Heidelberg (2010). doi:10.​1007/​978-1-4419-1665-5_​4 CrossRef
24.
Ross, G.T., Soland, R.M.: A branch and bound algorithm for the generalized assignment problem. Math. Program. 8(1), 91–103 (1975). Springer, HeidelbergMathSciNetCrossRefMATH
25.
26.
Savelsbergh, M.: A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6), 831–841 (1997). INFORMS, CatonsvilleMathSciNetCrossRefMATH
27.
Sulewski, D., Edelkamp, S., Kissmann, P.: Exploiting the computational power of the graphics card: optimal state space planning on the GPU. In: 21st International Conference on Automated Planning and Scheduling - ICAPS, Freiburg (2011)
28.
Wilson, J.M.: A genetic algorithm for the generalised assignment problem. J. Oper. Res. Soc. 48(8), 804–809 (1997). Elsevier, AmsterdamCrossRefMATH
29.
Yagiura, M., Ibaraki, T., Glover, F.: A path relinking approach with ejection chains for the generalized assignment problem. Eur. J. Oper. Res. 169(2), 548–569 (2006)MathSciNetCrossRefMATH
Metadaten
Titel
A Hybrid CPU-GPU Scatter Search for Large-Sized Generalized Assignment Problems
verfasst von
Danilo S. Souza
Haroldo G. Santos
Igor M. Coelho
Janniele A. S. Araujo
Copyright-Jahr
2017
Buch
Computational Science and Its Applications – ICCSA 2017

Print ISBN: 978-3-319-62391-7

Electronic ISBN: 978-3-319-62392-4

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-62392-4_10