Реферат з теми випускної роботи

Вступ

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

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

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

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

Мета і завдання дослідження

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

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

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

Актуальність

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

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

Запланована наукова новизна

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

Огляд досліджень по темі

Вітчизняні

    За результатами пошуку серед матеріалів порталу магістрів ДонНТУ були знайдені роботи Гливка А. Г., Хаустова Д. О., Сергєєва О. Ю., в яких розглядаються проблеми оперативно-календарного планування в різних галузях. З наукових робіт викладачів нашого університету з даної теми були знайдені роботи Секірін О. І.

    В цілому по Україні було знайдено безліч робіт по суміжних областях з розроблюваної підсистемою. Можна виділити також існуючі розробки з даної теми: СПРУТ-ОКП и Zenith SPPS.

Закордонні

    Основна маса робіт по даній темі є закордонною. Можна зробити висновок, що на заході дана тема набагато краще опрацьована, внаслідок того, що там постійно удосконалюються засоби виробництва. З зарубіжних авторів можна виділити: M. Dorigo, G. Di Caro, Rong Zhou, Alan S. Manne. Із закордонних готових систем можна виділити: LEKIN и TACTIC.

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

Постановка завдання дослідження

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

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

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

    

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

    Наведений приклад задачі ми можемо пов'язати з диз'юнктивні графом G = (V, A, E), де V набір вузлів, A - з'єднувальний набір дуг, і E - диз'юнктивні набір дуг. Вузли V відповідають всім операціям і двом фіктивним вузлам, джерелу і виходу. Сполучні дуги A представляють відносини передування між операціями для кожної деталі, а диз'юнктивні дуги E представляють всі пари операцій, які будуть виконані на тому ж самому верстаті. Всім дугам, вихідних від вузла, присвоюється тривалість обробки операції. Біля джерела є сполучні дуги з нульовою довжиною для всіх перших операцій кожної деталі, а біля виходу є сполучні дуги, вихідні з усіх останніх операцій. Планування, яке виконується, відповідає вибору однієї дуги від кожної диз'юнктивній дуги і з'єднується таким чином, щоб отриманий спрямований граф був нециклічним, тобто щоб у ньому не було петель. Проблема зменшення періоду обробки зводиться до виявлення ряду диз'юнктивних дуг які мінімізують довжину критичного шляху в направленому графі. [2]

Опис мурашиних алгоритмів

    Для вирішення даної задачі були обрані мурашині алгоритми (МА), які засновані на використанні популяції потенційних рішень і розроблені для вирішення задач комбінаторної оптимізації, перш за все, пошуку різних шляхів на графах. Кооперація між особинами (штучними мурашками) тут реалізується на основі моделювання «stigmergy». При цьому кожен агент, званий штучним мурахою, шукає рішення поставленої задачі. Штучні мурашки послідовно будують рішення завдання, пересуваючись по графу, відкладають феромон і при виборі подальшого ділянки шляху враховують концентрацію цього ферменту. Чим більше концентрація феромону в подальшому ділянці, тим більше ймовірність його вибору.[3]

    Як ілюстрацію візьмемо завдання пошуку найкоротшого шляху між двома вузлами графа G = (V, E), де V - безліч вузлів (вершин), а E - матриця, яка представляє зв'язку між вузлами. Нехай - число вузлів у графі. Позначимо – довжину шляху в графі, пройденого k-м мурахою, що дорівнює числу пройдених дуг (стрибків між вершинами) від першої до останньої вершини шляху. Приклад графа з виділеним шляхом представлений на малюнку 1. З кожною дугою, що сполучає вершини (i, j) асоціюємо концентрацію феромона .

Рисунок 1 Приклад просування по графу (анімація: об'єм - 36кб, розмір - 407Х264, кількість кадрів - 6, затримка між кадрами - 300 мс, кількість циклів повторення - безперервний цикл повторення).

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

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

(1)

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

(2)

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

(3)

    где - число мурашок. З (3) випливає, що загальна концентрація феромона для даної дуги пропорційна «якості» шляхів, в які входить ця дуга, оскільки відкладаєме відображає «якість» відповідного шляху [5].

Схема роботи алгоритму

    Наведемо формалізований алгоритм роботи даної системи:

1. Формування графа виробничого цеху з урахуванням необхідності обробки заданого числа деталей;
2. Ініціалізація параметрів алгоритму;
3. Створення мурашиної колонії і розміщення її в початковому пункті;
4. Побудова схеми переходів між вершинами графа;
5. Вибір найбільш оптимального маршруту (на підставі раніше вибраних евристик);
6. Оновлення феромона.

    Пункти 3) - 6) повторюються до тих пір, поки не буде досягнутий необхідний результат.

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

1. Закінчення при перевищенні заданого числа ітерацій;
2. Закінчення зі знайденого прийнятного рішення ;
3. Закінчення, коли протягом декількох запусків не було відзначено повторних змін;
4. Закінчення, коли всі мурашки йдуть одним і тим же шляхом.

Висновок

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

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

Список літератури

1. Система оперативно-календарного планування автоматизованого механообробного дрібносерійного виробництва на основі комплексних моделей: дисертація д-ра техн. наук Загідулліна Равіля Рустембековіча: 05.13.06 Уфа, 2006 448 с. РГБ ОД, 71:07-5/452.
2. Swarm Intelligence. Focus on Ant and Particle Swarm Optimization, 2007 I-Tech Education and Publishing.
3. Ройові алгоритми, курс лекцій, Скобцов Ю.О., 2009 г.
4. [202] M. Dorigo and G. Di Caro. The Ant Colony Optimization Meta-Heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 11-32. McGraw-Hill, 1999.
5. Donald W. Fogarty, Yohn H. Blackstone, Yr. And Thomas R. Hoffman. Production and Inventory management (Cincinnati: South - Western Publishing, 1991). P. 452 - 453.
6. Штовба С.Д. Мурашині алгоритми / / Exponental Pro. Математика в додатках, 2003, №4, с. 70-75
7. Офіційний сайт СПРУТ-ОКП. URL: http://sprut.ru/productsandservices/mrpii
8. Офіційний сайт Zenith SPPS. URL: http://www.zspps.com/soft.html
9. Особистий сайт M. Dorigo. URL: http://iridia.ulb.ac.be/~mdorigo/HomePageDorigo/
10. Перелік наукових статей G. Di Caro. URL: http://www.idsia.ch/~gianni/my_publications.html
11. Перелік наукових статей Rong Zhou. URL: http://www2.parc.com/isl/members/rzhou/pub-cat.html
12. On the Job Shop Scheduling Problem. URL: http://ideas.repec.org/p/cwl/cwldpp/73.html
13. Офіційний сайт LEKIN. URL: http://www.stern.nyu.edu/om/software/lekin/index.htm
14. Офіційний сайт TACTIC. URL: http://www.waterloo-software.com/

При написанні даного автореферату магістерська робота ще не завершена. Остаточне завершення: грудень 2010 р. Повний текст роботи й матеріали по темі можуть бути отримані в автора або його керівника після зазначеної дати.

© ДонНТУ 2010, Чорний М.С.