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

В данной работе приводится анализ оценок снизу и сверху оптимального решения для задачи оптимизации прерываемых расписаний на одной машине с чётными временами выполнения, произвольного времени появления и приоритетности, целевой функцией, минимизирующей суммарное взвешенное время выполнения всех работ. Актуальность обосновывается тем, что прерываемые расписания на одной машине представляют практически важный класс трудно решаемых задач (NP - трудных), для решения которых используются переборные алгоритмы ветвей и границ (АВИГ). В зависимости от точности и трудоемкости применяемых границ (оценок) возможно существенно увеличить точность и размеры решаемых задач АВИГ. Целью является обобщение оценок снизу и сверху для прерываемых расписаний на одной машине с постоянными длительностями выполнения работ на случай произвольных четных длительностей выполнения работ.

Publisher
Общество с ограниченной ответственностью "Агентство международных исследований"
Language
Russian
Pages
19-21
Status
Published
Year
2023
Organizations
  • 1 Российский университет дружбы народов
Keywords
теория расписаний; оценки снизу и сверху; оптимальное решение; задача о назначении; прерываемые расписания на одной машине; четные длительности выполнения работ
Share

Other records

Kovrizhkina E.L., Gorislova A.Y., Kat'kova A.K.
ПРОБЛЕМЫ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ИННОВАЦИОННЫХ ИССЛЕДОВАНИЙ И ПУТИ ИХ РЕШЕНИЯ. Общество с ограниченной ответственностью "Агентство международных исследований". 2023. P. 28-30