Open-shop scheduling
 | This article provides insufficient context for those unfamiliar with the subject. (March 2011) |
The open-shop scheduling problem (OSSP) is a scheduling problem where, given n jobs and m workstations, each job has to be processed on a workstation at least once. However, some of these processing times may be zero. The order in which this happens is not relevant (in contrast to the job-shop problem, where the order of jobs does matter).
NP-hardness
The OSSP can be solved in polynomial time for two machines. For three or more machines, the problem is known to be NP-hard. However, when all tasks have the same length, the problem may be solved in polynomial time as an instance of the edge coloring problem for bipartite graphs.
References
- Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B. (1997), "Short shop schedules", Operations Research, 45 (2): 288–294, doi:10.1287/opre.45.2.288, JSTOR 171745, MR 1644998.