Graph balancing: a special case of scheduling unrelated parallel machines (Q2441586)

This paper considers a special case of the scheduling problem on unrelated parallel machines. We are given a set of jobs and a group M of machines; each job \(j_i\) has processing time \(p_i\) and it can be processed by at most 2 machines from M. The goal is to schedule the jobs so as to minimize the makespan or completion time of the last job. This problem is equivalent to the graph balancing problem, where we are given a multigraph with weights on the edges and the goal is to orient the edgers so that the maximum total weight of the edges directed towards a vertex is minimum. The main result of the paper is a 1.75 approximation algorithm for the above problem. This algorithm is based on the classic 2-approximation algorithm of \textit{J. K. Lenstra} et al. [Math. Program. 46, No. 3 (A), 259--271 (1990; Zbl 0715.90063)] for scheduling jobs on unrelated parallel machines. However, the authors need to introduce a different integer programming formulation for the problem with a stronger linear programming relaxation than the one used by Lenstra et al. [loc. cit.]. They propose two different linear programs that have integrality gap 1.75. The new programming formulations make use of the fact that no vertex can have more than one large weight edge pointing towards it. A somewhat elaborated rounding procedure allows a solution for any of the above linear programs to be converted into an integral solution of value at most 1.75 times the optimum. The authors also show that for the versions of the problem when machines have different speeds, or when a job can be processed by up to three machines, their linear programming formulations and the configuration linear program of \textit{N. Bansal} and \textit{M. Sviridenko} [``The Santa Claus problem'', in: Proceedings of the thirty-eighth annual ACM symposium on theory of computing (STOC 2006). New York, NY: ACM Press. 31--40 (2006; \url{doi:10.1145/1132516.1132522})] have integrality gap of value 2.