Preview

Информатика

Расширенный поиск

МИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ

Полный текст:

Аннотация

Исследуется задача построения расписания с минимальной суммой взвешенных моментов завершения обслуживания n требований одним прибором при условии, что известны нижние и верхние границы возможных значений длительностей операций по обслуживанию требований. Доказывается необходимое и достаточное условие, при выполнении которого требование Ju доминирует требование Jv (иными словами, для каждого множества возможных длительностей операций существует оптимальная перестановка n требований, в которой Ju предшествует Jv). Приводится критерий существования единственной перестановки n требований, которая является оптимальной при любых возможных длительностях операций. Доказывается необходимое и достаточное условие, при котором любая перестановка n требований является единственной оптимальной перестановкой при некотором множестве возможных длительностей операций. Полученные условия проверяются за полиномиальное от n время.

Об авторах

Н. Г. Егорова
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

1. Sequencing and scheduling: Algorithms and complexity / E.L. Lawler [et al.] // Handbooks in Operations Research and Management Science. Logistics of Production and Inventory. – North-Holland, USA, N.-Y., 1993. – P. 445–522.

2. Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск: ОИПИ НАН Беларуси, 2004. – 290 c.

3. Smith, W.E. Various optimizers for single-stage production / W.E. Smith // Naval Research and Logistics Quarterly. – 1956. – Vol. 3, № 1. – Р. 59–66.

4. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. – М.: Наука, 1984. – 336 с.

5. Шафранский, Я.М. Задачи теорий расписаний с неопределенными числовыми параметрами: направления исследований и некоторые результаты / Я.М. Шафранский // Информатика. – 2005. – № 3. – С. 5–15.

6. Танаев, В.С. Теория расписаний. Одностадийные системы / В.С. Танаев, В.С. Гордон, Я.М. Шафранский. – М.: Наука, 1984. – 384 c.

7. Лещенко, Н.М. Оптимальное по быстродействию обслуживание конфликтных требований с нефиксированными длительностями / Н.М. Лещенко, Ю.Н. Сотсков // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 4. – С. 103–110.

8. Егорова, Н.Г. Выбор оптимального порядка обслуживания требований двумя приборами в процессе реализации расписания / Н.Г. Егорова, Н.М. Матвейчук, Ю.Н. Сотсков // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 5. – С. 20–24.

9. Егорова, Н.Г. Планирование рабочего времени с учетом интервальных длительностей операций / Н.Г. Егорова, Н.М. Матвейчук, Ю.Н. Сотсков // Третья научная конференция «Танаевские чтения». – Минск: ОИПИ НАН Беларуси, 2007. – С. 60–64.

10. Модели и комплекс программ для планирования рабочего времени / Ю.Н. Сотсков

11. [и др.] // Информатика. – 2007. – № 4. – С. 5–15.


Для цитирования:


Егорова Н.Г., Сотсков Ю.Н. МИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ. Информатика. 2008;(3(19)):5-16.

Просмотров: 104


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)