автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Алгоритмичное и программное обеспечение автоматизированной системы управления дискретным производством смешанного типа

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

РГБ ОД

- . >

Па правах рукопису УДК 658.012.011:519.8

МИХАЙЛОВ Володимир Волевнч

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

Спеціальність 05.13.06 — «Автоматизовані системи управління»

АВТОРЕФЕРАТ ДИСЕРТАЦІЇ на здобуття наукового ступеня кандидата технічних наук

Київ •— 1994

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

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

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

Павлов О. А.

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

Михайленко В. М., кандидат технічних наук Остапченко К. Б.

Провідна організація: Харківський інститут

радіоелектроніки

Захист відбудеться «_ » /Р^РЛ^>/иЯ 1994 р. о

годині на засіданні спеціалізованої Ради Д 068.14.07 при Київському політехнічному інституті за адресою: 252056, м. Київ, проспект Перемоги, 37, актовий зал головного корпусу.

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

Автореферат розіслана « » 1994 р.

Учений секретар . спеціалізованої Ради, доктор технічних наук

РОМАНЕНКО В. Д.

• АНОТАЦІЯ

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

виробництвом для машинобудівного' підприємства змінного

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

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

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

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

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

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

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

Автор захищає:

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

ДО РИНКОВОЇ економіки; . • . _

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

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

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

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

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

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

програмну реалізацію розроблених моделе., і алгоритмів у

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

• ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ Актуальність теми. Перехід економіки від адміністративно -, командного управління до ринкових відносин кардинально змінює мотиви та характер поведінки суб'єктів господарської діяльності. В першу чергу, це відноситься до великих та середніх промислових підприємств. - Вимоги ринку примушують значно підвисити мобільність виробництва, постійно оновлювати та розширяти номенклатуру виробляємої продукції, у напкоротші строки задовільняти замовлення споживачів, екоротчувати витрати виробництва та знижувати собівартість виробляємої продукції. Перераховані причини призводять до необхідності зміни традиційних способів та методів оперативно-виробничого планування і управління виробництвом.

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

з

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

'Практична данність /результатів які одержано в дисертаційній

роботі складається в тому, що розроблені; моделі, процедури та алгоритм вирішення задач оперативно-виробничого планування 2 управління покладено в основу алгоритмічного забезпечення розробленої автоматнаовааної системи оперативного управління основним виробництвом САС 0У03) для машинобудівного підЯриешства. Дана автоматизована система знаходиться в промисловий ексллуатац11 на 45-му механічному заводі См. Вінні.ляЗ.

Реалізація результатів роботи виконувалась * у рамках слідуючихДоговорів : “Разработка универсальных программных

