Open shop problems with unit time operations |
| |
Authors: | Peter Brucker Bernd Jurisch Marion Jurisch |
| |
Institution: | (1) Fachbereich Mathematik/Informatik, Universität Osnabrück, Albrechtstraße 28, 4500 Osnabrück, Germany |
| |
Abstract: | We show that them-machine open shop problem in which all operations have unit processing times can be polynomially transformed to a special preemptive scheduling problem onm identical parallel machines. Many results published recently as well as some new results are derived by using this transformation. The new results include solutions of open problems mentioned in a recent paper by Kubiak et al. p]A similar relationship is derived between no-wait open shop problems with unit time operations andm-machine problems with jobs having unit processing times.This work was supported by Deutsche Forschungsgemeinschaft (Project JoPTAG). |
| |
Keywords: | Open shop scheduling parallel machine scheduling polynomial algorithm NP-hard problem |
本文献已被 SpringerLink 等数据库收录! |