2.2.3. Дослідження задачі оперативного планування

Організація оперативно-диспетчерського управління виробництвом ґрунтується на деталізації по виконавцях раніше розрахованого календарного плану випуску продукції в межах заданого планового інтервалу. Реалізація цієї функції здійснюється задачею оперативного планування, результатом якої є просторове та часове впорядкування комплексу запланованих робіт. Просторове упорядкування виражається у визначенні кожному виконавцю поопераційного плану робіт, а часове – встановлення черговості надходження або терміну виконання робіт.

У ГВС оперативний плановий інтервал, як правило, не перевищує зміни (доби), а виконавцем є технологічне устаткування.

Математичною формою подання задач даного класу є дискретна оптимізаційна модель, а методологією розв’язання – дискретне лінійне програмування (ДЛП) та імітаційні методи дослідження.

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

Формально задача подається наступним чином.

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

Виготовлення партії деталей кожного найменування заздалегідь визначене послідовністю проходження деталей через групи устаткування, яку називають технологічним маршрутом , де L_іj – технологічна операція, яка виконується і-ою за порядком виготовлення j-ої деталі; M_j – кількість операцій, які виконуються над j-ою деталлю.

У маршруті технологічні операції L_ij = (Q_іj , T_ij) мають такі характеристики:

Q_іj = k – номер групи устаткування, налагодженого на виконання операції L_іj;

T_іj – нормативна тривалість виконання операції L_іj.

Необхідно скласти розклад , який визначає моменти початку виконання операцій (моменти запуску партії деталей на одиницях устаткування) і задовольняє системі обмежень:

– умові виконання технологічної послідовності:

;

– умові виконання технологічних маршрутів;

– умові виконання операцій без перерв:

;

– умові виконання в кожний момент часу тільки однієї операції на одиниці устаткування:

,

де – момент закінчення виконання операції .

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

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

Найбільш поширеними типами критеріїв є:

1) отпимізація виробничого циклу – часу випуску заданого обсягу продукції як сумарної тривалості обробки всіх деталей:

;

;

,

де – сумарний час виконання операцій на k-ій одиниці устаткування;

– сумарний час простоїв k-ої одиниці устаткування;

– очікування j-ої деталі перед обробкою на і-ій операції;

2) оптимізація використання устаткування (фондовіддачі):

– максимізація завантаження устаткування, а саме:

мінімального – ;

загального – ,

де – коефіцієнт завантаження k-ої одиниці устаткування;

– мінімізація часу простою устаткування, а саме:

максимального сумарного – ;

максимального міжопераційного – ;

загального – ,

де – простій k-ої одиниці устаткування (k = Q_іj) перед виконанням операції L_іj;

– сумарний простій k-ої одиниці устаткування;

– мінімізація середнього міжопераційного простою устаткування, а саме:

максимального – ;

загального – ,

де N_k – кількість операцій, що виконується на k-ій одиниці устаткування, або кількість одиниць простою у випадку, якщо устаткування виконує однакову кількість операцій;

3) отпимізація незавершеного виробництва:

– мінімізація очікування деталей перед обробкою, а саме:

максимального міжопераційного – ;

максимального подетального – ;

загального – ;

– мінімізація середнього очікування деталей перед обробкою, а саме:

максимального –

;

;

загального –

,

де N_j – кількість одиниць часу очікування j-ої деталі перед обробкою (може застосовуватися у випадку, якщо M_j однакове для всіх деталей).

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

Часто в реальних виробничий умовах необхідно вирішувати задачу оперативного планування, враховуючи одночасно декілька критеріїв. Одним із засобів розв’язання багатокритеріальної задачі є створення компромісного критерію. Його створення передбачає наступне:

– для кожного локального критерію розв’язується задача оптимізації і обчислюється її екстремальне значення E_і^*;

