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

д-р экон. наук, профессор РЭА им. Г.В. Плеханова

Степанова М.С.,
аспирант
МГТУ им. Н.Э. Баумана

<1> Работа выполнена при поддержке гранта РФФИ № 04-06-80121.

Инвестиционная фаза проекта является наиболее капиталоемкой на всем жизненном цикле самого проекта. Она заключается в проектировании и непосредственном строительстве системы или объекта, являющихся предметом проекта. Успешное выполнение всех действий, относящихся к инвестиционной фазе проекта, зависит от правильного планирования, которое позволяет определить необходимые параметры выполнения проекта: продолжительность по каждому из контролируемых элементов проекта, потребность в трудовых, материальных, технических и финансовых ресурсах, сроки поставки сырья, материалов. Планирование проекта позволяет реализовать проект в заданные сроки  с минимальной стоимостью в рамках нормативных затрат ресурсов.

Основная цель планирования на инвестиционной фазе проекта заключается в построении модели реализации проекта. С ее помощью определяется последовательность работ, которые должны быть выполнены, сроки выполнения этих работ и вычисляется допустимый и оптимальный план выполнения работ. Ниже представлена задача оптимизации выполнения комплекса работ (заданий), заданных сетевой моделью.

Постановка задачи

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

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

В общем виде рассматриваемые ниже задачи могут быть сформулированы следующим образом: 1) есть набор заданий T={T1,…, Tn}, подлежащий обработке и не допускающий прерываний; 2) знак < обозначает заданное отношение частичного порядка, которое определяет ограничения на последовательность выполнения заданий; знак Ti<Tj означает, что Ti должно быть выполнено раньше, чем начнется выполнение Tj; 3) задано m исполнителей с одинаковой производительностью, которые обрабатывают задания; 4) продолжительность выполнения заданий i есть функция параметра ti, меняющегося на интервале [ai, bi], то есть i= i(t), ti[ai, bi]. Для выполнения каждого задания необходимо непрерывно использовать одного исполнителя. Требуется так организовать обработку заданий (T1,…,Tn), чтобы при выполнении ограничений на последовательность обработки заданий и количество используемых исполнителей минимизировать время выполнения всех заданий при различных значениях ti[ai, bi], (i=1,…,n).

Необходимо отметить, что уже при фиксированных длительностях выполнения заданий данная задача является NP-полной [1]. Исследования таких задач рассмотрены в работах [1—3].

Анализ решений в условиях неточной информации

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

Следующее утверждение дает ответ на вопрос: «Всегда ли существуют длительности заданий, для которых данное базовое расписание является оптимальным?»

Утверждение 1. Каждое базовое расписание может быть оптимальным при соответствующих длинах заданий.

Доказательство. Сумма длин выполняемых заданий каждым исполнителем i выражается в виде . Здесь Pi — одно из подмножеств всего множества работ.

Выпишем систему m уравнений с n неизвестными (n>m):
=С, i=1,…,m,  >0, где C — суммарная длина заданий, выполняемых i-м
исполнителем.

Учитывая, что у этой системы всегда есть хотя бы одно отличное от 0 решение, получим доказательство утверждения. Длина работ, выполняемых исполнителем i, вычисляется по формуле , где i — число заданий у исполнителя i (i = 1,…,m).

В работе [6] изложен алгоритм вычисления максимальной величины  > 0, на которую может быть увеличена продолжительность выполнения каждого из заданий T1,…,Tn, сохраняющая прежней оптимальную последовательность их выполнения. Тогда может быть доказано следующее утверждение.

Утверждение 2. Пусть исходная продолжительность выполнения заданий определяется величинами  Если продолжительность выполнения заданий увеличить на любые , то интервал изменения [0,) может быть разбит на конечное число отрезков, на каждом из которых будет сохранять оптимальность одно из базовых расписаний.

Доказательство. Напомним, что согласно [4] базовой системой решений называется такое всевозможное распределение заданий по исполнителям, в котором перераспределение исполнителей по невыполненным заданиям происходит только в момент завершения одного или нескольких заданий. Число таких расписаний для n независимых заданий и m исполнителей вычисляется по формуле:

Согласно [5] каждому базовому расписанию Ri (i = 1,…,N) может быть поставлен однозначно в соответствие орграф, который задает последовательность выполнения заданий по расписанию Ri.

Обозначим через Sкр(Re,) длину критического пути в граґфе, соответствующем базовому расписанию Re. При увеличении всех длин заданий на величину e переход от одного оптимального расписания Rк к другому Re происходит, если Sкр(Re,) < Sкр(Rк,).

Это возможно, если число заданий в критическом пути Re меньше, чем число заданий в Rк, либо если число заданий одно и то же, но сумма длин заданий в критическом пути Re меньше, чем сумма длин заданий в Rк, то есть Sкр(Re,0) < Sкр(Rк,0). Учитывая конечность ситуаций первого и второго рода, получим требуемое утверждение.

Приведем несколько примеров, когда на всем интервале изменения [0,) сохраняет оптимальность одно базовое решение.

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

