Математические методы решения задачи составления цеховых расписаний

Базовым понятием для задач составления расписаний (Machine Scheduling, MS) является операция. Для задания операции, как правило, необходимы два агента: объект операции, или ее материальный носитель, – то, над чем производят операцию, и субъект операции, или исполнитель, – тот, кто (или что) выполняет операцию. В качестве материального носителя операции может выступать отдельная деталь или сборочная единица создаваемого изделия. Носителем операции может быть человек, обслуживаемый другими людьми (приборами). Субъектами операций являются станки (инструменты, люди), необходимые для выполнения этих операций. В моделях MS они обычно называются машинами .

Некоторые подмножества операций организационно (и технологически) объединяются в работы. Например, если завод выпускает сложные изделия (машины, самолеты и т. п.), то все операции, относящиеся к одному изделию, составляют одну работу. На некоторые работы может быть наложен жесткий директивный срок их окончания, которому соответствует английский термин Deadline (смертельная линия), и/или желаемый срок окончания Due Date, отклонение от которого наказывается штрафом; при этом Deadline и Due Date одной и той же работы могут не совпадать. Моменты {Cj} окончания работ {Jj} (С — от Completion Time) играют существенную роль в оценке качества обозначения построенного расписания: как правило, целевая функция задачи является функцией f (C1,..., Cn) от моментов завершения работ J1 ,..., Jn .

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

• –    каждая операция относится ровно к одной работе;

• –    каждая операция выполняется ровно на одной машине (возможно, выбираемой из множества альтернативных машин);

• –    никакие две операции одной работы не могут выполняться одновременно;

• –    никакие две операции одной машины не могут выполняться одновременно.

Задача составления плана проекта при ограниченных ресурсах (Resource-Constrained Project Scheduling Problem, RCPSP) [1] может быть сформулирована следующим образом. Дано n работ i = 1,..., n и r возобновляемых ресурсов к = 1,..., r . Постоянное количество R_k ресурса k доступно в любое время. Работа i должна быть произведена за время p_i . В течение этого времени на данной работе задействовано постоянное количество r_ik ресурса k . Кроме того, для работ определены отношения предшествования i ^ j , где i ^ j означает, что работа j не может начаться, пока не закончится работа i . Задача определения моментов начал S_i ставится для работ i = 1,..., n таким образом, что:

• –    в каждый момент времени t общая потребность в некотором ресурсе меньше либо равна наличию данного ресурса;

• –    соблюдены определенные выше отношения предшествования работ;

• -    величина C max = max C i принимает свое мини- i = 1... n

мальное значение, где C i = S i + p i - время завершения работы i .

Возможно прерывание работ.

Иногда полезно добавить начальную псевдоработу 0 и конечную псевдоработу n + 1, каждую с нулевой длительностью. Для всех работ i = 1,..., n , должны выполняться условия 0 ^ i и i ^ n + 1. Псевдоработы не требуют ресурсов. S ₀ – момент начала проекта, а момент S_{n + 1} может быть интерпретирован как момент окончания проекта.

Структура RCPSP должна быть представлена с помощью графа, где вершинами являются работы G = ( V , E ) . Здесь V - множество всех работ, E = { ( i , j ) | i , j е V ; i ^ j } отражает отношения предшествования. Каждой работе i ставятся в соответствие два множества: Fred ( i ) = { j | ( j , i ) е E } и

Succ ( i ) = { j | ( i , j ) e E } , где Fred ( i ) (Succ ( i ) ) -множество работ, находящихся в графе непосредственно перед (за) работой i .

Отношение предшествования i ^ j может быть заменено отношением «начало–начало»:

