назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [ 100 ] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


100

Вычислить Тн

Вычислить Те

Определить li окончания очередного в данном варианте

Вычислить ГГСг,)

= /+1

Найдено оптимальное решение

-►(1Х0Д

В качестве оптимального

выбираем решение, которому соответствует последнее значение Те

Положить Те равной продолжительности полученного плана

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



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

Те-Тп

(11.21)

где Те- последнее значение верхней оценки; - значение нижней оценки; К- требуемая относительная точность решения в процентах.

11.2.2. Анализ устойчивости решений в задаче оптимизации времени реализации проекта. Мы

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

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

екта может принимать любое значение t из интервала

. Учиты-

вая, что рассмотренная выше задача планирования вьшолнения проекта является общей задачей теории расписаний, анализ влияния на оптимальный план (расписание) вьшолнения проекта изменения значений исходных параметров выполняется в рамках исследования устойчивости задачи. Далее этапы проекта, следуя терминологии [37], будем называть работами.

Учитывая сделанные замечания, рассмотрим задачу оптимального планирования вьшолнения проекта в следующей постановке.

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

соответствие множество работ = так, что в множество R входят 308



те и только те работы, которые должны быть выполнены прежде, чем может быть начато выполнение работы di.

Каждая работа характеризуется интервалом длительности выполнения [ f]. Длительность работы di может быть любым числом интервалаРесурсы, необходимые для выполнения работы di, задаются вектором Qi =(aii,...,ai), где ay - количество ресурсов у, необходимых для выполнения работы i, (i = \,,.., п; j = \,..., т). Общий объем ресурсов, который может привлекаться к выполнению работ, задается вектором bi = {bi,..„b).

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

Определение 11.1. Допустимым расписанием выполнения работ di,,,,,d назовем набор множеств работи набор интервалов

времени[г(,Г2], ... [rfrf] длиной Tj,...,?) соответственно такие, что в интервале времени [г{,Г2] выполняются работы только из множества (i = \,.,„k;k< п).

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

1.работа dl может начать выполняться только в том случае, если выполнены все работы Ri;

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

2.общий объем используемых ресурсов в каждый момент времени интервалов [г{,Г2] не должен превышать значения bj(j= l,...,w);

3.все работы <Д/= 1,...,«) должны непрерывно выполняться в течение времени , где ti - продолжительность работы d.

Задача составления оптимального расписания заключается в том, что-

бы для каждого вектора длительности работ teYl tptt (/-0) найти

расписание минимальной длины. Обозначим через Р «-мерный паралле-

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [ 100 ] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]