Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

Hanna Furmańczyk , Marek Kubale


In 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.
Author Hanna Furmańczyk (FMPI / II)
Hanna Furmańczyk,,
- Institute of Informatics
, Marek Kubale
Marek Kubale,,
Other language title versions
Journal seriesBulletin of the Polish Academy of Sciences, Technical Sciences, ISSN 0239-7528, (A 20 pkt)
Issue year2017
Publication size in sheets0.5
Keywords in Englishequitable coloring, NP-hardness, polynomial algorithm, scheduling, uniform machine
Languageen angielski
LicenseJournal (articles only); published final; Uznanie Autorstwa - Użycie Niekomercyjne - Bez utworów zależnych (CC-BY-NC-ND); with publication
Score (nominal)25
ScoreMinisterial score = 20.0, 20-12-2017, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 20-12-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 1.156 (2) - 2016=1.238 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.