Two-Machine Open Shops with Renewable Resources

Bernd Jurisch and Wieslaw Kubiak
Additional contact information
Bernd Jurisch: Memorial University of Newfoundland, St. John's, Newfoundland, Canada
Wieslaw Kubiak: Memorial University of Newfoundland, St. John's, Newfoundland, Canada

Operations Research, 1997, vol. 45, issue 4, 544-552

Abstract: In open shops with renewable resources, an operation may require additional resources, besides a machine, for its execution. All resources required by the operation are allocated to it all the time during its execution. At no time may total resource requirements exceed resource capacities. We consider the problem of minimizing makespan in a two-machine open shop with a single renewable resource. We show that optimal nonpreemptive schedules are not longer than optimal preemptive schedules, which we then translate into a polynomial time algorithm for the makespan minimization problem. This is an important generalization of a well-known result obtained by Gonzalez and Sahni (Gonzalez, G., S. Sahni. 1976. Open shop scheduling to minimize finish time. J. ACM 23 665–679.) for the two-machine open shop without additional resources. We also study the problem of minimizing makespan in a two-machine open shop with at least two different resources. In this case, optimal nonpreemptive schedules may be longer than optimal preemptive ones. We show that this makes the makespan minimization problem NP-hard.

Keywords: production/scheduling; open shop; resource constraints; analysis of algorithms; computational complexity (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.4.544 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:4:p:544-552

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().