aon.cpp

Go to the documentation of this file.

/* dtree: Dick Barr's Critical Path Method, Activity-on-Node networks
*/

// #include <fstream.h>
#include <fstream>
#include "stdio.h"
#include <cmath>
#include <iostream>
#include <sstream>
#include <climits>
#include <stack>
//#include <stdlib.h>
#include <string>
#include <math.h>
//#include <stddef.h>
#include <cstring>
#include <cstdlib>

#define MAX(AA,BB) (((AA)>(BB))?(AA):(BB)) 
#define MAXNODES 100
#define MAXARCS  500
#define MAXDESC 50     //Arc descriptor length
#define MAXID 4        //Arc id length
#define NAMELEN 8
#define debug    0


using namespace std;

struct activity{long num, dur; activity *next;};
struct NODE {           // Node = task or activity to be assigned to station
                long            nodenumber;
                char            nodename[NAMELEN+1];
                long            tasktime;
                long            fstar;                  // First arc in fstar linked list
                long            bstar;                  // First arc in bstar linked list
                long            fcount;                 // number of forward arcs out of this node
                long            bcount;                 // number of backward arcs into this node
                long            preds;                  // number of predecessor tasks
                long            successors;             // number of successor tasks
                long            rank;                   // sorted rank of node
                long            station;                // assigned station number
                long            label;                  // temporary label
                long            ES;                     // earliest task start time
                long            EF;                     // earliest finish time
                long            LS;                     // latest start time
                long            LF;                     // latest finish time
                long            slack;                  // activity slack
                long            unsetpreds;             // for forward pass
                long            unsetsuccs;             // for backward pass
                char            nodeid[MAXID+1];        // Node identifier string
                char            nodeDesc[MAXDESC+1];    // Node descriptor
                };

struct ARC {            // Arc = dependency between two nodes
                long            arcnumber;              // unique arc id number
                long            fromnode;               // from node id
                long            tonode;                 // to node id
                long            fstar;                  // Next arc in fstar linked list
                long            bstar;                  // First arc in bstar linked list
                };

struct STATION {
        long    stationtime;                    // total time for all assigned tasks
        long numTasks;                          // number of assigned tasks
        long stationNum;                                // station sequence number
        };

class project {
public:
   project(){tMax = 0; numNodes=numArcs=0;}
   long min, n; // Minimum event number and n = max - min + 1
   void ReadProblem(const char *fname);
   void ReadProblem2(const char *fname);
   void AssignAllTasks(long,long);
   void AssignmentReport(long,long);
   long NodeNum(char*);
   long NewNodeNum(char*);
   long MakeStation(long,long);
   long IsTie(long,long);
   long  FindTaskFit(long);
   void RankTasks(long);
   long  Better(long,long,long);
   void PrintRanking(long);
   void CountPreds();
   void CountSuccessors();
   void AddPreds(long);
   void AddSuccessors(long);
   void ZeroNodeLabels();
   void ZeroNodePreds();
   void ZeroNodeSuccessors();
   void Printout();
   void NodeReport();
   void ArcReport();
   void Evaluate();
   void DoNode(long,string);
   void PutNode(long);
   void OutNodeLabel(long);
   void PutArc(long, string, long);
   void Driver(long,char**);
   void CPM();
private:
   long         tMax;
   long         numNodes;
   long         numArcs;                                // number of arcs
   long         numStations;
   long         numCritical;                    // # critical activities
   long         root;
   long         totaltime;
   long         istart;                         // the start node
   long         iend;                           // the end node
   NODE         node[MAXNODES+1];
   ARC          arc[MAXARCS+1];
   STATION      station[MAXNODES+1];
   long         tsort[MAXNODES+1];
   void         SkipRestLine(ifstream &file);
   stack <long> nodestack;
};


void project::AssignmentReport(long ct,long rule) {
        long i,idle,calc;
        double e;
        cout << endl << "  *** ASSEMBLY LINE SUMMARY ***" << endl << endl;

        printf("Problem:\n");
        printf("--------\n");
        printf("Number of tasks       %d\n",numNodes);
        printf("Total task time       %d\n",totaltime);
        printf("Longest task time     %d\n",tMax);
        printf("Target cycle time     %d\n\n",ct);

        printf("Assignment:\n");
        printf("-----------\n");
        printf("Rule                  %d\n",rule);
        for(i=1, calc=0; i <= numStations; ++i) {calc = MAX(calc,station[i].stationtime);}
        ct = calc;
        printf("Computed cycle time   %d\n",ct);
        printf("Stations used, N      %d\n",numStations);
        idle = 0;
        for(i=1; i <= numStations; ++i) {idle += (ct-station[i].stationtime);}

        printf("Output per hour, N'   %.2lf (if seconds)\n",3600.0/(double)ct);
        printf("                      %.2lf (if minutes)\n",60.0/(double)ct);
        printf("Station time/cycle    %d\n",numStations*ct);
        printf("Idle time/cycle       %d\n",idle);
        e = (double)totaltime/((double) numStations*(double)ct);
        printf("Efficiency, E         %lf\n",e);
        printf("Fraction idle, 1-E    %lf\n",1.0-e);
        printf("Balance delay         %lf\n",100.0*(1.0-e));
        }

