The open shop scheduling problem (OSSP) is a scheduling

Scheduling (production processes)

Scheduling is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to minimize the production time and costs, by telling a production facility when to make, with which staff, and on...

 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

Job-shop problem

The job-shop problem is a problem in discrete or combinatorial optimization, and is a generalization of the famous travelling salesman 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

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

. However, when all tasks have the same length, the problem may be solved in polynomial time as an instance of the edge coloring

Edge coloring

In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...

 problem for bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

s.