средств ;в (рамках АСУ ГПС с ГАУ механообработки” та "Разработка пйке'га прикладных программ "АСУ Цех-Сборка" між кафедрою АСУВ КЇЇІ та 'СНВінституту Кібернетики АН УРСР ім.В.М.Глушкова, часткоЕ їй ‘економі чни-1 ефект від впровадження основних резУлі>таіч?в (рббоТИ 84 тис. крб. у цінах 1990 року;

"Разработка ■автоматизированной системі оперативного управления о&кШйШ* !ЦройЗв<ДОїв<5м (Ч'и її очередь)” ми* кафедрою АСУВ КПІ та ’механічним наво/ом м. Вінниця, частковий економічний ефйіїт ?, 9'ШН.ирб >у 'Цінах Грудня 1992 року.

АНрббйІШ ре&УЛьтатїв іробо'ти. Основні положення дисертації та рбСо'та в и і лому ’були докйадені на III польсько-радянській Науково-технічніи конференці ї ""Комплексная автоматизация промяиленности" (м.Вроцлав,'Республика Польща, 1ЭЭ9 р. ), на IV ■Міжреспубліканській конфйренШ1! ""’Актуальные проблемы разработки 'автоматизированных систем управления’" ( КП1, Київ, 1990 р.).

На Міжнародній конференцій ’’"Ривкая автоматизация ’90" (м. Ёрй'ткслава, ЧСФР, 19Э0 -на наукових семінагах кафедри

АСУВ Київського політехнічного інституту "Методы оптимизации И Проблемы построения АСУ {Київ 1990,1993,1994 рр.). .

Публікацій. Основні результати, які викладені в дисертації,

відображено в дев’яти друкованих роботах.

• Структура і обсяг роботи. .Дисертаційна робота складається з вступу, Чотирьох глав, висновку, переліку основної літератури э 116 найменувань і 1 додатку. Основний зміст роботи викладено на 16# сторінках, машинописного тексту і виміщуе 3 таблиці.

В першому розділі визначені основні характеристики зиша* него багвтономенклатурного серійного та дрібносерійкого типу виробництва э середньою довжино» циклу виготовлення виробів, описано технологію планування та змінений организаиіпної моделі оперативно-виробничого планування та управління на підприємствах в умовах переходу до ринкової економіки, сформульовані вимоги до моделей систем міжцехового та вкутрішньоцехового оперативно-виробичого : планування та управління для розглянутого типу виробництва.в сучасних умовах. Сформульовано та обгрунтовано задачі дослідиень. . В другому розділі запропоновано комплекс •узгодженим, моделей та лроцедур оперативно-виробничого планування та управління, що охоплює міжцеховий та внутрішньо-цеховий рівні управління. Показано переваги розробленого комплексу моделей, у зрівнянні з традиційними типовими сйоте-мами, для розглянутого типу виробництва в умовах переходу до ринкової кономікв. В третьму . розділі проведено дослідаения класичної НР-трудног задачі теорії розкладу - мінімізації сумарного взваженого моменту закінчення виконання множини завдань з різними директивними строками одним приладам. На, основі ряду затверджень розроблено, та якісно обгрунтовано 'еі£ективннй алгоритм' рішення даної задачі, , проведено його експериментальне дослідження та порівняння отриманих умовно-оптимальних розкладів з оптимальними Сдля малих розмірів}, та з розкладами отриманими алгоритмом їїилдп-Фр!дмана С для великих розмірів задачо. В четвертому розділі розглянуто питання практичного використання результатів робти, наведено загальний опис автоматизованої системи оперативного управління основним виробництвом машинойудівельного підприємства. .'

ЗМІСТ РОБОТИ

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

Б

дарне планування) значно змінюється. Деякі з причин. що викликали Ш зміни, слідуючі; . різко зросла самостійність підприємств, зниження концентрації виробництв та розділення підприємств на більш дрібні самостійні ОДИНИЦІ; різке зниження розміру держзамовлення; більша частина виробничої програми формується на основі прямих договорів а зазначенням конкретних термінів постачання, об'єма та номенклатури продукції; договори, на постачання укладаються безперервно на протязі року та строк від укладання договору до моменту постачання мінімальний; тенденція до випуску різнородної продукції, що має технологічну схожість , до розширення номенклатури випускаємо! продукції б зв'язку з змінюичимкся ринками збуту, необхідністю більш ПОРНО ураховувати запроси користувачів і, як наслідок, зниження серійності виготовляємо! продукції; різке зменшення величини обігових коштів, що примушує відмовитись від створення великих запасів та снияуватк об'єм незевершекого виробництво; структурна перебудова економіки та міграція робочої сили з промисловості в інші сфери.

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

велика номенклатура виробляємо! продукції Сбільш 100 найменувань виробів), переважання складних в конструкторському плані виробів Спонад 1000 деталей), значна частка продукції має конструкторсько-технологічну схожість, що призводить ДО ВИСОКОЇ питомої ваги уніфікованих та стандартизованих деталей та вузлів-, по більшості випускаємих виробів технологічний цикл виготовлення складає 0, б - 1.6 місяця Ссередня тривалість);

загальна кількість різних деталей та вузлів на підприємстві перевищує 10000 найменувань, більшість детален проходить по технологічному маршруту 2-3 цехи;

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

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

виробництва;

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

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

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

■ б*ємно-календарного планування показав, що більшість задач складання розкладу є МР-трудними і за допомогою точних методів можливо вирішити задачі тільки малої розмірності. Тому практично єдиним засібом вирішення задач складання розкладу при реальних Г">змірах є розробка еврістичних поліноміальних алгоритмів.

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

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

