Модель и алгоритм формирования оптимального логистического плана выполнения комплекса взаимосвязанных работ

Полный текст

Введение Широко распространенный в практике управления экономическими системами класс задач составляют задачи минимизации времени выполнения комплекса взаимосвязанных работ при ограничениях на количество исполнителей, их взаимозаменяемости и стоимости привлечения к выполнению тех или иных работ. В частности, к этому классу относятся задачи организации переоснащения производственных объектов (Кежаев В.А., 2004), разработки и реализации инновационных проектов (Чечеватов А.В., 2006; Босов Д.Б., 2009; Тебекин А.В., 2017; Новиков В.Е., 2016), планирования научной работы в научно-исследовательских организациях и многие др. В задачах этого класса материальные логистические процессы переплетаются с процессами их финансового обеспечения, то есть с финансовой логистикой. Сложность подобных задач и существенные финансовые издержки, обусловленные просчетами в организации логистических процессов, приводят к тому, что их решение должно опираться не только на опыт и интуицию, но и на объективные научные обоснования. Инструментом для таких обоснований могут быть соответствующие математические модели. Построение модели При построении этих моделей состав и взаимосвязь работ, составляющих материальный логистический процесс, целесообразно отображать в виде сети (Босов Д.Б., 2006) G = {(i, j)}, i, j = 0, 1, …, m, i < j, (1) где i, j - номера узлов сети; (m + 1) - количество узлов. Каждой работе в сети (1) ставится в соответствие дуга (i, j), соединяющая i-й и j-й узлы. Узел i = 0 соответствует событию начала выполнения комплекса работ, представленного сетью (1). Узлы i = 1, 2, …, m соответствуют событиям, состоящим в завершении всех работ, описываемых входящими в каждый из них дугами. Общее количество работ (дуг) равно N. Последовательность работ подчиняется логистическому правилу: работа, соответствующая выходящей из любого узла дуге, не может быть начата до завершения всех работ, соответствующих дугам, входящим в этот узел. Каждая работа (i, j) характеризуется необходимым количеством n(i, j) исполнителей и продолжительностью τ(i, j). Множество исполнителей, привлекаемых к выполнению комплекса работ, обозначим R = {1, 2, …, k, …, K} (k - условный порядковый номер (идентификатор) исполнителя; K - количество исполнителей). Взаимозаменяемость исполнителей в формализованном виде представим матрицей Δ = ||δk(i, j)||, k = 1, 2, …, K, (i, j) G, (2) ⎧1, если k-й исполнитель может привлекаться ⎪ где dk (i, j) = ⎨ к выполнению (i, j) работы, (3) ⎩ ⎪0 в противном случае. Стоимости привлечения исполнителей к выполнению работ представим в виде компонент вектора C = ||ck(i, j)||, k = 1, 2, …, K, (i, j) Î G, (4) где ck(i, j) - стоимость единицы времени привлечения k-го исполнителя к выполнению (i, j)-й работы. Логистический план выполнения комплекса работ определяется множеством Y = {XY(i, j), rY(i, j)|(i, j) Î G, rY(i, j) Ì R}, (5) где XY(i, j) - определяемый планом Y момент времени, соответствующий началу (i, j)-й работы; rY(i, j) - множество исполнителей, привлекаемых к выполнению (i, j)-й работы в соответствии с планом Y. Будем полагать, что прерывание каждой начатой работы (i, j) Î G не допускается и состав rY(i, j) выделенных исполнителей не изменяется. С учетом принятых обозначений, стоимость ΩY(i, j) выполнения работы (i, j) при реализации плана Y определяется соотношением ΩY(i, j) = k Î rY(i, j)ck(i, j)τ(i, j). (6) Обозначим через GL множество всех путей сети (1), связывающих ее начальную и конечную вершины. Время выполнения всего комплекса работ при реализации плана (5) будет равно максимальной продолжительности TL пути L Î GL из начальной вершины i = 0 сети (1) в конечную j = m. С учетом принятых обозначений задача формирования логистического плана (5), минимизирующего время выполнения комплекса работ (1) при ограничениях на количество, взаимозаменяемость и стоимость исполнителей в формализованном виде сводится к следующей задаче математического программирования: · определить логистический план * * Y * = {XY (i, j), rY (i, j)|(i, j) Î G, rY(i, j) Í R}; (7) · выполнения комплекса (1) работ, обеспечивающий соблюдение условия T * = T (Y * ) = min maxTL (Y ); (8) Y LÎGL · при ограничениях XY (i, j) ³ max{XY (l, i) + t(l, i)}, (i, j) ÎG; l, i (9) å (i, j )ÎrY (i, j ) å dk (i, j) = n(i, j); n(i, j) £ K ; (10) (11) (i, j )ÎFY (t ) K ådk (i, j) ³ n(i, j); k =1 (12) å (i, j )ÎG ÙY (i, j) £ Ù*, (13) где FY(t) - множество работ комплекса (1), выполняемых в каждый момент времени t при реализации логистического плана Y; Ω* - максимально допустимая стоимость выполнения комплекса (1) работ. В задаче (7)-(13) условие (8) формализует стремление минимизировать время выполнения комплекса работ. Ограничение (9) отражает логистическое правило, что работы, выходящие из любого узла сети (1), могут начинаться только после завершения всех работ, входящих в этот узел. Ограничение (10) формализует требование выделения на каждую работу установленного количества исполнителей. Ограничение (11) отражает естественное условие, состоящее в том, что количество исполнителей, одновременно привлекаемых к выполнению работ, не может превышать их общего количества. Ограничение (12) формализует требование, состоящее в том, что количество и взаимозаменяемость исполнителей должны обеспечивать возможность выполнения каждой работы комплекса (1). Ограничение (13) означает, что общая стоимость выполнения комплекса работ (1) не может превышать установленного допустимого уровня. Задача (7)-(13) относится к нелинейным задачам распределения дискретных неоднородных ресурсов на произвольной сети. Она является NP - сложной задачей дискретного программирования (Алексеев А.О., 1988; Анисимов В.Г., Анисимов Е.Г., 1997). Точные методы решения задач такого класса впервые предложены в работах (Анисимов В.Г., Анисимов Е.Г., 1992, 1997). Однако в моделях, рассмотренных в этих работах, учитывались только исполнители работ и их производительность. Вместе с тем, при формировании планов реализации реальных логистических процессов в экономических системах, наряду с возобновляемыми ресурсами (исполнителями), необходимо учитывать и имеющиеся не возобновляемые (например, финансовые) ресурсы. В задаче (7)-(13) такими ресурсами является стоимость ΩY(i, j) выполнения каждой работы (i, j) Î G при реализации плана Y. Ограниченность этих ресурсов формально отражает соотношение (13). Полученная в результате введения этого соотношения модель (7)-(13) служит дальнейшим обобщением рассмотренной в модели (Анисимов В.Г., Анисимов Е.Г., 1997). Точные алгоритмы решения задачи (7)-(13) в настоящее время отсутствуют. Вместе с тем потребности практики управления реализацией сложных проектов обусловливают необходимость их разработки. Построение одного из таких алгоритмов - цель настоящей работы. Для существования решения задачи (7)-(13) необходимо и достаточно, чтобы: а) состав и взаимозаменяемость исполнителей обеспечивали возможность выполнения всего комплекса работ (1); б) установленный уровень Ω* допустимой стоимости позволял выполнить комплекс работ (1). В формализованном виде выполнение первого (а) из этих требований заключается в выполнении ограничения (12). Оно означает, что из состава исполнителей работ можно подобрать специалистов, способных выполнить любую работу комплекса (1). В целях проверки выполнения второго (б) требования можно воспользоваться множеством R* = {r q(i, j)|(i, j) Î G, q = 1, 2, …} (14) всех возможных вариантов назначения ресурсов для соответствующих работ. С этим множеством связано множество Ω = {Ωq(i, j), q = 1, 2, …, (i, j) Î G} (15) стоимостей Ωq(i, j) выполнения соответствующих работ при соответствующих вариантах назначения ресурсов. Элементы множества (15) определяются соотношением Ùq (i, j) = t(i, j) å ck (i, j). (16) kÎrq (i, j ) С учетом формулы (16) второе из требований, обеспечивающих существование решения рассматриваемой задачи (7)-(13), в формализованном виде представляется соотношением å (i, j )ÎG min Ùq (i, j) £ Ù*, q = 1, 2, ... . q (17) Проверку выполнимости условий (12) и (17) целесообразно проводить еще до начала процедуры поиска решения задачи (7)-(13). Если они не выполняются, то решение задачи (7)-(13) не существует. Если же они выполняются, то процедура оптимизации логистического плана выполнения комплекса работ (1) может быть реализована. В основу этой процедуры (алгоритма формирования оптимального плана) поиска может быть положен подход, впервые предложенный в работе (Анисимов В.Г., Анисимов Е.Г., 1997). Он опирается на следующие построения: а) представление множества V = {S} допустимых по ограничениям фрагментов S логистического плана Y в виде дерева подмножеств (ветвление); б) вычисление для ветвей дерева (выделенных подмножеств) нижней границы целевой функции (8); в) поиск допустимых вариантов логистического плана; г) проверка установленных допустимых вариантов на оптимальность. Предложенная процедура позволяет определить логистический план (7) выполнения комплекса работ (1), удовлетворяющий условиям (9)-(12). Особенность рассматриваемого в настоящей работе алгоритма состоит в необходимости учета на каждом шаге ветвления и условия (13). Если оно нарушается, то дальнейшее продолжение рассматриваемой ветви дерева вариантов не представляется возможным и осуществляется переход к новой ветви. Как и в алгоритме (Анисимов В.Г., Анисимов Е.Г., 1997), ветвление в предлагаемом алгоритме осуществляется на основе дихотомической схемы. При ее реализации каждая вершина vS S-й ветви дерева вариантов представляет собой элемент логистического плана. Причем, если соответствующая этому элементу работа (i, j) начинается в момент времени xS(i, j) при rS(i, j)-м варианте назначения исполнителей, то полагаем: vS = {xS(i, j), rS(i, j)}. (18) Если же работа (i, j) не начинается в момент времени xS(i, j) при rS(i, j)-м варианте назначения исполнителей, то полагаем: vS = Ø. (19) Для каждой ветви S Î V величины xS(i, j), (i, j) Î G, (моменты начала работ) должны выбираться из соответствующей этой ветви возрастающей последовательности S tS = {t n}, n = 1, 2, … . 1 n При этом tS = 0, а последующие моменты tS , n = 2, 3, …, определяются на основе соотношения S t n = min S (i, j )ÎF (t n-1 ) {xS (i, j) + t(i, j)}, (20) n-1 где FS(tS ) - множество работ (i, j), ранее включенных в S-ю ветвь и незавершенных к n-1 моменту времени tS , т.е. n-1 n-1 FS(tS ) = {(i, j)|(i, j) Î G, xS(i, j) £ tS £ xS(i, j) + τ(i, j)}. (21) Таким образом, tS представляет собой последовательность моментов времени, в которые завершаются работы, включенные в очередную ветвь дерева и высвобождаются соответствующие исполнители. S Условие t 1 = 0 отражает тот факт, что все варианты логистического плана начинаются в момент времени t = 0. Докажем, что назначение сроков начала работ не в соответствии с последовательностями tS не позволяет сократить общее время выполнения рассматриваемого комплекса работ (1). Действительно, для любого плана Y, содержащего фрагмент S, ранний срок начала любой работы (i, j) Î S по определению принадлежит последовательности tS. Следовательно, и поздние сроки начала работ, лежащих на критических для плана Y путях, также принадлежат этой последовательности. Для работ, не принадлежащих критическим путям, возможна вариация сроков начала в пределах соответствующих резервов времени. Вместе с тем, границы этих резервов также принадлежат этой последовательности, а вариация внутри границ не изменяет время выполнения комплекса работ в целом. Следовательно, сроки начала и завершения работ оптимального по критерию (8) логистического плана (7) должны принадлежать соответствующей этому плану последовательности tS. В интересах реализации принятой дихотомической схемы ветвления введем в рассмотрение связанное с уравнением (14) множество D = {dq|q = 1, 2, …}, (22) в котором dq = 1, если для выполнения (i, j)-й работы используется вариант r q(i, j) назначения ресурсов, или dq = 0 в противном случае. В этом случае порядковый номер q элемента dq = 1 множества D характеризует и выполняемую работу, и вариант назначения ресурсов, и стоимость привлеченных к ее выполнению ресурсов. С учетом множества (22) процесс ветвления в интересах составления оптимального логистического плана (7) заключается в выборе для каждого очередно- S q S q го момента времени t n допустимых переменных d Î D и установлении их значений, т.е. имеет место соотношение (18) (vS = {t n, d = 1}), если соответствующая S переменной dq работа (i, j) Î G начинается в момент времени xS = t n при r n q(i, j)-м S S q S q варианте назначения ресурсов или - (19) (vS = {tS , dq = 0}), если указанная работа при рассматриваемом варианте назначения ресурсов в момент t n не начинается. Множество Pn переменных d Î D, которые могут быть включены в S-й фрагмент логистического плана (7) в момент времени t n, содержит величины d Î D, соответствующие ранее не включенным в рассматриваемую ветвь S работам (i, j) Î G, удовлетворяющие условиям: S x(l, i) + τ(l, i) £ t n, (l, i) Î G; (23) S r q(i, j) Í Rn; (24) Ù* - å S mÎDS (t n-1 ) dmÙm + Ùq ³ 0, q = 1, 2, ..., (25) n n где RS - множество свободных ресурсов для S-го фрагмента плана в момент времени tS ; n-1 DS(tS ) - множество переменных dq включенных в ветвь S дерева вариантов к моменту n-1 времени tS . n Условие (23) выделяет работы, для которых к моменту tS выполнены все предшествующие. Условие (24) выделяет работы, для которых имеются допустимые наряды свободных исполнителей, а (25) - допустимые по стоимости наряды свободных исполнителей. S В качестве оценки WS нижней границы целевой функции (8) для каждого фрагмента S календарного плана может быть принята максимальная продолжительность пути из начальной вершины графа G в конечную, определяемая без учета ресурсных ограничений (11), (13) для работ, не включенных в S. При этом, если на очередном, соответствующем моменту t n, шаге ветвления устанавливается dq = 1, то для определения WS(dq = 1) полагается следующее: а) работы (l, i) Î G, ранее вошедшие в S-й фрагмент плана (т.е. работы, для S S которых xS(l, i) < t n, начинаются в соответствующие моменты x (l, i) и завершаются в моменты xS(l, i) + τ(l, i); S S S S б) для работы (i, j) Î G, соответствующей переменной dq = Pn и, следовательно, включаемой на рассматриваемом шаге в S-ю ветвь дерева вариантов xS(i, j) = t n; в) для работ (e, h) Î G, соответствующих переменным du Î Pn, u ¹ q, которые по ресурсному ограничению (2, 9) в момент t n не могут быть включены в план n+1 одновременно с (i, j), время начала равно tS n+1 , а длительность определяется соотношением tS + τ(e, h). Если же на рассматриваемом шаге ветвления устанавливается dq = 0, то для определения WS(dq = 0) дополнительно полагается следующее: а) работы (l, i) Î G, ранее вошедшие в S-й фрагмент логистического плана (т.е. S S работы, для которых xS(l, i) < t n), начинаются в соответствующие моменты x (l, i) и завершаются в моменты xS(l, i) + τ(l, i); S б) работа (i, j), соответствующая переменной dq Î Pn, начинается в момент S времени t n+1 S и завершается в момент t n+1 + τ(l, i); n в) остальные работы (e, h) Î G, соответствующие переменным du Î PS , u ¹ q, n n начинаются в момент tS и завершаются в моменты tS + τ(e, h). Важным элементом рассматриваемого алгоритма решения задачи (7)-(13), существенно влияющим на его сходимость, является способ выбора очередной работы и варианта назначения для нее ресурсов. Формально он состоит в выборе n n переменных dq Î PS для включения в S-ю ветвь в момент времени tS. В предлагаемом алгоритме выбор dq на очередном шаге ветвления осуществляется в два этапа: на первом выбирается работа, а на втором - вариант назначения ресурсов. Очередная работа выбирается в соответствии с такой последовательностью предпочтений: j min T (n) → max τ(i, j) → min i → min j, т.е. первой в план включается работа, которой соответствует меньший поздний (n) срок окончания T j . Если таких работ несколько, то из них выбирается работа максимального объема. Если и таких работ несколько - то работа с наименьшими номерами i, j. При этом поздние сроки окончания должны определяться с учетом рассматриваемого фрагмента S логистического плана. Вариант r(i, j) назначения исполнителей для выбранной работы (i, j) определяется из условия минимума величины å å kÎr(i, j )(l, h)ÏS dk (l, h), т.е. назначаются наименее универсальные для оставшихся работ (l, h) Î S исполнители. S S Выбранная таким образом работа (i, j) и вариант r(i, j) назначения исполнителей однозначно определяют очередную переменную dq Î Pn, включаемую в S-ю ветвь дерева вариантов плана в момент t n. Обход дерева организуется в соответствии с правилом «иди вправо». Это позволяет хранить в памяти ЭВМ при решении задачи только текущий фрагмент логистического плана, наименьшее из полученных ранее значений целевой функции и соответствующий ему допустимый вариант плана. Указанное правило в сочетании с рассмотренным способом выбора работ и исполнителей составляет приближенный алгоритм решения задачи (7)-(13), позволяющий получить первое допустимое решение за конечное число шагов, равное количеству N работ в сети (1). Каждая S-я ветвь заканчивается, если в нее вошли все N работ, т.е. получен допустимый логистический план Y, или если WS ³ T0(1 - μ), 0 £ μ £ 1, (26) где T0 - наименьшее значение целевой функции для ранее полученных допустимых логистических планов (рекорд); μ - заданное допустимое отклонение целевой функции от оптимального (точность оптимизации). Выполнение условия (26) означает, что на рассматриваемой ветви улучшить ранее полученный рекорд более чем на 100μ% нельзя и ее продолжение в рамках заданной точности оптимизации не имеет смысла. Заключение Процедура поиска решения заканчивается, если для всех оставшихся ветвей выполняется условие (26). При установленном способе обхода дерева вариантов такой ситуации соответствует второй возврат в корневую вершину. При этом последний рекорд есть искомое значение целевой функции (8), а соответствующий ему допустимый план выполнения комплекса работ - оптимальный логистический план Y*. Использование рассмотренного алгоритма обеспечивает анализ всех возможных вариантов плана и исключает повторы при их просмотре. В целом предложенный алгоритм обеспечивает получение как точного, так и приближенных решений задачи формирования оптимального логистического плана выполнения комплекса взаимосвязанных работ.

Об авторах

Владимир Георгиевич Анисимов

Санкт-Петербургский политехнический университет Петра Великого

Автор, ответственный за переписку.
Email: an-33@yandex.ru

доктор технических наук, профессор кафедры информационных систем в экономике и менеджменте

ул. Политехническая, 29, Санкт-Петербург, Россия, 195251

Мурат Романович Гапов

Министерство экономического развития Карачаево-Черкесской республики

Email: mgapov@gmail.com

кандидат экономических наук, заместитель министра экономического развития

ул. Комсомольская 23, Черкесск, Россия, 369000

Евгения Сергеевна Родионова

Санкт-Петербургский им. В. Б. Бобкова филиал Российской таможенной академии

Email: wart1983@mail.ru

кандидат экономических наук, доцент кафедры международных экономических отношений экономического факультета

Софийская ул., 52A, Санкт-Петербург, Россия, 192236

Список литературы