Разреженное производное множество — пример 2

Модель сетевого планирования по методу PERT/CPM, приведенная ниже (файл PRT.LNG в поддиректории “Samples”) использует для определения разреженного множества PRED метод явного списка. PRED является множеством, устанавливающим порядок следования поставок в плане строительных работ.

MODEL:

1 ]! Модель PERT/CPM;

2]!

3]! Диаграмма, устанавливающая порядок следования:

4]! /FCAST\———SCHED————COSTOUT\

5]! / \ \

6]! FIRST \ \

7]! \ \ \

8]! \SURVEY—PRICE——————————————FINAL;

9]

10] SETS:

21]! Для каждого этапа работ имеем: Time (время), Early Start (ранний срок начала работы) (ES),

22] Поздний срок начала работы (LS), and Slack (время простоя);

23] TASK/ FIRST, FCAST, SURVEY, PRICE,

24] SCHED, COSTOUT, FINAL/: TIME, ES, LS, SLACK;

25]

26]! Далее приведены связи, устанавливающие порядок следования работ, первый этап работ в этих связях the

27] должна быть завершена до того, как начнет выполняться второй этап;

28]

29] PRED(TASK, TASK)/ FIRST,FCAST, FIRST,SURVEY,

30] FCAST,PRICE, FCAST,SCHED, SURVEY,PRICE,

31] SCHED,COSTOUT, PRICE,FINAL, COSTOUT,FINAL/;

32] ENDSETS

33]

34] DATA:! здесь приведены времена выполнения каждого этапа;

35] TIME = 0, 14, 3, 3, 7, 4, 10;

36] ENDDATA

37]

38]! Для первого этапа ранний срок начала = 0;

39] ES(1) = 0;

40]

41]! вычислим ранних сроков для всех этапов, кроме первого;

42] @FOR(TASK(J)| J #GT# 1:

43] ES(J) = @MAX(PRED(I, J): ES(I) + TIME(I)););

44]

45]! Для последнего этапа ранний срок начала = позднему сроку начала;

46] LTASK = @SIZE(TASK);

47] LS(LTASK) = ES(LTASK); SLACK(LTASK) = 0;

48]

49]! Вычислим поздние сроки начала работ для всех этапов, кроме последнего;

50] @FOR(TASK(I)| I #LT# LTASK:

51] LS(I) = @MIN(PRED(I, J): LS(J) - TIME(I));

52] SLACK(I) = LS(I) - ES(I););

END

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

TIME Время выполнения задачи на этапе

ES ранний возможный срок начала выполнения этапа

LS самый поздний возможный срок выполнения этапа

SLACK Разность между LS и ES (известная как время простоя) для этапа

Строки с 29 по 31 определяют разреженное множество PRED, явно перечисляя порядок следования различных этапов. Порядок следования устанавливается для двух этапов, один из них должен предшествовать другому. Например, работы по закладке фундамента должны предшествовать кровельным работам. Отметим, что только перечислено только восемь пар из 49 возможных — таким образом, используя разреженность, мы храним только 8 элементов множества вместо 49. Это приведет к уменьшению используемой памяти и ускорению решения. Для больших моделей возможная экономия может быть весьма ощутимой.

Строка 38 устанавливает ES (ранний срок начала работы) для первого этапа равным 0. Строка 46 использует функцию @SIZE для определения количества задач (этапов работ) в модели. Отметим, что @SIZE принимает имя множества в качестве аргумента и возвращает количество элементов в множестве.

Строки 42 по 43 и 50 по 52 вычисляют значения атрибутов LS, ES и SLACK. Мы не вдаемся в детали этих вычислений, чтобы не отвлекать вас от главной цели: возможности использования явных списков элементов в разреженных производных множествах и потенциальной возможности экономии памяти, предоставляемой этим методом.

Дата добавления: 2015-11-16