3. Проверка замечания 2:
r( ) maxtj; 235 45 замечание выполняется.
j1,n
4.Формирование строк элементной матрицы.
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
Т1 |
x11 t1 |
x12 t2 |
x13 t3 |
x14 t4 |
x15 t5 |
x16 t6 |
Δt1 = r Σx1j×tj |
Т2 |
x21 t1 |
x22 t2 |
x23 t3 |
x24 t4 |
x25 t5 |
x26 t6 |
Δt2 = r Σx2j×tj |
Т3 |
x31 t1 |
x32 t2 |
x33 t3 |
x34 t4 |
x35 t5 |
x36 t6 |
Δt3 = r Σx3j×tj |
Т4 |
x41 t1 |
x42 t2 |
x43 t3 |
x44 t4 |
x45 t5 |
x46 t6 |
Δt4 = r Σx4j×tj |
Т5 |
x51 t1 |
x52 t2 |
x53 t3 |
x54 t4 |
x55 t5 |
x56 t6 |
Δt5 = r Σx5j×tj |
Т6 |
x61 t1 |
x52 t2 |
x63 t3 |
x64 t4 |
x65 t5 |
x66 t6 |
Δt6 = r Σx6j×tj |
Тm+1 |
хm+1 t1 |
xm+2 t2 |
xm+3 t3 |
xm+4 t4 |
xm+5 t5 |
xm+6 t6 |
Δtm+1 = r Σxm+1j×tj |
Фаза 1
1. Формирование первой строки.
x11t1 ≤ r ; 1 × 5 ≤ 235; 2 × 5 ≤ 235; …;
5 × 10 ≤ 235; 5 × 11 ≤ 235;
x11 ≤ ω1; 1<10; 2<10; …; 10 = 10; 11>10 условие (x11 ≤ ω1) не выполняется. Возвращение к предыдущему шагу.
Поскольку все элементы со временем t1 выбраны, берутся элементы со временем t2:
x12t2 ≤ 235 – 5 × 10; |
1 × 7 ≤ 185; |
2 × 7 ≤ 185; …; |
26 × 7 ≤ 185; 27 × 7 ≥ 185; |
|
|
x12 ≤ ω2; 1 < 33; |
2 < 33; …; |
26 < 33; 27 < 33 условие |
(x12t2 ≤ 235 5 × 10) не выполняется. Возвращение к предыдущему шагу.
2. Определение оставшегосяколичества элементов современемt2:
ω22 = ω2 – x12 = 33 – 26 = 7.
3. Определениевозможностипомещения элементов современемt3:
x13t3 ≤ 235 – (50 + 182); 1 × 10 > 235 – 232 условие (x13t3 ≤ 235 –
(50 + 182)) не выполняется. x13 = 25; 1 < 25.
15
Значит, помещать эти элементы в первую строку нельзя. Поскольку время выполнения оставшихся элементов возрастает, то их помещать также нельзя. В противном случае требуется проверка возможности помещения всех остальных элементов.
Таким образом, первая строка элементной матрицы имеет вид:
|
t1 |
t2 |
t3 |
t4 |
|
t5 |
t6 |
Δti |
|
|
|
|
|
|
|
|
|
|
|
Т1 |
10 |
26 |
0 |
0 |
|
0 |
0 |
Δt1= 235 232 = 3 |
|
|
4. Формирование второй строки. |
|
|
|
|
||||
|
Так как элементы со временем t1 |
все помещены в первую строку, |
|||||||
они не рассматриваются для помещения во вторую и все оставшиеся строки.
Размещаются все оставшиеся элементы со временем t2:
x22t2 ≤ 235; 1 × 7 ≤ 235; |
2 × 7 ≤ 235; …; 7 × 7 ≤ 235; 8 × 7 ≤ 235; |
x22 ≤ 7; 1 < 7; 2 < 7; …; |
7 = 7; 8 > 7 условие (x22 ≤ 7) не выпол- |
няется. Возвращение к предыдущему шагу. Все 7 элементов со временем t2 размещены в строке T2.
Размещение элементов со временем t3 во вторую строку:
x23t3 ≤ 235 – 49; |
1 × 10 ≤ 186; 2 × 10 ≤ 186; …; |
18 × 10 < 186; |
19 × 10 > 186; |
x23 ≤ 25; 1 < 25; 2 < 25; …; 18 < 25; 19 < 25 условие
(x23t3 ≤ 235 – 49) не выполняется. Возвращение к предыдущему шагу. Помещение элементов со временем t4 невозможно, так как
r (δ) – Σx2jtj < t4; 235 (49 + 180) = 6 < 15.
Вторая строка элементной матрицы имеет вид:
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
Т2 |
0 |
7 |
18 |
0 |
0 |
0 |
Δt2 = 235 229 = 6 |
5. Формирование третьей строки.
Определение оставшегося количества элементов со временем t3:
ω33 = ω3 x23 = 25 18 = 7.
Размещение оставшихся элементов со временем t3 в третью стро-
ку:
16
x33t3 ≤235; 1 ×10≤ 235; 2× 10≤235;…; 7× 10≤ 235;8× 10≤ 235;
|
x33 ≤ 7; |
1< 7; 2 < 7; …; |
7 = 7; |
8 > 7 условие (x33 ≤ 7) не вы- |
|||||||||
полняется. Возвращение к предыдущему шагу. |
|
|
|||||||||||
|
Размещение элементов со временем t4 в третью строку: |
||||||||||||
|
x34t4 ≤ 235 70; 1 × 15 ≤ 165; 2 × 15 ≤ 165; …; |
|
|
||||||||||
|
8 × 15 ≤ 165; 9 × 15 ≤ 165; |
|
|
|
|
|
|||||||
|
x34 ≤ 8; |
1< 8; 2< 8; …; |
8 = 8; |
9 > 8 условие (x34 ≤ 8) не вы- |
|||||||||
полняется. Возвращение к предыдущему шагу. |
|
|
|||||||||||
|
Размещение элементов со временем t5 в третью строку: |
||||||||||||
|
x35t5 ≤ 235 – (70+120); |
1 × 18 ≤ 45; 2 × 18 ≤ 45; …; 3 × 18 > 45; |
|||||||||||
|
x35 |
≤ 22; |
1 < 22; 2 < 22; …; |
3 < 22 условие (x35t5 ≤ 235 – |
|||||||||
(70+120)) не выполняется. Возвращение к предыдущему шагу. |
|||||||||||||
|
Третья строка элементной матрицы имеет вид: |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t1 |
|
t2 |
|
t3 |
t4 |
|
t5 |
|
t6 |
|
Δti |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Т3 |
0 |
|
0 |
|
7 |
8 |
|
2 |
|
0 |
|
Δt3 = 235 226 = 9 |
|
6. Формирование четвертой строки.
Определение оставшегося количества элементов t5:
ω45 = ω5 x35 = 22 2 = 20.
Размещение элементов со временем t5 в четвертую строку:
x45t5 ≤ 235; 1×18 ≤ 235; 2×18 ≤ 235; …; 13×18 < 235; 14×18 > 235;
x45 ≤ 20; 1 < 20; 2 < 20; …; 13 < 20; 14 < 20 условие (x45t5 ≤ 235)
не выполняется. Возвращение к предыдущему шагу.
Помещение элементов со временем t6 невозможно, так как
r(δ) –Σx4jtj < t6, т.е. 235 234 = 1 < 18.
Четвертая строка элементной матрицы имеет вид:
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
|
|
|
|
|
|
|
|
Т4 |
0 |
0 |
0 |
0 |
13 |
0 |
Δt4 = 235 234 = 1 |
|
|
|
|
|
|
|
|
7. Формирование пятой строки.
Определение оставшегося количества элементов со временем t5:
ω55 = ω5 (x35 x45) = 22 (2 + 13) = 7.
Размещение элементов со временем t5 в пятую строку:
17
x55t5 ≤ 235; 1 × 18≤ 235; 2 × 18 ≤ 235; …; 7 × 18 ≤ 235; 8 × 18 ≤ 235;
x55 ≤ 7; 1< 7; 2< 7; …; 7 = 7; 8 > 7 условие (x55 ≤ 7) не выполня-
ется. Возвращение к предыдущему шагу.
Размещение элементов со временем t6 в пятую строку:
x56t6 ≤ 235 – 126; 1 × 45 ≤ 109; 2 × 45 ≤ 109; 3 × 45 > 109;
x56 ≤ 8; 1 < 8; 2 < 8; 3 < 8 условие (x56t6 ≤ 235 – 126) не выпол-
няется. Возвращение к предыдущему шагу. Пятая строка элементной матрицы имеет вид:
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
|
|
|
|
|
|
|
|
Т5 |
0 |
0 |
0 |
0 |
7 |
2 |
Δt5=235 (126+90) =19 |
|
|
|
|
|
|
|
|
8. Формирование шестой строки.
Определение оставшегося количества элементов со временем t6:
ω66 = ω6 x56 = 8 2 = 6.
Размещение элементов со временем t6 в шестую строку:
x66t6 ≤ 235; 1 × 45 ≤ 235; 2 × 45 ≤ 235; …; 5 × 45 ≤ 235;
6 × 45 > 235;
x66 ≤ 6; 1 < 6; 2 < 6; …; 5 < 6; 6 = 6 условие (x66t6 ≤ 235) не вы-
полняется. Возвращение к предыдущему шагу. Шестая строка элементной матрицы имеет вид:
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
|
|
|
|
|
|
|
|
Т6 |
0 |
0 |
0 |
0 |
0 |
5 |
Δt6 = 235 225 = 10 |
9. Формирование (m + 1)-й строки.
Определение оставшегося количества элементов со временем t6 для формирования (m + 1)-й строки:
ωm+1,6 = ω6 (x56 +x66) = 8 (2 +5) = 1.
(m + 1)-я строка элементной матрицы имеет вид:
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
Тm+1 |
0 |
0 |
0 |
0 |
0 |
1 |
Δtm+1 = 45 |
18
10. Элементная матрица после фазы 1 имеет вид:
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
Δti |
|
|
|
|
|
|
|
|
Т1 |
10 |
26 |
0 |
0 |
0 |
0 |
3 |
Т2 |
0 |
7 |
18 |
0 |
0 |
0 |
6 |
|
|
|
|
|
|
|
|
Т3 |
0 |
0 |
7 |
8 |
2 |
0 |
9 |
|
|
|
|
|
|
|
|
Т4 |
0 |
0 |
0 |
0 |
13 |
0 |
1 |
Т5 |
0 |
0 |
0 |
0 |
7 |
2 |
19 |
Т6 |
0 |
0 |
0 |
0 |
0 |
5 |
10 |
|
|
|
|
|
|
|
|
Тm+1 |
0 |
0 |
0 |
0 |
0 |
1 |
45 |
Тm+2 |
10 |
33 |
25 |
8 |
22 |
8 |
|
(m + 2)-я строка является контрольной. Она показывает, все ли элементы распределены; сравнением контрольной суммы по столбцам и исходных данных можно в этом убедиться.
Поскольку в (m + 1)-й строке есть один элемент, это говорит о том, что на первой фазе задача не решена. Требуется применение фазы 2. Для этого необходимо проверить условие
m n
ti xm 1, j tj; 48>45 – условие выполняется.
i 1 |
j 1 |
Фаза 2
1. Выбираем две строки и два столбца, где i = 1, k = 6, j = 1, l = 6.
Правило выбора строк и столбцов в элементной матрице: вычисление элементов матрицы в фазе 2 производится исходя из полученных значений элементов предыдущей фазы.
Первым шагом является выбор двух ключевых строк. Ключевой будем называть строку, в которой ti > 0 или tk > 0.
Из множества (Δti) выбирается ti, отличное от нуля, которому соответствует определенная строка. Она имеет номер. Этот номер присваивается индексу i (i =1,m). Просмотр ti следует проводить, начиная с первой строки матрицы, т.е. i = 1.
19