Решение минимаксной обобщенной задачи о назначениях при неодновременном поступлении работ. (Лекция 4) презентация

{A1,, Ai ,, Am};
множество исполнителей B = {B1,, B j ,, Bn}; матрица затрат времени
T = tij ; αi – момент поступления в обслуживающую систему i-й работы (рис.).

Рис. Выполнение работ при их неодновременном поступлении

следующих принципов:
порядок выполнения работ на приборах должен обеспечивать уменьшение времени их простоя, т.е. в первую очередь должны быть
распределены работы, имеющие минимальное значение αi -е моментов
их поступления в систему;
при расчете загрузки прибора необходимо учитывать его простой, вызванный ожиданием поступления следующей работы.

z−1 ).

k

v

Вариант 2: простой j-го прибора существует, т.к. момент поступления z-й

по порядку работы, имеющий номер

ik , больше момента окончания

предыдущей по порядку z–1-й работы, т.е. αi > T j (G z−1 ) (рис.)

k

v

Все работы упорядочиваются в порядке возрастания моментов их поступления в обслуживающую систему, т.е. αi1 ≤  ≤ αiл ≤  ≤ αim.

Строки матрицы T = tij

Этап.1. Формируется

; также упорядочиваются: T = tik j

, k = 1, m.

множество всех возможных по исполнителям, и находится

вариантов

распределения работ
ξ (G0 ) = max (Δ1, Δ2 )

нижняя оценка

( ik )

⎜ i1

1 ik ik j

1

2

k =1 ⎠

Δ = 1 ⎛ α + m τ ⎞.

Δ : τ = min t

, Δ = max τ

+ α , k = 1, m;

ik

ik ⎟

j

n ⎝

∑

Этап 2. Распределяется первая работа, имеющая индекс i1 т.е. z = i1.
Шаг 2.1. Исходное множество делится на n непересекающихся подмножеств G1, ,G1,,G1 : (рис.).
1 v n

множеств N j (Gv ), j = 1, n;v = 1, n

1

N1 (G1 ) = {i1}, N1 (G1 ) = {0}, N1 (G1 ) = {0},

N j (G1 ) = {0}, N
1

(Gv ) = {i1}, N
1

(G1 ) = {0},

N (G1 ) = {0}, N

(G1 ) = {0}, N

n (G1 ) = {i }.
v 1

1 v v

n 1

j

j

v

n

v

Δ1, Δ2 , Δ3. Окончательно, ξ (G1 ) = max{Δ1, Δ2 , Δ3},

v

Δ1 = max (τi + αi ), k = 2, m; T j (G1 ) = ∑ (ti ik ∈ N j (G1 ),

j +αi ),

j1 jn jn

j2 3 2

⎝ s=1 k =2 ⎠

= 1 ⎛

T ≤ T ≤  ≤ T ; Δ = T ; Δ

n m ⎞
T + τ .

k k k

k

js

ik ⎟

v

v

n ⎜ ∑

∑

Таким образом, на этапе 2 для каждого из подмножеств определена нижняя оценка.
Этап 3. Конкурирующими являются подмножества, полученные на этапе 2, и в качестве перспективного выбирается подмножество, имеющее минимальную оценку. Предположим, что это подмножество –

1

Gv. В качестве второй по порядку рассматривается работа

i2. Она

назначается первому, второму, ..., v-му, ..., n-му исполнителям. В

результате образуются новые подмножества G1

, ,G1 ,,G1
v,v v,n

v,1

(рис.).

порядку работы. Эта работа имеет номер iz . Находятся множества

N1 (Gv,11 ),, N j (Gv,11 ),, Nn (Gv,11 ) для вершины Gv,1 :

z− z− z−

z−1

N1 (Gv,11 ) = N1 (Gv

1 ) iz .

z−

z−

Все остальные множества совпадают

с соответствующими

множествами вершины – родителя G z−1.

v

в качестве нижней оценки выбирается максимальная из них:

ξ (G1 ) = max (Δ , Δ , Δ ); Δ : τ

v,v 1 2 3 1 ik

, Δ = max (τ + α ), k = z +1, m.

