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

Размещено на http://www.allbest.ru/

Національний технічний університет України

"київський політехнічний інститут"

Автореферат

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

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

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

Вакуленко Оксана Сергіївна

Київ - 2001

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

Роботу виконано на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України "Київський політехнічний інститут".

Науковий керівник:

доктор технічних наук, професор Павлов Олександр Анатолійович, Національний технічний університет України "Київський політехнічний інститут", декан факультету інформатики та обчислювальної техніки.

Офіційні опоненти:

доктор технічних наук, професор Михайленко Віктор Мефодійович, проректор Європейського університету фінансів, інформаційних систем, менеджменту і бізнесу, директор Українського науково-дослідного інституту системних досліджень стабілізації та розвитку економіки, м. Київ;

Кандидат технічних наук, Загоровська Лариса Григорівна, доцент кафедри інформатики Українського державного університету харчових технологій, м. Київ.

Провідна установа: Міжнародний науково-навчальний центр інформаційних технологій та систем ЮНЕСКО/МПІ НАН України і Міносвіти та науки України, відділ автоматизованих систем обробки даних.

Вчений секретар спеціалізованої вченої ради Д 26.002.03 доктор технічних наук І.І. Коваленко

Анотація

дрібносерійний виріб внутрішньокомірковий

Вакуленко О.С. “Розробка та дослідження алгоритмів оперативного планування взаємопов'язаних виробничих процесів в одиничному та дрібносерійному виробництві”. Дисертація у вигляді рукопису на здобуття наукового ступеня кандидата технічних наук. Cпеціальність 05.13.06 - “Автоматизовані системи управління та прогресивні інформаційні технології”. Національний технічний університет України “Київський політехнічний інститут”. Київ, 2001 р.

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

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

Аннотация

Вакуленко О.С. “Разработка и исследование алгоритмов оперативного планирования взаимосвязанных производственных процессов в единичном и мелкосерийном производстве”. Диссертация в виде рукописи на соискание ученой степени кандидата технических наук. Cпециальность 05.13.06 - “Автоматизированные системы управления и прогрессивные информационные технологии”. Национальный технический университет Украины “Киевский политехнический институт”. Киев, 2001 г.

Защищаются результаты разработки алгоритмического обеспечения уровня оперативного (внутриячеечного) планирования автоматизированной системы планирования и управления мелкосерийным производством. Исследованы свойства и разработан алгоритм решения труднорешаемой комбинаторной задачи “Минимизация суммарного взвешенного запаздывания выполнения независимых заданий одним прибором”. Разработаны эффективные быстродействующие алгоритмы внутриячеечного планирования по критериям минимизации штрафа предприятия за невыполнение в срок изделий, для которых заданы директивные сроки, а также при наличии изделий, директивные сроки которых в процессе выполнения не могут быть нарушены и минимальной длительности переналадки ячейки для случая, когда ячейка состоит из одного рабочего места.

Ключевые слова: оперативное (внутриячеечное) планирование, мелкосерийное производство, теория расписаний, труднорешаемые комбинаторные задачи, суммарное взвешенное запаздывание.

Abstract

Vakulenko O. S. “Development and research of algorithms of operational planning of the interconnected production processes in single and small-scale production”. Thesis for a doctor's (Ph.D's) degree (technical sciences) by specialty 05.13.06 - "Automated control systems and progressive information technologies". The National Technical University of Ukraine "Kiev polytechnics institute", Kiev, 2001.

Results of development of an algorithmic maintenance of the third level (operational (cell) planning) of an automated planning and control system of small-scale production are vindicated.

It is shown, that existing scientific and the technological level of development on planning and management of functioning of the enterprises is insufficient for their application in modern conditions.

The requirements of high efficiency of manufactures provide maximization of the enterprise profit, that is associated with necessity of completion of the orders "just in time", maximization of an equipment load, minimization of uncompleted manufacture.

All this can be supplied at presence is scientific of reasonable methods of planning and production management in new conditions. Designing modern automated systems of planning and management of manufacture functioning in market conditions is impossible without the decision of questions, associated with development new high efficiency methods of calendar planning that will allow to take into account dynamics of manufactures functioning, variety of industrial connections.

