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.