Файл: Голенко Д.И. Статистические модели в управлении производством.pdf

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

Наиболее часто при математическом моделировании применяется критерий К \ . Его применение многими авто­ рами объясняется тем, что он косвенно снижает издерж­ ки производства. Однако это мнение не всегда достаточ­ но обосновано, поскольку не учитывает реальные условия производства.

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

Переходя к описанию методов решения поставленных выше задач, следует заметить, что детерминистические методы исследования моделей календарного планирова­ ния исторически предшествовали статистическим мето­ дам и внесли в последние ряд полезных эвристических приемов. В то же время практическое использование ме­ тодологии оптимального календарного планирования, по мнению большинства исследователей, связано с разработ­ кой статистических методов. Работы по созданию при­ ближенных вычислительных методов с помощью рандо­ мизированных правил предпочтения, процедуры МонтеКарло, «обучающихся» схем и их сочетаний являются в настоящее время весьма перспективными.

§ 2. 3. Детерминистические и статистические методы исследования моделей календарного планирования

Модели календарного планирования представляют собой особый класс моделей со сложными алгебраичес­ кими структурами и дискретным характером оптимизи­ руемых функций. В последнее время под давлением на­ сущных вопросов практики методы исследования моде­ лей календарного планирования интенсивно разрабаты-

ваются в рамках развивающейся в последнее время тео­ рии расписаний.

Несколько условно детерминистические методы мож­ но разделить на две большие группы:

—точные методы, которые приводят к нахождению оптимального расписания за конечное число шагов;

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

К точным методам относятся: полный перебор вариан­ тов, методы математического программирования (линей­ ного, нелинейного и динамического), последовательный анализ вариантов, метод «ветвей и границ», комбинации метода «ветвей и границ» с последовательным анализом вариантов.

Остановимся на некоторых из перечисленных мето­ дов. Полный перебор означает, что мы последовательно просматриваем все возможные варианты (планы), под­ считываем для каждого из них значение целевой функции и выбираем тот, для которого эта функция имеет наи­ меньшее значение.

Неэффективность такого подхода следует из того, что в задаче очередности (упрощенной задаче календарного планирования) количество действительных планов для п деталей составляет га! и даже для сравнительно неболь­ ших га эта величина превосходит возможности ЭВМ.

Использование методов математического программи­ рования для решения задач календарного планирования широко обсуждалось в литературе [2.1, 2.5]. Трудности, возникающие на этом пути, связаны с необходимостью решения задачи целочисленного программирования и на­ личием большого количества ограничений и переменных. Те простые примеры иллюстративного характера, кото­ рые удавалось решить методами линейного целочислен­ ного программирования, могли быть решены методом пе­ ребора с меньшим объемом вычислительных работ. Не­ которые исследователи считают, что такое положение не случайно, так как «насильственное» включение ярко вы­ раженных комбинаторных задач в схемы линейного про­ граммирования может привести только к усложнению решения задачи.

Методы динамического программирования в приме-

'правила отбора вариантов, лежащие в основе этих алго­ ритмов, с «идеальными» правилами отбора, вытекаю- ш.ими из точной .постановки задачи. Для задач календар­ ного планирования правила отбора вариантов реализу­ ются посредством правил предпочтения (приоритетов), отражающих логику и соображения, накопленные в ре­ зультате личного опыта. Правила предпочтения исполь­ зуются в процессе моделирования расписания при разре­ шении конфликтных ситуаций. Разрешить конфликтную ситуацию — значит поставить на обработку одну из де­ талей на данный станок. Реализация каждого из правил предпочтения состоит из двух этапов:

— вычисления функции предпочтения, которая каж­ дой операции из множества М операций, готовых к об­ работке на некотором освободившемся станке, ставит в соответствие определенное число;

•—выбора из множества М операции, для которой это число наименьшее (наибольшее).

Наиболее представительными и общими правилами являются:

правило SIO (Shortest imminent operation) [2, 2.], со­ гласно которому отдается предпочтение той детали из множества готовых к обработке на освободившемся стан­ ке, у которой операционное время обработки на этом станке наименьшее;