Therefore there was the necessity in designing system of planning of short run manufacture in market conditions, based on new methods of planning of manufacture.

It is shown, that the mathematical models of planning and production management belong to a class of intractable problems of combinatorial optimization, the exact decision of which by exact traditional methods decision their complex structure and large dimension is impossible. Therefore there were the inapplicable classical methods of optimization and other exact methods of the decision these problems. There were inefficient also the attempts of application of existing approached methods, that reduces the view scope of allowable variants of the decision. It stipulates necessity of development of a new method of problem solving of calendar scheduling, which will allow to discover optimum solutions of the intractable combinatorial problems, and also to solve the problems of real dimensionalities, which arise at scheduling modern production.

The three-level model of small-scale production planning is represented which is a basis of an automated planning and control system of small-scale production.

Because of researches of the single machine total weighted tardiness problems properties, which is NP-hard, the directional truncated search method it of a solution is offered. Because of it is developed:

a) an exact algorithm of the single machine total weighted tardiness problems solving;

b) by virtue of exact algorithm the approximate algorithm of a solution of the single machine total weighted tardiness problems is developed which can be applied to the applications of the large dimensionality;

c) effective resolving algorithms of operational (cell) planning on next criteria are developed:

- minimizing of the single machine total weighted tardiness if for a part of the jobs the tardinesses are prohibited;

- minimizing of the single machine total weighted tardiness if the early and tardy jobs for a part of the jobs are prohibited;

- minimizing of the single machine total weighted tardiness under condition of changeover times minimum.

The analysis of the developed algorithmic maintenances efficiency is carried out. The computational results indicate that the developed algorithms have rather high speed and efficiency. It allows applying them in conditions of automated planning and controlling systems in a real time scale.

Keywords: an operational (cell) planning, small-scale production, scheduling theory, intractable combinatorial problems, the total weighted tardiness problem.

1. Загальна характеристика роботи

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках наукового напрямку, що розвивається на кафедрі АСОІУ НТУУ “КПІ” під керівництвом д.т.н. проф. О.А. Павлова, та пов'язаний з розв'язанням важкорозв'язуваних комбінаторних задач. Базовими для підготовки дисертаційної роботи є науково-дослідні роботи:

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

Разработка информационных технологий, математического и программного обеспечения типовых модулей интегрированной системы планирования и управления мелкосерийным производством (№ держреєстрації 0196U008671). Автор брав участь у написанні розділів 2, 3.

Исследование проблемы разработки эффективных ПДС-алгоритмов для трудноразрешимых комбинаторных задач и создание новых информационных технологий их решения (№ держреєстрації 0196U008670). Автор брав участь у написанні розділів 2, 3.

Разработка моделей, методов и инструментальных средств создания системы планирования и управления функционированием производственных подразделений в составе единой взаимосвязанной системы прогнозного и точного планирования (№ держреєстрації 0197U006541). Автор брав участь у написанні розділів 2, 3.

Гіперсистемні технології обробки інформації та управління КІВ на основі формалізації системного та експертного досвіду (№ держреєстрації 0197U016127). Автор брав участь у написанні розділів 1, 2.

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

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

- розробка точного алгоритму розв'язання задачі “Мінімізація сумарного зваженого запізнення виконання множини незалежних завдань одним приладом” (МЗЗ) та створення на його основі наближеного алгоритму для розв'язання прикладних задач реальних розмірностей;

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

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

Наукова новизна одержаних результатів:

на основі проведених досліджень властивостей важкорозв'язуваної комбінаторної задачі “Мінімізація сумарного зваженого запізнення виконання множини незалежних завдань одним приладом” (МЗЗ) виведення нових властивостей оптимальних розв'язків цієї задачі;

на основі відомих та виведених автором властивостей оптимальних розв'язків задачі МЗЗ та відомого методу направленого перебору з відсіканнями [2,3] розробка нового точного алгоритму розв'язання задачі МЗЗ та на його основі розробка нового наближеного алгоритму розв'язання задачі МЗЗ;

для розробленого наближеного алгоритму розв'язання задачі МЗЗ одержання оцінки відхилення розв'язків від оптимальних;

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

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

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

