i> 1, j D 2, N (1)= d 2,1 + D 1, N (1) U 2= d 2, i ... D 2, ( i - 1) N (1) +1== d 2, i + D 1,1 D 2, ( i - 1) N (1) +2== d 2, i + D 1,2 ... D 2, ( i - 1) N (1) + j == d 2, i + D 1, j D 2, i? N (1) = d 2, i + D 1, N (1) < i align="justify"> U 2= d 2, N (2) ...... D 2, ( N (2) - 1) N (1) +1 == d 2, N (2) + D 1,1 D 2, ( N (2) - 1) N (1 ) +2== d 2, N (2) + D 1,2 ...... D 2, ( N (2)? N (1))== d 2, N (2) + D 1, N (1)
При складанні таблиці використовуються наступні правила і виконуються певні процедури:
кількість рядків дорівнює кількості різних значень управлінь U 2. У кожному рядку вказується відповідне значення: d 2,1,., D 2, j,., D 2, N (1);
кількість стовпців відповідає кількості станів на попередньому i=1 кроці, тобто в заголовку стовпців вказуються значення
D 1,1, D 1,2,., D 1, j,., D 1, N (1);
кожна клітина таблиці розбивається на 2 частини. У нижній частині записується сума значень, зазначених у заголовках відповідних стовпців і рядків. Ця сума визначає стан для другого етапу - кількість процесорів, що розподіляються на етапі. Неприпустимі значення викреслюються, і для них не визначаються значення верхній частині клітини;
проводиться заповнення верхньої частини кожної клітини, в якій вказується максимальне з таких двох значень: перше значення - час виконання другого модуля при реалізації управління U 2; друге значення - час виконання першого модуля на залишилися процесорах;
складається остаточний таблиця для другого етапу ухвалення рішення. Ця таблиця містить три стовпці: у першому стовпці вказуються унікальні значення станів для другого етапу (табл). У проміжній таблиці маються повторювані значення станів. такому випадку необхідно для стану D2,1 знайти клітини, що мають такі ж значення станів, і серед них вибрати клітку з мінімальним значенням T2 * (D2,1), тобто T2 (D2,1)=min {T2 * (D2,1)}. Оптимальне значення управління U2 для стану D2,1 вказується у другому стовпці остаточної таблиці, а в третьому стовпці записується умовне оптимальне час виконання перших двох програмних модулів R1 і R2 при наявності D2,1 процесорів - T2 (D2,1). Аналогічні дії виконуються для всіх інших з?? стоянь D2, s, s =, і критерію.
Остаточна таблиця для другого етапу
Стан D 2, i Управління U 2 Умовне оптимальний час T 2 ( D 2, i) D 2,1 U 2,1 T 2 ( D 2,1) D 2,2 U 2,2 T 2 ( D 2 , 2)... D 2, s U 2, s T 2 ( D 2, s )... D 2, z (2) U 2, z (2) T 2 ( D 2, z (2))
Етап 3 . Здійснюємо розподіл між R 1 -м, R 2 -м, R 3 -м програмними модулями поточної кількості процесорів D. Функціональне рівняння Беллмана для i=3 має наступний вигляд:
T 3 (D)=max (t (d 3, j), T 2 (Dd 3, j)).
Формуються елементи третього етапу, при їх формуванні використовуємо наступне співвідношення:
