Skip to Main content Skip to Navigation
Reports

Semi-matching algorithms for scheduling parallel tasks under resource constraints

Anne Benoit 1, 2 Johannes Langguth 2 Bora Uçar 1, 2, *
* Corresponding author
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We study the problem of minimum makespan scheduling when tasks are restricted to subsets of the processors (resource constraints), and require either one or multiple distinct processors to be executed (parallel tasks). This problem is related to the minimum makespan scheduling problem on unrelated machines, as well as to the concurrent job shop problem, and it amounts to finding a semi-matching in bipartite graphs or hypergraphs. While the problem was known to be NP-complete for bipartite graphs, but solvable in polynomial time for unweighted graphs (i.e., unit tasks), we prove that the problem is NP-complete for hypergraphs even in the unweighted case. We design several greedy algorithms of low complexity to solve two versions of the problem, and assess their performance through a set of exhaustive simulations. Even though there is no approximation guarantee on these linear algorithms, they return solutions close to the optimal (or a known lower bound) in average.
Complete list of metadatas

https://hal.inria.fr/hal-00738393
Contributor : Bora Uçar <>
Submitted on : Wednesday, October 24, 2012 - 4:57:03 PM
Last modification on : Wednesday, February 26, 2020 - 11:14:25 AM
Long-term archiving on: : Saturday, December 17, 2016 - 4:34:02 AM

File

rr-8089.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00738393, version 2

Collections

Citation

Anne Benoit, Johannes Langguth, Bora Uçar. Semi-matching algorithms for scheduling parallel tasks under resource constraints. [Research Report] RR-8089, 2012, pp.30. ⟨hal-00738393v2⟩

Share

Metrics

Record views

37

Files downloads

20