<<
>>

4.2.Э. Алгоритм формирования расписания работ в ГПК

В моделях, представленных в данной работе могут быть использованы как аналитические алгоритмы, так и эвристические. Аналитические алгоритмы, рассмотренные как в рамках теории расписаний [261, 263, 131, 264, 269, 224, 262], так и с точки зрения решения дискретных задач на графах [135, 280, 223, 43, 152 и др.], как правило, позволяют решать задачи либо с ограниченным числом параметров, либо небольшой размерности, либо алгоритмы имеют жесткую привязку к конкретному критерию.
В то же время использование таких алгоритмов, например, известного метода ветвей и границ, полезно с точки зрения проверки адекватности, как самих математических моделей, так и оценки эффективности эвристических алгоритмов для этих моделей.

Большинство алгоритмов, используемых на сегодняшний день в ОКП и MES-системах, являются закрытыми, поскольку представляют собой know-how фирм-разработчиков ПО. На основании этих же соображений в работе представлен один из возможных для построения расписаний, работающих алгоритмов, обладающих допустимой сходимостью и скоро-стью сходимости (время составления расписания для 70 ГПМ, 500 операций и пяти ТС не превышает трех минут), основы которого были разработаны автором в работах [62, 258, 63] и дополнены в настоящей работе с учетом всего разнообразия ОУ, применяемых в ГПК и их структурных и технологических особенностей при обслуживании.

Постановка задачи в общем случае выглядит следующим образом.

На номенклатуре деталей M{e..,i = \,m;j = l,p.}, представленной в

U '

виде пооперационной технологии ЕП е.. и множестве ОУ, в качестве ко-

202 торых выступают ГПМ, ТС и ОУ складской системы N{n,} U R{r,} U S{n }

необходимо составить оптимальное расписание по выбранному критерию задачи.

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

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

Рис.4.7. Сетевая интерпретация задачи расписания

Данный тип задач при количестве ОУ больше трех относится к классу JVP-сложных задач в сильном смысле [263] и ее графическая интерпретация всегда может быть представлена в виде сети (рис.4.7).

203

Данная сетевая интерпретация потоковой задачи справедлива не только для ГПК, но также для случая составления расписания только для

ПЛОДНОГО ГПМ. На сети G{^ 2 ен)необходимо построить путь или назна-

нн 3

чение в , который бы включал в себя все вершины, не содержал циклов и

удовлетворял условиям задачи.

В качестве вершин выступают ЕП, а весовые оценки дуг Q пред-ставляют собой времена переналадок ГПМ при включении в расписание данной ЕП.

В качестве алгоритма решения подобных задач в работе предлагается аддитивный алгоритм [113], разработанный на основе метода ветвей и границ (МВГ) и других алгоритмов и опробованный на аналогичных мате-матических моделях [62,258, 63].

Исходными данными для алгоритма формирования расписания в ГПК являются:

1) Информация по деталям:

1.1) Номенклатура деталей М, представленная в виде ЕП е..и назна-

ченная на обработку на данном горизонте планирования.

1.2) Полная технологическая информация по деталям - технологиче

ские матрицы Г, , директивные сроки выполнения деталей, мат-

ai

рицы возможности обработки конкретных деталей на каждой из единиц технологического оборудования.

2) Информация по технологическому оборудованию:

Перечень ГПМ, функционирующих на данном горизонте планирования с указанием моментов начала и окончания их планируемого фонда времени.

Матрицы состояний ГПМ S, , сформировавшиеся на момент пла-

j

нирования.

204

2.3) Структурные особенности каждого ГПМ, отраженные структурны

ми формулами (4.8).

2.4) Технологические условие функционирования - возможность со

вмещения процессов переналадки и съема-установки ресурсов, ха

рактер моментов съема-установки (4.8).

3) Информация по складским системам:

Перечень ОУ складских систем, функционирующих на данном горизонте планирования с указанием моментов начала и окончания их планируемого фонда времени.

