Русский  English
ДонНТУ   Портал магістрів

Зміст

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

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

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

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

    Науковою новизною володіють.

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

    • 3. Аналіз задач оптимізації теорії розкладів планування діяльності підприємства

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

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

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

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

    4. Огляд досліджень і розробок

    Задачі складання календарних планів рабіт відносятся до класу задач, вивчаємих в рамках теорії розкладів, зʼявившейся в 50-і роки XX сторіччя [3]. Розвитном даного направлення науки займалися відомі вчені: Беллман Р. [4], Гэри М., Джонсон C. [5], Брукс Г. Н., Брукер П., Конвей Р. [6], Максвелл В., Миллер Л., Танаев В. С.[3], Шкурба В. В. [3], Гордон В. С., Шафранский Я. Н., Прилуцкий М. Х. [7], Норенков И. П. [8], Лазарев А. А. та ін.

    Планування та складання розкладів НЕ нова тема. Методи планування та складання розкладів були запропоновані та проаналізовані принаймні з 1950-х років. Хоча існують методи для знаходження оптимальних рішень для деяких конкретних проблемних завдань планування, багато методи не працюють, коли структура обмежень або цілей змінюється. Наприклад, планування евристичний, що каже "запланувати задачу, яка використовує найменшу кількість ресурсів" може не виконуватися оптимально, коли проблема змінена, щоб включати в себе різні види ресурсів. Крім того, багато методи не працюють оптимально, коли стикаються з проблемами значного розміру. У багатьох випадках, просто знайти реальні рішення є непростим завданням. Загалом, проблема планування є NP-важким завданням, тобто там немає відомих алгоритмів пошуку оптимальних рішень за поліноміальний час. Існують алгоритми для вирішення саме деяких форм цієї проблеми, але вони, як правило, занадто довго обчислюються (тобто більш ніж за поліноміальний час), коли розмір задачі зростає або коли додаткові обмеження додаються. В результаті, велика частина досліджень була присвячена або спрощення завдань планування до точки, де деякі алгоритми можуть знайти рішення, або розробки ефективної евристики для пошуку оптимальних рішень. У деяких випадках це завдання може зводитися до пошуку допустимого рішення, і часто знаходження можливе рішення не може бути гарантовано.

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

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

    Генетичні алгоритми є методом стохастичного пошуку і введені в 1970 у Сполучених Штатах Джоном Холландом, в Німеччині Інго Рехенберге. На основі спрощень природних еволюційних процесів, генетичні алгоритми працюють на популяції рішень, а не на одному рішенні і використовують евристичні методи, такі як вибір, кросовер, і мутації розвиваються в найкраще рішення.

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

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

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

    5.1 Вербальне описання моделі

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

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

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

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

    У найбільш загальній формі завдання планування з обмеженими ресурсами і часом визначається наступним чином:

    Дано:

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

    • Задача включає в себу наступні характеристики:

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

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

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

    5.2 Математична постановка

    Вхідніе данні:

    1.     1..P — кількість продуктів, що виробляются

    2.    1..M — озагальна кількість видів машин

    3.     1..W — загальна кількість робіт, що виконуються на машинах 

    4.    Tp  – кількість часу, що піде на обробкуу p-го вирбу на m-ій машині. 

    5.     Techp — технологічний процес віробницства p-го віробу

    1,

    2

     

    6.     NTechp – кількість кроків, що входять до технологічного процесу виробництва p-го виробу

    7.     k – крок технологічної операції   k = 1..NTechp

    8.     3 – тривалість операції

    9.     5 – номер технологічної операції

    10.                       5 – Вартість переналагодження машини з одного виду роботи на іншу

    11.                       6

    Также дан двомірний масив розмірос M на W, елемент якого m,w визначає витрати на виконання w-й роботи на m-ії машині за одну одиніцю часу (якщо w-у роботу неможливо виконати на m-ії машині, то cm,w = +∞). 

    Невідомі:

    Невідомими є сукупність векторів завдань Xm, m = 1..M.

    Кожен такий вектор завдань описує план завантаження m-ї машини, а сукупність векторів завдань описує виробничій план підприємства по віробництву P виробів.

    Km — загальна кількість завдань для m-ї машині (у вигляді вектора)

    dm,k — це номер виробу, оброблюваного m-ю машиною в процесі k-ї роботи

    xm,k — це номер кроку технологічного процесу 7 виробництва dm,k-го виробу

    sm,k — це момент часу, в який починается виконання k-ї роботи m-ю машиною.

    Xm – план завантаження m-ї машини   m = 1..M (у вигляді вектора)

    8

    9

    Обмеження:

    По тривалості операції:

    10 

    За номером технологічної операції:

    11 

    k = 1..NTechp

    За технологічним процесом:

    12

     

    Цільовая функція

    Необхідно мінімізувати витрати (Accounts) на виконання виробничого плану:

    13.

     

    Поставлена ​​задача є задачею без переривань типу Job Shop. У вищеописаної постановці дана задача є NP-повною.

    6. Тестовый приклад: 3 віроби, 2 машини

    Дано

    Кількість верстатів M = 2, (верстати не взаємозамінні)

    Кількість видів робіт, виконуваних на верстатах, W = 5

    Витрати на виконання п'яти робіт (технологічних операцій) на двох верстатах:

    14

    Вартості переналагодження робіт на 1-ймашині (рядок - попередня, стовпець наступна):

    15

    Вартості переналагодження робіт на 2-й машині:

    16

    Час переналагодження робіт на 1-й магині (рядок - попередня, стовпець наступна):

    17

     

    Час переналагодження робіт на 2-й машині:

    18

    Кількість вироблених виробів P = 3

    ·        перший виріб треба виготовити протягом не більше ніж T1 = 100 одиниць часу (від початку обробки)

    Технологічний процес для 1-го виробу Tech1 = {(1,20), (4,30), (5,10)} (це означає операція 1 - 20 од. часу, операція 4 -  30 од. часу, операція 5 - 10 од. часу)

    Кількість кроків технологічного процесу для 1-го виробу NTech1 = 3

    ·        другий виріб треба виготовити протягом не більше ніж T2 = 140 одиниць часу

    Технологічний процес для 2-го виробу Tech2 = {(1,30), (2,10), (3,20), (5,20)}.

    Кількість кроків технологічного процесу для 2-го виробу NTech2 = 4

    ·        третій виріб треба виготовити протягом не більше ніж T3 = 140 одиниць часу

    Технологічний процес для 3-го виробу Tech3 = {(1,30), (2,10), (3,20)}.

    Кількість кроків технологічного процесу для 3-го виробу NTech3 = 3

     

    Невідомі

    19

    Цельовая функія

    Необхідно мінімізувати витрати (Accounts) на виконання виробничого плану:

     

    20

     

    Обмеження

     

    21

     

    Рішення

    K1 = 6, K2 = 4 -  кількість етапів робіт на кожній машині

    X1={(1,1,0), (1,3,20),(1,2,40),(2,2,73),(3,2,88),(3,3,113)};

    X1={(2,1,20), (3,1,53),(2,3,63),(4,2,108)};

    На першій машині виконуються такі завдання:

    1)      1-й етап обробки (технологічного процесу виробництва) 1-го виробу, починається в момент часу 0;

    2)      1-й етап обробки (технологічного процесу виробництва) 3-го виробу, починається в момент часу 20;

    3)      1-й етап обробки (технологічного процесу виробництва) 2-го виробу, починається в момент часу 40;


    4)     2-й етап обробки (технологічного процесу виробництва) 2-го виробу, починається в момент часу 73;

    5)      3-й етап обробки (технологічного процесу виробництва) 2-го виробу, починається в момент часу 88;

    6)      3-й етап обробки (технологічного процесу виробництва) 3-го виробу, починається в момент часу 113.

    На другій машині виконуються такі завдання:

    1)      2-й етап обробки (технологічного процесу виробництва) 1-го виробу, починається в момент часу 2;

    2)      3-й етап обробки (технологічного процесу виробництва) 1-го виробу, починається в момент часу53;

    3)      2-й етап обробки (технологічного процесу виробництва) 3-го виробу, починається в момент часу 63;

    4)      4-й етап обробки (технологічного процесу виробництва) 3-го виробу, починається в момент часу 108.

     

    22

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

    A (X1,X2) = 2*1+2*1+3*1+1*3+2+2*2+3+2*3+2+3*2+1*2+2+1*2+2*2+2*2=47 д.ед.

     

    7. Рішення задачі, розроба алгоритма

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

    Висновки

    У даній роботі сформована математична постановка задачі календарного планування випуску безлічі виробів на безлічі машин. Дана задача відноситься до класу задач календарного планування з обмеженими ресурсами. На підставі аналізу методів вирішення даного класу завдань був обраний евристичний метод, заснований на генетичному алгоритмі.

    Отримано сукупність векторів завдань Xm, m = 1..M. Кожен такий вектор завдань описує план завантаження m-ї машини, а сукупність векторів завдань описує виробничий план підприємства з виробництва P виробів.

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

    Список джерел

    1.  Мышенков К. С., Романов А. Ю. Система управления ремонтами оборудования, как элемент системы стратегического управления предприятием // Стратегическое управление организациями: проблемы и возможности современной экономики: Сб. науч. тр. – СПб.: Изд-во Политехн. ун-та, 2009. – Ч. 1. – С. 77-83.

    2. Романов А. Ю. Структурный анализ системы управления ремонтами оборудования кондитерской фабрики // Общеуниверситетская науч. конф. молодых ученых и спец.: Сб. матер. / Отв. ред. С. А. Хуршудян. – М.: Изд. комплекс МГУПП, 2009. – С. 305-311.

    3.        Танаев В. ., Шкурба В. В. Введение в теорию расписаний. – М: Изд-во «Наука», 1975. – 256 с.

    4.    Bellman R., Gross O., Some combinatorial problems arising in the theory of multistage processes // Journ. Soc. industr. and appl. mathematics. – Vol. 2. – No. 3. – 1945.

    5.        Johnson, S.M. Optimal two- and three-stage production schedules with setup times included // Nav. res. log. quart. – Vol. 1. – No. 1. – 1954.

    6.        Конвей Р. В. Теория расписаний / Р. В. Конвей, В. Л. Максвелл, Л. В. Миллер. – М.: Наука, 1975.

    7.     Батищев Д. И., Прилуцкий М. Х., Гудман Э. Д., Норенков И. П. Метод комбинирования эвристик для решения комбинаторных задач упорядочения и распределения ресурсов // Информационные технологии, – 1997. –  2. – С.29-32.

    8.        Норенков И.П. Комбинированные и генетические алгоритмы составления расписаний в задачах проектирования // Вестник МГТУ им. Н. Э. Баумана. – 1995. – №2. – С. 36-43.

    9.        Мышенков К. С., Романов А. Ю. Постановка задачи составления календарного плана ремонтов оборудования предприятия // Системный анализ в проектировании и управлении: Cб. науч. тр. XIV Междунар. науч.-практ. конф. / СПбГПУ. – СПб.: Изд-во Политехн. ун-та, 2010. – Ч. 1. – С. 240-243.

    10.   Hartmann S. A. Competitive Genetic Algorithm for Resource-Constrained Project Scheduling, Naval Research Logistics. – Vol. 45. – 1998. – pp. 733-750.

    11.   Hartmann S. A Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraints, Naval Research Logistics – Vol. 49. – 2002. – pp. 433-448.

    12.   Holland H. J. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.

    13.   Wall M. B. A Genetic Algorithm for Resource-Constrained Scheduling, Massachusetts Institute of Technology, 1991

    14.   Higgins P.G. Job Shop Scheduling: Hybrid Intelligent Human-Computer Paradigm, Department of Mechanical and Manufacturing Engineering The University of Melbourne, 1999

    15.   Shyh-Chang Lin, Erik D. Goodman, William F. Punch III, Investigating Parallel Genetic Algorithms on Job Shop Scheduling Problems, Michigan State University, 1995

    16.   Caelier J. and Pinson E., “An Algorithm for Solving the Job-shop Problem,” Management Science, vol. 35, pp. 164-176, 1989.

    17.   Grabowski J., Nowicki E., and Zdrzalka S. “A Block Approach for Single  Machine Scheduling with Release Date and Due Date,”  European J. Oper. Res., vol. 26, pp. 278-285, 1986.

    18.   Manderick B. and Spiessens P. “Fine-Grained Parallel Genetic Algorithms,” Proc. Third Int’l Conf. on Genetic Algorithms, pp.428-433, Morgan Kaufmann, San Mateo, CA, 1989.

    19.   Bierwirth C. “A Generalized Permutation Approach to Job-Shop Scheduling with Genetic Algorithms,” OR-pektrum, Special Issue: Applied Local Search, Pesch E. and Vo S. (eds), vol. 17, No. 213, pp. 87-92, 1995.

    20.   Davis L., “Job-Shop Scheduling with Genetic Algorithms, ”Proc. Int’l Conf. on Genetic Algorithms and their Applications, pp. 136 - 149, Lawrence Erlbaum, Hillsdale, NJ, 1985.