Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines

摘要

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines.We present two new algorithms that are a significant improvement over the known algorithms.The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj = G = bisubquartic | C_(max).The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1,G = bisubquartic|ΣCj,where m ∈ {2,3,4}.The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width,and on the properties of ideal machine,an abstract machine that we introduce in this paper.