In the pursuit of finding subclasses of the makespan minimization problem on unrelated\nparallel machines that have approximation algorithms with approximation ratio better than 2, the\ngraph balancing problem has been of current interest. In the graph balancing problem each job can\nbe non-preemptively scheduled on one of at most two machines with the same processing time on\neither machine. Recently, Ebenlendr, KrÃ?â?¡cÃ?¡l, and Sgall (Algorithmica 2014, 68, 62ââ?¬â??80.) presented a\n7/4-approximation algorithm for the graph balancing problem. Let r, s âË?Ë? Z+. In this paper we\nconsider the graph balancing problem with two weights, where a job either takes r time units or\ns time units. We present a 3/2-approximation algorithm for this problem. This is an improvement\nover the previously best-known approximation algorithm for the problem with approximation\nratio 1.652 and it matches the best known inapproximability bound for it.
Loading....