Оптимизация структуры гибридного генетического алгоритма для решения задач синтеза расписаний и распределения ресурсов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Горбачев, Владимир Николаевич

• Горбачев, Владимир Николаевич
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Горбачев, Владимир Николаевич

Введение.

ГЛАВА 1. Анализ методов решения задач оперативного управления технологическими процессами.

1.1 Цели и задачи краткосрочного планирования в мелкосерийном многономенклатурном производстве.

1.2 Анализ моделей мелкосерийных многономенклатурных производств дискретного типа.

1.3 Анализ задач календарного планирования.

1.4 Алгоритмы решения общей задачи календарного планирования

1.5 Эвристические приоритетные правила.

1.6 Решение задач дискретной оптимизации с помощью генетических алгоритмов.

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

Выводы и результаты по главе 1.

ГЛАВА 2. Разработка модели производства и алгоритма синтеза расписаний.

2.1 Выбор критерия оптимизации.

2.2 Разработка математической модели производственной системы.

2.3 Исследование математической модели.

2.4 Разработка алгоритма решения задачи синтеза расписаний.

2.5 Анализ алгоритма синтеза расписаний.

Выводы и результаты по главе 2.

ГЛАВА 3. Решение задач синтеза расписаний и распределения ресурсов с помощью генетических алгоритмов

3.1 Структурная схема генетического алгоритма.

3.2 Модификация структуры генетического алгоритма.

3.3 Выбор метода кодирования параметров задачи в хромосомы.

3.4 Разработка структурной схемы генетического алгоритма

3.5 Алгоритмы управления эвристиками в процессе генетического поиска.

3.6 Алгоритмы управления макромутациями.

Выводы и результаты по главе 3.

ГЛАВА 4. Практическая реализация генетического алгоритма для решения задач синтеза расписаний.

4.1 Разработка программного комплекса оперативного планирования.

4.2 Исходные данные и результаты работы подсистемы.

4.3 Взаимодействие элементов программного комплекса

4.4 Методика практического использования программного комплекса планирования работ и распределения ресурсов. . 101 Выводы и результаты по главе 4.

Введение диссертации (часть автореферата) на тему «Оптимизация структуры гибридного генетического алгоритма для решения задач синтеза расписаний и распределения ресурсов»

Повышение эффективности производственных процессов - задача сложная и многоплановая. Её решение связано с совершенствованием организации труда, применением научно обоснованных методов управления производством и внедрением интегрированных автоматизированных систем управления (ИАСУ) на основе широкого использования современных средств вычислительной техники и последних достижений в области разработки программно-алгоритмического обеспечения.

Построение и развитие ИАСУ обусловлено появлением современных компьютерных систем, созданием эффективных средств автоматизации производства, разработкой теории управления сложными системами, теории обработки и хранения информации, теории и методов искусственного интеллекта и т.д.

Одной из основных функций ИАСУ является оперативное управление, в ходе которого осуществляется процесс принятия решений на основе использования текущей информации об управляемом объекте. Оперативное управление состоит из двух фаз - планирования и управления в реальном масштабе времени. Целью задачи планирования является обеспечение равномерной загрузки всех подразделений предприятия и ритмичного выпуска продукции в установленные сроки. Планирование работы производственной системы (ПС) осуществляется в условиях неопределенности данных о ее будущих состояниях, влияния случайных возмущений и изменения состояния внешней среды. Учитывая текущее состояние ПС и ориентируясь на некоторые предположения о её поведении в будущем, планированию, таким образом, придают характер прогноза желаемого хода производства.

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

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

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

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

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

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

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

Выделяют две группы ограничений [37,38,56]: технологические и ресурсные. При отсутствии технологических ограничений задачи планирования решаются методами линейного программирования. При отсутствии ограничений по ресурсам задачи планирования сводятся к задачам сетевого планирования, основным методом решения которых является метод «критического пути».

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

Анализ литературы показывает, что одним из наиболее эффективных методов решения задач планирования в мелкосерийном многономенклатурном производстве является эвристический алгоритм, основанный на использовании комбинированных приоритетных правил [13, 20, 56, 80].

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

