Строительные исследования
страница - 0
Многостадийные задачи распределения и упорядочения с нечеткими характеристиками
Прилуцкий М.Х. (pril@liso.sandy.nnov.su), Попов Д.В.(dennis popov@hotmail.com)
Нижегородский государственный университет им. Н.И.Лобачевского, Россия, 603600, Нижний Новгород, пр. Гагарина, 23
Рассматриваются многостадийные задачи теории расписаний в достаточно общей постановке (с учетом переналадок, затрат на выполнение работ, директивных сроков, произвольных технологических маршрутов выполнения работ) с нечеткими исходными параметрами, связанными с временными и стоимостными характеристиками работ. Строится общая математическая модель, в которой присутствуют операторы и операции с нечеткими параметрами. Ставятся оптимизационные задачи и предлагаются алгоритмы их решения.
1. Содержательная постановка задачи.
Задачи распределения ресурсов для реальных объектов характеризуются, как правило, отсутствием "точных" характеристик, описывающих функционирование систем. В работах [1,2] предпринята попытка адаптации математической модели к реальным объектам с помощью введения интервальных временных характеристик. В данной работе проблема "неточности" исходных параметров решается с помощью введения "нечеткости". Рассматривается задача составления расписаний выполнения работ в достаточно общей постановке для многостадийных производственных систем при произвольных технологических маршрутах и альтернативных вариантах выполнения работ на машинах. Оценка качества расписаний как и в [3,4] определяется тремя основными составляющим: затратами на выполнение работ на машинах, затратами на переналадки машин и штрафными санкциями, налагаемыми на систему за нарушения заданных директивных сроков. Отличие рассматриваемых здесь задач от задач из [3,4] состоит, во-первых, в том, что в данной работе предполагается возможность выполнения работ в соответствии с произвольными технологическими маршрутами, и, во-вторых, временные и стоимостные характеристики работ в рассматриваемых моделях могут задаваться нечеткими числами, а тем самым в математических моделях могут присутствовать нечеткие операторы и операции с нечеткими числами. В результате решения задачи строится «нечеткое расписание», определяемое «нечеткими» моментами начала и окончания выполнения работ на машинах. Стоит заметить, что нечеткое расписание является некоторым обобщением обычного, «четкого» расписания, которое можно представить как частный случай «нечеткого».
2. Общая математическая модель («четкий случай»).
2.1.Исходные параметры модели.
Пусть J - множество работ, I - множество машин, K - множество стадий, объединяющих однотипные машины. Работе j поставим в соответствие набор fi = j,r2jrj ), Гдеr/ - номер стадии, на которой должна выполняться l-тая
операция работы j, r/ e K, l = 1, kj, jeJ. Здесь под операцией понимается процесс выполнения работы на машине какой-либо стадии. Обозначим через tifl - время выполнения l -ой операции работы j (на стадии rlj) на машине , cijl - затраты за единицу времени выполнения работы j на машине i стадии l, tisj - время переналадки машины с работы s на работу j, r jl - время наладки машины i на l -тую операцию работы j, disj - затраты за единицу времени переналадки машины i с работы s на работу j, Dj - директивный срок завершения последней операции работы j, gj -коэффициент, определяющий штрафные санкции, связанные с нарушением работой j
определенного для этой работы директивного срока, iel, l = 1, kj , je J, se J. 2.2.Варьируемые параметры модели.
Обозначим через X={ xijl, iel, l = 1, kj je J }, где xijl - момент начала выполнения операции l работы j на машине i; Y={yijl, iel, l = 1, k, jeJ}, где
ijl
1, если операция l работы j выполняется на машине 0, в противном случае,
Z={ ztjl, iel, l = 1, kj jeJ}, где ztjl - номер по порядку выполнения l -ой операции j -ой
z
работы на i-ой машине, ztjl e {0,1,...,N }, N = kj, iel, l = 1,kj jeJ.
jej
2.3. Ограничения математической модели:
(Каждая операция любой работы выполняется на одной машине)
Если yijl =1 и ysjl-1 =1 ,то xn ~ -1 + tsn-1, l = 2, kj, i e 1, s e 1, j e j. (2)
(Начало любой операции может наступить лишь после завершения всех операций, ей предшествующих по технологии)
i,
Если У jfl = 1 У vs = 1 zj = zivs + 1тоxj > xivs + tj + tvj ,
i e I, s = 1, kv, / = 1, k}, v e J, 7 e J.(3)
(Начало выполнения любой работы на машине может начаться лишьпосле завершения выполнения на этой машине предыдущей работы).
x,fl > r,fl, если z,fl = 1, ie I, / = 1 kj , j e J.(4)
(Момент начала выполнения самой первой для машины операцииможет наступить лишь после наладки машины на эту работу)
xifl > 0, yifl e {0,1}, zifl e {0,1,..., N}, ieI, / = Uj , jeJ.(5) (Естественные условия на введенные переменные).
3. Формализация критериев оптимальности
В качестве частных критериев оптимальности выберем следующие три группы:
•группу частных критериев, связанных с директивными сроками выполнения
работ:
f17 (Х, Y, Z) = g max(0,+ t - D}. ) - min , где /0 = k7 , a = 1,(6)
*- 0
-штрафные санкции, связанные с нарушением директивного срока, определенного для
работы j, je J;
•группу частных критериев, связанных с затратами на переналадки машин: F2; (X,Y,Z) =Vy* - min(7)
-суммарные затраты, связанные с переналадками машины с номером i, ie I;
•группу частных критериев, связанных с затратами на выполнение на машинах всех операций работы с номером j, je J:
F3j.(X, Y,Z) = Хл - min .(8)
iei /=1
-суммарные затраты, связанные с выполнением всех операций по работе с номером
j, je J.
В качестве свертки частных критериев оптимальности выберем аддитивную свертку как внутри групп частных критериев, так и между группами:
f =I f1 j + I F2i + IF3 j •(9)
jeJieijej
Полученная задача построения расписаний выполнения работ в многостадийных системах включает в себя исходные параметры, варьируемые параметры, ограничения (1 )-(5) и обобщенный критерий (9), который можно интерпретировать как суммарные затраты на выполнение работ. Эта задача является задачей математического программирования с существенно нелинейными ограничениями, нелинейным критерием и частично целочисленными неизвестными. В рамках построенной модели могут быть поставлены такие известные задачи, как задача коммивояжера (учет только переналадок на одной машине), множественного коммивояжера (учет переналадок на нескольких машинах), задача о ранце (не учитывается порядок обработки деталей при заданных директивных сроках) и др.
содержание:
[стр.Введение] [стр.1] [стр.2]