При увеличении длин заданий на любое [0,) это эквивалентно увеличению длин всех заданий в  раз (где  — длина задания). В этом случае, как показано в работе [6], множество оптимальных расписаний сохраняется и время оптимального расписания возрастает в  раз. Учитывая это, каждое оптимальное расписание сохранит оптимальность при увеличении всех длительностей на любое [0,).

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

Рассмотрим случай, когда длительности выполняемых заданий i могут принимать значения, задаваемые функцией , где  (i=1,…,n). Значения продолжительностей выполняемых заданий есть вектор-функция области значений из параллелепипеда P

В этой ситуации аналогично тому, как это показано в [4], может быть построена система базовых расписаний R1,…,Rn, каждое из которых принимает значение в интервале

Рассмотрим случай, когда длительности выполняемых работ i являются непрерывными функциями  параметра  (i = 1,…,n). Необходимо определить оптимальное расписание для продолжительностей i= i(t) для всех tP

В этом случае длительность работы i принимает все значения из интервала . при соответствующих параметрах t.

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

Каждое базовое расписание в этой ситуации характеризуется длиной расписания

и системой неравенств

Решив задачу максимизации и минимизации функционала (1) при ограничениях (2), получим интервал  в котором меняется длина расписания Ri.

Построим все возможные интервальные оценки для всех остальных базовых расписаний , k = 1,…,N.

Пусть R — такое базовое расписание, что

Образуем множество базовых расписаний R{R}, для которых выполняется соотношение

где {R} – множество всех базовых расписаний.

Очевидно, что при любых tP минимальными могут быть только расписания из множества {R}. Область изменения параметра tP, в которой расписание Rj{R} является оптимальным, вычисляется из следующих соотношений:

Здесь неравенство (3) отбраковывает все точки P, на которых расписание Rj будет иметь большую длину, чем какое-либо из базовых расписаний (3). Неравенства (4) аналогично [4] задают соотношение между длинами заданий, определяющих расписание Rj.

Таким образом, параллелепипед  может быть разбит на конечное число непересекающихся множеств M1,…,ML (здесь L равно числу базовых расписаний, содержащихся в {R}), каждому из которых соответствует одно базовое расписание Ri{R}. Оно является оптимальным для всех длительностей заданий из Mi.

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

Рассмотрим влияние изменения последовательности выполнения заданий на оптимальное расписание. Пусть последовательность выполнения заданий определяется орграфом G(m,n) с n вершинами, означающими задания, и m дугами, которые отражают последовательность выполнения задания. Последовательность выполнения заданий может быть также задана с помощью матрицы (rij) размером n x n. Здесь rij задается следующим образом:  

<1>  Если для выполнения i-го задания не должно быть предварительно выполнено задание j.
<2> Если задание i может быть начато только после выполнения j.

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

Утверждение 3. Пусть задано n заданий, выполняемых m исполнителями, с последовательностью выполнения, заданной матрицей (rij). Оптимальной последовательностью выполнения заданий является граф, состоящий из m параллельных цепочек и заданный матрицей Rопт. Если последовательность выполнения заданий определить любой другой матрицей R<Rопт, то оптимальная последовательность выполнения заданий будет задана матрицей R.

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

Рассмотрим пример, иллюстрирующий методы оптимизации инвестиционной фазы проекта при интервальном задании продолжительности этапов.

Пусть существует проект, последовательность этапов которого задана следующим ориентированным графом:
G (m, n) = G (0,5) – это означает, что все этапы независимы, отсутствуют транзитивные дуги графа.
ai = 1 – количество исполнителей, необходимое для проведения i-го этапа.
b = 2 – количество исполнителей.

Длительности выполнения этапов с первого по пятый заданы интервально следующим образом:

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

Порядок выполнения этапов исполнителями приведен на рис. 1 и выглядит следующим образом:

Рис.1. Порядок выполнения этапов исполнителями

Сформируем базовое решение и систему неравенств, при которых оно будет допустимо. Базовое решение (план) обладает следующим свойством:

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

Все множество базовых решений обладает следующими свойствами:

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

Шаг 1. Из подмножества этапов M1, выполнение которых начинается в момент времени t=0, выбрать то множество этапов, которое претендует на оптимальное, , где f1 – кратчайший этап из множества .

Шаг 2. :

Шаг 3. Из M1 исключаем все те этапы, для которых

Произведем сравнение продолжительностей выполнения первого и второго этапов:

Оба этапа могут быть кратчайшими. Назначим кратчайшим первый этап (t1).

Пусть t1t2. Тогда система (1) примет следующий вид:


0t23.
Проведем сравнение с продолжительностью третьего этапа.
3t38.

Аналогично проведем сравнение продолжительностей  и (t5) этапов.

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

Общая продолжительность выполнения данного плана T есть

Множество длительностей этапов, на котором данный план допустим, задается системой неравенств (7).

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

ЛИТЕРАТУРА

Отдельные номера журналов Вы можете купить на сайте www.5B.ru
Оформление подписки на журнал: http://dis.ru/e-store/subscription/