Open shops with jobs overlap – revisited

In this communication we consider a two machine open shop in which a job requires processing on both machines. However, in contrast to the classical open shop, the two operations of any given job may overlap in time. The objective function under consideration is the minimization of the total completion time. This model has been considered before by Wagneur and Sriskandarajah and they presented a proof showing that minimizing the total completion time in a two machine open shop with jobs overlap is strongly NP-hard. Their proof is based on a reduction of the numerical matching with target sums (NMTS) problem; however, their proof is unfortunately not correct. In this communication we provide a counterexample that shows that their reduction does not hold. Our counterexample implies that the complexity status of the two machine open shop with job overlap remains open.