MAHTEMATICAL METHODS OF SOLUTION OF WORKSHOP SCHEDULING PROBLEM

Abstract

The authors present the analysis of modern systems, mathematical models and methods for planning and manage- ment of the described production. Optimization criteria for workshop scheduling are considered, computational com- plexity of scheduling optimization problems is estimated. A model of multi-criteria optimization of discrete production manufacturing scheduling problem is suggested. The model takes into account all technological restrictions.

Full Text

Базовым понятием для задач составления расписа- ний (Machine Scheduling, MS) является операция. Для задания операции, как правило, необходимы два агента: объект операции, или ее материальный носитель, – то, над чем производят операцию, и субъект операции, или исполнитель, – тот, кто (или что) выполняет операцию. В качестве матери- ального носителя операции может выступать от- дельная деталь или сборочная единица создаваемого изделия. Носителем операции может быть человек, обслуживаемый другими людьми (приборами). Субъ- Некоторые подмножества операций организаци- онно (и технологически) объединяются в работы. Например, если завод выпускает сложные изделия (машины, самолеты и т. п.), то все операции, отно- сящиеся к одному изделию, составляют одну работу. На некоторые работы может быть наложен жесткий директивный срок их окончания, которому соответ- ствует английский термин Deadline (смертельная ли- ния), и/или желаемый срок окончания Due Date, от- клонение от которого наказывается штрафом; при этом Deadline и Due Date одной и той же работы мо- ектами операций являются станки (инструменты, лю- ди), необходимые для выполнения этих операций. гут не совпадать. Моменты {C j } окончания работ В моделях MS они обычно называются машинами. {J j } (C – от Completion Time) играют существенную 29 Математика, механика, информатика роль в оценке качества обозначения построенного расписания: как правило, целевая функция задачи Succ (i ) = { j | (i, j ) ∈ E}, где Рred (i ) ( Succ (i ) ) – является функцией f (C1 , ..., Cn ) от моментов завер- множество работ, находящихся в графе непосредст- венно перед (за) работой i . шения работ J1 , ..., J n . В классических моделях MS присутствуют только три основных понятия: операции, работы и машины. При этом соблюдаются строгие правила: Отношение предшествования i → j заменено отношением «начало–начало»: Si + lij ≤ S j , может быть (1) – каждая операция относится ровно к одной ра- боте; где lij – любое целое число, от знака которого зави- – каждая операция выполняется ровно на одной сит смысл соотношения (1). Если lij > 0 , то тогда ра- машине (возможно, выбираемой из множества аль- бота j не может начаться, пока не пройдет lij време- тернативных машин); – никакие две операции одной работы не могут выполняться одновременно; ни после начала работы i, т. е. работа j не может на- чаться до момента начала работы i , и в этом случае – никакие две операции одной машины не могут lij – минимальная разница между моментами начала выполняться одновременно. Задача составления плана проекта при ограничен- двух работ. Если lij < 0 , то работа i должна начаться ных ресурсах (Resource-Constrained Project Scheduling не позже чем через −lij времени после начала работы Problem, RCPSP) [1] может быть сформулирована j. Таким образом, lij называется положительной (от- следующим образом. Дано n работ i = 1, ..., n и r рицательной) временной задержкой, если (1) выпол- возобновляемых ресурсов k = 1, ..., r . Постоянное няется и lij > 0 ( lij < 0 ). количество Rk ресурса k доступно в любое время. Соотношения (1) являются обобщенными. Напри- Работа i должна быть произведена за время pi . В мер, если lij = pi , то это не что иное, как i → j . Если течение этого времени на данной работе задействова- же между окончанием работы i и началом работы j но постоянное количество rik ресурса k. Кроме того, должно пройти не меньше dij времени, то это можно для работ определены отношения предшествования записать как Si + pi + dij ≤ S j . Если выполняются ус- i → j, где i → j означает, что работа j не может начаться, пока не закончится работа i . Задача опре- ловия Si + pi + dij ≤ S j и S j − uij − pi ≤ Si , где деления моментов начал Si ставится для работ 0 ≤ dij ≤ uij , то время между окончанием работы i и i = 1, ..., n таким образом, что: началом работы j должно быть не менее dij , но не – в каждый момент времени t общая потребность более uij . Последнее включает частный случай в некотором ресурсе меньше либо равна наличию данного ресурса; 0 ≤ dij = uij , где работа j должна начаться точно че- – соблюдены определенные выше отношения рез lij временных единиц после окончания работы i . предшествования работ; Для работы i ранние сроки начала ri (r – Release) – величина Cmax = max Ci принимает свое мини- и поздние сроки окончания di (d – Deadlines) могут мальное значение, где ния работы i . i =1...n Ci = Si + pi – время заверше- быть смоделированы соотношениями (1): S0 + ri ≤ Si , Si − (di − pi ) ≤ S0 . Возможно прерывание работ. Временной интервал [ri , di ] называется времен- Иногда полезно добавить начальную псевдоработу ным окном работы i . Работа i должна начаться и 0 и конечную псевдоработу n + 1 , каждую с нулевой закончиться между границами данного временного длительностью. Для всех работ i = 1, ..., n, должны окна. выполняться условия 0 → i и i → n + 1 . Псевдорабо- Таким образом, необходимо определить возобнов- ты не требуют ресурсов. S0 – момент начала проекта, ляемый ресурс k объемом rjkm для работы j дли- а момент Sn +1 может быть интерпретирован как мо- тельностью p jm . мент окончания проекта. Общая постановка задачи составления цехово- Структура RCPSP должна быть представлена с помощью графа, где вершинами являются работы го расписания. Пусть имеются работы j = 1, ..., n и G = (V , E ) . Здесь V – множество всех работ, m машин M1 , ..., M m . Работа j состоит из n j опера- E = {(i, j ) | i, j ∈V ; i → j} отражает отношения пред- ций O1 j , ..., On j , j. Две операции одной работы не шествования. Каждой работе i ставятся в соответст- могут производиться одновременно. Операция Oij вие два множества: Рred (i ) = { j | ( j, i ) ∈ E} и имеет длительность pij , если производится машиной 30 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева μ ∈{M1 , ..., M m } . Отношения предшествования суще- ствуют между любыми операциями. Такая общая за- дача составления цехового расписания может быть менение статистических методов, методов имитации на ЭВМ. Эти методы носят эвристический характер и зачастую взаимно переплетаются друг с другом. интерпретирована как RCPSP с r = m + n возобнов- Основная особенность статистических методов за- ключается в возможности учета времени, используе- ляемыми ресурсами, где Rk = 1 для k = 1, ..., m + n , и с n числом операций Oij , равным ∑n j . Кроме того, опе- j =1 мого для решения задачи. Роль имитационных моделей состоит в наиболее полном использовании возможностей современных ЭВМ. Первоначально эти модели имели вид простей- рация где Oij использует объем ресурса k , равный rijk , ших в логическом отношении способов построения календарных графиков. Современные имитационные модели представляют собой сложные комплексы ⎧0, если r ⎨ μij = M k или k = m + j, взаимосвязанных алгоритмов, включающие в себя ijk ⎩1 в противном случае. построение моделей и их реализацию на базе различ- Ресурсы k = 1, ..., m соответствуют оборудованию, ных методов [10]. в то время как ресурсы m + j ( j = 1, ..., n ) необходи- Для решения задачи составления расписаний ши- мы, чтобы моделировать ситуации, когда разные опе- рации одной работы j не могут производиться одно- временно. Для многих частных случаев общей задачи состав- ления цехового расписания в настоящее время суще- ствуют либо точные детерминированные полиноми- альные алгоритмы их решения, либо приблизитель- ные эвристические алгоритмы, находящие прибли- женно оптимальное решение за полиномиальное вре- мя. Как было сказано выше, к уже существующим ограничениям для работы i можно добавлять ранние роко применяются методы динамического програм- мирования и метод ветвей и границ [2], который с большим успехом используется при решении одной из разновидностей задачи одного станка [11] – задачи о переналадках [12]. В экономической литературе описана задача об определении оптимального размера партии запуска- выпуска деталей [13–16]. Размер партии деталей как основной плановый норматив в серийном производ- стве оказывает существенное влияние на экономиче- ские результаты деятельности предприятия, цеха, участка. сроки начала ri и поздние сроки окончания di . Среди математически моделируемых задач кален- Рассмотрим основные этапы применения матема- тических методов к задаче оптимизации производст- венных расписаний. Современная история математического моделиро- вания задачи расписаний ведет свое начало с форму- лировки Р. Беллманом задачи об определении крат- чайшей по времени последовательности обработки ряда деталей на нескольких станках [2]. Первое реше- ние задачи для двух станков и частного случая трех станков описано С. Джонсоном [3]. Именно задача расписаний, в наиболее отчетливой форме отражаю- щая временной аспект календарного планирования, составила основу специальной ветви математической экономики, известной как теория расписаний [4–7]. Особый этап в решении этой задачи состоял в по- исках ее описания в виде модели математического программирования, которое сводится к последова- тельному решению задач линейного программирова- ния (ЛП) [8; 9]. Недостатки формулировки модели в дискретном времени связаны с растущей громоздко- стью задачи при уменьшении длительности такта. Однако при укрупнении такта теряется точность от- ражения действительности, поскольку календарный план (расписание) внутри такта во внимание не при- нимается. Дальнейшее применение математических методов к задаче расписаний развивалось, с одной стороны, по пути теоретических исследований и разного рода обобщений, а с другой – по пути поиска практических решений. Здесь можно выделить использование сис- темы приоритетов или функций предпочтения, при- дарного планирования выделяют задачу распределе- ния производственной программы по отдельным ка- лендарным периодам (ОКП), которая может быть ре- шена с помощью комплекса моделей, охватывающего всю систему организации подготовки производства на предприятии. Имитационное моделирование. В имитационной модели присутствуют станки, перед которыми в про- цессе изготовления изделий накапливаются очереди из партий одинаковых деталей, ожидающих обработ- ки. Каждая партия деталей в очереди имеет приоритет – численное значение, характеризующее порядок вы- бора партии деталей из очереди для обработки. При- оритеты могут быть как постоянными на промежутке времени, в течение которого партия деталей находит- ся в очереди, так и изменяющимися в зависимости от ситуации в цехе. Имитационная модель прежде всего загружает те операции, которые могут начаться в этот момент. Как только все такие операции назначены, модель про- двинет время до следующего события, например до момента окончания самой короткой по длительности операции из ранее запущенных. В этом случае со- стояние ресурса (машина, человек) меняется с занято- го на свободное и модель будет пытаться загрузить следующую операцию на освободившийся ресурс. Далее модель работает в таком же режиме, продвигая время до момента следующего события и назначая операции на освободившиеся ресурсы до тех пор, по- ка все операции не будут загружены. 31 Математика, механика, информатика Одним из главных вопросов при составлении рас- писаний является вопрос о критерии или критериях оптимизации расписания. Одним из таких критериев является критерий ми- нимума календарной длительности выполнения всего комплекса работ, который очень часто используется в системах управления проектами и в MES-системах (от англ. Manufacturing Execution System – производст- венная исполнительная система) начального уровня. Но этот критерий имеет существенный недостаток. Допустим, имеется некое множество M работ (тех- нологических операций), которое необходимо выпол- нить на множестве N рабочих центров (РЦ). Возьмем классический случай, когда каждая операция может быть выполнена на любом из РЦ. Если во множестве N имеются не две-три опера- ции, а значительно больше, как это и бывает в реаль- ных случаях (например, в мелкосерийном производ- стве участок из 100 РЦ за смену может обработать до 300 операций), то оптимальному решению при ис- пользовании критерия минимума календарной дли- тельности всегда соответствует хотя бы одна после- довательность операций a, b, …, c, для которой сум- марное время выполнения этой последовательности T нельзя уменьшить. Если на первых же итерациях по- иска будет получен плотный по загрузке оборудова- ния вариант, который высвободит сразу несколько РЦ, то высвободившихся при этом рабочих можно переместить на другие участки, где есть потребность в рабочей силе. Если же будет получен вариант, характеризую- щийся весьма неэффективным распределением опе- раций между РЦ, то дальнейший поиск ничего не даст, так как величина длительности выполнения все- го множества работ T не уменьшится. Руководствуясь таким критерием и отработав все варианты, алгоритм выдаст график загрузки в виде «лоскутного одеяла», который характеризуется простоями оборудования. А ведь за простои рабочему надо платить, да и сами станки, как известно, бесплатно не простаивают. Вот почему «интегральной характеристикой любого про- изводственного расписания может являться общая площадь этого самого „лоскутного одеяла“ на диа- грамме Гантта» [17]. Нередко иные начальники производств для повы- шения коэффициента загрузки оборудования стара- ются минимизировать простои станков путем запол- нения пробелов в расписании работами, относящими- ся к выпуску изделий следующего планового периода, т. е. сознательно увеличивают объем незавершенного производства (НЗП). Однако неоправданный рост НЗП – это настоящее «самоедство» для любого про- изводства, поскольку при этом связывается значи- тельная доля оборотных средства предприятия. Рассмотренная проблема характерна не только для критерия минимума календарной длительности, но и для других подобных ему частных критериев. Можно сказать, что многие частные критерии, улучшая тот или иной показатель расписания, могут ухудшить остальные его показатели. Например, если в расписа- нии не настаивать на требовании, чтобы все работы непременно уложились за время Т, то можно было бы еще сильнее уплотнить диаграмму Гантта. В этом и состоит та особенность, которая отличает алгорит- мы планирования, принятые в управлении проектами, когда минимизируются суммарное время исполнения проекта (здесь время Т увеличивать нельзя, можно только его сокращать), от алгоритмов составления расписаний, используемых в MES-системах, когда выдвигается интегральное требование минимизации площади, занятой распределяемыми работами. Итак, что же такое частный критерий? Это крите- рий, который отражает какую-либо одну особенность при построении расписания, например минимизацию времени переналадок, минимум транспортных опера- ций и др. В противовес этим критериям существуют критерии интегрального характера, к которым отно- сятся критерии минимума всех непроизводительных времен, минимума стоимости выполненного расписа- ния и др. Для таких критериев системный анализ на основе жесткого руководства «Разделяй и властвуй» дает более гибкое решение: «Разделяй, синтезируй, власт- вуй». Это, в частности, относится к так называемым векторным критериям планирования. Векторный кри- терий – это такой интегральный критерий, в который могут входить несколько частных критериев, иногда противоречивых, при этом чем более противоречат друг другу частные критерии, тем сложнее отыскать оптимальное решение. Нетрудно догадаться, что из нескольких частных критериев можно создать очень большое количество комбинаций, которые могут пригодиться для самых различных производственных ситуаций. При оптими- зации расписаний в MES-системах с помощью век- торных критериев применяются различные методики, но чаще всего это поиск оптимума на парето- множествах [18]. Таким образом, за счет использования в MES-сис- темах векторных критериев повышается управляе- мость при построении расписаний, что существенно увеличивает эффективность использования парка до- рогостоящего оборудования. Следующим весьма интересным вопросом являет- ся вопрос о назначении приоритетов партий деталей при планировании. Как мы уже отмечали, каждая пар- тия деталей в очереди имеет приоритет – численное значение, характеризующее порядок выбора партии деталей из очереди для обработки. Приоритеты могут быть как постоянными на промежутке времени, в те- чение которого партия деталей находится в очереди, так и динамическими. Правила диспетчирования, в соответствии с кото- рыми работы выбираются из очереди перед станком, были классифицированы, а в дальнейшем были про- ведены исследования по определению того, какие правила диспетчирования дают более точное решение в задачах с заданными критериями построения распи- саний [19]. 32 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Класс 1 содержит простые приоритетные правила, в основу которых положена информация о работах, например: – Shortest Processing Time (SPT) – наименьшая длительность обработки; – Earliest Due Date (EDD) – ближайший срок го- товности; – Minimum Slack (MINSLACK) – минимальный ре- зерв времени; – First In – First Out (FIFO) – первым вошел, пер- вым вышел. пряженность заказа, тем выше приоритет. В процессе планирования MES-система отыскивает для каждого заказа момент начала его выполнения таким образом, чтобы этот момент не превышал директивного мо- мента τid . Такой метод назначения приоритетов помогает MES-системе правильно распределить заказы между сменами. Если же на всем горизонте планирования любой заказ может быть выполнен в любой момент времени, то расстановка приоритетов является из- лишней. Класс 2 состоит из правил, являющихся комбина- циями правил из класса 1. В частности, правило Моменты τid становятся известными на этапе может динамически зависеть от ситуации в цехе. Например, если длина очереди меньше 5, то применя- ется правило FIFO, в противном случае – правило SPT. Это способствует тому, что работы с большими длительностями обработки не будут долго стоять в очереди. Класс 3 содержит правила, относящиеся к взве- шенным приоритетным коэффициентам. Назначение приоритетов в общем случае происходит строго в со- ответствии со следующей методикой. Допустим, что у нас есть некий заказ – партия де- талей i-го наименования из множества номенклатуры предварительного планирования – это функция SCM в APS-системах, управление цепочками поставок, в том числе временными цепочками потока номенк- латуры для цехов предприятия. В последние 40 лет эффективность большого ко- личества правил диспетчирования была широко изу- чена с применением имитационного моделирования [20]. Целью этих исследований был поиск ответа на вопрос: «Какое правило диспетчирования нужно выбрать, чтобы оптимизировать конкретный крите- рий, выбранный при составлении расписания?» Большая часть ранних работ была сконцентрирована запуска N = {1, 2, …, i, …, n}, имеющая согласно тех- на правиле наименьшей длительности обработки (SPT). Р. В. Конвей [21] был первым, кто изучил пра- нологическому процессу определенное количество операций, для каждой из которых нам известно время ее выполнения. Тогда сумму времени для выполнения всей операционной последовательности i-го заказа обозначим через ti . Кроме того, у каждого заказа из- вестен директивный момент его выхода из цеха τid . Если мы начнем составлять план на несколько дней на каком-либо горизонте планирования от мо- мента начала плана, то увидим, что некоторые заказы можно выполнить только в первый день, так как пе- ренос начала их выполнения на следующий день или даже чуть ранее приведет к нарушению директивных вило SPT и его вариации. Он показал, что хотя неко- торые отдельные работы могут иметь достаточно продолжительные суммарные (вместе с ожиданиями) времена обработки, правило наименьшей длительно- сти обработки минимизирует средние суммарные (вместе с ожиданиями) времена обработки для всего множества работ на горизонте планирования. Он так- же показал, что правило SPT является лучшим выбо- ром для минимизации среднего времени ожидания работ в очереди и максимизации среднего коэффици- ента использования оборудования.