2-MACHINE OPEN SHOPS WITH RENEWABLE RESOURCES

In open shops with renewable resources, an operation may require addit ional resources, besides a machine, for its execution. All resources r equired by the operation are allocated to it all the time during its e xecution. At no time may total resource requirements exceed resource c apacities. We consider the problem of minimizing makespan in a two-mac hine open shop with a single renewable resource. We show that optimal nonpreemptive schedules are not longer than optimal preemptive schedul es, which we then translate into a polynomial time algorithm for the m akespan minimization problem. This is an important generalization of a well-known result obtained by Gonzalez and Sahni (1976) for the two-m achine open shop without additional resources. We also study the probl em of minimizing makespan in a two-machine open shop with at least two different resources. In this case, optimal nonpreemptive schedules ma y be longer than optimal preemptive ones. We show that this makes the makespan minimization problem NP-hard.