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


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


101

А /2

s Тогда задача отыскания минимального по дли-

лепипед РеЦ

тельности расписания для каждого teP(t = {ti,,.,,t)) может быть сформулирована следующим образом.

Для каждого t е Р найти минимум функционала

in(11.22)

при ограничениях

txkybj(11.23)

/=1 ~"

txlTiciti i = U.n.(11.24)

Если

XiO, то ixTcta (i=h--,n)(11.25)

для всех daRi

Ti>0 /=1,...,(11.26)

где Tl - величина интервала времени [т{, Г2 ];

Здесь г 6 Р(г = (/!,...,/„)) задает длительность работ, для которых находится оптимальное расписание.

i fl, если в 1-й интервал времени выполняется работа [О, если работа dj в этом интервале не выполняется,

с\ - равно единице в том случае, если существуют такие к, к2, что

1 + </, И Z XjTj » и при этом Xj = 1 ДЛя всех к< j <к-{к2.В

остальных случаях с/ = О •

Прежде чем перейти к описанию метода решения поставленной задачи, докажем вспомогательное утверждение. Зафиксируем какой-либо вектор teP, задающий длительность выполнения работ.



Среди всех допустимых расписаний задачи (11.22Н 11.26) рассмотрим те, которые могут быть получены по следующей схеме. При первом назначении работ на выполнение рассмотрим все подмножества работ,

которые могут выполняться на интервале [г1,Г2], не нарушая ограничений на последовательность выполнения работ и ресурсные ограничения. Пусть векторы jxp-,х[ соответствуют этим подмножествам работ так, что

1, если 1Я работа вошла в подмножество j

О, если i-H работа не вошла в подмножество у.

Введем отношение частичного порядка на множестве векторов Х},.-.,j. Будем считать, что х) х], если x)i Х 0* = 1,...,«). Заданное отношение порядка разбивает множество векторов на классы, в каждом из которых существует максимальный

элемент. Оставим среди множества векторов только мак-

симальные элементы и выберем какой-либо из них хр- Среди работ, соответствующих ненулевым координатам вектора хр» выберем такую работу , у которой время выполнения минимально. Положим

T]=t и будем считать, что работа d выполнена. После этого пе-Р\Р\

рейдем к построению совокупности векторов, соответст-

вующих множеству работ, готовых к выполнению после выполнения работы d .

Выполняя процедуру выбора максимальных элементов и выбирая один из таких элементов, найдем минимальную по продолжительности работу d с учетом ее возможного выполнения на предыдущем Pi

шаге. Будем считать Titр где tptpда"

t*p-tptp если Xрр=- Через к{к<п) шагов мы получим некоторое допустимое расписание задачи (11.22)-(11.26). Рассматривая



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

Каждое базовое расписание, учитывая определение 11.1, может быть представлено следующим образом. Сопоставим каждому вектору Xt »

задающему множество выполняемых работ на интервале [г1,Г2] номер JSfi самой короткой работы среди работ, соответствующих ненулевым координатам вектора Xi > учитывая при этом время выполнения этих работ на интервалах времени[rf,Г2],...[ri~\Г2"]. Получим, что множе-

ство векторов и номеров уД/ = 1,...,Л:) однозначно определяет допустимое базовое расписание.

Значение функционала (11.22) подсчитывается по формуле

к к

/=1/=1

где дг - продолжительность работы d м учетом ее возможного вы-полнения на этапах 1,...,/- 1. Если в задаче (11.22)-( 11.26) интервалы времени [?,] таковы, что t] = t] Для всех / = 1,..., «, то получена

задача оптимального распределения ресурсов с фиксированным временем выполнения работ. По построению среди базовых расписаний будет хотя бы одно расписание минимальной длины. Докажем следующее утверждение.

Лемма 11.1. Длина оптимального расписания задачи (11.22)-( 11.26) при фиксированном времени выполнения работ может быть представле-п

на как Y.Xiti, где x/g{0,1}.

Доказательство, Пусть Xp-JSTjj. - векторы оптимального расписания. Построим разбиение всех работ на К классов L\-Li следующим образом: di е Lj , если Ху = 1 (/ = 1, к). Сопоставим оптимальному расписанию орграф G, заданный следующим образом. Если d е Li,

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