ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ

Єфіменко Надія Анатоліївна

УДК 519.854.2

МОДЕЛІ ТА АЛГОРИТМИ АВТОМАТИЗОВАНОГО ОПЕРАТИВНОГО НОМЕНКЛАТУРНО-КАЛЕНДАРНОГО ПЛАНУВАННЯ ДИСКРЕТНИХ ВИРОБНИЦТВ

05.13.06 – автоматизовані системи управління та прогресивні інформаційні технології

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Черкаси – 2004

Дисертацією є рукопис

Робота виконана у Черкаському державному технологічному університеті,

Міністерство освіти і науки України.

Науковий керівник: доктор технічних наук, професор

Лега Юрій Григорович,

Черкаський державний технологічний університет,

завідувач кафедри комп’ютерних систем

Офіційні опоненти: доктор технічних наук, професор

Тесля Юрій Миколайович,

Київський національний університет

будівництва і архітектури,

професор кафедри інформаційних технологій

кандидат технічних наук, доцент

Ус Михайло Федорович,

Східноєвропейський університет

економіки і менеджменту,

доцент кафедри інформаційних технологій

та економічної кібернетики.

Провідна установа: Харківський національний університет

радіоелектроніки, кафедра інформаційних

управляючих систем,

Міністерство освіти і науки України, м. Харків

Захист відбудеться 29.06.2004 р. о 14 год. в залі засідань спеціалізованої вченої ради К 73.052.01 у Черкаському державному технологічному університеті за адресою: 18006, м. Черкаси бул. Шевченка 460.

З дисертацією можна ознайомитись в бібліотеці Черкаського державного технологічного університету за адресою: 18006, м. Черкаси, бул. Шевченка, 460.

Автореферат розісланий 28.05.2004 р.

Вчений секретар

спеціалізованої вченої ради В.В. Палагін

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Вказану проблему в різний час досліджували вітчизняні та зарубіжні вчені такі як: О.С.Вакуленко, В.Л.Волкович, В.С.Гордон, Ю.П.Зайченко, О.С.Мельников, О.Б.Місюра, В.С.Міхалевич, Н.М.Моісєєв, О.А.Павлов, О.А.Павлова, С.Ф.Півоваров, А.А.Тимченко, В.С.Танаєв, Я.М.Шафонський, A.S.Jain, S.Meeran, Nuijten W.P.M., Le Pape та інші. Слід сказати, що науковці в значній мірі розвинули теорію складання оптимальних розкладів календарних планів дискретних виробництв. Поряд з цим критеріальні оцінки розв’язання оптимальних задач календарного планування не включають оцінок мінімального за часом завантаження обладнання за умов виконання в директивний термін планів основного і оновлювального виробництва.

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

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

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

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

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами.

Дисертаційну роботу виконано згідно з планом науково-дослідних робіт Черкаського державного технологічного університету в рамках держбюджетної науково-дослідної теми (державний реєстраційний № 0103U003686) „Еволюційні моделі, методи і засоби підтримки прийняття рішень при створенні віртуальних підприємств”, в яких автор був виконавцем і його роль полягала в розробці моделей довгострокового об’ємного планування і моделей календарного змінно-добового та місячного планування машинобудівних виробництв з дрібносерійним та середньосерійним характером виробництв в умовах їх автоматизованого функціонування.

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

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

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

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

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

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

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

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

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

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

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

Практичне значення отриманих результатів полягає в тому, що на основі удосконалення наукових розробок в області моделювання технологічних процесів дискретних виробництва і використання наукових результатів, отриманих автором, зроблений певний ефективний практичний крок в напрямку підвищення автоматизованого рівня та ефективності розв’язання задач оперативного багатономенклатурного календарного планування машинобудівних підприємств з дрібно- та середньосерійним характером виробництва. А саме, при розв’язанні задач оперативного планування підвищити швидкодію алгоритмів (за рахунок скорочення комп’ютерного часу на розв’язання задач формування календарних планів), забезпечити збіжність оптимальних рішень за умов великої інформаційної та топологічної розмірності задач планування; пов’язувати ефективним чином процес оперативного планування із оптимальним використанням матеріальних і сировинних ресурсів. Модельні і алгоритмічні розробки дисертації ввійшли в склад підсистеми “оперативного управління виробництвом” загальної АСУ “СПЕКТР-ВИРОБНИЦВО” в практику підприємств ВАТ “Метровагонмаш” м. Шполи Черкаської області та ТОВ НВК „АСКЄНН” м. Черкаси безпосередньо при формуванні оперативних календарних та номенклатурно-календарних планів та календарних розкладів виробництва, при розробці перспективних планів розвитку виробництва.

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

