Файл: Голенко Д.И. Статистические модели в управлении производством.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 155

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

^

= {(1,1),(2,1),(3,2)},

Л - { ( І Д ) , ( 3 , 2 ) , ( 1 , 3 ) } .

Из матриц Т' и П' вычеркиваем

множество

элементов

П ^і = {(1,1), (3,2)}, при этом

получаем

 

 

IXtf)

CI ,2)

(1,3)

 

SMTf

Г2.1.)

(3,1)

Г 1 =

(.2,1)

(2,3)

(2,2)

П

-User

(1,2)

(2,2)

 

ІЯ&Ї

(3,1)

(3,3)

 

(1,3)

(2,3)

(3,3)

На втором шаге по Ті

и Пі

формируем L 2 и F2

L2 ={(1,2),(2,1),(3,1)},

F 2 =

{(2,1),(1,2),(1,3)}-

Из матриц Т'\ и П'і вычеркиваем множество элемен­

тов L 2

П F2 = { 1 , 2), (2, 1)}, при этом получаем

 

VНа

 

U ^ T

 

(і,з)

 

U-гГТ

U r n

(3,1)

 

(2,3)

 

(2,2)

fT

Ut2)

X1t2^ (2,2)

І2&>

(3,1)

 

(3,3)

 

(1,3)

(2,3)

(3,3)

третьем шаге по Г'2 и П'г формируем L 3

и F 3

L 3 =

{(1,3),(2,3),(3,1)},

F 3 = {(3,1) (2,2) (1,3)}-

Из матриц Т'2 и ГГ2 вычеркиваем множество

элемен­

тов L 3

П F з = {(1,3),

(3,1)}, при этом получаем

 

 

І ^ П

Ш21

 

U?3fl

 

U-rf-т

t a r n

ІЗГГГ

 

І2гГТ

(2,3)

 

(2,2)

 

JUT2T Ur2T (2,2)

 

І Д Л

ХЗгГТ

 

(3,3)

 

ЦтЗУ

(2,3)

(3,3)

На

четвертом

шаге по Т'3 и ГУ3 формируем L 4 и F 4

 

L 4 =

{(2,3),(3,3)},

^ 4 = { ( 2 , 2 ) , ( 2 , 3 ) } .

 

Из

матриц Т'з

и П ' 3 вычеркиваем множество

элемен­

тов Ц П / 7 4 = : {(2,3)}, при этом получаем

 

 

 

(МП

SAtfl

 

U-r*7

 

i - W T

ІЛг&Г

Uri-T

 

 

ІЛгЗТ

(2,2)

" і "

І3г27

£-h27

(2,2)

 

ІЗ^Г

ІЖЇ

 

(3,3)

Д+ГЗТ

ІЛтЗГ

(3,3)

 

 

 

На тіятом шаге по Т\

и П'4 формируем L 5 и F 5

15=1(2,2),

(3,3)},

F 5 = { ( 2 , 2 ) , ( 3 , 3 ) } .

Из матриц Т\

