ОПТИМІЗАЦІЯ РОЗПОДІЛУ РЕСУРСІВ ПРИ КАЛЕНДАРНОМУ ПЛАНУВАННІ БАГАТОНОМЕНКЛАТУРНОГО ВИРОБНИЦТВА.
Розглянемо один з найскладніших варіантів постановки задачі календарного планування, а саме планування багатономенклатурного виробництва (індивідуальне виробництво в машинобудуванні, судоремонт, дослідно-конструкторське виробництво і т. п.). Процес виконання кожного замовлення представлений у вигляді сітьового графа, в якому кожна робота може виконуватися з використанням кількох видів ресурсів. Для визначеності розглядатимемо трудові ресурси — робочих різних спеціальностей.
Нехай на підприємстві виконується N (n = 1, 2 … N) замовлень різними підрозділами (цехами, бригадами). По l-му (l = 1, 2 … L) підрозділу відома чисельність спеціалістів 
р-ї (р = 1, 2 … Р) професії.
Представимо процес виконання робіт п-го замовлення у вигляді сітьового графа Gn{Mn, An}, де Mn — сукупність вузлів, а
An — множина дуг, що з’єднують вузли графа. Кожна дуга графа Gn є однією з робіт п-го замовлення.
Припустимо, що для виконання кожної роботи (і, j) сітьового графа комплектується група з різних спеціалістів у кожному підрозділі 
, де 
— кількість спеціалістів р-ї професії в l-му підрозділі, що входять до к-ї групи, для виконання роботи (і, j).
Склад групи вважатимемо оптимальним, якщо вона виконує роботу (і, j) за мінімальний час 
. Через 
позначимо директивний строк виконання п-го замовлення.
Визначимо календарний план як сукупність упорядкованих у часі чисел 
, де 
— відповідно момент початку та закінчення роботи (і, j).
Необхідно побудувати такий календарний план роботи підприємства, щоб усі замовлення були виконані не пізніше директивного строку і щоб ні в які моменти часу сумарна потреба у виконавцях не перевищувала їхньої наявної чисельності.
Оцінимо діяльність кожного спеціаліста певною кількістю балів bp. Тоді діяльність спеціалістів р-ї професії в l-му підрозділі
к-ї групи при виконанні роботи (і, j) визначається кількістю 
балів. Звідси діяльність кожної групи спеціалістів 
при виконанні роботи (і, j) можна оцінити сумарною кількістю балів
, (1)
причому для оптимального складу групи ця оцінка є найбільшою
. (2)
Логічно припустити існування і найменшої оцінки 
.
Тоді
, (і, j) 
Gn. (3)
Якщо робота виконується єдино можливим складом групи, вираз (3) перетворюється на рівність.
Визначимо ступінь збільшення тривалості виконання роботи (і, j) за рахунок неоптимальності складу групи параметром
, (4)
який змінюється в сегменті 
.
Величина 
визначає інтенсивність виконання роботи (і, j).
Тривалість tij виконання роботи (і, j) визначається формулою
. (5)
Побудуємо сітьові графи виконання кожного замовлення і розрахуємо їх основні характеристики (резерви робіт 
, довжину критичних шляхів 
і т. д.).
Графи замовлень, для яких 
, назвемо кращими.
Дуги критичних шляхів кращих графів відмітимо ознакою подвійної критичності (**), дуги некритичних шляхів цих же графів — ознакою критичності (*), а дуги інших залишимо невідміченими.
Сукупність усіх робіт, які за сітьовим графом можна виконувати одночасно в момент t, назвемо фронтом робіт Ф (t). В один фронт робіт можуть входити лише роботи, що належать різним шляхам сітьового графа.
Об’єднаємо множину джерел графів Gn у вузол S шляхом введення допоміжних дуг ( ), де 
— номер джерела п-го графа, а множину стоків — у вузол Т шляхом уведення допоміжних дуг ( ), де — номер стоку графа Gn. Отримаємо розширений граф G*.
У графі G* є дуги, відмічені ознакою подвійної критичності (їх множину позначимо через К2), а також такі, що відмічені одинарною ознакою критичності (К1). Окрему множину створюють дуги, не помічені ознакою критичності.
Згідно з [1] уведімо поняття замикання всередині сітки. Якщо х Î К2, у Î К2, всі дуги, по яким можна здійснити перехід з вузла х у вузол у, не змінюючи орієнтацію обходу, назвемо замиканням вузлів х і у, яке позначимо через w(х, у). Замикання w(х, у) є частковим замиканням в сітці, якщо х ¹ S, у ¹ t. У кожний момент часу для будь-яких двох вузлів множини К2 або К1 можна утворити тільки одне замикання, але таких замикань у сітці може бути стільки, скільки шляхів відмічено ознаками критичності. Кожне замикання однозначно визначено початковими і кінцевими вузлами.
Для побудови алгоритму розподілу ресурсів розглянемо попередньо задачу визначення оптимальної інтенсивності виконання робіт на замиканні. Розв’язання цієї задачі надалі буде складовою побудови календарного плану.
Користуючись наведеними позначеннями і визначеннями, розглянемо таку задачу.
Нехай на сітьовому графі визначені роботи, що складають критичний шлях. Відомі його довжина Ткр і найменша тривалість виконання кожної роботи (і, j) — tij. У кожний момент часу в сітці існує деякий фронт робіт. Тоді по критичній роботі (х*, у*) із фронта робіт можна побудувати замикання w(х, у) (х = х* — початок замикання, у = у* — його кінець), в яке ввійдуть як дуги даного фронту, так і дуги наступних фронтів.
Необхідно визначити фактичну інтенсивність обходу дуг замикання w(х, у), яка задовольняла б заданим обмеженням на ресурси, а час обходу дуг замикання мінімально відрізнявся б від часу, величина якого визначається ділянкою критичного шляху, що потрапив у замикання.
Ця задача зводиться до розв’язання задачі лінійного програмування в такій постановці.
Зафіксуємо множину шляхів П = {Пх, у} із х в у для замикання w(х, у) і підрахуємо кількість шляхів у ньому за виключенням критичного шляху.
Розв’язуємо задачу визначення таких інтенсивностей hij обходу дуг замикання w(х, у), за яких час фактичного обходу дуг замикання мінімально відрізнявся б від часу обходу дуг, що утворюють критичний шлях і потрапили в замикання, тобто необхідно шукати мінімум функції
, (6)
де 
— множина дуг критичного шляху.
З урахуванням (5) маємо
. (7)
Із умови, що тривалість tij обходу кожної дуги замикання обмежена знизу і зверху складом групи спеціалістів , отримуємо обмеження на змінні величини tij функції (7)
. (8)
Крім того, логічним є обмеження з фонду робочого часу jl кожного підрозділу за період 
, l = 1, 2 … L . (9)
Аналогічно записується обмеження з фонду робочого часу підприємства в цілому за той самий період:
. (10)
Схема розв’язання задачі оптимізації розподілу ресурсів на замиканні сітки складається з таких етапів.
1. Шляхом розв’язання задачі лінійного програмування (7) —(10) визначають оптимальні значення 
для всіх (і, j) Î w(х, у).
2. Визначаються оптимальні значення величин hij за формулою
, (і, j) Î w(х, у). (11)
3. Обчислюється оцінка в балах тієї групи спеціалістів, яка в змозі виконувати роботу (і, j) з інтенсивністю 
за час
, (і, j) Î w(х, у). (12)
4. Здійснюється добір складу груп , що якнайкраще відповідають отриманим оцінкам, і їх закріплення за відповідними роботами (і, j) Î w(х, у).
5. Визначається період часу 
, протягом якого будуть виконані всі роботи, що належать w(х, у).
Література
Карагодова Е. А., Маслюк Г. Ф. Об одной задаче оптимального планирования на основе сетевых моделей с учетом ресурсов второго рода // Строительное производство. — 1968. — № 7. — К.: Будівельник. — С. 16—18.
І. Г. Лук’яненко, канд. екон. наук, доцент,
А. О. Губачов, магістр Національний університет «Києво-Могилянська академія»