зменьшення інтервалу планування до п’ятиденки Сдекади) та його діференціація для різних деталей, попускається рівномірність ВИПУСКУ усередені ІНТерЬаЛУ;

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

плановою одиницею приймається кількість деталей, яке дорівнює її споживанню на інтервал планування з урахуванням випереджу- 1ННЯ;

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

підрозділи маршруту виготовлення виробу МІЖ СОбОЮ;

обліковою одиницею комплектності виготовлення виробів

Сзабезпечуваності зборки деталями) прийнято машиьокомлпект

виробу по цеху з урахуванням різних випереджувань входячих

деталей, та вузлів;

планування нормалізованих та уніфікованих деталей на базі

складської моделі;

позмінне формування на базі подетально-комплектного,

машинокомплектного обліку та дефіціту на кінцевій зборці

оперативних завдань дільницям цехів:

позмінне планування кінцевої та вузлової зборки за

допомогою індивідуальних графиків випуску.

Розглянемо стисло модель подетального наскрізного

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

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

Нехай {1,2,...,р,...,а,...,Р) - інтервали планування для У-і

.деталі (п'ятиденки чи декади), пронумеровані з початку року, йр.

сґ и <3£ - кількість робочих днів, перший та останній день у

р~ну інтервалі» 0і - загальне випереджування по деталі ] »

}=Т7й >> кр), деталь і застосовується в п виробах у

кількості ,т ) ) кожний віріб І виготовляється у

р-му інтервалі у кількості Іір , - витрата, деталей У на

випуск я вгробів у р-му плановому інтервалі, ,

дҐ=бҐ,О3. - план по деталі і на інтервал складає

кількість деталей, що дорівнює потребі на виріб, запланований до

випуску з <і[ по сі?’ :

~ ' , р . ~,р і , , ~ ,

чі^/к + V у-* + У-\,

р в В р в в+д в4 І 4 І Р в4 1+7 8414!

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

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

д = { тіпр' І рЧИ.гІ, £ V* > ^ ), = 0і .

' р =1 р=> ^

де С‘‘ - кількість виготовлених деталей J з початку року, с;^ -

кількість деталей J ь рахунок плану 9-го інтервалу.

' <3* якщо С*- 2 и 3 ; 2 У'і = О, г>д, г-остан. місяць

_ р=т ь „ р=ч+< розрахунку плану

Я-* = сі^ якщо 3 кі С-^ ^ &><3 та план на ч+не розра-

р=/ р хован

сі’ + |с^ / ЕМ ] - 1 в інших випадках.

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

Розглянемо модель обліку комплектності виготовлення виробів в підрозділах підприємтсва, яка вводить "псевдо-позамовний” облік виробництва по кожному виду продукції та підрозділу за

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

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

дорівнює: Я?. = І Ч£ V* + ( 2і* - <3- ) / й- * V- і, де

V ІрГі р я ч я і

- робочий день, на який забезпечена зборка виробу І виготовленими в підрозділі деталями J, <] - інтервалі у який попадає 2і. Забезпечений машинокомплект по виробу і: И3{ = шіп^СМ^). Робочий день 2(, на який зебезпечена зборка виробу і підрозділом розраховується аналогічно 23у якщо узяти замість О1. Для прийняття управлінських рішень використовуються показники -

дефіпит J-ї деталі на зборці 1-го виробу у и-й робо ми день:

■ри-і

% - Г ]* = \рї 7Г +(и\} 7 •

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

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

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

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

деталі <7° ; деталі що запізднюються деталі по

1 і?3 і> 4 41 і

яким не виконан план поточного р-го інтервалу; «7 },

.... «/£ ~*= +’}; "додаткові" деталі )-

Найвищий приорітет и-* мають деталі з «7?» найменший - з «7*.

«Я в?

Для кожної парт.і деталей по Л-му виду операції відома тривалість обробки & . Основні обмеження: умови забезпечення

виконання плана неявно задають директивні строки для

деталей з <7° та «7® директивний строк Для Леталей з

