In the pursuit of finding subclasses of the makespan minimization problem on unrelated parallel machines that have approximation algorithms with approximation ratio better than 2, the graph balancing problem has been of current interest. In the graph balancing problem each job can be non-preemptively scheduled on one of at most two machines with the same processing time on either machine. Recently, Ebenlendr, Krčál, and Sgall (Algorithmica 2014, 68, 62–80.) presented a -approximation algorithm for the graph balancing problem. Let . In this paper we consider the graph balancing problem with two weights, where a job either takes r time units or s time units. We present a -approximation algorithm for this problem. This is an improvement over the previously best-known approximation algorithm for the problem with approximation ratio 1.652 and it matches the best known inapproximability bound for it.
Let there be m parallel machines and n jobs, where a job j can be scheduled on machine i to take pi, j ∈ Z+ time units. The makespan Cmax is the completion time of a machine that finishes last. The goal is to produce a schedule with all n jobs that has minimum makespan. This is the makespan problem on unrelated parallel machines, denoted as R||Cmax. Assume p,q ∈ Z+ are constants, let A(p,q) = {a ∈ Z+ | p ≤ a ≤ q}. We explore a general NP-hard subclass of R||Cmax when processing times are between p and q inclusive or pi,j=∞ abbreviated as R|pi,j ∈ A(p,q)∪{∞}|Cmax, where pi,j = ∞ means job j cannot be scheduled to machine i. We give a (q/p)-approximation algorithm for R|pi,j ∈ A(p,q)∪{∞}|Cmax. As a consequence, we obtain a 2-approximation algorithm for the NP-hard subclass R||Cmax with job lengths 1, 2, or pi,j=∞. In addition, we prove R||Cmax with job lengths 1, 2, and 3 is NP-hard, and present a 3/2-approximation algorithm for this subclass of R||Cmax.