A Lagrangean relaxation scheme for a scheduling problem

The scheduling problem discussed in this paper has a strong resemblance to the generalized assignment problem. It arises when several operations are to be scheduled on a number of machines and the objective is to uniformly maximize the slack time on all the machines. The authors show that it is possible to solve this scheduling problem with little computational effort by using a Lagrangean relaxation scheme. The Lagrangean subproblems, which are of knapsack type with parametric right hand sides, are easily solved using dynamic programming. Although standard dual subgradient optimization techniques are used, the numerical results presented are so remarkably good that they are worth noting.