.....^ - 2У=2{--сГ; якщо 8-а дільниця не є першою дільницею

л Є» & & Р

на маршруті 3-о\ деталі, то необхідна наявність .7-х деталей, які ПРОЙШЛИ обробку На Попередній ДІЛЬНИЦІ, ТОбТО чи

; для /-і деталі необхідні матеріально-технічні ресурси СМТРЗ у кількості ія£ (у=1,У), які доступні 5-й дільниці з кількості ®он,я Р°б1тничого часу дільниці на зміну по Л-й групі

робочих місць дорівнює ¥ (/і=Т7Н). Задача полягає у складі..іні

черги обробки деталей множини на

& 5 Є & «> ® ®

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

де - час завершення обробки J-l деталі на 5-ій дільниці.

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

декомпозирувати множину </ на на підмножини^ для кожної

М групи робочих МІСЦЬ: 'геп=ит^н''ІІь'іТІн‘ • • • ■ •Далі

всі кроки виконуються окремо для кожної групи робочих МІСЦЬ:

кожна й-а група інтерпретується як один станок, тривалість детнллоперашя СробітЗ масштабується. Побудувати послідовність

8 п виконання множин робіт <7^ по критерію мінімізації

Ть = %н. О] ;

визначити послідовності | 2^, $

5^45"^ із збереженням черги. Для 5^ розрахувати забезпечення МТР відповідно з впорядкуванням. Забезпечені МТР роботи складають послідовність Я* . Роботи з й* назначити на робочі зміни.

»** ЄП, ГУ,

Результатом процедури є послідовності робіт - ГОТОВИХ

виконання, - не готових із-за відсутності МТР, 5“^ - не

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

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

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

/ = гаг ( ти ( - РрвН, О 1 ] ,

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

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

інтервалів за допомогою коефіцієнту ритмічності Для

ритмічної роботи дільниці необхідно виконання умови А що досягається при дД _ ? Я к.< £’ к)/к.-Н. . ,0 1

Р'еЬ. Ц£р. Рвь. [£р, р р Р єЬ. J

Розглянемо стисло модель та процедуру оперативного планування та управління складальним цехом з постовим спосібом кінцевої зборки. Для кінцевої зборки і основі плану випуску на п'ятиденку складаються позмінні графіки випуску готових виробів. Нехай І - множина виробів запланованих до випуску на р-ту п'ятиденну, 0){ - приорітет 1-го виробу. Дільниця кінцевої зборки складається з а постів. Для кожного виробу потрібна множина деталей «Г , що складається з підмножин та «Г® - деталі та вузли, установка яких на виріб можлива на посту і поза межами пос у, Іг~ *'чожина виробів длл зборки на і-я день, ~

множини деталей для ^го виробу на і-я робочий день. <1 г - мко-

жина деталей на складах, на дільницях цеху та на складах заводу.

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

/ = - йі ), ' де Г{ та - час завершення та початку зборки 1-го виробу.

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

V І е Іь визначити запезпечения деталями, що передані з

попередніх-за маршрутом цехів, робочий день зборки: = тіп

