Algorithms for minimizing maximum lateness with unit length tasks and resource constraints (Q1803669)

The paper presents the algorithms for deterministic scheduling \(n\) unit length tasks on identical processors in the presence of additional resource constraints. The objective is to minimize maximum lateness. The paper shows that the problem can be solved 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 resource unit is idle in an optimal schedule). For the more general problem without saturation, two heuristic algorithms, and for the exact solution of the problem a branch and bound algorithm are proposed. The results of computational tests of these algorithms are also included.