В нашей стране и за рубежом исследованию вопросов теории и практики планирования с применением эвристических методов и приоритетных правил посвящены работы многих ученых, в том числе: В.В Португала, М. X. Блехермана, B.C. Танаева, В.В. Шкурбы, Д. Геллера, Д. Логемана, Д. Томпсона, Р. Конвея, У. Максвелла и др.

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

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

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

Известны примеры применения ГА к решению задач на графах [31], для синтеза расписаний [33-37], компоновки и размещения элементов в радиоэлектронной аппаратуре [38], конструирования механизмов [39], и т.д.

К достоинствам генетического подхода следует отнести присущий ему внутренний параллелизм, низкие требования к регулярности пространства поиска, способность эффективно выявлять и использовать эти регулярности для направления поиска в полезные подпространства [10, 21]. В процессе оптимизации информация, накапливаемая популяцией в ходе поиска решения задачи, активно используется для адаптации алгоритма к изменениям в производственной системе.

Круг задач, решаемых с помощью генетических алгоритмов, расширяется с каждым годом. Как следствие, область применения ГА постепенно перемещается от теоретических проблем, таких как задача коммивояжера (Traveling Salesman Problem), к реальным приложениям. Этот сдвиг является важным подтверждением эффективности работы ГА при решении сложных практических задач.

За последнее десятилетие было разработано большое количество генетических операторов и функций, сочетание которых порождает множество генетических методов [10, 12, 28, 63, 75, 90, 103, 105]. Практика показала, что для успешного применения генетического подхода необходимо произвести модификацию базового генетического алгоритма и настройку его параметров для решения конкретных задач.

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

В соответствии с поставленной целью основными задачами работы являются:

- Анализ особенностей функционирования подсистем оперативного производственного планирования и управления, работающих в составе ИАСУ цеха;

- Анализ методов и алгоритмов решения задач синтеза расписаний и распределения ресурсов в производственных системах дискретного типа;

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

- Разработка эвристического алгоритма синтеза расписаний, основанного на использовании детерминированных приоритетных правил.

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

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

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

Научная новизна работы.

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

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

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

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

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

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

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

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

Основные результаты работы были доложены и обсуждены:

- на 2-й Московской международной телекоммуникационной конференции студентов и молодых ученых "Молодежь и наука" 20-24 января 1998г в Москве;

- на 3-й Московской международной телекоммуникационной конференции студентов и молодых ученых "Молодежь и наука" 20-24 января 1999г в Москве;

- на научной сессии МИФИ - 2000, проводимой в г. Москве;

- на 2-й Международной научно-технической конференции "Информационные технологии в моделировании и управлении". 2000г в г. Санкт-Петербург.

- на научной сессии МИФИ - 2001, проводимой в г. Москве.

Публикации. По теме диссертации опубликовано 6 печатных работ.

Структура работы. Текст диссертации состоит из введения, четырех глав и заключения.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Горбачев, Владимир Николаевич

Выводы но главе 4

1. В главе рассматривается реализация программного комплекса, предназначенного для pen гения задач синтеза расписаний и распределения ресурсов в котором воплощены методы и алгоритмы, рассмотренные в предыдущих главах.

2. Приведено описание структуры программного комплекса и взаимодействия его элементов.

3. Рассмотрена методика практического использования программного комплекса на примере решения тестовых задач различной размерности с применением различных вариантов генетических операторов.

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

Заключение.

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

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

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

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

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

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

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

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

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

9. На основе разработанных алгоритмов и методов создан программный комплекс для решения задач оперативного планирования, который отличается широкими возможностями адаптации к различным условиям функционирования, а также конфигурации производственных систем. Разработана схема взаимодействия программного комплекса с компонентами ИАСУ.

10. Разработана методика практического использования программного комплекса при решении задач планирования работ в ремонтно-механическом цехе. Исследованы характеристики работы программного комплекса при решении задач различной размерности.

11 .Разработанные в диссертационной работе алгоритмы и методы решения задач синтеза расписаний и распределения ресурсов использованы при создании ИАСУ ремонтно-механического цеха в ОАО «Машиностроительный завод», что подтверждается соответствующим актом о внедрении.

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

Список литературы диссертационного исследования кандидат технических наук Горбачев, Владимир Николаевич, 2001 год