void project::AssignAllTasks(long ct,long rule) {
        long i, tasksleft;
        cout << endl << "  *** WORKSTATION ASSIGNMENTS ***" << endl << endl;
        cout << "For cycle time = " << ct << ", using rule " << rule << endl ;
        if (ct < tMax) {
                cout << "Infeasible cycle time, reset to " << tMax << ", the largest task time"<< endl;
                ct = tMax;
                }
        cout << endl;

        for (i=1; i <= numNodes; ++i) node[i].label = node[i].bcount;

        for (numStations=0,tasksleft=numNodes; numStations <= numNodes && tasksleft; ) {
                ++numStations;
                MakeStation(numStations,ct);
                tasksleft -= station[numStations].numTasks;
                }
        }

long project::MakeStation(long s, long cycletime) {      // assign tasks to workstation s, return # assigned
        long t,a,timeleft,cumtime;
        static STATION initstation = {0,0,0};

        timeleft = cycletime;
        cumtime  = 0;
        station[s] = initstation;
        // NodeReport();
        // ArcReport();

        // cout << endl<<"Station " << s << ":" << endl;
        // cout << "Task  Time  CumTime" << endl;
        // cout << "----  ----  -------" << endl;
        cout << "Station " << s << " tasks:" ;

        while ((timeleft > 0) && (t=FindTaskFit(timeleft)) > 0) {
                node[t].station = s;
                ++station[s].numTasks;
                station[s].stationtime += node[t].tasktime;
                timeleft -= node[t].tasktime;
                // printf("%4d%6d%9d\n", t, node[t].tasktime, station[s].stationtime);
                cout << " " << node[t].nodename;
                a = node[t].fstar;
                while(a) { --node[arc[a].tonode].label; a = arc[a].fstar;}
                }

        cout << " (time = " << station[s].stationtime << ")" << endl;
        // cout <<"-------------------" << endl;
        }

long project::FindTaskFit(long timeleft) {    // Return next task that fits or 0
        long i,t;
        for (i=1; i <= numNodes; ++i) {
                t = tsort[i];
                if (t <= 0) continue;         // skip if already assigned
                if (node[t].label) continue;  // skip if all preds not assigned
                if (node[t].tasktime <= timeleft) {
                        tsort[i] = -tsort[i];
                        return t;
                        }
                }
        return 0;
        }

void project::PrintRanking(long rule){
        long ties = 0;
        cout << "Tasks ranked by rule " << rule << ":" << endl;
        for (long i=1; i <= numNodes; ++i) {
                cout << " " << node[tsort[i]].nodename;
                if (IsTie(tsort[i],tsort[i-1])) {++ties; cout << "*"; }
                // if (IsTie(tsort[i],tsort[i-1]) || IsTie(tsort[i],tsort[i+1])) {++ties; cout << "*"; }
                }
        cout << endl;
        if (ties) cout << " (*task tied with prior task in ranking)" << endl;
        }

long project::IsTie(long i, long j) {
        if(i <1 || i > numNodes || j < 1 || j > numNodes) return 0;
        if (node[i].preds == node[j].preds && node[i].tasktime == node[j].tasktime) return 1;
        else return 0;
        }

void project::RankTasks(long rule) {
        long i,j,best,hold;
        for (i=1; i <= numNodes; ++i) tsort[i] = i;
        for (i=1; i < numNodes; ++i) {
                best = i;
                for (j=i+1; j <= numNodes; ++j) { if(Better(tsort[j],tsort[best],rule)) best = j; }
                if (best != i) {hold = tsort[i]; tsort[i]=tsort[best]; tsort[best] = hold;} // Swap
                }
        }

long project::Better(long j, long i, long rule) { // returns i or j, whichever is better
        switch (rule) {
                case 1: if (node[j].preds > node[i].preds) return 0;
                                else if (node[j].preds < node[i].preds) return 1;
                                break;
                case 2: if (node[j].successors < node[i].successors) return 0;
                                else if (node[j].successors > node[i].successors) return 1;
                                break;
                }
        // Tie-breaker: longer task time first
        if (node[j].tasktime > node[i].tasktime) return 1;
        else return 0;
        }

void project::OutNodeLabel(long i){
        char buf[20];

        cout << i;
        }