Апробація результатів дисертації. Головні результати дисертаційної роботи апробовані на п’яти міжнародних конференціях. Зокрема, VI Міжнародній науково-практичній конференції “Наука і освіта 2003” (Дніпропетровськ – Черкаси 2003 р.), на VIII та IX-й Міжнародних науково-практичних конференціях “Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти” (Київ, ЄУФІМБ, 2002 р., 2003 р.), на VI Міжнародній науково-практичній конференції “Наука і освіта” (Дніпропетровськ – Мелітополь, 2003 р.), на II Міжнародній науково-технічній конференції “Інформаційна техніка та електромеханіка” (ІТЕМ 2003 р., Луганськ, квітень 2003 р.).

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

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, трьох розділів, висновків, списку використаних літературних джерел і додатків. Загальний обсяг дисертації складає 143 стор., у тому числі 4 таблиці, 6 рисунків, 2 додатків та список використаних джерел із 102 найменувань.

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

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

У першому розділі „Концепція технологічно-організаційного планування та управління дискретним виробництвом” з позиції системного підходу визначається концепція технологічно-організаційного планування і управління дискретним виробництвом.

Системну модель планування та оперативного управління дискретним машинобудівним виробництвом представляється у вигляді трійки:

(1)

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

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

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

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

- ідентифікації виробничої системи в умовах її ринкового розвитку – визначення множини аналітичних операторів та інтегрованих виходів системи , як згортки критеріїв за відомими входами та виходами ;

- прогнозування станів розвитку виробничої системи – визначення майбутніх станів системи і вихідних інформаційних змінних із застосуванням операторів та виходів ;

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

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

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

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

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

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

Критерії оцінки оперативних номенклатурно-календарних оптимальних рішень.

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

Необхідно:

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

, (2)

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

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

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

, (3)

де - відповідно дерева мінімальної довжини та найкоротшого шляху; - оптимальне дерево.

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

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

(4)

(5)

або (6)

(7)

Примітка. При формуванні рівнянь (4) – (7) враховувались умови мінімального розфарбування хроматичного графу .

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

, (8)

, (9)

або , (10)

, (11)

Якщо вважати, що індекс тривалості -ї операції співпадає із індексом -го завдання, яке включає виконання скінченої множини однотипних операцій -ї індексації в межах одного коміркокомплекту, то, змінюючи в (8) – (9) на (вектор завдань ), отримаємо:

, (12)

, (13)

або , (14)

. (15)

Рівняння (12) – (15) складають основні мінімально-збиткові обмеження комбінаторної задачі ЦЛП, до якої приводиться задача оптимізації номенклатурно-календарного планування.

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

Знайти: , (16)

при обмеженнях , (17)

, (18)

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

Розв’язання задачі (16) – (17) здійснюється методом послідовного аналізу варіантів (ПАВ) із застосуванням обмежень на відсікання зайвих варіантів, які визначаються топологічними властивостями моделей узгоджених поопераційно та за часом технологічних циклів та властивостями розв’язання задачі мінімізації зваженого запізнення (МЗЗ). Як ефективні інструменти розв’язання задачі ПАВ в роботі запропоновані наступні евристичні алгоритми:

- алгоритм оптимального упорядкування завдань (АОУЗ) за пріоритетами, який дає можливість отримання оптимальної послідовності виконання множини завдань за критеріями і ;

- алгоритм послідовного аналізу варіантів (АПАВ) за умов відсікання варіантів на основі алгоритму топологічних перетворень (АТП) при формуванні матриць і та оптимальних властивостей задачі МЗЗ відсікань за обмеженнями задачі ЦЛП та відсікань за цільовою функцією задачі ЦЛП.

