Open-shop scheduling oropen-shop scheduling problem (OSSP) is anoptimization problem incomputer science andoperations research. It is a variant ofoptimal job scheduling. In a general job-scheduling problem, we are givenn jobsJ₁, J₂, ..., J_n of varying processing times, which need to be scheduled onm machines with varying processing power, while trying to minimize themakespan - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known asopen-shop scheduling, each job consists of a set ofoperationsO₁, O₂, ..., O_n which need to be processed in anarbitrary order. The problem was first studied byTeofilo F. Gonzalez andSartaj Sahni in 1976.^[1]

In the standardthree-field notation for optimal job-scheduling problems, the open-shop variant is denoted byO in the first field. For example, the problem denoted by "O3|${\displaystyle p_{ij}}$|${\displaystyle C_{max}}$" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.

The input to the open-shop scheduling problem consists of a set ofn jobs, another set ofm workstations, and a two-dimensional table of the amount of time each job should spend at each workstation (possibly zero). Each job may be processed only at one workstation at a time, and each workstation can process only one job at a time. However, unlike thejob-shop problem, the order in which the processing steps happen can vary freely. The goal is to assign a time for each job to be processed by each workstation, so that no two jobs are assigned to the same workstation at the same time, no job is assigned to two workstations at the same time, and every job is assigned to each workstation for the desired amount of time. The usual measure of quality of a solution is itsmakespan, the amount of time from the start of the schedule (the first assignment of a job to a workstation) to its end (the finishing time of the last job at the last workstation).

The open-shop scheduling problem can be solved inpolynomial time for instances that have only two workstations or only two jobs. It may also be solved in polynomial time when all nonzero processing times are equal: in this case the problem becomes equivalent toedge coloring abipartite graph that has the jobs and workstations as its vertices, and that has an edge for every job-workstation pair that has a nonzero processing time. The color of an edge in the coloring corresponds to the segment of time at which a job-workstation pair is scheduled to be processed. Because theline graphs ofbipartite graphs areperfect graphs, bipartite graphs may be edge-colored in polynomial time.

For three or more workstations, or three or more jobs, with varying processing times, open-shop scheduling isNP-hard.^[2]

• Job-shop scheduling is a similar problem but with a yet additional constraint – the operations must be done in a specific order.
• Flow-shop scheduling is a job-shop scheduling but with an additionalflow constraint – each operation must be done on a specific machine.