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

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