Содержание к диссертации
Введение 4
1 Исследование комбинаторных свойств задачи 1 11 ^ 7} 13
Постановка задачи суммарного запаздывания для одного прибора 14
Алгоритмы построения оптимальных расписаний, основанные на декомпозиционных свойствах задачи 23
Построение оптимальных расписаний в случае фиксированного количества запаздывающих требований 33
Оценки SPT расписаний 41
Первая оценка 42
Вторая оценка 44
Задача построения набора требований с заданным оптимальным значением целевой функции 47
1.5 Результаты экспериментальных исследований 49
2 Полиномиально и псевдо- полиномиально разрешимые слу
чаи задачи 1 11 Yl 7) 57
Свойства оптимальных расписаний 59
Описание похода к решению примеров задачи 63
Алгоритм В-1 67
Алгоритм В-к 72
Алгоритм СЛ 77
Алгоритм В-п 85
3 Исследование свойств и приложения Алгоритма В-1 89
Свойство В-1 90
Алгоритм решения задач разбиения 94
Постановка и полиномиальная сводимость задач о разбиении 94
Алгоритм В-1-канонический 98
3.3 Алгоритм В-1-модифицироваиный 101
Заключение 111
Указатель обозначений 113
Список литературы 116
Введение к работе
В теории расписаний основное внимание уделяется вопросам оптимального распределения и упорядочения конечного множества требований, обслуживаемых детерминированными системами с одним или несколькими приборами при различных предположениях относительно характера их обслуживания [27]. Изучаемые в теории расписаний задачи выбора очередности обслуживания имеют самый общий характер и возникают при различных видах целенаправленной деятельности, например, при календарном планировании производства, транспортных перевозок, обучения, информационно-вычислительных процессов.
Принято считать, что исследование задач теории расписаний началось с публикации С. Джонсоном своей работы [49], в которой рассматривалась задача выбора очередности обслуживания множества деталей, каждая из которых должна пройти последовательную обработку на нескольких станках с целью минимизации момента окончания обслуживания всех деталей. Начиная с первых публикация по теории расписаний [48, 78, 72] выяснилось, что большинство рассматриваемых задач являются трудоемкими для решения. Поэтому, значительная часть работ в этой области посвящена исследованию и выявлению сложности задач1. Обзоры по задачам теории
хНа данный момент наиболее полная и постоянно обновляемая классификация NP-трудных и открытых задач теории расписаний приведена на сайтах и durr/query/.
расписаний и их сложности представлены в работах Гэри и Джонсона [5], Карпа [6], Лоулера [60], Ленстры и др. [61], Танаева и др. [27, 28], Брукера [37, 38]
Большинство задач теории расписаний являются NP-трудными, поэтому важным направлением исследований является разработка подходов к их решению. Задачи теории расписаний принадлежат классу экстремальных комбинаторных задач и допускают формулировку в терминах математического программирования. Поэтому при разработке алгоритмов их решения применяются идеи метода ветвей и границ [9, 25], динамического программирования [1, 50], методов нахождения приближенного решения [10, 11, 30]. В последнее время динамически развивается направление разработки алгоритмов параллельных вычислений для решения таких задач [23]. Среди работ, посвященных методам решения задач дискретной оптимизации в целом и теории расписаний в частности, можно выделить статьи [2, 3, 4, 47] и книги [24, 25, 26, 27, 28, 29, 31, 33, 36, 37, 41, 66].
В теории расписаний особое значение имеют задачи для одного прибора. Результаты, получаемые при исследовании данных задач, могут быть использованы для построения алгоритмов решения более сложных многоприборных и многостадийных задач, возникающих на практике. При этом, задачи для одного прибора могут быть использованы как для построения эвристических алгоритмов решения многоприборных и многостадийных задач, так и для получения оценок оптимального значения. Кроме того, решение некоторых многоприборных и многостадийных задач можно свести к решению некоторой совокупности задач для одного прибора.
Диссертационная работа посвящена исследованию классической NP- трудной (в обычном смысле) задачи теории расписаний минимизации суммар-
ного запаздывания для одного прибора (далее2 - задача 1 11 ^ Tj) с целью отыскания новых свойств оптимальных расписаний общего и некоторых частных случаев задачи, построения на их основе новых алгоритмов решения данной задачи и применения полученных результатов для построения алгоритма решения NP-полных задачи РАЗБИЕНИЕ.
Задача 1 11 )ї) впервые была сформулирована в статье [62]. Приведем краткую постановку задачи. Необходимо обслужить п требований на одном приборе. Прерывания при обслуживании, обслуживание более одного требования в каждый момент времени запрещены. Требования поступают на обслуживание одновременно в момент времени to. Требования пронумерованы числами 1,2,..., п, множество N = {1,2,..., п) называют множеством требований. Расписание обслуживания требований однозначно задается перестановкой 7Г элементов множества N. Основной характеристикой обслуживания требования j Є N при расписании 7г является момент окончания обслуживания Cj(tt). Величину Tj(n) = max{0, Cj(k) —dj} называют запаздыванием требования j при расписании 7Г. Задача 1 | | ^2 Tj заключается в построении такого расписания 7Г, при котором достигается минимум целевой функции F(ir) = J2jENTj(n)-
Основные используемые в дальнейшем обозначения представлены в разделе «Указатель обозначений».
Первые свойства оптимальных расписаний рассматриваемой задачи представлены в работе Эммонса [45]. Им, в частности, было установлено существование такого оптимального расписания 7г*, что если для требований г, j Є ./V выполняется pi < pj и d{ < dj, то обслуживание требова-
2В теории расписаний принята следующая нотация для обозначения задач. Каждой задаче соответствует запись а \ (3 \ -у, где а обозначает количество и тип доступных приборов, /3 описывает дополнительные ограничения задачи (например, наличие отношения предшествования между требованиями), 7 представляет собой критерий задачи.
ния і предшествует обслуживанию требования j при расписании 7Г*, т.е. {і —> j)ir*- В соответствии с этим условием, если dj = const (j Є N), то SPT расписание является оптимальным, и если pj = const (j Є N), то EDD расписание является оптимальным. Некоторые улучшения результатов Эммонса приведены в работах [46, 71]. Разработке алгоритмов построения оптимальных расписаний для рассматриваемой задачи, основанных на идее метода ветвей и границ, посвящены работы [12, 40, 44, 46, 65, 68, 71, 73, 74, 77, 81, 82, 83, 85]. Применение метода динамического программирования для построения алгоритмов решения рассматривалось в работах [35, 52, 57, 58, 67, 69, 76, 79]. Для решения примеров рассматриваемой задачи Б. Лоулером [58, 59] построены псевдополиномиальный алгоритм трудоемкости 0(п4 J2Pj)i а также вполне полиномиальный е- приближенный алгоритм с оценкой трудоемкости 0(п7/е). Последняя оценка была понижена М.Я. Ковалевым [8] на порядок.
Построению приближенных (в т.ч. эвристических) алгоритмов для задачи 1 || ^Tj посвящены работы [32, 34, 39, 51, 63, 64, 70, 86]. В статье [42] исследовались нижние оценки относительной погрешности суммарного запаздывания для расписаний, построенных с помощью всех известных для рассматриваемой задачи эвристических алгоритмов AU [63], MDD [34], PSK [64], WI [86], COVERT [39], NBR [51], и DEC/MDD, DEC/PSK, DEC/WI [70]. В этой статье были построены примеры, для которых данные эвристические алгоритмы имеют неограниченно большое значение относительной погрешности значения суммарного запаздывания.
NP-трудность рассматриваемой задачи минимизации суммарного запаздывания для одного прибора была установлена в 1990 году [43]. В работе [43] предложена схема полиномиального сведения задачи четно-нечетного разбиения к исследуемой задаче. Поскольку задача четно-нечетного раз-
биения является NP-полной в обычном смысле [5], то задача 1 || ]Г)7) является NP-трудной в обычном смысле.
Среди обзорных статей, посвященных задаче минимизации суммарного запаздывания для одного прибора и смежных ей задачах, следует выделить работы [53, 75, 80, 84].
С задачей 1 11 ^ Ъ тесно связана задача минимизации суммарного опережения для одного прибора. Эта задача заключается в построении расписания, при котором достигается минимальное значение целевой функции YTj=\ max{0, dj — Cj(ir)}. Данные задачи эквивалентны с той точки зрения, что алгоритм решения одной задачи может быть использован для получения решения второй задачи. Пусть / = ({Pj,dj}jeN,to) является примером задачи суммарного запаздывания. Построим пример задачи суммарного опережения Г = ({pj,dj-}j6W,o), гДе Ц = (to + ^2ieNPi) - dj + Pj, j Є N. Пусть 7г* = (ji,J2,---,Jn) является оптимальным расписанием для примера / задачи суммарного запаздывания. Тогда расписание -к'* — (jn,jn-i, > ji) является оптимальным расписанием для примера Г задачи суммарного опережения, и наоборот [43]. Поэтому, результаты, представленные в диссертации, непосредственным образом могут быть использованы для задачи минимизации суммарного опережения для одного прибора.
Диссертационная работа состоит из введения, трех глав, заключения и указателя обозначений. Список использованной литературы включает 86 наименований.
В первой главе рассматриваются комбинаторные свойства задачи минимизации суммарного запаздывания для одного прибора 1 11 Yl^i-. получены свойства оптимальных расписаний, приводятся алгоритмы решения примеров общего случая задачи на основе полученных свойств, а также
некоторые оценки оптимального значения целевой функции. В параграфе 1.1 приводится постановка исследуемой задачи, вводятся необходимые понятия и обозначения. Параграф 1.2 посвящен декомпозиционным свойствам задачи 1 11 ^Tj. В этом параграфе приводятся два алгоритма построения оптимальных расписаний общего случая задачи, основанные на переборе подходящих позиций для требования с максимальной продолжительностью в оптимальном расписании и дальнейшему разбиению примера на подпримеры по подходящим позициям. В параграфе 1.3 приводится алгоритм решения примеров, для которых при любом расписании запаздывает постоянное количество требований. В параграфе 1.4 приводятся некоторые оценки оптимального значения целевой функции, полученные с помощью исследования свойств SPT расписаний. Параграф 1.5 посвящен эскпериментальным исследованиям задачи 1 11 Yl Tj.
Вторая глава посвящена исследованию частного случая задачи, когда параметры требований удовлетворяют условиям
Pi > V2 > > Рп d\ < d2 < - < dn.
В параграфе 2.1 формулируются и доказываются две леммы, которые устанавливают свойства оптимальных расписаний в рассматриваемом случае. В параграфе 2.2 описывается подход к решению примеров в данном случае, при котором (а) производится разбиение множества требований N на к подмножеств .Мі, Лі2,..., Мк, таких что разница между максимальным и минимальным директивными сроками требований из одного подмножества меньше, чем минимальная продолжительность обслуживания требований из этого подмножества, и (Ь) построение оптимального расписания на основе полученного разбиения с использованием идеи метода динамического программирования. В параграфе 2.4 приводится Алгоритм В-к решения
данного случая с трудоемкостью 0(kn^/?j). Особо выделяются три под-случая исследуемого случая, для которых получены свойства оптимальных расписаний и предложены соответствующие алгоритмы решения:
в параграфе 2.3 - иодслучай k = 1, для решения которого используется предложенный в работе [14](с.80) Алгоритм ВЛ трудоемкости 0(n^2Pj) операций (свойства и модификации данного алгоритма изучаются в третьей главе диссертации);
в параграфе 2.5 - подслучай dn — d\ < 1, для решения которого предложен Алгоритм СЛ трудоемкости 0{п2) операций;
в параграфе 2.6 - подслучай k = п, для решения которого предложен Алгоритм В-п трудоемкости 0(п2) операций.
Исследуемый во второй главе случай интересен по следующим причинам. Во-первых, данному случаю принадлежат примеры, для которых не существует априорного отношения предшествования на множестве требований, заданных условиями Эммонса. Во-вторых, как было показано в работе [42], на некоторых примерах, принадлежащих данному случаю, достигается наибольшая относительная погрешность для известных эвристических алгоритмов,
В третьей главе диссертации изучаются свойства Алгоритма ВЛ. В параграфе 3.1 определяется расписание, обладающее Свойством В-1, и доказывается теорема о том, что Алгоритм ВЛ оптимальное расписание для некоторого примера / тогда и только тогда, когда существует оптимальное расписание, обладающее Свойством В-1. В этом же параграфе приводится пример использования данной теоремы. В параграфе 3.2 рассматриваются три NP-полные задачи о разбиении: РАЗБИЕНИЕ, ЧЕТНО-НЕЧЕТНОЕ
РАЗБИЕНИЕ и ЧЕТНО-НЕЧЕТНОЕ РАЗБИЕНИЕ С ОГРАНИЧЕНИЯМИ, приводятся схемы полиномиального сведения данных задач друг к другу и к задаче 1 11 ^ 7} (при этом использованы материалы статьи [43]). Примеры задачи 1 11 ]Г}7), которые получаются путем применения схемы полиномиального сведения к примерам указанных задач о разбиении, будем называть каноническими примерами. В параграфе 3.2 показывается, что Алгоритм ВЛ находит оптимальное расписание для канонических примеров, и, следовательно, может быть использован для решения рассматриваемых задач о разбиении. Приводится Алгоритм ВЛ-канонический, который является модификацией Алгоритма ВЛ с учетом особенностей канонических примеров. При этом, трудоемкость использования Алгоритма В-I-канонический для решения задачи РАЗБИЕНИЕ не хуже, чем трудоемкость известного алгоритма Гэри и Джонсона [5]. В параграфе 3.3 рассматриваются свойства кусочно-линейных функций, которые возникают при использовании Алгоритма ВЛ, и операции над данными функциями. Приводится Алгоритм ВЛ-модифицированный, при использовании которого сокращается трудоемкость решения примеров по сравнению с использованием Алгоритма ВЛ.
Основные результаты диссертации изложены в одиннадцати публикациях, в том числе две из них в центральной печати, шесть в материалах и три в тезисах докладов на международных и российских конференциях. Результаты первой главы: теоретические и экспериментальные исследования различных алгоритмов решения рассматриваемой задачи 1 11 ]Г) 7} и оценки оптимального значения целевой функции, опубликованы в работах [7, 16, 17, 18, 19, 54]. Результаты второй главы: свойства оптимальных расписаний и полиномиальные и всевдополиномиальные алгоритмы решения для некоторых частных случаев задачи, - в работах [20, 22, 55]. Результаты
третьей главы: исследование и алгоритмы решения задачи РАЗБИЕНИЕ, - в работах [21, 56].