В розділі проведена експериментальна оцінка ефективності запропонованих евристичних алгоритмів при розв’язанні задачі складання оптимального розкладу календарного плану. В експерименті 1 порівнювалась швидкодія Алгоритму 1 розв’язання задачі МЗЗ із запропонованим Алгоритмом 2, який є модифікованим Алгоритмом 1 за умов мінімального розфарбування ребер технологічного графу (умова ) – алгоритм мінімального розфарбування графу (АМРГ), за умов топологічних властивостей графів і - алгоритм дерев графу (АДГ). В табл. 1 приведені розрахунки швидкодії алгоритмів.

Таблиця 1

Розрахунки швидкодії алгоритмів

Розмірність задачі | 50/216 | 90/326 | 120/495 | 150/617

Алгоритм 1 | 7,247 | 28,328 | 47,325 | 64,295

Алгоритм 2 (умова ) | 4.547 | 17,324 | 27,324 | 31,627 | Алгоритм 2 (умова ) | 4,218 | 18,327 | 25,817 | 29,427 | Алгоритм 2(умови та ) | 1,418 | 7,325 | 11,141 | 17,324

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

Таблиця 2

Розрахунки швидкодії алгоритмів

Розмірність задачі | 50/216 | 90/326 | 120/495 | 150/617

Алгоритм 3 (за умов відсікання варіантів згідно алгоритму 1) | 27,471 | 44,218 | 113,614 | 187/925

Алгоритм 4 (умова відсікання варіантів на основі властивостей топологічної мо-делі узгоджених 15технологічних циклів) | 8,327 | 11,418 | 48,326 | 74,328 | В розділі проведена експериментальна оцінка чутливості моделі задачі ЦЛП, яка показала на ефективність щодо швидкодії та збіжності запропонованих в розділі евристичних алгоритмів порівняно з відомими.

В розділі 3 „Моделі планування та управління запасами матеріальних ресурсів дискретних виробництв за умов стратегічного управління” розглядаються наступні задачі: дослідження моделі планування запасів матеріальних ресурсів; дослідження моделі управління запасами матеріальних ресурсів при випадковому попиті на продукцію, а також досліджуються моделі обслуговування запасів з очікуванням та з відмовою.

Задача планування і управління запасами матеріальних ресурсів в розділі пов’язана із задачею оперативного планування технологічних процесів за умов визначеного за часом запуску у виробництво нових виробів і, як наслідок, за умов включення за обсягами (приладо-годинами) та за часом в технологічний процес (ТП) резервного обладнання. В такій постановці загальна задача планування і управління запасами в роботі приведена до низки задач систем масового обслуговування (СМО). Розв’язання включає наступні етапи:

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

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

, (19)

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

. (20)

3. Формування моделі оптимального управління запасами при випадковому попиті на продукцію. Реалізація цієї моделі розглянута в розділі як задача умовної мінімізації функції витрат :               

, (21)

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

З урахуванням (21) отримана функція Лагранжа:

, (22)

де (23)

рівняння зв’язку складових . вектора . Розв’язуючи систему рівнянь (22), (23) методом невизначених множників Лагранжа, отримаємо оптимальний розв’язок , як оптимальний вектор вимірний вектор ресурсів резерву часу, розподілений на всіх ребрах графу . Включення ресурсів здійснюється з урахуванням характеристик ефективності обслуговування для задачі СМО з очікуванням, або для задачі СМО з відмовою та із застосуванням запропонованих в роботі алгоритмів формування календарних планів.

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

ВИСНОВКИ

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

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

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

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

4. Удосконалена математична модель оптимального оперативного номенклатурно-календарного планування дискретним виробництвом, як багатовимірна задача ЦЛП та наближений евристичний алгоритм її розв’язання з використанням топологічних властивостей моделей УГМ та ТМУЦ, який відрізняється від існуючих більш високою швидкодією та надійністю (стосовно чутливості оптимальних рішень задачі ЦЛП) та дозволяє вести оптимізацію за критеріями:

- максимального завантаження обладнання при виконанні виробничої програми за умов обмеження ресурсів та за умов використання за часом та обсягами запасів матеріальних ресурсів;

- мінімізації за умови не порушення директивних строків виконання множини завдань;

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

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