1. Айала Ф. Введение в популяционную и эволюционную генетику. / Пер. с англ.- М.: Мир, 1994.

2. Айнутдинов В.А., Горбачев В.Н. Автоматизированная систама подготовки и управления производством. // Сборник научных трудов, ч.5.,"Информатика и вычислительная техника", М.,МИФИ, 1998.

3. Айнутдинов В.А., Горбачев В.Н. Автоматизированная система управления роботизированным участком. // Сборник научных трудов, т. 7, "Информатика и компьютерные системы", М, МИФИ, 1999.

4. Айнутдинов В.А., Горбачев В.Н. Модели производственных систем дискретного типа. // Труды II международной научно-практической конференции "Информационные технологии в моделировании и управлении", СПб., Изд-во СПбГТУ.,2000.

5. Айнутдинов В.А., Горбачев В.Н. Построение автоматизированных систем управления ГПС. // Сборник научных трудов, т. 2, "Информатика и информационные технологии", М, МИФИ, 2000.

6. Айнутдинов В.А., Горбачев В.Н. Оптимизация структуры генетического алгоритма для решения задач синтеза расписаний и распределения ресурсов. // Сборник научных трудов, т.2, "Информатика и информационные технологии", М, МИФИ, 2001.

7. Акимов А.П. Математические модели планирования выпуска продукции в ГПС., М.,1986.

8. Баранов В.И. Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М., Наука, 1989.

9. Батшцев Д.И., Коган Д. И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород: Нижегородский госуниверситет, 1994. - 114с.

10. Батшцев Д.И. Генетические алгоритмы решения экстремальных задач: Учеб. пособ. / Воронежский гос. техн. ун-т, Нижегородский гос. ун-т, Воронеж, ВГТУ, 1995. - 69с.

11. Батшцев Д.И. Многокритериальный выбор с учетом индивидуальных предпочтений, Нижний Новгород, 1994. - 86с.

12. Батшцев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод декомпозиций для решения комбинаторных задач упорядочения и распределения ресурсов // Информационные технологии, 1997, № 1, с. 29-33.

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

14. Батшцев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов./Межвузовский сборник научных трудов "Высокие технологии в технике, медицине и образовании", Воронеж, ВГТУ, 1997г, с. 4-17.

15. Батшцев Д.И., Исаев С.А., Ремер Е.К. Эволюционно-генетический подход к решению задач невыпуклой оптимизации. / Межвузовский сборник научных трудов "Оптимизация и моделирование в автоматизированных системах", Воронеж, ВГТУ, 1998г, с. 20-28

16. Батшцев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа, Нижний Новгород, 1994.

17. Бек Н.Н. Голенко Д.И. Статистические методы оптимизации в экономических исследованиях, М.:Статистика, 1976.

18. Блехерман М.Х. Гибкие производственные системы : организационно экономические аспекты, - М., Экономика, 1988.

19. Букатова И.Л. Эволюционное моделирование и его приложения. М.: Наука, 1979.

20. Василенко С.И. Эвристические алгоритмы решения одной задачи теории расписаний // Математические методы в распознавании образов, М.: ВЦ АН СССР, 1987.

21. Васильев В.И. Ильясов Б.Г. Интеллектуальные системы управления с использованием генетических алгоритмов. Учеб. пособ., Уфа, 1999.

22. Гибкие производственные системы, промышленные роботы, робото-технические комплексы: практ. пособ. в 14кн., кн. 12. Оперативно-производственное планирование в ГПС. М., Высш. шк., 1989.

23. Горбачев В.Н. Генетические алгоритмы в задачах синтеза расписаний и распределения ресурсов. // Сборник научных трудов "Актуальные проблемы науки в исследованиях российских и зарубежных ученых", М, Спутник, 2000.

24. Душкин Г.А. Панова Т.Ф. Автоматизация корректировки планов выпуска продукции с учетом равномерной загрузки оборудования // Механизация и автоматизация производства. № 12, с 26-27. 1987.

25. Душутин И.В. Мультихромосомные генетические алгоритмы оптимизации структуры автоматизированных информационных систем., М., 1998.

26. Закревский А.Д. Алгоритмы решения логико-комбинаторных задач, Минск, 1980.

