Name
Abstract | ||
|---|---|---|
We study the problem of minimum make span 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 make span 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 hyper graphs. The problem is known to be NP-complete for bipartite graphs with general vertex (task) weights, and solvable in polynomial time for unweighted graphs (i.e., unit-weight tasks). We prove that the problem is NP-complete for hyper graphs 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 for these low-complexity algorithms, they return solutions close to the optimal (or a known lower bound) in average. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/IPDPSW.2013.30 | Parallel and Distributed Processing Symposium Workshops & PhD Forum |
Keywords | Field | DocType |
parallel tasks,general vertex,concurrent job shop problem,semi-matching algorithms,resource constraints,bipartite graph,hyper graph,exhaustive simulation,unweighted graph,span scheduling problem,approximation guarantee,span scheduling,unweighted case,bipartite graphs,pattern matching,algorithm design and analysis,np complete problem,job shop scheduling,scheduling,polynomials,greedy algorithm,hypergraphs,silicon,resource allocation,greedy algorithms,polynomial time,computational complexity,graph theory | Graph theory,Mathematical optimization,Job shop scheduling,Computer science,Bipartite graph,Algorithm,Open-shop scheduling,Constraint satisfaction dual problem,Vertex cover,Longest path problem,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-0-7695-4979-8 | 1 | 0.36 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anne Benoit | 1 | 342 | 33.74 |
| Johannes Langguth | 2 | 85 | 12.71 |
| Bora Ucar | 3 | 75 | 7.50 |