25466

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

Электронная публикация: 

Да

ISBN/ISSN: 

ISSN 0165-4896

Наименование источника: 

  • Mathematical Social Sciences

Обозначение и номер тома: 

65, No.3

Город: 

  • Amsterdam

Издательство: 

  • Elsevier

Год издания: 

2013

Страницы: 

232 http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a
Аннотация
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.

Библиографическая ссылка: 

Гафаров Е.Р., Лазарев А.А., Werner F. 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. 65, No.3 . С. 232 http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a.