1

= min t

ik j ik ik

j

Для Δ2

и Δ3 определяется занятость j-го прибора:

j ( v, 1 ) j ( v, 1 ).
v

i j , k

= ∑ b k

z− z−

v

T G

i ∈ N G

Введение переменной

bik j

предназначено для учета возможности

простоя j-го прибора:
bik j = tik j − в случае отсутствия простоя прибора.

j-го прибора.

Полученные значения

T j упорядочиваются

в возрастающей

последовательности: T j1 ≤ T j2 ≤  ≤ T jn . Окончательно

Δ3 = T ; Δ

2

r ⎝ s=1

k = z+1

⎞ ⎧n,
τ , r =

если z ≤ m − n, если z > m − n.

= 1 ⎛

⎩m − z,

n

s

k ⎠

r

m
∑

j

j

i ⎟

T +

⎨

⎜ ∑

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

оценкой.

Задана вычислительная система, содержащая М типов памяти, каждый из которых характеризуется значением объема и временными параметрами доступа к данным. Необходимо отметить, что лучшие временные характеристики имеют типы памяти, относящиеся к верхним уровням иерархии (рис.), в то же время эти типы памяти характеризуются меньшими объемами.

Рис. Иерархия типов памяти

значения объемов Vi , i = 1, M и времени доступа к данным ti , i = 1, M . В вычислительной системе необходимо хранить N информационных файлов/массивов для каждого из которых установлены следующие параметры: rj −активность j-
го файла; W j −объем j-го файла; j = 1, N. Под активностью rj понимается количество обращений к j-му файлу за период функционирования
системы. Необходимо распределить файлы по уровням памяти таким образом, чтобы суммарное время, затрачиваемое на доступ к ним за период функционирования системы, было бы минимальным и

выполнялись ограничения на объемы для каждого из типов Очевидным является выполнение ограничения целостности

памяти. файлов:

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

Вводится переменная

x j , j = 1, N ,

где x j = i −если

j-й файл

распределен на i-й уровень памяти.
Необходимо найти вектор решений x = {x1, x2 ,, x j ,, xN }.

всех

файлов на первый уровень иерархии памяти.
Критерий. Минимизация суммарных затрат на доступ к каждому из файлов за время функционирование системы.
Очевидно, что затраты на доступ к j-му файлу равны количеству обращений к нему за время функционирования системы, умноженному на время одного доступа, т.е. rj ⋅ ti .

Критерий представляется в виде:

j=1 i=1

⎧0, если

⎩1, если

a = 0;

a ≠ 0.

F = ∑ rj ∑ ti (1− δ(i − x j )) → min,

δ(a) = ⎨

N M

Ограничения. Суммарный объем всех файлов, размещаемых на i-м уровне, должен быть меньше либо равен объему памяти i-го уровня. Количество ограничений равно количеству уровней:

N
∑ W j (1− δ(i − x j )) ≤ Vi ,
j=1

i = 1, M .

расчете нижней оценки задача размещения файлов по уровням памяти представляется как транспортная задача с неправильным балансом. Существуют следующие соответствия между компонентами указанных задач: каждый из уровней памяти выступает в виде завода-изготовителя, а каждый файл соответствует заводу-потребителю; объем запасов завода- изготовителя равен объему памяти определенного уровня, а объем заявок завода-потребителя равен объему соответствующего файла (рис.).

Рис. Соответствие между транспортной задачей и задачей размещения

таблица.
Предварительный этап. На этом этапе по исходным данным формируется транспортная таблица следующего вида (табл.1). Строки
соответствуют уровням памяти, столбцы – файлам.
Элементы транспортной таблицы cij представляют временные затраты

на считывание единицы j-го файла с i-го уровня памяти за период функционирования системы. Тогда rj ⋅ ti .– суммарные затраты времени,

необходимые для выполнения rj

обращений к j-му файлу за период

функционирования, a Wj – объем j-го файла: cij = W ti .

rj

j

W j .

i=1 j=1

M

N

