2.2.2. Дослідження задачі календарного планування виробничої системи

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

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

   2.2.2.1. Формулювання задачі календарного планування

Номенклатурний список продукції, що виробляється за плановий період, складається з n найменувань (i = 1,n). Плановий період включає T часових інтервалів (k = 1,T ). У виробництві використовується m видів ресурсів (j = 1,n). Ресурсами можуть бути групи обладнання, матеріальні ресурси, групи спеціалістів тощо.

Ресурси, які надходять у виробництво, вважаються заданими і характеризуються:

1) технологічними умовами – нормативними витратами на виготовлення продукції A = [Aij], де Aij – обсяг j-го ресурсу, необхідного для виготовлення деталей і-го найменування (нормативна трудомісткість виготовлення і-ої деталі на j-му обладнанні; нормативні витрати j-го виду матеріалів на виготовлення і-ої деталі);
2) організаційними умовами – нормативними запасами ресурсів в k-му інтервалі Bk = [Bkj], де Bkj – обсяг j-го ресурсу у k-му інтервалі (нормативний фонд часу роботи j-го обладнання у k-му інтервалі; надходження j-го виду матеріалів у k-му інтервалі).

Перед підрозділами формулюється задача виконання виробничої програми за обсягом випуску продукції P = (Pi | i = 1,n) за плановий період так, щоб своєчасно постачати деталі відповідно до зовнішніх потреб Fk = (Fki | i = 1,n) (наприклад, потреб складального виробництва або умов постачання продукції), де Pі – плановий обсяг випуску деталей і-го найменування; Fkі – потреби деталей і-го найменування у k-му інтервалі.

Формально подамо наведену задачу за допомогою наступної лінійної оптимізаційної моделі.

Стан виробництва у k-му інтервалі будемо задавати вектором Xk = (Xki | i = 1,n), компонента якого Xk – випуск деталей і-го найменування у k-му інтервалі. Тоді обсяг використаного j-го ресурсу у k-му інтервалі не повинен перевищувати встановленого значення норми, тобто:

 j = 1,m, k = 1,T. (2.13)  

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

 j = 1,m, k = 1,T, (2.14)  

тобто обсяг j-го ресурсу, використаного за k інтервалів, не повинен перевищувати обсягу, який надійшов до k-го інтервалу.

Таким чином, обмеження (2.13), яке не враховує використання ресурсів у попередні інтервали, доцільно використовувати у випадку часового обліку ресурсів (фонд часу обладнання), а обмеження (2.14) – при кількісному обліку ресурсів (витрати матеріалів).

Але якщо не встановлені організаційні умови витрат ресурсів за час планового періоду, то обмеження на їх використання повинно мати вигляд:

 j = 1,m

або

 j = 1,m, (2.15)  

де

Кінцевий випуск продукції за умовами задачі повинен дорівнювати плану виробництва, тобто

 i = 1,n. (2.16)  

Якщо врахувати, що виготовлена продукція безпосередньо даною виробничою одиницею не використовується, то Xi = (Xki | k = 1,T) – невід’ємна послідовність, тобто

Xki ≥ 0, k = 1,T, i = 1,n. (2.17)  

Календарний план випуску продукції (Xki | k = 1,T ), який задовольняє наведеним обмеженням, називають прийнятним. В реальних виробничих умовах існує кінцева, але достатньо велика множина прийнятних планів випуску, серед яких необхідно вибрати найкращий з точки зору максимального задоволення потреби (Fk | k = 1,T ). Тому як критерій задачі необхідно розглядати цільову функцію (ЦФ) мінімізації сумарного по інтервалах та деталях відхилення випуску від потреби:

(2.18)  

Якщо перевиробництво неприпустиме (випуск не повинен перевищувати потреби), то у виразі критерію значення відхилення випуску від потреби необхідно врахувати за модулем (|Fki – Xki|).

  2.2.2.2. Метод задачі календарного планування

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

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

Математичне формування задачі ЛЦП, до якої застосовують метод, має наступний вигляд:

(2.19)  

за умов:

 i = 1,m; (2.20)  
Xj ≥ 0, j = 1,n; (2.21)  
Xj – цілі числа. (2.22)  

Процес знаходження оптимального рішення починають із розв’язання неперервної задачі ЛП. Якщо одержаний при цьому оптимальний план Xo не задовольняє умові (2.22), то значення ЦФ F(Xo) дає верхню оцінку Ω для шуканого рішення.

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

Схема алгоритму ітераційної процедури:

Крок 1 – розгалуження.
Вибрати змінну Xjo, значення котрої не є цілочисельним. Покласти L = [Xjo], де [ ] – процедура виділення цілої частини. Сформулювати дві задачі: у першу додати обмеження Xj ≥ L + 1, а у другу – Xj ≤ L. Відібрати одну з них як поточну, а другу ввести у список задач G для подальшого створення множини рішень.

Крок 2.
Розв’язати поточну ЛП-задачу як неперервну та знайти її оптимальний план Xo.

Крок 3.
Розрахунок оцінки Ω = F(Xo).

Крок 4 – перевірка оптимальності.
Якщо Xo – цілочисельне та Ω = max {Ω(G)}, то Xo – оптимальне рішення. В іншому випадку відбираємо з G задачу з нецілочисельним рішенням, у якої оцінка є max {Ω(G)}, та переходимо до початку наступної ітерації.

Перед розв’язанням задачі необхідно попередньо виконати такі процедури:

1) привести математичну модель до канонічного вигляду у формі задачі на максимум, тобто обмеження (2.20) перетворити на рівняння за допомогою додаткових (структурних) змінних, а форму ЦФ подати як (2.19);
2) визначити початковий прийнятний (невід’ємний) базисний розв’язок задачі і у випадку необхідності ввести штучні змінні;

Особливості застосування методу:

1. Метод можна застосовувати як для повністю, так і для частково цілочисельних задач.
2. Нові обмеження виду Xj ≥ [Xjo] + 1 чи Xj ≤ [Xjo], які вводяться на кожній ітерації, виступають у вигляді відтинів.
3. При введенні нового обмеження немає необхідності знову розв’язувати всю задачу (2.19)–(2.22), а можна використовувати результати попередньої ітерації, безпосередньо вводячи в таблицю оптимального рішення нове обмеження.
4. При розв’язанні ЛП-задачі на мінімум використовують нижню границю – Ω(G) = min{F(X)}. В цьому випадку ознака оптимальності формулюється протилежним чином.