cpm.m

一些常被用于教学或者参考的概率论的实例的源代码

%cpm.m/created by PJNahin for "Duelling Idiots"(10/17/98)
%This m-file executes the Critical Path Method algorithm
%for the project shown in Figure 21.1.
%
%
ntasks=8;             %number of tasks, where task #1 is the pseudo-task
                      %BEGIN and the last task is the pseudo-task END;
                      %it is assummed that all tasks are numbered in
                      %sequence, from BEGIN as task #1 to END;
data(1,:)=[0,0,0,0];  %enter individual task data, in the following
data(2,:)=[1,1,2,0];  %format: for task i, data(i,:)=
data(3,:)=[1,1,1,0];  %[<# of immediate predecessor tasks>,
data(4,:)=[2,2,3,1];  %<task #'s of immediate predecessors>,
data(5,:)=[2,2,3,2];  %<time to do task>];
data(6,:)=[1,4,2,0];  %IMPORTANT POINT 1: all data statements must be
data(7,:)=[2,5,6,1];  %of the same length, so pad-out all statements
data(8,:)=[1,7,0,0];  %that have less than the maximum length with
                      %zeros.
                      %IMPORTANT POINT 2: the data statements MUST be
                      %entered in sequence from BEGIN to END, i.e.,
                      %all of the predecessor tasks of each task
                      %must appear in earlier data statements;
%
time=zeros(50,5);     %initialize matrix of important times;
p=zeros(50,50);       %initialize immediate predecessor matrix;
for i=1:ntasks            %for task i, get number of immediate predecessors
  npred=data(i,1);        %where data(i,2) to data(i,1+npred) are the task
                          %numbers of the immediate predecessors of task i;
  k=1+npred;
    for j=2:k
       p(i,data(i,j))=1;  %tag the task pointed at by data(i,j) as
                          %an immediate predecessor of task i, i.e.,
                          %p(i,q)=1 if task q is an immediate
                          %predecessor of task i;
    end
 time(i,5)=data(i,k+1);   %enter time to do task i into
                          %matrix of important times
end
%Start forward pass to determine the earliest start and finish times
%for each task, stored as time(i,1) and time(i,2), respectively.
 for i=1:ntasks
    earlyctime=0;         %initialize earliest possible completion
                          %time for immediate predecessors of task i
                          %(we are looking for the immediate predecessor
                          %with the MAXIMUM completion time, as task i
                          %cannot be started until ALL of its predecessors
                          %are done);
       for j=1:ntasks                   
          if p(i,j)==1    %if task j is an immediate                
                          %predecessor of task i then .....
               if earlyctime<time(j,2)    %if we have found a new
                                          %maximum completion time then .....
                  earlyctime=time(j,2);   %up-date maximum
                                          %completion time of a
                  else                    %predecessor task to task i;
                end
               else
            end
         end                              %have we checked for all
                                          %predecessor tasks?
time(i,1)=earlyctime;             %yes, so record earliest time task i can
time(i,2)=earlyctime+time(i,5);   %start and record earliest time task i
                                  %can be finished;
end                               %repeat for next task;
%
%
%Start backward pass to determine the latest start and finish times
%for each task, stored as time(i,3) and time(i,4), respectively.
projectdone=time(ntasks,1);       %get the time required to do the project
for i=ntasks:-1:1
   lateftime=projectdone;    %initialize latest possible finish
                             %time for task i; to do do this, look
                             %at all of the successor tasks for
                             %task i and find the one that starts
                             %soonest, i.e., find the successor
                             %task that has the MINIMUM start
                             %time (if task i starts later than
                             %that time then that successor task
                             %will be delayed);
    for j=1:ntasks
       if p(j,i)==1;         %if task i is an immediate predecessor
                             %task j (i.e., if task j is an
                             %immediate successor of task i) then ...
           if lateftime>time(j,3)    %if we have found a new minimum
                                     %start time for task j then ...
              lateftime=time(j,3);   %up-date late finish time
             else                    %for task i;
           end
          else
        end
end                             %have we checked for all successor tasks?
time(i,4)=lateftime;            %yes, so record latest time task i can end;
time(i,3)=lateftime-time(i,5);  %and latest time that task i can start;
end
%Display results
disp('Total time required for project = '), disp(projectdone)
disp('task     early start time     slack')
realtasks=ntasks-1;
for i=2:realtasks
   slack=time(i,3)-time(i,1);
   ans=[i     time(i,1)      slack];
   fprintf('  %g              %g              %g\n',ans(1),ans(2),ans(3))
end