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

• Автор: Тузиков, Александр Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Минск
• Количество страниц: 145 c. : ил

ШВА I. ЛЕКСИКОГРАФИЧЕСКАЯ МИНИМИЗАЦИЯ НА ПЕРЕСТАНОВКАХ

§ I. Основные ПОНЯТИЯ

§ 2. Постановка задачи. Векторные приоритето-порождающие функционалы

§ 3. Минимизация векторных приоритето-порождающих

функционалов

§ 4. Минимизация векторных функционалов специального

вида

Глава II. ОПИСАНИЕ МНОЖЕСТВА Я* ВСЕХ ОПТИМАЛЬНЫХ ПЕРЕСТАНОВОК

§ I. Описание множества Я* при заданном группировании элементов

§ 2. ^-допустимые графы

§ 3. Преобразование ориентированных графов

§ 4. Описание множества Я* при древовидных и последовательно-параллельных ограничениях предшествования
§ 5. Общий случай. Построение множества -Я*"
§ 6. Минимизация максимального штрафа на Я*
Глава III. РЕШЕНИЕ НЕКОТОРЫХ КЛАССОВ ДВУХКРИТЕРИАЛЬНЫХ
ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ
§ I. Постановка задачи. Схема решения
§ 2. Задачи на перестановках

§ 3. Сведение к задаче о назначении
§ 4. Минимизация максимального штрафа
§ 5. Нефиксированные длительности обслуживания ... 12
ЛИТЕРАТУРА

Многие практические задачи оптимального планирования, проектирования и управления приводят к необходимости рассмотрения многокритериальных оптимизационных задач в той или иной постановке. Несмотря на то, что к настоящему времени общая теория многокритериальной оптимизации достаточно развита [5,8,3,36) 39,44,45,49,60,35], по-прежнему актуальны вопросы разработки практически приемлемых методов решения многих классов многокритериальных задач с учетом их специфических особенностей.
Диссертационная работа посвящена разработке и исследованию эффективных алгоритмов решения некоторых классов многокритериальных задач теории расписаний. В рамках теории расписаний строятся и анализируются математические модели специфических ситуаций, постоянно возникающих при календарном планировании различных видов человеческой деятельности; создаются формальные методы принятия наилучших решений в этих ситуациях; вырабатываются практические рекомендации по улучшению планирования и управления [48]
Как самостоятельный раздел исследования операций, теория расписаний интенсивно развивается на протяжении последних 30 лет. Состояние этой теории достаточно полно отражено в монографиях [29^34, 47-, 49,50] . Рассмотрению многокритериальных задач теории расписаний уделялось явно недостаточное внимание. Лишь в последнее время многокритериальные задачи начали привлекать внимание специалистов, что объясняется с одной стороны возросшими потреб ностями решения практических задач, а с другой - значительными успехами в области решения однокритериальных задач теории расписаний. Задачи с несколькими упорядоченными по важности критериями рассматривались в [2.2 ,23,24,67.,65,66,74,92,99,102], а с неупорядоПоложим М = , Л=(/,Ж) и ^ _ множество висячих
вершин графа, полученного из & в результате удаления вершины I . Если М - 0 , то полагаем Л *= Л и алгоритм завершает работу. В противном случае переходим к отысканию следующего элемента с
Утверждение 4.1. Перестановка (^, гг,г/г), построенная по алгоритму 4.2, является оптимальной.
Доказательство. Пусть Л=( ^ > 1г у 1п ) произвольная оптимальная перестановка и 1*ь • Находим наименьшее Р ,5 <р* , 5 *•/>, <р справедливо ч 1р
В силу условия (4.4) соотношение 1р не имеет места ни для
каких р1; 5 ч р1 < р . Поэтому перестановка Л0 , полученная из л транспозицией элементов и 1р , принадлежит множеству (С) . Покажем, что перестановка Л° является оптимальной. Так как ^ >6^ в силу условия (4.3), то У-^(Л°))й у>Л}(^(Я ^ - 1, гг>1 для любых I * и уУУ£•/ (Я0)) ^ Ч>1>
5 5
^ Поэтому выполняется условие ^(Л°) ~ г .
Так как =4 Lp и функционал (Л) является 1-приоритето-по-рождающим П рода на /Рп(6) , то Ф*(Л)
этому перестановка Л° является оптимальной. Найдем в переста?-новке Л° ближайший справа к элементу ^ элемент £'* , та-
• / , ■' п~0
кой, что г$ ^ *р' . Перейдем от перестановки л к перестановке Л" транспозицией элементов и £р/ . Аналогично доказывается, что полученная перестановка Л" является оптимальной. Не более, чем за /г шагов построим оптимальную перестановку Л"', в которой элемент стоит на последнем месте. Выполняя аналогичные действия, построим перестановку Л'У , в которой элемент Iп.ч стоит на предпоследнем месте. За XI шагов будет по-