Розділ 2. Алгоритмізація задач управління інтегрованим виробництвом

Алгоритмізація – це етап розв’язання задачі, що полягає у знаходженні за її формулюванням методу рішення.

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

Таким чином, під алгоритмізацією управління інтегрованим виробництвом будемо розуміти процес проектування моделей, методів і алгоритмів задач управління ГВС та їх верифікації.

2.1. Автоматизоване планування в інтегрованому виробництві

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

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

Головна відмінність організаційно-економічних систем від систем технологічного управління 3 і 4 рівнів полягає в характері об’єкта управління. Якщо в системах технологічного управління об’єктом є технологічні одиниці та комплекси устаткування різного призначення, то в організаційно-економічних системах – це колективи людей, які взаємодіють, обслуговують, організують роботу технологічних комплексів. Тому одними з визначальних задач, що забезпечують скоординоване функціонування всього виробництва, є задачі планування різних рівнів управління.

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

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

В залежності від того, на які періоди складаються плани, загальнозаводське планування (планування на рівні цілого підприємства) поділяють на перспективне і поточне (рис.2.1).

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

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

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

Рис. 2.1. Структура загальнозаводського планування

Поточне планування визначає склад робіт, їх розподіл по підрозділах. Воно поділяється на техніко-економічне (річне, календарне з робивкою по інтервалах періоду) і оперативне.

Техніко-економічне планування деталізує показники перспективного плану на даний період і коригує їх відповідно до вимог планового завдання підприємства.

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

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

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

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

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

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

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

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

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

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

Міжцехове планування – це встановлення скоординованих складових загальних планів виробництва – календарних планів підрозділів.

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

Таким чином, задачі автоматизованого планування можна класіфікувати за наступними ознаками належності до таких групи:

1) за об’єктом або рівнем управління – загальнозаводське планування, міжцехове планування (планування роботи великих виробничих підрозділів), всередині-цехове планування (планування завдань робочим місцям);

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

3) за видом отриманих результатів – з просторовим впорядкуванням за устаткуванням, підрозділами обсягів і номенклатури, з часовим впорядкуванням комплексу планових робіт (номенклатури випуску).

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

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

– об’ємно-календарного планування (охоплює задачі перспективного і техніко-економічного планування загальнозаводського і міжцехового рівня з часовим впорядкуванням результатів);

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

2.2. Типові задачі планування в інтегрованому виробництві та методи їх розв’язання

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

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

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

Сфера застосування моделей та методів такого роду у даний час охоплює широкий спектр функцій організаційного управління [10].

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

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

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

1) витрати виробника на виготовлення вітчизняних товарів встановленої номенклатури, враховуючи ліцензію на вивіз – ;

2) ціни на вітчизняні товари при продажу оптом за валюту у Європі – ;

3) максимально доступні розміри партій вітчизняних товарів – ;

4) фрахтові ставки при перевезенні вітчизняних товарів – ;

5) ціни на товари закордонного виробництва встановленої номенклатури при купівлі оптом за валюту у Європі – ;

6) фрахтові ставки при перевезенні іноземних товарів – ;

7) ціни на європейські товари при продажу за гривні в роздріб – ;

8) коефіцієнт перерахунку оптової ціни в роздрібну при продажу – ;

9) ставка податків на продаж – ;

10) валютний курс гривні – ;

11) коефіцієнти загальних втрат при роботі з вітчизняними товарами – ;

12) коефіцієнти загальних втрат при роботі з іноземними товарами при продажу їх оптом та в роздріб ;

13) максимальні розміри партій іноземних товарів, які можна реалізувати у рамках зазначених втрат – ;

14) сума грошових коштів, які має виробник – ;

15) сума одержаного кредиту – ;

16) процентна ставка з кредиту – ;

17) обмеження на вивезення валюти з Європи – ;

18) обмеження на вивезення валюти з України – .

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

В результаті математичний запис задачі має наступний вигляд:

за умов

– обмеження коштів на виробництво, перевезення і компенсації втрат;

– обмеження коштів на придбання іноземних товарів

– обмеження на вивезення валюти з Європи;

– обмеження на вивезення валюти з України;

– обмеження на максимальний обсяг партій вітчизняних товарів;

– обмеження на максимальний обсяг партій іноземних товарів.

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

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

2) технологічні процеси орієнтовані на одержання продукції з наявних в системі матеріалів;

3) витрати ресурсів системи, які пов’язані з кожним із технологічних процесів, визначаються трудовитратами (виміряними в людино-тижнях), а також кількістю матеріалів (в одиницях ваги), які витрачаються за встановлений час планового періоду;

4) загальні трудовитрати виробництва повинні не перевищувати , а матеріальні запаси - .

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

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

за умов

;

.

Іншим варіантом задачі розподілу ресурсів є розрахунок завантаження устаткування, який виконується за такими початковими даними:

1) B_і – пропускна здатність і - ої групи устаткування ();

2) A_іj – трудомісткість j - го виробу (), виготовленого на обладнанні і - ої групи;

