informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-573Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGМИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИЕгороваН. Г.СотсковЮ. Н.Объединенный институт проблем информатики НАН БеларусиBelarus20080511201803(19)516Copyright © Егорова Н.Г., Сотсков Ю.Н., 20182018Егорова Н.Г., Сотсков Ю.Н.Егорова Н.Г., Сотсков Ю.Н.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/573

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

ReferencesSequencing 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.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.Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск: ОИПИ НАН Беларуси, 2004. – 290 c.Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск: ОИПИ НАН Беларуси, 2004. – 290 c.Smith, W.E. Various optimizers for single-stage production / W.E. Smith // Naval Research and Logistics Quarterly. – 1956. – Vol. 3, № 1. – Р. 59–66.Smith, W.E. Various optimizers for single-stage production / W.E. Smith // Naval Research and Logistics Quarterly. – 1956. – Vol. 3, № 1. – Р. 59–66.Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. – М.: Наука, 1984. – 336 с.Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. – М.: Наука, 1984. – 336 с.Шафранский, Я.М. Задачи теорий расписаний с неопределенными числовыми параметрами: направления исследований и некоторые результаты / Я.М. Шафранский // Информатика. – 2005. – № 3. – С. 5–15.Шафранский, Я.М. Задачи теорий расписаний с неопределенными числовыми параметрами: направления исследований и некоторые результаты / Я.М. Шафранский // Информатика. – 2005. – № 3. – С. 5–15.Танаев, В.С. Теория расписаний. Одностадийные системы / В.С. Танаев, В.С. Гордон, Я.М. Шафранский. – М.: Наука, 1984. – 384 c.Танаев, В.С. Теория расписаний. Одностадийные системы / В.С. Танаев, В.С. Гордон, Я.М. Шафранский. – М.: Наука, 1984. – 384 c.Лещенко, Н.М. Оптимальное по быстродействию обслуживание конфликтных требований с нефиксированными длительностями / Н.М. Лещенко, Ю.Н. Сотсков // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 4. – С. 103–110.Лещенко, Н.М. Оптимальное по быстродействию обслуживание конфликтных требований с нефиксированными длительностями / Н.М. Лещенко, Ю.Н. Сотсков // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 4. – С. 103–110.Егорова, Н.Г. Выбор оптимального порядка обслуживания требований двумя приборами в процессе реализации расписания / Н.Г. Егорова, Н.М. Матвейчук, Ю.Н. Сотсков // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 5. – С. 20–24.Егорова, Н.Г. Выбор оптимального порядка обслуживания требований двумя приборами в процессе реализации расписания / Н.Г. Егорова, Н.М. Матвейчук, Ю.Н. Сотсков // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2006. – № 5. – С. 20–24.Егорова, Н.Г. Планирование рабочего времени с учетом интервальных длительностей операций / Н.Г. Егорова, Н.М. Матвейчук, Ю.Н. Сотсков // Третья научная конференция «Танаевские чтения». – Минск: ОИПИ НАН Беларуси, 2007. – С. 60–64.Егорова, Н.Г. Планирование рабочего времени с учетом интервальных длительностей операций / Н.Г. Егорова, Н.М. Матвейчук, Ю.Н. Сотсков // Третья научная конференция «Танаевские чтения». – Минск: ОИПИ НАН Беларуси, 2007. – С. 60–64.Модели и комплекс программ для планирования рабочего времени / Ю.Н. СотсковМодели и комплекс программ для планирования рабочего времени / Ю.Н. Сотсков[и др.] // Информатика. – 2007. – № 4. – С. 5–15.[и др.] // Информатика. – 2007. – № 4. – С. 5–15.

The authors declare that there are no conflicts of interest present.