6. Із позицій стратегічного управління виробництвом, підвищення надійності виконання календарних планів в установлені директивні терміни за умов спланованого запуску у виробництво нових виробів удосконалені моделі планування і управління запасами матеріальними ресурсами (МР) дискретних виробництв, а саме:

- моделі обслуговування запасів МР з очікуванням та з відмовою, як моделі систем масового обслуговування;

- моделі планування та управління запасами матеріальних ресурсів (МР) при випадковому попиті на продукцію виробництв.

7. Розроблена детальна функціональна структура загального алгоритму оптимального оперативного номенклатурно-календарного планування за умов стратегічного управління виробництвом.

8. Модельні і алгоритмічні розробки дисертації ввійшли до складу підсистеми „оперативного управління виробництвом” АСУ „СПЕКТР - ВИРОБНИЦТВО” ВАТ „Метровагонмаш” м. Шполи, Черкаської області та ТОВ НВК „АСКЄНН” м. Черкаси.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Єфіменко Н.А. Постановка та формулювання задач оптимального управління технологічним процесом машинобудівного виробництва // Вісник ЧДТУ № 2. – Черкаси, 2002. – С. 9 – 13.

2. Єфіменко Н.А. Формальна технологічна модель управління середньосерійним машинобудівним виробництвом // Вісник ЧДТУ № 3. – Черкаси, 2002. – С. 49 – 54.

3. Єфіменко Н.А. Оптимальне календарне планування технологічної підготовки машинобудівного виробництва в умовах ринку // Весник государственного технического университета № 3(19). – Херсон, 2003. – С. 131 – 134.

4. Єфіменко Н.А. Оптимальне управління якістю продукції на машинобудівному виробництві // Вісник Східноукраїнського національного університету ім. В. Даля, 2003. – № 4(62). – Луганськ. – С. 171 – 173.

5. Єфіменко Н.А. Формальна узагальнена графова модель оперативного управління дискретним виробництвом // Вісник ЧДТУ № 3. – Черкаси, 2003. – С. 55 – 59.

6. Єфіменко Н.А. Модель планування запасів матеріальних ресурсів на машинобудівному підприємстві // Вісник ЧДТУ № 4. – Черкаси, 2003. – С. 106 – 108.

7. Єфіменко Н.А. Модель забезпечення автоматизованої підсистеми погодженого планування середньосерійного машинобудівного виробництва // Матеріали VIII Міжнародної науково-практичної конференції „Інформаційні технології в економіці, менеджменті і бізнесі”. Проблеми науки, практики і освіти. – Київ: ЄУФІМБ. – 2002. – С. 100 – 103.

8. Єфіменко Н.А. Інформаційне та програмне забезпечення задач автоматизованого управління середньосерійним машинобудівним виробництвом // Матеріали VI Міжнародної науково-практичної конференції „Наука і освіта 2003”. – Т. 28 – Дніпропетровськ – Черкаси. – 2003. – С. 11 – 12.

9. Єфіменко Н.А. Впровадження автоматизованої системи підготовки та управління виробництвом // Матеріали VI Міжнародної науково-практичної конференції „Наука і освіта 2003”. – Т. 30 – Дніпропетровськ – Мелітополь. – 2003. – С. 38 – 39.

10. Єфіменко Н.А. Аналіз існуючих методів автоматизованого контролю та управління // Праці Луганського відділення Міжнародної Академії інформатизації. – 2003. – № 1(6). – С. 20 – 21.

11. Єфіменко Н.А. Стратегічне управління запасами дискретних виробництв // Тези IX Міжнародної науково-практичної конференції „Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти”, Київ: ЄУФІМБ. – 2003. – С. 27 – 29.

АНОТАЦІЯ

Єфіменко Н.А. Моделі та алгоритми автоматизованого оперативного номенклатурно-календарного планування дискретних виробництв. – Рукопис.

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

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

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

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

ABSTRACT

N. Yefimenko. Models and Algorithms of Autoimmunized Operational Nomenclature scheduling of Discoutinuous Production. – Manuscript.

The thesis to take academic degree of Doctor of Phylosophy in speciality 05.13.06 – Autoimmunization Control Systems and Progressive Information Technologies – Cherkasy State Technological University. – Cherkasy, 2004.

