МИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ
Аннотация
Исследуется задача построения расписания с минимальной суммой взвешенных моментов завершения обслуживания 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.
Просмотров: 443
Послать статью по эл. почте 