Оптимизация сетевого графика

Построение календарного графика

На основе полученных расчетов строится календарный график. По ОХ – время, по ОУ – работы.

Критический путь изображается сплошной горизонтальной линией.

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

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

Некритические работы расположены в порядке возрастания первого индекса или второго.

Каждой некритической работе соответствует отрезок от раннего начала до позднего окончания.

Некритические работы изображаются пунктирной линией.

Над каждым отрезком ставится продолжительность работы.

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

1) Если величина полного резерва работы = величине свободного резерва этой работы, то увеличение продолжительности работы на величину полного резерва не повлияет на результаты всех последующих работ

2) Если свободный резерв работы ij меньше полного резерва, то для того чтобы не повлиять на резервы последующих работ, продолжительность работы ij можно увеличить на величину не превосходящую свободного резерва.

Задача № 1

Минимизация трудовых ресурсов при заданном времени выполнения комплекса работ.

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

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

Задача № 2

Задача минимизации времени выполнения комплекса работ при ограниченных трудовых ресурсов.

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

Задача № 3

Предположим, что время выполнения комплекса работа t_крит превосходит заданное время T.

Какие дополнительные средства в работы необходимо вложить так, чтобы время выполнения комплекса работ не превышало заданного T, а сумма вложенных средств была минимальна?

Мат.модель:

a₁…a_n – работы

t₁…t_n – продолжительность

x_i – кол-во дополнительных средств вложенных в работы a_i.

Предположим, что вложение средств x_i в работы a_i уменьшит ее продолжительность до t’_i = φ (x_i), тогда в качестве целевой функции f(x), мы возьмем

f(x_i) =

φ_i (x_i) =

t_крит > T, но нет возможности вложить дополнительные средства для уменьшения t_крит.

Поэтому необходимо уменьшить t_крит за счет перераспределения ресурсов между не критическими и критическими работами.

Задача № 4 (продолжение 3)

Возникает зачада «какое количество средств и с каких работ перераспределить так, чтобы t_крит стало минимальным?»

Мат. Модель:

Предположим, что вложим дополнительных средств x_i в работы a_i до φ_{i ,} а заберем x_i средства из работ a_i.

Предположим, что изначально в каждый a_i было вложено b_i средств.

Обозначим через x_i – количество вложенных средств в работы a_i

x_i ≥ - b_i

f(x_i) =

Задача № 5

Предположим, что t_крит ≤ T, тогда за счет высвобождения некоторых средств и увеличения продолжительности работ можно увеличить t_крит и получить при этом некоторую прибыль.

Возникает задача «до каких пределов можно увеличить время выполнения работы и каких работ так, чтобы полученная при этом экономия средств была максимальна?».

Предположим, что увеличение продолжительности работ a_i на τ_i дает экономию средств x_i =

f(x) =

τ_i ≥ 0

Дата добавления: 2015-04-23