V-shop scheduling

This paper deals with V-shop scheduling where the route by which a job passes through the machines is: M₁ → M₂ → ? → M_m?1 → M_m → M_m?1 → ? → M₂ → M₁. Flowshop scheduling is a special case of V-shop. The two-machine, minimum schedule length V-shop scheduling problem is proved to be binary NP-complete. Efficient solvable algorithms are presented for some simple special cases of NP-complete V-shop problems; specifically n/2/V/C_max with a dominating machine and n/m/V, t_ij = 1/(C_max ∩ ΣC_i). n/m/V/C_max, m?2, with an increasing series of dominating machines is discussed.