27. Захаров В.Н. Интеллектуальные системы управления: основные понятия и определения // Изв. РАН. Техническая кибернетика, 1992- № 5, 1993 -№4,5, 1994-№4.

28. Исаев С.А. Генетический алгоритм для решения задач нелинейной многокритериальной оптимизации. / Сборник "Вестник ННГУ". Н.Новгород, 1999, стр. 260.

29. Использование методов оптимизации в текущем планировании и оперативном управлении производством М.: ВНИИСИ, 1980.

30. Кисляк B.M. Модели и методы оптимального объемно-календарного планирования сложного промышленного производства, Свердловск, Знание, 1989.

31. Левнер Е.В. Сетевой подход к задачам теории расписаний // Исследования по дискретной математике, под ред. Фридмана A.M., -М.,Наука, 1973.

32. Мироносецкий Н.Б. Экономике математические методы календарного планирования, - Новосибирск, Наука, 1973.

33. Многоуровневая система оперативного управления ГПС в машиностроении / Соколицин С.А., В.А. Дуболазов, Ю.Н. Демченко, Л.: Политехника, 1991.

34. Норенков И.П. , Косачевский О.Т. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации. // Информационные технологии, 1999, № 2, с.2-7.

35. Норенков И.П. Генетические методы структурного синтеза проектных решений. // Информационные технологии, 1998, № 1, с.9-13.

36. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации.// Информационные технологии, 1999, № 1, с.2-7.

37. Первин Ю.А. Португал В.М. Семенов А.И. Планирование мелкосерийного производства в АСУП, М., Наука, 1973.

38. Первозванский А.А. Математические методы в управлении производством, М., Наука, 1975.

39. Планирование производства в условиях АСУ: Справочник /К.Ф. Ефетова, Т.П. Подчасова, В.М. Португал, Киев, Техшка, 1984.

40. Португал В.М., Семенов А.И. Модели планирования на предприятии, М„ Наука, 1978.

41. Рабинович М.Г. Многокритериальные модели и методы оптимизации в текущем планировании производства, Л., ЛГУ, 1988.

42. Ревенко В.А. Модели, методы и алгоритмы решения производственных задач планирования большой размерности в условиях АСУП, в 2-х ч., 1976.

43. Семенов А.И. Задачи теории расписаний в календарном планировании мелкосерийного производства, М., Наука, 1972.

44. Семенов А.И., Португал В.М. Задачи теории расписаний в календарном планировании мелкосерийного производства. М., Наука, 1972.

45. Семенов А.И., Португал В.М. Организационная структура оперативного управления производства, М., Наука, 1986.

46. Скурихин А. Н. Генетические алгоритмы // Новости искусственного интеллекта, 1995 -№4

47. Соколицин С.А., Кузин Б.И. Организация и оперативное управление машиностроительным производством, Л., Машиностроение, 1988.

48. Танаев B.C. Экстремальные задачи оптимального планирования и проектирования, Минск, 1991,- 152с.

49. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М., Наука, 1989,- 328с.

50. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М., Наука, 1975.

51. Тимофеев А.В., Юсупов P.M. Интеллектуализация систем автоматического управления // Изв. РАН. Техническая кибернетика, 1994.

52. Управление ГПС: Модели и алгоритмы/Под общ. ред. С.В. Емельянова. М., Машиностроение.- 1987, 386с.,ил.

53. Царевский Н. Н. Комплекс задач оперативного календарного планирования для автоматизированных производственных систем, М., ВЦ АН СССР, 1989.

54. Цирлин A.M. Оптимальное управление технологическими процессами М.;Энергоатомиздат, 1986.- 400 с.

55. Чернов В.А. Построение системы календарного планирования с помощью генетического подхода., М., 1992.

56. Эвристические методы календарного планирования / Т.П. Подчасова, В.М. Португал, В.А. Татаров, В.В. Шкурба, Киев, Технка, 1980.

57. Ashour S. A Decomposition Approach for the Machine Scheduling Problem. //International Journal of Production Research, Volume 6, № 2, pp. 109-122, 1967.

58. Back T. Optimal Mutation Rates in Genetic Search. // Department of Computer Science University of Dortmund, 1993.

