Open-shop scheduling
From Wikipedia, the free encyclopedia
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.[1]
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||" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.