Меню
Главная
Авторизация/Регистрация
 
Главная arrow Логистика arrow Методы управления ограниченными ресурсами в логистике

РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ДЛЯ ВЫПОЛНЕНИЯ КОМПЛЕКСА РАБОТ ПРИ НЕТОЧНЫХ ЗНАЧЕНИЯХ ИСХОДНЫХ ПАРАМЕТРОВ МОДЕЛИ В ЛОГИСТИЧЕСКИХ СИСТЕМАХ

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

Проблемам распределения ограниченных ресурсов посвящены многочисленные отечественные и зарубежные публикации, к числу которых, в частности, принадлежат [7, 4]. К задачам, связанным с оптимальным распределение ресурсов, относятся прежде всего задачи дискретного сетевого планирования. Одна из распространенных постановок этих задач заключается в следующем.

Используя ограниченное множество ресурсов или обслуживающих приборов, необходимо выполнить определенную совокупность работ (заданий). Выполнение работ должно осуществляться с учетом ограничений, наложенных на последовательность их выполнения, и ограничений на используемые ресурсы в каждый момент времени выполнения работ. Критерием, по которому планируется последовательность выполнения работ, является либо минимизация времени, за которое будут выполнены все задания, либо среднее время пребывания заданий в системе. Постановки этих задач могут быть или детерминированными, т.е. все исходные параметры задачи заданы точно, или часть параметров, таких, например, как длительность выполнения заданий, множество выполняемых заданий, могут изменяться в заданных диапазонах.

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

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

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

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

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

Пусть есть множество работ dv ..., dn, последовательность выполнения которых задана ациклическим орграфом G, у которого отсутствуют транзитивные дуги, поэтому каждой работе dt может быть поставлено в соответствие множество работ Rj = {dRj так, что в множество Rj входят те и только те работы, которые должны быть выполнены, прежде чем может быть начато выполнение работы dr

Каждая работа характеризуется интервалом длительности выполнения [г!, Й]. Длительность работы dj может быть любым числом из интервала [t, t^. Ресурсы, необходимые для выполнения работы dp задаются вектором я, = п, где дг. — количество ресурсов

вида у, необходимых для выполнения работы i (/= 1,..., nj= 1,..., т). Общий объем ресурсов, который может привлекаться к выполнению работ, задается вектором b = {,..., Ьт).

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

Определение 2.1. Допустимым расписанием выполнения работ dv ..., dn назовем набор множеств работ Хг ..., Хк и набор интервалов времени [xj, х!,], ..., [х*, х*] длиной Tv ..., Тк соответственно такой, что в интервале времени [xj, х^] выполняются работы только из множества X. (/ = 1, ..., К; К < п). При этом должны выполняться следующие ограничения:

1) работа dj может начать выполняться только в том случае, если выполнены все работы /?..

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

  • 2) общий объем используемых ресурсов в каждый момент времени интервалов [т}, т^] не должен превышать значения Ь. (J = 1,
  • т)
  • 3) все работы d. (/= 1, п) должны непрерывно выполняться в течение времени где /. — продолжительность работы dr

Задача составления оптимального расписания заключается в том,

чтобы для каждого вектора длительности работ найти расписание минимальной длины. Обозначим через Р «-мерный параллелепипед Тогда задача отыскания ми

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

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

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

Если , то для всех

где величина интервала времени

Пусть ) задает длительность работ, для которых

находится оптимальное расписание.

C't — равно единице в том случае, если существуют такие Kv Kv что и при этом Xj = 1 для всех K{{ +

+ К2. В остальных случаях С' = 0.

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

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

нарушая ограничения на последовательностьвыполнения работ и ресурсные ограничения. Пусть векторы соответствуют

этим подмножествам работ так, что

Введем отношение частичногопорядка на множестве векторов Будем считать, что , если