59. Baker, K. R. Introduction to Sequencing and Scheduling.- John Wiley, New York, 1974.

60. Balas E., Lancia G., Serafini P., Vazacopoulos A. Job-Shop Scheduling with Deadlines. // Journal of Combinatorial Optimization, Volume 1, № 4, pp. 329-353., 1998.

61. Barr R. S„ Golden B. L., Kelly J. P., Resende M. G. C„ Stewart W. R. Designing and Reporting on Computational Experiments with Heuristic Methods. //Journal of Heuristics, Fall, Volume 1, № 1, pp. 9-32, 1995.

62. Bean, J. Genetic Algorithms and Random Keys for Sequencing and Optimization. //ORSA J. Computing, Volume 6, № 2, pp. 154-160, 1994.

63. Beasley D. Bull D. Martin R. An Overview of Genetic Algorithms.//' In University Computing, 1993.

64. Bierwirth C., Mattfeld D. C. and Kopfer H. On Permutation Representations for Scheduling Problems. // Parallel Problem Solving from Nature, Springer-Verlag, Berlin, Heidelberg, Germany, pp. 310-318, 1996.

65. Blanton J., Wainwright R. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms. // Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann, 1993.

66. Вгискег P., Hurink, J. and Werner, F. Improving Local Search Heuristics for Some Scheduling Problems. // Discrete Applied Mathematics, Volume 65, № 3, pp. 97-122, 1996.

67. Bruns R. Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling. // Proceedings of the 5th International Conference on Genetic Algorithms, 1993.

68. Chang Y. L, Sueyoshi T. and Sullivan, R. S. Ranking Dispatching Rules by Data Envelopment Analysis in a Job-Shop Environment. // IIE Transactions, Volume 28, №8, 1996.

69. Cherkassky V. and Zhou D. N. Comparison of Conventional and Neural Network Heuristics for JobShop Scheduling // Proceedings of the SPIE -International Society for Optical Engineering, Orlando, Volume 2, № 1, pp. 815-825, 1992.

70. Cherkassky V., Gehring, D., Mulier, F. Comparison of Adaptive Methods for Function Estimation from Samples, IEEE Transactions on Neural Networks, Volume 7, № 4, pp. 969-984, 1996.

71. Conway R. W., Maxwell W. L., Miller L. W. Theory of Scheduling, -Addison-Wesley, Reading Massachusetts, 1967.

72. Dagli С. H. and Sittisathanchai S. Genetic Neuro-Scheduler A New Approach for Job-Shop Scheduling // International Journal of Production Economics, Volume 41, № 1-3, 1995.

73. Davis L. Job shop scheduling with genetic algorithms // Proceedings of the First Int. Conf. on genetic algorithms and their applications. Pittsburgh, PA: Laurence Erlbaum, 1985.

74. De Jong K.A. Adaptive System Design: A Genetic Approach // IEEE transactions on systems, Man and Cybernryics.,1980.

75. De Jong K.A. Learning with Genetic Algorithms: An Overview // Machine learning., Vol 3, 1988.

76. De Jong K., Spears W.M. Using genetic algorithms to solve NP-complete problems. // Proceedings of the Third International Conference on Genetic Algorithms, pp. 124-132., Morgan Kaufmann, 1989.

77. De Jong, K. and W. Spears A Formal Analysis of the Role of Multi-point Crossover in Genetic Algorithms. // Annals of Mathematics and Artificial Intelligence, Volume 5, № 1, 1992.

78. Evans J. R. Structural Analysis of Local Heuristics in Combinatorial Optimization // Computers and Operations Research, Volume 14, № 6, pp. 465-477, 1987.

79. Fang H.-L., Ross P., Corne D. A Promising Genetic Algorithm Approach to Job-Shop Scheduling, Rescheduling, and Open-Shop Scheduling Problems. // Department of Artificial Intelligence University of Edinburgh, UK, 1993.

80. Fang H.-L., Ross P., Corne D. A Promising Hybrid GA/Heuristic Approach for Open Shop Scheduling Problems. // Proceedings of the 11th European Conference on Artificial Intelligence, John Wiley and Sons, 1994.

