множество исполнителей B = {B1,, B j ,, Bn}; матрица затрат времени
T = tij ; αi – момент поступления в обслуживающую систему i-й работы (рис.).
Рис. Выполнение работ при их неодновременном поступлении
Рис. Выполнение работ при их неодновременном поступлении
k
v
Вариант 2: простой j-го прибора существует, т.к. момент поступления z-й
по порядку работы, имеющий номер
ik , больше момента окончания
предыдущей по порядку z–1-й работы, т.е. αi > T j (G z−1 ) (рис.)
k
v
Строки матрицы 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
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
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
(рис.).
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 − в случае отсутствия простоя прибора.
Полученные значения
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 +
⎨
⎜ ∑
Таким образом, определены нижние оценки для всех конкурирующих подмножеств.
Рис. Иерархия типов памяти
выполнялись ограничения на объемы для каждого из типов Очевидным является выполнение ограничения целостности
памяти. файлов:
каждый файл размещается только на одном уровне иерархии памяти.
Вводится переменная
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 .
Рис. Соответствие между транспортной задачей и задачей размещения
необходимые для выполнения rj
обращений к j-му файлу за период
функционирования, a Wj – объем j-го файла: cij = W ti .
rj
j
i=1 j=1
M
N
Этап 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
Рис. Преобразование транспортной таблицы
Vv = Vv −W1.
*
Для полученной
транспортной таблицы
находится
оптимальное
решение, и найденное значение
критерия транспортной
задачи
представляет собой вторую компоненту нижней оценки:
H (G1 ) = ∑ ∑ cij yij .
M |N
i=1 j=1
v
Таким образом, после выполнения второго этапа для каждого из конкурирующих подмножеств известна нижняя оценка и найдена соответствующая транспортная таблица, которая должна сохраняться для последующих преобразований.
было выбрано подмножество 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
уровня памяти. Дополнительные преобразования этой таблицы состоят в том, что вычеркивается второй столбец и корректируется значение
объема памяти для первого уровня: V1 = V1 −W2.
*
После этого решается транспортная задача и вычисляется значение
критерия: H (G1 ) =
M |N
v,1
i=1 j=1
c y .
ij ij
∑ ∑
Замечание. Перед вычислением нижних оценок для подмножеств вначале необходимо проверить допустимость соответствующего варианта распределения. В том случае, когда объем памяти уровня меньше, чем объем файлов, назначаемых на этот уровень, то, очевидно, такой вариант
и подмножества, переобозначение
отброшенные на
Производится
конкурирующих
подмножеств в виде G2 ,G2 , ,G2 .
1 2
ρ(2)
состоять только из одной составляющей T (G N ). В этом случае значение
v
критерия совпадает с нижней оценкой ξ (G N ).
v
Замечание. Для анализируемой задачи
существует
модифицированный вариант ветвления, когда в качестве конкурирующих рассматриваются только вновь образованные подмножества. Такая процедура повторяется до тех пор, пока не будет распределен последний файл, т.е. будут получены оценки для конечных подмножеств и среди них
выбрано подмножество с минимальной минимальное значение объявляется текущим анализируется необходимость ветвления
оценкой. рекордом. ранее
Полученное После этого отброшенных
Таблица 6.
Параметры ЗУ
Таблица 7.
Параметры файлов
Предварительный этап. На основе исходных данных формируется транспортная таблица, в которой столбцы упорядочены по убыванию величины rj W j . В частности, должен быть изменен порядок столбцов
для четвертого и пятого файлов (табл.8).
из решения транспортной задачи. Решение транспортной задачи для множества 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
1
Распределение для G1
1
G2 = 700, ξ G2
(
1 )
= 1276.
Для G1 первый файл распределен на устройство 3 (табл.14 и 15).
3
G3 = 1000, ξ G3
(
1 )
= 1576.
4
Таблица 16.
Таблица 17.
Транспортная таблица для G1
4
Распределение для G1
4
(
1 )
H G4 = 576, T
(
1 )
G4
= 1400, ξ G4
(
1 )
= 1976.
из числа
Этап 3.
выбирается
В качестве перспективного
конкурирующих
подмножество G1,
1
т.е. первый файл распределяется на
первое устройство. Производится переход на выполнение следующей
2
файл распределен на устройство 2 (табл.18 и 19).
Таблица 18.
Таблица 19.
Транспортная таблица для G2 Распределение для G2
2 2
(
2 )
H G2 = 294, T G2 = 804, ξ G2
(
2 )
(
2 )
= 1098.
Таблица 21.
Транспортная таблица для G2
3
Распределение для G2
3
(
2 )
H G3 = 294, T G3 = 1020, ξ G3
(
2 )
(
2 )
= 1314.
4
Таблица 22 Таблица 23
Транспортная таблица для G2 Распределение для G2
4 4
(
2 )
H G4 = 294, T G4
(
2 )
= 1038, ξ G4
(
2 )
= 1602.
Перспективным является подмножество G2, имеющее минимальную
2
Параметры ЗУ Параметры файлов
Где K1, K2, K3 – последние
цифры шифра зачетной книжки.
Построить
дерево
ветвлений.
Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:
Email: Нажмите что бы посмотреть