|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
When the difference in machine loads leads to efficient scheduling in open shopsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Kononov A., Sevastianov S., Tchernykh I.
- Журнал: Annals of Operations Research
- Том: 92
- Год издания: 1999
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 211
- Последняя страница: 239
- DOI: 10.1023/A:1018986731638
- Аннотация: We consider the open shop problem with n jobs, m machines, and the minimum makespancriterion. Let l_i stand for the load of the i-th machine, l_max be the maximum machine load, and p_max be the maximum operation length. Suppose that the machines are numbered in nonincreasing order of their loads and that p_max = 1, while other processing times are numbers in the interval [0, 1]. Then, given an instance of the open shop problem, we define its vector of differences VOD=(D(1),…,D(m)), where D(i) = l_max – l_i. An instance is called normal if its optimal schedule has length l_max. A vector D \in Rm is called normalizing if every instance with VOD = D is normal. A vector D \in Rm is called efficiently normalizing if it is normalizing and there is a polynomial-time algorithm which for any instance with VOD = D constructs its optimal schedule. In this paper, a few nontrivial classes of efficiently normalizing vectors are found in Rm. It is also shown that the vector (0, 0, 2) is the unique minimal normalizing vector in R3, and that there are at least two minimal normalizing vectors in R4.
- Добавил в систему: Кононов Александр Вениаминович