81. Field Paul. A Multary Theory for Genetic Algorithms: Unifying Binary and Nonbinary Problem Representations. // University of London. 1999.

82. Fisher H. and Thompson G. L. Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. // Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, Ch 15, pp. 225-251, 1963.

83. Forrest S., Mitchell M. Towards a stronger building-blocks hypothesis: Effects of relative building-block fitness on GA performance. I I In Foundations of Genetic Algorithms, volume 2, pages 109—126, Vail, Colorado, Morgan Kaufmann, 1993.

84. Gere W. S. Jr. Heuristics in Job-Shop Scheduling // Management Science, Volume 13, pp. 167-190, 1966.

85. Giffler В., Thompson G. L. Algorithms for Solving Production Scheduling Problems // Operations Research, Volume 8, № 4, pp. 487-503, 1960.

86. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley. 1989, 412p.

87. Goldberg D.E. Sizing populations for serial and parallel genetic algorithms. //Proceedings of the Third International Conference on Genetic Algorithms, pp. 70-79, Morgan Kaufmann, 1989.

88. Goodman E. D. An Introduction to GALOPPS: Hie "Genetic Algorithm Optimized for Portability and Parallelism" System. // Technical Report # 96-07-01, Michigan State University, 1996.

89. Gottlieb J., Julstrom B.A., Raidl G.R., Rothlauf F. A Poor Representation of Spanning Trees for Evolutionary Search // IlliGAL Technical Report № 2001001.

90. Grabot В., Geneste, L. Dispatching Rules in Scheduling: A Fuzzy Approach. // International Journal of Production Research, Volume 32, № 4, pp. 903-915, 1994.

91. Grefenstette J.J. Optimization of control parameters for genetic algorithms. //IEEE Trans SMC, 1986.

92. Grefenstette J.J., Rosimaita B. Genetic Algorithm for the Traveling Salesman Problem. // Proceedings of the First Int. Conf. on genetic algorithms and their applications. Pittsburgh, PA: Laurence Erlbaum, 1985.

93. Hara H. Job-Shop Scheduling by Minimal Conflict Search // Japanese Artificial Intelligence Society, Volume 10, № 1, pp. 88-93, 1995.

94. Holland J. Adaptation in natural and artificial systems. The University of Michigan Press., Ann Arbor. 1975.

95. Johnson D. S., Aragon C. R., McGeoch L. A., Schevon C. Optimization by Simulated Annealing: An Experimental Evaluation. // Operations Research, Volume 37, № 6, pp. 865-892, 1989.

96. Johnson S.M. Optimal Two- and Three-Stage Production Schedules with Set-Up Times Included, Naval Research Logistics Quarterly, vol. 1, p.61-68, 1954.

97. Jones T.C., Forrest S. Genetic algorithms and heuristic search. // Technical Report 95-02-021, Santa Fe Institute, 1995.

98. Jones T.C., Rawlins G.J.E. Reverse hillclimbing, genetic algorithms and the busy beaver problem. // Proceedings of the Fifth International Conference, pp. 70-75, San Mateo, CA, Morgan Kaufmann, 1993.

99. Juels A. Wattenberg M. Stochastic Hillclimbing as a Baseline Method for Evaluating Genetic Algorithms. // University of California at Berkeley. 1994

100. Karr C., Freeman L.M. Genetic Algorithm Based Fuzzy Control of Spacecraft Autonomouse Rendezvous // Engineering Application of Artificial Intelligence, Volume 10, No3, 1997.

101. Kim S. Y., Lee Y. H. Agnihotri D. A Hybrid Approach for Sequencing Jobs using Heuristic Rules and Neural Networks // Production Planning and Control, Volume 6, № 5, pp. 445-454, 1995.

102. Knjazew D. Ordering messy genetic algorithm in С++. // IlliGAL Technical Report № 2000034.

103. Knjazew D., Goldberg D.E. OMEGA Ordering Messy GA: Solving Permutation Problems with the Fast Messy Genetic Algorithm and Random Keys // IlliGAL Technical Report № 2000004.

104. Knjazew D., Goldberg, D.E Large-Scale Permutation Optimization with the Ordering Messy Genetic Algorithm // IlliGAL Technical Report № 2000012.

