Одноетапні задачі теорії розкладів у багаторівневій системі планування (стр. 2 )

Блок 3. Оптимізація послідовностей сімейств , . Вбудовування чергового завдання на більш ранню позицію, якщо є резерви та виконується:

.

У результаті виконання блока 3 отримуємо для кожного сімейства послідовності , . Для кожного сімейства визначаємо найбільш ефективний початок виконання .

У блоках 1-3 реалізується алгоритм МВЗ.

Блок 4. Побудова розкладу виконання сімейств . Впорядкування сімейств за неспаданням тривалостей їх виконання (послідовність ). Побудова послідовності . Розглянемо послідовність . Визначимо інтервали вставки для чергового сімейства з послідовності сімейств : ; . Якщо цей інтервал вільний, то сімейство займе вказані позиції. Інакше шукаємо для вставки сімейства новий інтервал, на якому максимально наближений до . У процесі побудови послідовності можливі ситуації, коли сімейство перетинається з іншим сімейством за виконанням. Розглянемо такі випадки:

1) . У цьому разі сімейство займе більш пізні позиції: ; . Якщо, в свою чергу, існує сімейство , для якого , сімейство переміщується на більш ранні позиції після , а сімейство вставляється після нього (рис. 1): ; ; .

Рис. 1. Перетин з кінцем

2) . У цьому разі сімейство зсувається на більш ранні позиції: ; . Якщо виявиться, що в результаті вставки сімейство перетинається з сімейством і виконується , то сімейство переміщується на більш пізні позиції, а сімейство вставляється перед ним (рис. 2): ; ; ; .

Рис. 2. Перетин з початком

Така процедура виконується до тих пір, поки сімейство не буде вставлено в послідовність . Якщо , тоді за алгоритмом розв’язання задачі МВЗ перевпорядковуємо завдання в межах сімейства.

Переходимо до наступного сімейства завдань послідовності . Якщо вставлені всі сімейства, послідовність побудовано. Якщо , і в межах сімейств оптимальні послідовності завдань, то − оптимальний розклад виконання завдань у випадку, коли дозволені простої обладнання. В іншому разі виконується блок 5.

Блок 5. Виконання попарних перестановок сусідніх сімейств, якщо значення функціоналу в результаті перестановки зменшується.

Алгоритм А2.

Блок 1. Встановити , , .

Блок 2. Для кожного сімейства в множині визначити послідовність всіх завдань у сімействі для і-ї позиції сімейства, починаючи з останньої позиції. Розв’язується задача МВЗ. Початок виконання сімейства k визначається як .

Блок 3. Визначити значення функціоналу для кожного сімейства і-ї позиції.

Блок 4. Обрати сімейство з мінімальним значенням функціоналу. Видалити з множини і перенести в множину .

Блок 5. Встановити . Якщо , то перейти на блок 6, інакше – на
блок 2.

Блок 6. Визначити послідовність завдань в останньому сімействі в , де , розв’язуючи алгоритм МВЗ, та помістити перед існуючими сімействами в .

Блок 7. Визначити значення всього функціоналу послідовності . Кінець алгоритму.

Алгоритм А3.

Блок 1. Побудова початкової послідовності. На множині без врахування налагоджень розв’язується задача МВЗ. Отримуємо послідовність .

Блок 2. У послідовності для завдань, щодо яких задані налагодження приладу, включаємо значення налагоджень. Отримуємо послідовність .

Блок 3. Локальний пошук кращого розв’язку. У послідовності знаходимо завдання j, виконання якого вимагає максимального часу налагодження приладу: , де завдання k займає позицію, що безпосередньо передує завданню j.

Блок 4. Знаходимо в завдання i, для яких . Організуємо список S цих завдань, упорядкований за неспаданням значень часу налагодження.

Блок 5. Будуємо нові поточні послідовності завдань. Завдання j з позиції за допомогою відповідного оператора переносимо на позицію , на якій налагодження для завдання j мінімальне. У зв’язку зі зміною послідовності змінюємо значення налагоджень: налагодження завдання j на новій позиції і налагодження завдання, що безпосередньо слідує за новою позицією завдання j. Перераховуємо тривалість виконання завдань і визначаємо значення функціоналу. Аналогічно будуємо наступну поточну послідовність, переставляючи в послідовності завдання j після наступного завдання зі списку S і виконуючи всі процедури, описані в блоці 5. Така побудова поточної послідовності виконується, поки не буде переглянутий весь список можливих позицій перестановки завдання j.

Блок 6. З усіх побудованих поточних послідовностей вибираємо послідовність із найменшим значенням функціоналу, позначимо її sR2. У цій послідовності завдання j позначається з метою виключення його з подальшого розгляду. Здійснюємо перехід на блок 1, розглядаючи в якості послідовність . У послідовності знаходимо непомічене завдання j, виконання якого вимагає максимального часу налагодження приладу, і виконуємо блоки 3–5. Якщо в черговій поточній послідовності відсутні непомічені завдання, що вимагають налагодження, то алгоритм закінчує роботу.