3) S_j – собівартість виробів;

4) C_j – вартість виробів;

5) X_j – шукана програма випуску;

6) обмеження з пропускної здатності устаткування:

.

В залежності від економічних вимог використовуються різні критерії оцінки шуканої програми випуску при задоволенні обмеження з пропускної здатності:

1) найменший сумарний розмір простоїв:

,

де ;

2) максимізація випуску у вартісному вираженні:

;

3) максимізація прибутку:

.

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

Симплекс-метод є найбільш поширеним та універсальним обчислювальним методом, який використовується для розв’язання будь-яких задач ЛП за допомогою ЕОМ. Ідея методу полягає у послідовному проходженні по базисних рішеннях опорних планів задачі доти, доки не буде одержане оптимальне рішення (іншими словами, у послідовному покращенні планів задачі за визначеним критерієм).

Розглянемо процес підготовки початкових даних і алгоритм розв’язання задачі ЛП табличним симплекс-методом.

Математична модель задачі ЛП має одну із наступних лінійних форм:

(2.1)

за умов:

; (2.2)

X_j ³ 0, (2.3)

або

(2.4)

за умов:

(2.5)

X_j ³ 0, . (2.6)

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

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

2) визначити початковий прийнятний (невід’ємний) базисний розв’язок задачі (у випадку обмежень (2.5) ввести штучні змінні);

3) ввести в початкову симплекс-таблицю такі параметри, які відповідають початковому базисному розв’язку (рис.2.2):

– вагові коефіцієнти при змінних X_j в ЦФ (рядок C_j);

– змінні X_j, які входять до наявного базису;

– значення базисних змінних X_і = B_і = A₀ (стовпець A ₀);

– елементи , матриці умов задачі A [ m ´ n ] (стовпці A ₁, A ₂,..., A_n);

– оцінки , що відповідають стовпцям A ₁, A ₂,..., A_n і визначаються за формулою:

. (2.7)

Рис. 2.2. Структура початкової симплекс-таблиці

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

Алгоритм симплекс-методу (для (2.1)) має вигляд [5]:

1. Заповнити початкову симплекс-таблицю.

2. Якщо D_j ³ 0 для всіх , то отриманий план оптимальний.

3. Якщо є D_j < 0 і в стовпці A_j всі елементи A_іj £ 0, то ЦФ необмежена зверху умовами задачі і знайти оптимальний план неможливо.

4. Якщо у стовпцях A_j, що відповідають від’ємним оцінкам D_j, існує хоча б один A_іj > 0, то можливий перехід до нового, кращого плану.

5. Стовпець A_k, який необхідно ввести до базису для покращення плану, визначається за найменшим D_j < 0. Стовпець, в якому міститься ця оцінка, називається напрямним.

6. Стовпець A_r, який необхідно вивести з базису, визначається за відношенням r: , (A_іk ¹ 0). Рядок r називається напрямним. Елемент A_rk, який стоїть на перехресті напрямного рядка і стовпця, називається напрямним елементом.

7. Заповнюється нова симплекс-таблиця, яка відповідатиме новому базисному розв’язку:

при ; (2.8)

при ; ; ,

де l – номер ітерації.

Значення D_j визначається одним з двох способів:

а) як кожний елемент таблиці за виразом (2.8);

б) за формулою (2.7).

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

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

1. Якщо за початковий базис беруть базис із вільних змінних, для яких C_і = 0, то оцінки для всіх небазисних змінних дорівнюють D_j = A _{0 j} = - C_j, а відповідні значення .

2. При розв’язанні задачі з математичною моделлю у формі на мінімум в базис вводиться стовпець з найбільшою додатною оцінкою.

3. Відсутність стовпців з D_j < 0 (при розв’язанні задачі з математичною моделлю у формі на максимум) або з D_j > 0 (при розв’язанні задачі з математичною моделлю у формі намінімум) є ознакою оптимальності відповідного базисного рішення.

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

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

Нехай в задачі ЛП B = [ B_i ] – обмеження значень ресурсів, а dB = [ dB_i ] – прийнятні варіації цих ресурсів. Дослідимо їх вплив на зміну оптимального значення ЦФ L (X_oпт (B)) = L (B). Якщо прийняти, що B = B + dB, то нове оптимальне значення ЦФ буде рівним L (B + dB). Обчисливши приріст dL (B + dB) = L (B + dB) – L (B), знайдемо границю співвідношення:

– частинна похідна ЦФ по змінній B_i.

За теоремою подвійності одержимо:

C • X_oпт = L (X_oпт) = L_подв (Y_опт) = B • Y_опт,

де Y_опт – оптимальний розв‘язок подвійної задачі ЛП;

L_подв – ЦФ подвійної задачі.