105. Knjazew D. Application of the Fast Messy Genetic Algorithm to Permutation and Scheduling Problems. // IlliGAL Report № 2000022., 2000.

106. Kobayashi S., Ono I., Yamamura M. An Efficient Genetic Algorithm for Job Shop Scheduling Problem // Proceedings of the 6th International Conference on Genetic Algorithms, Morgan Kaufmann ,1995.

107. Koza John R. Genetic Programming: On Programming Computers by Means of Natural Selection and Genetics, MIT Press, 1992.

108. Kriiger K., Shakhlevich N. V., Sotskov Y. N., Werner, F. A Heuristic Decomposition Algorithm for Scheduling Problems on Mixed Graphs. // Journal of the Operational Research Society, Volume 46, 1995.

109. Kvasnicka V., Pelikan M., Jiri Pospichal Hill Climbing with Learning An Abstraction of Genetic Algorithm.// Proceedings of the First International Conference on Genetic Algorithms in Brno, 1995.

110. Lawrence S. Supplement to Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques. // Carnegie-Mellon University, Pittsburgh, USA, 1984.

111. Lee Y. H., Bhaskaran K. and Pinedo M. A Heuristic to Minimise the Total Weighted Tardiness with Sequence Dependent Setups // Technical Report, IEORDept, Columbia University, NY., 1992.

112. Lin S.-C., Goodman E.D., Punch W.F. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. // Michigan State University, 1997.

113. Lin S.-C., Goodman E.D., Punch W.F. Investigating Parallel Genetic Algorithms on Job Shop Scheduling Problems. // Michigan State University, 1997.

114. Lobo F.G., Goldberg D.E., Pelikan M. Time complexity of genetic algorithms on exponentially scaled problems // IlliGAL Technical Report №2000015.

115. Mahfoud S. W. An analysis of Boltzmann tournament selection: Part II: An experimental analysis of Boltzmann tournament selection // IlliGAL Report No. 94007, Urbana: University of Illinois., 1994.

116. Martin O., Otto S. W„ Felten E. W. Large-Step Markov Chains for TSP Incorporating Local Search Heuristics // Operations Research Letters, Volume 11, pp. 219-224., 1992.

117. Mattfeld D. C. Evolutionary Search and the Job Shop: Investigations on Genetic Algorithms for Production Scheduling // Physica-Verlag, Heidelberg, Germany. 1996.

118. Morton Т. E. and Pentico D. W. Heuristic Scheduling Systems, Wiley Series in Engineering and Technology Management, Wiley, New York., 1993.

119. Nakano R. & Yamada T. Conventional genetic algorithm for job shop problems. // Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann ,1991.

120. Nawaz M., Enscore E. E. Jr., Ham, I. A Heuristic Algorithm for the m-Machine n-Job Flow-shop Sequencing Problem // The International Journal of Management Science, Volume 11, № 1, pp. 91-95. 1983.

121. Norenkov I. Scheduling and Allocation for Simulation and Syntesis of CAD System Hardware. EWITD 94, Moscow, 1994.

122. Norenkov I., Goodman E., Solving Scheduling Problems via Evolutionary Methods for Rule Sequence Optimization., Soft Computing in Engineering Design and Manufacture, P.K. Chawdry, R. Roy, eds., Springer Verlag, 1998.

123. Norman B. & Bean J. A random keys genetic algorithm for job shop scheduling. // Engineering Design and Automation, Volume 3, 1997.

124. Ono O., Kobayashi В., Kato H. Optimal Dynamic Motion Planing of Autonomous Vehicles by a Structured Genetic Algorithm // Proceedings of the 13th World Congress off IFAC, Volume Q,1996.

125. Pelikan M., Goldberg D.E. Escaping Hierarchical Traps with Competent Genetic Algorithms. // IlliGAL Report No. №2001003., 2001.

126. Pelikan M., Goldberg D.E., Cantu-Paz E. Bayesian Optimization Algorithm, Population Sizing, and Time to Convergence // IlliGAL Technical Report №2000001.

127. Pelikan M., Goldberg D.E., Sastry K. Bayesian Optimization Algorithm, Decision Graphs, and Occam's Razor algorithms // IlliGAL Technical Report № 2000020.

