The 2-valued case of makespan minimization with assignment constraints

We consider the following special case of minimizing makespan. A set of jobs J and a set of machines M   are given. Each job j∈Jj∈J can be scheduled on a machine from a subset MjMj of M. The processing time of j   is the same on all machines in MjMj. The jobs are of two sizes, namely b (big) and s (small). We present a polynomial-time algorithm that approximates the value of the optimal makespan within a factor of 1.883 and some further improvements when every job can be scheduled on at most two machines.

► We examine a natural special case of minimizing makespan with assignment constraints, where each job is either “big” or “small”. ► Improved approximation algorithms are obtained for this 2-valued case. ► Improved results are also obtained for the 2-valued case of the related graph balancing problem.