A mathematical model of a complex serving system with stochastic parameters and mutual dependency between the jobs.

Oleinikova Svetlana Aleksandrovna Doctor of Technical Science Associate Professor, Department of Automated and Computing Systems, Voronezh State Technical University 394026, Russia, g. Voronezh, Moskovskii prospekt, 14 s.a.oleynikova@gmail.com Other publications by this author

Введение

В настоящее время к большинству обслуживающих и производственных систем предъявляется целый ряд требований, от учета которых зависит эффективность управления производственным процессом. Необходимость обработки сразу нескольких заявок с индивидуальными вариантами обслуживания, включающими решение большого количества взаимозависимых задач со стохастическими параметрами, временные и ресурсные ограничения, наличие нескольких центров обслуживания обуславливают формирование и развитие соответствующих математических моделей, отражающих все вышеперечисленные особенности. Частично такие модели уже построены. В частности, взаимная зависимость работ широко исследована в теории управления проектами ^[1-4]. Среди множества классов задач в данной области особое место занимают задачи со случайной длительностью обслуживания. Существует метод PERT, который позволяет оценить данную характеристику. Анализу этого метода, а также развитию методов планирования в условиях стохастических характеристик отдельных работ посвящены научные труды Д.И. Голенко-Гинзбурга, А. Кофмана, Г. Дебазея и др. ^[3,4]. Существует множество программных средств, позволяющих автоматизировать существующие подходы для оптимизации сложных обслуживающих комплексов. В частности, в статьях ^[5-9] проанализирована специфика таких программных продуктов как MS Project, GanntProject, Spider Project, ProjectLibre и OpenProj.

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

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

1. Постановка задачи и ее особенности

Рассматривается задача оптимизации сложной системы, состоящей из нескольких центров, каждый из которых специализируется в некотором виде обслуживания ^{[9, 10]}. Каждый центр предназначен для выполнения работ определенного типа. Он обладает множеством ресурсов нескольких типов, необходимых для выполнения работ. Под ресурсами могут пониматься специалисты, выполняющие работу, оборудование, на котором она выполняется, и т.д. Специфика таких ресурсов заключается в том, что при выполнении некоторой работы их невозможно использовать для других работ, однако по завершении очередной работы они вновь могут быть доступны. Существует также другая категория ресурсов, используемых в системе. Особенность данной категории заключается в том, что они расходуются прямопропорционально с выполнением работы и после ее завершения не восполняются. К ресурсам такого типа относятся материалы, необходимые для работ, финансовые ресурсы и т.д.

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

Рисунок 1 – Функционирование исследуемой обслуживающей системы

Здесь символами P1,…, Pn обозначены поступающие заявки; S1,…, SL – центры обслуживания. Верхняя часть рисунка показывает множество маршрутов по обслуживанию заявок; нижняя представляет собой граф, иллюстрирующий взаимную зависимость работ (ребра), которые необходимо выполнить для данной заявки.

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

Таким образом, для исследуемой системы можно выдвинуть следующие допущения и предположения:

- продолжительности всех работ являются случайными величинами, имеющими бета-паспределение;

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

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

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

2. Математическая модель исследуемой системы и оптимизационная задача

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

Исходные параметры математической модели

Исследуемая система задается своими центрами обслуживания:

. (1)

Каждый центр j (j=1,…,L) обладает множеством ресурсов нескольких типов:

. (2)

Здесь kj – количество типов ресурсов в центре j, Rj1,…, Rjkj – объем ресурсов каждого типа.

Каждая заявка Pm, поступающая на вход модели, представляет собой множество взаимно-зависимых работ Wm со случайной длительностью обслуживания. Кроме работ, заявка еще задается директивным временем Tm, к которому необходимо завершить ее обслуживание:

. (3)

Любая работа wiÎWm задается следующим набором характеристик:

. (4)

Здесь Si – центр, в котором выполняется работа i; dliti – ориентировочное время обслуживания; Ri=(Ri1,…, Riki) – объемы ресурсов, необходимые для выполнения; Pri – множество работ, непосредственно предшествующих выполнению работы i, с помощью которого задается взаимная зависимость работ. Для задания данного множества используются две дополнительные характеристики работы: время ее раннего начала и раннего окончания. Они определяются заранее без учета ресурсов. Тогда

. (5)

Оцениваемые параметры модели

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

Анализ существующих законов распределения, удовлетворяющих вышеперечисленным свойствам, показал, что наиболее целесообразно длительность обслуживания описать с помощью случайной величины, распределенной по закону бета. Плотность этого закона распределения имеет вид ^[10]:

