Open Shop

The jobs of a set N = 1, 2,…, n are processed in a system consisting of M sequential machines. A job i ∈ N enters a system at time d_i > 0. For each job of set N, a route (a processing order) is not given in advance and may be different for different jobs. The processing times t_iL ≥ 0 of each job i ∈N on each machine L, 1 ≤ L ≥M, are given. The notation t_iL = 0 implies that job i is not processed on machine L. At any time, each job is processed on at most one machine, and each machine processes no more than one job. Such processing systems are called open shops.