( 2сі ) та впорядкувати вироби з Іі по зменшенню ш{ та Одержана послідовність - Б1 ;

V і-го виробу, що стоїть в 5* на &-й позиції V J £, «Т

розрахувати в^(к) - дефіцит J-1 деталі (вузла) на початок Г-го дня, та Б^(к) - сумарне відставання деталей 1-го

виробу, підмножин ^ та : = щах 01,

^ '&?«> (Х-гЬи ^ Ш&Р«> (і~гЬ)-

де Р?? - використання J-\ деталі у і-му виробі, залишок

? 1

/-1 деталі після розподілу її на к-2 виробу з 3 , 2“^ - день, не який виконан план попереднім цехом, £^(к) та £>? - множини

дефіцитних деталей і-го виробу: &*(к> = (J\ J € «Ту, І)(:0.(к) > О), 1^<к} = { J |. J е ос(°(к) > О ) ;

послідовність виробів з множинами І^1к) та показниками

5пг*> и зДОО

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

Я(ЬУ' $п<ь)$ $я(к) для

послідовності 82. Цей та попередній крок повторюєтьс.' .до тих пір, поки график зборки не задовільнить диспетчера,- .

вироби з 5^ призначаються на закріплені за ним\* пост чи ■ простоючі пости, на зміни ігі+1,.... Б наслідок будуть одержані послідовності для кожного з з постів : Я™,...........

V / розрахувати - кількість У-1 деталі у дефіциті н аміни !■,£■+?,...д”, які включаються у множину термінових детелея для усіх попереднх цехів.

Процедура має полін«>міальну обчислювану складність.

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

В роботі досліджена вказана задача і для її вирішення розроблен ефективний алгоритм. Математична постановка наступна. Задана множина незалежних завдань J=iJ VJ г,. ..>Jnh які складаються з однієї операції» VJ задані lj- тривалість виконання, tOj

- ваговий коефіцієнт та Dj- директивний строк. Завдання надходять у систему одночасно в момент часу J-TTii,

переривання не допускаються. Побудувати розклад для одного станка по критерію

/ = £ Wj * тах( О, - DJ ) •

Уведем ряд визначень.

Визначення. Перестановкою називається процедура переносу завдання J на позицію g (J<g) і, одночасно, завдань J+7,...,g на

ПОЗИЦІЇ

Визначення. Встроюванням називається процедура переносу завдання g на позицію р (g>p) та, одночасно, завдань p,...,g-7 на позиці і р+/,...,g.

Визначення. Послідовністю називаюг ся завдання

множини J впорядковані ао зменшенню відносини ,я) •

Затвердження І. Якщо у 0у11 зап і з днюючим завданням не попереджують завдання з резервом часу, то не існує переносів завдань, що призводять до покращення цільової функщ-.

Затвердження 2. Встроювання запізднюючого завдання g на позицію І < р , може привести до погіршення цільової функції.

Затвердження 3. Запізднююче завдання g у оуп в результаті встроювання може зайняти більш ранішу позицію, що призведе до покращення цільової функції тільки якщо у 0у11 З z : D - Т > О.

VTT Z Z е

Затвердження 4. Якщо в ojr ні для жодного з запізднюючихся завдань g не існує завдань в ( в < g ) для яких виконується

та ^а_ї>в>СІ’ ^e>0g~^s' то ' нв 1снує перестановок та

встроювань, що призводять до погіршення цільової функиї:

Визначення. Процедурою вільної перестановки називається

перестановка завдання к на позицію q ( k < ] ) при умові W 1 3 Dj < Tj . ...

Визначення. Послідовністю, яка одержана в результаті

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

Затвердження 5. Затвердження 2, 3 та 4 справедливі д"я осп. Затвердження Є. Для послідовності осп не існує перестановок та встроювань, що призводять до покращення цільової функцч, якщо виконуються умови: В^Т^О, V 3=і ,р, ;

V І=Т7Т ; В -Т Ю, ; О -Т ф, V /=Т7п.

•/ 0 1с.

Визначення. Послідовністю а називається послідовність

СІІ

одержана зо. у результаті виконання ряду перестановок

та встроювань покращуючих цільову функцію. _

Визначення Конкурентним називається запізднююче завдання 8 у послідовності ок, якщо З І •, І < g, 1 Ог<Т .

Введемо правила позначок у послідовності о* при -виконанні перестановок та встроювань, які позначають будь яке завдання, що порушує вихідну послідовність 0у11 та використовує резерви, завдань з більш вищим приорітетсм: •

при перестановці завдання І на позиці» 8 знаком * позначити усі завдання і ,8^ • для яких ш{/Т{<шг/71 и Сі-!Г{<0 ).-

при встроюванні завдання в на позначку р, завдання £

позначається, якщо існує завдання і: ії.Ір+1 ,£■/, ®(/7г

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

Св разі відсутності резервів) на (р,8~11 є завдання з

позначками. Умова встроювання завдання 8 на позицію р

Д/ V] - } + у > ле

Я*=(І*\Шр',8-1П, '

умова переставлення позначеного завдання я на позицію 8. в->

2 (ю.тіп(1 ,Т,-В.) - іу І... > О •

■ » ■> т З У п У

З=т+1 „

Затвердження в. Неконкурентні завдання у послідовності сг

СГГ

не можуть займати більш ранні позиції ніж в о .

Затвердження 9. Запізднююче завдання 8 на й-й ітерації у

послідовності ок не може бути встроєно на більш ранню позицію

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

V гс_Ґр,8~1} виконується £>г -■ Т £ О та для усіх позначених на Ір,8~1) завдань виконується V] (то )Ф

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

