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

• Автор: Коваленко, Юлия Викторовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Омск
• Количество страниц: 129 с. : ил.

Оглавление
Введение
1. Задача составления расписаний с группировкой машин по технологиям
1.1. Постановка задачи и анализ ее сложности
1.2. Генетический алгоритм с равномерным кроссинговером
1.3. Генетический алгоритм с оптимальной рекомбинацией
1.4. Вычислительный эксперимент
2. Задача календарного планирования с переменной интенсивностью потребления и поступления ресурса возобновимого типа
2.1. Постановка задачи и анализ ее сложности
2.2. Дискретный случай
2.3. Вычислительный эксперимент
3. Оптимальная рекомбинация для задачи минимизации общего времени завершения на одной машине
3.1. Постановка задачи оптимальной рекомбинации
3.2. ЫР-трудность задачи оптимальной рекомбинации
3.3. Решение задачи оптимальной рекомбинации
3.4. Экспериментальное исследование задачи оптимальной рекомбинации в генетическом алгоритме
Заключение

Литература
Приложение
Приложение
Приложение
Введение
Стремительное развитие техники, появление новых технологий все чаще вызывает необходимость построения расписаний, связанных с функционированием промышленных предприятий и планированием выпуска продукции, а также эффективным использованием различного рода ресурсов.
Первые задачи составления расписаний были сформулированы и исследованы в 50-х годах прошлого столетия. Теория расписаний стала отдельным направлением в области оптимизации благодаря работам Конвея Р.В., Максвелла B.JI. и Миллера JI.B. [39], Танаева B.C. и Шкурбы В.В. [57], Веллмана Р. [5], Брукнера П. [71], Глебова Н.И. [8], Михайлевича B.C. [44] и др. Сейчас это направление активно развивается в работах Гимади Э.Х., Ковалева М.Я., Кононова A.B., Лазарева A.A., Серваха В.В., Севастьянова С.В. и других авторов [2, И,40,43,49,51,55,64,78,83,85,95,102,121].
Большое практическое значение имеют задачи составления расписаний для производства, где в процессе выполнения операций на имеющемся множестве машин происходит получение одних веществ из других. Вещества подразделяются на сырье, промежуточные и окончательные продукты. Различают задачи с прерываниями и без прерываний. В задачах с прерываниями каждая операция может быть прервана и возобновлена позднее (см., например, [2,49,64]), а в задачах без прерываний - не допускаются прерывания выполнения операций (см., например, [66,81]). Продукты могут производиться либо непрерывно [100,105], либо партиями [78,99]. Кроме того, необходимо учитывать погрузку, хранение и транспортировку продуктов, переналадку машин и т. д. Теоретическое и экспериментальное исследование такого рода задач представлено, например, в [3,4,55,78,83,103,105,110,114,120].

математических ожиданий имеем:
Я[0] = ^[©|С1,0 = С] • РІС1'0 = О < (Ті + т2) РІС1’0 = с) = Ті + т2.
С€П° СєП°
Далее справедливость утверждения следует из того, что после обнаружения оптимального генотипа, в каждой последующей популяции будет присутствовать такой генотип. Утверждение 1.2 доказано.
1.3. Генетический алгоритм с оптимальной рекомбинацией
Для решения задачи Р^е^, яіи(1Стах может быть использован генетический алгоритм с оптимальной рекомбинацией [68], основывающийся на решении серии подзадач вида (1.2) - (1.11), в которых часть булевых переменных исходной задачи фиксирована.
Используя схему представления решений из п. 1.2, сформулируем задачу оптимальной рекомбинации для Р^е^, 8іидСтах: для произвольных заданных родительских генотипов р1 = (С1,р1), р2 = (С2!7?2)! представляющих допустимые решения, требуется построить представляютций допустимое решение генотип С' = (С,7/), такой что:
(І) Сг3 = СІЗ ИЛИ Сгз = 4 Для всех * = 1= • • • Л 3 = 1. ■ • ' , иг ;
(ii) п[3 = л}3 или І%3 = г)13 для всех г = 1> • • • ,к,з = 1,...,иг ;
(iii) С' имеет минимальное значение целевой функции среди всех генотипов, удовлетворяющих условиям (І) И (ІІ).
Поскольку результатом оптимальной рекомбинации является один генотип, а не два, инструкции шагов 2.3 и 2.4 в ГА модифицируются соответствующим образом.
Исследуем сходимость ГА с оптимальной рекомбинацией и оценим среднее