Single machine scheduling problems with financial resource constraints: some complexity results and properties (Q554491)

In this paper single-machine scheduling problems with a non-renewable resource are studied. Given is a set of jobs \(j=1,\ldots,n\) with processing times \(p_j\) which have to be processed on a single machine. Furthermore, a non-renewable resource is given, which becomes available at specified points in time and is consumed by the jobs. The goal is to find a feasible schedule respecting the resource constraints and minimizing a given objective function. It is shown that the problem is strongly NP-hard for the makespan objective, minimizing the total tardiness (even if all due dates are the same) and that it is NP-hard for the total completion time. Afterwards, structural properties for special cases of the tardiness problem are studied. Finally, the so-called budget problem minimizing the makespan is considered.