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


[Старт] [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]


102

то Ri =0 (/ = 1, п). Если df eL и для <еще не построено Л/, то проверяем, существует ли к\:

(11.27)

В случае если (11.27) выполняется, то в множество R войдет работа м 1 где N i - номер кратчайшей работы для вектораЕсли

-1 = 1, то в Ri войдет только работа d ]\/ , в противном случае в Ri войдут еще и все работы R • В построенный учитывающий ресурсные ограничения орграф будет входить исходное множество работ d\,;dn и длина критического пути будет равна продолжительности

соответствующего базового расписания. Лемма доказана.

Рассмотрим свойства допустимых расписаний задачи (11.22)-(11.26) для случая, когда времена выполнения работ di заключены в интервалах Ui\ /] (/ = 1,..-, «). Выберем какую-либо точку t е Р и построим для нее систему базовых расписаний {i,..., л}. Пусть Ak - одно из базовых расписаний, которому соответствует набор векторов {Х\ ,,..yXk} и

набор номеров работОтметим, что для работы d вы-

полняется одно из условий:

1 j4 фО

mini

minlminl

где mini -номер работы, удовлетворяющий условию 1. Выберем все остальные работы:

/1 /2 minimini

(11.28)

Включим в множество М. те работы, которые удовлетворяют условию (11.28) и работу djnini. Нетрудно видеть, что для всякого t е Р кратчайшими работами среди работ, соответствующих ненулевым координатам вектора Х\, могут быть только те работы, которые принадлежат множеству М,. Выберем какую-либо работу dk е М\и «назначим»

ее самой короткой работой. Тогда очевидно, что длительность остальных



работ должна быт* такой, что > tk для всех /(1 <i<n) dt е М\. Поэтому преобразуем по формуле

t) = max dieM,

tit}}-

С другой стороны, понятно, что если dk - кратчайшая работа, то tk

не может быть больше любого из (di е Mi)

t} = min

t = t}, d, € Ml

(11.29)

(11.30)

После того как работа dk будет выполнена, интервалы, задающие длительность работ dl, для которых У1/ Ф О, будут удовлетворять следующим условиям:

tl = max

0,-1-I);

(11.31)

djEMi

tt!-tk\dieMx.(11.32)

Будем считать t} и t} равными правым частям в неравенствах (11.31) и (11.32). Сформируем далее множество максимальных векторов, характеризующих возможность вьшолнения остальных работ орграфа G после того как выполнена работа dk и выберем один из них: X-i. Затем, аналогично тому, как это бьшо сделано ранее, формируем множество кратчайших работ назначаем кратчайшую работу и преобразовываем интервалы

[t],t}] (/: )2i 0). Когда все работы будут выполнены, получим допустимое решение для всех точек t е Р , удовлетворяющих системе неравенств:

6,</,Д/=1,2,...,«; :с/=1),(11.33)

где Х! - вектор {Xi = {0,1}, / = 1,...,«), у которого ненулевые координаты соответствуют работам, вьшолняемым после завершения / - 1 работы.

если работа dk не выполнялась на интервале

к,- Z fkr-

i=l-\-mi

если работа dt выполнялась на интервале ./-1 ./-1



tj,если работа не выполнялась на интервале

i=l-\-mj- в противном случае.

где mi - число интервалов, предшествующих интервалу

, на ко-

торых выполнялась работа dki mt - количество интервалов, предше-

ствующих

, на которых вьшолнялась работа dtj, k - номер кратчайшей работы, вьшолняемой на интервале /(< / -1). Рассмотрев все возможные варианты назначения кратчайших работ из множества М,.,.М при фиксированном способе выбора максимальных векторов, получим такое множество базовых расписаний, что каждое из расписаний остается допустимым для всех точек многогранника, полученного из исходного параллелепипеда добавлением системы ограничений (11.33). Этот результат можно сформулировать в виде леммы.

Лемма 11.2. Пусть необходимо выполнить работы, последовательность выполнения которых задана орграфом G и длительность выполнения работ di может изменяться в интервалах [t},tf] (/ = 1, «). Тогда существует конечный набор базовых решенийи разбиение

параллелепипеда Р системой гиперплоскостей на многогранники В,„,В такое, что

1)11/ = ; /=1

2)для любого Bi существует такое базовое расписание Л; с {i,..., Л }, что оно остается допустимых для всех точек tsB.

Непосредственно используя лемму 11.2, можно доказать следующую теорему.

Теорема 11.1, Для любого орграфа G, задающего последовательность выполнения работ и любого параллелепипеда Р продолжительностей работ задачи (11.22)-( 11.26), существует множество гиперплоскостей, проходящих через начало координат и разбивающих параллелепипед Р на конечное число многогранников, и множество таких допустимых расписаний {Аи.„,Ам}, что каждому многограннику В (/=1,...,Л0 взаимно однозначно соответствует некоторое допустимое расписание

[Старт] [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]