A note on proving the strong NP-hardness of a scheduling problem with position dependent job processing times |
| |
Authors: | Radosław Rudek |
| |
Affiliation: | 1. Wroc?aw University of Economics, Komandorska 118/120, 53-345, Wroc?aw, Poland
|
| |
Abstract: | In this paper, we show that the strong NP-hardness proof of the single machine makespan minimization problem with ready times and job processing times described by a non-increasing power function dependent on a job position in a sequence presented in Bachman and Janiak (J Oper Res Soc 55:257–264, 2004) is incorrect. Namely, the applied transformation from 3- Partition problem to the considered scheduling problem is polynomial not pseudopolynomial. Thus, the related problem is NP-hard, but it is not proved to be strongly NP-hard. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|