The thesis is devoted to the problems of developing models and algorithms of nomenclature scheduling and one-shot operation machine building industry control under conditions of strategic planning and material-stock control by volume and time of utilization.

The technical organizational planning and control of discontinuous execution conception is defined as the conception of general setting new operational nomenclature scheduling under condition of production strategic control.

The proposed mathematical models are: the generalized graph model of coordinated one-shot technological cycles and the topological model of technological cycles coordinated by time in carrying out program of planning model and material reserve stock control. It happens under condition of parallel conduction of base and reserved production and under condition accidental demand for realization of ready production.

The proposed heuristic algorithms of problem of minimization of planned schedule realization expenses by criteria: maximal machine utilization and prohibition of advance and delays with regard to directive plan due take.

Key words: discontinuous production scheduling, strategic control, technological cycle, minimization of expenses, mass service system.

АННОТАЦИЯ

Ефименко Н.А. Модели и алгоритмы автоматизированного оперативного номенклатурно-календарного планирования дискретных производств. – Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.06 – автоматизированные системы управления и прогрессивные информационные технологии. – Черкасский государственный технологический университет, Черкассы, 2004.

Диссертационная работа посвящена вопросам разработки моделей и алгоритмов номенклатурно-календарного планирования и пооперационного оперативного управления дискретным машиностроительным производством в условиях стратегического планирования и управления запасами материальных ресурсов по объему и времени их использования.

Определение концепции организационно-технологического планирования и управления дискретным производством, как концепции общей постановки новой задачи оперативного номенклатурно-календарного планирования в условиях стратегического управления производством. Разработаны математические модели: обобщённая графовая модель согласованных пооперационно и топологическая модель согласованных во времени системы технологических циклов по выполнению производственной программы, модели планирования и управления резервными запасами материальных ресурсов в условиях параллельного ведения основного и вновь вводимого производства и случайного спроса на реализацию готовой продукции. Предложены эвристические алгоритмы решения задачи минимизации расходов на реализацию календарного плана по критериям: максимальной загрузки оборудования и запрета на опережение и задержку относительно директивных сроков выполнения плана.

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

Предложена функциональная схема общего алгоритма реализации задачи оптимального оперативного номенклатурно-календарного планирования в условиях стратегического управления, который на конструктивном уровне позволяет составлять и оценивать оперативный календарный план эффективно используя стандартные программные продукты в средах Mathcad, Mathlab.

Реализация алгоритма включает выполнение следующих функциональных задач: обработка априорных дынных относительно составляющих технологического процесса; формирование критериев оптимизации задач номенклатурно-календарного планирования; формирование минимально избыточного графа системы технологических циклов; построение топологической модели согласованных пооперационно и во времени технологических циклов; формирование моделирующего графа на построенной топологической модели – формирование ограничений на материальные ресурсы и топологических ограничений на формирование конкретных технологических циклов; формирование модели оперативного, оптимального номенклатурно-календарного планирования дискретным производством как задачи целочисленной дискретной оптимизации; решение указанной задачи с использованием двух вспомогательных алгоритмов: упорядочения заданий по приоритетам и последовательного анализа вариантов с учётом условий отсекания вариантов по ограничениям и по целевой функции задачи дискретного программирования; исследование чувствительности оптимальных решений указанной задачи по указанным ограничениям.

Математическое и алгоритмическое обеспечение ориентировано на повышение уровня автоматизированного управления и даёт возможность связать эффективным образом процесс оперативного планирования из оптимальным использованием материальных ресурсов. Модельные и алгоритмические разработки являются универсальными и могут быть рекомендованы для разработки подсистем “оперативного управления производством” при построении АСУ дискретных производств различных отраслей.

Впервые с позиций стратегического управления производством, повышения надёжности выполнения календарных планов в установленные директивные термины в условиях спланированного запуска в производство новых изделий разработаны и построены модели планирования и управления запасами материальных ресурсов (МР) дискретных производств, такие как: модели обслуживания запасов МР с ожиданием и отказом; модели планирования и управления запасами МР при случайном спросе на продукцию производства. Разработана детальная функциональная структура общего алгоритма оптимального оперативного номенклатурно-календарного планирования в условиях стратегического управления производством.

Ключевые слова: дискретное