Минимальное время – минимальная стоимость при монотонном варьировании ресурсов

Пример

Операция Непосредственно предшествующая операция Время операции, недель
A B C D E F G H - - - A, B B, C C D, E F, G

 

Критический путь – операции В – Е – G - Н

Некритические операции – F , D , A , C.

Резерв времени выполнения операции F равен R(F) = ПН-РН=19-6=13

R(D) = 11-10

R(A) = 3-0

R(C) = 4-0

 

 

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

 

 

Операция Предшествующая операция Стандартное время (нед.) Стандартная стоимость ($) Критическое значение врем. Критическое значение стоимости
A B C D E F G H - - - A, B B, C C D, E F, G
Общие издержки      

 

 

Стоимость строительной площадки – 1000 $ в неделю.

 

Необходимо ответить на вопросы:

  1. Каково минимальное время, в течение которого можно завершить проект?
  2. Какова соответствующая минимальная дополнительная стоимость?

 

По нашим исходным данным построим вершинный граф и рассчитаем его дважды:

  1. По стандартным параметрам.
  2. По критическим параметрам.

 

Вершинный граф примет вид

 

 

 

 

Стандартная стоимость – Стоимость операций + 39 * стоимость строительной площадки в неделю = 82500 + 39 * 1000 = 121500 $.

 

Критическая стоимость = 102750 + 28 * 1000 = 130750 $.

 

Некритические операции – A, C, D, F

 

Минимальная стоимость выполнения проекта за 28 недель составит:

130750 – 1500 (А) – 1000 (С) – 3500 (F) = 124750 $.

 

Дополнительная стоимость, связанная с завершением проекта на 11 недель раньше, будет равна:

124750 – 121500 = 3250 $.

 

Минимальное время – минимальная стоимость при монотонном варьировании ресурсов

 

Пример – Контракт на производство партии станков.

 

 

Операция и предшеств. опер. Станд. время Станд. Стоим. Возможное сокращение на ….. недель Критич. время Дополн. издержки
A - B A C B D B E D F C, E G F H D I D J H, I K G, J L K 1=2-1 1=1-0 2=4-2 2=6-4 1=3-2 1=3-2 1=4-3 2=2-0 2=3-1 4=8-4 1=2-1 1=2-1
  Сумма =      

 

 

Дополнительные издержки = 400*1+125*2+175*4+250*2+200*2+125*3+200*1+100*4+250*1+150*1=3625

Переменные накладные расходы составляют 250 $ в неделю.

 

Необходимо:

1. Определить стандартные значения общего времени выполнения и общей стоимости проекта.

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

 

Стандартный блок – 9 ячеек

Самое раннее нач. СТ./ Самое раннее нач. КР. Самое раннее окончание Критический срок Самое раннее окончание
Операция Стандартная длительность На сколько можно сократ./ Критическая длительность
Самое позднее нач. СТ./ Самое позднее нач. КР. Самое позднее окончание Критический срок Самое позднее окончание

 

При стандартных параметрах один критический путь: A, B, D, I, J, K, L.

 

При критических параметрах имеем два критических пути:

  1. A, B, D, H, J, K, L
  2. A, B, D, I, J, K, L

 

Стандартная минимальная продолжительность выполнения проекта равна 24-м неделям, стандартная стоимость = 24*250 + 4050 = 6000 + 4050 = 10050 $.

 

Минимальная продолжительность проекта – 12 недель, критическая стоимость = 12*250 + 4050 + 3625 = 10675 $.

 

Некритические операции – C, E, F, G. Рассмотрим возможность перехода в некритических операциях на стандартные сроки выполнения.

Продолжительность операций в данном примере можно изменять по интервалам в одну неделю, так как единицей измерения продолжительности является неделя. В первую очередь рассмотрим операции, которые, если использовать их некритические значения, могут принести наибольшую экономию денежных средств. Здесь формально возникает задача перебора на множестве некритических операций при критерии оптимальности – максимум экономии ресурсов. В нашем случае установим порядок предпочтения в соответствии с эффектом экономии средств от различных операций: E(250$) - F(200$) - C(125$) - G(125$). Операцию E можно вернуть к стандартному сроку (см. граф). Операцию F удается удлинить только на одну неделю от критического срока. При этом операция G становится критической. Остается операция С, которую можно вернуть к стандартному сроку выполнения.

При переходе в некритических операциях на стандартные сроки выполнения экономия составит: 2*250+1*200+2*125 = 950 $ при сохранении минимальной продолжительности выполнения проекта 12 недель.

Теперь минимальная стоимость проекта = 10675 – 950 = 9725 $.