УДК 004 : [658.52 : 681.51] : 621.38
Ю. О. СОРОКИНА
J. O. SOROKINA
КОНЦЕПТУАЛЬНАЯ ОСНОВА И НОТАЦИЯ ДЛЯ ДЕТЕРМИНИРОВАННЫХ МОДЕЛЕЙ ОПЕРАТИВНО-КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА
CONCEPTUAL FRAMEWORK AND NOTATION FOR SCHEDULING DETERMINISTIC MODELS
В статье представлена адаптированная версия нотации, используемой в детерминированных моделях оперативно-календарного планирования производства.
Ключевые слова: оперативно-календарное планирование; работа; станок; продолжительность выполнения работы; плановая дата начала работы; плановая дата окончания работы; поточная обработка; гибкая непоточная обработка.
In this paper presents an adapted version of notation for scheduling deterministic model.
Keywords: scheduling; job; machine; processing time; release date; due date; flow shop; flexible job shop.
ВВЕДЕНИЕ
Необходимость непрерывного и ритмичного производственного процесса обусловливает применение на предприятиях оперативно-календарного планирования, при котором обеспечивается согласованность действий всех структурных подразделений и, как следствие, эффективное достижение запланированных результатов деятельности предприятия. Оперативно-календарное планирование (ОКП) представляет собой процесс принятия решений, направленный на решение комплекса задач во времени и пространстве, связанных с контролем, учетом и регулированием хода производственных работ в соответствии с установленными планами и заданиями в рамках взаимосвязанных рабочих центров (цехов) [1].
Опыт показывает, что обеспечить эффективное оперативно-календарное планирование на предприятии бывает порой чрезвычайно сложно. Процесс оперативно-календарного планирования включает комплексное решение следующих взаимосвязанных задач [3]:
- составление наиболее рациональных технологических маршрутов обработки различных деталей и изделий;
- оптимальное распределение и закрепление детале-операций между станками внутри выделенных групп взаимозаменяемого оборудования;
- определение оптимального размера партии обрабатываемых деталей;
- обеспечение оптимальной очередности запуска деталей в обработку;
- обеспечение выпуска готовой продукции в необходимом объеме и в требуемые сроки.
Решение всех перечисленных задач ОКП на современном производстве без применения информационных технологий, в основе которых лежат адекватные математические модели, практически невозможно. В данной статье предлагается гибкая концептуальная основа и нотация для детерминированных моделей ОКП.
КОНЦЕПТУАЛЬНАЯ ОСНОВА И НОТАЦИЯ
При решении всех задач ОКП оперируют понятиями конечных множеств работ и ресурсов. Работ и ресурсы могут принимать множество форм. Так, в качестве ресурсов можно рассматривать оборудование рабочих центров, бригады рабочих на производственных площадках, обрабатывающие устройства в вычислительной среде и т. д. Работы могут быть представлены операциями производственного процесса, этапами различных проектов, алгоритмами компьютерных программ и т. п. При описании концептуальной основы и нотации в рамках данной статьи будем соотносить оборудование (станки) рабочих центров (цехов) с ресурсами, а производственные задания на обработку деталей и изделий – с работами.
Итак, обозначим литерой n количество работ, а количество станков – литерой m. Нижний индекс j соотнесем с работой, а нижний индекс i – со станком. Введем следующую нотацию, связанную с работой j:
- pij – продолжительность (время) выполнения работы j на станке i. Если продолжительность выполнения работы j не зависит от станка или работа j выполняется только на одном имеющемся станке, то нижний индекс i может быть опущен;
- rj – плановая дата начала работы j. Соотносится с временем прихода работы в производственную систему. Другими словами, это самое раннее время начала выполнения работы j;
- dj – плановая дата окончания работы j. Соотносится с плановой датой отгрузки или обещанной клиенту датой завершения работы j. Отметим, что работа может быть завершена позже своей плановой даты окончания, что, в свою очередь, приводит к возникновению дополнительных (штрафных) издержек. Если плановая дата окончания работы выступает в качестве предельно допустимого срока ее завершения, то нотация меняется на dj´;
- wj – вес работы j. Отражает приоритет (важность) работы по отношению к другим работам в системе производства.
Будем описывать задачу ОКП триплетом α | β | γ. Поле α описывает обрабатывающую (станочную, машинную) среду и содержит только одну запись. Поле β детализирует особенности и ограничения производственного процесса и может как совсем не содержать записей, так и содержать единственную или множественные записи. Поле γ описывает целевую функцию, которую необходимо минимизировать и, как правило, содержит единственную запись.
Рассмотрим возможные варианты обрабатывающей среды, определяемой в поле α:
1. Одиночный станок (1). Вариант с единственным обрабатывающим станком является самым простым из всех возможных вариантов обрабатывающей среды.
2. Однотипные параллельно обрабатывающие станки (Pm). Вариант с m однотипными параллельно обрабатывающими станками. Подразумевается, что работа j, представленная единичной операцией, может быть выполнена на любом из m станков. Если это условие не выполняется, и работа j может быть выполнена только на одном из станков, принадлежащем определенному подмножеству Mj, то соответствующая запись Mj заносится в поле β.
3. Параллельно обрабатывающие станки с различной скоростью (Qm). Вариант с m разноскоростными параллельно обрабатывающими станками. Скорость обработки станка i будем обозначать vi. Продолжительность выполнения pij для работы j на станке i приравнивается к величине pj / vi (предполагается, что работа j полностью выполняется на станке i). В данном случае, такая обрабатывающая среда является однородной (состоит из однородных станков). Если все станки имеют одинаковую скорость обработки, например, vi = 1 для всех i и pij = pj, то данная среда совпадает с ранее рассмотренной.
4. Неоднородные параллельно обрабатывающие станки (Rm). Данный вариант обобщает предыдущий. Пусть имеется m различных параллельно обрабатывающих станков. Станок i может выполнять работу j со скоростью vij. Продолжительность выполнения pij для работы j на станке i приравнивается к величине pj / vij (снова предполагается, что работа j полностью выполняется на станке i). Если скорость обработки станка не зависит от работы, то есть vij = vi для всех i и j, то данная среда совпадает с ранее рассмотренной.
5. Поточная обработка (Fm). Вариант представляется последовательностью из m станков. Каждая работа должна быть выполнена на каждом из m станков. Все работы должны следовать по одинаковому маршруту. После своего завершения на одном станке работа становится в очередь к следующему станку. Довольно часто все очереди обслуживаются по дисциплине FIFO (первый вошел – первый вышел). Если предусматривается возможность преодоления дисциплины FIFO, то поточная обработка превращается в поточную обработку с изменениями (перестановками), и в поле β заносится соответствующая запись.
6. Гибкая поточная обработка (FFc). Гибкая поточная обработка является обобщением вариантов среды поточной обработки и среды параллельно обрабатывающих станков. Вместо m последовательных станков среда представляется как c последовательных секций (групп). В каждой секции располагается определенное количество однотипных параллельно обрабатывающих станков. Каждая работа должна быть выполнена сначала в секции 1, потом в секции 2 и т. д. Секция функционирует как ряд параллельных станков. В каждой секции требуется выполнить работу j только на одном из любых станков. Управление очередями между разными секциями может осуществляться (а может, в частности, и не осуществляться) по дисциплине FCFS (первый пришел – первый обслужен).
7. Непоточная обработка (Jm). При непоточной обработке на m станках каждая работа имеет собственный предопределенный маршрут следования. Следует различать непоточную обработку, при которой каждая работа выполняется на каждом станке не более одного раза, и непоточную обработку, при которой каждая работа выполняется на каждом станке неоднократно. В последнем случае в поле β заносится соответствующая запись.
8. Гибкая непоточная обработка (FJc). Гибкая непоточная обработка является обобщением непоточной обработки и среды параллельно обрабатывающих станков. Вместо m последовательных станков среда представляется как c рабочих центров. В каждом рабочем центре располагается определенное количество одинаковых параллельно обрабатывающих станков. Каждая работа имеет собственный предопределенный маршрут движения при выполнении. В каждом рабочем центре требуется выполнить работу j только на одном из любых станков. Если в маршруте движения работы предусмотрено ее неоднократное выполнение, то в поле β заносится соответствующая запись.
9. Открытая непоточная обработка (Om). Вариант с m станками. Каждая работа должна быть выполнена на каждом из m станков. Следует отметить, что при этом в некоторых случаях продолжительность выполнения работы может быть нулевой. В данном варианте нет предопределений в отношении маршрутов движения каждой работы через производственную систему. Допускается определять индивидуальный маршрут движения для каждой работы.
Особенности и ограничения производственного процесса, определяемые в поле β, могут содержать множественные записи. Возможными записями в поле β являются следующие:
1. Плановая дата начала работы (rj). Если данная запись появляется в поле β, то работа j не может начать выполняться раньше своей плановой даты начала rj. Если rj не заносится в поле β, выполнение работы j может начаться в любое время. Отметим, что в отличие от плановой датой начала, плановая дата окончания работы не отражается в поле β. О наличии плановой даты окончания работы в ограничениях можно судить по типу целевой функции.
2. Приоритетные прерывания выполнения (prmp). Предполагается необязательность выполнения уже начавшейся работы на станке до полного ее завершения. Разрешается прерывать выполнение в любой момент времени и начинать другую работу на станке с сохранением результата прерванной работы. Причем, последующее выполнение прерванной работы на том же станке (или на другом станке в случае с параллельно обрабатывающими станками) будет осуществляться только в течение оставшейся продолжительности выполнения. Если приоритетные прерывания выполнения разрешены, то в поле β заносится запись prmp, и наоборот.
3. Ограничения предшествования (prec). Данные ограничения могут появиться в варианте обрабатывающей среды с одиночным станком или в варианте с параллельно обрабатывающими станками и содержат требование, чтобы одна или несколько работ могли бы быть завершены до того, как будет разрешено выполнение другой работы. Можно выделить несколько определенных видов ограничений предшествования: если каждая работа имеет не более одной предыдущей и не более одной последующей работы, то видом ограничений являются цепи. Если каждая работа имеет не более одной последующей работы, то ограничения относят к виду восходящего дерева. Если каждая работа имеет не более одной предыдущей работы, то ограничения относят к виду нисходящего дерева. Если поле β не содержит запись prec, то на работы не распространяются ограничения предшествования.
4. Последовательность зависимых времен переналадки (sjk). Представляет зависимую последовательность времен переналадки оборудования между выполнением работ j и k. Причем, s0k обозначает время наладки перед работой k, если работа k первая в последовательности, и sj0 – время чистки после работы j, если она последняя в последовательности (s0k и sj0 могут принимать нулевые значения). Если время переналадки между работами j и k зависит от станка, то нижний индекс i включается в обозначение, т. е. sijk. Если поле β не содержит запись sjk, то предполагается, что значения всех времен переналадки равны нулю или последовательность независима. В последнем случае значения времен переналадки входят в состав значений времен выполнения работ.
5. Семейства работ (fmls). В данном случае предполагается принадлежность n работ различным F семействам. Работы из одного семейства могут иметь различную продолжительность выполнения. Однако они могут быть выполнены на станке одна за другой без необходимости переналадки оборудования между ними. Тем не менее, если станок переключается между семействами работ, например, от семейства g к семейству h, то необходимо выполнить его переналадку. Если это время переналадки зависит как от g, так и от h, и последовательность является зависимой, то оно обозначается как sgh. Если время переналадки зависит только от семейства, с которого началось выполнение (семейства h), то оно обозначается как sh. Если оно не зависит от любого семейства, то обозначается как s.
6. Партионная обработка (batch(b)). Станок может выполнять некоторое количество работ (например, b) одновременно. Иначе говоря, может обрабатывать партию деталей вплоть до b деталей в одно и тоже время. Времена выполнения работ из партии могут быть различными, тогда обработка всей партии завершится вместе с завершением последней работы из партии. Подразумевается, что время обработки всей партии определяется работой с наибольшей продолжительностью выполнения. Если b = 1, то задача сводится к стандартной задаче ОКП.
7. Поломки (brkdwn). Предполагается возможность поломки оборудования, что ведет к его недоступности в непрерывном режиме. Будем считать, что период, в течение которого оборудование недоступно, является фиксированным (например, из-за перемещений или запланированного технического обслуживания). Если имеется перечень одинаковых параллельно обрабатывающих станков, то количество доступных станков в любой момент времени определяется функцией от времени m(t).
8. Запреты на пригодность станка (Mj). Символ Mj может появиться в поле β в том случае, если среда обработки представлена вариантом с m одинаковыми параллельно обрабатывающими станками (Pm). Если запись Mj присутствует, то не на всех m станках может выполняться работа j. Множество Mj описывает множество станков, которые могут выполнять работу j. Если поле β не содержит Mj, работа j может быть выполнена на любом из m станков.
9. Перестановки (prmu). Данное ограничение может появиться в варианте с поточной обработкой, при которой очереди перед каждым станком обслуживаются по дисциплине FIFO. Подразумевается, что порядок (или перестановка), в котором работы проходят через первый станок, поддерживается во всей системе.
10. Блокировка (block). Событие блокировки может произойти в среде поточной обработки. Если при поточной обработке между двумя последовательными станками существует ограниченный буфер, то в случае полного буфера расположенный вверх по потоку станок не может выпустить завершенную работу. Подразумевается, что при блокировке завершенная работа должна оставаться на предыдущем в последовательности станке для предотвращения его занятие следующей работой. Наиболее общий случай блокировки – наличие нулевого буфера между любыми двумя последовательными станками. При этом завершенная на имеющемся станке работа не может его покинуть до тех пор, пока не будет завершено выполнение предыдущей работы на следующем в последовательности станке. Заблокированная работа также не допускает и начало выполнения следующей работы на имеющемся станке.
11. Без ожиданий (nwt). Явление «нетерпеливости» также встречается в среде поточной обработки. Не допускается ожидание работ между двумя последовательными станками. Подразумевается, что начало выполнения работы на первом станке задерживается, пока не будет проверена возможность прохода работы без ожиданий через все станки поточной обработки. Как и в предыдущем ограничении, обслуживание станков осуществляется по дисциплине FIFO.
12. Циклическая обработка (rcrc). Циклическая обработка встречается в средах непоточной обработки и гибкой непоточной обработки, когда работа может посетить станок или рабочий центр более одного раза.
Любая другая запись, которая может появиться в поле β, не требует отдельного пояснения. Например, pj = p подразумевает равенство всех времен выполнения работ, а dj = d – равенство всех плановых дат окончания работ.
Перейдем к рассмотрению записей в поле γ. Целевая функция, которую необходимо минимизировать, всегда представляется функцией времени завершения работ, зависящей от плана. Время завершения операции по выполнению работы j на станке i обозначим как Cij. Время выхода работы j из системы производства обозначим Cj. Целевая функция также может быть представлена функцией плановой даты окончания работ. Задержка работы j определяется по следующей формуле:
.
Величина задержки является положительной, когда работа j завершена позднее, и отрицательной, когда завершена раньше. Запаздывание работы j определяется следующим образом:
.
Отличие задержки от запаздывания заключается в том, что величина запаздывания никогда не бывает отрицательной. Причем, единица издержек (штрафа), Uj, принимается равной единице, если Lj > 0, и равной нулю во всех остальных случаях.
Приведем возможные примеры целевых функций в поле γ, исследуемых на минимум:
1. Время (период) производства (Cmax). Определяется как max(C1, …, Cn) и является эквивалентом времени завершения последней работы, покидающей производственную систему. Минимизация периода производства в большинстве случаев ведет к приемлемому коэффициенту использования станков.
2. Максимальная задержка (Lmax). Определяется как max(L1, …, Ln) и является оценкой самого грубого нарушения плановых дат завершения работ.
3. Суммарное взвешенное время завершения (∑wjCj). Сумма взвешенных времен завершения n работ является индикатором суммарных издержек, возникающих при выполнении плана.
4. Оцененное суммарное взвешенное время завершения (∑
). Является обобщенной стоимостной функцией по сравнению с предыдущей. Стоимость рассчитывается с учетом процента скидки r, 0 < r < 1, на единицу времени. Так, если работа j не завершена ко времени t, то добавочная стоимость 
начисляется за период [t, t + dt]. Если работа j завершена ко времени t, то общие издержки за период [0, t] составляют 
.
5. Суммарное взвешенное запаздывание (∑wjTj). Также является обобщенной функцией по сравнению с суммарным взвешенным временем завершения.
6. Взвешенное количество запоздалых работ (∑wjUj). Представляет интерес простотой своей записи и практическим значением.
ЗАКЛЮЧЕНИЕ
В заключение рассмотрим пример нотации для наукоемкого производства полупроводниковых приборов [2]. Нотация FJc | rj, sijk, rcrc | ∑wjTj описывает среду гибкой непоточной обработки с c рабочими центрами. Работы имеют разные плановые даты начала и подчиняются последовательности зависимых времен переналадки, которые зависят от каждого конкретного станка. При этом возможны случаи возникновения циклической обработки, вследствие неоднократного посещения одной и той же работой одного рабочего центра.
Хотелось бы отметить, что на практике могут существовать модели ОКП, полностью не охватываемые предложенной концепцией и нотацией. Например, модель, в которой смешаны среды гибкой и открытой непоточных обработок. В этом случае маршрут для некоторых работ является предопределенных, в то время как для других работ (частично) – открытым.
Кроме этого, существуют возможности адаптации рассмотренной концептуальной основы и нотации для стохастических моделей ОКП. Одной из возможностей является рассмотрение переменных, связанных с работой j, в качестве стохастических, а не детерминированных переменных.
СПИСОК ЛИТЕРАТУРЫ
1. Василенко, (операционный) менеджмент [Текст] / Валентин Александрович Василенко, Татьяна Ивановна Ткаченко. – К.: ЦУЛ, 2003. – 532 с.
2. Калинина рекомендаций по автоматизации управления производством силовой электроники [Текст] / Юлия Олеговна Калинина // Информационные технологии в науке, образовании и производстве. ИТНОП-2010: Материалы IV Международной научно-технической конференции. – Орел: ОрелГТУ, 2010. – Т.3. – С. 113-119.
3. Пелих, -математические методы и модели в управлении производством [Текст] / Анатолий Савельевич Пелих, Лев Леонидович Терехов, Любовь Андреевна Терехова. – Ростов н/Д: Феникс, 2005. – 248 с.
ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
Аспирант кафедры «Информационные системы»
Тел.: +7(48
E-mail: *****@***ru
