A note on the paper ‘Single machine scheduling problems with financial resource constraints: Some complexity results and properties’ by E.R. Gafarov et al.

Mathematical Social Sciences. 2013. Vol. 65. No. 3. P. 232.

Alexander A. Lazarev, Gafarov E., Wernerb F.

In the article E.R. Gafarov, A.A. Lazarev, F. Werner, Single machine scheduling problems with financial resource constraints: Some complexity results and properties, Mathematical Social Sciences, 62 (2011), 7–13, the following mistake is found in Section 3.2, where the authors consider the problem denoted as 1|NR, dj = d, gj = g|  Tj and claim that it is NP-hard. In the proof, a reduction from the Partition Problem was used which is not polynomial, since M exponentially depends on n. However, it is not difficult to correct this proof. The main idea of using Mn−i+1 was that the processing time of a job belongs to a pair with the smallest number being greater than the total sum of the processing times of all jobs from the pairs with larger numbers, e.g., for the job V2: p2 ≫ n i=2(p2i−1 + p2i). Instead of using p2i = Mn−i+1, where M = (n  bj)n (see the definition of the instance given in (3) on page 11), we can consider, e.g., p2i = 2n • 2n−i+1M, where M = (n  bj). In this case, the reduction will be polynomial in the input length, if we suppose that all digits used are coded in a binary system with approximately 2n zero–one symbols per digit.

Keywords: дискретная оптимизация, discrete optimization