Jump to content

Open-shop scheduling

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Deb (talk | contribs) at 11:53, 30 March 2011 (tag). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Open Shop Scheduling Problem or OSSP is a scheduling problem where, given jobs and 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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Open-shop_scheduling&oldid=421470467"