Матрицы состояний ОУ складских систем, сформировавшиеся на момент планирования.

Структурные особенности каждого склада, отраженные структурными формулами (4.15).

Состояние всех ресурсов на складах (инструмент и оснастка, временные параметры инструмента).

4) Информация по транспортным средствам:

Перечень ТС, функционирующих на данном горизонте планирования с указанием моментов начала и окончания их планируемого фонда времени.

Матрица транспортной системы с указанием состояния и положе-ния ТС на путеводе.

5) Информация по требуемой эффективности ГПК:

Выбранный критерий эффективности из табл.4.1.

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

Сетевая интерпретация (см. рис.4.7) дает лишь общее представление

о поточном характере алгоритма решения и полностью отражает механизм формирования расписания для ГПК имеющего в своем составе только одно обслуживающее устройство - ГПМ.

В случае нескольких типов ОУ каждая из вершин сети - ЕП может быть обслужена различными ОУ и поэтому алгоритм формирования рас-

205

расписания может быть представлен в виде ориентированного графа G (рис.4.8).

Рис.4.8. Представление задачи составления расписания в виде графа

Граф имеет фиктивную вершину-источник S^, после которой идут вершины, представляющие ЕП е.,. Каждая единица планирования пред-

ставлена на графе п раз по количеству ГПМ в ГПК.

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

206

T*av

= minF

к,' if к

(4.22)

*<*('«*)

-T

0eijk ,J

i,ceM;keN;

¦H ^ /»-KH

Oe... гЧ)е.. , ;

ijk ij-ls

k,seN{l,n};

^H •> TKH

T0.17 ~тОе ilk

dpds

где параметр Ф^,, \e А- это загрузка &-го ГПМ при включении в его рас-писание ЕП е ,, последней перед рассматриваемой ЕП е.., и его можно найти из следующего рекуррентного уравнения:

max

_KH ^.KH

ЧШРе.., ,cT?e..t

ijk ijk

k,s e N{\,n};

le.eAf^v^ee.;

кн Oe

csk

C?'(4.23)

(4.24) (4.25)

Ф'ск[еукУФ'ск{ес^)+1Ое ' V

max

кн кн

ЧШРе.., iTT?e..7

ijk ijk

i,ceM;keN;

кн Ое

csk

(4.26)

Выражение (4.22) означает выполнение условия по выбранному функционалу F задачи. Выражение (4.23) представляет собой ограничение задачи по загрузке технологического оборудования. Выражение (4.24) -условие предшествования ЕП согласно логике ТП. Выражение (4.25) - условие предшествования для ЕП в виде сборочных узлов.

Данные условия аддитивности являются достаточными в случае отсутствия транспортной операции, вызванной заявкой ГПМ на установку или съем ресурсов в ГПМ.

В процессе формирования расписания при просмотре аддитивных вершин на графе ветвления определяют наличие транспортной операции. Если на пути графа поиска, т.е. в расписании в, существует ЕП е..,, то

207 при включении в этот путь ЕП е.. ., появляется транспортная операция. В

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

"1 "2 г

Рис.4.9. Учет транспортной операции

Ф

Т/ГЫгГ'тР, е.., + ГТТУ7 е.., +'ТТС, е... +

lm ijk lm ijk lm ijk

+,ТСУ, *..t+fTCC, «... SV*M:

lm ijk lm ijk

(4.27)

KH

-H

>T,

/ ijk fmhq

, l€R;i,meM;k,qeN{l,n};

(4.28)

где параметр ФТ/(е > ]- это загрузка /-го ТС при включении в его расписание операции по перевозке ЕП е ,, последней перед рассматриваемой ЕП е.., и его можно найти из следующего рекуррентного уравнения:

+ f2 + *?

+/,

Фт/Ы

1=фт/Ы

lm ijk lm ijk

lm ijk

ТР, е.., "ТГУ, е.., "ТТС, е..,

(4.29)

+ *ТСУ, е.., +'ТСС7 е..,

lm ijk lm ijk

208