попередні завданння, що запізднюються ї на А-1-му кроці також ьиключеніз числа конкурентноздібних та V^ ( j^^p,£-11 )

виконується & и 11^/1^ уа^,'-я-

Затвердження II. Якщо на ітерації & у послідовності ок для конкурируючого завдання в З І:

в) І < > Тя-гв. ,) < итіпа^т^) ;

б) І < 8, 1>г > Те~Іг> .

и>.(Т~0) * 2 ю,тШІ ,тах(0,Т -І) )) < ь> т1п(1 ,Т -І> ) ;

» в • + | J J в * в в

то при виконанні (о) чи (0) переставлення завдання і на позицію 5 призводить до покращення цільової функції.

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

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

Визначення.' Множиною реалізація алгоритму називається сукупність алгоритмі*, що складаються з єдиного попереднього етапу та етапів оптимізації, що відрізняються один від одного порядком виконання процедур перестановок та встроювань.

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

• Затвердження ІЗ. Будь-яка реалізація запропонованого алгоритму приводить до одного я того же умовно-оптимального розкладу.

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

трудомісткості 0(п у більшості випадків виконується зрізаний С скорочений ) направления перебір.' Алгоритм е еврістичним С тому, що но% доведена ідентичність оптимального та умовно-оптимального розкладу та не одержано теоретичні оцінки похибки алгоритму), практична його обоснованість базується на статистичному аналізі достатньо великої кількості вирішених задач:

при вирішенні задач невеликої розмірності точним та

1Б

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

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

при вирішенні задач великої розмірності усі . побудовані умовно-оптимальні розклади краще розкладів побудованих відомим алгоритмом Шилда-Фрідмана.

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

В роботі наведено короткий опис розробленої автоматизованої системи оперативного управління основним виробництвом машинобудівного підприємства з змішаним серійним та дрібносе-ріяним типом виробництва та середнім по довжині циклом виготовлення основної продукції С АС ОУОП СТ), яка є сучасною системою розподіленої обробки даних, що функціонує в режимі реального часу та складається із сукупності автоматизованих робочих місць робітників, адміністративно-управлінського' та технічного персоналу. Функціонально АС ОУОП складається з підсистем: ведення НСІ, оперативного планування виробництва, обліку та аналізу виконання планів виробництва, оперативного обліку та аналізу руху деталей по підрозділам підприємства, оперативного регулювання виконання планів виробництва, оперативного матеріально-технічного забезпечення. У рамках ряду задач АС ОУОП СТ реалізовано описаний вище комплекс взаємозв’язаних моделей оперативно-виробничого ял; чуаання та управління Міжцехового та внутріпньоцехового рівня. Програмна реалізація виконана у сітьовому варіанті у середовищі СУБД ґохРго г2.0.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ '

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

2. Розробляй комплекс узгоджених моделей оперативно-вир<чіничого планування та управління для машинобудівного підприєм'-т».-) з розглядаемим типом виробнитва у сучасних умовах:

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

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

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

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

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

ПЕРЕЛПС ОСНОВНЫХ ПУБЛШАЩИ ПО ТЕМ1 ДНСЕРШЦГ

1. Павлов А.А., Мисюра Е.Б., Михайлов .В.В- Исследование

задачи минимизации суммарного взвешенного момента окончания

выполнения множества заданий о директивными сроками одним прибором / Киевск. политехи, ин-т. - Ни в, 19УЗ. - 26с. - Деи. в УкрНИИНТИ 29.06.93 N 1276 - УкЭЗ

2. Михайлов В.В. Алгоритм решения задачи минимизации суммвр-рного взвешенного момента окончания'выполнения югосвптза заданий о директивными сроками одним прибором / Киевск. политехи, ии-т.

