Методы решения задач календарного планирования

Задачи оперативного управления производством часто называют задачами календарного планирования, т.е. планирования во времени. Причем собственно календарными считаются задачи, относящиеся к составлению календарных графиков по дням, сменам, часам работы. Задачи управления на уровне декады, месяца, квартала называют задачами декадного, месячного, квартального планирования. Формирование класса этих задач связано с одной из первых попыток решения экономических проблем методами математического программирования в начале 50-х годов. С тех пор актуальность решения данных задач сильно возросла. Увеличился диапазон подходов к их решению, но одновременно сохраняются трудности их реализации. Для решения задач календарного планирования привлекаются разнообразные методы прикладной математики (линейного, нелинейного, динамического программирования и др.).

С математической точки зрения задача календарного планирования представляет собой сложную комбинаторную задачу, имеющую множество решений, среди которых необходимо найти решение, оптимальное в смысле некоторого критерия. Данная задача может быть решена точно или приближенно, в соответствии с этим и методы ее решения делятся на точные и приближенные.

Точные методы. К точным методам решения задач относятся методы линейного программирования.

Пример
Пример некоторой задачи линейного программирования. Пусть цех выпускает Nнаименований изделий и Xj – количество изделий j-го наименования (j=1,N). Количество станков в цехе M. Обработка одного изделия может происходить последовательно на нескольких станках, при чем tij – время обработки j-го изделия на i-ом станке (i=1,M). Тогда общая трудоемкость изделий

Ограничения, при котором решается задача

Xj>0,

где bi – фонд рабочего времени i-го станка.

Как правило,данные, входящие в модель, не так точны, как это предполагается методом. Это в значительной степени затрудняет практическое использование методов линейного программирования, однако, они имеют целый ряд интересных для практического использования приложений. К таким задачам можно отнести задачу об оптимальном раскрое материала, составление оптимальных смесей и т.д.

К точным методам решения задачи календарного планирования относится также алгоритм целочисленного программирования Гомори, в котором предполагается, что все коэффициенты в выражениях целевой функции и ограничений являются целыми числами. Этот метод имеет определённые возможности учитывать комбинаторный характер плановых решений, неделимость отдельных видов работ и ресурсов и т.д.

Приближенные методы.Применение ЭВМ для решения задач календарного планирования позволили привлечь методы моделирования, в которых используются многие приемы (локальные правила), применяющиеся при ручном способе составления расписаний. Локальное правило календарного планирования это такое правило, которое используется рабочим-станочником при выполнении запланированных работ и требует от него только знания работ, ожидающих своей очереди перед его станком. Известно множество локальных правил, каждое из которых дает расписание, близкое к оптимальному для конкретной модели календарного планирования. Предпочтительность того или иного правила в зависимости от размерности задачи или от последовательности выполнения работ определить трудно. Во всех случаях определяется лишь расписание, близкое к условно оптимальному, т.е. оптимальному в условиях применения определенных локальных правил.

Наиболее широкое распространение за рубежом получила система CAPOSS (capacity planning and operations sequencing system), разработанная специалистами фирмы IBM. В системе реализуются функции долгосрочного и краткосрочного планирования,производится расчет времени изготовления заказов и составляется последовательность операций с использованием локальных правил, в том числе правила априорных приоритетов, в соответствии с которыми каждому заказу или операции присваивается приоритет, определяющий очередность их назначения на выполнение. В любом случае получается такой вариант расписания, близость которого к оптимальному остается не известной. Это связано с отсутствием информации как о характере изменения целевой функции в области допустимых расписаний, так и о границах этой области. Для определения оптимального решения существуют методы поиска, основанные на направленном переборе допустимых вариантов расписаний. Основными недостатками этих методов являются потребность в большом объеме оперативной памяти и продолжительное время решения задачи.

Tags: задача асуп CAPOSS IBM планирование календарь

Social

  • Twitter
  • Facebook