Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. The authors present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, the authors develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, the authors employ a Lagrangean dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrealated machine scheduling problem, they describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-of-air missiles in a naval battle-group engagement scenario. The authors present computational results for this problem using suitable realistic data.