Управление принятием заказов на предприятии на основе двойственного подхода теории расписаний

В работе рассматривается «верхний» уровень трёхуровневого планирования расписания работы промышленного предприятия. При таком подходе на вернем уровне выполняется стратегическое планирование (принятие решений о выполнении или отказе от заказов), на среднем уровне выполняется планирование внутри предприятия (распределение работы между подразделениями и составление соответствующего графика), а на нижнем уровне выполняется подробное планирование производственной линии каждого подразделения. Задача стратегического планирования рассматривается в качестве одноприборной задачи теории расписаний, в которой предприятие рассматривается как один прибор, выполняющий заказы без прерываний искусственных простоев, строится расписание работы, оптимизирующее некоторую целевую функцию (прибыль). Задача 1|rj|Fmax является NP-трудной. Для решения данной задачи предложено использовать алгоритм на основе метода ветвей и границ и нижних оценок значения целевой функции, получаемых при помощи решения двойственной задачи. При необходимости работу алгоритма можно прервать в любой момент и использовать текущее решение в качестве приближённого результата. Использованный алгоритм решения двойственной задачи позволяет получить оценку снизу значения целевой функции за число шагов, полиномиально зависящее от количества заказов.