void project::PutArc(long a, string tab, long usetab)
// Print arc[a], if usetab then print tab first
        {
        const char* cp;
        char buf[10];

        cp = tab.c_str();
        return;
        }

void  project::DoNode(long i, string tab1)
// Process node[i] and all outbound branches
        {
        long a,j,lvl,t;
        string postfix;
        
        a = node[i].bstar;
        t = 0;
        while (a) {
                PutArc(a,tab1,t);
                DoNode(arc[a].tonode,postfix);
                a = arc[a].bstar;
                t = 1;
                }
        cout << tab1 << endl;
        return;
        }

        
void project::SkipRestLine(ifstream &file)
{  char ch;
   do file.get(ch); while (!file.fail() && ch != '\n');
}


long project::NodeNum(char* s) {
        if (numNodes == 0) return NewNodeNum(s);
        for (long i=1; i <= numNodes; ++i) { if (!strncmp(s,node[i].nodename,NAMELEN)) return i; }
        return NewNodeNum(s);
        }

long project::NewNodeNum(char* s) {
        ++numNodes;
        memcpy(node[numNodes].nodename, s, sizeof(char)*(NAMELEN));
        node[numNodes].nodename[NAMELEN+1] = '\0';
        node[numNodes].ES       = 0;
        node[numNodes].LS       = LONG_MAX;
        return numNodes;
        }

void project::ReadProblem2(const char *fname)
{       long  ifrom, jto, tasktime;
        int nstart, nend;   // number of start/end nodes (with 0 preds/succs)
        char buf[256],save[256];
        char *token;

        ifstream file;
        file.open(fname, ios_base::in);
        if (file.fail()) {  cout << "Cannot open input file.\n"; exit(1); }

        for (numArcs=0;;)
          {  
          file.getline (buf,256);
          if (file.eof()) break;
          memcpy(save,buf,sizeof(char)*256);

          token = strtok(buf," \t");    // Node/task name
          jto = NodeNum(token);

          token = strtok(NULL," \t");
          node[jto].tasktime = atoi(token);
          if (node[jto].tasktime > tMax) tMax = node[jto].tasktime;
          totaltime += node[jto].tasktime;

          while (token = strtok(NULL," \t") ) {
                ifrom = NodeNum(token);
                ++numArcs;
                arc[numArcs].fromnode = ifrom;
                arc[numArcs].tonode     = jto;
                arc[numArcs].bstar      = node[jto].bstar;
                node[jto].bstar         = numArcs;
                arc[numArcs].fstar      = node[ifrom].fstar;
                node[ifrom].fstar               = numArcs;
                ++node[ifrom].fcount;
                ++node[jto].bcount;
                }
          for (int i=1, nstart=nend=0; i <= numNodes; ++i) {
                if (node[i].preds == 0) { istart = i; ++nstart;}
                if (node[i].successors == 0) { iend = i; ++nend;}
                }
                
      }

   file.close();
   cout << numNodes << " task nodes, " << numArcs << " precedence arcs";
   cout << ", and " << totaltime << " time units for all tasks" << endl;
   if(istart != 1) { cout << "Exactly 1 start node (with no predecessors) is required.\n"; exit(1); }
   if(iend != 1) { cout << "Exactly 1 end node (with no successors) is required.\n"; exit(1); }
}

void project::CountPreds(){
        long i;
        ZeroNodePreds();
        for (i=1; i <= numNodes; ++i) {
                ZeroNodeLabels();
                AddPreds(i);
                }
        return;
        }

void project::AddPreds(long i){
        long a;
        if (node[i].label) return;
        ++node[i].preds;
        node[i].label = 1;
        a = node[i].fstar;
        while(a) {
                AddPreds(arc[a].tonode);
                a = arc[a].fstar;
                }
        return;
        }

void project::ZeroNodeLabels(){
        for(long i=1; i<= numNodes; ++i) node[i].label = 0;
        }

void project::ZeroNodePreds(){
        for(long i=1; i<= numNodes; ++i) node[i].preds = -1;
        }


void project::CountSuccessors(){
        long i;
        ZeroNodeSuccessors();
        for (i=1; i <= numNodes; ++i) {
                ZeroNodeLabels();
                AddSuccessors(i);
                }
        return;
        }

void project::AddSuccessors(long i){
        long a;
        if (node[i].label) return;
        ++node[i].successors;
        node[i].label = 1;
        a = node[i].bstar;
        while(a) {
                AddSuccessors(arc[a].fromnode);
                a = arc[a].bstar;
                }
        return;
        }

void project::ZeroNodeSuccessors(){
        for(long i=1; i<= numNodes; ++i) node[i].successors = -1;
        }