Выражение (4.27) представляет собой ограничение задачи по загрузке ТС. Выражение (4.28) отражает условие предшествования для ТС.

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

Далее формируется структурная формула обслуживания (3.2) и для данной формулы из таблиц 3.1 и 3.2 определяются соответствующие временные зависимости обслуживания заявок (см. главу 3) и их величины. При этом определяется как время занятости ТС, так и время занятости ОУ склада.

Структурная формула обслуживания для каждого конкретного случая в процессе поиска определяется автоматически и основой ее синтеза служат элементы структуры, представленные в модели задачи.

Таким образом, определяется участие в работе по включению в рас-писание работы ГПК текущей ЕП не только ТС, но и складской системы. При участии складской системы должно выполняться следующее условие аддитивности, образованное от ограничения по фонду времени ОУ складской системы общей модели.

ФСК/Ы+'СУ, ,.., +'СС, е.., *ФСкГ ,eS<4>; <4-30>

209 где параметр Фг ,[ е , 1 - это загрузка /-го ОУ склада при включении в его расписание операции по перевозке ЕП е ,, последней перед рассматриваемой ЕП е.., и он также определяется рекуррентно:

*ы{%УФ'сА%*кУ'сУ1те..к+,СС1те..^ l*SW' (4J1>

Кроме того, должно соблюдаться условие предшествования для ОУ складской системы из общей модели:

ТСе ~ГСе ' ^S;i,meM;k,qeN{\,n}; I ijk I mhq

Если рассматриваемая вершина удовлетворяет всем вышеперечисленным условиям аддитивности, то она включается в текущий путь-

расписание в.

Для каждой вершины, из которой осуществляется ветвление, определяется множество аддитивных вершин (АВ)

V=№ (432)

где в подмножество С, входят все вершины, которые были включены в

расписание в', а в В.., входят вершины, не включенные на данном этапе в

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

rj(e.jV...,eijn) = {0,\}. (4.33)

Если какая-либо ЕП е.., была включена в в', то всем ЕП, имеющим схожие первые индексы / и j присваивается значение маркера равным «1» и в

210

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

Поскольку времена переналадок ГПМ Л-гор являются неопре-

eijk

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

дачи F для любого первого пути на графе, удовлетворяющего ограниче-

ниям задачи. В начале работы алгоритма функционалу F присваивается значение оо.

При включении каждой очередной ЕП изменяются состояние любого к-то ГПМ, в который бьша включена аддитивная вершина, на очередное 7+1-е 5, , состояния складских систем и транспортной системы.

7+1

После нахождения первого допустимого решения задачи, характеризующегося включением в расписание всех ЕП, текущим значением функ-

г

ционала F и допустимым расписанием в', осуществляется поиск оптимального решения.

Оптимизация заключается в последовательности процедур возврата на графе поиска и последующего ветвления с нахождением нового назначения в' с новой текущей оценкой. При нахождении каждого допустимого решения задачи, начиная с первого, для допустимой последовательности в' фиксируется список включаемых вершин (ЕП) с порядком включения. Фиксируются также все состояния ресурсов (ГПМ, ТС, складов) для каждой включаемой вершины на текущем пути в'.

В данном алгоритме с процедурами ветвления-возврата, для сокращения времени счета предусмотрены, кроме рассмотренных выше, следующие процедуры:

211

1) Группирование партий ЕП, до процедуры ветвления, с такими из

вестными эмпирическими правилами, как:

первыми в исходный стек вершин графа устанавливаются наиболее длительные, по количеству операций, партии деталей;

первыми устанавливаются наиболее длительные, по времени обработки, ЕП, и другие аналогичные правила.

Плавающее значение горизонта планирования. При этом первоначальное значение горизонта планирования равно минимальной величине обработки партии ЕП из номенклатуры запуска. В дальнейшем, значение горизонта увеличивается до номинальной с дискретой, величина которой зависит от средней величины выполнения ЕП для номенклатуры запуска. Такой прием позволяет более плотно, по аналогии с упаковочными задачами, загрузить временные оси ГПМ теми или иными ЕП.

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

4) Фрагментация временной оси обслуживающего устройства. При