Результати дисертаційної роботи використані для розробки автоматизованої системи планування та управління дрібносерійним виробництвом.

Результати дисертаційної роботи впроваджено на ДП “АСУ АЕС” ВАТ “Атомсервіс”.

Особистий внесок здобувача.

1. На основі відомого методу направленого перебору з відсіканнями, відомих властивостей задачі МЗЗ, а також виведених автором нових властивостей оптимальних розв'язків задачі МЗЗ розроблено:

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

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

2. Проведено дослідження ефективності розробленого алгоритмічного забезпечення.

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідались на міжнародних наукових конференціях “Автоматика 97”, “Автоматика 98”, “Вимірювання 98”, а також на наукових семінарах кафедри АСОІУ НТУУ “КПІ”.

Публікації. По темі дисертаційної роботи опубліковано 7 друкованих праць.

Структура та об'єм роботи. Дисертація складається зі вступу, 4 розділів, висновків, списку використаних джерел (105 найменувань) та одного додатку. Основний зміст роботи викладено на 142 сторінках машинописного тексту, в тому числі 4 рисунки, 6 таблиць.

2. Зміст роботи

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

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

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

Сформульовано властивості такої системи оперативного управління виробництвом, що відповідатиме вимогам сучасного виробництва, яке повинно бути організовано за прогресивним принципом “виробляти тільки те, що потрібно, тоді, коли потрібно і стільки, скільки потрібно”.

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

Наведено трирівневу модель планування дрібносерійного виробництва в умовах ринку, що лежить в основі розробленої на кафедрі АСОІУ НТУУ “КПІ” системи планування та управління дрібносерійним виробництвом.

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

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

б) максимізація прибутку за наявності штрафів за порушення директивних строків;

в) максимізація прибутку при виконанні замовлень “точно в строк” за наступних обмежень:

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

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

Загальна схема розвязання задач у системі складається з трьох рівнів:

підсистема прогнозного планування виробництва;

підсистема узгодженого планування виробництва;

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

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

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

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

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

Критерієм оптимальності плану виробництва є максимізація прибутку підприємства в ринкових умовах.

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

.

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

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

- мінімальної тривалості переналагодження комірки.

Здобувачем розроблено алгоритмічне забезпечення третього рівня системи САПДВ (рівня внутрішньокоміркового планування) для випадку, коли робоча комірка складається з одного робочого місця.

У другому розділі представлено алгоритмічне забезпечення розв'язання задачі “Мінімізація сумарного зваженого запізнення виконання незалежних завдань одним приладом” (МЗЗ), що є класичною задачею теорії розкладів та належить до класу NP-важких задач у сильному розумінні [1]. Дана робота базується на результатах, одержаних в [2, 3], і є розвитком цього напрямку.

Постановка задачі.

Задано множину незалежних завдань I = { i₁ , i₂ ,... , i_N }, кожне з яких складається з однієї операції. Для кожного завдання відомі - тривалість виконання, - ваговий коефіцієнт і - директивний строк виконання. Завдання надходять у систему одночасно, а переривання їх виконання не дозволяється. Необхідно побудувати розклад виконання завдань в даній комірці за критерієм мінімізації сумарного штрафу за затримку виконання завдань відносно директивних строків:

= min,

де - момент закінчення виконання завдання i.

Алгоритм А1 (алгоритм побудови послідовності *(, , …, , )).

Вхід: послідовність (, , …, , );

Вихід: послідовність *(, , …, , ).

Позначимо g+1=NULL, якщо g - останнє завдання в послідовності .

1. j = k, g = .

2. Якщо j = 0, то зняти усі позначки “*” з завдань і кінець - отримано послідовність *(, , …, , ). Інакше перехід на п. 3.

3. Якщо g (при jk) або якщо g NULL (при j=k) перехід на п. 4.

Інакше j = j -1 і перехід на п. 2.

4. Якщо завдання g не запізнене, то перехід на п. 9.

5. Для завдання g виконати процедуру В. Якщо g = , то перехід на п. 9.

6. Якщо g < , то g = і перехід на п. 4.

