виконання програмного модуля в j-му варіанті;
- Процесор D i (за умовою задачі N) ставиться у відповідність складу М j;
Наявність цих відповідностей і дозволяє звести на концептуальному рівні вирішувати завдання до мінімаксної завданню оптимального розподілу програмних модулів між процесорами і застосувати для її вирішення алгоритми, розроблені для даної задачі.
1.3 Математична постановка задачі
Розглянемо математичну постановку мінімаксної задачі оптимального розподілу програмних модулів між процесорами. Для цього введемо змінні:
У поставленому завданню необхідно провести разрузочно-навантажувальні роботи на N - складах, час виконання всіх робіт - t ij (N), де N - кількість працівників.
У ході вирішення завдання зводиться до формування чисельності бригад, які проведуть всі роботи за мінімальну кількість часу. Рішення проводиться відповідно до алгоритмом прямий прогонки. Рівняння Беллмана буде виглядати наступним чином:
Рішення рівняння Беллмана дасть нам оптимальний розподіл чисельності працівників по бригадах і мінімальним витратам на виконання необхідних робіт.
2. Алгоритмізація вирішення задачі
2.1 Аналіз методів рішення задачі
Даний метод розв'язання задачі вирішується в m етапів, де m - кількість програмних модулів. Потім завдання вирішується відповідно до алгоритму зворотного прогону.
Ідея динамічного програмування, заснована на алгоритмі зворотного прогонки, полягає в тому, що в якості етапу, для якого на першому кроці знаходиться локальне оптимальне управління, розглядається останній етап прийняття рішень. Рішення, прийняті на цьому етапі не роблять впливу на подальший етап, оскільки цей етап є останнім. Однак при такому підході є невідомим стан, в якому буде знаходитися система перед початком виконання останнього етапу. Тому локальне оптимальне управління необхідно знайти для всіх можливих станів, у яких може перебувати система, перед виконанням останнього етапу. Після цього здійснюється перехід до оптимізації управління на передостанньому етапі. Оптимальне керування на цьому етапі перебуває з урахуванням того, що вже відомо оптимальне управління на останньому етапі. Таким чином, для кожного стану передостаннього етапу знаходиться локальне оптимальне управління. Така процедура повторюється для всіх наступних етапів: n - 2, n - 3, ..., i, ..., 2, аж до першого етапу, тобто, оптимальне рішення для першого етапу визначається з урахуванням раніше знайдених оптимальних рішень для подальших етапів.
2.2 Вибір і опис методу
Сучасне трактування методу динамічного програмування дозволяє знаходити оптимальне рішення не тільки для адитивних критеріїв, але й для мінімаксних.
В даному випадку для проектування інформаційної системи виділено безліч програмних модулів R={R 1,., R i,., R m}. Ці модулі є інформаційно-незалежними один від одного і можуть паралельно виконуватися на багатопроцесорної обчислювальної системі, яка містить D o процесорів.
Для кожного з програмних модулів визначені варіанти їх реалізації, які формально задаються змінної d ij, визначальною кількість процесорів, які можуть використовуватися для виконання R i -го програмного модуля в j-му варіанті. Необхідно розподілити наявні процесори по програмним модулям, щоб їх виконання було закінчено в найкоротший час, тобто слід зменшити відрізок часу, що починається з моменту початку виконання робіт і закінчується в момент виконання останнього модуля.
Враховуючи, що нам є відомим значення часу t (d ij (z)) виконання R i -го модуля в j (z) варіанті розподілу, то нехай T i (z) - час виконання i-го модуля в z-му варіанті - визначається наступним чином: T i (z)=t (d ij (z)).
Очевидно, що час закінчення реалізації всіх програмних модулів для z-го варіанта складе Т (z)=Ti (z).
Тоді з усього безлічі варіантів необхідно вибрати такий варіант, для якого T (l)=T (z)=Ti (z)=t (dij (z)).
Рівняння Беллмана для мінімаксної задачі при реалізації алгоритму прямої прогонки має наступний вигляд:
Wi (S)=max {wi (S, Ui), Wi - 1 (- 1 (S, Ui))},
де - 1 (S, Ui) - оператор, що задає номер стану, в якому перебувала система на попередньому (i - 1) етапі. Для розглянутої задачі рівняння Беллмана представляється як
Ti (D)=max {(t (dij), Ti - 1 (D-dij))}.
Інтерпретація основних компонент рівняння Беллмана:
- етапи - i=m, де m - кі...