- Киев, 1993. - 7 С. - Деп. в УкрНИИНТИ 29.08.93 N 1275 - УкЭЗ

. 3. Павлов А.А., Мисюра Е.Б., Михайлов В.В., Ковалюк Т.В.

Планирование выпуска продукции для мелкосерийного производства в условиях хозрасчета / Киевский политехн. институт. - Киев, 1389. Деп. 3 УкрНИИНТИ И 1991-УК8Э.-11 с.

4. Павлов А.А..Михайлов В.В.,Щербатенко 0,В.,Ковалш Т.В. Составление расписания выполнения частично упорядоченного множества работ по критерию минимизации общей длины расписания / Киевский политехн. институт, Киев, 1989, Деп. в УкрНИИНТИ й 706-Ук89 от 6.03.89.-11 с.

.5. ?йкайлов В.В., Щербатенко О.В., Ковелжж Т.В. Модели оперативного управления мелкосерийным сборочным производством./Моя-дународная научно-техн. конф. "Гибкая автоматизация'90". -

Братислава, 1990.

6. Михайлов В.В., Щербатенко О.В., Пика Е.Н. Алгоритм-месячного цехового номеяклатурно-обьомного планирования. / IV Мокра спу блик ан ск а я конференция "Актуальные проблемы разработки АСУ". - Киевский политехн. ин-т, Киев, 1990.

7. Павлов А,А., Михайлов В.В., Мисюра Е.Б., Жданова Е.Г. Пакет прикладных программ решения оптимизационных задач большой размерности/Материалы ш польско-ссв. научно-техн. конф. "Комплексная автоматизация промышленности".-Вроцлав,1939.-Ч.2,с.Э—1 б.

. 8. Павлов А.А., Михайлов В.В., Щербатенко О.В. Оптимизация

планирования процесса обработки деталей в ГАУ / Киев, политехн. ИН-т.-Киев, 1939.-9с. - Деп. в УкрНИИНТИ 07.06.89 № 10537 Ук89.

9 . Гриша С.Н., Щербатенко О.В., Михайлов В.В. Оптимизация технологического группирования деталей для ГПМ / Киев., политехн. ин-т. -Киев, 1989. - 7с. - Деп. в УкрНИИНТИ Об.03.89 N*705 Ук8Э.

Михайлов В.В. Алгоритмическое и прогрв.лмнов обеспечение автоматизированной системы управления дискретным производством смешанного типа. Рукопись. 05.13.06.-"Автоматизированные системы управления". Киевский политехнический институт. Киев 19Э4.

В диссертации рассмотрены особенности оперативно-производ-водственного планирования и управления на предприятиях со смешанным многономенклатурным серийным и мелкосерийным типом производства и средней длительностью цикла изготовления изделий в условиях перехода к рыночной экономике. Разработан и обоснован комплекс согласованных моделей и процедур автоматизированного межцехового и внутрицехового оперативно-производственного планирования и управления для предприятия с указанным типом производства. Исследована классическая in--трудаая задача теории расписаний - минимизация суммарного взвешенного момента окончания выполнения множеЬтва заданий с различными директивными сроками одним прибором. Разработан и качественно обоснован аффективный алгоритм решения указанной задачи. Результаты работы внедрены в составе автоматизированной системы оперативного управления основным производством машиностроительного предприятия.

Mikhailov V.V. Algorithms and software of the automatized control systems of the mixed type discreta manufacturing. Manuscript. 05.13.06-"Automatized control systems". Kiev, 1994. Kiev Po^ytechnical Institute. Kiev, 1994.

The dissertation deals with the peculiarities of the active - manufacturing planning and control in plants having the mixed multi-nomenclature aerial and low-serial manufacturing type and the middle-lasting cycle of the production under the conditions of the transition towards market economy. A great deal of the coordinated models and procedures of active-manufacturing planning and control has been elaborated and grounded especially for the plants with above-mentioned manufacturing type. The classic NP-task of. schedule theory ( вingle-machine schedule task with low cost linear function, different directive times and priorities ) has been ' researched and effective algorithm of the task Bolutlon has been elaborated and grounded qualitatively. These results has been introduced as a part of the machine-building plant automatized control system.

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