ALGORITHMS FOR MINIMIZING MAXIMUM LATENESS WITH UNIT LENGTH TASKS ANDRESOURCE CONSTRAINTS

The problem we consider is that of scheduling n unit length tasks on i dentical processors in the presence of additional scarce resources. Th e objective is to minimize maximum lateness. It has been known for som e time that the problem is NP-hard even for two processors and one res ource type. In the present paper we show that the problem can be solve d in O(n log n) time, even for an arbitrary number of resources if the instance of the problem has the saturation property (i.e., no resourc e unit is idle in an optimal schedule). For the more general problem w ithout saturation, two heuristic algorithms and a branch and bound app roach are proposed. The results of computational tests of the above me thods are also reported.