Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[30]

Пример 7.1. Пусть для частных алгоритмов 2ti, 21т, входящих в ЛСА Я = i2 2Ii Т1 ив л Т2 2Гз 1s 21, ЭДв Т311212 wi л,

заданы следующие времена кх выполнения ti, н стоимости с, .в условных единицах:

«7

2 - 40

, = 40,

4= 30,

5= 50, 5 = 40, ,= 100,

с - 3: С2 = 4 ; с8=5 ; с4 = 10 ; с6 = 10; <?в = 15 ; с, = 20.

Кроме того, известна следующая матрица переходных вероятностей:

ati

2ta

at3

at4 ar5

ate at,

1/3

2/3

ai2

i

ai3

l

ai*

3/5

2/5

ats

1

ate

1/4

3/4

Я;

1

Для построения вектора а выпишем следующую систему уравнений: а» + (3/5) а4 = а1; (1/3) fli+(l/4)ae==a2; (2/5)a< = aa;

<*а - а4; (2/3)а1 = ац о7 =з а6;

о,+ (3/4) ав = а7; I Я1 + в2 + а8 + в4 + а5 + ав + а7 = 1.

После решения этой системы получим ai=3/16; й2=9/80; йз=1/20; а*=1/8; as=°-1/8; аб=1/5; в7=1/5. Приравняем Д2=1. Тогда после пересчета по формуле a,=ai/a2 получим: a\=W; а-, = \; аз=4/9; а\=10/9: а5=10/9; as=l6i9: д7=16/9.

7

В соответствии с (7.3) получим ГСР= 2 aV«=449 с. Пусть ГДОп=300 с. Тогда В = 7"еР-7,дОП=149 с. Следовательно, в соответствии с (7.5) необходимо

7

иметь 2btXj>-\49 с, где Xj={Q; 1}.

Найдем допустимые подмножества частных алгоритмов, считая, что <<==«=2 с и конечный частный алгоритм 21» должен выполняться в ЦУУ. Кроме того, примем /.А,, ==<i.

Рассмотрим вначале подмножества, включающие по одному частному алгоритму (табл. 7.4) *, при этом значение Ь< вычисляем по формуле (7.4).

Здесь и далее в таблицах вместо 2t< указан номер t.

Из табл. 7.4 видно, что выполнение только одного частного алгоритма в афб позволит создать ММУС с аданной производительностью. Поэтому принимаем R1= {St7}. Очевидно, R1 является минимально допустимым подмножеством.

Таблица 7.4

аг,-

1

3

4

5

6

7

30

3,5

31,1

66,7

65,3

174,2

2с,

3

5

10

10

15

20

