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

Гафаров, Е.Р.; Лазарев, А.А.; Werner, F.

Авторы: Гафаров Е.Р., Лазарев А.А., Werner F.
Журнал: 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.
Добавил в систему: Лазарев Александр Алексеевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

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

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