матрицы ciN +1 = 0, т.е. затраты на считывание фиктивного N+1-го файла равны нулю. Эти значения заносятся в дополнительный столбец. После этого выполняется следующая итерация.
Итерация 0

Этап 1. Формируется начальное множество

Go, представляющее

собой множество возможных вариантов размещения файлов по уровням памяти:
все массивы размещаются на первом уровне памяти x = 1, 1, ,1 ;
первый, второй, ..., N-1-й массивы размещаются на первом уровне памяти, N-й файл – на втором уровне памяти x = 1, 1, , 2 ;

все массивы размещаются на М-м уровне памяти x = M , M , , M .

нижней

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

отношения:

rj1 ≥ rj2

W j1 W j2 W jN

rj
≥  ≥ N , а строки – в порядке возрастания

значений времени считывания данных:

ti1 ≤ ti2 ≤  ≤ tiM .

Тогда

допустимое решение транспортной задачи, полученное методом северо- западного угла, является также и оптимальным решением. В том случае,

если упорядочивание столбцов и строк по

значениям rj W j и

ti не

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

при решении

M N
транспортной задачи, то ξ (Go ) = ∑ ∑ cij yij .
i=1 j=1
Этап 2. Производится распределение первого файла по различным

уровням памяти, т.е. исходное множество

G0 делится на М

непересекающихся подмножеств G1, ,G1,,G1 .
1 v M

)

ξ G1 = T G1 + H G1 ,

где T (G1 ) – компонента, учитывающая временные затраты на считывание

1

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

первый файл: T (G1 ) = r ⋅ t .

1 1 1

Компонента H (G1 ) находится из решения транспортной задачи. Для

1

этого вначале транспортной

выполняются необходимые преобразования для

G1. Эти

таблицы, соответствующие множеству

1

преобразования учитывают, что первый файл распределен и занята часть

объема памяти первого типа. Тогда соответствующей множеству

из транспортной

таблицы,

Go, вычеркивается первый столбец и

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

полученных при

операции

выполняются

для всех подмножеств, для произвольного

ветвлении.

В частности,

подмножества G1 : ξ Gv

v

(

1 )

(

1 )

(

1 )

, где T Gv = r ⋅ t .

= T Gv + H Gv

(

1 )

1 v

Рис. Преобразование транспортной таблицы

транспортной таблице, соответствующей множеству-родителю Go, вычеркивается первый столбец и корректируется значение объема памяти для v-го уровня, т.е. находится скорректированное значение Vv:

Vv = Vv −W1.

*

Для полученной

транспортной таблицы

находится

оптимальное

решение, и найденное значение

критерия транспортной

задачи

представляет собой вторую компоненту нижней оценки:

H (G1 ) = ∑ ∑ cij yij .

M |N

i=1 j=1

v

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

числа конкурирующих выбирается подмножество, имеющее минимальную нижнюю оценку, и производится переход к выполнению следующей итерации.
Итерация 1. На предыдущей итерации в качестве перспективного

было выбрано подмножество G1.

v

Этап 1. Производится распределение второго файла, т.е.

подмножество G1 делится на М непересекающихся подмножеств (рис.).

v

Подмножество G1 представляет собой все те варианты размещения

v,1

файлов по уровням памяти, в которых первый файл распределен на v-й уровень, а второй файл – на первый уровень памяти. Распределение других файлов по уровням памяти еще не произведено.
Для образованных подмножеств находится нижняя оценка. В

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

G1

v,1

:

( ) ( ) ( )

1

1

1

ξ Gv,1

= T Gv,1 + H Gv,1 ,

T (G1

) = r1 ⋅ tv + r2 ⋅ t1.

v,1

вычеркнут первый столбец, и скорректировано значение объема v -го

уровня памяти. Дополнительные преобразования этой таблицы состоят в том, что вычеркивается второй столбец и корректируется значение

объема памяти для первого уровня: V1 = V1 −W2.

*

После этого решается транспортная задача и вычисляется значение

критерия: H (G1 ) =

M |N

v,1

i=1 j=1

c y .

ij ij

∑ ∑

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

предыдущих этапах.

и подмножества, переобозначение

отброшенные на

Производится

конкурирующих