Найдем другие допустимые подмножества. Однако прежде чем начать их поиск, найдем покрываемые подмножества. Для этого вычислим вначале удельные нагрузки на афб{, t=l, 3, 4, 5, 6, 7, по формуле


Примем tai = tl. Тогда:

#,= (2 + 40) 4/9=18,7; Vl = (2 + 20) 5/3 = 36,7 ; 05 = (2 + 50) 10/9 = 57,8 #4 = (2 + 30) 10/9 = 35,6; = (2+100) 16/9= 181,3 i/6 = (2 + 40) 16/9 = 74,7.

егк видеть, что условие (7.6) выполняется только для двух подмножеств [St5] и {St6}, причем подмножество {Sts} покрывает подмножество {2tt}. Следовательно, подмножество {St6} из дальнейшего рассмотрения исключается.

Рассмотрим теперь подмножества из двух частных алгоритмов, за исключением тех, в которые входит St6 (в табл. 7.5).

Таблица 7.5 I

{1,3}

{1,4}

{1,5}

{1,7}

{3,4}

{3,5}

{3,7}

{4,5}

{4,7}

{5,7}

33,5

61,1

96,7

204,2

34,6

70,2

177,7

97,8

205,3

240,9

2с,

8

13

13

23

15

15

25

20

30

30

Из табл. 7.5 с учетом удельных нагрузок видно, что отсутствуют покрываемые подмножества. При этом выявились следующие допустимые подмножества: Л2={211, 217}; л3={Яз, Я7}; /?4={2t4, 2t7}; л5={315, 2Iz}.

Рассмотрим теперь подмножества из трех частных алгоритмов (табл. 7.6). Из табл. 7.6 видно, что имеются следующие допустимые подмножества: R6={St1, St44, St7}; R7={St1, St5, St7}; R8={St1, St4, St7}; R9={St3, St4, St7}; R10= {St4, St5, St7}. При этом нет покрываемых подмножеств.

Таблица 7.6 I

{21/}

{1,3,4}

{1,3,5}

{1,3,7}

{1,4,7}

{1,5,7}

{3,4,5}

{3,4,7}

{3,5,7}

{1,4,5}

{1,3, 4,6}

{4,5,7}

64,6

100,2

207,7

235,3

270,9

101,3

209,8

244,4

127,8

129,9

272,0

2С[

18

18

28

33

33

25

35

35

23

33

40

Ш

{1,3,4,5}

{1,3,4,7}

{1,3,5,7}

{1,4,5,7}

{3,4,5,7} {1,3,4,5,7}

131,3

238,4

274,4

302,0

275,5

305,5

2ct

28

38

38

43

45

48

ИЧ ЛйпЛ7ГтЧН° полУчаем и остальные допустимые подмножества (табл. 7.7)

ш таол находим следующие допустимые подмножества:

*i. = {3ti. «„И., 5ГТ}; /?и={Я1, 2Г3, 2Г6, %] ; 14={2Г1,2Г4,2Г6,2Г7};

#15 = {2г3, ЗГ4, 5г5, 21,} и я1в= {«а,, я,, si.,. щ5. 31,}.

Таким образом, на первом этапе получено множество всевозможных несравнимых допустимых подмножеств, удовлетворяющих у ел с/вию (/,о),

дгьл6л выполнены в АФБ» состоит из времени активизации афь-?л. и времени выполнения 2t,-лл .

Однако при наличию конечного числа АФБ, для заданной нагрузки у, может оказаться, что в момент,

когда необходимо включить АФБ„ не найдется ни одного свободного АФБ,. Тогда ЦУУ поставит

заявку в очередь на включение АФБ, после его освобождения. В связи с этим фактическое выполнение

21, в АФБ, с учетом времени ожидания в очереди л, составит /„, +1 л +tA,.

Легко видеть, что удельная .нагрузка на группу АФБ, при однократном выполнении объединенного

алгоритма функционироваяия yi- (лал+лАфБ, )а,, а общая нагрузка при N одновременно. выполняемых

технологических процессов У,=г/,л.

На втором этапе проектирования структуры ММУС для каждого допустимого подмножества

частных алгоритмов из полученного на первом этапе подмножества несравнимых допустимых

подмножеств частных алгоритмов определяется число АФБ в каждой группе.

Примем, что включение однотипных АФБ в каждой группе полнодоступное, а поступающий поток заявок на включение АФБ оудем считать простейщим. Тогда необходимое число АФБ, в, группе для удовлетворения необходимого качества обслуживания заявок, выражающееся в выполнении условия *ож1 л 7ож.дои.,ч(7.7)

где toxf- среднее время ожидания в очереди к АФБ„ может быть получено методами теории массового


обслуживания [25]. В алл лУЛе общее время выполнения Я. при его реализации вАФЬс состоит из времени, затрачиваемого ЦУУ на включение АФЬ, и принятие от него сигнала прерывания, tiAta, времени ожидания в очереди на занятие АФБ, /ож, и времени выполнения St. в АФБ, л , т. е. лАФБ, = л + лож; + лАФБ,-

Следовательно, с учетом того, что при организации АФБ из т частных алгоритмов функционирования / частных алгоритмов ЭДц, 21л выполняется в АФБ, а остальные 2л, л-лл- непосредственно в ЦУУ, среднее время однократного выполнения алгоритма 21 вместо (7.3) определяется выражением

Тлр = л ал лов + "л а\ t,y(7.8).

Получение наиболее экономичного варианта структуры ММУС, соответствующего каждому допустимому подмножеству частных алгоритмов Ri, выполняется независимо от других допустимых подмножеств. Затем результаты, соответствующие всем допустимым подмножествам, сравниваются друг с другом. Принят будет тот вариант структуры, которому соответствует наименьшая суммарная стоимость АФБ.

Получение наиболее экономичного варианта структуры ММУС, «соответствующего одному лis{J?g}, сводится к решению следующей задачи.

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

S "§ Лож tg (-Aig) л лож.доп-(7.9)

и обращают в минимум линейную функцию

<с=ллл

S=i

где tox.ic(xit) -время ожидания в очереди к АФБл при их числе, равном х,. ; лож.доп-допустимое время ожидания в очередях ко всем АФБ в процессе выполнения объединенного алгоритма 21, а значит, и любого из 2ts{2t1, St-л}.

Время /ож.доп должно быть, очевидно, таким, чтобы лрлТдо„. .(7.10)

Решение этой задачи, полученное для подмножества Ri алгоритма 21, назовем оптимальным решением для л? Среди оптимальных решений для всех подмножеств Rii={RA} найдем такое, для которого при удовлетворении условия (7.10) требуются наименьшие затраты на организацию АФБ. Это решение будем называть оптимальным для алгоритма 21. Структуру ММУС, соответствующую оптимальному решению для алгоритма 2t, будем называть оптимальной.

Пример 7.2. Для рассматриваемого примера на первом этапе (см. пример 7.1) получено 16 допустимых несравнимых решений. Найдем вначале оптимальное решение для R;. При этом допустимое время ожидания

лж.доп<2б,-5„.(7.11)

Таким образом, для л время /ож.доп 1=174,2-149=25,2 с. По номограммам для систем массового обслуживания с ожиданием и экспоненциальным распределением времени обслуживания найдем время ожидания при заданной нагрузке на группы АФБ (см. приложение 3) и различном числе АФБ в группе. При Л/=10 получим

v », 181,3

К = л=зб-10=°5Эрл-

Тогда при числе АФБт 1/7=4 задержка tow 7 (4) =21.. с. В этом случае стоимость группы АФБт для /?i

1

равна Сд =20-4=80.

Рассмотрим теперь допустимое подмножество Rs=[Sii, Sir}. Для Rs имеем foHs.soa 2=204,2- 149=55,2 с, которое должно быть больше или равно времени ожидания в очереди как к афб!, так и к АФБ/.

Поскольку в подмножестве Rs содержатся два частных алгоритма, для получения оптимального решения воспользуемся алгоритмом дискретного программирования. Для этого составим табл. 7.8, в которой п<-число блоков АФБ<, которые добавляются к основному для уменьшения времени ожидания, а в клетках указаны величины, характеризующие уменьшения времени ожидания при введении очередного (п+1}-го блока для Yi=0,t2 Э.рл и Ут=0,5 Эрл. В данном случае для одного афб) <ож.(1)=11 с и для АФБг <ож.7(1) =93 с, т. е. общее время ожидания fox i, 7(1,1) =104 с, тогда как допустимое время ожидания /ож.доп 2=55,2 с. Таким образом, недостает <„ж i, 7(1,1)-<ож.доп2=104-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36]