8.Условия 1-оптимальности расписания

1- оптимальность расписания может быть установлена на основа­нии следующего признака.

Теорема 2. Для того чтобы расписание π было 1-оптимальным, достаточно, чтобы для каждой пары существовало , такое, что .

Доказательство. Если выполняется

то, в силу леммы 2, не существует ни одного эффективного преоб­разования расписания π. Следовательно, расписание 𝜋 являет­ся 1-оптимальным.

Теорема доказана.

9. 1-оптимальные алгоритмы

На основании проведенных выше исследований составим алгоритм поиска приближенно 1-оптимальных расписаний. Будем использовать эффективные преобразования. В основу алгоритмов положены лемма 2, утверждение 1 и теорема 2.

Алгоритм А1.

Шаг1 (выбор начального решения).

1. Задается 0, r:= 1.

2. Выбирается опорное расписание π.

3. Формируется матрица времен выполнения работ .

4. Вычисляется нижняя оценка С₀ длины расписаний с заданными параметрами

Если C(π) - C₀ ≤ , то π - искомое расписание (работа алго­ритма завершена).

Заметим, что приведенный здесь способ построения нижней оценки С₀ не является единственным.

Шаг 2 (элиминация неэффективных преобразований в соответ­ствии с леммой 2 и условием 14).

1. Фиксируется

2. Строится множество M критических путей матрицы А(𝜋) и со­ответствующее ему множество индексов I_M: u ∈ I_M ⇒ S_u ∈ M.

3. Формируется множество

Если , выполняется шаг 5, иначе Δ:= Δ_ag.

Шаг 3. Из множества исключается максимальный элемент. Пусть это . Если таких элементов несколько, выбор произво­лен.

Шаг 4. Выполняется преобразование

1. Если С(π) , то π*_opt = и работа алгоритма завершена.

2. Если

то

1. фиксируется := ;

2. из множества исключаются все элементы, меньшие ;

3. производится переназначение := .

Если , выполняется шаг 3, иначе - шаг 5.

Если = 0, то при условии , выполняется шаг 3, ина­че - шаг 5.

Шаг 5.

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

2. Если ,, то полагается r:= r + 1. Расписание объявляется опорным. Полагается π:= и осуществляется переход к шагу 2 (новая итерация).

Алгоритм А2.

Шаги 1 - 3, 4 (п. 1, п. 3), 5 совпадают с соответствующими ша­гами алгоритма А1.

Шаг 4. Выполняется преобразование .

2. Если

,

то фиксируется := и выполняется переход к шагу 5.

Список используемой литературы:

1. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. М: МГУ, 2001.

2. И.Ю. Мирецкий, М.А. Щербаков. Матричные модели и методы в теории расписаний Пенза: Издательство Пензенского государственного университета, 2003.

3. Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер. Теория расписаний. М: Наука, 1975.

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