128. Reeves C. R. (Ed.) Modern heuristic techniques for combinatorial problems. Oxford, UK.: Blackwell Scientific Press. 1993.

129. Rothlauf F., Goldberg D.E., Heinzl A. Network random keys a tree network representation scheme for genetic and evolutionary algorithms // IlliGAL Technical Report № 2000031.

130. Rudlof S., Koppen M. Stochastic Hill Climbing with Learning by Vectors of Normal Distributions. // Fraunhofer Institute for Production Systems and Design Technology, Berlin, 1996.

131. Sadeh N. and Fox, M. S. Variable and Value Ordering Heuristics for the Job Shop Scheduling // Artificial Intelligence, Volume 86, № 1, pp. 1-41., 1996.

132. Sastry K., Goldberg D.E. On Extended Compact Genetic Algorithm algorithms // IlliGAL Technical Report № 2000026.

133. Shi G. A Genetic Algorithm Applied to a Classic Job-Shop Scheduling Problem 11 International Journal of Systems Science, Volume 28, № 1, pp. 25-32., 1997.

134. Spears W. The role of mutation and recombination in evolutionary algorithms, George Mason University, Fairfax, VA, 1998.

135. Spears W., DeJong K. An analysis of multi-point crossover. // In Foundations of Genetic Algorithms, pp. 301-315. Morgan Kaufmann, 1991.

136. Spears W., De Jong K. On the virtues of parameterized uniform crossover. //International Conference on Genetic Algorithms, Volume 4, Morgan Kaufmann., 1991.

137. Spears. W. M. Recombination Parameters. // In The Handbook of Evolutionary Computation, IOP Publishing and Oxford University Press., 1997

138. Syswerda G. Uniform crossover in genetic algorithms. In International Conference on Genetic Algorithms, Volume 3, pp. 2-9, Morgan Kaufmann., 1989.

139. Tcheprasov V.,Punch W.,Goodman E.,Ragatz G., Norenkov I. A Genetic Algorithm to Generate a Pro-Active Scheduler for Printed Circuit Board Assembly, In Proc. EvGA'96, Moscow, 1996.

140. Uckun S., Bagchi S., Kawamura K., & Miyabe Y. Managing genetic search in job shop scheduling. // IEEE Expert, 8 (5), 1993.

141. Vaessens E.H.L. Aarts J.K. Job-shop scheduling by local Search. //Eindhoven University of Technology, 1994.

142. Vose M. Modeling simple genetic algorithms.// Evolutionary Computation, Volume 3, pp. 453-472., 1995.

143. Whitley D. An executable model of a simple genetic algorithm. // Foundations of Genetic Algorithms, Volume 2, pp. 45-62, Morgan Kaufmann, 1992.

144. Whitley D., Starkweather Т., Fuduay D. Scheduling problems and Traveling Salesman: the Genetic Edge Recombination Operator // Proceedings of the 3th International Conference on Genetic Algorithms, Morgan Kaufmann ,1989.

145. Whitley L.D., Yoo N.-W. Modeling simple genetic algorithms for permutation problems. In L.D. Whitley and M.D. Vose, editors, Foundations of Genetic Algorithms, volume 3, San Mateo, CA, 1995. Morgan Kaufmann.

146. William M. Spears and Kenneth A. De Jong. Dining with GAs: Operator Lunch Theorem. In Proceedings of Foundations of Genetic Algorithms, Springer-Verlag, 1998.

147. William M. Spears. The Role of Mutation and Recombination Evolutionary Algorithms / Ph.D. thesis, George Mason University, VA, 1998.

148. Yamada Т., Nakano R. Genetic Algorithms for Job-Shop Scheduling Problems //Proceedings of Modern Heuristic for Decision Support, pp. 67-81, UNICOM94, London, 1997.

149. Yamada Т., Nakano R. Job-shop scheduling // Genetic algorithms in engineering systems, The Institution of Electrical, 1997.

150. Yamada, Т., & Nakano, R. A genetic algorithm applicable to large-scale job-shop problems. Parallel Problem Solving from Nature. PPSNII, 1992.

151. Zalzala A., Fleming P. Genetic Algorithms: Principles and Applications in Engineering Systems. Neural Network, Volume 6, No5, 1996.