назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [ 104 ] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


104

X ...X

В качестве одной из своих вершин

содержит начало координат. Тогда разбиение на многогранники устойчивости оптимальных решений обладает свойствами, описьюаемыми следующей леммой.

Лемма 11.4. Пусть для некоторого множества работ последовательность вьшолнения которых задана орграфом G,

существует разбиение параллелепипеда множеством гиперплоскостей {Гь..., Гл,} на многогранники устойчивости Д.(/ = 1,...,Л) оптимальных

решенийТогда это решение обладает следующими свойст-

вами:

1.Для любого другого параллелепипеда Р множество гиперплоскостей {Ль..., Лд,}, разбивающее параллелепипед на многогранники устойчивости оптимальных решений, таково, что

{Г1,...,Г,,,}с{Гь...,Гл,}.

2.Для каждого teP {и > 0: / = 1,..., п) существует Aj с {.4,...,}, которое является оптимальным для точки t.

3.Среди множества оптимальных решений {,...,}существуют такие, которые будут оптимальны для всех орграфов работ G, полученных из G удалением любого конечного числа работ. Доказательство. Утверждение 1 леммы 11.4 следует из того, что:

а)при построении всех возможных разбиений параллелепипеда Р на многогранники 5.(/ = 1,...,ЛГ) и соответствующих систем допустимых решений на каждом шаге построения какого-либо допустимого расписания на роль короткой работы будут претендовать все работы, вьшолнявшиеся на соответствующем интервале времени;

б)любые два допустимые расписания А и Ai, каждое из которых

остается допустимым для всех точек многогранников Bf и В, в

качестве нижней оценки времени выполнения всех работ имеют ноль.

Докажем утверждение 2 леммы 11.4. Выберем Я по формуле

Я = min -.



Тогда точка Я/ е Р . Из леммы 11.3 следует, что в этом случае t существует оптимальное расписание из системы оптимальных расписаний

Утверждение 3 леммы является следствием того факта, что при построении разбиения параллелепипеда Р на многогранники устойчивости оптимальных решений среди множества расписаний {А \,...уА д,} существуют оптимальные расписания для всех точек параллелепипеда Р, в том числе и для его граничных точек.

Пусть в орграф, задающий последовательность вьшолнения работ (ip...,(i„, входят пути S,...,S,. Определим понятия параллельно выполняемых работ.

Определение 11.2. Назовем работы и параллельно выполняемыми, если они не входят в один и тот же путь орграфа G.

Следующая лемма описывает свойства оптимальных расписаний при некоторых специальных ограничениях на параллелепипед Р, задающий длительность выполняемых работ.

Лемма 11.5. Пусть орграф G работ d,,.,,d задан матрицей R и объем ресурсов 6 = (й,...,й) настолько велик, что любые две параллельно

выполняемые работы могут выполняться одновременно. Тогда для любой работы d(l = 1,...,«) существует параллелепипед Р задающий длительности вьшолнения работ, при котором для всех точек параллелепипеда оптимальным будет любое базовое расписание, в котором в каждый момент времени выполняется работа из критического пути орграфа G.

Доказательство. Построим параллелепипед следующим образом. Зададим для всех работ J • = (/ ф I) произвольно интервалы вьшолнения

работ [/,/]. Для работы di выберем чтобы выполнялось неравен-

ство

а tf = ti + (2, где а > О.

Нетрудно видеть, что для всех tePi критическими могут быть только

пути, в которые вошла работа d. Так как Г > Тр , где Г - ллика

оптимального расписания, если на каждом этапе построения базового рас-320



писания выделять ресурсы в первую очередь работам критического пути, то по условию леммы Т = Tjp, что и доказывает утверждение леммы.

Рассмотрим еще один подход для получения многогранников устойчивости оптимальных решений, когда длительности выполнения работ меняются на параллелепипеде Р,

Пусть фиксирована tеР , Рассмотрим некоторое допустимое базовое решение задачи (11.22)-(11.26), когда длины выполнения работ равны = (г,...,/). Как бьшо показано вьппе, любое базовое решение может

быть представлено как набор векторов{Х1,..., Хк}, каждому из которых поставлена в соответствие работа dj(l = 1,...,А:), являющаяся самой короткой

работой среди работ, соответствующих ненулевым координатам вектора Xl. Каждому базовому расписанию может быть поставлена в соответствие система неравенства (11.33). Если построить систему неравенств для всех базовых решений точки и взять их объединение, то получим многогранник л/, на котором система базовых решений остается такой же, как и для точки . На многограннике А/* могут быть определены интервалы 1212

[Т Т ],...,[Г Г ] системы базовых расписаний {Л 1,..., }.

11 "-N N Выберем среди них

т\ = min Т.

Отбросим BCQTQAkil <к<ло, для которых[ТТ]п[TjlijTjjj] = 0-Остальные базовые расписания {i,..., Aj} {N <N) будут принимать оптимальные значения на некоторых точках многогранника М*. Пусть многогранник л/ задан системой неравенств

Ycijti<b] 7=l,2,...,m,; /=1

/,>0(/ = 1,...,«).

Тогда для решения Ак с {i,..., Ам} многогранник устойчивости оптимального решения А к задается следующим образом:

Y.Cijti<bj (7 = l,2,...,mp /,>0; / = 1,...,«); /=1

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [ 104 ] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]