S i + l j < S j , (1) где l_ij – любое целое число, от знака которого зависит смысл соотношения (1). Если l j >  0 , то тогда работа j не может начаться, пока не пройдет l_ij времени после начала работы i , т. е. работа j не может начаться до момента начала работы i , и в этом случае l_ij – минимальная разница между моментами начала двух работ. Если l j <  0 , то работа i должна начаться не позже чем через - l j времени после начала работы j . Таким образом, l_ij называется положительной ( отрицательной ) временной задержкой , если (1) выполняется и l j >  0 ( l j <  0).

Соотношения (1) являются обобщенными. Например, если l j = p i , то это не что иное, как i ^ j . Если же между окончанием работы i и началом работы j должно пройти не меньше d_ij времени, то это можно записать как S i + p i + d j <  S j . Если выполняются условия S i + p, + d j <  S j и S j ^- u j — p i < S i , где 0 <  d ij <  u jj , то время между окончанием работы i и началом работы j должно быть не менее d_ij , но не более u_ij . Последнее включает частный случай 0 <  d ij = u jj , где работа j должна начаться точно через l_ij временных единиц после окончания работы i .

Для работы i ранние сроки начала r_i ( r – Release) и поздние сроки окончания d_i ( d – Deadlines) могут быть смоделированы соотношениями (1):

