Open shops with jobs overlaprevisited Academic Article uri icon


  • 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 [Eur. J. Oper. Res. 71 (1993) 366] 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. 2004 Elsevier B.V. All rights reserved.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Leung, J., Li, H., Pinedo, M., & Sriskandarajah, C.

citation count

  • 17

complete list of authors

  • Leung, Joseph Y-T||Li, Haibing||Pinedo, Michael||Sriskandarajah, Chelliah

publication date

  • June 2005