In the specific variant known as open-shop scheduling, each job consists of a set of operations O1, O2, ..., On which need to be processed in an arbitrary order.
[1] In the standard three-field notation for optimal job-scheduling problems, the open-shop variant is denoted by O in the first field.
However, unlike the job-shop problem, the order in which the processing steps happen can vary freely.
The open-shop scheduling problem can be solved in polynomial time for instances that have only two workstations or only two jobs.
For three or more workstations, or three or more jobs, with varying processing times, open-shop scheduling is NP-hard.