nach oben

Journal of Combinatorial Optimization

Erschienen in:

18.11.2017

Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays

verfasst von: Sven Mallach

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set.

Vorheriger Artikel Optimization problems with color-induced budget constraints

Nächster Artikel Planning personnel retraining: column generation heuristics

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 "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

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

http://www.gurobi.com/.

Ait El Cadi A, Ben Atitallah R, Hanafi S, Mladenović N, Artiba A (2014) New MIP model for multiprocessor scheduling problem with communication delays. Optim Lett. https://doi.org/10.1007/s11590-014-0802-2 MATH

Baxter J, Patel J (1989) The LAST algorithm—a heuristic-based static task allocation algorithm. In: Proceedings of international conference on parallel processing, Pennsylvania State University, University Park, PA, USA, pp 217–222

Chrétienne P, Picouleau C (1995) Scheduling with communication delays: a survey. In: Chrétienne P, Coffman EG, Lenstra JK, Liu Z (eds) Scheduling theory and its applications, chap 4. Wiley, Hoboken

Davidović T, Crainic TG (2006) Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems. Comput OR 33:2155–2177. https://doi.org/10.1016/j.cor.2005.01.005 MathSciNetCrossRefMATH

Davidović T, Liberti L, Maculan N, Mladenović N (2004) Mathematical programming-based approach to scheduling of communicating tasks. TR G-2004-99, Montréal, Canada

Davidović T, Liberti L, Maculan N, Mladenović N (2007) Towards the optimal solution of the multiprocessor scheduling problem with communication delays. In: Baptiste P, Kendall G, Munier-Kordon A, Sourd F (eds) Proceedings of 3rd multidisciplinary international conference on scheduling: theory and application, École Polytechnique, Paris, France, pp 128–135

Davidović T, Maculan N, Mladenović N (2003) Mathematical programming formulation for the multiprocessor scheduling problem with communication delays. In: Proc. Simpozijum o operacionim istraživanjima (symposium on operational research), pp 331–334

Djordjević GL, Tošić MB (1996) A heuristic for scheduling task graphs with communication delays onto multiprocessors. Parallel Comput 22(9):1197–1214. https://doi.org/10.1016/S0167-8191(96)00041-5 MathSciNetCrossRefMATH

El-Rewini H, Lewis TG (1990) Scheduling parallel program tasks onto arbitrary target machines. J Parallel Distrib Comput 9(2):138–153. https://doi.org/10.1016/0743-7315(90)90042-N CrossRefMATH

Fortet R (1960) Applications de l’algèbre de boole en recherche opérationnelle. Revue de la Société Française de Recherche Opérationnelle 4:17–26MATH

Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discrete Appl Math 5(1):89–98. https://doi.org/10.1016/0166-218X(83)90018-5 MathSciNetCrossRefMATH

Fujita S, Yamashita M (2000) Approximation algorithms for multiprocessor scheduling problem. IEICE Trans Inform Syst 83(3):503–509

Fujita S, Masukawa M, Tagashira S (2003) A fast branch-and-bound scheme for the multiprocessor scheduling problem with communication time. In: Proceedings of international conference parallel processing, IEEE, pp 104–111. https://doi.org/10.1109/ICPPW.2003.1240360

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New YorkMATH

Giroudeau R, König JC (2007) Scheduling with communication delays. In: Levner E (ed) Multiprocessor scheduling, theory and applications, chap 4. InTech, London