подмножеств в виде G2 ,G2 , ,G2 .

1 2

ρ(2)

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

состоять только из одной составляющей T (G N ). В этом случае значение

v

критерия совпадает с нижней оценкой ξ (G N ).

v

Замечание. Для анализируемой задачи

существует

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

выбрано подмножество с минимальной минимальное значение объявляется текущим анализируется необходимость ветвления

оценкой. рекордом. ранее

Полученное После этого отброшенных

по уровням памяти для следующих исходных данных: количество файлов N = 4; количество уровней памяти M= 5; параметры устройств памяти и файлов приведены в табл. 6 и 7.

Таблица 6.

Параметры ЗУ

Таблица 7.

Параметры файлов

Предварительный этап. На основе исходных данных формируется транспортная таблица, в которой столбцы упорядочены по убыванию величины rj W j . В частности, должен быть изменен порядок столбцов

для четвертого и пятого файлов (табл.8).

G0 представляет собой значение критерия, полученного

из решения транспортной задачи. Решение транспортной задачи для множества G0 представлено в табл. 9.

Таблица 8.
Транспортная таблица для G0

Таблица 9.
Распределение для G0

Значение критерия для транспортной задачи H (G0 )=1148, ξ (G0 ) = 1148.

варианты, в которых

2
первый файл распределен на второе устройство и т.д. Последовательно

находятся нижние оценки для сформированных подмножеств.

Для G1 :

1

(

1 )

(

1 )

( 1 ) (

ξ G1 = T G1 + H G1 ;T G1 = r ⋅ t = 100 ⋅ 3 = 300; H G1 −

1 )

1 1

(

1 )

значение критерия для транспортной таблицы, в которой исключен первый столбец и скорректировано значение для свободного объема памяти первого устройства (табл. 10). Решение транспортной задачи для

подмножества G1 приведено в табл. 11.

1

Значение критерия для транспортной задачи:

H (G1 ) = 848.

1

Окончательно, ξ (G1 ) = 1148. Аналогично находятся нижние оценки для

1

G1

1

Распределение для G1

1

)

G2 = 700, ξ G2

(

1 )

= 1276.

Для G1 первый файл распределен на устройство 3 (табл.14 и 15).

3

)

G3 = 1000, ξ G3

(

1 )

= 1576.

17).

4

Таблица 16.

Таблица 17.

Транспортная таблица для G1

4

Распределение для G1

4

(

1 )

H G4 = 576, T

(

1 )

G4

= 1400, ξ G4

(

1 )

= 1976.

из числа

Этап 3.

выбирается

В качестве перспективного

конкурирующих

подмножество G1,

1

т.е. первый файл распределяется на

первое устройство. Производится переход на выполнение следующей

второго файлов на устройстве 1. Для G2 второй

2

файл распределен на устройство 2 (табл.18 и 19).

Таблица 18.

Таблица 19.

Транспортная таблица для G2 Распределение для G2
2 2

(

2 )

H G2 = 294, T G2 = 804, ξ G2

(

2 )

(

2 )

= 1098.

20.

Таблица 21.

Транспортная таблица для G2

3

Распределение для G2

3

(

2 )

H G3 = 294, T G3 = 1020, ξ G3

(

2 )

(

2 )

= 1314.

23).

4

Таблица 22 Таблица 23

Транспортная таблица для G2 Распределение для G2

4 4

(

2 )

H G4 = 294, T G4

(

2 )

= 1038, ξ G4

(

2 )

= 1602.

Перспективным является подмножество G2, имеющее минимальную

2

распределения файлов по уровням памяти.
Оптимальное размещение определяется следующим набором переменных: x1 = 1, x2 = 2, x3 = 1, x4 = 2, x5 = 2.

Минимальное время доступа к массивам составляет 1212 единиц времени.

по уровням памяти для следующих исходных данных: количество файлов N = 6; количество уровней памяти M= 5; параметры устройств памяти и файлов приведены в таблицах.

Параметры ЗУ Параметры файлов

Где K1, K2, K3 – последние

цифры шифра зачетной книжки.

Построить

дерево

ветвлений.