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

Bulletin of the Polish Academy of Sciences. Technical Sciences

M. KubaleDepartment of Algorithms and System Modelling, Gda?sk University of Technology, Narutowicza 11/12, 80-233 Gda?sk, PolandOther articles by this author:De Gruyter OnlineGoogle Scholar¹  H. Furma?czykCorresponding authorInstitute of Informatics, University of Gda?sk, Wita Stwosza 57, 80-309 Gda?sk, PolandEmailOther articles by this author:De Gruyter OnlineGoogle Scholar² 

[1] Department of Algorithms and System Modelling, Gda?sk University of Technology, Narutowicza 11/12, 80-233 Gda?sk, Poland;Institute of Informatics, University of Gda?sk, Wita Stwosza 57, 80-309 Gda?sk, Poland

关键词: Keywords: equitable coloring;    NP-hardness;    polynomial algorithm;    scheduling;    uniform machine;   

DOI  :  10.1515/bpasts-2017-0004

学科分类：工程和技术（综合）

来源: Polska Akademia Nauk * Centrum Upowszechniania Nauki / Polish Academy of Sciences, Center for the Advancement of Science

【 摘 要 】

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.

【 授权许可】

Unknown