S 0 + r < S i , S_t - ( d i - р^ < S 0 .

Временной интервал [ r , d i ] называется временным окном работы i . Работа i должна начаться и закончиться между границами данного временного окна.

Таким образом, необходимо определить возобновляемый ресурс k объемом r_jkm для работы j длительностью p_jm .

Общая постановка задачи составления цехового расписания. Пусть имеются работы j = 1,..., n и m машин M1 ,..., Mm . Работа j состоит из nj операций O1j,..., Onj , j. Две операции одной работы не могут производиться одновременно. Операция Oij имеет длительность pij , если производится машиной ц е {M1,..., Mm }. Отношения предшествования существуют между любыми операциями. Такая общая задача составления цехового расписания может быть интерпретирована как RCPSP с r = m + n возобновляемыми ресурсами, где Rk = 1 для к = 1, ..., m + n , и с

n числом операций Oj, равным ^ nj . Кроме того, опе-j=1

рация O_ij использует объем ресурса k , равный r_ijk , где

• 1 0,    если ц j = M k или к = m + j, j = 1 1

[ 1 в противном случае.

Ресурсы к = 1,..., m соответствуют оборудованию, в то время как ресурсы m + j ( j = 1,..., n ) необходимы, чтобы моделировать ситуации, когда разные операции одной работы j не могут производиться одновременно.

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

Рассмотрим основные этапы применения математических методов к задаче оптимизации производственных расписаний.

Современная история математического моделирования задачи расписаний ведет свое начало с формулировки Р. Беллманом задачи об определении кратчайшей по времени последовательности обработки ряда деталей на нескольких станках [2]. Первое решение задачи для двух станков и частного случая трех станков описано С. Джонсоном [3]. Именно задача расписаний, в наиболее отчетливой форме отражающая временной аспект календарного планирования, составила основу специальной ветви математической экономики, известной как теория расписаний [4–7].

Особый этап в решении этой задачи состоял в поисках ее описания в виде модели математического программирования, которое сводится к последовательному решению задач линейного программирования (ЛП) [8; 9]. Недостатки формулировки модели в дискретном времени связаны с растущей громоздкостью задачи при уменьшении длительности такта. Однако при укрупнении такта теряется точность отражения действительности, поскольку календарный план (расписание) внутри такта во внимание не принимается.

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

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

Роль имитационных моделей состоит в наиболее полном использовании возможностей современных ЭВМ. Первоначально эти модели имели вид простейших в логическом отношении способов построения календарных графиков. Современные имитационные модели представляют собой сложные комплексы взаимосвязанных алгоритмов, включающие в себя построение моделей и их реализацию на базе различных методов [10].

Для решения задачи составления расписаний широко применяются методы динамического программирования и метод ветвей и границ [2], который с большим успехом используется при решении одной из разновидностей задачи одного станка [11] – задачи о переналадках [12].

В экономической литературе описана задача об определении оптимального размера партии запуска-выпуска деталей [13–16]. Размер партии деталей как основной плановый норматив в серийном производстве оказывает существенное влияние на экономические результаты деятельности предприятия, цеха, участка.

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

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

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

Одним из главных вопросов при составлении расписаний является вопрос о критерии или критериях оптимизации расписания.

Одним из таких критериев является критерий минимума календарной длительности выполнения всего комплекса работ, который очень часто используется в системах управления проектами и в MES-системах (от англ. Manufacturing Execution System – производственная исполнительная система) начального уровня. Но этот критерий имеет существенный недостаток.

Допустим, имеется некое множество M работ (технологических операций), которое необходимо выполнить на множестве N рабочих центров (РЦ). Возьмем классический случай, когда каждая операция может быть выполнена на любом из РЦ.

Если во множестве N имеются не две-три операции, а значительно больше, как это и бывает в реальных случаях (например, в мелкосерийном производстве участок из 100 РЦ за смену может обработать до 300 операций), то оптимальному решению при использовании критерия минимума календарной длительности всегда соответствует хотя бы одна последовательность операций a , b , …, c , для которой суммарное время выполнения этой последовательности T нельзя уменьшить. Если на первых же итерациях поиска будет получен плотный по загрузке оборудования вариант, который высвободит сразу несколько РЦ, то высвободившихся при этом рабочих можно переместить на другие участки, где есть потребность в рабочей силе.

Если же будет получен вариант, характеризующийся весьма неэффективным распределением операций между РЦ, то дальнейший поиск ничего не даст, так как величина длительности выполнения всего множества работ T не уменьшится. Руководствуясь таким критерием и отработав все варианты, алгоритм выдаст график загрузки в виде «лоскутного одеяла», который характеризуется простоями оборудования. А ведь за простои рабочему надо платить, да и сами станки, как известно, бесплатно не простаивают. Вот почему «интегральной характеристикой любого производственного расписания может являться общая площадь этого самого „лоскутного одеяла“ на диаграмме Гантта» [17].

Нередко иные начальники производств для повышения коэффициента загрузки оборудования стараются минимизировать простои станков путем заполнения пробелов в расписании работами, относящимися к выпуску изделий следующего планового периода, т. е. сознательно увеличивают объем незавершенного производства (НЗП). Однако неоправданный рост НЗП – это настоящее «самоедство» для любого производства, поскольку при этом связывается значительная доля оборотных средства предприятия.

Рассмотренная проблема характерна не только для критерия минимума календарной длительности, но и для других подобных ему частных критериев. Можно сказать, что многие частные критерии, улучшая тот или иной показатель расписания, могут ухудшить остальные его показатели. Например, если в расписа- нии не настаивать на требовании, чтобы все работы непременно уложились за время Т, то можно было бы еще сильнее уплотнить диаграмму Гантта. В этом и состоит та особенность, которая отличает алгоритмы планирования, принятые в управлении проектами, когда минимизируются суммарное время исполнения проекта (здесь время Т увеличивать нельзя, можно только его сокращать), от алгоритмов составления расписаний, используемых в MES-системах, когда выдвигается интегральное требование минимизации площади, занятой распределяемыми работами.

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

Для таких критериев системный анализ на основе жесткого руководства «Разделяй и властвуй» дает более гибкое решение: «Разделяй, синтезируй, властвуй». Это, в частности, относится к так называемым векторным критериям планирования. Векторный критерий – это такой интегральный критерий, в который могут входить несколько частных критериев, иногда противоречивых, при этом чем более противоречат друг другу частные критерии, тем сложнее отыскать оптимальное решение.

Нетрудно догадаться, что из нескольких частных критериев можно создать очень большое количество комбинаций, которые могут пригодиться для самых различных производственных ситуаций. При оптимизации расписаний в MES-системах с помощью векторных критериев применяются различные методики, но чаще всего это поиск оптимума на парето-множествах [18].

Таким образом, за счет использования в MES-системах векторных критериев повышается управляемость при построении расписаний, что существенно увеличивает эффективность использования парка дорогостоящего оборудования.

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

Правила диспетчирования, в соответствии с которыми работы выбираются из очереди перед станком, были классифицированы, а в дальнейшем были проведены исследования по определению того, какие правила диспетчирования дают более точное решение в задачах с заданными критериями построения расписаний [19].

Класс 1 содержит простые приоритетные правила, в основу которых положена информация о работах, например:

– Shortest Processing Time (SPT) – наименьшая длительность обработки;

– Earliest Due Date (EDD) – ближайший срок готовности;

– Minimum Slack (MINSLACK) – минимальный резерв времени;

– First In – First Out (FIFO) – первым вошел, первым вышел.

Класс 2 состоит из правил, являющихся комбинациями правил из класса 1. В частности, правило может динамически зависеть от ситуации в цехе. Например, если длина очереди меньше 5, то применяется правило FIFO, в противном случае – правило SPT. Это способствует тому, что работы с большими длительностями обработки не будут долго стоять в очереди.

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

Допустим, что у нас есть некий заказ – партия деталей i -го наименования из множества номенклатуры запуска N = { 1,2, .., i, ..., n } , имеющая согласно технологическому процессу определенное количество операций, для каждой из которых нам известно время ее выполнения. Тогда сумму времени для выполнения всей операционной последовательности i -го заказа обозначим через t_i . Кроме того, у каждого заказа известен директивный момент его выхода из цеха т id .

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

В любом случае заказ может быть выполнен, если момент окончания его выполнения т,„ не больше ди-iк рективного срока выпуска, т. е. должно выполняться условие тiк < тid. Тогда напряженность для любого i-го заказа можно представить в виде его коэффициента напряженности K 1 = ti /{гid -тiн), где тiн - момент начала выполнения заказа.

Другим вариантом взвешенного коэффициента напряженности может быть коэффициент ^K 2 = w j t i + w 2 ( t тек - T id ) , где t тек ^- текущее время; w j и w ₂ – весовые коэффициенты, задаваемые пользователями.

Вся номенклатура, подлежащая планированию в MES-системе, ранжируется согласно коэффициенту напряженности заказов K1 или K2 , в соответствии с которым назначаются приоритеты: чем больше на- пряженность заказа, тем выше приоритет. В процессе планирования MES-система отыскивает для каждого заказа момент начала его выполнения таким образом, чтобы этот момент не превышал директивного момента тУ.

Такой метод назначения приоритетов помогает MES-системе правильно распределить заказы между сменами. Если же на всем горизонте планирования любой заказ может быть выполнен в любой момент времени, то расстановка приоритетов является излишней.

Моменты т id становятся известными на этапе предварительного планирования – это функция SCM в APS-системах, управление цепочками поставок, в том числе временными цепочками потока номенклатуры для цехов предприятия.

В последние 40 лет эффективность большого количества правил диспетчирования была широко изучена с применением имитационного моделирования [20]. Целью этих исследований был поиск ответа на вопрос: «Какое правило диспетчирования нужно выбрать, чтобы оптимизировать конкретный критерий, выбранный при составлении расписания?» Большая часть ранних работ была сконцентрирована на правиле наименьшей длительности обработки (SPT). Р. В. Конвей [21] был первым, кто изучил правило SPT и его вариации. Он показал, что хотя некоторые отдельные работы могут иметь достаточно продолжительные суммарные (вместе с ожиданиями) времена обработки, правило наименьшей длительности обработки минимизирует средние суммарные (вместе с ожиданиями) времена обработки для всего множества работ на горизонте планирования. Он также показал, что правило SPT является лучшим выбором для минимизации среднего времени ожидания работ в очереди и максимизации среднего коэффициента использования оборудования.