и П/4 (вычеркиваем множество элемен­

тов L 5 П ^5== {(2,2), (3,3} и получаем матрицы Т'$ и ІГ5, у которых все элементы зачеркнуты, этим доказано,

что исходной матрице П соответствует

допустимое

рас­

писание.

 

 

 

 

 

 

 

Используя предложенный метод,

можно

построить

оценки

размерности области D расписаний общей

за­

дачи

календарного

планирования.

 

 

 

 

 

Если любая операция может быть

выполнена

на

од­

ном из

станков n{j

некоторого множества

Na,

то,

очевид­

но,

(J

Nij

cr N, где N — множество всех станков. Введем

Оц

 

~

 

 

 

 

 

 

множество

E = NnX...XN\mi

XN2\X...XN2m2X...XNniX

X...XNnm.n

 

как прямое произведение множеств Nij.

Лю­

бой

элемент е є £

представляет собой

упорядоченное

множество станков и определяет закрепление любой де-

талеоперации

за

конкретным

станком.

 

 

 

Если

каждое

из множеств

состоит

из единствен­

ного станка

пі},

т. е. операция Oj3- выполняется

только

на станке с номером п^,

то число всех вектор-перестано­

вок

к=

(jTi,...,Ttm)

равно

m

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R=

П

(flf c )!,

 

 

где

аи — число операций,

закрепленных за

k-ш станком.

Число R всех перестановок я с учетом всевозможных

закреплений

деталеопераций

за станками

равно

 

 

 

 

 

 

m

 

 

 

 

 

 

 

/?= 2

П

(S6« f t (e))!,

 

 

г д е

 

 

 

е е Е

ft=i

і,)

 

 

„

.

Г1, если операция Ojj выполняется на k-u

станке,

°ijfe(e) —|oj в противном случае.

 

 

Если на k-u станке может выполняться bhp операций детали Р, тогда оценка размерности задачи может быть получена по формуле

R= 2

П

•

spE

h=l

n

 

'

П bhP

 

 

2>=1

6. Д . И. Голенко

81

Если на любом станке может выполняться не более, чем одна операция по обработке каждой детали, то для за­ дачи п'Хт можно получить оценку размерности как част­ ный случай предыдущих формул:

R={n\)m

•

 

Естественно, что оценки

значительно

превосходят

число расписаний множества

D, так как

они получены

как число всевозможных порядков обработки деталей на каждом из станков или число всевозможных вектор-пе­ рестановок я.

Меру завышения полученных оценок можно опреде­ лить приближенно следующим образом. Согласно опи­ санному алгоритму, перестановке я соответствует допу­

стимое

расписание

А , если

процесс зачеркивания

эле­

ментов

в матрицах V и ІГ продолжается

до тех

пор,

пока не останется ни одного элемента.

 

 

 

Пусть на /г-м шаге зачеркивания элементов в матри­

цах Т

и П оставшееся число

 

деталеопераций

равно х,

число

элементов

множества

Lk равно m

и

число

эле­

ментов

множества

Fu равно

п.

Тогда вероятность

Ро(х):

того, что в множествах Lk и Fu не окажется общих эле­ ментов (деталеопераций), можно подсчитать по фор­ муле

{x-m)

\ (х—п)\

Р°(х>-'

'хцх-т-п)1

Вероятность р (s, т, п) того, что процесс зачеркива­ ния продолжается до конца, можно определить по фор­ муле

р (s,

т, гс) =

_Пs

/( 1

(х—т)

\ (х—п)\

 

 

т+п

\

х\

(х—т—п)\

п

и mi —число

всех

операций детали dt. Под-

где s = 2mi

i=i

 

 

(s, т,

п) можно рассматривать

считанную вероятность р

приближенно как

коэффициент, показывающий во сколь­

ко раз количество всех вектор-перестановок я некоторой задачи превосходит размерность области D действитель­

ных расписаний.

 

Для задачи

I I I величины 1 0 Х І 0 Х І 0

(10 деталей об­

рабатывается

на 10 станках, причем

число операций

любой детали

равно

10), величины R

и

 

вероятность

р (100, 10, 10)

соответственно равны

 

 

 

 

 

/?= (10!)1 0 ££ 1066

 

 

 

р loo, ю,

 

юо

/

і - -

(х—10)!

(х—10)!

\

^lo-e .

ю ) = п

 

—

L

 

 

 

х = 2 0 V

 

*!(*—20)!

 

/

 

Последняя

 

цифра

показывает,

насколько мала при

моделировании случайной вектор-перестановки вероят­ ность того, что ей соответствует допустимое расписание.

Как указывалось выше, для использования метода Монте-Карло при решении задачи календарного плани­ рования возникает проблема моделирования расписания, равномерно распределенного в области D. Можно пред­

ложить

алгоритм

моделирования такого

 

расписания,

включающий следующие

этапы:

 

 

 

 

 

1. Для каждой операции моделируем

номер

станка,

на котором эта операция может быть выполнена.

 

Sj

2. Для каждого станка / формируем

множество

операций, претендующих на обработку на

этом

станке.

3. Для каждого станка моделируем

перестановку

я;-

из элементов множества

Sj.

 

 

 

 

 

4. Составляем расписание, соответствующее вектор-

перестановке.

 

А,

 

 

 

 

 

 

5. Если расписания

соответствующего

я =

(яі,

Яг,

... ,я т ),

не существует,

то

переходим к

п. 1 и

повторяем

процедуру.

 

 

 

 

 

 

 

 

Существенным

недостатком предложенного алгорит­

ма является то, что для получения одного

расписания

А

необходимо выполнить большое число «холостых» опе­ раций.

Этот недостаток можно устранить, если в моменты од­ новременных простоев всех станков просматривать пос­ ледние в определенном порядке и для станка / в очеред­ ности Яг выбрать первую деталь, которая может загрузить этот станок. Эта процедура обеспечивает просматривание всего множества D, но, вообще говоря, не равномерно.

Часто целесообразно моделировать не на всем мно­ жестве D, а на некотором подмножестве DczD расписа­ ний, удовлетворяющих следующему дополнительному ог­ раничению: если станок свободен и имеется множество деталей, готовых к обработке на этом станке, то на ста­

нок запускается

одна из деталей этого множества.

9*

83

Этот процесс моделирования дает возможность по­ лучить «хорошее» расписание за гораздо меньшее чис­ ло испытаний, чем при моделировании -на всем множе­ стве D. Необходимо отметить, что оптимальное расписа­ ние в D может не попасть.

Построение расписания можно рассматривать как процесс разрешения конфликтных ситуаций.

Напомним, что

ситуация считается

конфликтной,

если в некоторый

момент времени на

освободившийся

станок претендует несколько деталей. Разрешение кон­ фликтной ситуации методом Монте-Карло достигается путем случайного отбора некоторой детали из числа «конкурентных». Множество D также может быть пред­ ставлено в виде множества путей некоторого дерева, которые соединяют исходную вершину с концевыми вершинами. Любая вершина представляет собой множе­ ство возможных решений о запуске одной из деталей на освободившийся станок.

Размер множества действительных планов сильно растет с ростом «площадей» задач; даже для задач ти­ па 10X10x4 (10 деталей обрабатывается на десяти станках, причем каждая деталь имеет не более четырех операций) полный перебор нереализуем на существую­ щих ЭВМ. ^

При использовании метода Монте-Карло,

основанного

на описанном выше

процессе

моделирования

случайного

расписания, имеет

место так

называемый «эффект

уси­

ления» [2. 5], который заключается в следующем.

Если

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

Смотрите также файлы