(6)

Здесь p и q – параметры закона, а a и b – границы, в пределах которых плотность распределения будет ненулевой (можно также считать параметрами распределения), B(p,q) – бета функция от параметров p и q.

В общем случае она определяется формулой ^[10]:

(7)

В формуле (7) Г(х) – это гамма-функция аргумента х.

Тогда оценкой длительности обслуживания будет являться математическое ожидание случайной величины, распределенной по закону бета с неизвестными параметрами p и q и известными параметрами a и b.

. (8)

Варьируемые параметры модели

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

Целевая функция

Опишем соответствующую оптимизационную задачу. В качестве критерия оптимизации рассмотрим обобщенный ресурсный критерий. Введем в рассмотрение также функцию fj (t)=(fj1(t),…, f j kj(t)), определяющую наиболее целесообразный объем ресурсов, используемых в момент времени t в центре j. Занятость системы обслуживанием заявок, поступивших ранее, в центре j описывается вектором:

. (9)

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

. (10)

Здесь символами wj.ri обозначено множество ресурсов типа i, требующихся для выполнения работы j. Каждое отдельное выражение описывает определенный центр обслуживания. Суммирование ведется по времени и по всем имеющимся в данном центре ресурсам.

Такая целевая функция выбрана по следующим причинам. Во-первых, для целого ряда задач необходимо обслужить заявку к заданному сроку. При этом, ее выполнение в минимально возможные сроки (в пределах заданных ограничений) не только не является наилучшим вариантом планирования, но и не всегда целесообразно. Во-вторых, такая загрузка системы позволяет увеличить резерв ее производительности в целом. Следует также допустить появление новых внеплановых заявок, требующих скорейшего обслуживания в сжатые сроки. При формировании расписания для заявок, поступивших ранее, с точки зрения скорейшего завершения, система в данный момент может не располагать достаточным резервом свободных ресурсов, который позволит обеспечить своевременное выполнение новой заявки. В связи с этим, может потребоваться перераспределение работ, которым уже назначено плановое время начала, на более поздние сроки, т.е. внесение изменение в существующее расписание. При наличии взаимной зависимости между работами, а также временных и ресурсных ограничений, данная задача может потребовать существенных временных и алгоритмических затрат. Кроме того, варьирование функциями fj может обеспечить решение исходной задачи в различных условиях. Если эта функция будет совпадать с функцией (9), то это обеспечит возможность максимальной загрузки системы. Если функция будет меньше (9), но не будет изменяться во времени, то получится критерий равномерной загрузки. Критерий (10) отражает необходимость в каждый момент времени планировать расписание таким образом, чтобы при этом объем задействованных ресурсов каждого типа был близок к эталонному значению.

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

Ограничения

Рассмотрим дополнительные ограничения, которые возникнут в процессе планирования. В первую очередь, это ограничения на объем используемых ресурсов. Данные ограничения подразумевают, что формировать множество работ Wt, которым будет назначено время начала t, можно лишь таким образом, чтобы суммарный объем ресурсов этих работ (по каждому типу отдельно) совместно с еще незавершенными работами, время выполнения которым назначили раньше, не превосходил общего объема ресурсов данного типа Rji:

. (11)

Введем в рассмотрение множество Wнезав t незавершенных работ к моменту t:

. (12)

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

. (13)

Будем считать, что после завершения планирования на данном этапе множество Rисп j будет модифицироваться за счет работ из множества Wt, которым назначено время начала t:

. (14)

Ресурсные ограничения подразумевают, что в каждый момент времени t в каждом центре j количество используемых ресурсов каждого типа i, 1,…,m, Rj(t) не превышало объем имеющихся ресурсов Rj:

(15)

Кроме того следует учесть ограничение на взаимную зависимость работ:

. (16)

Одним из важнейших ограничений, определяющих специфику задачи, является ограничение на время завершения обслуживания. Как следует из формулы (3), для каждой заявки Pi задан директивный срок ее окончания Ti. Решение оптимизационной задачи предполагает нахождение времени начала t нач_ij каждой работы j каждого проекта i. В этом случае, время начала должно быть таково, чтобы для каждой заявки выполнялось условие:

(17)

Здесь Tфакт_i – фактическое время завершения обслуживания заявки i с учетом составленного расписания; Ti – директивный срок завершения ее обслуживания.

Фактическое время завершения обслуживания заявки – это момент, в который будет закончена самая последняя ее работа. С точки зрения задач управления проектами это критическое время проекта ^[1-4]. Его можно определить по формуле:

. (18)

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

