|
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
Єфіменко Надія Анатоліївна
УДК 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) „Еволюційні моделі, методи і засоби підтримки прийняття рішень при створенні віртуальних підприємств”, в яких автор був виконавцем і його роль полягала в розробці моделей довгострокового об’ємного планування і моделей календарного змінно-добового та місячного планування машинобудівних виробництв з дрібносерійним та середньосерійним характером виробництв в умовах їх автоматизованого функціонування.
Мета та задачі дослідження. Мета дисертаційної роботи полягає у вдосконаленні існуючих та дослідженні і розробці нових моделей, методів і алгоритмів автоматизованого оперативного номенклатурно-календарного планування дискретних виробництв на основі системного дослідження та структурно-функціонального поєднання процесів стратегічного та оперативного управління.
Задачами дослідження є: визначення сучасної концепції технологічно-організаційного планування та управління дискретним виробництвом; математичне моделювання процесів автоматизованого оперативного управління дискретним виробництвом; математичне моделювання процесів планування і управління запасами матеріальних ресурсів дискретних виробництв за умов ринкового середовища.
Об’єктом дослідження є інформаційні процеси оперативного у реальному вимірі часу оптимального перерозподілу та упорядкування матеріальних ресурсів за часом та обсягами при виконанні календарного плану у виробничих системах з дискретним характером виробництва.
Предметом досліджень є моделі, алгоритми та їх інформаційне забезпечення щодо автоматизованого оперативного номенклатурно-календарного планування дискретних виробництв за умов їх стратегічного розвитку.
Методи дослідження ґрунтуються на використанні теорії і методів системного аналізу виробничих систем; теорії графів та матричного аналізу методів математичного дискретного програмування; теорії і методів дослідження операцій; теорій систем масового обслуговування; теорій імовірностей та математичної статистики; теорії інформаційної взаємодії; теорії та методів стратегічного управління.
Наукова новизна одержаних результатів. Полягає в тому, що автором вперше вирішена задача оперативного номенклатурно-календарного планування дискретних виробництв за умов системного поєднання її із задачами стратегічного управління та управління запасами матеріальних ресурсів. Для розв’язання цієї задачі автором отримані наступні наукові результати:
- Набули подальшого розвитку ідеї, моделі та алгоритми побудови оптимальних розкладів, які на відміну від існуючих забезпечують більш високу швидкодію та збіжність при розв’язанні задач календарного планування великого розміру та обмеженості на змінні за умов виконання календарного плану основного і оновлювального виробництва.
- Вперше на системному рівні визначена концепція технологічно-організаційного планування і управління дискретним виробництвом, яка на відміну від існуючої формує науковий підхід інформаційного поєднання за часом процесів стратегічного і оперативного управління виробництвом.
- Запропонована топологічна модель узгоджених за часом технологічних циклів багатономенклатурного дискретного виробництва, яка на відміну від існуючих дає можливість не тільки формувати систему основних обмежень математичної моделі задачі оперативного номенклатурно-календарного планування, але визначити систему суттєвого відсікання варіантів на ітераційних кроках розв’язання багатовимірних задач цілочисельного лінійного програмування (ЦЛП).
- Удосконалена математична модель задачі номенклатурно-календарного планування дискретних виробництв та евристичний алгоритм її розв’язання, який дозволяє на відміну від існуючих, оптимальним чином за часом та обсягами, спланувати технологічний процес за умов мінімального за часом завантаження приладів.
- Удосконалена математична модель планування і управління матеріальними ресурсами за часом та обсягами, як модель систем масового обслуговування при випадковому попиті на продукцію, яка в новій інтерпретації на відміну від існуючих реалізує задачу оптимального поєднання за заданими директивними термінами виготовлення виробів основного і оновлювального виробництва.
Практичне значення отриманих результатів полягає в тому, що на основі удосконалення наукових розробок в області моделювання технологічних процесів дискретних виробництва і використання наукових результатів, отриманих автором, зроблений певний ефективний практичний крок в напрямку підвищення автоматизованого рівня та ефективності розв’язання задач оперативного багатономенклатурного календарного планування машинобудівних підприємств з дрібно- та середньосерійним характером виробництва. А саме, при розв’язанні задач оперативного планування підвищити швидкодію алгоритмів (за рахунок скорочення комп’ютерного часу на розв’язання задач формування календарних планів), забезпечити збіжність оптимальних рішень за умов великої інформаційної та топологічної розмірності задач планування; пов’язувати ефективним чином процес оперативного планування із оптимальним використанням матеріальних і сировинних ресурсів. Модельні і алгоритмічні розробки дисертації ввійшли в склад підсистеми “оперативного управління виробництвом” загальної АСУ “СПЕКТР-ВИРОБНИЦВО” в практику підприємств ВАТ “Метровагонмаш” м. Шполи Черкаської області та ТОВ НВК „АСКЄНН” м. Черкаси безпосередньо при формуванні оперативних календарних та номенклатурно-календарних планів та календарних розкладів виробництва, при розробці перспективних планів розвитку виробництва.
Особистий внесок здобувача. Дисертація є самостійно виконаною завершеною роботою здобувача. Наукові розробки, узагальнення, висновки та пропозиції, що містяться в дисертаційній роботі одержано автором самостійно. Опубліковані праці підготовлені без співавторства особисто здобувачем.
Апробація результатів дисертації. Головні результати дисертаційної роботи апробовані на п’яти міжнародних конференціях. Зокрема, 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)
| 
