Estimating the makespan of the two-valued restricted assignment problem (Q1751100)

The paper deals with a scheduling problem of unrelated machines, where each considered job from a finite set of jobs must be assigned to one of the machines which are able to process the job. Each couple job-machine is connected to an individual processing time of the job on the machine. The sum of all processing times of the jobs assigned to a machine is denoted as the makespan of the machine. Objective of the restricted assignment problem is to minimize the maximal makespan across the set of machines. The authors focused their effort on a theoretical research concerning a special case of the above problem, where only two different values of processing time are taken into account. The goal of the research consists in improvement of the integrality gap estimation, what is ratio of optimal objective function values of the original integer programming problem and the linear programming relaxation of the problem. The authors were successful in improving the integrality gap from the previously known value of 11/6 to the value of 5/3. This excellent result was achieved by utilizing and improving the Svensson's bound and search technique. The presented research is properly described by a sequence of theorems and lemmas and carefully performed proofs. Generally, the paper constitutes a valuable piece of work for community of professionals in the theory of algorithms.