Jump to content

Open-shop scheduling

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 05:45, 4 August 2011 (moved Open Shop Scheduling to Open shop scheduling: Wikipedia case conventions for titles, override lowercase redirect to worse target. The move deletes a redirect with no other edit history.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

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