Linear optimization for pert/cpr

Hello everyone. I am currently studiyng operational research using Frederik Hillier's book.

I am in the part of PERT/CPM.

In it, project crashing is defined as an integer optimization problem with auxiliary variables. Crashing consists on spending as much money as possible to finnish tasks as fast as possible.

There are tasks A to N to be performed. The goal is to minimize the expenditure while at the same time, finishing the project in 40 weeks.

The relationships between the different tasks can be seen in the following figure:

The times and costs for all tasks are as follow, with times in weeks and the costs in thousands of dollars:

Activity Regular time Crashed time Regular cost Crash cost Max. time reduction Weekly crash $

A 2 1 180 280 1 100

B 4 2 320 420 2 50

C 10 7 620 860 3 80

D 6 4 260 340 2 40

E 4 3 410 570 1 160

F 5 3 180 260 2 40

G 7 4 900 1020 3 40

H 9 6 200 380 3 60

I 7 5 210 270 2 30

J 8 6 430 490 2 30

K 4 3 160 200 1 40

L 5 3 250 350 2 50

M 2 1 100 200 1 100

N 6 3 330 510 3 60

If all times are added, it can be seen that without crashing, 44 weeks are needed to end the process.

I have developed the following code to try to solve this problem, where, as suggested in the book, equations are represented as :

, which represents duration of task j=regular time , and is the starting time of each activity.

close all
clear
clc

    %xa xb xc xd xe  xf xg xh xi xj xk xl xm  xn  yb yc yd ye yf yg yh yi yj yk yl ym yn yFIN
f =[100 50 80 40 160 40 40 60 30 30 40 50 100 60  0  0  0  0  0  0  0  0  0  0  0  0  0  0];
%Function to minimize (costs of crashing each task)
intcon = [1:length(f)];
lb = zeros(size(intcon));
    %xa xb xc xd xe xf xg xh xi xj xk xl xm xn yb yc yd ye yf yg yh yi yj yk yl ym yn yFIN
 A=[-1  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0;%B-A
     % yB >=0+2-xA==>-2 >=-xA-yB  Each of these equations represents the upper row
     0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0  0;%C-B
     % yC >= yB+4-xB==> -4 >= -xB+yB-yC
     0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0  0  0;%D-C
     % yD >= yC+10-xC==> -10 >= -xC+yC-yD
     0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0 -1  0  0  0  0  0  0  0  0  0  0;%E-C
     % yE >= yC +10 -xC==> -10 >= -xC+yC-yE
     0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0  0  0;%F-E
     % yF >= yE +4 -xE==> -4 >= -xE+yE-yF
     0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 -1  0  0  0  0  0  0  0  0;%G-D
     % yG >= yD +6 -xD ==> -6 >= -xD+yD-yG
     0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 -1  0  0  0  0  0  0  0;%H-E
     % yH >= yE + 4 -xE ==> -4 >= -xE+yE-yH
     0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0;%H-G
     % yH >= yG + 7 -xG ==> -7 >= -xG+yG-yH
     0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0 -1  0  0  0  0  0  0;%I-C
     % yI >= yC + 10 -xC ==> -10 >= -xC+yC-yI
     0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0 -1  0  0  0  0  0;%J-F
     % yJ >= yF + 5 -xF ==> -5 >= -xF+yF-yJ
     0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0  0;%J-I
     % yJ >= yI + 7 -xI ==> -7 >= -xI+yI-yJ
     0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1  0  0  0  0;%K-J
     % yK >= yJ + 8 -xJ ==> -8 >= -xJ+yJ-yK
     0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0 -1  0  0  0;%L-J
     % yL >= yJ + 8 -xJ ==> -8 >= -xJ+yJ-yL
     0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0 -1  0  0;%M-H
     % yM >= yH + 9 -xH ==> -9 >= -xH+yH-yM
     0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0 -1  0;%N-K
     % yN >= yK + 4 -xK ==> -4 >= -xK+yK-yN
     0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0 -1  0;%N-L
     % yN >= yL + 5 -xL ==> -5 >= -xL+yL-yN
     0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0 -1;%Fin-M
     % yFIN >= yM + 2 -xM ==> -2 >= -xM+yM-yFIN
     0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1];%Fin-N
     % yFIN >= yN + 6 -xN ==> -6 >= -xN+yN-yFIN
 
 
 %   A   B C   C   E  D  E  G  C   F  I  J  J  H  K  L  M  N   
 b=-[2; 4; 10; 10; 4; 6; 4; 7; 10; 5; 7; 8; 8; 9; 4; 5; 2; 6];
%This vector contains the durations of the non-crashed tasks of matrix A

%    xa xb xc xd xe xf xg xh xi xj xk xl xm  xn  yb yc yd ye yf yg yh yi yj yk yl ym yn yFIN 
ub =[1  2  3  3  1  2  3  3  2  2  1  2  1   3   4  10 6  4  5  7  9  7  8  4  5  2  6  40];
%Máximum crashed and regular end times for each task 


[x,fval] = intlinprog(f,intcon,A,b,[],[],lb,ub)

No feasible solution found.

Intlinprog stopped because no point satisfies the constraints.


x =

     []


fval =

     []

However, if it is run, it arrives to an ungeasible solution.

Has someone developed this code before and can share it? if not, can someone please help me?

Best regards.

Jaime.