ДонНТУ   Портал магистров

Кондрашук Виктория Валериевна

Факультет менеджмента

Кафедра экономической кибернетики

Специальность Экономическая кибернетика

Оптимизация расписаний на производстве с использованием генетических алгоритмов в условиях ограниченных ресурсов

Научный руководитель: к.ф.-м.н., доц. Ситникова Ольга Дмитриевна

Резюме Биография Реферат Библиотека Ссылки Отчет о поиске Индивидуальный раздел

Реферат по теме выпускной работы

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования, планируемые результаты
• 3. Анализ задач оптимизации теории расписаний планирования деятельности предприятия
• 4. Обзор исследований и разработок
• 5. Постановка задачи
• 5.1 Вербальное описание модели
• 5.2 Математическая постановка
• 6. Тестовы пример 3 изделия, 2 станка
• 7. Решение задачи, разработка алгоритма
• Выводы
• Список источников

Введение

В наше время задачи составления расписаний широко распространены во многих областях экономики.

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

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

1. Актуальность темы

В условиях рыночной экономики работа по единичным и небольшим заказам становится характерной чертой современных машиностроительных предприятий.

Для организации производства продукции отдельными партиями в сроки, устраивающие заказчиков необходимо: автоматизация производственных процессов, обеспечиваемая компьютерными системами проектирования; использование на производстве оборудования с числовым программным управлением и компьютерное управление комплексами технологического и сервисного оборудования позволяют организовать выпуск продукции партиями в сроки.

Формой организации производства служит технология "точно вовремя" (Just in time, JIT-технология), при которой перемещение изделий в процессе производства и поступления от поставщиков заказов тщательно спланированы во времени так, что на каждом этапе процесса следующая работа выполняется в тот момент, когда предыдущая работа завершена.

Производство становится бесперебойным, исключаются простои оборудования, неритмичную сборку, снижаются затраты на переналадку станков.

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

Автоматизация решения задачи календарного планирования (календарного производства) данной проблемы помогает снизить общее время, потраченное на производство изделий. Разработка программной среды, позволяющей в автоматизированном режиме составлять оптимальное производственное расписание для производства множества видов изделий на множестве станков с разными видами работ, является актуальной.

2. Цель и задачи исследования, планируемые результаты

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

Для достижения этой цели в работе решены следующие задачи:

выполнена математическая формулировка задачи календарного планирования и составлена математическая модель производства;

разработан алгоритм календарного планирования производства на базе теории эволюционных вычислений;

выполнена программная реализация данного алгоритма.

Объектом исследования является формирование оптимального по времени расписания синхронного производства множества видов изделий на множестве станков в условиях ограниченных ресурсов.

Предметом исследований есть методы, алгоритмы и программные средства формирования оптимального по времени расписания.

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

Научной новизной обладают.

математическая постановка задачи и ее реализация с помощью генетического алгоритма для поиска оптимального решения по текущим критериям подачи заготовок на станки для обработки;

формализованное описание процедур оптимизации календарного плана производства, основанных на применении генетического алгоритма.

3. Анализ задач оптимизации теории расписаний планирования деятельности предприятия

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

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

Данная работа описывает генетический алгоритм для нахождения оптимальных решений динамических задач планирования в условиях ограниченных ресурсов. Единый алгоритм обеспечивает перспективную производительность на многих различных объектах деятельности с общими проблемами. В то время как традиционные методы планирования используют поисковые или эвристические методы, характерные для моделей проектов в ограниченной формулировке, новый метод на работает большой предметной области. Представление обеспечивает очередностью, и целевая функция измеряет ресурсы нарушения ограничений и общую производительность. В самом общем виде задача с ограниченными ресурсами планирования спрашивает следующее: учитывая некий комплекс мероприятий, набор ресурсов, измерение эффективности, какой план является наиболее оптимальным, чтобы назначить ресурсы для деятельности таким образом, чтобы производительность была максимальна? Общая задача инкапсулирует множество вариаций, таких как виды работ, планирование производства, и проблему с ограниченными ресурсами календарного планирования.

Стоит отметить, что планирование задач динамично, и основано на неполных данных. В расписании нет статичности, пока проект не завершен и большинство планов может изменяться сразу. В зависимости от продолжительности проекта тоже может быть определено и для целей. Динамика может быть связана с плохими оценками, неполными данными или непредвиденными помехами.

4. Обзор исследований и разработок

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

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

Многие методы решения были предложены и реализованы. Раньше подходы решения упрощали варианты проблемы точно, но исследователи быстро поняли, что реальные проблемы слишком велики и сложны для любого точного решения. Например, деревья решений были использованы перечисления всех возможные выборов. Затем были разработаны эвристические методы, чтобы найти оптимальные решения, или просто найти возможные решения для действительно сложных проблем. Большинство исследований в настоящее время состоит из проектирования лучшей эвристики для конкретных типов задач планирования. Тем не менее, эвристические решения, как правило, ограничиваются определенным набором ограничений или постановкой задачи, и разработка новых эвристик весьма затруднительны.

Комбинаторные задачи планирования привели многих исследователей к экспериментам с генетическими алгоритмами, как методом решения. Они расхвалили их за способность решать нелинейные и комбинаторные задачи, генетические алгоритмы обычно хорошо работать на задачах, в которых цель или пространство поиска объединяет обе дискретные и непрерывные переменные. Они также часто эффективно применяются для поиска больших, мультимодальных задач, так как они работают на популяции решений , а не на одного человека и не используют градиент или другую конкретную информацию.

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

Хотя генетические алгоритмы были изучены более 60 лет назад, их реализация зачастую в такой же степени искусство как проектирование эффективных эвристических методов. Большая часть литературы о генетических алгоритмах посвящена относительно простым проблемам. Упрощенное применение генетического алгоритма к небольшим проблемам часто дает неплохие результаты, но наивное применение генетических алгоритмов в более серьезных проблемах часто приводит к снижению производительности. Это связано как с характером генетического поиска и взаимосвязями между генетическим представлением и генетическими операторами. Прямое представительство проблем, т.е. использование отличных битовых строк типов данных, обещает дальнейшие улучшения в применении генетического алгоритма, надежности и производительности.

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

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

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

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

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

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

В процессе производства при изменении любой из характеристик возникает затрата времени на переналадку оборудования.

В наиболее общей форме задача планирования с ограниченными ресурсами и временем определяется следующим образом:

Дано:

Комплекс мероприятий, которые должны быть выполнены

Набор ресурсов для осуществления деятельности

Набор ограничений, которые должны быть выполнены

Набор целей, для вывода наиболее результативного расписания, при котором осуществляется присвоение ресурсов для деятельности в определенное время такое, что все ограничения выполнены и достигнута максимальная эффективность.

Задача включает в себя следующие характеристики:

каждая задача может быть выполнена в более чем одним образом в зависимости от ресурсов, которые завязаны на нее;

задача отношений предшествования может включать в себя перекрытие так, что данная задача может начаться, когда предшествующая закончена полностью или частично;

каждая задача может быть прервана в соответствии с заранее определенным набором прерывания режима (специфичные для каждой задачи), либо без прерывания;

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

ресурсы могут быть возобновляемыми (труд, машины), не возобновляемыми (сырье);

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

ресурсы могут иметь временные ограничения;

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

доступность ресурса может изменяться;

требование ресурса могут изменяться;

цели могут изменяться;

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

Входные данные:

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

Исследования на данном этапе проведены не полностью. Данная магистерская работа будет завершена в декабре текущего года.

Выводы

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

Получена совокупность векторов заданий X_m, 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.