Методы решения задач календарного планирования
Задачи оперативного управления производством часто называют задачамикалендарного планирования, т.е. планирования во времени. Причем собственно календарнымисчитаются задачи, относящиеся к составлению календарных графиков по дням,сменам, часам работы. Задачи управления на уровне декады, месяца, кварталаназывают задачами декадного, месячного, квартального планирования. Формированиекласса этих задач связано с одной из первых попыток решения экономическихпроблем методами математического программирования в начале 50-х годов. С техпор актуальность решения данных задач сильно возросла. Увеличился диапазон подходовк их решению, но одновременно сохраняются трудности их реализации. Для решениязадач календарного планирования привлекаются разнообразные методы прикладнойматематики (линейного, нелинейного, динамического программирования и др.).
Сматематической точки зрения задача календарного планирования представляет собойсложную комбинаторную задачу, имеющую множество решений, среди которыхнеобходимо найти решение, оптимальное в смысле некоторого критерия.Даннаязадача может быть решена точно или приближенно, в соответствии с этим и методыее решения делятся на точные и приближенные.
Точные методы. К точным методам решения задач относятся методы линейногопрограммирования.
Ограничения, при которомрешается задача
Xj>0,
где bi – фонд рабочего времени i-гостанка.
Как правило,данные, входящие в модель, не так точны, как это предполагается методом. Это взначительной степени затрудняет практическое использование методов линейногопрограммирования, однако, они имеют целый ряд интересных для практическогоиспользования приложений. К таким задачам можно отнести задачу об оптимальномраскрое материала, составление оптимальных смесей и т.д.
К точнымметодам решения задачи календарного планирования относится также алгоритмцелочисленного программирования Гомори, в котором предполагается, что всекоэффициенты в выражениях целевой функции и ограничений являются целымичислами. Этот метод имеет определённые возможности учитывать комбинаторныйхарактер плановых решений, неделимость отдельных видов работ и ресурсов и т.д.
Приближенныеметоды.Применение ЭВМ для решения задач календарного планирования позволили привлечьметоды моделирования, в которых используются многие приемы (локальные правила),применяющиеся при ручном способе составления расписаний. Локальное правило календарного планирования это такое правило, которое используется рабочим-станочникомпри выполнении запланированных работ и требует от него только знания работ,ожидающих своей очереди перед его станком. Известно множество локальных правил,каждое из которых дает расписание, близкое к оптимальному для конкретной моделикалендарного планирования. Предпочтительность того или иного правила в зависимостиот размерности задачи или от последовательности выполнения работ определитьтрудно. Во всех случаях определяется лишь расписание, близкое к условнооптимальному, т.е. оптимальному в условиях применения определенных локальныхправил.
Наиболее широкоераспространение за рубежом получила система CAPOSS (capacity planning and operations sequencing system), разработанная специалистами фирмы IBM. Всистеме реализуются функции долгосрочного и краткосрочного планирования,производится расчет времени изготовления заказов и составляетсяпоследовательность операций с использованием локальных правил, в том числе правилааприорных приоритетов, в соответствии с которыми каждому заказу илиоперации присваивается приоритет, определяющий очередность их назначения навыполнение. В любом случае получается такой вариант расписания, близость которогок оптимальному остается не известной. Это связано с отсутствием информации како характере изменения целевой функции в области допустимых расписаний, так и ограницах этой области. Для определения оптимального решения существуют методыпоиска, основанные на направленном переборе допустимых вариантоврасписаний. Основными недостатками этих методов являются потребность в большомобъеме оперативной памяти и продолжительное время решения задачи.