7. Якщо g - запізнюється і не має позначки “*”, то виконати перестановку завдання g на позицію p_min (g) і позначити його “*”.

Якщо ж g - запізнюється, має позначку “*”, виконується > і наступне після g запізнене завдання має менший пріоритет, ніж , то зняти з завдання g позначку “*”.

8. Якщо g < , то g = і перехід на п. 4.

9. g = g +1. Перехід на п. 3.

Процедура В.

(Виконується для завдання g(, , …, , )| ( g <, якщо j і g, якщо j = k) при збереженні порядку <<…<).

1. Якщо завдання g не запізнене, то кінець. Інакше перехід на п. 2.

2. Знайти завдання p[[1], g-1] | p, t=, для якого справджується:

A(p) = min{, }- max {- max(, 0), 0}> 0,

= max(-, 0), =- і A(p) ={A(i)}.

Якщо такого завдання не існує, то кінець. Інакше перехід на п. 3.

3. Виконати перестановку завдання p на позицію завдання g+1. Якщо p =, то кінець. Інакше перехід на п. 1.

На основі вищенаведеної схеми розв'язання задачі МЗЗ сформульовано алгоритм її розв'язання:

Алгоритм А2.

Побудувати послідовність ^уп. F_min= F( ^уп), ^min = ^уп.

=1, j =2.

=1.

якщо {для деякого s = виконується =}

то { перехід на п. 4}

інакше {перехід на п. 5}

якщо { k}

то {=+1 і перехід на п. 3}

інакше { якщо { j =1}

то { ^opt = ^min і кінець}

інакше { j = j -1 і перехід на п. 4}}

якщо {j k}

то {j = j +1 і перехід на п. 2}

інакше {перехід на п. 6}

Побудувати послідовність (,, …,) наступним чином:

1. В послідовності ^уп перемістити завдання на позицію p_min (). j =2.

2. В отриманій послідовності перемістити завдання на позицію max{p_min (), +1}.

3. Якщо j = k, то перехід на п.7, інакше j = j +1 і перехід на п. 2.

4. Для послідовності (,, …,) за допомогою алгоритму А1 побудувати послідовність *(,, …,).

Якщо F(*) < F_min, то F_min= F(*) і ^min =*.

j = k. Перехід на п. 4

Доведено такі твердження:

1. Послідовність *(,, …,), що отримана з послідовності (,, …,) після виконання алгоритму А1, є оптимальною серед усіх послідовностей, в яких < < …< < .

2. Розклад ^opt, що отриманий при виконанні алгоритму А2, є оптимальним.

Для розробленого алгоритму А2 сформульовано правила відсікань надлишкових віток.

На основі точного алгоритму А2 розв'язання задачі МЗЗ розроблено наближений алгоритм розв'язання цієї задачі з оцінкою точності одержаного розв'язку :

F() - F( ^opt) F_ms. Наведено процедуру обчислення оцінки F_ms.

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

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

Задача В1. Мінімізація за умови непорушення директивних строків для завдань множини Q = {}, i=(k<N).

Задача В2. Мінімізація за умови, що для завдань множини Q = {}, i=(k<N) заборонені випередження та запізнення відносно директивних строків .

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

Алгоритм розв'язання задачі В1 складається з двох етапів: перший етап полягає в побудові розкладу, в якому для усіх завдань множини Q виконується умова непорушення директивних строків ; на другому етапі виконується оптимізація цього розкладу за допомогою наближеного алгоритму А2, при виконанні якого вводиться обмеження на заборону запізнень завдань множини Q відносно директивних строків.

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

Алгоритм розв'язання задачі В3 складається з двох етапів: на першому етапі виконується оптимізація структури початкової послідовності, тобто виконується об'єднання завдань з метою мінімізації тривалості переналагодження комірки; на другому етапі виконується оптимізація отриманої послідовності за допомогою наближеного алгоритму А2.

Наведено обґрунтування евристичних правил, використаних в розроблених алгоритмах В1-В3.

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

Залежність процесорного часу, необхідного для розв'язання задачі МЗЗ алгоритмами А2 точним та наближеним відповідно, від розмірності задачі n (кількості коміркокомплектів). Усі дослідження виконувались на комп'ютері IBM PC з процесором Intel Pentium 233MMX. Для кожної розмірності було розв'язано 100 індивідуальних задач.

