Knapsack-Based Approaches to the Makespan Problem on Multiple Processors

Publisher Website
Google Scholar
Abstract
In this paper we study the problem of scheduling n independent jobs available at time zero on m ≥ 2 parallel and identical processors with the objective of minimizing the makespanJWe propose two approaches, both are Knapsack-based. The first is analytical and depends on reducing the set of m occupancy constraints to a single Diophantine equation. We capitalize on the very special structure of the ILP to effect the reduction with small multipliers. The second approach is an iterative heuristic procedure that is based on the observation that a two-machine makespan problem is trivially reduced to a Knapsack problem. Computational experience indicates the superiority of this approach over other existing approaches. Realistic problems of up to 100 jobs on 10 machines are solved in a few seconds on the IBM 370/165.