Алгоритм А4.

Побудова початкової послідовності проводиться аналогічно алгоритму А3.

В алгоритмі використовуються дві структури околу.

Окіл перестановок. Розглянемо окіл, що складається з перестановок двох завдань та : .

Нехай – послідовність, що отримана з поточної послідовності перестановкою завдань на позиціях та :

(1)

Окіл вставок. Розглянемо окіл, що складається з послідовних переносів завдань.

Для кожного завдання i, виконується послідовний перенос на подальші позиції . Нехай послідовність, яка отримана переносом завдання і після завдання , тобто:

(2)

Алгоритм локального пошуку включає дві процедури.

1. Розглянемо послідовність . Послідовно міняються місцями два чергові завдання, починаючи з першої позиції. Завдання на позиції 1 поступово міняється місцями з завданнями, що займають позиції 2, 3,…, . Нехай вже виконані перестановки для завдань на позиціях 1, 2,…,. Завдання на позиції i міняється з завданнями на позиціях i+1,i+2,…n. Нехай – послідовність, що отримана з поточної послідовності перестановкою завдань i та j, i, . У цій послідовності відкоригуємо значення налагоджень. Значення функціоналу часткової послідовності становить:

.

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

2. Розглядається послідовність з початку. Кожне чергове завдання i поступово вбудовується на позицію j в послідовності , .

Нехай розглядається завдання, яке займає позицію i. Поступово вбудовуємо його на позицію j, У поточній послідовності корегуємо тривалість налагоджень і визначаємо значення функціоналу часткової послідовності i,…,j. Якщо , використовується вираз:

.

Якщо : .

Якщо значення функціоналу не покращилося, повертаємо завдання на позицію i, інакше оновлюємо поточну послідовність. Процес продовжуємо, починаючи з позиції i+1.

Приклади застосування запропонованих методів, наведені в дисертації, ілюструють їх ефективність. Показано, як наявність простоїв приладу суттєво зменшує значення функціоналу.

У третьому розділі описані алгоритми А1-А4, наведено результати статистичного дослідження їх ефективності. Також розглянуто алгоритми розв’язання задач МСЗ та МВЗ, які є складовою алгоритмів А1-А4. Представлено концепцію моделювання для дослідження ефективності алгоритмів мінімізації сумарного випередження та запізнення. Наведено методику вибору значень параметрів вхідних задач і їх розмірностей, що ґрунтується на методиці проведення наукового дослідження для підтвердження результатів. Генерація завдань проходить за схемою, запропонованою Д. Фішером у 1976 році, що з тих пір традиційно використовується для перевірки різноманітних алгоритмів. Серед наукової спільноти домінує думка про універсальність такої схеми, а результати, що їх отримують на задачах, згенерованих з однаковими параметрами, вважаються такими, що отримані на однакових задачах.

Розглянуто структуру системи моделювання та дослідження ефективності алгоритмів А1–А4 (рис. 3), що розроблена на основі загальної концепції моделювання.

Рис.3. Структура системи моделювання

Середовище статистики, зокрема, дає змогу групувати отримані результати за досліджуваними параметрами і формує зведені статистичні дані щодо розв’язання певних класів задач. Отримані статистичні результати проведеного моделювання відображаються дослідникам через інтерфейс для проведення аналізу. Наведено деталізовану схему алгоритму, за яким проводилася генерація задач, їх розв’язання відповідним алгоритмом 1-МВЗН та збір статистики.

У роботі було проведено ряд досліджень для обґрунтування ефективності алгоритмів А1–А4. Ці дослідження включають визначення впливу фактору директивних строків і фактору запізнення для алгоритмів А1–А4, впливу розмірності задачі на її розв’язання алгоритмами.

У табл. 1-3 показано залежність середнього часу розв’язання від розмірності для найскладнішої комбінації параметрів I (; ) для алгоритмів А1−А4.

Таблиця 1

Залежність часу розв’язання від розмірності при ; (мс)

	2	4	8	10	2	4	8	10
Алгоритм А1	Алгоритм А2
5	9.5	19.0	39.2	49.9	20.0	81.3	327.5	513.8
10	24.9	49.9	102.1	128.3	51.3	207.5	840.0	1325.0
15	42.8	86.7	176.9	222.1	88.8	360.0	1462.5	2287.5
20	62.9	128.3	261.3	328.9	131.3	531.3	2162.5	3387.5
25	85.5	173.4	353.9	445.3	177.5	720.0	2925.0	4587.5
30	109.3	222.1	453.6	571.2	227.5	922.5	3750.0	5875.0
35	134.2	274.3	559.3	704.2	281.3	1138.8	4612.5	7250.0
40	161.5	328.9	670.9	844.3	336.3	1362.5	5537.5	8687.5
45	188.8	385.9	788.5	991.6	395.0	1603.3	6508.2	10201.1
50	218.5	445.3	909.6	1144.8	456.3	1852.2	7510.3	11776.0

Таблиця 2