В таблиці 1 наведено результати дослідження ефективності наближеного алгоритму А2.

Таблиця 1. Дослідження ефективності наближеного алгоритму А2

Розмірність	n = 50	n = 100	n = 150
Максимальна похибка	4,942%	4,321%	4,718%
Середня похибка	0,423%	0,809%	0,614%
Час, сек	1,107	28,591	52,607

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

Таблиця 2. Дослідження ефективності введення правил відсікань

Розмірність, n	20	30
Алгоритм А2 (Направлений перебір без відсікань)	124,598	1381,494
Алгоритм А2 (Правило 1)	3,307	28,361
Алгоритм А2 (Правила 1+2)	1,548	14,188
Алгоритм А2 (Правила 1+2+3)	1,539	14,185
Алгоритм А2 наближений (Правила 1+2+3+4)	0,049	0,14

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

У висновку висвітлено головні результати роботи:

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

Показано, що сучасному рівню виробництва повинна відповідати принципово нова методологія оперативного управління ним. Сформульовано властивості такої системи оперативного управління, що відповідатиме вимогам до сучасного виробництва, яке повинно бути організовано за прогресивним принципом “виробляти тільки те, що потрібно, тоді, коли потрібно і стільки, скільки потрібно”.

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

Наведено трирівневу модель планування дрібносерійного виробництва в умовах ринку, що лежить в основі системи планування та управління дрібносерійним та одиничним виробництвом САПДВ.

2. На основі відомого методу направленого перебору з відсіканнями, відомих властивостей важкорозв'язуваної комбінаторної задачі МЗЗ та виведених здобувачем нових властивостей оптимальних розв'язків задачі МЗЗ розроблено:

а) точний алгоритм розв'язання задачі МЗЗ;

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

в) розроблено ефективні швидкодіючі алгоритми внутрішньокоміркового планування за наступними критеріями:

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

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

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

3. Проведено аналіз ефективності розробленого алгоритмічного забезпечення.

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

Основні роботи

1. Павлов А.А., Мисюpа Е.Б., Вакуленко О.С. Алгоритм решения задачи “Минимизация суммарного штрафа при условии, что для некоторых заданий директивные сроки не могут быть нарушены” // Проблемы информатизации и управления: Сб. науч. тр. Вып. 2 - К.: КМУГА, 1997. - С. 58-60.

2. Павлов А.А., Мисюpа Е.Б., Вакуленко О.С. Организация планиpования мелкосеpийного пpоизводства в условиях pынка // Інформаційні управляючі системи і технології: Збірник наукових праць Українського державного морського морського технічного університету, Миколаїв. - 1998, № 9 (357). - с. 104-107.

3. Павлов О.А., Місюpа О.Б., Вакуленко О.С. Алгоритм розв'язання задачі “Мінімізація сумарного зваженого запізнення при виконанні множини незалежних завдань одним приладом” // Вісник НТУУ “КПІ”. Інформатика, управління та обчислювальна техніка. “ВЕК+”, К., 2000, № 33, с. 3-7.

4. Павлов О.А., Місюpа О.Б., Вакуленко О.С. Мінімізація сумарного зваженого запізнення при виконанні множини незалежних завдань одним приладом // Вісник НТУУ “КПІ”. Інформатика, управління та обчислювальна техніка. “ВЕК+”, К., 2001, № 35, с. 118-126.

5. Павлов О.А., Місюpа О.Б., Мельников О.В., Вакуленко О.С. Система перспективного та оперативного управління дрібносерійним виробництвом // “Автоматика-97” - 4-та українська конференція з автоматичного управління, Черкаси, 23-28 червня 1997 р., том. ІІ, 1997.

6. Павлов О.А., Місюpа О.Б., Мельников О.В., Вакуленко О.С. Багаторівнева система планування дрібносерійного виробництва в умовах ринку // “Автоматика-98” - п'ята українська конференція з автоматичного управління, - Київ: НТУУ “КПІ”, ч. ІІ. - 1998.- с. 182-186.

Размещено на Allbest.ru

...