Доповнення алгоритму та програмування

Потрібно доробити алгоритм для РОЗПОДІЛУ ЗАВДАНЬ ПО

ПАРАЛЕЛЬНИХ ПРИЛАДАХ З ДИРЕКТИВНИМ ТЕРМІНОМ та запрограмувати його на мові C# + js

Алгоритм послідовного аналізу варіантів.

1.  Ініціалізація:

-    Вказати кількість завдань (n); кількість пристроїв (m); тривалість завдань (ti); директивний термін (d); технологічний порядок слідування виконання для підмножини завдань, якщо потрібно.

-    Створити пустий список для зберігання оптимального розкладу.

-    Встановити матрицю залежностей між завданнями (Pij), при наявності технологічного порядку.

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

-    Порівняти нижню оцінку для мінімального можливого часу отриману на основі загального часу виконання завдань та заданої кількості машин з директивним терміном.

2.  Створення розкладу (методом перебору з урахуванням послідовності виконання завдань визначити найоптимальніший графік їх виконання):

    a. Для кожного завдання:

-    Обчислити константу, що відповідає зайнятості, кожного пристрою (спочатку заповнювати всі пристрої з 0 потім з 1 і так далі).

-    Вибрати пристрій із найменшою константою (знаходити пристрій з найменшим часом завершення з огляду на залежність від попередніх завдань та тимчасові обмеження).

-    Перевірити, чи вибраний пристрій може виконати завдання у зазначеній послідовності (якщо послідовність задана).

-    Додати завдання до розкладу на вибраний пристрій та оновити час завершення пристрою.

-    Оновити константу для вибраного пристрою.

b. Повторювати крок 2a, поки всі завдання не будуть додані до розкладу.

3.  Перевірка директивних термінів:

-    Якщо розклад отримано з модуля 3 і отримано прийнятне значення цільової функції, то переходимо на п. 4.

-    Якщо розклад задовольняє директивним термінам, то кінець, розклад побудовано. Порушень немає, значення цільової функції дорівнює 0. Перейти на п. 4 пункт.

-    Для кожного пристрою знайти час порушення директивного терміну, тобто значення дельтаі (трикутник) = Ti - d, i = 1, m (зверху риска), де Ti – час завершення роботи і-го пристрою.

-    Визначити значення, що відповідає максимальному порушенню директивного терміну, тобто константу дельта (трикутник) = max дельтаі (трикутник).

-    Алгоритм покращення поточного допустимого розв’язку задачі. На цей алгоритм ми попадаємо, коли є порушення директивного терміну. ПЕРЕДАЄМО ДАНІ В ТОЙ МОДУЛЬ ПРОГРАМИ (МОДУЛЬ 3), ЯКИЙ БУДУЄ РОЗКЛАД, ЩО ПОКРАЩУЄ ЗНАЧЕННЯ ЦІЛЬОВОЇ ФУНКЦІЇ, ТОБТО ЗМЕНШУЄ (ЯКЩО ЦЕ МОЖЛИВО) МАКСИМАЛЬНИЙ ЧАС ВІДХИЛЕННЯ ВІД ДИРЕКТИВНОГО ТЕРМІНУ.

ОТРИМАНИЙ РЕЗУЛЬТАТ (ТОБТО РОЗКЛАД) ЦЬОГО МОДУЛЮ ПЕРЕДАЄМО НА П. 3.

4.  Вивід результатів:

-    Вивести отриманий графік виконання завдань, що відповідає поставленій задачі.

5.  Завершення.