. (19)

Здесь Pi – вероятность, с которой проект i должен завершиться к моменту Ti. С учетом аппарата теории вероятностей неравенство (19) можно переписать в виде:

, (20)

где - функция распределения случайной величиныTфакт_i, описывающей длительность завершения проекта i.

Формулы (1)-(20) и составляют основу математической модели многостадийной системы, учитывающую случайную длительность обслуживания и ограничения на взаимную зависимость работ, а также временные и ресурсные ограничения, и позволяющую оптимизировать процесс ее функционирования с точки зрения обобщенного ресурсного критерия. Принципиальным отличием разработанной модели от существующих аналогов является использование критериальной функции (10), а также учет остальных особенностей задачи в данных условиях. Разработанная модель может быть применена для описания функционирования любых многостадийных производственных и обслуживающих комплексов, отличительной особенностью которых является стохастический характер длительности обслуживания, взаимная зависимость работ по обслуживанию заявки, а также необходимость эффективного распределения ресурсов во времени.

Приведем примеры систем, для описания которых будет целесообразным использование данной модели ^{[11, 12]}. С ее помощью можно описать и исследовать функционирование распределенных вычислительных систем (кластеров, многопроцессорных систем, систем общего доступа). Все устройства могут работать на максимальную мощность, но целесообразно ввести некоторый ресурсный резерв и обеспечить равномерную загрузку. К другой категории можно отнести различные ремонтные мастерские, когда к какому-либо оборудованию предъявляются аналогичные требования. Еще одним видом исследуемых систем могут являться медицинские учреждения, основной задачей которых является незамедлительное реагирование в случае чрезвычайных ситуаций. Как следствие, для них целесообразно при планировании оставить некоторый запас, чтобы иметь возможность такого реагирования.

Соответствующая оптимизационная задача, целью которой является формирование наиболее предпочтительного графика обслуживания заявки, определяется многокритериальной функцией (10), а также ресурсными ограничениями (11) и (15), ограничениями на взаимную зависимость работ (16) и временными ограничениями (17) или (19).

3. Оценка длительности обслуживания как одного из параметров модели

Одним из важнейших параметров математической модели (1)-(20) является длительность обслуживания. Нахождение оценки соответствующей характеристики, отличающейся повышенной точностью, является важнейшей задачей, поскольку это напрямую влияет на качество составленного расписания. Как правило, для решения данной задачи используют следующие данные:

- наименьшее время обслуживания a;

- наибольшее время обслуживания b;

- наиболее вероятное время обслуживании (мода) m.

Самым подходящим законом для описания соответствующей случайной величины является закон бета. На сегодняшний день одним из наиболее распространенных подходов для оценки математического ожидания этой величины является метод PERT (Program Evaluation and Review Technique). Его расчетные формулы следующие ^[1-4]:

(21)

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

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

(22)

где

, (23)

а

(24)

Доказательство основывается на следующей вспомогательной лемме.

Лемма. Пусть x - случайная величина, распределенная по закону бета в интервале ^[0,1], с известной модой m и дисперсией Dx. Тогда ее математическое ожидание будет определяться следующим образом:

, (25)

где

, (26)

а

. (27)

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

. (28)

На основании (28) было составлено кубическое уравнение для математического ожидания бета-распределения:

(29)

Представим его в каноническом виде:

. (30)

При этом q r будут определяться по формулам (26) и (27) соответственно. Воспользовавшись формулой Кардано, несложно найти корни данного уравнения:

(31)

где

. (32)

Добавив к полученным корням значение -(1+m)/3, получим корни исходного уравнения (29). В ^[13] было доказано, что уравнение (30) будет иметь три вещественных корня, а также показано, что математическому ожиданию соответствует корень y3.

Таким образом, лемма доказана.

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

Для обоснования эффективности полученной оценки был проведен вычислительный эксперимент, целью которого являлось сравнение сгенерированной бета-величины с оценкой метода PERT и оценкой, предложенной в формуле (22). В результате было получено, что средняя погрешность при оценивании бета-величины математическим ожиданием равно 0,004484, методом PERT – 0,02538.

Выводы

Детальный анализ функционирования сложной многостадийной системы со стохастическими параметрами позволил построить математическую модель, адекватно описывающую специфику ее функционирования. В частности, определены формулы, описывающие длительность системы, взаимную зависимость между отдельными работами, а также целевую функцию и ограничения. Новизна заключается в использовании специфической критериальной функции (10) совместно с ограничениями (11), (15) и (17), а также учета остальных особенностей задачи в данных условиях.

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

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