Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов решения задач оперативного управления технологическими процессами 14
1.1 Цели и задачи краткосрочного планирования в мелкосерийном многономенклатурном производстве 15
1.2 Анализ моделей мелкосерийных многономенклатурных производств дискретного типа 21
1.3 Анализ задач календарного планирования 26
1.4 Алгоритмы решения общей задачи календарного планирования 28
1.5 Эвристические приоритетные правила 33
1.6 Решение задач дискретной оптимизации с помощью генетических алгоритмов 37
1.7 Постановка задачи 40
Выводы и результаты по главе 1 42
ГЛАВА 2. Разработка модели производства и алгоритма синтеза расписаний 44
2.1 Выбор критерия оптимизации 45
2.2 Разработка математической модели производственной системы 48
2.3 Исследование математической модели 54
2.4 Разработка алгоритма решения задачи синтеза расписаний 56
2.5 Анализ алгоритма синтеза расписаний 58
Выводы и результаты по главе 2 65
ГЛАВА 3. Решение задач синтеза расписаний и распределения ресурсов с помощью генетических алгоритмов 66
3.1 Структурная схема генетического алгоритма 67
3.2 Модификация структуры генетического алгоритма 76
3.3 Выбор метода кодирования параметров задачи в хромосомы 77
3.4 Разработка структурной схемы генетического алгоритма 80
3.5 Алгоритмы управления эвристиками в процессе генетического поиска 82
3.6 Алгоритмы управления макромутациями 87
Выводы и результаты по главе 3 89
ГЛАВА 4. Практическая реализация генетического алгоритма для решения задач синтеза расписаний 90
4.1 Разработка программного комплекса оперативного планирования 91
4.2 Исходные данные и результаты работы подсистемы 92
4.3 Взаимодействие элементов программного комплекса . 96
4.4 Методика практического использования программного комплекса планирования работ и распределения ресурсов 101
Выводы и результаты по главе 4 104
Заключение 105
Литература 108
Приложения 123
- Анализ моделей мелкосерийных многономенклатурных производств дискретного типа
- Решение задач дискретной оптимизации с помощью генетических алгоритмов
- Разработка математической модели производственной системы
- Алгоритмы управления эвристиками в процессе генетического поиска
Анализ моделей мелкосерийных многономенклатурных производств дискретного типа
Календарным планом (расписанием) называется совокупность календарных времен начала выполнения всех операций, определенных исходя из анализа наличных ресурсов и удовлетворяющих всем требованиям, вытекающим из производственных ограничений. где / - множество работ, подлежащих выполнению, Т- множество, указывающее на время начала работ, R - множество исполнителей работ. Широкий спектр различных производственных факторов, влияющих на способ организации производства и, следовательно, на формулируемые ограничения и критериальные функции, является причиной разработки большого числа моделей календарного планирования. Известные модели КП, описанные в литературе, как правило, учитывают отдельные особенности производства, но для получения качественного решения задачи необходим учет всей их совокупности.
Основными факторами, влияющими на характер ограничений в моделях календарного планирования, являются: - характер производства (непрерывный или дискретный); - тип производства (массовое, серийное, дискретное); - структура технологического графа, определяемая стадиями производственного процесса (сетевой, линейный); - число единиц оборудования в производственном подразделении. В диссертационной работе рассматриваются методы решения задач синтеза расписаний и распределения ресурсов в мелкосерийном многономенклатурном производстве дискретного типа. Общему решению таких задач ввиду их практической важности и возможности четкой математической формулировки посвящено большое количество исследований [8, 24, 29, 33, 40, 45, 47, 48, 53, 59, 61, ПО]. Разработка автоматизированной подсистемы оперативного планирования технологическим процессом дискретного типа наталкивается на целый ряд проблем, обусловленных следующими особенностями мелкосерийного многономенклатурного производства: - широкое разнообразие состава выполняемых работ, которые выполняются на различных видах оборудования, приводит к увеличению производственного цикла, ограничивает возможности типизации технологических процессов, применении стандартизованных решений, и как следствие, приводят к увеличению размерности решаемых задач; - заказы, как правило, не повторяются. Возможна лишь эпизодическая повторяемость отдельных заказов через длительные, заранее неизвестные промежутки времени. Помимо этого, мал удельный вес унифицированных деталей; - имеется некоторое количество приоритетных заказов, для которых заданы "мягкие" и "жесткие" плановые сроки их завершения. За нарушение указанных сроков устанавливаются штрафные санкции; - множество единиц оборудования разбито на виды по характеру выполняемых операций, технологические маршруты изготовления изделий расписаны с точностью до вида оборудования; - множество видов оборудования объединено в группы с целью обеспечения взаимозаменяемости, повышения равномерности загрузки и коэффициента использования оборудования; - имеется некоторое количество приоритетных заказов, для которых заданы контрольные и директивные сроки их завершения; контрольные сроки могут быть превышены; за нарушение директивных сроков накладывается штраф; - технология изготовления любого заказа представляет собой граф произвольного вида. Модели, предполагающие линейную структуру технологического маршрута изготовления продукции, разрабатываются в рамках теории расписаний. Это обширный класс моделей календарного планирования работы цеха (участка). Технология, формализованная во многих известных моделях [7, 8, 18, 22, 30, 31] ориентирована на изготовление деталей и поэтому, как правило, ограничена линейной последовательностью операций. В нашем случае технология изготовления изделия задается графом произвольной структуры, который нельзя свести к совокупности линейных, поскольку это приведет к отказу от важного ограничения, что на одном станке одновременно не может обрабатываться более одной детали, и как следствие снизится эффективность работы алгоритма.
Модели, учитывающие сетевую структуру технологического графа изготовления изделий и ограничения, накладываемые на используемые ресурсы, представляет собой логическое развитие и обобщение моделей сетевого планирования.
Известно большое количество моделей [7, 22, 34], учитывающих наличие видов оборудования (совокупность исполнителей, которые могут выполнить данную работу), но не отражающих объединение видов в группы. Это позволяет однозначно определить расписание заданием начала (или окончания) каждой технологической операции. Однако, имеющееся в рассматриваемом производстве объединение видов оборудования в группы не позволяет произвести такое сопоставление, поэтому в мелкосерийном производстве дискретного типа для однозначного задания расписания кроме начала операции требуется явное указание единицы оборудования, на которой она выполняется.
Некоторые модели [44, 48] учитывают наличие приоритетных заказов (изделий), но не учитывают наличия групп оборудования, участков, и т.д.
Таким образом, анализ представленных моделей позволяет сделать вывод, что ни одна из известных моделей не отражает всех особенностей единичного многономенклатурного производства в целом, а также специфики дискретного производства в частности. Поэтому, разработка системы календарного планирования должна основываться на модели, комплексно учитывающей особенности мелкосерийного многономенклатурного производства дискретного типа. Рассмотрим типовые задачи календарного планирования работы механического цеха мелкосерийного дискретного производства, отражающие многообразие моделей КП.
Решение задач дискретной оптимизации с помощью генетических алгоритмов
Процесс поиска решения как бы независим от метода оценки качества полученного решения. В данном случае ситуация противоположна случаю, когда используются точные или регулярные приближенные методы, например, симплекс-метод, где аналитическое выражение целевой функции играет важную роль в направлении процесса поиска решения по оптимальной траектории.
Таким образом, характерной особенностью эвристического метода является отсутствие средств для осуществления направленного процесса поиска оптимального решения. Эвристический алгоритм гарантирует лишь получение одного из допустимых решений. Изменив функцию предпочтения или применив один из приемов ее модификации и повторив еще раз процесс решения, снова можно получить новые допустимые решения. Существенным является вопрос о близости получаемых решений к оптимальным. Лишь для некоторых простейших, частных моделей календарного планирования, существуют регулярные методы такой оценки. Поэтому только по отношению к этим моделям эвристический метод может быть назван приближенным методом. В общем случае, в том числе и для подавляющего большинства реальных задач, этого утверждать нельзя.
Из сказанного вытекает очень важная и сложная проблема - отыскание методов повышения эффективности эвристических алгоритмов синтеза расписаний, обеспечивающих возможность той или иной функции предпочтения в определенных условиях обеспечивать получение удовлетворительных решений.
Одним из методов решения данной проблемы является использование генетических алгоритмов для поиска наилучшей комбинации эвристик из множества возможных, обеспечивающих получение экстремального значения обобщенного критерия оптимальности. 1. Разработана структурно-критериальная модель мелкосерийного многономенклатурного производства дискретного типа, учитывающая многостадийность производственного процесса, временные и стоимостные затраты выполнения работ на машинах, а также затраты на переналадки машин при переходе к выполнению работ другой группы. 2. Разработан алгоритм синтеза расписаний, особенность которого заключается в использовании метода планирования по "существенным" моментам времени, представляющим собой моменты завершения выполнения / операции на у машине. Применение данного алгоритма позволяет значительно снизить вычислительные затраты на поиск решения, поскольку из рассмотрения исключается множество вариантов, в которых не происходит никаких изменений в расписании. 3. Для оценки качества решения задачи синтеза расписаний и распределения ресурсов предложено использовать аддитивный векторный критерий оптимальности на основе весовых коэффициентов. 4. В результате проведенного вычислительного эксперимента выявлена высокая зависимость эффективности используемых в алгоритме синтеза расписаний эвристик от используемого обобщенного критерия оптимальности. 5. Сформулирован вывод о необходимости совершенствования эвристического алгоритма с целью стабилизации эффективности использования отдельных эвристик. 6. В качестве метода повышения эффективности эвристического алгоритма предлагается использовать генетический алгоритм. Глава посвящена разработке эволюционно-генетического алгоритма решения задач синтеза расписаний, который является одним из наиболее эффективных методов решения NP-трудных задач дискретной оптимизации. С этой целью проанализированы существующие типы генетических алгоритмов, приведена базовая схема ГА, рассмотрены теоретические основы работы ГА в процессе поиска оптимального решения.
На основе проведенного анализа осуществлена оптимизация структуры генетического алгоритма для решения задач синтеза расписаний. В качестве базового метода поиска оптимального значения целевой функции использован метод комбинирования эвристик.
С целью дальнейшего повышения эффективности генетического алгоритма для решения задач синтеза расписаний разработаны процедуры управления эвристиками и макромутациями, которые позволяют направить генетический поиск в предпочтительные области пространства решений, а также использованы операторы локального поиска, позволяющие повысить скорость сходимости алгоритма и снизить вероятность появления стагнации в зонах локальных экстремумов.
Разработка математической модели производственной системы
Обоснование адаптивных свойств данного алгоритма основывается на факте изменения значения генетической вариансы сг2 в процессе эво люции. В процессе генетического поиска происходит сходимость алго ритма к некоторому субоптимальному значению, которая сопровождает ся уменьшением разнообразия хромосомного набора и сокращением рассеивания значений функции пригодности fxt в популяции. Это озна чает, что на каждом шаге эволюции происходит сокращение числа мутируемых генов пропорционально изменению величины. 1. В главе проведен анализ структуры и механизмов работы генетических алгоритмов. Исследованы виды генетических операторов, рассмотрены особенности их использования при решении задач синтеза расписаний и распределения ресурсов. 2. С целью повышения эффективности работы ГА обоснована необходимость модификации структуры и настройки его параметров на решение комбинаторных задач дискретной оптимизации, к которым относятся задачи синтеза расписаний и распределения ресурсов. 3. Предложен способ кодирования структурных параметров в хромосомы, в котором значениями генов являются имена эвристик. При этом отпадает необходимость в применении дополнительных операторов коррекции, снижающих эффективность генетического поиска. 4. С целью повышения скорости сходимости ГА использован оператор локального поиска, а также механизмы выбора эвристик, повышающие вероятность нахождения оптимального решения. 5. С учетом специфики задач синтеза расписаний и распределения ресурсов обоснованы способы рекомбинации генов в хромосоме, способствующие интенсификации поиска оптимальной комбинации эвристик. Глава посвящена реализации программного комплекса, в котором на основе результатов исследований, проведенных в предыдущих главах, реализованы предложенные методы и алгоритмы решения задач синтеза расписаний и распределения ресурсов. В данной главе приводится описание программного комплекса, осуществляющего синтез расписаний, рассматривается его структура и взаимодействие составляющих элементов, излагается методика практического использования, даются рекомендации по настройке параметров алгоритма для решения практических задач. Проводится сравнительный анализ решения задач планирования работы участков цеха механообработки с использованием различных видов генетических алгоритмов. На основе материалов, изложенных в предыдущих главах, разработан программный комплекс, с помощью которого осуществляется краткосрочное календарное планирование работ на цеховом уровне. Программный комплекс выполняет основные функции подсистемы оперативного календарного планирования и диспетчерского контроля производственного процесса на цеховом уровне, такие как: - формирование и коррекция оперативных производственных планов цеха с учетом текущего состояния станочной системы; - расчет производственного расписания загрузки оборудования по различным критериям; - представление результатов расчета расписания в виде таблиц текущего состояния партий запуска и диаграмм загрузки технологического оборудования; - формирование сменно-суточных заданий на рабочие места цеха (участка); - составление и автоматическая коррекция планово-учетного графика изготовления комплектов деталей с контролем готовности каждой партии запуска; - формирование внутрицеховых документов: сменно-суточные задания на рабочие места, оперативные маршрутные карты, рабочие наряды, планово-учетные графики изготовления изделий и пр. Программный комплекс является составной частью АСУП ремонт-но-механического цеха и осуществляет обмен информацией с ее различными элементами и подсистемами. Программный комплекс разработан в среде Delphi 4 и работает под управлением операционных систем семейства Windows (Windows 95/98/ME/N172000). - форма ввода исходных данных; - модуль синтеза расписаний; - база эвристик; - модуль генетических операторов; - блок настройки параметров алгоритма; - и блок генерации отчетов. Рассмотрим подробнее работу каждого элемента.
Особенностью подсистемы календарного планирования является обработка большого количества исходных данных, используемых при решении оптимизационных задач, что существенно увеличивает трудоемкость работ. Для удобного и наглядного отображения и редактирования исходных параметров предназначена форма ввода данных. Все параметры логически объединены в группы и располагаются на отдельных вкладках формы.
На первой вкладке (рис 4.2) находятся поля, определяющие количество станков, групп оборудования, объем заказов и количество операций. Эти данные непосредственно характеризуют размерность задачи.
Ниже располагается таблица, в первой колонке которой определен состав выпускаемых изделий. Во второй и третьей колонке заданы контрольные и директивные сроки выполнения работ за нарушение которых накладываются штрафные санкции.
Алгоритмы управления эвристиками в процессе генетического поиска
Методика работы с программой включает в себя 3-й этапа: настройка параметров, планирование и корректировка расписаний.
На первом этапе определяется рабочий набор эвристик, состав генетических операторов и вероятности их использования. Количество используемых эвристик на данном этапе можно расширить с целью поиска наилучших правил для заданного критерия оптимальности. По завершении пробного прогона, заключающегося в выполнении 3-5 шагов эволюции, определяют эффективность каждой эвристики. Эвристики с наименьшими значениями эффективности становятся кандидатами на исключение из рабочего набора.
На этапе планирования вводятся параметры выполнения генетического алгоригма, рассчитанные на основе пробного прогона. Спецификой предложенного метода комбинирования эвристик является тот факт, что поиск решения в основном происходит за счет оператора мутации, в отличие от классического генетического алгоритма, в котором главную роль играет оператор кроссовера. В предложенном методе оператор мутаций производит интенсивное обновление хромосом новыми эвристиками, в то время как оператор кроссовера осуществляет позиционирование эвристик и сохраняет положительную наследственную информацию. Следовательно, вероятность выполнения оператора мутаций необходимо увеличить до значения рш= 0,3 -f 0,4, в то время как в классическом ГА это значение не превосходит рт= 0,1.
Рабочий набор формируется из эвристик со значением эффективности больше некоторого порогового значения (ір. В результате вычислительного эксперимента установлено, что оптимальным является использование 3-5-6 эвристик в рабочем наборе. Сокращение числа эвристик ведет к сужению поискового пространства и снижению точности получаемых решений. Увеличение числа эвристик приводит к значительному увеличению затрат времени на поиск решения задачи.
На этапе корректировки планов производится уточнение исходных данных, а синтез расписаний возможно производить на основе уже найденной комбинации эвристик для заданного критерия оптимальности.
Исследование работы генетических алгоритмов проводилось на тестовых задачах со следующими параметрами: Варьировались следующие параметры генетического алгоритма: 1. Размер популяции. В исследованиях применялись значения размера популяции Pt= {30, 50, 70); 2. Вероятность выполнения макромутаций: рт = {0.2, 0.35, 0.5}; 3. Схемы позиционирования мутируемых генов: - распределенный случайный (рис.3.8); - сосредоточенный горизонтальный (рис.3.9); - сосредоточенный вертикальный (рис.3.10); 4. Управление размером макромутаций: - с постоянным числом мутируемых генов; - с переменным числом мутируемых генов; - с применением адаптивного алгоритма управления размером макромутаций. На основе результатов численных экспериментов были сформулированы следующие выводы: 1. Качество полученного решения задачи синтеза расписаний в значительной мере зависит от используемого набора эвристик. 2. Применение эволюционно-генетического алгоритма позволило получить решения лучше, чем применение отдельных эвристик. 3. Эволюционно - генетические алгоритмы позволяют сократить время поиска решения по сравнению со случайным алгоритмом поиска (метод Монте-Карло). 4. Применение процедур управления эвристиками в процессе генетического поиска позволяет значительно повысить эффективность алгоритма. 5. Адапгивный алгоритм управления размером макромутаций превосходит по эффективности алгоритм с постоянным числом му-тируемых генов. 6. При сравнении эффективности алгоритмов позиционирования мутируемых генов лучшие результаты быль получены в варианте с использованием сосредоточенного вертикального алгоритма. 7. Применение модифицированного генетического алгоритма позволяет повысить качество и эффективность решения задач синтеза расписаний и распределения ресурсов. 1. В главе рассматривается реализация программного комплекса, предназначенного для решения задач синтеза расписаний и распределения ресурсов в котором воплощены методы и алгоритмы, рассмотренные в предыдущих главах. 2. Приведено описание структуры программного комплекса и взаимодействия его элементов. 3. Рассмотрена методика практического использования программного комплекса на примере решения тестовых задач различной размерности с применением различных вариантов генетических операторов. 4. На основе анализа полученных результатов сделан вывод об эффективности предложенных методов для решения задач синтеза расписаний и распределения ресурсов.
