Two-machine open shops with renewable resources
成果类型：
Article
署名作者：
Jurisch, B; Kubiak, W
署名单位：
Memorial University Newfoundland
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.4.544
发表日期：
1997
页码：
544-552
关键词：
摘要：
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 (1976) 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.