Заданное отношение порядка разбивает множество векторов на классы, в каждом из которых существует максимальный элемент. Оставим среди множества векторов {Х,...,Х } только максимальные элементы и выберем какой-либо из них: Xх.

Среди работ, соответствующих ненулевым координатам вектора Xх, выберем такую работу dpl, у которой время выполнения минимально. Положим Г, = tp] и будем считать, что работа d х выполнена. После этого перейдем к построению совокупности векторов {Х,...,Ххк}, соответствующих множеству работ, готовых к выполнению после выполнения работы.

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

если Хрр2 = 1. Через к (к <п) шагов мы получим некоторое допустимое расписание задачи (2.1)—(2.5). Рассматривая все возможные варианты выбора максимальных элементов на всех этапах построения допустимого расписания, получим множество допустимых расписаний, которые назовем базовым множеством расписаний.

Каждое базовое расписание, учитывая определение 2.1, может быть представлено следующим образом. Сопоставим каждому вектору Хг задающему множество выполняемых работ на интервале [т'р г'2], номер Ж самой короткой работы среди работ, соответствующих ненулевым координатам вектора Хг учитывая при этом время выполнения этих работ на интервалах времени [т[, т^],[т{-1, т^-1]. Получим, что множество векторов X. и номеров работ Ж/ (/= 1, ..., к) однозначно определяет допустимое базовое расписание.

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

где t'N продолжительность работы dN c учетом ее возможного выполнения на этапах 1, ..., i - 1. Если в задаче (2.1)—(2.5) интервалы времени [t, t2] таковы, что t = t2 для всех i = 1, ..., п, то получена задача оптимального распределения ресурсов с фиксированным временем выполнения работ. По построению среди базовых расписаний будет хотя бы одно расписание минимальной длины.

Докажем следующее утверждение.

Лемма 2.1. Длина оптимального расписания задачи (2.1)—(2.5) при фиксированном времени исполнения работ может быть представлена как где Х{ е {0, 1}.

Доказательство. ПустьХ1?..., Хк векторы оптимального расписания. Построим разбиение всех работ на К классов Lv ..., Lk следующим образом: d. е Lj, если Х~= 1 (/= 1,..., к). Сопоставим оптимальному расписанию орграф G, заданный следующим образом. Если d. е Lj, то = 0 (/ = 1, ..., п). Если d. е ^и для d{ еще не построено R., то проверяем, существует ли К:.

В случае если (2.6) выполняется, то в множество Л войдет работа dN (, где N j — номер кратчайшей работы для вектора X v Если р - 1 = 1, то в Л войдет только работа dN , в противном случае в Л войдут еще и все работы RN . В построенный орграф будет входить исходное множество работ dv ..., dn, и длина критического пути будет равна продолжительности соответствующего базового расписания. Лемма доказана.

Рассмотрим свойства допустимых расписаний задачи (2.1)—(2.5) для случая, когда времена выполнения работ d{ заключены в интервалах (/= 1,я). Выберем какую-либо точку t е Р и построим для нее систему базовых расписаний х, AN). Пусть А1к — одно из базовых расписаний, которому соответствует набор векторов и набор номеров работ . Отметим, что для

работы выполняется одно из условий:

где min 1 — номер работы, удовлетворяющий условию 1).

Выберем все остальные работы:

Включим в множество Мх те работы, которые удовлетворяют условию (2.7), и работу dminV Нетрудно видеть, что для всех t е Р кратчайшими работами среди работ, соответствующих ненулевым координатам вектора Хх, могут быть только те работы, которые принадлежат множеству Мх. Выберем какую-либо работу dk е Мх и «назначим» ее самой короткой работой. Тогда очевидно, что длительность остальных работ должна быть такой, что t > t. для всех /(1 ) d; e Л/,. Поэтому преобразуем t по формуле

С другой стороны, понятно, что если dk кратчайшая работа, то t не может быть больше любого из t] (dj е Мх).

После того как работа dk будет выполнена, интервалы, задающие длительность работ d., для которых Хеи * 0, будут удовлетворять следующим условиям:

Будем считать tj и tf равными правым частям в неравенствах (2.10) и (2.11). Сформируем далее множество максимальных векторов, характеризующих возможность выполнения остальных работ орграфа G, после того как выполнена работа dk, и выберем один из них: Xj. Затем аналогично тому, как это было сделано выше, формируем множество кратчайших работ М2, назначаем кратчайшую работу и преобразовываем интервалы [t, г] (1 : Хкъ * 0). Когда все работы будут выполнены, получим допустимое решение для всех точек t е Р, удовлетворяющих системе неравенств:

где Xе вектор , у которого ненулевые координаты соответствуют работам, выполняемым после завершения (/ - 1)-й работы.

Здесь те число интервалов, предшествующих интервалу [тх|], на которых выполнялась работа dK; mj — количество интервалов, предшествующих [х, т|], на которых выполнялась работа dK; Kjномер кратчайшей работы, выполняемой на интервале / (/ < е - 1).

Рассмотрев все возможные варианты назначения кратчайших работ из множества М{, ..., Мп при фиксированном способе выбора максимальных векторов, получим такое множество базовых расписаний, что каждое из расписаний остается допустимым для всех точек многогранника, полученного из исходного параллелепипеда добавлением системы ограничений (2.12). Этот результат можно сформулировать в виде леммы.

Лемма 2.2. Пусть необходимо выполнить работы, последовательность выполнения которых задана орграфом G и длительность выполнения работ dt может изменяться в интервалах [tj, tf] (/=1,..., п). Тогда существует конечный набор базовых решений {, ..., AN} и разбиение параллелепипеда Р системой гиперплоскостей на многогранники Ву,..., BN:

2) для любого В.{ существует такое базовое расписание Af с: р ..., Ам), что оно остается допустимым для всех точек t е Вг

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

Теорема 2.1. Для любого орграфа G, задающего последовательность выполнения работ, и любого параллелепипеда Р задачи (2.1)— (2.5) существует множество гиперплоскостей, проходящих через начало координат и разбивающих параллелепипед Р на конечное число многогранников, и множество таких допустимых расписаний {.А{,..., An}, что каждому многограннику Bj(i= 1, ..., N) взаимно однозначно соответствует некоторое допустимое расписанное Aj с с {,..., An), которое остается оптимальным для всех точек многогранника Вг

Доказательство. Как было показано выше, при фиксированном времени выполнения работ для каждого базового расписания можно построить такой орграф G' из работ исходного орграфа G, что длина базового расписания будет равна длине критического пути орграфа G. Построим для базового расписания А{ соответствующий орграф G', отражающий последовательность выполнения работ по расписанию^.. Пусть Z>{,..., D'n — все пути орграфа G', соответствующего базовому расписанию Аг Тогда среди путей D[,..., D‘N существует по крайней мере один критический путь D'k такой, что для любой точки t g Bi длина расписания А( равна

Интервал изменения длины пути D'K, а значит, и интервал изменения длины расписания [Г/, Тf] могут быть оценены, если будут вычислены максимум и минимум функционала:

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

где t=(tv ..., tn), с' — матрица kxn; V=(Vp ..., Vk); неравенства (2.14), (2.15) задают многогранник Вг

Пусть [Г}, Т?] (/= 1,..., N) — верхнее и нижнее значения соответствующего базового расписания А. на многограннике Вг Определим для заданного разбиения величины Tlmin и Т2т[п по формулам:

Рассмотрев все возможные разбиения параллелепипеда Р на систему многогранников у ..., BNj} (i = 1,Ь2), где L2 количество разбиений при всех возможных вариантах выбора максимальных векторов на всех этапах построения допустимого расписания, получим возможность попарно сравнивать значения расписаний на общей части многогранников Ву На каждом шаге / (1 < / < п) построения допустимого базового расписания при новом разбиении параллелепипеда Р можем оценить снизу значение этого расписания.

Пусть Dy ..., Dк— все пути орграфа G, задающего последовательность выполнения работ. Вычислим минимум следующего выражения:

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

где D‘ — невыполненные работы пути D.; С — матрица кхп; к — количество ограничений, полученных за / шагов построения базового расписания.

Ограничения (2.16) задают построенный многогранник при составлении базового расписания. Обозначим Если

окажется, что где t] — нижняя оценка длительности кратчайших работ на этапах 1,2,1, то прекращаем дальнейшее построение допустимого расписания, так как оно заведомо хуже составленного ранее.

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

  • 1) интервалы длительности допустимых расписаний не пересекаются;
  • 2) интервалы длительности пересекаются.

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

Во втором случае проводится дополнительная разделяющая гиперплоскость вида

где в левой части равенства (2.17) стоит сумма длительностей работ соответствующего критического пути для нового, а в правой части — критического пути для ранее полученного допустимого расписания. Таким образом, мы разделили гиперплоскостью (2.17) общую часть многогранников для решения Лн и Аст на два многогранника и поставили каждому из них в соответствие решения Ан и Аст После того как будут произведены все возможные выборы максимальных векторов при построении допустимых расписаний, получим такое разбиение параллелепипеда Р на многогранники Bv ..., BN, что каждому многограннику В{ будет поставлено в соответствие расписание А х, которое будет наилучшим среди базовых допустимых расписаний для всех t е Вр а поэтому оно будет и оптимальным для этих точек.

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

Рассмотрим некоторые свойства разбиений, полученных в теореме 2.1.

Лемма 2.3. Пусть для орграфа G и параллелепипеда возможных времен выполнения работ Р существует разбиение на такие многогранники Вх (/ = 1,..., N), что каждому многограннику соответствует некоторое оптимальное для всех точек Вх решение А{ (i - 1, ..., TV). Тогда, если t ё Р, но существует такое X > 0, что Xt е Р, и такое Ак с с {Ах,..., An}, что является оптимальным расписанием для точки Xt, то расписание Ак будет оптимальным и для точки t.

Доказательство. Утверждение леммы 2.3 следует из того факта, что если в орграфе G с фиксированной длительностью выполнения работ и оптимальным расписанием А время выполнения всех работ умножить на одну и ту же константу с > 0, то расписание А останется оптимальным для орграфа G, продолжительность работ которого с/. (/= 1,..., п), где t. — первоначальная продолжительность работ.

Предположим, что для всех работ di (i= 1, ..., п) продолжительность работ изменяется в интервале [0, tj] (/= 1, ..., п), т.е. параллелепипед Р° = [0, /j2] х [0, /2] х ... х [0, /2] в качестве одной из своих вершин содержит начало координат. Тогда разбиение на многогранники устойчивости оптимальных решений обладает свойствами, описываемыми следующей леммой.

Лемма 2.4. Пусть для некоторого множества работ dv ..., dn, последовательность выполнения которых задана орграфом G, существует разбиение параллелепипеда Р° множеством гиперплоскостей {Г°, Г^} на многогранники устойчивости В. (/ = 1, N) оптимальных решений р AN). Тогда это решение обладает следующими свойствами.

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

  • 2. Для каждого t ё Р° (t. > 0; / = 1, ..., п) существует Ак с {Av ..., An}, которое является оптимальным для точки t.
  • 3. Среди множества оптимальных решений {Л,, ..., AN} существуют такие, которые будут оптимальны для всех орграфов работ G', полученных из G удалением любого конечного числа работ.

Доказательство. Утверждение 1 леммы 2.4 следует из того, что:

  • а) при построении всех возможных разбиений параллелепипеда Р на многогранники Bi(i= 1, ..., N'.) и соответствующих систем допустимых решений на каждом шаге построения какого-либо допустимого расписания на роль самой короткой работы будут претендовать все работы, выполнявшиеся на соответствующем интервале времени;
  • б) любые два допустимых расписания Ак и А, каждое из которых остается допустимым для всех точек многогранников Вк и Ве, в качестве нижней оценки времени выполнения всех работ имеют нуль.

Докажем утверждение 2 леммы 2.4.

Выберем X по формуле

Тогда точка Xt е Р. Из леммы 2.3 следует, что в этом случае для t существует оптимальное расписание из системы оптимальных расписаний {Л,°,..., А°м}.

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

Пусть в орграф, задающий последовательность выполнения работ d{,..., dn, входят пути Sv SK. Определим понятия параллельно выполняемых работ.

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

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

Лемма 2.5. Пусть орграф G работ dv ..., dn задан матрицей R и ресурсы b = (Ь{,..., bm) таковы, что любые две параллельно выполняемые работы могут выполняться одновременно. Тогда для любой работы de (е = 1, ..., п) существует параллелепипед Р длительности выполнения работ, при этом для всех точек параллелепипеда оптимальным будет любое базовое расписание, на каждом этапе выполнения которого выполняется работа из критического пути орграфа G.

Доказательство. Построим параллелепипед Ре следующим образом. Зададим для всех работ d} (/ * е) произвольно интервалы выполнения работ [tj, tf]. Для работы de выберем Р, чтобы выполнялось неравенство

Нетрудно видеть, что для всех / е Ре критическими могут быть только пути, в которые вошла работа de. Так как ТА^ > Ткр, где 7^ — длина оптимального расписания, если на каждом этапе построения базового расписания выделять ресурсы в первую очередь работам критического пути, то по условию леммы ТА^ = Ткр, что и доказывает утверждение леммы.

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

Пусть фиксирована t е Р. Рассмотрим некоторое допустимое базовое решение задачи (2.1)—(2.5), когда длины выполнения работ равны t' = (t, ..., /'). Как было показано выше, любое базовое решение может быть представлено как набор векторов {, ..., Х^, каждому из которых поставлена в соответствие работа de (/= 1,..., К), являющаяся самой короткой работой среди работ, соответствующих ненулевым координатам вектора Хг Каждому базовому расписанию может быть поставлена в соответствие система неравенств вида

зз

(2.12). Если построить систему неравенств для всех базовых решений точки f и взять их объединение, то получим многогранник М*, на котором система базовых решений остается такой же, как и для точки На многограннике М* могут быть определены интервалы [Т, Т12],..., [7^, rjy] системы базовых решений, задающие пределы, в которых может меняться длина базовых расписаний {Av ..., AN}.

Выберем среди них

Отбросим все те Ак (1 < К< N), для которых [ Рк, Рк) П [7^, 7^.п].

Остальные базовые расписания {,..., AN<} (TV, < N) будут принимать оптимальные значения на некоторых точках многогранника М*.

Пусть многогранник М* задан системой неравенств

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

гдезадает линейный функционал базового

расписания Aj.

Описанная выше процедура позволяет получить многогранник устойчивости М' оптимального решения по заданной точке t' е Р, и расписание А' остается оптимальным для всех точек t е М'. Это позволяет строить многогранники устойчивости оптимальных решений, не делая полного разбиения параллелепипеда на многогранники устойчивости оптимальных решений.

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

Пусть Gp GK вершины многогранника, заданного неравенствами (2.18), (2.19), координаты которых соответственно равны

Построим параллелепипед Р с вершинами:

Этот параллелепипед будет содержать в себе многогранник, заданный неравенствами (2.18)—(2.19). Для решения задачи разбиения на многогранники устойчивости для случая, когда время выполнения работ меняется на множестве, заданном неравенствами (2.18)—(2.19), нужно сделать разбиение на многогранники устойчивости оптимальных решений для параллелепипеда, заданного формулами (2.20)—(2.21), и после этого для каждой системы неравенств, задающих многогранник, добавить ограничения (2.18).

Пусть длина выполнения работ изменяется на многограннике Р, заданном неравенствами (2.18)—(2.19). Рассмотрим следующую задачу: среди точек многогранника Р найти такую, для которой значение оптимального расписания было бы не больше, чем для всех других точек многогранника Р. Назовем эту точку точкой глобального оптимума задачи (2.1)—(2.5). Если многогранник Р является

параллелепипедом то решение этой задачи дается следующей леммой.

Лемма 2.6. Вершина параллелепипеда Р, удовлетворяющая условию tl = tj, является точкой глобального оптимума для задачи (2.1)—(2.5) с нефиксированным временем выполнения работ.

Доказательство. Предположим, что существует t'*t и A'f < At, где А( и А[> — значения оптимальных расписаний для точек t и t'. Тогда среди координат точки t' = (t',..., ф существует tj> L (1 а для всех остальных / (/ = 1,2,..., п; i Ф j) t'>t.. Это означает, что, увеличив продолжительность работы dj, сократим длину оптимального расписания. Полученное противоречие и доказывает утверждение леммы.

В случае если многогранник М, заданный формулами (2.18)— (2.19), не является параллелепипедом, точка глобального оптимума может быть определена следующим образом. Сначала осуществляется разбиение многогранника М на многогранники устойчивости оптимальных решений М. (/ = 1, ..., N), где N — количество многогранников, полученных при разбиении, и пусть f. (/ = 1, ..., TV) — линейные функционалы, соответствующие оптимальному решению А . для многогранника М.. Далее решается для каждого М. задача минимизации функционала^. на многограннике и затем определяется

где^тш — минимум функционала^. на многограннике М..

Точка t е М, на которой будет выполняться (2.22), будет точкой глобального оптимума.

Теорема 2.2. Пусть длина выполнения работ заключена в многограннике М, заданном неравенствами (2.18)—(2.19). Тогда точка глобального оптимума является граничной точкой многогранника М.

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

Лемма 2.7. Пусть задан орграф, отражающий последовательность выполнения работ орграфа G с фиксированным временем выполнения работ t, и существует базовое оптимальное расписание Аопт для орграфа G. Тогда если длины всех работ умножить на С > 0, то оптимальное расписание сохранится и Т'л = СТА , где ТА — длина оп- тимального расписания для работ длительности t , а ТА длина опта-

I ''опт

мального расписания для работ с временем выполнения ctj (/ = 1, ..., л).

Доказательство. Утверждение леммы очевидно. Геометрически это означает, что если Аопт является оптимальным расписанием для точки t, то оно будет оптимально и для всех точек прямой, проходящей через начало координат и через точку t.

Лемма 2.8. Если в орграфе G с фиксированными длительностями выполнения работ время выполнения всех работ уменьшить на величину е > 0, то длина оптимального расписания уменьшится не менее чем на 8.

Доказательство. Выберем среди работ d.{ (/= 1,..., л) работу с максимальной продолжительностью dmax, время выполнения всех работ разделим на величину С. где

Из леммы 1.6 следует, что оптимальное расписание при этом не изменится.

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

Оценим, как изменилась продолжительность работ по сравнению с *,(/= 1,

Оценим, как изменилось время оптимального расписания:

Так как

Уменьшим теперь продолжительность всех работ на величину е(?тах “ ^)Ащах - Получим для всех работ f' = t. - г.

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

Доказательство теоремы 2.2. Предположим, что утверждение теоремы неверно, и поэтому точка глобального оптимума t = (t{, ..., tn) является внутренней. Тогда можно подобрать такое 8, что t' = = t. - е е М, а следовательно, по лемме длина оптимального расписания для точки t'n) меньше, чем для точки t = (t{,..., tn), что

противоречит первоначальному предположению.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы