UNIT-TIME SCHEDULING PROBLEMS WITH TIME-DEPENDENT RESOURCES

We investigate the computational complexity of scheduling problems, wh ere the operations consume certain amounts of renewable resources whic h are available in time-dependent quantities. In particular, we consid er unit-time open shop problems and unit-time scheduling problems with identical parallel processors. For the case where the number of machi nes, the number of resources and the demand for every resource are all bounded by a constant, we derive polynomial time results for several objective functions. Furthermore, we establish a borderline between ha rd and easy variants of such problems by proving NP-hardness of most r emaining cases.