void project::Evaluate(){
        long i;
        long queue[MAXNODES+1];
        long qlen;
        long evnode; // node being evaluated
        long evarc;
        long pred;
        long evcount;

        qlen = 0;
    for(i = 1; i <=numNodes; ++i) {
                }

        evcount = numNodes;
        while (qlen > 0) {
                evnode = queue[qlen--];
                --evcount;
                evarc  = node[evnode].fstar;
                pred   = node[evnode].bstar;
                --node[pred].label;
                if (debug) {cout << "Evaluating node " << evnode << "  Q = {";
                    for (i=1; i<= qlen; ++i) cout << queue[i] << " ";
                        cout << "}" << endl;
                        }
                        
                        node[pred].bstar = evarc;  // add to chain of child arcs for pred node
                        if ((node[pred].label) <= 0) queue[++qlen] = pred;
                }

        if (evcount) cout << "** There are " << evcount << " unevaluated nodes" << endl;
        root = evnode;
        }

void project::NodeReport(){
   long i;
   char buf[25];

   cout <<endl<<"      *** TASK SUMMARY ***"<< endl << endl ;
   cout << "    Task   Time   Preds Succs";
   if (debug) cout << "Fstar Bstar   Fcount Bcount   Label";
   cout << endl;
   for(i=1;i<=numNodes; ++i) {
                printf("%8.8s   %4d   %5d %5d ",node[i].nodename,node[i].tasktime, node[i].preds, node[i].successors); 
                if (debug) printf("%    %5d %5d   %5d",
                        node[i].fstar, node[i].bstar, node[i].fcount, node[i].bcount, node[i].label);
                cout << endl;
                }
        cout << endl;
}

void project::ArcReport(){
   long i;

   cout << endl << "  *** TASK PRECEDENCE REQUIREMENTS ***"<< endl << endl;
   printf(" Arc  From   To   Fstar  Bstar\n");
   printf("----- ---------   -----  -----\n");

   for(i=1;i<=numArcs; ++i) {
                printf("%3d  %3d  %3d   %5d  %5d\n", 
                i, arc[i].fromnode, arc[i].tonode, arc[i].fstar, arc[i].bstar);
                }
        }

void project::Driver(long argc, char *argv[])
        {
        char *fname; 
        long cycletm, irule;

        if (argc != 2) {
                cout << "Usage:  aon  inputFilename \n";
                exit(1);
        }
        fname = argv[1];
        cout << "*** CPM-AON Critical Path Method, Activity-on-Node *** " << endl << endl;
        ReadProblem2(fname);     // Find range of event numbers
        CountPreds();
        CountSuccessors();
        NodeReport();
        RankTasks(irule);
        PrintRanking(irule);
        AssignAllTasks(cycletm,irule);
        AssignmentReport(cycletm,irule);
        }

void project::CPM ()
        {
//   Forward pass
        long i,j,n,EFi,LSi;

        for (i=1; i < numNodes; ++i) {
                node[i].unsetpreds = node[i].bcount;
                node[i].unsetsuccs = node[i].fcount;
                }

        node[istart].ES = 0;
        nodestack.push(istart);
        do      {
                i = nodestack.top();
                nodestack.pop();
                EFi = node[i].EF        = node[i].ES + node[i].tasktime;
                // Explore fstar list for node i and add complete ones to stack
                if ((n = node[i].fcount) > 0) {
                        j = arc[node[i].fstar].tonode; // next successor
                        for(; n >0; --n){
                                if(EFi > node[j].EF) node[j].EF = EFi;
                                if((--node[j].unsetpreds) == 0) nodestack.push(j);
                                j = arc[node[j].fstar].tonode; // next successor
                                }       
                        }
                } while(!nodestack.empty());

//    Backward pass

        node[iend].LF   = node[iend].EF;
        nodestack.push(iend);
        do      {
                i       = nodestack.top();
                nodestack.pop();
                LSi     = node[i].LS    = node[i].LF - node[i].tasktime;
                if((n = node[i].bcount) > 0) {
                        j = arc[node[i].bstar].fromnode;    // next predecessor node
                        for (; n > 0; --n) {
                                if(LSi < node[j].LS) node[j].LS = LSi;   // new min LSj
                                if((--node[j].unsetsuccs) == 0) nodestack.push(j);
                                j = arc[node[j].bstar].fromnode;        // next pred in bstar list
                                }
                        }
                } while(!nodestack.empty());

//    Compute slacks

        for(i=1,numCritical=0; i<numNodes; ++i) {
                node[i].slack = node[i].EF - node[i].ES;
                if(node[i].slack == 0) ++numCritical;
                }
        }

int main(int argc, char *argv[])
{  project g;

        g.Driver(argc,argv);
   return 0;
}

---