правило LRT (Longest remaining time) [2.3, 2.4], тре­ бующее выбора детали, у которой сумма времени выпол­ нения оставшихся операций наибольшая.

Приведем несколько эвристических методов, разрабо­ танных для решения задачи очередности, критерием ка­ чества которой является минимальное время завершения всех работ. В этих методиках приоритеты выступают как

В случае конфликтной ситуации каждое из конкурирую­ щих изделий располагается на первом месте, после чего определяется суммарное время простаивания станков для каждого из вариантов (время простоя оценивается до полного завершения всех работ).

В качестве изделия, подлежащего обработке, в пер­ вую очередь выбирается то, которому отвечает наимень-

тетав (восьмерки) и т. д., пока получится результирую­ щая очередность для всего ряда изделий.

При каждом сравнении, как нетрудно проследить, имеются две последовательности комбинаций, которые идентичны, за исключением последней пары, находя­ щейся в двух возможных вариантах. Поэтому для выб­ ранного критерия (например, полного времени заверше­ ния обработки) при каждом сравнении требуется не­ большое количество дополнительных вычислений, если мы в состоянии хранить всю промежуточную информацию в памяти ЭВМ; при этом, когда число изделий удваи­ вается, время вычислений на ЭВМ увеличивается приб­ лизительно в три раза. Если промежуточная информа­ ция на ЭВМ не сохраняется, то необходимое для вычис­ лений время при удваивании количества деталей воз­ растает приблизительно в 4 раза. Естественно, что при решении задачи данным методом рассматриваются не все возможные очередности, а только такое подмноже­ ство их, в котором усматривается «хороший» порядок; чем больше это подмножество, тем вероятнее получить хорошую конечную 'Очередность. Однако при этом сле­ дует учитывать, что время вычислений на ЭВМ соот­ ветственно увеличивается.

Метод сдваивания. Этот метод, являющийся вариан­ том предыдущего метода, использует перебор меньшего числа комбинаций. Это связано с тем, что пара, квартет и т. д. рассматриваются как фиксированные. Если, на­ пример, фиксируются пары (а, Ь) и (с, d), то при обра­ зовании квартетов можно сравнивать только очередности (а, Ъ, с, d) и (с, d, а, Ъ) и из них выбирается та, которая соответствует лучшему значению оптимизируемой функции. Конечно, в этом случае мы получим худшее приближение к оптимуму, чем в методе сращивания. Однако этот недостаток, вызванный перебором меньше­ го числа комбинаций, компенсируется уменьшением объема вычислений. При применении метода сдваивания время вычислений увеличивается примерно в два раза, когда число изделий удваивается. Иногда метод сдваи­ вания может давать даже лучшие результаты, нежели метод сращивания, так как комбинации, которые испы­ тывает первый метод, могут не совпадать с теми, кото­ рые испытывает другой метод. Например, метод сращи­ вания из двух пар (а, Ъ) и (с, d) отбирает (а, с), (а, с,

d) и (а, с, d, b) и не образует квартета (а, Ь, с, d), кото­ рый может быть выбран методом сдваивания. В среднем метод сращивания дает лучшие результаты, чем метод сдваивания, но требует большого объема вычислений.

Метод обмена I. Построенную очередность располо­ жения изделий (каким-либо из описанных выше мето­ дов) можно улучшить обменом смежных деталей. Пос­ ледний имеет место лишь в том случае, когда значение критериальной функции улучшается. Обмен продолжа­ ется до тех пор, пока не будет установлена очередность, у которой обмен может только ухудшить чКритериальную функцию.

Метод обмена II [2. 5]. Как и предыдущие, этот ме­ тод основан на сортировке числовой информации. Бу­ дучи опробован на задачах больших «площадей» он дал хорошие результаты и поэтому представляет интерес.

мененный к какой-либо перестановке Р, осуществляет транспозицию элементов pi и pj. Транспозиция элементов плана, произведенная оператором pif и последующее вы­ числение критериальной функции называется шагом по­

к перестановке с наименьшим значением целевой функ­ ции на множестве перестановок {Р1 *}.

Перестановка Р\1=Р2\ принимается за исходную для второй итерадии; в случае получения нескольких перес­