ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність дисертаційної роботи, сформульовано мету і задачі дослідження, наукову новизну і практичне значення одержаних результатів. Наведено дані про впровадження результатів роботи, їх апробацію, публікацїі та особистий внесок здобувача.

У першому розділі здійснено аналіз сучасного стану інформаційних технологій планування та управління в багаторівневих системах з мережевим представленням технологічних процесів та обмеженими ресурсами, а також сучасних методів розв'язання оптимізаційних задач планування в складних організаційно-виробничих системах.

Виробничі системи з мережевим представленням технологічних процесів та обмеженими ресурсами охоплюють близько 80% всіх типів виробництв. Сформульовано особливості, властиві для складних типів виробництв. Ці особливості обумовлюють важкість формалізації задач планування в багаторівневих виробничих системах з мережевою технологією та обмеженими ресурсами, необхідність створення ефективних методів їх розв’язання.

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

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

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

У другому розділі представлені нові ефективні методи розв’язання наступних задач мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН): у разі, коли простої обладнання дозволені; для випадку, коли простої обладнання заборонені; у разі, коли налагодження залежать від послідовності завдань.

Постановка задачі 1. Задача складання розкладів груп на одному приладі з часами налагодження сімейств може бути сформульована таким чином: задано число сімейств, позначене , і кількість завдань у кожному сімействі, представлена числом для сімейства , які необхідно виконати без переривання на одному приладі. Тривалість виконання і директивний строк -го завдання з сімейства визначені як і відповідно. Крім того, якщо завдання слідує за попереднім завданням з того ж сімейства, то між ними немає часу налагодження, інакше потрібен час налагодження сімейства перед наступним процесом виконання, причому не залежить від позиції, займаної сімейством. До того ж передбачається, що є налагодження до виконання першої роботи в будь-якій послідовності. Всі завдання доступні в момент часу нуль, простої приладу допускаються, а переривання завдань заборонено. Прилад виконує не більш ніж одне завдання одночасно, і не може виконувати жодного завдання, поки виконується його налагодження. Всі завдання в кожному сімействі мають бути призначені разом. Отже, у будь-якій допустимій послідовності повинно бути тільки налагоджень. Загальна кількість завдань . Ціль полягає в тому, щоб знайти розклад, який мінімізує сумарне випередження і запізнення всіх завдань: . Для розв’язання цієї задачі запропоновано нові методи, які реалізовані у вигляді алгоритмів А1, А2.

Постановка задачі 2. Множина з n незалежних завдань повинна бути призначена на виконання без переривань на одному приладі, який може працювати не більш ніж з одним завданням одночасно. Прилад та завдання передбачаються безупинно доступними з моменту часу нуль, а простої приладу не допускаються. Завдання j, де , вимагає часу виконання і в ідеалі повинно бути закінчене у свій директивний термін . Для окремих завдань задано час налагодження . Це означає, що в розкладі, в якому завдання j виконується відразу після завдання i, повинен бути час налагодження одиниць часу між моментами завершення завдання i, позначеним через , та часом початку завдання , що дорівнює . Упродовж періоду налагодження жодне інше завдання не може виконуватися приладом. Тривалості налагодження залежні від послідовності, тому що вони залежать як від , так і від . Ціль полягає в тому, щоб знайти розклад, який мінімізує сумарне випередження і запізнення всіх завдань: . Для розв’язання цієї задачі запропоновані нові методи, які реалізовані у вигляді алгоритмів А3, А4.

Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань одним приладом (МСЗ), мінімізації сумарного випередження та запізнення завдань (МВЗ) одним приладом, розроблених у науковій школі О.А. Павлова, та 1-МВЗН. В основу розроблених методів покладено метод розв'язання задачі МВЗ, який в свою чергу заснований на ПДС-алгоритмі розв’язання задачі МСЗ. В алгоритмах А1 і А2 використано можливість врахування налагоджень безпосередньо в структурі алгоритму МВЗ, що дало змогу розробити ефективні, близькі до оптимальних, методи розв’язання задачі 1-МВЗН. У алгоритмах А3, А4 методом розв’язання задачі МВЗ побудовано початкову послідовність. Це дало можливість статистично значимо при локальному пошуку кращого розв’язку в околі поточного розв’язку потрапити в область глобального оптимуму та отримати ефективні, близькі до оптимальних алгоритми розв’язання задачі 1-МВЗН.

Задача 1-МВЗН груп завдань для випадку, коли дозволені простої обладнання складається з двох підзадач :

1) знайти оптимальну послідовність завдань у межах кожного сімейства, в якій досягається оптимальне значення заданого критерію ефективності;

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

Ці підзадачі взаємно зв’язані. Оскільки від позиції, яку кожне сімейство займає в послідовності сімейств, залежить оптимальність послідовності у межах самого сімейства, стає важливим визначити для кожного сімейства найефективніший момент початку його виконання.