66. Оптимизация проекта по стоимости при фиксированной величине критического пути

Пусть для каждой работы известны след. данные:

- мин. прод-ть выполн. раб., кот. соотв. наименьшие затраты .

-норм. прод-ть, кот. будут соответств. наименьшие затраты .

Будем считать, что затраты на выполнение отд. работ нах-ся в обратной зав-ти от прод-ти их выплн-я.

К-м доп. затрат (КДЗ) будем считать к-т, кот. нах-ся по форм. и показывает, насколько увел-ся ст-ть работы (ij)при уменьшении времени её выполнения на одну ед.

Пусть задан сетевой гр. проекта. Известны прод-ти выполнения работ и их ст-ть в срочном режиме (;).

Понятно, что в этом сл. cт-ть проекта будет наиб-й, а время вып-я наименьшим. Ставится задача миним-и ст-ти проекта за счёт увеличения времени отд. работ при фиксир. сроке t0 . В этом сл. tкр. может быть < заданного срока или равно ему. Если =t0 , то в этом сл. оптим-я возможна только за счёт резервов некрит. работ, а если <0, то за счёт резервов всех работ проекта. После оптим-и все работы будут крит-ми, т.к. их прод-ти будутдостигать наиб-х возм. значений. Ни одно событие, ни одна работа не будут иметь резерва. Такой план наз-ся безерезервным. Здесь ранние и поздние сроки свершения событий будут совпадать, а времена начала и окончания работ будут совпадать со сроками свершения событий, поэтому неизв. задачи будем считать сроки свершения событий. Прод-ть выпол-я кажд. работы в оптим. плане опр-ся как разность , а ст-ть вып-я работ будет опр-ся по формуле.

След-но, модель задачи запишется в виде:

->=, (i;j)∊

=0, <=

67. Оптимизация проекта по ресурсам

Данная задача явл-ся осн. задачей при планир-и.

Пусть задан сет. график проекта: G=(E;). Кол-во ресурсов =R. Для каждой работы будут приписаны 2 числа: 1. Прод-ть вып-я работы (); 2.– интенсивность потр. рес-в, т.е. кол-во ресурса, кот. необходимо для вып-я работ (i;j). Требуется так разместить работы во времени, чтобы в любой момент времени было дост. кол-во ресурса и при этом время вып-я всего комплекса работ было мин-м.

Алгоритм

Предв. шаг: по сет. гр. составляем лин., по кот. опр-м крит. время и крит. путь.

1. 1 проецир-м на ось времени начало и конец кажд. работы. На каждом врем. отрезке опр-м суммарное кол-во потр-го ресурса.

1.2 рассматриваем отрезок [] . Над этим отрезком рассм-м все работы. Нумеруем эти работы в порядке возрастания их полных резервов времени. Работы с одинаковыми полными резервами нумеруем в порядке убывания интенсивности.

1.3 в порядке присвоенных номеров послед-но суммируем инт-ти работ и сравниваем полученные суммы с заданной величиной ресурса. Если после прибавления инт-ти оосн. работ сумма превосходит R, то эта работа сдвигается вправо на вел-ну рассматр. отрезка. Переходим к добавлению инт-ти очередной работы.

Общий шаг:

1. Рассматриваем отрезок [;]. Рассм. все работы, лежащие над этим отрезком. Нумеруем эти работы, но в первую очередь нумеруются работы, кот. нач-ся левее начала отрезка. Эти работы нумеруются в порядке возрастания разности между остальными резервами этих работ и концом отрезка. Ост. работы нум-ся согл. 1-го шага.

2. пунк 3 1-го шага.