Open shop scheduling

The open shop scheduling problem (OSSP) is a scheduling problem where, given n jobs and m workstations, each job has to visit a workstation at least once. 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, MR1644998 .