Graham RL, Lawler EL, Lenstra JK, Kan AHGR (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. In: Hammer PL, Johnson EL, Korte BH (eds) Discrete optimization II, proceedings of Advanced Research Institute on discrete optimization and systems applications of the systems science panel of NATO and the discrete optimization symposium, annals of discrete mathematics, vol 5. Elsevier, pp 287–326

Hwang JJ, Chow YC, Anger FD, Lee CY (1989) Scheduling precedence graphs in systems with interprocessor communication times. SIAM J Comput 18(2):244–257. https://doi.org/10.1137/0218016 MathSciNetCrossRefMATH

Jabrayilov A, Mallach S, Mutzel P, Rüegg U, von Hanxleden R (2016) Compact layered drawings of general directed graphs. In: Hu Y, Nöllenburg M (eds) 24th international symposium on graph drawing network visualization, revised selected papers, Springer, Lecture Notes in Computer Science, vol 9801, pp 209–221. https://doi.org/10.1007/978-3-319-50106-2_17

Jin S, Schiavone G, Turgut D (2008) A performance study of multiprocessor task scheduling algorithms. J Supercomput 43(1):77–97. https://doi.org/10.1007/s11227-007-0139-z CrossRef

Kim D, Yi BG (1994) A two-pass scheduling algorithm for parallel programs. Parallel Comput 20(6):869–885. https://doi.org/10.1016/0167-8191(94)90121-X MathSciNetCrossRefMATH

Kim SJ, Browne JC (1989) A general approach to mapping of parallel computation upon multiprocessor architectures. In: Ris F, Kogge PM (eds) Proceedings of the international conference on parallel processing, Pennsylvania State University Press, vol 3, pp 1–8

Kong X, Sun J, Ye B, Xu W (2007) An efficient quantum-behaved particle swarm optimization for multiprocessor scheduling. In: Shi Y, van Albada GD, Dongarra J, Sloot PMA (eds) Proceedings of the 7th international conference on computational science (ICCS), part I. Springer, Berlin, pp 278–285. https://doi.org/10.1007/978-3-540-72584-8_36

Kruatrachue B, Lewis TG (1987) Duplication scheduling heuristic (DSH), a new precedence task scheduler for parallel processor systems. Technical Report OR 97331, Oregon State University

Kwok YK, Ahmad I (1995) Bubble scheduling: a quasi dynamic algorithm for static allocation of tasks to parallel architectures. In: Proceedings of IEEE symposium on parallel and distributed processing, IEEE Computer Society, Washington, DC, USA, pp 36–43

Kwok YK, Ahmad I (1996) Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans Parallel Distrib Syst 7(5):506–521. https://doi.org/10.1109/71.503776 CrossRef

Kwok YK, Ahmad I (1999) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv 31(4):406–471. https://doi.org/10.1145/344588.344618 CrossRef

Kwok YK, Ahmad I, Gu J (1996) FAST: a low-complexity algorithm for efficient scheduling of DAGs on parallel processors. In: Proceedings of international conference on parallel processing, vol 2, pp 150–157. https://doi.org/10.1109/ICPP.1996.537394

Liberti L (2007) Compact linearization for binary quadratic problems. 4OR 5(3):231–245. https://doi.org/10.1007/s10288-006-0015-3 MathSciNetCrossRefMATH

Mallach S (2016) Compact linearization for binary quadratic problems subject to assignment constraints. CoRR arXiv:1610.05375

McCreary C, Gill H (1989) Automatic determination of grain size for efficient parallel processing. Commun ACM 32(9):1073–1078. https://doi.org/10.1145/66451.66454 CrossRef

Mehdiratta N, Ghose K (1994) A bottom-up approach to task scheduling on distributed memory multiprocessors. In: Proceedings of the international conference on parallel processing, vol 2, pp 151–154. https://doi.org/10.1109/ICPP.1994.14

Möhring RH, Schäffter MW, Schulz AS (1996) Scheduling jobs with communication delays: using infeasible solutions for approximation (extended abstract). In: Diaz J, Serna M (eds) Proceedings of the 4th European symposium on algorithms, Springer, Berlin, LNCS, vol 1136, pp 76–90. https://doi.org/10.1007/3-540-61680-2_48

Rayward-Smith VJ (1987a) The complexity of preemptive scheduling given interprocessor communication delays. Inf Process Lett 25(2):123–125. https://doi.org/10.1016/0020-0190(87)90231-6 MathSciNetCrossRef

Rayward-Smith VJ (1987b) UET scheduling with unit interprocessor communication delays. Discrete Appl Math 18(1):55–71. https://doi.org/10.1016/0166-218X(87)90042-4 MathSciNetCrossRefMATH

Sarkar V (1989) Partitioning and scheduling parallel programs for multiprocessors. MIT Press, CambridgeMATH

Satish N, Nadathur K, Keutzer K (2007) A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In: Proceedings of the conference on design, automation and test in Europe, EDA Consortium, San Jose, CA, USA, pp 57–62

Senar MA, Ripoll A, Cortés A, Luque E (2003) Clustering and reassignment-based mapping strategy for message-passing architectures. J Syst Archit 48(8–10):267–283. https://doi.org/10.1016/S1383-7621(03)00011-0 CrossRef

Shahul AZS, Sinnen O (2010) Scheduling task graphs optimally with A*. J Supercomput 51(3):310–332. https://doi.org/10.1007/s11227-010-0395-1 CrossRef

Sih GC, Lee EA (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans Parallel Distrib Syst 4(2):175–187. https://doi.org/10.1109/71.207593 CrossRef

Veltman B (1993) Multiprocessor scheduling with communication delays. PhD thesis, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Veltman B, Lageweg BJ, Lenstra JK (1990) Multiprocessor scheduling with communication delays. Parallel Comput 16(2):173–182. https://doi.org/10.1016/0167-8191(90)90056-F CrossRefMATH

Venugopalan S, Sinnen O (2012) Optimal linear programming solutions for multiprocessor scheduling with communication delays. In: Xiang Y, Stojmenovic I, Apduhan BO, Wang G, Nakano K, Zomaya A (eds) Proceedings of the 12th international conference on algorithms and architectures for parallel processing, part I. Springer, Berlin, pp 129–138. https://doi.org/10.1007/978-3-642-33078-0_10

Venugopalan S, Sinnen O (2015) ILP formulations for optimal task scheduling with communication delays on parallel systems. IEEE Trans Parallel Distrib Syst 26(1):142–151. https://doi.org/10.1109/TPDS.2014.2308175 CrossRef

Wu MY, Gajski DD (1988) A programming aid for hypercube architectures. J Supercomput 2(3):349–372. https://doi.org/10.1007/BF00129784 CrossRef

Yang T, Gerasoulis A (1991) A fast static scheduling algorithm for DAGs on an unbounded number of processors. In: Proceedings of the ACM/IEEE conference on supercomputing, ACM, New York, NY, USA, Supercomputing ’91, pp 633–642. https://doi.org/10.1145/125826.126138

Yang T, Gerasoulis A (1993) List scheduling with and without communication delays. Parallel Comput 19(12):1321–1344. https://doi.org/10.1016/0167-8191(93)90079-Z CrossRefMATH

Yang T, Gerasoulis A (1994) DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans Parallel Distrib Syst 5(9):951–967. https://doi.org/10.1109/71.308533 CrossRef

Titel: Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays
verfasst von: Sven Mallach
Publikationsdatum: 18.11.2017
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0199-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2018

Base polyhedra and the linking property

On the m-clique free interval subgraphs polytope: polyhedral analysis and applications

ILP formulation of the degree-constrained minimum spanning hierarchy problem

The weakly connected independent set polytope in corona and join of graphs

An algorithm for finding a representation of a subtree distance

A compact representation for minimizers of k-submodular functions

Premium Partner