Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine

In this paper we extend the classical single-machine scheduling problem with the maximal lateness criterion to the case where the job processing times are controllable by allocating common limited resources. For the single resource problem we determine the optimal job sequence and resource allocation in O(n³) time, while for the two-resource problem the optimal solution is obtained in O(n³log(1/ϵ)) time, where ϵ is a given accuracy. For both cases, we assume a convex resource consumption function.