ПЛАНИРОВАНИЕ ВЫПОЛНЕНИЯ РАБОТ ПРИ ПЕРЕМЕННОМ ОБЪЕМЕ ИСПОЛЬЗУЕМЫХ РЕСУРСОВ

Вернемся к задаче с фиксированным временем выполнения работ и рассмотрим зависимость времени выполнения всего множества работ по оптимальному расписанию от величины вектора ресурсов b = {b_v ..., b_m) при условии, что для любой работы dj количество потребляемого ресурса a_(j в процессе ее выполнения постоянно. Легко видеть, что для того, чтобы все работы могли быть выполнены, вектор b должен удовлетворять следующим условиям:

С другой стороны, если вектор ресурсов b таков, что можно построить базовое расписание, для которого в каждый момент времени выполняются все работы, удовлетворяющие ограничениям на последовательность выполнения работ, то время выполнения всех работ будет равно длине критического пути в орграфе G. Очевидно, что в этом случае система базовых допустимых расписаний будет состоять из единственного расписания. Вектор b = (Ь_{,..., Ь_т) при этом должен удовлетворять условиям:

где {Х,..., X"} — множество векторов единственного в данном случае оптимального расписания.

Обозначим правую часть неравенства (2.24) через Ь™^ах, а правую часть неравенства (2.23) — через Iff"". Очевидно, что b™^ax > bj"ⁿj = 1, ..., т, и если Ь™^ах = Ь™^т, то ограничения на последовательность выполнения работ таковы, что в каждый момент времени можно выполнять только одну работу.

Лемма 2.9. Параллелепипед может быть

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

Доказательство. Пусть {А,..., } — система всех базовых распи

сании для точки bj = bf"ⁿ.

Не уменьшая общности, можно считать, что где Т. 1 — длина Л! допустимого расписания. Для каждого вектораХ.¹

А ¹ J

(у = 1,..., п) проверяем, позволяют ли топологические ограничения на последовательность выполнения работ увеличить в векторах Х.^[ число ненулевых координат, увеличив соответственно вектор ресурсов bf¹¹". Рассмотрим все возможные варианты добавления новых работ для каждого из векторов и все возможные соответствующие векторы изменения ресурсов A bj,..., А Ь^, выберем среди них минимальные Ab^lK < АЬ¹К (К_{ > 0) по правилу Abf < АЬ, если Ab^[KJ < Ab^lej (у = = 1, ..., m). Проделав эту операцию по всем векторам всех базовых расписаний {A_{,...,A_N } и выбрав минимальные элементы, получим набор векторов {A b,..., АЬц}.

Для каждого Ab] (i = 1, ..., L_{), пересчитав соответствующие базовые расписания, получим новую систему базовых расписаний , такую, что Тогда существует такое

, что Очевидно, что е

е {А,..., Поэтому для каждого А² (/= 1,К_{) существует соответствующий вектор АД,- е {АД¹,Ab]^}, такой, что решение А² является оптимальным, если С? > Ь? > Ь + Ь^хи, где Cf — вектор, координаты которого будут определены ниже.

Если Т_А2 = Т_кр, где Г_кр — длина критического пути исходного орграфа работ, то для вектора ресурсов Ь построено оптимальное расписание для заданного орграфа G и заданных времен выполнения работ, которое не улучшится, как бы мы ни увеличивали ресурсы. В этом случае положим С² = b^max (b^max = (6™³*,..., 6™^ах)).

Если Т_А2 > Т_КР, то для каждого вектора ресурсов Д. (/ = 1, ..., X,) считаем систему минимальных векторов {АД²,..., АЬ²^}, затем строим систему допустимых базовых расписаний {Д³,..., Д^} для вектора увеличения ресурсов и производим сравнение 7з = Г_кр.

Очевидно, что через конечное число шагов получим Т^ех = Т_кр, при этом расписанию А соответствует некоторый вектор ресурсов Ъ^еу Включаем вектор Ь[ в множество M_Qm. Далее строим систему минимальных векторов {АД, ..., АД}, положим С.¹ = bj + Abj для векторов ресурсов tf,...,b^eL и среди векторов ресурсов {Af⁺¹,...,Z>?⁺|} отбрасываем те, для которых существует вектор Д е M_Qm такой, что М^+{ > Ь_г Если среди остальных векторов {Ь^+х,...,Ь^е^} есть такие Ab^ek^+x, что время соответствующего допустимого решения Af^+l = Т, то вклю- чаем bf⁺¹ в множество М. Нетрудно видеть, что через конечное

К ОПТ дг m т

число шагов получим такое N, что все векторы щ ,...,Ь^} будут либо отброшены, либо будут переведены в множество М_от.

Выше было показано, что каждому базовому решению соответствует некоторый орграф G, при этом длина критического пути в орграфе (7 равна длине соответствующего оптимального расписания.

Зададим структуру каждого орграфа работ матрицей R так, что каждый элемент строки / равен единице, если выполнение работ Д должно предшествовать выполнению работы Д, и нулю в противном случае.

Введем отношение частичного порядка для орграфов, в которые входят одни и те же работы. Будем считать, что R^l < R², если rl < г?. и существуют /, к для которых г¹ек < г²ек.

Теорема 2.3. Пусть задан орграф (?,, описываемый структурой R_] с фиксированными временами выполнения работ. Для того чтобы существовал вектор ресурсов b такой, что Т_А = Г_кр и R_l < R_v необходимо, чтобы существовало К такое, что с - с, > t . , где R-. — структура орграфа, соответствующая расписанию А_опт; Т_А — длина расписания А' с — длина критического пути в орграфе G,; с. — длина /f-пути в G_{ /_min — время самой короткой работы в орграфе G_v

Доказательство. Предположим, что для всех j = 1,N_{, где — количество путей в орграфе G_v выполняется с_кр - c_k < t_min и R_{ < R_T Тогда в орграфе G_v соответствующем расписанию А_от, есть такой путь, что

где с — длина пути в G₂; t_k — продолжительность одной из работ.

Неравенство (2.25) противоречит начальному предположению о том, чтс

В лемме 2.1 было показано, что для каждого орграфа G и параллелепипеда Р, в котором изменяются длины работ, существует такое разбиение параллелепипеда Р (может быть, неединственное) на многогранники В;:

где L — число разбиений; kj — количество многогранников в каждом разбиении;

б) в каждом разбиении для каждого 2? существует такое допустимое расписание А_р которое остается допустимым для всех точек t€ В.

Следующая теорема описывает случаи, когда к. = 1 (у = 1,..., L) и L= 1.

Теорема 2.3.1. Для каждого орграфа G можно так назначить интервалы длин работ, что в каждом разбиении kj= 1 (у = 1,..., L).

• 2. Для каждого орграфа С существует такой вектор Ь = (Ь_{,..., Ь_т), что L= 1.
• 3. Для каждого орграфа G существует такой вектор b = (b_v ...,Ь_т) и такие интервалы [tf, tf(i= 1,..., п), что L = 1.

Доказательство. Утверждение 1 теоремы 2.3.1 будет доказано, если интервалы [tj, tf] будут назначены так, что при построении любого базового расписания на каждом шаге построения кратчайшая работа будет определена однозначно. Перенумеруем произвольно все работы сети и назначим первой работе d_x интервал [tf, tf] произвольным образом; интервал длительности выполнения для работы d_e (1 < /< п) назначаем так, чтобы

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

Докажем утверждение 2 теоремы. Пусть {х_р ..., Хд,} — всевозможные векторы с булевыми переменными, такие, что для любого 1=1, ..., N и для любого к и у (к= 1, ..., nj = 1, ..., п) если x_jk = 1 и х.. = 1, то работы d. и d. не принадлежат одному пути, т.е. могут вы- полняться параллельно. Вектор b = (b_v ..., b_m) выберем следующим образом:

Легко видеть, что если bj(j = 1, ..., т) удовлетворяют условию (2.27), то на каждом шаге построения допустимого базового расписания система максимальных векторов будет состоять из одного вектора, и поэтому разбиение на многогранники, описанное в лемме 1.1, будет единственным.

Утверждение 3 теоремы 2.3.1 будет доказано, если интервалы [tj, t?] (i = 1, ..., п) построить по формуле (2.26), а вектор b = (Ь_{, ..., Ь_т) выбрать по формуле (2.27).

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

• 1) блок разбиения заданного параллелепипеда Р на многогранники устойчивости оптимальных расписаний;
• 2) поиск оптимального расписания по некоторой точке t е Р.

Алгоритм был реализован для множества, состоящего из девяти

работ.

В процессе численного эксперимента было установлено, что для некоторых случаев поиск решения и соответствующего ему многогранника по заданному t = {t_v ..., t_n) происходит в несколько раз быстрее, чем построение решения по методу ветвей и границ.