этом для каждой временной оси на каждом шаге алгоритма, начиная с пер

вого, фиксируется множество свободных интервалов времени, которые в

дальнейшем рассматриваются на предмет заполнения той или иной рабо

той.

Процедура улучшения функционала осуществляется до тех пор, пока множество Bs для источника не окажется пустым. При этом текущее зна-

чение функционала F после окончания поиска окажется искомым оптимумом задачи, а текущее расписание &' будет представлять оптимальное

у

расписание всего ГПК - в с линейной последовательностью включения ЕП в расписание

^tyf-V*- (434)

212 Данное расписание расписывается на соответствующие ГПМ:

ei{el\V"eijk ^7z%\V'">eQrsJ

е*\

2П\2""*<1Г!1> . (4.35)

en\e52n""empmnj

В случае если в процессе решения не будет найдено ни одно решение, необходимо корректировать изначальную модель планирования -уменьшать назначение, увеличивать количество ОУ и т.д.

Поскольку информация о состоянии всех ресурсов в ГПК сохраняется только для текущего пути в', то необходимо восстановить все состояния ГПК для оптимального расписания в качестве директивных указаний согласно последовательности (4.34). Для этого в алгоритме используется процедура прямого хода.

<< | >>
Источник: Загидуллин Равиль Рустэм-бекович. Система оперативно-календарного планирования автоматизированного механообрабатывающего мелкосерийного производства на основе комплексных моделей [Электронный ресурс] : диссертация... д-ра техн. наук : 05.13.06. - Москва: РГБ,2007. - (Из фондов Российской Государственной Библиотеки).. 2007

Еще по теме 4.2.Э. Алгоритм формирования расписания работ в ГПК:

  1. 2.7. Имитационная модель формирования расписания в ГПК
  2. 4.5.3.2. Математическая модель формирования межцеховых расписаний для нескольких ГПК и СОУ с различным составом функционала и ограничений
  3. 4.2.Э.1. Процедура прямого хода в алгоритме формирования оптимального расписания
  4. 4.5.3.1. Математическая модель формирования межцеховых расписаний для нескольких ГПК и СОУ с одинаковым составом функционала и ограничений
  5. Стадия 1. Формирование алгоритма работы и доверия
  6. 5.4. Особенности алгоритма формирования работ в ГПС с учетом дифференциации операций
  7. Алгоритм поэтапного построения оптимального расписания для многокритериальной задачи (остаточный метод)
  8. 4.5.3.2.1. Особенности алгоритма построения оптимального расписания для многокритериальной задачиОптимизация с помощью оптимума Парето
  9. 2.3. Алгоритм формирования множества номенклатуры деталей, подлежащих планированию
  10. 4.1. РАЗРАБОТКА МНОГОПОТОЧНОГО АЛГОРИТМА РАБОТЫ МУЛЬТИГОЛОВОЧНОГО ДОЗАТОРА
  11. 2.2. ОПРЕДЕЛЕНИЕ ХАРАКТЕРИСТИК МАСС ГОТОВЫХ ДОЗ НА ВЫХОДЕ ИЗ ДОЗАТОРА ДЛЯ РАЗЛИЧНЫХ АЛГОРИТМОВ РАБОТЫ МГД
  12. 2.6. Модель укрупненного планирования в ГПК
  13. 4.2. Комплексная модель ОКП для ГПК механической обработки
  14. Формирование у учащихся умений и навыков домашней учебной работы
  15. Глава 26. ФОРМИРОВАНИЕ МИРОВОЗЗРЕНИЯ ШКОЛЬНИКОВ В ОБЩЕЙ СИСТЕМЕ УЧЕБНО-ВОСПИТАТЕЛЬНОЙ РАБОТЫ
  16. 4.5.1. Математические модели расписаний с локальными обслуживающими устройствами