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

Информация о цитировании статьи получена из Scopus, Web of Science
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 14 сентября 2013 г.
• Авторы:
• Журнал: Mathematical Social Science
• Том: 65
• Номер: 3
• Год издания: 2013
• Издательство: Elsevier BV
• Местоположение издательства: Netherlands
• Первая страница: 232
• Последняя страница: 237
• DOI: 10.1016/j.mathsocsci.2012.11.004
• Аннотация: 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.
• Добавил в систему: Лазарев Александр Алексеевич

#### Прикрепленные файлы

Имя Описание Имя файла Размер Добавлен
1. 1-s2.0-S0165489612001102-main.pdf 1-s2.0-S0165489612001102-main.pdf 146,0 КБ 18 сентября 2013 [Lazarev]