Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
Hanna Furmańczyk , Marek Kubale
AbstractIn the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.
|Other language title versions|
|Journal series||Bulletin of the Polish Academy of Sciences, Technical Sciences, ISSN 0239-7528|
|Publication size in sheets||0.5|
|Keywords in English||equitable coloring, NP-hardness, polynomial algorithm, scheduling, uniform machine|
|Score|| = 20.0, 20-12-2017, ArticleFromJournal|
= 25.0, 20-12-2017, ArticleFromJournal
|Publication indicators||: 2016 = 1.156 (2) - 2016=1.238 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.