Jump to content

Open-shop scheduling

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Styhn (talk | contribs) at 11:52, 30 March 2011 (←Created page with 'The '''Open Shop Scheduling Problem''' or '''OSSP''' is a scheduling problem where, given <math>n</math> jobs and <math>m</math> workstations, each job has to visit...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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=421470362"