МИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ
Исследуется задача построения расписания с минимальной суммой взвешенных моментов завершения обслуживания n требований одним прибором при условии, что известны нижние и верхние границы возможных значений длительностей операций по обслуживанию требований. Доказывается необходимое и достаточное услови...
Saved in:
| Format: | Article |
|---|---|
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2018-11-01
|
| Series: | Informatika |
| Online Access: | https://inf.grid.by/jour/article/view/573 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Исследуется задача построения расписания с минимальной суммой взвешенных моментов завершения обслуживания n требований одним прибором при условии, что известны нижние и верхние границы возможных значений длительностей операций по обслуживанию требований. Доказывается необходимое и достаточное условие, при выполнении которого требование Ju доминирует требование Jv (иными словами, для каждого множества возможных длительностей операций существует оптимальная перестановка n требований, в которой Ju предшествует Jv). Приводится критерий существования единственной перестановки n требований, которая является оптимальной при любых возможных длительностях операций. Доказывается необходимое и достаточное условие, при котором любая перестановка n требований является единственной оптимальной перестановкой при некотором множестве возможных длительностей операций. Полученные условия проверяются за полиномиальное от n время. |
|---|---|
| ISSN: | 1816-0301 |