Open-shop scheduling

Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan - the total length of the schedule (that is, when all the jobs have finished processing). 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. The problem was first studied by Teofilo F. Gonzalez and Sartaj Sahni in 1976.

In the standard three-field notation for optimal job-scheduling problems, the open-shop variant is denoted by O in the first field. For example, the problem denoted by "O3|

p

i

j

{\displaystyle p_{ij}}

|

C

max

{\displaystyle C_{\max }}

" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.

Definition

The input to the open-shop scheduling problem consists of a set of n jobs, another set of m 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 the job-shop problem, the order in which the processing steps happen can vary freely.