|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Integrality Property in Preemptive Parallel Machine Schedulingтезисы доклада
- Авторы: Baptiste P., Carlier J., Kononov A.V., Queyranne M., Sevastjanov S.V., Sviridenko M.I.
- Сборник: Computer Science - Theory and Applications. CSR 2009
- Серия: Lecture Notes in Computer Science
- Том: 5675
- Тезисы
- Год издания: 2009
- Издательство: Springer Berlin
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 38
- Последняя страница: 46
- DOI: 10.1007/978-3-642-03351-3_6
- Аннотация: We consider parallel machine scheduling problems with identical machines and preemption allowed. It is shown that every such problem with chain precedence constraints and release dates and an integer-concave objective function satisfies the following integrality property: for any problem instance with integral data there exists an optimal schedule where all interruptions occur at integral dates. As a straightforward consequence of this result, for a wide class of scheduling problems with unit processing times a so-called preemption redundancy property is valid. This means that every such preemptive scheduling problem is equivalent to its non-preemptive counterpart from the viewpoint of both its optimum value and the problem complexity. The equivalence provides new and simpler proofs for some known complexity results and closes a few open questions.
- Добавил в систему: Кононов Александр Вениаминович