Содержание к диссертации
Введение
Глава 1. Современное состояние вопроса, цель и задачи исследования 9
1.1 Актуальность ЛТ-организации производства 9
1.2 Проблема составления расписаний для производственных подразделений по принципу «точно вовремя» 12
1.3 Практический опыт «точно вовремя» 14
1.4 Обзор систем оперативно-календарного планирования 17
1.4.1 Система «ФОБОС» 18
1.4.2 Система «Zenith SPPS» 22
1.5 Практические методы календарного планирования 26
1.6 Критерии эффективности расписания для ГПС 30
1.7 Цель и задачи исследования 34
1.8 Выводы по первой главе 36
Глава 2 Формализованное представление автоматизированного синтеза расписания 37
2.1 Моделирование автоматизированных производств методом циклограмм 37
2.2 Концептуальная модель автоматизированного синтеза"ЛТ-расписаний 41
2.2 Алгоритмы модели работы производственной системы 48
2.2.1 Входные и выходные данные модели производственной системы 49
2.3 Формализация процессов функционирования ПС 51
2.4 Программная реализация модели и ее тестирование 65
2.4.1 Проверка адекватности компьютерной модели производственной системы 67
2.5 Выводы по второй главе 77
Глава 3 Разработка процедур синтеза производственного расписания 78
3.1 Выбор метода синтеза производственного расписания 78
3.2 Определение способа представления хромосом 84
3.2.1 Задача коммивояжера 84
3.3 Определение структуры популяции 91
3.1 Описание операторов скрещивания 95
3.1.1 Кроссинговер основанный на идее построения множества Кантора 95
3.1.2 Циклический кроссинговер 101
3.2 Достоверность нахождения оптимального производственного расписания 106
3.3 Выводы по третьей главе 111
Глава 4 Исследование системы автоматизированного синтеза производственных расписаний 112
4.1 Оценка сходимости генетического алгоритма 114
4.2 Исследование системы при изменении количества оборудования 117
4.3 Оценка составления производственного расписания при изменении вероятности мутации 118
4.4 Влияние количества смен работы оборудования на эффективность составления производственного расписания 124
4.5 Статистические исследования 126
4.6 Выводы по четвертой главе 129
Заключение 131
Список использованных источников 133
Приложение а 146
Приложение б 155
Приложение в 169
Приложение г 171
ПРИЛОЖЕНИЕ Д
- Проблема составления расписаний для производственных подразделений по принципу «точно вовремя»
- Концептуальная модель автоматизированного синтеза"ЛТ-расписаний
- Определение способа представления хромосом
- Исследование системы при изменении количества оборудования
Введение к работе
Актуальность темы. Работа по единичным заказам становится характерной чертой современных машиностроительных предприятий. Информатизация производственных процессов, обеспечиваемая компьютерными системами автоматизации проектирования, подготовки производства и управления, использование производственного оборудования с числовым программным управлением и компьютерное управление комплексами технологического и сервисного оборудования позволяют организовать выпуск продукции партиями от одного изделия и в сроки, устраивающие потребителей.
В условиях позаказной работы предприятия формой организации производства служит «точно вовремя» (Just in time, ЛТ-технология), при которой перемещение изделий в процессе производства и поступления от поставщиков тщательно спланированы во времени - так, что на каждом этапе процесса следующая партия прибывает для обработки точно в тот момент, когда предыдущая партия завершена.
Производство перестает быть серийным со всеми свойственными ему недостатками - «незавершенкой», замораживающей оборотные средства, неритмичной сборкой, мало способствующей стабильности качества продукции, непроизводительными простоями оборудования.
Применение системы «точно вовремя» повышает конкурентоспособность компаний за счёт выпуска более широкого ассортимента продукции при невысокой стоимости, хорошем качестве и минимальном производственном цикле. Все это происходит благодаря устранению потерь в процессе производства.
Однако, при всех достоинствах, ЛТ-технология обладает существенными недостатками: сложность обеспечения высокой согласованности между стадиями производства продукции; значительный риск срыва производства и реализации продукции.
Независимо от причины возникновения рассогласованности между стадиями производства, предприятию приходится производить оперативное перепланирование производственного цикла на предмет перестроения нового оптимального производственного расписания. Отсюда следует, что разработка программной среды, позволяющей в автоматизированном режиме составлять оптимальное производственное расписание для предприятий, работающих по принципу «точно вовремя», является актуальной.
Настоящая работа выполнена в рамках госбюджетной научно-исследовательской работы № 01000000120 «Разработка интеллектуальных систем автоматизированного проектирования и управления» на кафедре систем автоматизации производства Оренбургского государственного университета (ОГУ). Этапы работы финансировались в рамках выполнения грантов № 1.4.06 «Разработка методологии создания высокоэффективных производственных систем нового поколения с заданными свойствами» и №2.1.2/3596 «Применение эволюционных методов оптимизации в параметрическом синтезе гибких производственных систем», выполняемых в соответствии с аналитической ведомственной целевой программой «Развитие научного потенциала высшей школы».
Цель работы - повышение эффективности функционирования машиностроительных предприятий на основе разработки автоматизированных средств оперативного синтеза оптимальных производственных расписаний.
Задачи исследования:
анализ существующих систем составления производственных расписаний;
разработка математического обеспечения инструментальных средств для автоматизированного синтеза производственных расписаний;
алгоритмическая и программная реализация процедур имитационного моделирования производственных систем;
разработка процедур синтеза оптимального производственного расписания;
получение зависимостей влияния параметров алгоритма синтеза на процесс составления производственного расписания.
Объект исследования - процесс формирования расписаний функционирования производственных подразделений разного уровня автоматизации в условиях позаказной работы предприятия.
Предмет исследования - формализация процесса синтеза оптимальных расписаний по текущим критериям эффективности работы производственного оборудования.
Методы исследования. Использованы основные положения теорий производительности, расписаний, массового обслуживания, методы математического моделирования, метод циклограмм, математической логики, методы эволюционного синтеза, технология объектно-ориентированного программирования.
Для подтверждения достоверности разработанных моделей и их программной реализации использованы методы оценки чувствительности модели, формальных процедур верификации, проверки на тестовых примерах, сравнения полученных результатов моделирования с результатами работы программы-аналога, натурные испытания.
Научной новизной обладают:
математическое обеспечение автоматизированного синтеза расписаний, основанное на использовании метода циклограмм для моделирования работы оборудования и генетических алгоритмов для поиска оптимальной по текущим критериям очереди запуска заготовок в обработку;
компьютерная модель работы производственной системы, состоящей из произвольного числа технологических модулей различного функционального назначения, транспортных средств и накопителей разной компоновки;
формализованное описание процедур оптимизации очереди запуска изделий в обработку, основанных на применении генетического алгоритма, целевая функция в котором рассчитывается по результатам моделирования;
выявленные с использованием разработанной компьютерной модели закономерности влияния генетических операторов на процесс оптимизации и точность получаемого ЛТ-расписания.
Практическую значимость имеют:
- алгоритм имитационного моделирования работы производственной систе-
мы с широким диапазоном структурно-параметрической настройки производственного оборудования и маршрутных технологических процессов;
генетический алгоритм синтеза оптимального расписания работы производственного участка, основанный на путевом представлении операторов крос-синговера;
программное средство «Расписание», позволяющее по заданным моментам выпуска изделий произвольной номенклатуры и в зависимости от состава и параметров производственного оборудования рассчитать требуемые моменты запуска заготовок в обработку по разным критериям эффективности функционирования производства.
Результаты, выносимые на защиту:
математическое обеспечение инструментальных средств для автоматизированного синтеза ЛТ-расписаний;
формализованное описание функционирования производственного участка с комбинированным составом оборудования с использованием метода циклограмм;
математическое и алгоритмическое обеспечение процедур оптимизации производственного расписания, основанное на путевом представлении операторов кроссинговера;
программное средство «Расписание», позволяющее в зависимости от состава и параметров производственного оборудования и изготавливаемых изделий сформировать оптимальное по текущим критериям эффективности расписание работы производственного оборудования.
Реализация работы. Результаты работы в виде программы синтеза оптимальных расписаний «Расписание» (свид. № 2009614057 от 30.07.2009) и методических указаний по ее использованию внедрены в учебный процесс кафедры систем автоматизации производства ОГУ, приняты к внедрению на предприятиях ОАО «ПО "Стрела"» (г. Оренбург) и ООО «Технопром» (г. Оренбург).
Апробация работы. Основные результаты диссертационной работы обсуждались и получили одобрение на международных научно-практических конференциях «XVII Интернет-конференция молодых ученых и студентов по проблемам машиноведения» (Москва, 2005), «Авиация и космонавтика» (Москва, 2007 - 2008), «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2008), «Прогрессивные технологии в современном машиностроении» (Пенза, 2009), «Наука и образование: фундаментальные основы, технологии, инновации» (Оренбург, 2010); российских конференциях «Современные информационные технологии в науке, образовании и практике» (Оренбург, 2005), «Компьютерная интеграция производства и ИПИ-технологии» (Оренбург, 2009), 22-й научно-технической конференции молодых специалистов ОАО «ПО "Стрела"» (Оренбург, 2010).
Результаты работы докладывались на межкафедральном семинаре научной группы по информационной поддержке изделий машиностроения (ОГУ, 2009 -2010).
Публикации. По материалам диссертации опубликованы 20 работ, в том
числе: 3 - в журналах, включенных в «Перечень....» ВАК, 1 - монография, 2 -свидетельства о регистрации программных продуктов.
Структура и объем работы. Диссертация состоит из введения, четырех глав, общих выводов и результатов, списка использованных источников из 127 наименований. Работа выполнена на 177 страницах, включает 60 рисунков и 23 таблицы, 32 страницы приложений.
Проблема составления расписаний для производственных подразделений по принципу «точно вовремя»
Анализ влияния различных факторов на выполнение основного графика свидетельствует, что за счет коррекции производственного расписания можно добиться ликвидации до 75 % отклонений, в то время как баланс производственных мощностей дает не более 5% [90, 91, 101]. Ряд авторов [1,12, 58, 114, 115] по теории менеджмента выделяют три различных подхода к составлению графиков работы. Процедура составления графика при первом подходе, соответствует последовательности технологического процесса. Такой метод называют проталкивающим, так как указания проталкиваются через всю систему, начиная с са--мой первой стадии. Основной целью при составлении графика является повышение уровня загрузки оборудования. В основе последовательного календарного планирования лежит предположение, что материалы, используемые в производстве одного продукта, или покупатели, пользующиеся конкретной ус- лугой, всегда проходят через одну и ту же последовательность операций, или технологический маршрут. Весь процесс последователен и повторяем, стадии техпроцесса дискретны, и каждая последующая операция не может начаться до того, как завершится предыдущая, но и не обязана начинаться немедленно по ее завершении. При составлении планов-графиков обычно также предполагают, что вся партия обрабатывается совместно, как одна единица, и не переходит на следующую стадию до того, как будет полностью завершена ее обработка на предыдущей.
В последнее время финансовые и конкурентные воздействия привели к необходимости пересмотра целей и ограничения функционирования производственных систем (ПС) [28, 46, 57]. Это привело к появлению новых подходов к составлению расписаний, руководствующихся в первую очередь рыночным спросом и уделяющих первостепенное внимание не загрузке, а выпуску продукции: Эти подходы, известны как протягивающие, к которым относится и система «точно вовремя» [71, 56].
Зарубежные исследователи: [71у 114]! выделяют несколько этапов внедрения системы «точно вовремя»,-описанных далее. 1) Стандартизация, что требует разделения крупного производственного участка с широкой номенклатурой выпуска на несколько более мелких и независимых. Также может потребоваться рационализация самой номенклатуры и, в некоторой степени, перепроектирование, чтобы у продуктов появилось больше общих элементов. 2) Контроль качества. При отсутствии резервных запасовї любой де-фектныйшатериал или?комплектующая часть вызовут остановку производства, поэтому нужно добиться того, чтобы дефекты появлялись очень редко или отсутствовали вовсе. 3) Планово-предупредительное: обслуживание; Как и отклонения! в качестве, отказы оборудования недопустимы, поэтому необходимо эффективное профилактическое обслуживание: 4) Измененияівоборудовании (снижение-времени переналадки-и т.д.). 5) Планировка; В системе «точно вовремя» применяются;непрерывные поточные процессы; без межоперационньш заделов; что определяет m планировку цехов; Применение гибкой рабочей силы.и улучшение видимости требуют чтобы производственные площади были компактными; а каждая, стадия процесса была открыта для всех остальных. 6) Протягивающее календарное планирование. В системе «точно вовремя» поток работы определяется спросом, в то время как в традиционном планировании материалы проталкиваются через производство с первой его стадии. В «точно вовремя» активируется последняя стадия и только БІТОМ случае, когда есть спрос на готовый продукт., 7) Закупки точно вовремя. Чаще всего этот элемент считается первым, а порой и единственным в системе «точно вовремя» [67, 71і, 72, 118]. Обзор систем планирования .вразличных отраслях производства зарубежных стран показал, что систему «точно вовремя» в настоящее время использует практически около 71 % предприятий [114,120,121].
Наибольшее развитие она получила в автомобильной промышленности. Помимо фирмы «Toyota Motors», которая была основоположником этой системы, на сегодняшний день систему «точно вовремя» используют такие автомобильные компании как «General Motors», «Ford» (США), производители комплектующих, например компания Arvin Automotiv (США) [72,114,122].
Так, средний производственный цикл выпуска одной партии конкретной модели легкового автомобиля на Toyota составляет всего 2 дня, что в 5 раз меньше; чем в США и в 10 раз меньше, чем на лучшем предприятии России — АвтоВАЗе. Так, коэффициент оборачиваемости материально-технических запасов на Toyota имеет фантастически большую цифру, т.е.- период реализации товарно-материальных ценностей составляет 4 дня против- 60 - 70 дней у основных конкурентов, поэтому себестоимость автомобиля в 2 раза ниже, чем у американских и европейских фирм (таблица 1.1). Этот факт убедительно свидетельствует о том, какие огромные резервы имеются в сфере организации производства и в его главной функции - оперативном управлении основным производством, которое носит интегрированный характер и вбирает в себя все остальные функции управления предприятием [72].
Концептуальная модель автоматизированного синтеза"ЛТ-расписаний
Для формализации процесса построения производственного расписания разработана концептуальная модель автоматизированного синтеза ЛТ-расписаний подразделений механической обработки. В качестве объекта планирования по ЛТ-технологии приняты ГПС механической обработки, в общем случае состоящие из произвольного числа гибких производственных модулей (ГПМ) различного целевого назначения, объединенных системами управления И;автоматизированного транспорта. В частном случае это может быть одно или. несколько рабочих мест, выполняющих определенные технологические и транспортные операции.
Разработка концептуальной модели поиска оптимальных JIT-расписаний работы выбранного объекта предполагает решение двух задач: а): разработка компьютерной модели функционирования ГПС при текущем варианте сменного задания, и б) разработка алгоритма формирования оптимального расписания на множестве вариантов запуска в обработку изделий из текущего сменного задания.
Циклограммы описывают моменты начала, завершения и последовательность работы устройств. Продолжительность циклов зависит от технических параметров устройств (например, скорость робокар) и проходимых расстояний (например, путь резания, угол поворота, высота подъема), которые предопределяются текущим состоянием системы.
Циклограммы позволяют вскрыть внутренние потери эффективности ГПС, связанные с взаимодействием ее элементов, и внешние потери, обусловленные варьированием номенклатуры выпускаемой продукции. Таким образом, работа ГПС с точностью до секунды может быть представлена в виде временных циклограмм. По сути, циклограммы работы оборудования - это и есть модели функционирования технических систем. Таким образом, можно получить алгоритм моделирования, учитывающий в совокупности все основные параметры ГПС - от координатной привязки оборудования на схемах планировки и параметров транспортного средства до алгоритмов работы отдельных агрегатов, ресурса каждого режущего инструмента и гнезда с его местонахождением в магазине или в автоматическом складе. Программная реализация алгоритма моделирования позволяет с точностью до технологического перехода построить циклограмму функционирования ГПС на протяжении цикла ее безлюдной работы. Работа FIIG с любой требуемой точностью может быть расписана в виде циклограмм. Возможные погрешности срабатывания устройств можно учитывать вероятностными методами подобно тому, как учитывается рассеивание размеров деталей относительно номинальных значений.
Понятно, что вручную заниматься построением циклограмм работы автоматизированного оборудования - занятие трудоемкое, которое становится практически неосуществимо, если речь идет о выявлении каких-либо статистических закономерностей. В ГОУ ОГУ разработан метод автоматизированного построения циклограмм, имеющий следующие особенности: 1) позволяет строить циклограммы работы автоматизированного оборудования с разрешением на уровне технологического-перехода, что недоступно ни. в. одной из известных отечественных и зарубежных систем моделирования; 2) в качестве исходных данных используются:конкретные технические характеристики оборудования (станков, транспортных средств, накопителей) и алгоритмы, его взаимодействия, данные по технологическим процессам, составу сменного задания, начальному размещению заготовок и режущих инструментов, поэтому от пользователя программной реализации модели (проектировщика, технолога, диспетчера) требуется знание лишь предметной области; 3) включает специально разработанный математический аппарат для расчета по циклограмме показателей эффективности моделируемой системы: коэффициента загрузки, производительности, стоимости станко-часа, срока окупаемости затрат. Автоматически построенная циклограмма позволяет, с одной стороны, убедиться в корректности работы созданной программы, а с другой - визуально оценить наличие узких мест в работе оборудования. Для статистической оценки эффективности функционирования ГПС при заданном наборе параметров оборудования разработан метод экспресс анализа, основанный на автоматизированном построении циклограмм для выборки из множества вариантов сменных заданий. Циклограммы позволяют вскрыть внутренние потери эффективности ГПС, связанные с взаимодействием ее элементов, и внешние потери, обусловленные варьированием номенклатуры выпускаемой продукции. Сокращение или полное устранение внутренних потерь позволят оптимизировать проектные параметры ГПС, а сокращение внешних потерь - минимизировать эксплуатационные издержки.
В традиционном производстве также можно использовать циклограммы для моделирования производственного процесса. Большинство систем оперативно-календарного планирования используют для отображения результатов составления производственного расписания диаграммы Ганта. Однако, если математический аппарат для моделирования ГПС с помощью циклограмм разработан и описан в трудах [14, 84-87], то для традиционного производства. данная математика не подходит. Таким образом, необходима разработка математического обеспечения моделирования производственного процесса как для высокоавтоматизированных производств, к которым относятся ГПЯ; ГПС, РПС и другие, так и для традиционных производств, в которых прослеживается гораздо меньшая концентрация операций на технологическом оборудовании одной группы.
Определение способа представления хромосом
Выберем способ представления хромосом для генетического алгоритма. Так как в очереди фигурируют только целые числа, а также нет надобности работать с вещественными числами высокой точности, то остановимся на целочисленном подходе построения генетического алгоритма. Хромосому, в данной задаче удобно представить в виде, собственно, последовательности запуска. Так как в очередности запуска указывается, сколько изделий и какого наименования должно быть произведено, то применять классические варианты кроссинговеров не представляется возможным, потому что в них возможно получение потомка (очереди) с измененным количеством выпуска изделий. Так как в очереди запуска содержатся повторяющиеся элементы, то будем использовать не значение элемента очереди, а его номер. При перестановке номера элемента на новую позицию будем вместе с ним переставлять и элемент. Тогда задача оптимизации производственного расписания будет сведена к задаче коммивояжера.
Задача коммивояжера (ЗК) считается классической задачей генетических алгоритмов. Суть задачи следующая: путешественник (или коммивояжер) должен посетить каждый из базового набора городов и вернуться к исходной точке. Имеется стоимость билетов из одного города в другой. Необходимо составить план путешествия, чтобы сумма затраченных средств была минимальной. Поисковое пространство для ЗК - множество из N городов. Любая комбинация из N городов, где города не повторяются, является решением. Оптимальное решение - такая комбинация, стоимость которой (сумма из стоимостей переезда между каждыми из городов в комбинации) является минимальной. ЗК - достаточно старая проблема: она была сформулирована еще в 1759 году (под другим именем). Термин "Задача коммивояжера" был использован в 1932г. в немецкой книге "The traveling salesman, how and what he should to get commissions and be successful in his business", написанную старым коммивояжером.
Задача коммивояжера была отнесена к сложным задачам. Существуют строгие ограничения на последовательность, и количество городов может быть очень большим (существуют тесты, включающие несколько тысяч городов).
Кажется естественным, что представление тура - последовательность (//, І2, ... , /„), где (//, і2, ... , іп) - числа из множества (1 ... п), представляющие определенный город. Двоичное представление городов не будет иметь никаких преимуществ. Напротив, двоичное представление будет требовать специального ремонтирующего алгоритма, так как изменение одиночного бита может повлечь неправильность тура..
В настоящее время существует три основных представления пути: соседское, порядковое и путевое. Каждое из этих представлений имеет их собственные «генетические» операторы, все они очень.сильно различаются.
Соседское представление представляет тур как список из п городов. Город J находится на позиции L только в том случае, если маршрут проходит из города / в город J. Например, вектор (2 4839715 6) представляет следующий тур: 1-2-4-3-8-5-9-6-7 . Каждый маршрут имеет только одно соседское представление, но некоторые векторы в соседском представлении могут представлять неправильный маршрут. Например, вектор (2 48 1-9357 6) обозначает маршрут 1-2-4-1..., т.е. часть маршрута - замкнутый цикл. Это представление не поддерживает классическую операцию кроссинговера. Для соседского представления определены и исследованы три операции кроссинговера: alternating edges (альтернативные ребра), subtour chunks (куски подтуров), heuristic crossovers (эвристический кроссинговер). Кроссинговер alternating edges строит потомков, выбрав (случайно) ребро от первого родителя, потом следующее ребро от второго, потом опять следующее от первого и т.д. Если новое ребро представляет замкнутый цикл, берут случайный угол из того же родителя, который еще не выбирался и не образует замкнутого цикла. Для примера, один из потомков родителей Р1 = (2 3 8 7 9 1 4 5 6) и Р2 = (7 5 1 6 9 2 8 4 3) Может быть П1 = (2 5 8 7 9 1 6 4 3), где процесс начинался от угла (1,2) родителя Р1, продолжая до угла (7,8), вместо которого выбран угол (7,8), поскольку тот образуют замкнутый цикл. Кроссовер subtour chunks создает потомков, выбирая (случайно) подтур от одного из родителей, затем случайной длины кусок от другого из родителей, и т.д. И опять, если на каком-то уровне образуется замкнутый цикл, он решается аналогичным образом (выбирается другой случайный подтур, который еще не выбирался, из этого же родителя): Heuristic crossovers строит потомков, выбирая случайный город как стартовую точку для маршрута - потомка. Потом он сравнивает два соответствующих ребра от каждого из родителей и выбирает белее короткое. Затем конечный город выбирается как начальный для выбора следующего более короткого ребра из этого города. Если на каком-то шаге получается замкнутый тур, тур продолжается любым случайным городом, который еще не посещался.
Преимущества этого представления - в том, что оно позволяет схематически анализировать подобные маршруты. Это представление имеет в основании натуральные «строительные блоки» - ребра, маршруты между городами. Например, схема ( з 7 ) описывает множество всех маршрутов с ребрами ( 4 3 ) и ( 6 7 ). Основной же недостаток данного представления - в том, что множество всех его операций очень бедно. Кроссовер alternating edges часто разрушает хорошие туры, которые были у обоих родителей до примене ния этой операции. Кроссовер subtour chunks имеет лучшие характеристики, чем первый, благодаря тому, что его разрушительные свойства меньше. Но все равно его эксплуатационные качества все же достаточно низки. Кроссовер heuristic crossover, конечно же, наилучший оператор для данного представления. Причина - в том, что предыдущие операции слепы, они не берут в расчет настоящую длину ребер. С другой стороны, heuristic crossover выбирает лучшее ребро из двух возможных. Может получиться, что дальнейший путь будет невозможен и придется выбирать ребро, длина которого неоправданно большая. К тому же, производительность этой операции нестабильна. В трех экспериментах на 50, 100 и 200 городах система нашла туры с 25%, 16% и 27% оптимального, приблизительно за 15000, 20000 и 25000 итераций соответственно.
Исследование системы при изменении количества оборудования
Следующей серией экспериментов является исследование системы при изменении количества оборудования для выполнения сменных заданий трудоемкостью 114 мин и 340 мин. Количество станков увеличивается от четырех до двенадцати.
Из графиков видно, что время выполнения сменного задания изменяется несущественно, а коэффициент загрузки оборудования падает. Это объясняется тем, что транспорт не успевает обслужить все станки и возникают простои из-за доставки заготовок. Для улучшения ситуации необходимо увеличить количество транспортных средств. Данная возможность в модели производственной системы реализована.
Следующим этапом вычислительных экспериментов является оценка составления производственного расписания при изменении вероятности мутации. В программе реализованы два метода мутации: простая и модифицированная описанные в третьей главе. Основной целью данных генетических операторов является предотвращение преждевременной сходимости алгоритма. В этом случае существенно повышается количество отыскания глобального экстремума - оптимального производственного расписания. Так как различные методы мутации оказывают разное влияние на работу операторов скрещивания с использованием того или иного метода селекции, то необходимо для каждого варианта кроссинговера провести исследования на предмет эффективности использования того или иного вида мутации.
Вероятность мутации изменялась в диапазоне от 10 % до 100 %. Результаты проведения экспериментов с использованием простой мутации для различной длительности СЗ при оценке по времени работы и загрузке оборудования представлены на рисунках 4.7 - 4.9.
Из графиков видно, что на сменных заданиях с длительностью до 400 минут применение мутации не дает стабильных результатов. Это объясняется тем, что небольшой размер очереди запуска не позволяет составить оптимальное производственное расписание. В этой ситуации необходимо использовать стратегии инбридинга и аутбридинга. При увеличении длительности сменного задания нахождение оптимального производственного расписания стабилизируется. На рисунке 4.9 высокая загрузка оборудования более стабильна при использовании циклического кроссинговера и турнирной селекции. Судя из графиков вероятность простой мутации, следует устанавливать в диапазоне от 0 % до 40 %.
Рассмотрим, какое влияние оказывает на процесс поиска оптимального расписания модифицированная мутация. Полученные результаты (рисунки 4.10-4.11) схожи с результатами использования простой мутации. Однако в отличие от предыдущей серии опытов наблюдается меньший разброс значений показателей эффективности.
Из графиков видно, что эффективность производственной системы при-использовании оптимизации производственного расписания составляет 22-26 %, в то время как расписание, построенное без оптимизации, для одной смены показывает 7 %, и лишь к пятой смене позволяет достичь 18 %. Это объясняется тем, что последовательное распределение заготовок в очереди на обработку не учитывает наличие простаивающего оборудования. Поэтому в начале и конце смены возникают простои; которые постепенно устраняются по мере увеличения длительности оборудования. Однако даже самое высокое значение эффективности производственной системы, полученное с использованием расписания без оптимизации, на 4 % ниже минимальной эффективности, полученной при использовании оптимизации производственного расписания. При автоматизированном синтезе оптимального производственного расписания наблюдается более стабильная работа производственной системы для: различного количества смен. Прирост загрузки оборудования при этом составляет 8-15%.
Для проведения статистических исследований использованы положения теории математической статистики для нахождения вероятностных распределений и накопленной вероятности [7, 16, 50]. Для стратегии «точно вовремя» основным критерием составления производственного расписания является отклонение полученного расписания от заданного горизонта планирования. Для исследования этого показателя построена диаграмма распределения вероятности выполнения сменного задания в заданное время (рисунок 4.12) и накопленная вероятность выполнения сменного задания в заданное время (рисунок 4.13). Из диаграммы видно, что различные сочетания генетических операторов показывают различную величину отклонения полученного расписания. Отклонение в отрицательном направлении означает составление такого расписания, при котором время выполнения сменного задания меньше установленного. Накопленная вероятность выполнения сменного задания в заданное время Из диаграммы видно, что отклонение от установленного значения в большую сторону не превышает 50 мин, а вероятность получения такого расписания составляет не более 17 %. Отклонение в меньшую сторону достигает 70 мин. Основная часть генетических операторов позволяет получить производственное расписание с меньшим временем выполнения сменного задания до 40 мин с вероятностью 25-45 %. Из используемых здесь вариантов генетических операторов наиболее предпочтительными является сочетание кроссинговера Кантора с ранговой селекцией, циклического кроссинговера с турнирной селекцией и циклического кроссинговера с ранговой селекцией, который показал самую высокую вероятность получения нулевого отклонения от заданного времени выполнения сменного задания. Кроссинговер Кантора с турнирной селекцией позволяет получить производственное расписание, соответствующее минимальному времени выполнения сменного задания, но по принципу «точно вовремя» каждая деталь должна быть подготовлена для следующей операции в точно заданное время, чтобы обеспечить ритмичность работы производственной системы и сократить издержки на хранение заготовок. Поэтому данное сочетание генетических операторов рекомендуется использовать для составления производственного расписания по критерию минимального времени выполнения сменного задания.
Рассмотрим распределение коэффициента загрузки, представленное на рисунке 4.14 и накопленную вероятность стабильной загрузки оборудования (рисунок 4.15). Из графиков видно, что при использовании циклического кроссинговера и ранговой селекции, а также кроссинговера Кантора и ранговой селекции удается получить наиболее высокую загрузку с вероятностью 83 % и 100 % соответственно. Использование циклического кроссинговера также дает приемлемые результаты. Самым неудачным в данной ситуации опять оказалось сочетание кроссинговера Кантора с турнирной селекцией.
