Abstract:
Scheduling to Minimize the Makespan on Identical Parallel Machines: An LP-Based Algorithm
Polyhedral Combinatorics approaches have turned out to be successful
computational tools in many hard Combinatorial Optimization problems. We
present an approximation algorithm based on linear programming formulations
with binary decision variables which are a kind of assignment variables for
the classical deterministic scheduling problem of minimizing the makespan on
identical machines. The problem is known to be NP-hard in the strong
sense. The structure of the corresponding polytope is analyzed, and the
strong cutting planes are identified. Computational results show that, in
all tested cases, the problem can be solved exactly.