A note on proving the strong NP-hardness of some scheduling problems with start time dependent job processing times |
| |
Authors: | Radosław Rudek |
| |
Institution: | 1.Wroc?aw University of Economics,Wroc?aw,Poland |
| |
Abstract: | In this paper, we show that the strong NP-hardness proofs of some scheduling problems with start time dependent job processing times presented in Gawiejnowicz (Eur J Oper Res 180:472–478, 2007) and Zhao and Tang (Optim Lett 5:183–190, 2011) are incorrect. Namely, the applied transformations from 4-Product problem to the considered scheduling problems are polynomial not pseudopolynomial. Thus, the related problems are NP-hard, but their complete computational status is still an open issue: ordinary or strongly NP-hard? |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|