Содержание к диссертации
Введение
1 Алгоритмы решения задачи 1 11 2} и ее частных случаев 11
1.1 Постановка задачи минимизации суммарного запаздывания для одного прибора 1 11 J2 Tj 12
1.2 Точный алгоритм решения задачи 11|5^Tj 14
1.3 Случай В задачи l\\J2Tj 18
1.3.1 Случай В-1 и алгоритм его решения 18
1.3.2 Алгоритм В-1 модифицированный 21
1.3.3 Случай В-1 general и алгоритм его решения 23
1.4 Канонические примеры задачи 1|| ]>] 7) 31
1.4.1 Проблема Четно-Нечетного Разбиения (ЧНР) 31
1.4.2 Канонические DL-примеры задачи l|j Yl^j 32
1.4.3 Канонические LG-примеры задачи 1|| ^Tj 34
1.4.4 Свойства канонических LG-примеров ' 35
1.5 Трудоемкость известных алгоритмов для некоторых частных случаев задачи 54
1.5.1 Свойства канонических DL-примеров задачи 1|| X) Т,
1.5.2 Трудоемкость известных алгоритмов для канонических DL-примеров 65
1.5.3 Трудоемкость известных алгоритмов для случая BF 67
1.6 Метаэвристический подход решения задачи 11|^Tj 71
1.6.1 Алгоритм АСО для задачи 1|| J^Tj 71
1.6.2 Гибридный алгоритм 74
1.6.3 Эффективность алгоритмов для тестовых примеров Поттса и Ван Вассенхова 77
1.6.4 Эффективность алгоритмов для случая В-1 81
1.6.5 Эффективность алгоритмов для канонических DL-примеров 83
2 Графические алгоритмы решения задач Разбиение и Ранец 87
2.1 Алгоритм динамического программирования для задачи Ранец 88
2.2 Графический алгоритм для задачи Ранец 91
2.3 Трудоемкость графического алгоритма 97
2.4 Графический алгоритм для задачи Разбиение 98
2.4.1 Сокращение рассматриваемого интервала (схлопывание) 101
2.4.2 Пример 101
2.5 Трудоемкость Графического алгоритма для задачи Разбиение 105
2.6 Экспериментальная оценка трудоемкости Графического алгоритма 107
3 Исследование задач теории расписаний с отношениями предшествования и ресурсными ограничениями 112
3.1 Постановка задачи построения расписания проекта с учетом ограничений на ресурсы (RCPSP) 113
3.1.1 Алгоритм диспетчеризации для задачи RCPSP . 116
3.1.2 Задача RCPSP с прерываниями обслуживания требований 119
3.2 Относительная погрешность нижних оценок для задачи RCPSP 121
3.2.1 LBQ - длина критического пути 122
3.2.2 LB\ - максимальная загрузка ресурса 122
3.2.3 LBs - дополнение критического пути 123
3.2.4 Нижняя оценка Mingozzi 124
3.2.5 Оценка LBLG 128
3.3 Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний 132
3.3.1 Доказательство гипотезы для случая задачи RCPSP с одним ресурсом 138
3.4 Задача построения расписания для параллельных машин . 144
3.5 Частный случай задачи RCPSP с одним кумулятивным ресурсом мощности Qi и Pj — 1 147
3.6 Свойства задач построения расписания с ограничениями предшествования 150
3.6.1 Планарность сетевого графика для задач RCPSP и PMS150
3.6.2 Алгоритм укладки сетевого графика на плоскости . 153
3.6.3 Решение обратного примера для задач RCPSP и PMS 157
3.7 Метаэвристический алгоритм решения задачи RCPSP . 159
3.7.1 Алгоритм АСО в рамках 1С:УСО 164
Заключение 166
Список использованных источников 169
- Трудоемкость известных алгоритмов для некоторых частных случаев задачи
- Эффективность алгоритмов для тестовых примеров Поттса и Ван Вассенхова
- Экспериментальная оценка трудоемкости Графического алгоритма
- Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний
Введение к работе
В теории расписаний основное внимание уделяется вопросам оптимального распределения и упорядочения конечного множества требований, обслуживаемых детерминированными системами с одним или несколькими приборами при различных предположениях относительно характера их обслуживания [32]. Изучаемые в теории расписаний задачи выбора очередности обслуживания имеют самый общий характер и возникают при различных видах целенаправленной деятельности, например, при календарном планировании производства, строительства, транспортных перевозок, обучения, информационно-вычислительных процессов.
Принято считать, что исследование задач теории расписаний началось с публикации С. Джонсоном своей работы [64], в которой рассматривалась задача выбора очередности обслуживания множества деталей, каждая из которых должна пройти последовательную обработку на нескольких станках с целью минимизации момента окончания обслуживания всех деталей. Начиная с первых публикация по теории расписаний [63, 104, 98] выяснилось, что большинство рассматриваемых задач являются трудоемкими для решения. Поэтому, значительная часть работ в этой области посвящена исследованию и выявлению сложности задач1. Обзоры
*На данный момент наиболее полная и постоянно обновляемая классификация NP-трудных и открытых задач теории расписаний приведена на сайтах и durr/query/.
по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона [12], Карпа [14], Лаулера [81], Ленстры и др. [83], Танаева и др. [32, 33], Брукера [45, 46]
Большинство задач теории расписаний являются NP-трудными, поэтому важным направлением исследований является разработка подходов к их решению. Задачи теории расписаний принадлежат классу экстремальных комбинаторных задач и допускают формулировку в терминах математического программирования. Поэтому при разработке алгоритмов их решения применяются идеи метода ветвей и границ [17, 30], динамического программирования [1, 65], методов нахождения приближенного решения [18, 19, 35]. В последнее время динамически развивается направление разработки алгоритмов параллельных вычислений для решения таких задач [28]. Среди работ, посвященных методам решения задач дискретной оптимизации в целом и теории расписаний в частности, можно выделить статьи [2, 3, 4, 60] и книги [29, 30, 31, 32, 33, 34, 36, 40, 44, 45, 52, 91].
В теории расписаний особое значение имеют задачи для одного прибора. Результаты, получаемые при исследовании данных задач, могут быть использованы для построения алгоритмов решения более сложных многоприборных и многостадийных задач, возникающих на практике.
Диссертационная работа посвящена исследованию классической NP-трудной (в обычном смысле) задачи теории расписаний минимизации суммарного запаздывания для одного прибора (далее2 - задача 1 | |
2В теории расписаний принята следующая нотация для обозначения задач. Каждой задаче соответствует запись а | Р \ 7> где а обозначает количество и тип доступных приборов, /3 описывает дополнительные ограничения задачи (например, наличие отношения предшествования между требованиями), 7 представляет собой критерий задачи.
^2 Т3), исследованию NP-трудной (в сильном смысле) задачи построения расписания проекта с учетом ограничений на ресурсы (RCPSP), построению новых алгоритмов решения известных NP-трудных задачи Разбиение и задачи Ранец.
Целью исследований является отыскание новых свойств оптимальных решений, построения на их основе новых алгоритмов решения упомянутых задач и применения полученных результатов на практике.
Диссертационная работа состоит из введения, трех глав, заключения и одного приложения. Список использованных источников включает 110 наименований.
В первой главе приводятся результаты исследования классической задачи теории расписаний минимизации суммарного запаздывания для одного прибора 1 | | Yl^j- Предложены полиномиальные и псевдополиномиальный алгоритмы решения частных случаев задачи. Приводится доказательство NP-трудности в обычном смысле частного случая задачи. Показано, что популярные точные алгоритмы, для которых не получена оценка трудоемкости, имеют экспоненциальную трудоемкость на некоторых частных случаях, для которых предложены псевдополиномиальные и полиномиальные алгоритмы решения. На основе точного алгоритма и метаэвристического алгоритма "Муравьиные колонии" построен Гибридный алгоритм. Приводятся результаты его экспериментальных исследований на трех классах примеров.
Во второй главе приводятся два алгоритма решения классических NP-трудных задач Разбиение и Ранец, основанные на идее алгоритма В-1 модифицированный, описанного в первой главе и применяемого для решения задачи минимизации суммарного запаздывания. Приводятся
результаты экспериментальной оценки трудоемкости построенных алгоритмов.
В третьей главе рассматриваются задачи построения расписания на быстродействие (минимизация общего времени окончания обслуживания всего множества требований) с ресурсными ограничениями и отношениями предшествования. Данные задачи часто возникают на практике. Например, при строительстве того или иного объекта на разных стадиях строительства необходимо разное количество трудовых ресурсов, строительной техники, материалов и т.п. Между отдельными стадиями строительства существуют отношения предшествования обусловленные технологией. Требуется составить расписание выполнения работ, при котором не нарушаются отношения предшествования, ресурсные ограничения, и при этом срок окончания строительства минимален. Проведен анализ существующих алгоритмов вычисления нижних и верхних оценок. Показано, что для задачи построения расписания проекта с учетом ограничения на ресурсы (RCPSP) известные нижние оценки имеют относительную погрешность порядка размерности задачи или их нахождение - NP трудная задача. Выдвинута гипотеза, что оптимальные значения целевой функции для задачи RCPSP с прерываниями обслуживания требований и без прерываний отличаются не более чем в 2 раза. Доказательство (или опровержение) дайной гипотезы может оказать существенное влияние па построение эффективных алгоритмов решения задачи RCPSP. Показано, что любой пример задачи RCPSP можно преобразовать в аналогичный пример, граф отношений предшествования которого будет планарным, причем "мощность" графа не увеличится. Некоторые полученные результаты были доведены до практической реализации в программном продукте 1С:УСО и получили хорошую
— 10-
экспериментальную оценку.
Основные результаты диссертации изложены в тринадцати публикациях, в том числе три из них в центральной печати, восемь в материалах и тезисах докладов на международных и российских конференциях, две монографии. Результаты первой главы: теоретические и экспериментальные исследования различных алгоритмов решения рассматриваемой задачи 1 || Х^Т), - в работах [6, 7, 8, 9, 10, 11, 23, 25, 76, 51]. Результаты второй главы: исследование графических алгоритмов для задачи Разбиение и задачи Ранец, - в работах [10, 11, 75]. Результаты третьей главы: исследование задач теории расписаний с отношениями предшествования и ресурсными ограничениями, - в работах [10, 24, 77].
Трудоемкость известных алгоритмов для некоторых частных случаев задачи
В данной главе приводятся результаты исследования классической задачи теории расписаний минимизации суммарного запаздывания для одного прибора 1 ]С }- Предложены полиномиальные и псевдополиномиальный алгоритмы решения частных случаев задачи. Приводится доказательство NP-трудности в обычном смысле частного случая задачи. Показано, что популярные точные алгоритмы[107, 22, 50], для которых не получена оценка трудоемкости, имеют экспоненциальную трудоемкость на некоторых частных случаях, для которых предложены псевдополиномиальные и полиномиальные алгоритмы решения. На основе точного алгоритма и метаэвристического алгоритма "Муравьиные колонии" построен Гибридный алгоритм. Приводятся результаты его экспериментальных исследований на трех классах примеров.
В параграфе 1.1 приводится постановка исследуемой задачи, вводятся необходимые понятия и обозначения, описаны основные результаты исследования задачи, полученные другими исследователями. В параграфе 1.2 описываются известные правила сокращения перебора. Приводится точный алгоритм А, использующий при построении расписания правила исключения 1-4 [107, 22, 50]. Частный случай задачи и алгоритмы его решения рассмотрены в параграфе 1.3. В параграфе 1.4 исследуются два NP - трудных случая задачи -канонические примеры DL [55] и LG. Приводится доказательство NP -трудности частного случая В-1. В параграфе 1.5 показано, что известные точные алгоритмы [107, 108, 22, 50], для которых не получена оценка трудоемкости, имеют экспоненциальную трудоемкость для некоторых частных случаев задачи. В параграфе 1.6 приводятся Гибридный алгоритм решения задачи и результаты сравнительного анализа его эффективности и эффективности алгоритма "Муравьиные колонии". 1.1 Постановка задачи минимизации суммарного запаздывания для одного прибора 1 J 7} Необходимо обслужить п требований на одном приборе. Прерывания при обслуживании и обслуживание более одного требования в любой момент времени запрещены. Для требования j Є N = {1,2,..., n} заданы продолжительность обслуживания pj 0 и директивный срок окончания обслуживания d3, где N - множество требований, которые необходимо обслужить. Задан момент освобождения прибора to, с которого прибор готов начать обслуживание требований. Все требования поступают на обслуживание одновременно в момент времени Расписание обслуживания требований -к строится с момента времени to и однозначно задается перестановкой элементов множества N. Требуется построить расписание 7г обслуживания требований множества N, при котором достигается минимум функции F(7T,tQ) = X}j=imax{0) с-А7 ) 4? } гДе Cj C71")- момент завершения обслуживания требования j при расписании тт. Пусть 7г = {jiiJ2i---,jn)i тогда CjiC71") = о + Pji и Cjk(ir) = Cj -к) + Pjk для k = 2,3,...,п. Величина 7}(-7Г,о) = max{0, CJ(TT) — dj} называется запаздыванием требования j при расписании 7Г, a F(7r,t0) - суммарным запаздыванием требований множества N при расписании 7Г, построенном с момента времени to. В случае, когда Q = 0, будем обозначать 7}(7г) и F(ir). Исследуемая проблема является NP-трудной в обычном смысле [55]. Е.Л. Л аул ер [79] предложил псевдополиномиальный алгоритм решения общего случая проблемы трудоемкости 0(n4 2Pj)- В. Шварц и др. построили [107, 108] алгоритмы решения проблемы, которые были протестированы для примеров п 600 (тестовые примеры С.Н. Поттса и Л.Н. Ван Вассенхова [92]). Исследование приближенных алгоритмов решения проблемы было проведено в работе [53], где построены примеры, на которых известные приближенные алгоритмы находят решение с относительной погрешностью порядка размерности примера п. Определения. Расписание 7г = (ji, j2,..., jn) будем называть SPT-расписанием (short processing time), если выполняется p3-h р3і+к (для Pjk — Pjk+i имеем djk djk+l), к — 1,2, ...,n — 1. Расписание 7г называют LPT-расписаиием (large processing time), если pjk pjt+k (для pjk = pjk+1 выполняется djk djk+1), к = 1, 2,..., n — 1. Расписание 7Г = {ji,J2,jn) будем называть EDD-расписанием (early due date), если djk djk+1 (для dJk = djk+1 выполняется pjk Pjk+l). Расписание тг называется частичным расписанием, если при нем обслуживается некоторое подмножество требований N С JV. Также будем обозначать через P(N ) = J2i N Pi- Подмножество требований N С N, обслуживаемых при частичном расписании 7г будем обозначать через {тг }- Для частичного расписания 7г суммарную продолжительность обслуживания требований множества {-к } будем обозначать Р{тг ) = 2ІЄ{ТГ }РІ- ДЛЯ частичного расписания іг значение F(TT , t0) = ЕІЄ{7Г } max{0, сДтг ) - dj}. Через x = ({Pj,dj}j&N,to) обозначим пример проблемы, для которого требуется построить оптимальное расписание. Подпримером примера х будем называть пару {TV , t }, где N С N, N 0, и t t0. для произвольных Примеров Х\ = ({Pj, j}jeiVj) И #2 = ({ру, ф -+- С} едг,ї + С), где С - константа, множества оптимальных расписаний и оптимальные значения целевой функции совпадают. Такие примеры Х\ и Х2 будем называть эквивалентными примерами. Через (г —» j) обозначают, что требование г обслуживается раньше требования j при расписании 7Г. Без ограничения общности будем предполагать, что требования множества N пронумерованы в порядке неубывания директивных сроков di d2 ... dn, если dk = dk+i, то pk Pk+i
Эффективность алгоритмов для тестовых примеров Поттса и Ван Вассенхова
Кусочно-линейную функцию Fi(t), которая строится в процессе работы Алгоритма В-1 можно представить в виде: Fi(t) = a{t + bi,t Є [U, ti+i], і — 1,2,..., m, где U - точки "излома" функции, а аг- - количество запаздывающих требований при оптимальном частичном расписании на интервале [ti,tj.+i].
В результате последовательных вычислений будет построена функция Fi(t) := min{-P1(t),JP2( )} и соответствующее расписание 7г() из 7r1(t) и 7Г2(і) для любой точки t. Лемма 1.5 [15] Для случая (1.2) с помощью Алгоритма В-1 модифицированный будет построено оптимальное расписание. Алгоритм В-1 модифицированный перебирает не все целочисленные точки t из интервала [0,5 =1 как это происходит в Алгоритме В-1, а лишь точки "излома" графика функции Fi(t). Трудоемкость алгоритма полиномиально зависит от числа точек "излома". Идея данного алгоритма используется в алгоритмах, описанных во второй главе. Случай В-1 general и алгоритм его решения Рассмотрим следующий случай задачи: Лемма 1.6 Пусть выполняются условия (1.4) и при расписании 7Г = (Іі І2,jn) требование jk не запаздывает. Тогда при расписании 7г не запаздывают также требования ji,J2, ,jk-i Доказательство. Пусть требование jk не запаздывает при расписании 7г. Тогда Cjjjr) djk. Седовательно, для любого требования і Є Ob jk-i} выполняется: т.е. требования j\, J2, . ,jk-i при расписании 7г также не запаздывают.П Лемма 1.7 Пусть выполняются условия (1-4) и при расписании 7г = (іі)І2 ) требование jt запаздывает. Тогда при расписании 7г запаздывают также требования jk+i, ,jn Доказательство. Пусть требование jk запаздывает при расписании тт, т.е. выполняется Cjk(7r) djk. Покажем, что Cjk+l{iv) djk+1: Аналогично можно показать, что требования jk+2, запаздывают.П Несложно показать, что в случае (1.4) запаздывающие требования при оптимальном расписании обслуживаются в SPT порядке, кроме, быть может, первого запаздывающего требования. Лемма 1.8 ДЛЯ случая (1.4) существует оптимальное расписание вида {T EDDI SPT), KEDD и кSPT частичные расписания, построенные по правилам EDD и SPT, соответственно. Доказательство. Рассмотрим некоторое оптимальное расписание -тг = (тг1, 2), где I - первое по порядку запаздывающие требование. Покажем, что dn Q(7T) — р\. Предположим противное, пусть dn CI(TT) —pi. Рассмотрим CJ(IT), где j - требование, обслуживаемое последним при частичном расписании 7Г1. То Cj(ir) = сі(тт)—рі dn dj, т.е. j - также запаздывающее требование. Получили противоречие. Рассмотрим перестановку тг = (ji,.. ,jm-i,jm) из требований, которые обслуживаются при частичном расписании 7Г1, т.е. {7г } = {7Г1} Допустим, при расписании ттпеи) = (тг ,і,тг2), I - не первое запаздывающее требование. Покажем, что из 7г может запаздывать лишь требование jm Имеет место Cjm UeW) = Cjm(7Tn) - Pjm dn Pjm dn (dn - d{) = db TO cjm-A K new) — j m-i- Следовательно, требование jm \ не запаздывает. Аналогично можно показать, что не запаздывают требования Учитывая, что с 1) (момент завершения обслуживания всех требований множества {тг1} при расписании 7гпеш) неизменно, необходимо будет выбрать запаздывающим то требованием і Є {ji, - ,jm}, ПРИ котором с{і{1) — di минимально, т.е. с наибольшим директивным сроком. Тогда частичное расписание TCEDD будет оптимально для требований множества {7Г1}, где {TTEDD} = і71"1}- Более того, учитывая что в рассматриваемом оптимальном расписании 7Г = (7г1, Z, 7г2), I - первое запаздывающее требование, то все требования из частичного расписания KEDD будут не запаздывающими при расписании (KEDD, I,К2). Для случая (1.4) запаздывающие требования при оптимальном расписании обслуживаются в SPT порядке, кроме, быть может, первого запаздывающего требования, то существует оптимальное расписание вида тг = (KEDDJ,KSPT). Рассмотрим некоторое оптимальное расписание 7г = (ji,---,jk-hjk,jk+i,---,jn), где jk - первое запаздывающее требование, требования множества {j1;... ,jk-i} упорядочены по правилу EDD, а требования множества {jk+i,- ,jn} по правилу SPT. Если pjk Pjk+l, то расписание имеет вид (TTEDDJ SPT) И лемма формально верна. Если djk djk_1, то расписание имеет вид {T EDD SPT) И лемма верна.
Экспериментальная оценка трудоемкости Графического алгоритма
Выводы леммы 1.18 используются при доказательстве теоремы 1.6. При этом имеет место Ту (7г ) 25. Ситуация Ту (7г ) 25 нами не рассматривается, так как она не встречается.
На основе полученных лемм докажем следующую теорему. Теорема 1.6 Для случая (1.6) все оптимальные расписания являются каноническими (или могут быть преобразованы к каноническим расписаниям применением правила EDD к (n + 1) требованиям, обслуживаемым вначале расписания). Доказательство. Пусть 7Г - некоторое произвольное расписание. Согласно лемме 1.13 можно рассматривать только расписание следующего вида 7Г = {KEDDIKSPT), где {7Г/))} = (n + 1). При этом расписании требование V n+i занимает или позицию (п+1), или позицию (гг+2). Пусть расписание 7Г не каноническое. Так как 7Г не является каноническим расписанием, то в силу леммы 1.14 имеем при расписании 7Г пару требований {V -i, V }, которые не запаздывают, г п, или расписание 7Г имеет вид (1.7), при котором требование V2n+i обслуживается на (n + 2) месте. Если расписание имеет вид (1-?) т0 по лемме 1.15 для канонического расписания тх = выполняется F(TT) F(TT ). Переобозначим 7Г := 7г . Далее опишем алгоритм, состоящий из двух циклов, преобразования исходного расписания 7г к каноническому виду. Цикл 1. Пока среди не запаздывающих требований при очередном расписании 7Г присутствует пара требований V -i, Va, причем на позиции і "справа" обслуживается требование X $. {У2(і-і)-і,У2(г-і)}іХ Цп+1-Применяем для требований иХ перестановку описанную в леммах 1.16 и 1.17. В результате значение целевой функции уменьшится. Конец цикла 1. Переобозначим -к := тт . Количество шагов в цикле 1, очевидно, не превышает п. Первые (п + 1) требований при расписании 7Г упорядочим по правилу EDD. Требование V2n+i занимает или позицию (п + 1) или позицию п + 2 при расписании 7г. Если требование Ущ+і занимает позицию (n + 2) "слева" то позиции п и (п + 1) "слева" занимают требования УЇП-І и Vzn, соответственно, согласно циклу 1 и EDD сортировке. Рассмотрим возможные ситуации. I. Пусть требование У2П+і занимает позицию п + 2. Рассматривается некоторое расписание следующего вида 7Г = ( T b Vbn-ii nj ra+i) ), при котором требование V in обслуживается (п + 1) по порядку. При частичных расписаниях тт\ и 7г2 обслуживается по (п — 1) требованию, т.е. 1( )1 =п — 1 = П. Пусть требование V2n+i обслуживается (п + 1) по порядку. То в ситуации, описанной в лемме 1.18, будем иметь Ту(тт ) = Т2п+і{іг ) \8. Преобразование расписания, согласно лемме 1.18, уменьшит значение целевой функции. Цикл 2. Пока среди незапаздывающих требований при очередном расписании 7г присутствует пара требований V2i-i,V2i, причем на позиции -52 і "справа" обслуживается требование X Є {V («-i)-i V2(i-i)}- Применяем для требований X и У-ц перестановку, описанную в пунктах I и II. При этом значение целевой функции уменьшается. Конец цикла 2. Конец алгоритма преобразования исходного неканонического расписания. Таким образом, произвольное неканоническое расписание 7Г за 0(п) операций можно преобразовать к каноническому расписанию 7Г . Причем F(TT) F(TT ). Теорема 1.7 Решение примера ЧНР будет "ДА " тогда и только тогда, когда при оптимальном каноническом расписании С2П+і (тг) = (fan+i Доказательство. Рассмотрим каноническое расписание вида Функция Ф достигает максимальное значение равное Ф\ + 6— Е=і Є$ІІ когда Е"=і Ф(ъ)(йг) = Е1!=1е чт0 равнозначно Е"=і Н )й = E =i - Следовательно для модифицированного примера существуют два подмножества А\ и А2, таких что ЕаієЛі аг = 2агеА2 а (ответ "ДА"). При этом с2„+і(7г) = d2n+1. Если решение модифицированного примера ЧНР "НЕТ", то не выполняется равенство Х=і Ф{Ї)8І = \ Хї=і - "Учитывая значение d,2n+i, будем иметь c2n+i (7г) ф d2n+i Если С2п+і(тг) = d,2n+i, то из этого следует, что выполняется Yyi-=iPvtil = XX=i Pv2l + 2 — Y12.=i Ч,2, т-е- решение модифицированного примера ЧНР будет иметь ответ "ДА". 1.5 Трудоемкость известных алгоритмов для Некоторых частных случаев задачи 1 11 2 Tj В данном параграфе показано, что трудоемкость точных алгоритмов [107, 22, 50] решения задачи 1 Yl j экспоненциальная для двух частных случаев. Основу известных алгоритмов [107, 108, 22, 50] составляют следующие правила сокращения перебора: правила исключения 1-4 , анализ параметров Ej Lj, построение модифицированного примера. Показано, что алгоритмы, использующие только эти правила сокращения перебора, имеют экспоненциальную трудоемкость (от количества требований п) для некоторых частных случаев задачи 1 $ 7). В первом подразделе исследуется трудоемкость известных алгоритмов для канонических DL примеров [55]. Трудоемкость алгоритмов для частного случая BF, для которого существует алгоритм трудоемкости 0(п2) [15], анализируется в параграфе 1.5.3.
Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний
He трудно убедиться, что при любом расписании для любого примера случая (1.8) запаздывать будет ровно к требований. Для частного случая (1.8) в работе [15] приводится точный алгоритм решения трудоемкости 0{п2).
Лемма 1.24 Для примеров случая (1.8) дерево поиска содержит "двоичные ветвления" (рис. 1.4). Ветвление происходит при выборе позиции для очередного требования V -i- Для требования V2{ допустимой становится "противоположная" позиция, і = 1,..., (к — 1). Правила исключения 1 4 не сокращают "двоичные ветвления". Доказательство. Доказательство проводится аналогично доказательству леммы 1.19 и леммы 1.20. Предположим, что двоичное ветвление (когда первое требование из пары занимает "первую" или "последнюю" позицию, а второе требование из пары - "противоположную" позицию) имело место в парах 1,2,..., г — 1, і к. При очередном запуске процедуры ProcL(Nf,t ) рассматривается подмножество из п — 2г + 2 требований N С JV, Nr = {V -i, V n,..., Vn}. Множество требований N начинает обслуживаться с момента времени f = р2 + Р4 + + Р2І-2 + з где значение 5 удовлетворяет следующим ограничениям 0 6 Y?j=l(P2j-l Vlj) Vn Требование с максимальной продолжительностью обслуживания j = Vzi-i. Покажем, что "первая" и "последняя" позиции для требования У2%-1 подходящие. 1. Текущая "первая" позиция является для требования V -i подходящей. Очевидно, что правило б выполняется. Покажем, что выполняется правило а: . Требование V2i-i при постановке на "первую" позицию не запаздывает. Можно показать, что не запаздывает и "следующее" требование V2i Покажем, что Правило исключения 4 не исключает "первую" позицию. Рассмотрев 2 расписания 7г = (7Гі, V2i-i, V2i,-K2) И 7Г" = (тгь V2i, Цг-і,7г2), где P(TTI) = t\ легко убедиться, что Р(тт ) = F{TT"), т. к. при обоих расписаниях требования V i-i и V2i не запаздывают. Проводя аналогичные рассуждения не трудно доказать, что при постановке требования V i-i в "последнюю" позицию, для требования V2i допустимой становится "первая" позиция. 2. Покажем, что текущая "последняя" позиция для требования V2i-i подходящая. Покажем выполнение правила б. Покажем, что правило исключения 4 не сокращает перебор. Рассмотрим два частичных модифицированных EDD расписания 7г = (7Гі, 7Г2, 2і—і) и тг" = (тії, V -i, 7Г2), составленные из требований множества N , обслуживание которых начинается с момента времени t . Рассмотрим 2 случая. 2.1. Пусть при расписании У требование V i-i запаздывает. Очевидно, что при расписаниях 7г и 7г" запаздывают одни и те же требования. Для случая (1.2) запаздывающие требования при оптимальном расписании упорядочены в порядке SPT. Тогда F(ir ) F(TT"). 2.2. Пусть при расписании 7г" требование V2i-i не запаздывает. Представим расписания в виде: тг = (7Гі,7г2і,7Г22, V -i) и 7г" = (тгі, V2i-i,7r2i,7T22). Требования множества {7Г22} запаздывают при обоих расписаниях. Требования множества {7Г21}, (тггі О, при расписании 7г не запаздывают. Учитывая, что количество запаздывающих требований при любом полном расписании равно
