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 is an element of J can be scheduled on a machine from a subset M-j of M. The processing time of j is the same on all machines in M-j. 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. (C) 2012 Elsevier B.V. All rights reserved.
makespan minimization scheduling approximation algorithms graph balancing