– задаються вагові коефіцієнти пріоритету _і та визначаються рівняння відхилень кожного критерію від свого оптимального значення у кожному іншому випадку розв`язання задачі;

– будується вираз компромісного критерію з використанням адитивної функції або функції рівномірного відхилення ;

– розв’язується задача із застосуванням компромісного критерію або серед раніше знайдених рішень обирається те, яке оптимізує компромісний критерій.

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

Простій – це інтервал часу між завершенням виконання попередньої операції та початком наступної за розкладом роботи устаткування. Простої бувають доопераційні (час до початку виконання першої операції на обладнанні) та міжопераційні.

Очікування – це інтервал часу між завершенням виконання обробки деталі на попередній за технологічним маршрутом операції та початком виконання наступної операції.

Локальний резерв часу – це інтервал, на який можна збільшити тривалість операції, не змінюючи момент початку наступної за розкладом робіт операції.

Локальний резерв операції L_ij розраховується як мінімальне значення між простоєм устаткування k = Q_ij = Q_gh після виконання операції L_ij та часом очікування j-ої деталі перед обробкою на операції :

; ; ,

де – час очікування j-ої деталі перед обробкою на операції ;

– час простою k-го устаткування після виконання операції ;

– наступна після операція, що виконується на цьому обладнанні.

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

Основне призначення локального резерву полягає у використанні його в оперативно-диспетчерському управлінні з метою компенсування зовнішніх впливів на час виконання операцій.

Також резерви можуть бути використані для включення у розклад роботи додаткових робіт, що не порушують основну структуру розкладу, але підвищують завантаження устаткування.

Методи розв’язання задачі. Усі методи розв’язання задач цього типу умовно розбивають на наступні основні класи:

– аналітичні методи, які ґрунтуються на апараті дискретної оптимізації;

– імітаційні методи, які ґрунтуються на імітації роботи об’єкта планування та використання повного або часткового перебору варіантів запуску деталей в обробку;

– комбіновані аналітико-імітаційні методи.

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

Типовим представником таких задач, в яких відображаються найбільш поширені умови виробництва, є задача Джонсона “про два верстати”, що має оптимальний алгоритм розв’язання.

Виробнича ділянка складається з двох одиниць устаткування, яке обробляє вироби n типів за однаковим технологічним маршрутом, тобто деталі повинні послідовно пройти через усе устаткування. Необхідно визначити черговість запуску-випуску виробів за критерієм мінімізації виробничого циклу (загального часу) виготовлення усіх виробів.

Очевидно, що для отримання оптимального рішення потрібно мінімізувати сумарний час простою другого устаткування в очікуванні завершення обробки деталей на першому. Принципом оптимальності черговості запуску за визначеним критерієм ефективності є min(T_1k, T_2l) < min(T_1l, T_2k), якщо деталь k йде раніше деталі l. За допомогою цієї нерівності формується наступний алгоритм оптимізації:

– всі деталі поділяються на дві групи. До першої належать деталі, в яких T_1k < T_2k, а до другої – деталі, в яких T_1k  T_2k;

– в першій групі деталі впорядковуються за зростанням часу T_1k, а в другій – за зменшенням часу T_2k;

– загальна черговість запуску деталей визначається як послідовність обробки деталей з першої групи, а потім з другої.

Аналогічний алгоритм може застосовуватися і у випадку трьох верстатів. В цьому випадку принцип оптимальності набуває вигляду:

min(T_1k + T_2k, T_3l + T_2l) < min(T_1l + T_2l, T_3k + T_2k),

якщо деталь k йде раніше на обробку деталі l, тобто, в першій групі (T_1k < T_3k) деталі впорядковуються за зростанням часу (T_1k + T_2k), а в другій (T_1k  T_3k) – за зменшенням часу (T_3k + T_2k).

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

Імітаційні методи. Для складних задач (різні технологічні маршрути обробки, кількість устаткування перевищує три тощо) з точки зору практичних цілей отримання результату за короткий термін найчастіше використовують евристичні алгоритми складання розкладів на базі вирішальних правил в режимі імітації роботи виробничої системи. У цьому режимі виконуються паралельна (одночасна) побудова діаграм Ганта для всіх одиниць технологічного устаткування, які беруть участь у процесі планування.

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

Алгоритм побудови розкладів за даним методом наступний:

0. Нехай у деякий момент часу верстат l = Q_іj закінчив обробку операції і поточної деталі j. Цей момент визначається як мінімальний серед усіх встановлених на поточний момент термінів завершення виконання операцій в графіку робіт.

1. Оброблена деталь j заноситься у портфель робіт наступного за технологічним маршрутом верстата l = Q_і+1 j.

Портфель робіт це підготовлені (у стані очікування) до виконання на верстаті операції обробки деталей.

Якщо є декілька варіантів технологічного маршруту, деталь одночасно заноситься у відповідну кількість портфелів. Якщо виконана операція була останньою за технологічним маршрутом (і = M_j), то деталь виключається з розгляду. Цей пункт повторно виконується для всіх верстатів, які на момент T завершили виконання операцій.

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

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

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

4. Обирається наступний верстат з мінімальним поточним значенням T та виконується перехід до п. 0. Планування ведеться до повного виконання усіх операцій над деталями або до тих пір, поки не буде побудований розклад на потрібний інтервал планування (зміну/добу).

За вирішальні правила в алгоритмах імітаційного моделювання найчастіше використовуються наступні правила переваги:

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

2) правило максимальної залишкової трудомісткості – з поточного портфелю робіт, які підготовлені до обробки, вибирається деталь з максимальною сумою часу обробки на усіх ще невиконаних операціях; мета правила – закінчити обробку всіх деталей приблизно одночасно;

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

4) правило мінімальної залишкової трудомісткості – альтернатива правилу 2;

5) правило найдовшої операції – альтернатива правилу 1;

6) правило призначення у порядку надходження (FІFO) – з поточного портфелю робіт вибирається деталь, яка надійшла в чергу на обробку до верстата першою;

7) правило LІFO – альтернатива правилу 6.

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

Приклад розрахунку розкладу роботи за правилом найкоротшої операції наведено на рис. 2.3.

Рис. 2.3. Розрахунок розкладу за правилом найкоротшої операції

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

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

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