Algorithms for hierarchical and semi-partitioned parallel scheduling

Autor: Gianlorenzo D'Angelo, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela
Přispěvatelé: Istituto di Analisi dei Sistemi ed Informatica 'Antonio Ruberti' [Roma] (IASI), Consiglio Nazionale delle Ricerche (CNR), Gran Sasso Science Institute (GSSI), Istituto Nazionale di Fisica Nucleare (INFN), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Bonifaci, V., D'Angelo, G., Marchetti-Spaccamela, A., Snir, M., National Research Council of Italy | Consiglio Nazionale delle Ricerche (CNR), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Rate-monotonic scheduling
Open-shop scheduling
Computer science
Makespan minimization
0211 other engineering and technologies
Parallel computing
02 engineering and technology
01 natural sciences
Multiprocessor scheduling
Scheduling (computing)
Processor affinities
Fixed-priority pre-emptive scheduling
Lottery scheduling
clustered scheduling
laminar family
makespan minimization
processor affinities
unrelated machines
wrap-around rule
Information Systems
Computer Networks and Communications
Hardware and Architecture
Computer Science::Operating Systems
ComputingMilieux_MISCELLANEOUS
021103 operations research
Applied Mathematics
Approximation algorithm
Round-robin scheduling
Unrelated machine
Deadline-monotonic scheduling
Unrelated machines
Computational Theory and Mathematics
010201 computation theory & mathematics
Two-level scheduling
Processor affinitie
Algorithm
Earliest deadline first scheduling
General Computer Science
I/O scheduling
Least slack time scheduling
Processor scheduling
Dynamic priority scheduling
0102 computer and information sciences
Gang scheduling
Fair-share scheduling
Theoretical Computer Science
Nurse scheduling problem
Genetic algorithm scheduling
[INFO]Computer Science [cs]
Clustered scheduling
Laminar family
Wrap-around rule
Job shop scheduling
Flow shop scheduling
Stride scheduling
Zdroj: Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2021, 120, pp.116-136. ⟨10.1016/j.jcss.2021.03.006⟩
Journal of Computer and System Sciences, 2021, 120, pp.116-136. ⟨10.1016/j.jcss.2021.03.006⟩
Proceedings-IEEE International Parallel and Distributed Processing Symposium (2017): 738–747. doi:10.1109/IPDPS.2017.22
info:cnr-pdr/source/autori:Bonifaci, Vincenzo; D'Angelo, Gianlorenzo; Marchetti-Spaccamela, Alberto/titolo:Algorithms for Hierarchical and Semi-Partitioned Parallel Scheduling/doi:10.1109%2FIPDPS.2017.22/rivista:Proceedings-IEEE International Parallel and Distributed Processing Symposium/anno:2017/pagina_da:738/pagina_a:747/intervallo_pagine:738–747/volume
IPDPS
ISSN: 0022-0000
1090-2724
Popis: We propose a model for scheduling jobs in a parallel machine setting that takes into account the cost of migrations by assuming that the processing time of a job may depend on the specific set of machines among which the job is migrated. For the makespan minimization objective, the model generalizes classical scheduling problems such as unrelated parallel machine scheduling, as well as novel ones such as semi-partitioned and clustered scheduling. In the case of a hierarchical family of machines, we derive a compact integer linear programming (ILP) formulation for the job assignment subproblem, and show how to turn arbitrary ILP solutions into valid schedules. We also derive a polynomial-time 2-approximation algorithm for the problem. Extensions that incorporate memory capacity constraints are also discussed.
Databáze: OpenAIRE
Externí odkaz: