<<
>>

1.2. Построение модели операции

Для решения задач календарного планирования необходимо, в первую очередь, получить описание всех операций, то есть определить объем каждой операции и зависимость f(u) скорости операции от количества ресурсов.
Дело в том, что на практике, как правило, известны продолжительности операций при различных количествах ресурса на ней, то есть зависимости t(v). Если операции выполняются с фиксированным уровнем ресурсов (v принимает только одно значение) или с постоянным уровнем ресурсов (количество ресурсов в процессе выполнения операции не меняется), то проблем не возникает. Действительно, в этом случае

( ) W f ( ) W

t(v ) = ТМ или f (v ^"М, f (v) t(v)

и скорость операции определяется с точностью до параметра W (при известной зависимости t(v) объем W может выбираться произвольно). Ситуация становится сложнее, если операция выполняется с переменным уровнем ресурсов.

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

продолжительность i-ой части при j-ом уровне ресурса, i = 1, 2; j = 1, 2;

T1 = т11 + т21 T2 = т12 + т22

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

т11 =2, т21 =3, т12 =1, т22 =2, T1=5, T2=3.

Примем объем операции W = 15. Тогда при T1 = 5 средняя скорость операции w1 = 3, а при Т2 = 3 - w2 = 5. Пусть операция выполняется сначала при первом уровне ресурсов в течение 2 дней, а затем при втором уровне ресурсов. Тогда очевидно, что операция будет закончена за 4 дня, так как t11 + t22 = 4. Определим, однако, момент завершения операции на основе средних скоростей w1 и w2;. За два дня будет выполнено при скорости w1 = 3 х(2) = 6 ед. объема операции. Оставшиеся 15 - 6 = 9 ед. объема при скорости w2 = 5 будут выполнены за 9/5 = 1,8 дня. В целом операция будет завершена за 3,8 дня, что меньше истинного срока t = 4.

Если выполнять операцию сначала при втором уровне ресурса (w2 = 5) в течение одного дня, а затем при первом (w1 = 3), то операция, как легко проверить, завершится за 41/3 дня, что больше 4. Ошибки в определении времени завершения операции объясняются тем, что скорость завершения операции является средней величиной. Для уменьшения ошибки следует соответствующим образом выбрать объемы частей операции. Так, если взять объем первой части x1 = 7,5, и объем второй части x2 = 7,5, то ошибки не возникнет. Действительно, при выполнении первой части со скоростью wi = 3, она будет завершена за 7'5/3 = 2,5 дня. Вторая часть при скорости w2 = 5 будет завершена за 7,5/5 = 1,5 дня, что в сумме даст 4 дня.

Рассмотренный пример показывает, насколько важно выбрать объемы частей операции при ее выполнении с переменной интенсивностью.

Рассмотрим задачу выбора объемов частей операции в общем случае. Пусть операция состоит из n частей, каждая из которых может выполняться при m различных уровнях ресурсов. Обозначим xij - продолжительность i-ой части при j-ом уровне ресурсов, уi - объем i-ой части операции, Qj - продолжительность операции при j-м уровне ресурсов. Обозначим далее xij = 1, если i-ая операция выполняется j-м уровнем ресурсов, xij = 0 в другом случае. Тогда продолжительность операции определяется на основе ее описания (то есть на основе объемов частей {у^ и продолжительностей {Qj}) и будет равна

Q = Х YiQjXi, (1.2.1)

i,j

а истинная продолжительность

т = Х Xijtij. (1.2.2)

У

Относительная ошибка описания операции составит

5 =

1 - Q

(1.2.3)

T

Поставим задачу определить объемы частей {уi} и продолжительности {Qj} так, чтобы ошибка 5 была минимальной. Очевидно, что если существуют числа {у^ такие, что tij = уТ где Tj = ^tiJ , то ошибка 5 = 0. Запишем условие (1.2.3) в виде

-5 < 1 - Q <5 T

(12.4)

(1 -5)Т < Q <(1 + 5)Т. Условия (1.2.4) можно представить в виде двух неравенств: ]Tmin((1 + 5)тц- YiQj )> 0,

]Tmin(yiQj-(1 -5)ТЙ)> 0.

Наконец, введя новые переменные:

Ui = min((1 + 5)tij - yiQj), Vi = min(yiQJ -(1 -d)tij),

приведем задачу к следующему виду:

5 ® min,

Xui > 0, (1.2.5)

^ >0,

Ui =(1 + 5)tij - yiQj, i = 1,n, j = 1,m,

vi = y Qj-(1 -5)tij i = ^nJ =1,m. (1 2 5)

Это задача нелинейного программирования. Если зафиксировать {уш} или {Qj}, то она становится задачей линейного программирования. Поэтому задачу (1.2.5) можно решать как последовательность задач линейного программирования, фиксируя сначала значения {Qj}

(например, взяв Qj = ^xij, j = 1,m), а затем {У1} и т.д.

Заметим, что в ряде случаев величины {Qj} выбираются из других соображений. Так, например, мы хотим получить описание операции с линейной зависимостью скорости операции от количества ресурсов, то есть f(w) = u = W/Q. В этом случае Q = ^ , где uj -

количество ресурсов, соответствующее j-му уровню. Если принять W = 1, то Qj = ^ становится известным и задача (1.2.5) является

задачей линейного программирования.

Рассмотрим приближенный метод построения описания операции. В его основе лежит идея приближенного представления чисел tj в виде yiQj. Относительная ошибка такого представления составит

yiQj

(1.2.6)

1-

tj

5 = max

i,j

Представим (1.2.6) в виде

T • T •

(1 -5i)max^L j Qj j Qj

или

Tij • Tj

max^L - min- J

5 = j Qj j Qj (1.2.8)

i Tj , • Tij j Qj j Qj

5 = max 5i.

i

Легко показать, что задача минимизации 5 сводится к задаче

минимизации e = max ei, где

i

max Tijwj 1

(1.2.9)

ei =—j , wj = —

min Tijwj Qj

Условие (1.2.9) легко сводится к виду

wj 1 T 1

>-max^- = -qkj. (1.2.10)

wk e i Tj e Обозначим In wj = 1j, In e = h, In qkj = 1kj. Тогда система (1.2.10) сведется к виду

1j - 1k > 1kj - h , j, k = 1,m . (1.2.11)

Необходимо определить минимальную h > 0, при которой система (1.2.11) имеет решение.

Определим полный граф с m вершинами и длинами дуг (1kj- h). Как известно, система (1.2.11) имеет решение, если в графе отсутствуют контуры положительной длины.

<< | >>
Источник: Баркалов С.А., Бурков В.Н., Гилязов Н.М.. Методы агрегирования в управлении проектами. М.: ИПУ РАН, 1999- 55 с.. 1999

Еще по теме 1.2. Построение модели операции:

  1. 2. ОСНОВНЫЕ ВИДЫ МОДЕЛЕЙ, ИСПОЛЬЗУЕМЫХ В КРИМИНАЛИСТИКЕ
  2. N 1. Понятие, особенности, виды криминалистической модели и криминалистического моделирования
  3. Модели финансирования социального страхования
  4. Виды моделей
  5. 2.3.1. Модель деятельности управляющего информационным центром
  6. Практическое исследование современного состояния ИБ в органах власти предполагает проведение работ в областях определения, классификации и формализованного описания источников угроз СЗИ сайтов органов власти, определения методики построения модели угроз СЗИ сайтов органов власти, построения модели угроз СЗИ органов власти.
  7. 3.4. Методика построения модели угроз системам защиты информации сайтов органов власти Российской Федерации
  8. 1.2 Методы основанные на построении модели лица.
  9. Методологические подходы К построению модели «институционального человека»
  10. 6.1.4. Пошаговая процедура построения модели
  11. 6.1.8. Пример построения модели
  12. ГЛАВА 1. Методы построения агрегированных операций
  13. 1.2. Построение модели операции
  14. 6.2. Подходы к построению модели мониторинга государственных и муниципальных услуг
  15. ПОДХОДЫ К ФОРМИРОВАНИЮ РЕГИОНАЛЬНЫХ МОДЕЛЕЙ ПРЕДПРИНИМАТЕЛЬСТВА
  16. 5.3. Этапы построения многофакторной корреляционно-регрессионной модели