Open shops with jobs overlap––revisited |
| |
| Institution: | 1. Department of Computer Science, New Jersey Institute of Technology, Newark, NJ, USA;2. Department of Information, Operations and Management Science, Stern School of Business, New York University, 44 West Fourth Street, New York, NY 10012-1126, USA;3. School of Management, University of Texas at Dallas, Dallas, TX, USA;1. Department of Computer Science, Wuhan University of Technology, Wuhan 430063, PR China;2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System, Wuhan University of Science and Technology, PR China;3. College of Computer and Information Engineering, Nanyang Institute of Technology, Nanyang 473000, PR China;1. University of Santiago de Compostela, EPS, Hydraulic Eng., Campus Univ. s/n, 27002 Lugo, Spain;2. University of Plymouth, School of Marine Science and Engineering, Drake Circus, Plymouth PL4 8AA, UK;1. University of Santiago de Compostela, Spain;2. Plymouth University, UK;1. 211106, College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China;2. 200233, National Key Laboratory of Science and Technology on Avionics Integration, China Aeronautical Radio Electronics Research Institute, Shanghai, China |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
