Open shops with jobs overlap-revisited

Joseph Y.T. Leung, Haibing Li, Michael Pinedo, Chelliah Sriskandarajah

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)569-571
Number of pages3
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Jun 1 2005

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Open shops
  • Strongly NP-hard
  • Total completion time


Dive into the research topics of 'Open shops with jobs overlap-revisited'. Together they form a unique fingerprint.

Cite this