Звідси dL (B)/ dB_i = Y_{i опт}, що визначає максимальне значення приросту ЦФ прямої задачі при зміні і -го ресурсу B_i на 1 одиницю, а саме: чим більше Y_{i опт}, тим більша чутливість ЦФ прямої задачі до зміни вільних членів B_i в оптимальному розв‘язку X_опт. Якщо Y_{i опт} = 0, то це означає, що відповідний ресурс B_i не є суттєвим для моделі, тобто зміна його значення на 1 одиницю не призведе до зміни оптимального значення ЦФ і отриманого розв‘язку X_опт. Це обумовлює перетворення і -го обмеження прямої задачі у строгу нерівність , оскільки ресурс B_i знаходиться у надлишку на величину:

.

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

1) якщо оптимальне рішення задачі подвійності Y_{i опт} = 0, то відповідний ресурс прямої задачі B_i використовується частково і його значення може бути зменшене до величини ;

2) якщо оптимальне рішення задачі подвійності Y_{i опт} ¹ 0, то при зміні відповідного ресурсу B_i на 1 одиницю ЦФ прямої задачі одержить приріст на величину Y_{i опт}.

Слід зазначити, що знаходження значення Y_{i опт} можливе через значення D_j оцінок симплекс-таблиці оптимального розв‘язку прямої задачі, тобто Y_{i опт} = D_n+i.

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

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

В даний час на підприємствах звичайно прийняті наступні методи оперативно-календарного планування: по-детальне, добо-комплектне, машино-комплектне [4]. Такий розподіл визначається відповідними календарно-плановими нормативами, що повинні бути єдиними для всього підприємства. Однак різні цехи і дільниці можуть істотно відрізнятися календарно-плановими нормативами.

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

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

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

Розв‘язання задач календарного планування характерне для міжцехового планування. Перелік типових задач календарного планування наведено в табл. 2.1.

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

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

Таблиця 2.1

Задачі календарного планування на рівні міжцехового планування

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

1) технологічними умовами – нормативними витратами на виготовлення продукції А = [ A_ij ], де A_ij – обсяг i -го ресурсу, необхідного для виготовлення деталей j -го найменування (нормативна трудомісткість виготовлення j -ої деталі на i -му обладнанні; нормативні витрати i -го виду матеріалів на виготовлення j -ої деталі);

2) організаційними умовами – нормативними запасами ресурсів у k -му інтервалі B_k = [ B_ki ], де B_ki – обсяг i -го ресурсу в k -му інтервалі (нормативний фонд часу роботи i -го устаткування у k -му інтервалі; надходження i -го виду матеріалів у k -му інтервалі).

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

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

Стан виробництва у k -му інтервалі будемо задавати вектором , компонента якого X_kj – випуск деталей j -го найменування у k -му інтервалі. Тоді обсяг використаного i -го ресурсу у k -му інтервалі не повинен перевищувати встановленого значення норми, тобто

. (2.9)

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

, (2.10)

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

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

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

або

,

де

.

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

.

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

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

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

,

або максимізації загального прибутку:

.

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

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

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

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

(2.11)

за умов:

; (2.12)

X_j ³ 0, ; (2.13)

X_j – цілі числа. (2.14)

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

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

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

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

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

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

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

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

1) привести математичну модель до канонічного вигляду у формі задачі на максимум, тобто обмеження (2.12) перетворити на рівняння за допомогою додаткових (структурних) змінних, а форму ЦФ подати як (2.11);

2) визначити початковий прийнятний (невід’ємний) базисний розв’язок задачі і у випадку необхідності ввести штучні змінні.

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

1. Метод можна застосовувати як для повністю, так і для частково цілочисельних задач.

2. Нові обмеження виду X_j ³ [ X_jo ] + 1 чи X_j £ [ X_jo ], які вводяться на кожній ітерації, виступають у вигляді відтинів.

3. При введенні нового обмеження немає необхідності знову розв’язувати всю задачу (2.11)–(2.14), а можна використовувати результати попередньої ітерації, безпосередньо вводячи в таблицю оптимального рішення нове обмеження.

4. При розв’язанні ЛП-задачі на мінімум використовують нижню границю W(G) = min { F (X)}. В цьому випадку ознака оптимальності формулюється протилежним чином.

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_і та визначаються рівняння відхилень кожного критерію від свого оптимального значення у кожному іншому випадку розв`язання задачі;

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

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

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

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

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

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

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

; ; ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– всі деталі поділяються на дві групи. До першої належать деталі, в яких T _{1 k} < T _{2 k}, а до другої – деталі, в яких T _{1 k} ³ T _{2 k};

– в першій групі деталі впорядковуються за зростанням часу T _{1 k} , а в другій – за зменшенням часу T _{2 k} ;

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

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

min (T _{1 k} + T _{2 k}, T _{3 l} + T _{2 l}) < min (T _{1 l} + T _{2 l}, T _{3 k} + T _{2 k}),

якщо деталь k йде раніше на обробку деталі l, тобто, в першій групі (T _{1 k} < T _{3 k}) деталі впорядковуються за зростанням часу (T _{1 k} + T _{2 k}), а в другій (T _{1 k} ³ T _{3 k}) – за зменшенням часу (T _{3 k} + T _{2 k}).

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

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

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

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

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

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

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

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

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

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