#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
#include <string.h>

#include "sodl.h"
#include "sbd.h"
#include "om.h"
 




/* ********************************************************
   *********************************************************/

static int compare(const void *p1, const void *p2)
{
        struct jobco *i ;
        struct jobco *j ; 

        i = (struct jobco *) p1 ;
        j = (struct jobco *) p2 ;       
        
 if (i->rel > j->rel) { return(1) ; }
 else { return(-1) ;}
}

/*
 *
 */

qsorta(long numa)
{
        long i , j  ;
        int kk ;
        int temp_k ;
        int temp_rel ;
        int index ;

        for (i=1;i<=numa;i++) {
                kk = ((long)  RAND_MAXI) ;
                 for (j=i;j<=numa;j++) {
                         if (myn[j].rel < kk) {
                                 index = j ;
                                 kk = myn[j].rel ;
                         }
                 }
                 temp_k = myn[index].k  ;
                 temp_rel = myn[index].rel ;
                 myn[index].k = myn[i].k ;
                 myn[index].rel = myn[i].rel ;
                 myn[i].k = temp_k ;
                 myn[i].rel = temp_rel ;
        }


}


/* *********************************************************
   * onemachine()                                            *
   * This code solves the One Machine Scheduling Problem     *
   * and variations such that when we have  precedence       *
   * constraints and delays. Delays are certain time         *
   * delays between n that have to be satisfied.             *
   * The algorithm for the One Machine Scheduling problem    *
   * is of Carlier and the algorithm  for the precedence     *
   * constraints and delays are of Balas & Vazacopoulos.     *
   * The program is written by Alkiviadis Vazacopoulos.      *
   * Graduate School of Industrial Administration            *
   * Carnegie Mellon University. Pittsburgh, PA 15213        *
    **********************************************************/


onemachine(long n ,
     long *optimal_makespan ,
     long solve_with_deadlines ,
     long *bmksp ,
     long status )
{
  long i  ;
  long lower_root;
  long opt ;
  long lb  ; 

  visited = 0.0 ; 
  total_cjobs = 0.0 ;
  total_parci = 0.0 ;

  for (i=0;i<=n+1;i++) zero[i] = 0 ; 

  root      = (struct onema *) NULL ;
  lpointer  = (struct onema *) NULL ;
  md        = (struct onema *) NULL ;
  ms        = (struct onema *) NULL ;
  protos    = (struct onema *) NULL ;
  npointer  = (struct onema *) NULL ;

  opt      = ((long) RAND_MAXI) ; 
  idep     = 0 ;
  depth    = 1 ; 
  lb       = 0 ; 
  lower_root = 0 ;  
  nodes = 1;

  STORE_FIRST_PROBLEM(n,lb) ; 


  Strong = 0 ;
  Weak = 0 ; 
  Edges    = 0.0 ; 
  Branches = 0.0 ; 
  StrongB = 0 ; 
  Elimin = 0 ; 
  Critic = 0 ;
  Rel = 0 ;

/*  printf("Solving One machine ..... \n") ; */

  
  while  (( opt > lower_root) && 
          ( root != ((struct onema *) NULL) ) && 
          ( nodes <= maxnodes ))  {

          
          if (status) { if (opt < *bmksp) goto returni ; } 
    getaproblem(n,&lb,&opt) ;
    if (lb > lower_root) lower_root = lb ; 
    test_inverse = 0 ; 

    if (opt > lower_root) branching(n,lb,&opt) ;

    free(md->rls) ;
    free(md->tls) ;
    for (i=0;i<3;i++) free(md->rules[i]) ;
    free(md) ;
  }

 returni:


         cleanmemory() ;
  *optimal_makespan = opt ; 
  
  if (solve_with_deadlines) {
    RESTORE_RANDOM_PROBLEM(n) ; 
    CALCULATE_COMPLETION_TIMES(n) ;
  }
}



/*  ************************************************************ 
     *********************************************************** */

CALCULATE_COMPLETION_TIMES(long n )
{
  long i ;
  long ctime , cjob , okey ;
  long CHECK_PRED() ;

  ctime = 0 ;  
  for (i=1;i<=n;i++) { moda[i] = release[i] ; schedule[i] = 0 ; }
  for (i=1;i<=n;i++)
    {
     cjob = order[i] ; 
     okey = CHECK_PRED(cjob) ;
     if (!okey) {  printf("Error in CALCULATE COMPLETION TIMES \n") ; 
                   exit(1) ; }


     schedule[cjob] = 1 ;        
     if (moda[cjob] > ctime) { ctime = moda[cjob] ; }
     st[cjob] = ctime ; 
     ctime = ctime + pt[cjob] ;
     compl[cjob] = ctime ;
     UPDATE(cjob) ; 
   }
}



 /* **********************************************************
   *                                                         *
    ***********************************************************/

BABLOWER(     long n ,
     long *lb1 ,
     long *opt )
{
  long i , j , k ;
  long relt , tait ; 
  long hj ;
  long minar , minqi , totdtime ; 
  long jobi ; 
  long preset[MAXJOBS] ; 

  for (i=1;i<=n;i++) preset[i] = set[i] ;  
  *lb1 = 0 ; 
  for (i=1;i<=n;i++)
    {
      jobi = i ;
      relt = md->rls[jobi] ;
      for (j=n;j>=1;j--)
        { 
          jobi = j ; 
          tait = md->tls[jobi] ; 
          for (k=1;k<=n;k++)
            { set[k] = 0 ; 
              if ((md->tls[k] >= tait) && ( md->rls[k] >= relt)) set[k] = 1 ;
            }
          CALCULATE_LOWER_BOUND(n,&hj,&minar,&minqi,&totdtime) ;
          if (hj > *lb1) { *lb1 = hj ; }
        }
    }
  for (i=1;i<=n;i++) set[i] = preset[i] ;  
}

/* ******************************************************************
  * This performs the logical tests to fix more edges in the graph.  *
   ****************************************************************** */

LOGICAL_TESTS(
     long n ,
     long icritjob ,
     long *opt )
{ 
  long i , j , k ; 
  long hj ; 
  long minar ; 
  long minqi ;
  long totdtime ;
  long okey ;
  long oldset[MAXJOBS] ; 



  
 FATHOM = 0 ; 
 for (i=1;i<=n;i++) { oldset[i] = set[i] ; set[i] = pset[i] ; }  
 CALCULATE_LOWER_BOUND(n,&hj,&minar,&minqi,&totdtime) ;

 for (i=1;i<=n;i++)   {
   if (i != icritjob) {
     if ((!set[i]) && (pt[i] >= (*opt - hj))){
       okey = 1;
       for (k=1;k<=n;k++) if ((set[k]) && (delay[i][k])) okey = 0 ; 
       if (((md->rls[i] + pt[i] + totdtime + minqi ) >= *opt)  &&
           (!okey))  { FATHOM = 1 ;   return ; }

       if (!okey)   {
         for (j=1;j<=n;j++){ 
           if ((set[j]) && (!delay[i][j])) { 
             fixarc(i,j,pt[i]) ; 
             transitive(n,i,j) ;
             affect[i] = 1 ;
             affect[j] = 1 ;
           }
         }
       }

            
       if (((md->rls[i] + pt[i] + totdtime + minqi ) >= *opt) && (okey)) { 
         /* put the job after all of the jobs in J */
           for (j=1;j<=n;j++)  { 
             if ((set[j]) && (!delay[j][i])) { 
               fixarc(j,i,pt[j]) ; 
               transitive(n,j,i) ;

               affect[i] = 1 ;
               affect[j] = 1 ;
             }
           }
         }
       else    {
         okey = 1;
         for (k=1;k<=n;k++) if ((set[k]) && (delay[k][i]))  okey = 0 ; 
         if (((minar + totdtime + pt[i] + md->tls[i]) >= *opt) && 
             (!okey)) { FATHOM = 1 ;  return ; }

         if (!okey) {
           for (j=1;j<=n;j++)   {
             if ((set[j]) && (!delay[j][i]))     { 
               fixarc(j,i,pt[j]) ; 
               transitive(n,j,i) ;
               affect[i] = 1 ;
               affect[j] = 1 ;
             }
           }
         }
                
         if (((minar + totdtime + pt[i] +md->tls[i]) >= *opt) && (okey)) { 
           for (j=1;j<=n;j++)   {
             if ((set[j]) && (!delay[i][j])) {
               fixarc(i,j,pt[i]) ; 
               transitive(n,i,j) ;
               affect[i] = 1 ;
               affect[j] = 1 ;
             }
           }
         }
       }
     }
   }
 }
  for (i=1;i<=n;i++) { set[i] = oldset[i] ; }

} 

/* **********************************************************
   ********************************************************** */

transitive(
     long n ,
     long k ,
     long l )
{
 long i1 , j ;
 long jsuci , cjob , sjob , jpredi ; 
 long peek , low , plus , more ; 

 cjob = k ; 
 sjob = l ;
 peek = tpredo[cjob] + 1 ;
 low  = tsucco[sjob] + 1 ; 
 
 for (j=1;j<=peek;j++)
   {
    jpredi = predo[cjob][j] ;
    more   = delay[jpredi][cjob] + pt[cjob] ; 
    if (j == peek)  { jpredi = k ; more = pt[cjob] ; }
    for (i1=1;i1<=low;i1++)
     {
      jsuci = succo[sjob][i1] ;
      if (i1 < low) plus = more + delay[sjob][jsuci] ; 
      if (i1 == low) { jsuci = l ; plus = more ; }
      if (!delay[jpredi][jsuci]) fixarc(jpredi,jsuci,pt[jpredi]) ;
      delay[jpredi][jsuci] = MAX((delay[jpredi][jsuci]),plus) ;
    }
  }
}

 /* **************************************************************
   * getaproblem(). Retrieve a problem from the branch and        *
   * bound tree.                                                  *
    **************************************************************  */

getaproblem(
     long n ,
     long *lb ,
     long *opt )
 { long i , j ;

   md    = root ; 
   *lb   = md->lbound ; 
   depth = md->depth ; 
   root  = md->next ;
   depth++ ;

   for (i=1;i<=n;i++)
     { tpredo[i] = 0 ; tsucco[i] = 0 ; 
       for (j=1;j<=n;j++) delay[i][j] = 0 ; 
     }

   for (i=1;i<=md->total;i++)
     fixarc(md->rules[0][i],md->rules[1][i],md->rules[2][i]) ;

   backwardStrong = 0 ;
   if (nodes == 1)   { 
       for (i=1;i<=n;i++)   affect[i] = 1 ; 
       topsort(n,1) ;
       preemption(n,lb,opt) ;
     }
 }


 /* **********************************************************
   * TOPOLOGICAL_ORDER() : orders the n according to their    *
   * topological ordering. We use a O(n^2) algorithm to do    *
   * that and we update forward the md->rls times of the n    *
   * and backwards the md->tlss of the n.  It is used when    *
   * we have precedence constraints and delays to give        *
   * better lower bounds.                                     *
    ********************************************************** */

topsort( 
     long n ,
     long okey )
{ long i , j , i1 , j1 ;
  long cjob  ;
  long jpredi ;
  long jsuci ;
  long llist ;
  long test_j ; 
  long mini ;
  long tot_proc ;

  long *scanned ;
  long *ttpredo  ;

  myn = (struct jobco *) malloc((n+10)*sizeof(struct jobco)) ; 
  if (myn == NULL) { printf("Memory problem ... \n") ; exit(1) ; }


  if (!okey) extr++ ;
  scanned = (long *) calloc(n+10,sizeof(long)) ; 
  if (scanned  == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
  ttpredo  = (long *) calloc(n+10,sizeof(long)) ; 
  if (ttpredo == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
  memcpy(tordering,zero,(n+2)*sizeof(long)) ;
  memcpy(ttpredo,tpredo,(n+2)*sizeof(long)) ;


  for (i=1;i<=n;i++) scanned[i] = i ;
  llist = 0 ; 
  while (llist < n)    { 
      for (i=llist+1;i<=n;i++) {
              j = scanned[i] ;
          if (!ttpredo[j])  {
              scanned[i] = scanned[llist+1]  ; 
              llist++ ; 
              tordering[llist] = j ; 
              for (j1=1;j1<=tsucco[j];j1++) (ttpredo[succo[j][j1]])-- ;
              i += n ;
            }
        }  
    }


  
  /* transitive closure */
  
  for (i=n-2;i>=1;i--) {
      cjob = tordering[i] ; 
      for (j=1;j<=tsucco[cjob];j++)
        {
          jpredi = succo[cjob][j] ;
          if (affect[jpredi])
            {
              for (i1=1;i1<=tsucco[jpredi];i1++)
                {
                  jsuci = succo[jpredi][i1] ;
                  if (!delay[cjob][jsuci]) fixarc(cjob,jsuci,pt[cjob]) ;
                  if ( delay[cjob][jsuci] < 
                      ( delay[cjob][jpredi] + delay[jpredi][jsuci] ) )
                    delay[cjob][jsuci] =  
                      delay[cjob][jpredi] + delay[jpredi][jsuci] ;
                }
            }
        }
    }

           /* Update the releases forwards */


  for (i=1;i<=n;i++) 
    { 
      test_j   = tordering[i] ; 
      if (affect[test_j]) 
        {
          if (!okey) goto n1 ; 
          for (j=1;j<=tpredo[test_j];j++)
            { myn[j].k = ((int) predo[test_j][j]) ; 
              myn[j].rel = ((int) md->rls[predo[test_j][j]]) ;
            }
          qsorta(tpredo[test_j]) ; 
          tot_proc = 0 ;
          for (j=tpredo[test_j];j>=1;j--)  {
              tot_proc += pt[myn[j].k] ; 
              mini = ((long) myn[j].rel) ; 
              md->rls[test_j] = MAX((md->rls[test_j]),(mini+tot_proc)) ;
            }
          
          n1 :
            cjob = tordering[i] ; 
          for (j=1;j<=tsucco[cjob];j++)
            {
              jsuci = succo[cjob][j] ;
              md->rls[jsuci] = 
                MAX((md->rls[cjob]+delay[cjob][jsuci]),(md->rls[jsuci])) ;
            }
        }
    }

           /* Update the tails backwards */


  
  for (i=n;i>=1;i--)    {
      test_j = tordering[i] ;
      if (affect[test_j]) {
          if (!okey) goto n2 ;
          for (j=1;j<=tsucco[test_j];j++) {
                  myn[j].k = ((int) succo[test_j][j]) ; 
                  myn[j].rel = ((int) md->tls[succo[test_j][j]]) ; 
            }
          if (tsucco[test_j]) { 

          qsorta(tsucco[test_j]) ; 
          }
          tot_proc = 0 ; 
          for (j=tsucco[test_j];j>=1;j--)   {
              tot_proc += pt[myn[j].k] ; 
              mini = ((long)  myn[j].rel) ; 
              md->tls[test_j]=MAX((md->tls[test_j]),(mini+tot_proc)) ;
            }
          
        n2:
          cjob = tordering[i] ; 
          for (j=1;j<=tpredo[cjob];j++)             {
              jsuci = predo[cjob][j] ; 
              if (md->tls[jsuci] < (md->tls[cjob]+delay[jsuci][cjob] 
                                    - pt[jsuci] +pt[cjob]))
                { md->tls[jsuci] = md->tls[cjob]+ delay[jsuci][cjob] 
                    - pt[jsuci] + pt[cjob] ; }
            }
        }
    }
  
  free(scanned)   ; 
  free(ttpredo)   ; 
  for (i=1;i<=n;i++) affect[i] = 0 ; 
  free(myn) ;
}  

/*
 *
 */


easytopsort(     long n ,     long okey )
{
  long i , j , i1 , j1 ;
  long cjob  ;
  long jpredi ;
  long jsuci ;
  long llist ;
  long test_j ; 
  long mini ;
  long tot_proc ;

  long *scanned ;
  long *ttpredo  ;

  myn = (struct jobco *) malloc((n+1)*sizeof(struct jobco)) ; 
  if (myn == NULL) { printf("Memory problem ... \n") ; exit(1) ; }

  if (!okey) extr++ ;
  scanned = (long *) calloc(n+1,sizeof(long)) ; 
  if (scanned  == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
  ttpredo  = (long *) calloc(n+1,sizeof(long)) ; 
  if (ttpredo  == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
  memcpy(tordering,zero,(n+1)*sizeof(long)) ;
  memcpy(ttpredo,tpredo,(n+1)*sizeof(long)) ;
 
  for (i=1;i<=n;i++) scanned[i] = i ;
  llist = 0 ; 
  while (llist < n) 
    { 
      for (i=llist+1;i<=n;i++) 
        { j = scanned[i] ;
          if (!ttpredo[j])
            {
              scanned[i] = scanned[llist+1]  ; 
              llist++ ; 
              tordering[llist] = j ; 
              for (j1=1;j1<=tsucco[j];j1++) (ttpredo[succo[j][j1]])-- ;
              i += n ;
            }
        }  
    }
  
  /* transitive closure */
  
  for (i=n-2;i>=1;i--)
    {
      cjob = tordering[i] ; 
      for (j=1;j<=tsucco[cjob];j++)
        {
          jpredi = succo[cjob][j] ;
          if (affect[jpredi])
            {
              for (i1=1;i1<=tsucco[jpredi];i1++)
                {
                  jsuci = succo[jpredi][i1] ;
                  if (!delay[cjob][jsuci]) fixarc(cjob,jsuci,pt[cjob]) ;
                  if ( delay[cjob][jsuci] < 
                      ( delay[cjob][jpredi] + delay[jpredi][jsuci] ) )
                    delay[cjob][jsuci] =  
                      delay[cjob][jpredi] + delay[jpredi][jsuci] ;
                }
            }
        }
    }

           /* Update the releases forwards */

  for (i=1;i<=n;i++) 
    { 
      test_j   = tordering[i] ; 
      if (affect[test_j]) 
        {
          if (!okey) goto n1 ; 
          for (j=1;j<=tpredo[test_j];j++)  {
                  myn[j].k = ((int)  predo[test_j][j]) ; 
                  myn[j].rel = ((int) release[predo[test_j][j]]) ;
            }
          qsorta(tpredo[test_j]) ; 
          tot_proc = 0 ;
          for (j=tpredo[test_j];j>=1;j--)
            {
              tot_proc += pt[myn[j].k] ; 
              mini = ((long) myn[j].rel) ; 
              release[test_j] = MAX((release[test_j]),(mini+tot_proc)) ;
            }
          
          n1 :
            cjob = tordering[i] ; 
          for (j=1;j<=tsucco[cjob];j++)
            {
              jsuci = succo[cjob][j] ;
              release[jsuci] = 
                MAX((release[cjob]+delay[cjob][jsuci]),(release[jsuci])) ;
            }
        }
    }

           /* Update the tails backwards */

  for (i=n;i>=1;i--) 
    {
      test_j = tordering[i] ;
      if (affect[test_j]) 
        {
          if (!okey) goto n2 ;
          for (j=1;j<=tsucco[test_j];j++) {
                  myn[j].k = ((int) succo[test_j][j]) ; 
                  myn[j].rel = ((int) tail[succo[test_j][j]]) ; 
            }
          qsorta(tsucco[test_j]) ; 
          tot_proc = 0 ; 
          for (j=tsucco[test_j];j>=1;j--)  {
              tot_proc += pt[myn[j].k] ; 
              mini = ((long)  myn[j].rel) ; 
              tail[test_j]=MAX((tail[test_j]),(mini+tot_proc)) ;
            }
          
        n2:
          cjob = tordering[i] ; 
          for (j=1;j<=tpredo[cjob];j++)
            {
              jsuci = predo[cjob][j] ; 
              if (tail[jsuci] < (tail[cjob]+delay[jsuci][cjob] 
                                    - pt[jsuci] +pt[cjob]))
                { tail[jsuci] = tail[cjob]+ delay[jsuci][cjob] 
                    - pt[jsuci] + pt[cjob] ; }
            }
        }
    }
  

  free(scanned)   ; 
  free(ttpredo)   ; 
  for (i=1;i<=n;i++) affect[i] = 0 ; 
  free(myn) ;
}  


 /* ***********************************************************
   * cleanmemory():  This procedures clears the memory.        *
    ************************************************************/


cleanmemory() 
{
  long i ;

  while (root != ((struct onema *)  NULL))
    {
      protos = root ;
      root = root->next ;
      free(protos->rls) ;
      free(protos->tls) ;
      for (i=0;i<3;i++) free(protos->rules[i]) ;
      free(protos) ;
    }

  root      = (struct onema *) NULL ;
  lpointer  = (struct onema *) NULL ;
  md        = (struct onema *) NULL ;
  ms        = (struct onema *) NULL ;
  protos    = (struct onema *) NULL ;
  npointer  = (struct onema *) NULL ;
}

 /* *****************************************************
   * schrage() : This routine gives the sequencing from  *
   * the Schrage algorithm.                              *
    ***************************************************** */


schrage(    long n ,
     long *icritical , 
     long *ifinal )
{ long i , j , tavail , icur , iqi , k ;
  long itime_dummy , minrel , isn ;
  long CHECK_PRED() ;

  memcpy(modby,zero,(n+1)*sizeof(long));
  memcpy(schedule,zero,(n+1)*sizeof(long));
  memcpy(previous,zero,(n+1)*sizeof(long));
  memcpy(moda,md->rls,(n+1)*sizeof(long));

  isn         = 0 ;
  *icritical  = 0 ;
  tavail      = 0 ;
  itime_dummy = 0 ;
  iqi         = ((long) RAND_MAXI) ;

  
  for (i=1;i<=n;i++) dpt[i] = i ; 
  while  ( isn <  n )   {
      itime_dummy = tavail ; 
      findminrel(n,isn,&minrel) ;      
      if (minrel > itime_dummy ) itime_dummy = minrel ;

      iqi = -2 ; 
      for (i=isn+1;i<=n;i++)
        { j = dpt[i] ; 
          if (!schedule[j])
            {
              if (moda[j] <= itime_dummy)
                { 
                  if (md->tls[j] >= iqi ) 
                    {
                      iqi  = md->tls[j] ;
                      icur = j ; 
                      k = i ;
                    }
                }
            }
        }

      dpt[k] = dpt[isn+1] ; 
      
/*
      if (!CHECK_PRED(icur)) printf("Error ... in schrage \n") ;
      if (schedule[icur]) { printf("Major Error  .... \n") ;  exit(1) ;  } 
*/
    
      schedulejob(icur,&isn,&tavail) ;
      UPDATE(icur) ; 
      
      tavail = tavail + pt[icur] ;
      if ( (tavail + md->tls[icur]) > *icritical ) 
        {
          *ifinal    = icur ;
          *icritical = tavail + md->tls[icur] ;
        }
    }
}


 /* ********************************************************
    *********************************************************/

findminrel(long n , long isn , long *minrel )
{
  long i , j ;

  *minrel = ((long)  RAND_MAXI) ; 
  for (i=isn+1;i<=n;i++)
    {
      j = dpt[i] ;
      if ( (!schedule[j]) && (moda[j] <= *minrel) ) *minrel = moda[j] ;
    }
}

 /* ********************************************************
   * preemption() : This routine gives the sequencing from  *
   * the Schrage algorithm.                                 *
    *********************************************************/


preemption(long n , long *lb , long *opt )
  {
    long i  , icritical , tavail , icur , my  ;
    long iqi , itime_dummy , ttime , iimp ; 
    long minrel , isn , itail , ipreem , sttime ;
    long previ[MAXJOBS] , who[MAXJOBS] , inow , iposi ;
    long lb1 ; 
    long reli , tali ; 
    long CHECK_PRED() ;

    myn = (struct jobco *) malloc((n+1)*sizeof(struct jobco)) ; 
    if (myn == NULL) { printf("Memory problem ... \n") ; exit(1) ; }

    for (i=1;i<=n;i++)     {
        myn[i].k   = ((int) i) ;
        myn[i].rel = ((int) md->rls[i]) ; 
        moda[i]    = md->rls[i] ; 
      }

    memcpy(schedule,zero,(n+1)*sizeof(long)) ;
    memcpy(dpt,pt,(n+1)*sizeof(long)) ;

    iposi       = 0 ; 
    isn         = 0 ; 
    icritical   = 0 ; 
    tavail      = 0 ;      
    itime_dummy = 0 ;
    icur        = 0 ;

    qsorta(n) ;

    while  ( isn <  n )  
      {
        itime_dummy = tavail ;
        ipreem = 0 ; 
        if (icur) { itail = md->tls[icur] ; }
        else      { itail = ((long) RAND_MAXI) ; }

        minrel = ((long) RAND_MAXI) ;            
        ttime  = tavail ;
        sttime = ttime ;  
        for (i=1;i<=n;i++) {
            my = ((long) myn[i].k) ;
            if (!schedule[my])
              { if (moda[my] <= minrel) minrel = moda[my] ; 
                
                if ((moda[my] < ttime) &&  (md->tls[my] > itail))
                  { ipreem = my ; 
                    ttime = moda[my] ;  }
                if (( moda[my] == ttime) && (ipreem))
                  { if (md->tls[my] > md->tls[ipreem]) { ipreem = my ; } }
  
                if (moda[my] > sttime) i = n + 2 ; 
              }
          }
        


        if (ipreem) 
          {
            schedule[icur] = 0 ; 
            isn-- ; 
            dpt[icur] = dpt[icur] - moda[ipreem] + st[icur] ; 
            tavail = moda[ipreem] ; 
            icur = ipreem ;
          } 
        else
          {
            if (minrel >= itime_dummy ) itime_dummy = minrel ;

            iqi = -2 ; 
            for (i=1;i<=n;i++)  { 
                my = ((long) myn[i].k) ;
                if (!schedule[my]) 
                  { if ((moda[my] <= itime_dummy) && (md->tls[my] >= iqi )) 
                      { iqi = md->tls[my] ; icur = my ; }
                  }
                if (moda[my] > itime_dummy) i = n + 2 ; 
              }
          }

/*      if (!CHECK_PRED(icur)) printf("Error \n") ; 
        if (schedule[icur]) { printf("Major Error  .... \n") ;  exit(1) ;  } */


        iposi++ ; 
        who[iposi] = icur ;
        if (tavail < moda[icur]) { 
            tavail = moda[icur] ; 
            previ[iposi] = 0 ; 
          }
        else { previ[iposi] = iposi-1 ; }
            
        
        st[icur] = tavail ; 
        tavail += dpt[icur]  ;
        schedule[icur] = 1 ; 
        isn++ ; 

        if ((tavail + md->tls[icur]) > icritical )
          {
            icritical = tavail + md->tls[icur] ;
            iimp = iposi ;
          }
      }

    for (i=1;i<=n;i++) pset[i] = 0 ;
    inow = iimp ;
    pset[who[inow]] = 1 ; 
    inow = previ[inow] ; 
    while (inow)    {
        if (md->tls[who[inow]] >= md->tls[who[iimp]])
          {
            pset[who[inow]] = 1 ;
            inow = previ[inow] ;
          }
        else { inow = 0 ; }
      }

   lb1 = 0 ;
   reli = ((long) RAND_MAXI) ; 
   tali = ((long) RAND_MAXI) ; 

   for (i=1;i<=n;i++)  {
      if (pset[i]) {
          if (md->rls[i] <= reli) reli = md->rls[i] ;
          if (md->tls[i] <= tali) tali = md->tls[i] ;
          lb1 = lb1 + pt[i] ;
        }
    }
 
   lb1 = lb1 + tali + reli ; 

   if (lb1 != icritical) {  printf("Error in Lower Bound \n") ; exit(1) ; }

    if (icritical > *lb) { *lb = icritical ; }

/*

    BABLOWER(n,&lb1,opt) ;
    if (lb1 != *lb) printf("Error in lower bound \n") ;  

*/

    free(myn) ; 
}



 /* ********************************************************
   * schedulejob():                                         *
    ******************************************************** */

schedulejob(
     long icur ,
     long *isn ,
     long *tavail )
{
 schedule[icur] = 1 ; 
 (*isn)++ ;           
 thesis[icur] = *isn ;
 iorder[*isn] = icur ;     

 if (*isn == 1)                 
     { *tavail = moda[icur] ;
       previous[icur] = 0 ; 
     }
 else
     {
      if ( *tavail < moda[icur] )
       { *tavail = moda[icur] ;
         if ( moda[icur] > md->rls[icur])  { previous[icur] = modby[icur] ; }
         else { previous[icur]  = 0 ; }
       }  
      else { previous[icur] = iorder[*isn-1] ; }
     }
 st[icur] = *tavail ;
}




 /* ********************************************************
   * schedulejob():                                         *
    ******************************************************** */


randomschedulejob(long icur , long *isn ,long *tavail )
{
 schedule[icur] = 1 ; 
 (*isn)++ ;           
 thesis[icur] = *isn ;
 iorder[*isn] = icur ;     

 if (*isn == 1)   {
   *tavail = moda[icur] ;
   previous[icur] = 0 ; 
 }
 else  {
   if ( *tavail < moda[icur] ){
     *tavail = moda[icur] ;
     if ( moda[icur] > release[icur])  { previous[icur] = modby[icur] ; }
     else { previous[icur]  = 0 ; }
   }  
   else { previous[icur] = iorder[*isn-1] ; }
 }
 st[icur] = *tavail ;
}



 /* *******************************************************
   *  CHECK_PRED(test_job) : Checks if all the             *
   *  predecessors of test_job  have been scheduled        *
    ******************************************************* */

long CHECK_PRED(long test_job )
{ long i ;

 for (i=1;i<=tpredo[test_job];i++)
 {
   if (!schedule[predo[test_job][i]]) return(0) ;
 }
 return(1) ;
}


  
/*  ************************************************************ 
   * FIND_FIRST_SEGMENT() : find the first segment of the       *
   * the critical path. O->i(1)->i(2)->...->i(k)--->i(l)->....  * 
   * Where i(k)--->i(l) is a precedence arc.                    *
    ************************************************************ */

FIND_PRECEDENCE_ARCS(long ifinal , long *totparcs )
{
 long ifin ; 

 *totparcs = 0 ; 
 ifin      = ifinal ; 
 while (ifin) 
   {
    if (previous[ifin]) 
     { if (previous[ifin] == modby[ifin]) 
          { *totparcs = *totparcs + 1 ;
            parcs[*totparcs] = previous[ifin] ; } }
    ifin = previous[ifin] ; 
   }
}


 /* **********************************************************
   * UPDATE                                                   *
    ***********************************************************/

UPDATE(long icur )
{
 long i ;
 long sjob ;

 for (i=1;i<=tsucco[icur];i++)
   { 
     sjob = succo[icur][i] ; 
     if ((moda[sjob] < ( st[icur] + delay[icur][sjob] ))
         && (delay[icur][sjob] > pt[icur] ) ) modby[sjob]  = icur ; 

     if (moda[sjob] < ( st[icur] + delay[icur][sjob]) ) 
       {  moda[sjob] = st[icur] + delay[icur][sjob] ; }
  }
}

 /* ***********************************************************
   * fixarc(i,j,k)                                             *
    ************************************************************/

fixarc(long i , long j , long k )
{
 delay[i][j] = k ;
 (tpredo[j])++;
 predo[j][tpredo[j]] = i ;
 (tsucco[i])++ ;
 succo[i][tsucco[i]] = j ;
}



/* *************************************************************
  * test_branching() : Finds the critical path, critical        *
   **************************************************************/

test_branching(long n , long lb , long *opt )
{
/*   printf("Forward has weak branching .. \n") ; */
  backwardStrong = 0 ; 
  went_weak_backward = 0 ; 
  storeold(n) ;
  test_inverse = 1 ;
  inverse(n) ; 
  branching(n,lb,opt) ;
/*  if (backwardStrong)  printf("Inverse has Strong branching  \n") ;
  if (went_weak_backward) printf("Inverse has weak Branching branching  \n") ;
  if ((!backwardStrong) && 
  (!went_weak_backward)) printf("Inverse is optimal \n") ;  */
  if ((!backwardStrong) && (went_weak_backward)) restoreold(n) ; 
  test_inverse = 0 ; 
}

/* *********************************************************************
   ********************************************************************* */

inverse(     long n )
{
 long i , j ;
 long temprel , temptpredo ;  
 long temppred[MAXJOBS] ; 

 for (i=1;i<=n;i++)
   {
    /* inverser the tails with the releases */
    temprel = md->rls[i] ;
    md->rls[i] = md->tls[i] ;
    md->tls[i] = temprel ;
    temptpredo = tpredo[i] ;
    for (j=1;j<=tpredo[i];j++) temppred[j] = predo[i][j]  ;
    for (j=1;j<=tsucco[i];j++) predo[i][j] = succo[i][j] ;
    for (j=1;j<=tpredo[i];j++) succo[i][j] = temppred[j] ;
    tpredo[i] = tsucco[i] ;
    tsucco[i] = temptpredo ; 
   }

 for (i=1;i<=n;i++)
   for (j=1;j<=n;j++)
     { inverse_delay[j][i] = 0 ;
       if (delay[i][j]) inverse_delay[j][i] = delay[i][j] + pt[j] - pt[i] ;
     }

 for (i=1;i<=n;i++)
   for (j=1;j<=n;j++) delay[i][j] = inverse_delay[i][j] ; 


}

/* *************************************************************
  * branching() : Finds the critical path, critical             *
  * n, modified delayed n.                                      *
  * This routine is used in the One machine scheduling with     *
  * delayed precedence constraints.                             *
   **************************************************************/

branching(     long n ,
     long lb ,
     long *opt )
{ 
 
  long icritjob , pred_arc ;
  long icritical , ifinal , doit  ;


 doit = 1 ;   
 while (doit != 0) 
 { 
  if (doit == 1)
    {
     schrage(n,&icritical,&ifinal) ;
     MODIFY(opt,icritical,n) ;
   }


  postprocessing(n,ifinal,icritical) ;  
  doit = 0 ; 
  icritjob = 0 ; 
  pred_arc = 0 ;

  FIND_CRITICAL_JOB(n,ifinal,&icritjob,&pred_arc) ; 
  if (icritjob) { WITH_CRITICAL_JOB(n,ifinal,icritjob,lb,opt) ;   }
  else { THERE_IS_NO_CRITICAL_JOB(n,&ifinal,pred_arc,lb,opt,&doit) ; } 
 }

}

/* **********************************************************
  * WITH_CRITICAL_JOB(icritjob) : If there exists a critical *
  * job then. There are two different cases:                 *
  * a. All the n in the critical set have md->rls time       *
  *    greater than or equal to the starting time of the     *
  *    critical job.  In this case we create two new nodes   *
  *    in the B&B tree.                                      *
  * b. There exists a job i with md->rls time less than the  *
  *    starting time of the critical job c. Then we create   *
  *    two new nodes in the branch and bound tree. In the    *
  *    one i->c is imposed in the other c->i is imposed.     *
   ***********************************************************/

WITH_CRITICAL_JOB(
     long n ,
     long ifinal ,
     long icritjob ,
     long lb ,
     long *opt )
{
  long i ; 
   
  long iconflict ;
  long releao , tailo ;
  
  iconflict = 0 ; 
  IS_J_UNMODIFIED(ifinal,icritjob,&iconflict) ; 
  if (!iconflict)
    {

            CRITICAL_JOB_CALCULATIONS(n,icritjob,ifinal,&releao,&tailo) ; 
      for (i=1;i<=n;i++) pset[i] = set[i] ;
      LOGICAL_TESTS(n,icritjob,opt) ;  

      if (test_inverse) backwardStrong = 1 ; 
      Strong++ ; 
      storeold(n) ;
      for (i=1;i<=n;i++) if (set[i]) { Edges = Edges + 1.0 ; }
      Branches = Branches + 1.0 ;

      createafterJ(n,icritjob,releao,lb,opt) ;

      restoreold(n) ;

      createbeforeJ(n,icritjob,tailo,lb,opt) ;

    }                                             
  else
    { WEAK_BRANCHING(n,ifinal,icritjob,lb,opt,0) ;  } 

}


/* **********************************************************
  *                                                          *
   ***********************************************************/

storeold(long n)
{
 long i , j ;
 for (i=1;i<=n;i++)
   {
    temp_rls[i] = md->rls[i] ;
    temp_tls[i] = md->tls[i] ; 
    temp_tpredo[i] = tpredo[i] ;
    temp_tsucco[i] = tsucco[i] ;
    temp_affect[i] = affect[i] ;
    for (j=1;j<=tpredo[i];j++) temp_predo[i][j] = predo[i][j] ;    
    for (j=1;j<=tsucco[i];j++) temp_succo[i][j] = succo[i][j] ;    
    for (j=1;j<=n;j++) temp_delay[i][j] = delay[i][j] ;
  }
}

/* **********************************************************
  *                                                          *
   ***********************************************************/

restoreold(long n )
{
 long i , j ;
 for (i=1;i<=n;i++)
   {
    md->rls[i] = temp_rls[i] ;
    md->tls[i] = temp_tls[i] ; 
    tpredo[i] = temp_tpredo[i] ;
    tsucco[i] = temp_tsucco[i] ;
    affect[i] = temp_affect[i] ;
    for (j=1;j<=tpredo[i];j++) predo[i][j] = temp_predo[i][j] ;    
    for (j=1;j<=tsucco[i];j++) succo[i][j] = temp_succo[i][j] ;    
    for (j=1;j<=n;j++)  delay[i][j] = temp_delay[i][j] ; 
   }
}

/* **********************************************************
  *                                                          *
   ***********************************************************/

THERE_IS_NO_CRITICAL_JOB(
     long n ,
     long *ifinal ,
     long pred_arc ,
     long lb ,
     long *opt ,
     long *doit )
{
  long ifirst , ifin ; 
 long min_rel , ipred ;  
 long tottail ; 
 long FIND_MINIMUM_RELEASE_TIME() ;

 if (!pred_arc)  {  
   FIND_MINIMUM_RELEASE_TIME(ifinal,&ifirst,&min_rel) ; /* There are no */ 
   ifin = *ifinal ;                                /* precedence arcs in */
   while (ifin)                                    /* the P and also there */
    { if (md->rls[ifin] < min_rel)                 /* no critical n. */
     {                                             /* We check only for */
      WEAK_BRANCHING(n,ifin,ifirst,lb,opt,1) ;     /* n we md->rls time */
                                               /* smaller than */
      ifin = 0 ;                               /* the md->rls of i1*/
     }
     else { ifin = previous[ifin] ; } 
     }
   }
else
 {
  ifin = *ifinal ;
  ipred = pred_arc ; 
  min_rel = st[ipred] ;      
  ifirst = 0 ; 
  tottail = md->tls[*ifinal] ; 
  while (ifin != ipred) 
    {
     tottail = tottail + pt[ifin] ; 
     if ((md->rls[ifin] < min_rel) && (!delay[ipred][ifin]))
       { ifirst = ifin ; }
     ifin = previous[ifin] ; 
   }

  *doit = 0 ; 
  if (ifirst) { WEAK_BRANCHING(n,ifirst,ipred,lb,opt,2) ; }
  else
    { *doit = 2 ;
      ifin = *ifinal ;
      while (ifin != ipred) 
        {
         if (!delay[ipred][ifin])
            {
             fixarc(ipred,ifin,pt[ipred]) ;
             affect[ipred] = 1 ;
             affect[ifin]  = 1 ;
           }
         ifin = previous[ifin] ; 
        }
      *ifinal = previous[ipred] ;     
      if (md->tls[ipred] < tottail) 
        {
         md->tls[ipred] = tottail ;
         affect[ipred] = 1 ; 
         *doit = 1 ; 
        }
 md->tls[*ifinal] = tottail + delay[*ifinal][ipred] - pt[*ifinal] + pt[ipred] ;
 affect[*ifinal] = 1 ;     
      topsort(n,0) ; 
    }
 }
}

/* *************************************************************
   ************************************************************* */

WEAK_BRANCHING(
     long n ,
     long a ,
     long b ,
     long lb ,
     long *opt ,
     long typ )
{
        if (test_inverse) { went_weak_backward = 1 ; return ; }
  if (!test_inverse) test_branching(n,lb,opt) ;
  if ((backwardStrong) || (!went_weak_backward)) return ;


        
  Weak++ ;
  if (typ == 0) Critic++ ;
  if (typ == 1) Rel++ ;
  if (typ == 2) Elimin++ ;
 

  storeold(n) ;
  createprecedence(n,a,b,lb,opt,1) ;
  restoreold(n) ;
  createprecedence(n,b,a,lb,opt,0) ;
}

/* *************************************************************
   ************************************************************* */

STATISTICS(     long ifinal )
{ long ifin  ; 
  long parci , cn ;
  long qjp  ; 
  long tjobis ;


/*  printf("------------------------------------ \n") ;  */
  ifin = ifinal ;
  qjp  = md->tls[ifinal] ;

  cn     = 0 ;
  parci  = 0 ;
  tjobis = 0 ; 
  while ( ifin != 0) 
    {  
      tjobis++ ; 
      if (md->tls[ifin] < qjp) { cn++ ; /* printf("*") ; */ }
      if ( previous[ifin]) 
        { 
          if (previous[ifin] == modby[ifin] ) 
            { parci++ ; qjp = 0 ; /*  printf("<--(%ld)",modby[ifin]) ; */ }
        }
      ifin = previous[ifin] ; 
/*      printf("\n") ; */
    }

  visited++ ;
  total_cjobs = total_cjobs + (double) tjobis ;
  total_parci = total_parci + (double) parci ; 
  
}




/* ********************************************************
  *                                                        *
   ******************************************************** */

showpath(long ifinal )
{
 long ifin ; 

 ifin =  ifinal ;
 while (ifin) 
   {
    printf("%ld-",ifin) ;
if (previous[ifin]) { if (previous[ifin] == modby[ifin] ) {printf("-");} }
   ifin = previous[ifin] ; 
  }

 printf("\n") ; 
}

/* **********************************************************
  * postprocessing()                                         *
   ********************************************************** */

postprocessing(
     long n ,
     long origin ,
     long icritical )
{
 long ifin , tir ; 
 long prop , strongarc , actual ; 
 long ilast , relfirst ;

 START:
 ifin = origin ;
 strongarc = 0 ; 
 actual = 0 ;

 while (ifin)
  {
   if (previous[ifin])
    {
     if (previous[ifin] == modby[ifin]) 
        { actual = ifin ; 
          strongarc = previous[ifin] ;
        }
     }
   ifin = previous[ifin] ;
   }

 if (strongarc > 0)
   {
    ifin = previous[strongarc] ; 
    if (!ifin) printf("Error in the post ... \n") ; 

    prop = 1 ; 
    tir  = icritical - st[strongarc] - pt[strongarc] ; 
    while (ifin)
    {
     if ((!delay[ifin][strongarc])  && (md->tls[ifin] < tir)) prop = 0 ; 
     ilast = ifin ; 
     ifin = previous[ifin] ; 
    }
    relfirst = md->rls[ilast] ;  
    if (md->rls[ilast] != st[ilast]) printf("Error ilast \n") ;
    ifin = strongarc ; 
    while ((ifin) && (prop == 1))
     {
      if (md->rls[ifin] < relfirst) prop = 0 ; 
      ifin = previous[ifin] ;  
     }
   
    if (prop == 1) 
     {
      md->rls[actual]    = st[actual] ; 
      previous[actual]   = 0 ; 
      md->rls[strongarc] = st[strongarc] ; 
      ifin               = previous[strongarc] ; 
      while (ifin)
        { if (!delay[ifin][strongarc])
              {
               fixarc(ifin,strongarc,pt[ifin]) ; 
               affect[ifin] = 1 ;
               affect[strongarc] = 1 ; 
             }
          ifin = previous[ifin] ; 
        }
      topsort(n,0) ;
      goto START ; 
     }
 }
}

/* **********************************************************
  * CRITICAL_JOB_CALCULATIONS() :                            *
   ********************************************************** */

CRITICAL_JOB_CALCULATIONS(long n ,
                          long icritjob ,
                          long ifinal ,
                          long *releao ,
                          long *tailo )
{
 long qjp ; 
 long hj ; 
 long minar , minqi , totdtime ;

 qjp = md->tls[ifinal] ;
 CALCULATE_LOWER_BOUND(n,&hj,&minar,&minqi,&totdtime) ;
 if ( (minar+totdtime) > md->rls[icritjob] )
     { *releao = minar + totdtime ; }
 else
     { *releao = md->rls[icritjob] ;  }

 if ( ( qjp + totdtime ) > md->tls[icritjob] )
     { *tailo = qjp + totdtime ; }
 else
     { *tailo = md->tls[icritjob] ; }
}


/* **********************************************************
  * IS_J_UNMODIFIED():                                       *
   ********************************************************** */

IS_J_UNMODIFIED(long ifinal ,
                long itest ,
                long *iconflict )
{
        long ifin ;

  ifin      = ifinal ;
  *iconflict = 0 ;
  while (ifin != itest) 
    {
     if (md->rls[ifin] < st[itest])  { *iconflict = ifin ; }
     ifin = previous[ifin] ; 
    }
}


/* *********************************************************
  *                                                         * 
   ********************************************************* */

long FIND_MINIMUM_RELEASE_TIME(
                          long *ifinal ,
                          long *ifirst ,
                          long *min_rel )

{ long ifin ;

  *ifirst  = 0 ;
  *min_rel = ((long) RAND_MAXI) ;
  ifin     = *ifinal ;
  while (ifin)
    { 
     *min_rel = md->rls[ifin] ; 
     *ifirst = ifin ; 
     if (previous[ifin]) { if (previous[ifin] == modby[ifin]) {ifin = 0;}}
     if (ifin)  {  ifin = previous[ifin] ; }
   }
}


/* **********************************************************
  * FIND_CRITICAL_JOB()                                      *
   ********************************************************** */

FIND_CRITICAL_JOB(long n ,
                  long ifinal ,
                  long *icritjob ,
                  long *pred_arc ) 
{ long ifin  ; 
  long iw ;
  long qjp  ; 

  *icritjob = 0 ;     
  ifin = ifinal ;
  qjp = md->tls[ifinal] ;
  for (iw=1;iw<=n;iw++)   { set[iw] = 0 ;  }

  while ((ifin) && (!(*icritjob)))
    { if (md->tls[ifin] < qjp)  {  *icritjob = ifin ; } 
      else
         { set[ifin] = 1 ; 
           if (previous[ifin])
            {
             if (previous[ifin] == modby[ifin] )
              { *pred_arc = ifin ; 
                ifin=0; 
              }
            }
            if (ifin) {  ifin = previous[ifin] ; }
         }
    }
}

/* *******************************************************
  *  CALCULATE_LOWER_BOUND() : Calculates the lower       *
  *  bound for a set J                                    *
  *  of n (Used for the One Machine Scheduling Problem)   *
   ********************************************************/

CALCULATE_LOWER_BOUND(long n ,
     long *hj ,
     long *minar ,
     long *minqi ,
     long *totdtime )

{
 long i ; 

 *totdtime = 0 ;
 *minar = ((long) RAND_MAXI) ; 
 *minqi = ((long) RAND_MAXI) ; 
 *hj   = 0 ; 

 for (i=1;i<=n;i++) {
   if (set[i])  {
     *totdtime = *totdtime + pt[i] ;
     if ( md->rls[i] < *minar )  *minar = md->rls[i] ; 
     if ( md->tls[i] < *minqi )  *minqi = md->tls[i] ; 
    }
 }
 *hj = *minar + *totdtime + *minqi ;
}

 /* *********************************************************
   * fixpointer()                                            *
    ********************************************************* */

fixpointer()
 {
  protos->next  = npointer ;
  if (lpointer == ((struct onema *) NULL))
    { lpointer = protos ; root = protos ; }
   else
    { lpointer->next = protos ; }
 }


/* ***********************************************************
  * PRIORITY():                                               *
   *********************************************************** */

PRIORITY(
     long node_bound ,
     long tp )
{
  long value ;
  long st1 ;

   st1 = 0 ;
   ms = root ; 
   lpointer  = (struct onema *)  NULL ;
   npointer  = (struct onema *)  NULL ;


   while ( ( ms != ((struct onema *)  NULL)) && (!st1))
    {
     value = ms->lbound ;
     if (!tp)
       {
        if (node_bound < value)
         { npointer = ms ; 
           st1  = 1 ;   
         }
        else
         {
          lpointer = ms ;
          ms = ms->next ; 
         }
       }
     else
      {
        if (node_bound <=  value)  /* change it back to <= */
         { npointer = ms ; 
           st1  = 1 ;  
         }
        else
         {
          lpointer = ms  ; 
          ms = ms->next ;
         }
      }  
   }
}

/* ***************************************************************
  * createpointer():                                              *
   *************************************************************** */

createpointer(long n ,
              long k )
 {  
  long i ;
  ms = (struct onema *) calloc(1,sizeof(struct onema)) ;
  if (ms == NULL) { printf("Memory problem ... \n") ; exit(1) ; }

  ms->rls = (long *) calloc(n+1,sizeof(long)) ; 
  if (ms->rls  == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
  ms->tls = (long *) calloc(n+1,sizeof(long)) ; 
  if (ms->tls  == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
  for (i=0;i<3;i++)
{  ms->rules[i] = (long *) calloc(k+2,sizeof(long)) ; 
  if (ms->rules[i]  == NULL) { printf("Memory problem ... \n") ; exit(1) ; }
 }
}

/* ***************************************************************
   ***************************************************************  */

STORE_FIRST_PROBLEM(long n , long lb )
{
 long i , k ;

 k = 0 ; 
 for (i=1;i<=n;i++) k += tpredo[i] ; 
 createpointer(n,k) ;
 storefirst(n,lb,k) ; 
 fixpointer() ;
}

 /* *********************************************************
   * createafterJ(): This procedure creates a new node       *
   * in the branch and bound tree where the critical job     *
   * comes after all the n of the critical set J.            *
    ********************************************************* */

createafterJ(
     long n ,
     long icritjob ,
     long releao ,
     long lb ,
     long *opt)
{
    long  i, node_bound ; 

  md->rls[icritjob] = MAX((md->rls[icritjob]),releao) ;
  node_bound = lb ;

  for (i=1;i<=n;i++)  {
    if (set[i])    {
      affect[i] = 1 ;
      if (delay [ icritjob ] [ i ] )  return ; 
      if (!delay[i][icritjob])  { fixarc(i,icritjob,pt[i]) ;  }
      else { printf("Error in createafterJ \n") ;  }
    }
   }

  affect[icritjob] = 1; 


  topsort(n,1) ;

  preemption(n,&node_bound,opt) ;

  if (node_bound < *opt)
  { 
   nodes++ ;
   PRIORITY(node_bound,1) ;
   storeproblem(n,node_bound) ;
   fixpointer() ; 
 }

}

/* *************************************************************
  * createbeforeJ(): Stores the problem in the branch and     *
  * bound tree where the critical job comes before all the n    *
  * of the critical set J.                                      *
   ************************************************************* */

createbeforeJ(
     long n ,
     long icritjob ,
     long tailo ,
     long lb ,
     long *opt )
{ long i  , node_bound ;

   md->tls[icritjob] = MAX((md->tls[icritjob]),tailo) ;
   node_bound = lb ;

   for (i=1;i<=n;i++)  {
       if (set[i]) {
           affect[i] = 1 ;
           if (delay [ i ] [ icritjob ] )  return ; 
           if (!delay[icritjob][i]) { fixarc(icritjob,i,pt[icritjob]) ; }
           else { printf("Error in createbeforeJ\n") ;  }
         }
     }
   affect[icritjob] = 1; 
   
   topsort(n,1) ;
   preemption(n,&node_bound,opt) ;

   if (node_bound < *opt)
     { 
       nodes++ ;
       PRIORITY(node_bound,0) ;
       storeproblem(n,node_bound) ;
       fixpointer() ; 
     }
 }


/* ***************************************************************
  * createprecedence(ibefore,iafter)                             *
   *************************************************************** */

createprecedence(
     long n ,
     long ibefore ,
     long iafter ,
     long lb ,
     long *opt ,
     long type_ord )
{ long node_bound  ;

  if (delay[ibefore][iafter]) printf("Problem \n") ;

  node_bound = lb ;
  if (!delay[ibefore][iafter]) fixarc(ibefore,iafter,pt[ibefore]) ;
  affect[ibefore] = 1 ;
  affect[iafter]  = 1 ;
  topsort(n,1) ;
  preemption(n,&node_bound,opt) ;
  

  if (node_bound < *opt)
    {
      nodes++ ; 
      if (type_ord) { PRIORITY(node_bound,1) ;  }
      else          { PRIORITY(node_bound,0) ;  } 
      storeproblem(n,node_bound) ;
      fixpointer() ; 
    }
}

 /* ********************************************************
   * Store the lower bound associated with the node of the  *
   * branch and bound tree, and also the depth.             *
    ******************************************************** */

storeproblem(     long n ,    long node_bound )
{
  long i , j , w , k ;

  k = 0 ; for (i=1;i<=n;i++) k += tpredo[i] ; 
  createpointer(n,k) ; 
  ms->status = md->status ;
  if (test_inverse) 
    { if (md->status == 1) { ms->status = 0 ; }
      else { ms->status = 1 ; }
    }

  ms->lbound = node_bound ;
  ms->depth  = depth ;
  ms->total  = k ; 
  w = 0 ; 
  for (i=1;i<=n;i++)
    {
      ms->rls[i] = md->rls[i] ; 
      ms->tls[i] = md->tls[i] ; 
      for (j=1;j<=tpredo[i];j++)
        { w++ ; conjunction(w,predo[i][j],i,delay[predo[i][j]][i]) ; }
    }
  protos = ms ; 
}

/* ***********************************************************
   *********************************************************** */

storefirst(
     long n ,
     long lb ,
     long k )
{
  long i , j , w ; 
  
        
  ms->status = 1 ;
  ms->lbound = lb ;
  ms->depth  = depth ;
  ms->total  = k ;
  w = 0 ;
  for (i=1;i<=n;i++)
    {
      ms->rls[i] = release[i] ;
      ms->tls[i] = tail[i] ;
      for (j=1;j<=tpredo[i];j++)
        { w++ ; conjunction(w,predo[i][j],i,delay[predo[i][j]][i]) ; }
    }
  protos = ms ; 
}

/* *********************************************************
  * Stores a conjunctive arc in the branch and bound tree   *
   ********************************************************* */

conjunction(
     long k , 
     long i ,
     long j ,
     long del )
{
  ms->rules[0][k] = i ;
  ms->rules[1][k] = j ; 
  ms->rules[2][k] = del ; 
}

 /* ********************************************************
   * MODIFY.H : contains procedures for  the One            *
   * Machine Scheduling problem with Delays and             * 
   * the General One Machine Problem.                       *
    ******************************************************** */

MODIFY(
     long *opt ,
     long icritical ,
     long n )
{ 
  long i , kk , stat  ; 
  
  if (icritical < *opt)
    {
      *opt = icritical ; 
      idep = depth ;
      stat = 1 ;
      kk = 0 ;
      if ((md->status) && (test_inverse)) stat = 0 ;
      if ((md->status == 0) && (test_inverse)) stat = 1 ;
      if ((md->status == 0) && (!test_inverse)) stat = 0 ; 
      if (!stat) for (i=n;i>=1;i--) { kk++ ; order[kk] = iorder[i] ; }  
      if (stat) for (i=1;i<=n;i++) order[i] = iorder[i] ;  
    }
}

/* *****************************************************************
   *****************************************************************  */

PRINT_PROBLEM(
     long n ,
     long j1 )
{
  long  j2 , j3 ;
  long total ; 
  
  total = 0 ; 
  for (j2=1;j2<=n;j2++)
   for (j3=1;j3<=n;j3++) if (delay[j2][j3]) total++ ; 

  printf("%ld %ld\n",n,j1) ; 
  for (j2=1;j2<=n;j2++)
    printf("%ld %ld %ld \n",release[j2],tail[j2],pt[j2]) ;

  printf("%ld\n",total) ; 
  for (j2=1;j2<=n;j2++)
    for (j3=1;j3<=n;j3++) 
      if (delay[j2][j3]) printf("%ld %ld %ld \n",j2,j3,delay[j2][j3]) ;  
}



/* *****************************************************************
   *****************************************************************  */

GET_PROBLEM( long *n )
{
  long i , j , del ;
  long  j1 , j2 , j3 ;
  long total ; 
  
  scanf("%ld %ld",n,&j1) ; 
  for (j2=1;j2<=*n;j2++)
    scanf("%ld %ld %ld",&release[j2],&tail[j2],&pt[j2]) ;

  scanf("%ld\n",&total) ; 
  for (j3=1;j3<=total;j3++) 
    {
      scanf("%ld %ld %ld",&i,&j,&del) ; 
      fixarc(i,j,del) ;
    }
}



/* *************************************************************
   ************************************************************* */


STORE_RANDOM_PROBLEM( long n )
{
  long i , j ; 
  
  for (i=1;i<=n;i++)
    {
      keep_rls[i] = release[i] ; 
      keep_tls[i] = tail[i] ;
      keep_pt[i]  = pt[i] ; 
      old_tpredo[i] = tpredo[i] ;
      old_tsucco[i] = tsucco[i] ;
      for (j=1;j<=tpredo[i];j++) old_predo[i][j] = predo[i][j] ;    
      for (j=1;j<=tsucco[i];j++) old_succo[i][j] = succo[i][j] ;    
      for (j=1;j<=n;j++) old_delay[i][j] = delay[i][j] ;
    }
}



/* **************************************************************
   ************************************************************** */


RESTORE_RANDOM_PROBLEM(    long n )
{
  long i , j ;
  
  for (i=1;i<=n;i++)
    {
      release[i] = keep_rls[i] ; 
      tail[i]    = keep_tls[i] ;
      pt[i]      = keep_pt[i] ; 

      tpredo[i] = old_tpredo[i] ;
      tsucco[i] = old_tsucco[i] ;
      for (j=1;j<=tpredo[i];j++) predo[i][j] = old_predo[i][j] ;    
      for (j=1;j<=tsucco[i];j++) succo[i][j] = old_succo[i][j] ;    
      for (j=1;j<=n;j++) delay[i][j] = old_delay[i][j] ;
    }
}

/* ---------------------------------------------------------
  | Heuristics for the one machine scheduling               |
  | problem with setup_onemachine times                                |
   ---------------------------------------------------------  */
                                       /****/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


 


//#include "timern.h" 

struct job
   { 
    long index ; 
    struct job *next ;
    struct job *back ;
   } ;

struct job *ele ;         
struct job *temp ;         
struct job *tempos ;         
struct job *rooti ;         
struct job *point[MAXJOBS] ;         



long lower[MAXJOBS] ;
long upper[MAXJOBS] ;
 
long order2[MAXJOBS] ;					/****/
long wdwBegin[MAXJOBS] ;				/****/
long wdwEnd[MAXJOBS] ;					/****/
    
long crit[MAXJOBS]  ; 
long BEST[MAXJOBS]  ; 
double VALUE[MAXJOBS] ; 
double LTH1 , LTH2 , INS ;

long UB ,UB_GLOBAL ; 
long ifinal , pmax , smax ;
long best_solution_setup ; 
long makespan ; 
long printi ;
long firstp , lastp ; 


long MY_SEED , YESI ;


/*
double random_number()
{
  double l ; 

  MY_SEED = MY_SEED * 1103515245 + 12345 ; 
  if (MY_SEED >= 2147483648) { 
    MY_SEED = (MY_SEED % 2147483648) - 2147483648 ; 
  }
  if (MY_SEED < 0) { 
    if ((-MY_SEED) >= 2147483648) { 
    MY_SEED = 2147483648 - ((-MY_SEED) % 2147483648) ;
    }}
  l =((double)  MY_SEED) / 2147483648.0 ; 
  if (l < 0.0) l = 1.0 + l ; 
  return(l) ; 

}
*/

long order_temp[MAXJOBS] ; 

//#include "bound.h"

onemachinesetup(long n, long *optimal_makespan)
{
 long   j ,  j1  ;
 long     k  ; 
 long jobs , seed ;
 
 long problems ; 
  
 
 
 

 char guarantee, tightened, tightretval, moveon;	/****/
 long tempcost, perceivedmakespan;			/****/
 long UB_improvement;
 long dynK, init_makespan_val;	       			/****/
 long z1, z2, z3;

 seed     = 1 ; 
 problems = 1 ;  
 jobs = n ; 
 YESI     = 0 ; 

 printi = 0 ;
 k = 0 ;  
 if (printi) printf("Seed = %ld \n",seed) ; 
 pmax = 50; 
 smax = 50 ;


    k = 0 ; 
       
          UB_GLOBAL = ((long) RAND_MAXI) ; 
          MY_SEED = seed * jobs * k ; 
          //        STARTTIME(1) ; 
        /* GENERATE_RANDOM_PROBLEM(jobs,k) ; */
		
		/*  
		  for (j1=1;j1<=jobs;j1++) { 
			  printf("job: %ld, release = %ld, processing t = %ld, tail = %ld \n",
				  j1, release[j1], pt[j1],tail[j1]) ; 
		  }
		  for (j1=0;j1<=jobs;j1++) { 
			  for (j2=0;j2<=jobs;j2++) { 
                 printf("%ld ",setup_onemachine[j1][j2]) ; 
			  }
			  printf("\n") ; 
		  }
		  */

	  // 		 init_makespan = 0 ; 
	  //printf("starting init_makespan = %d\n",init_makespan);
		  if (init_makespan) { 
		    for (j=1;j<=jobs;j++) init_order[j] =   order[j] = j ;
           for (j=1;j<=jobs;j++) init_order[j] = order_temp[j] = order[j];
      CALCULATE_MAKESPAN(jobs);
      *optimal_makespan = UB_GLOBAL = init_makespan_val = makespan;
      //printf("startorder = ");
      //for(z1=0;z1<jobs+1;z1++)printf("%d ",order[z1]);printf("\n");
		  } 

                  
#define printtimewindows 0
#define printdynamicdetails 0
#define printprecedenceconstraints 0
//#define tighteningoff 1

if (jobs<myfirstK) dynK = jobs;
else dynK = myfirstK;

//tightened = (predlist[0]==0)*tighteningoff;

for (j1=1; j1<4; ) { /*j1=1 first time; j1=2 or 3 dynamic; j1=4 done*/
  //printf("***j1=%d***\n",j1);
  if (j1==1) {
    if (init_makespan) {UB_GLOBAL = init_makespan_val;}
    else {
      LONGEST_TAIL(jobs,1);
      for (j=1;j<=jobs;j++) init_order[j] = order_temp[j] = order[j];
      CALCULATE_MAKESPAN(jobs);
      *optimal_makespan = UB_GLOBAL = init_makespan_val = makespan;
    }
    /*initialize time windows*/
    release[0]=pt[0]=tail[0]=0;
    for (j=1; j<=jobs; j++) {
      wdwBegin[j] = release[j];
      wdwEnd[j] = UB_GLOBAL-1-tail[j]-pt[j];
      UB_improvement = 0;
    }
    j1++;
  }
  else { /* j1==2 regular j1==3 use init_order */
    order[0]= (j1==2) ? jobs+1 : 0;
    for (j=1; j<=jobs; j++) {
      wdwEnd[j] -= UB_improvement;
      if (printtimewindows)
        printf("Job %d has time window [%d,%d] and service time %d\n",
               j,wdwBegin[j],wdwEnd[j],pt[j]);
      if (wdwEnd[j]<wdwBegin[j]) {
        j = jobs+2; /*ends loop*/
        if (printdynamicdetails) printf("Time Windows Infeasible!!\n");
      }
    } /* if loop terminates normally, j == jobs+1 */
    if (j==jobs+1) {
      if (printdynamicdetails)
        printf("Attempting to find makespan of %d or better with K=%d (%d)\n",
               UB_GLOBAL-1,dynK,jobs+1);
      if (printprecedenceconstraints) {
        printf("-------\n");
        for(z1=0;predlist[z1];z1++)
        { printf(" before %d comes",predlist[z1]);
          for(z1++;predlist[z1];z1++)printf(" %d",predlist[z1]);
          printf("\n");
      } }

      tempcost = DynOpt(dynK,jobs+1,jobs+1,0,order,order2,
                        wdwBegin,wdwEnd,pt,&guarantee,predlist);
      if (printdynamicdetails)
      { if (tempcost > (1<<29))
          printf("No improved makespan found (%d)\n",tempcost);
        else { printf("Improved makespan found (%d)\n",tempcost);
               for(z1=0;z1<jobs+1;z1++)printf("%d ",order2[z1]);printf("\n");}
      }
    }
    else {
      tempcost = (1<<30);
      guarantee = 1; /* true */
    }

    if (tempcost < (1<<29)) { /* probable improvement found */
      for(j=1;j<=jobs;j++) {
        order_temp[j]=order2[j];
      }
      CALCULATE_MAKESPAN(jobs);
//printf("##### old makespan: %d",UB_GLOBAL);
//printf(" new perceived: %d",makespan);
      perceivedmakespan=makespan;
      CALCULATE_DELAYED_MAKESPAN(jobs,predlist);
//if (perceivedmakespan!=makespan) {printf(" #change#");}
//printf(" new actual: %d\n",makespan);
      //tightretval=2;
      //if (perceivedmakespan != makespan && tightened==0)
      //{ tightretval = TightenWindows(jobs,wdwBegin,wdwEnd,pt,predlist);
//printf("TIGHTEN2 DONE! %d\n",tightretval);
      //  tightened=1;
      //}
      if (UB_GLOBAL > makespan) { /* improvement */
        //tightened = (predlist[0]==0)*tighteningoff;
        UB_improvement = UB_GLOBAL - makespan;
        *optimal_makespan = UB_GLOBAL = makespan;
        for(j=1;j<=jobs;j++) {
          order[j]=order2[j];
        }
      }
      else { /* ghost improvement */
        for(j=1;j<=jobs;j++) {
          order_temp[j]=order[j];
        }
        //if (tightretval==2)
	guarantee=0; dynK=mymaxK; tempcost=(1<<29);
          /* the line above prevents an infinite loop when
              dynamic is fooled into thinking it found an improvement */
      }
    }

    if (tempcost >= (1<<29)) { /* no improvement found */
      moveon = 0;
      if (moveon==0 && guarantee==0 && dynK < mymaxK) {
        moveon = 1;
	dynK = mymaxK;
      }
      //if (moveon==0 && guarantee==0 && tightened==0) {
      //  tightretval = TightenWindows(jobs,wdwBegin,wdwEnd,pt,predlist);
      //printf("TIGHTEN DONE! %d\n",tightretval);
      //  tightened=1;
      //  moveon = (tightretval == 1);
      //}
      if (moveon==0 && guarantee==0 && UB_GLOBAL==init_makespan_val) {
	j1++;
	for (j=1;j<=jobs;j++) order_temp[j] = order[j] = init_order[j];
        //tightened = (predlist[0]==0)*tighteningoff;
        moveon = 1;
      }
      if (moveon==0) {
	for (j=1;j<=jobs;j++) order[j] = order_temp[j];
	j1=4;
      }
      UB_improvement = 0;
    }
  }
  //printf("final order = ");
  //for(z1=0;z1<jobs+1;z1++)printf("%d ",order[z1]);printf("\n");
}


//        STOPTIME(1) ;

 //            printf("Cpu time = %f seconds \n\n",(double) USERTIME(1)/1000) ;

           // printf("**********************************************\n") ;
			*optimal_makespan=UB_GLOBAL ;
         

}

/* ---------------------------------------------------------------
   --------------------------------------------------------------- */

WINDOWS(jobs) 
long jobs ;
{
 long i ; 
 long maxq ; 
 long due[MAXJOBS] ;
 
 maxq = 0 ; 
 for (i=1;i<=jobs;i++) if (tail[i] > maxq) maxq = tail[i] ;
 maxq = 10*maxq ;
 for (i=1;i<=jobs;i++) 
   {
    due[i] = maxq - tail[i] ; 
    VALUE[i] = ((double) ( due[i] - release[i] )) ; 
  }
}

/* ---------------------------------------------------------------
  | LONGEST_TAIL() : This procedure performs the longest tail      |
  | dispatching rule. Also it is modified for the case of the     |
  | setup_onemachine costs.  March 22, 1991.                                 |
   ---------------------------------------------------------------
*/

LONGEST_TAIL(jobs,typeo)
     long jobs ;
     long typeo ;
{
 long i  ; 
 long schedule[MAXJOBS] ;
 long tjobs , iprev , ijob , iqi ; 
 long mrelease , ctime , prevtime ;
  double   aa , bb , tweight , cweight   ;
  double weights [ MAXJOBS ] ; 
 // double random_number() ; 
 long candidates , SELECTED ; 
 long the_order[MAXJOBS] ; 

 for (i=1;i<=jobs;i++) { schedule[i] = 0 ; }
 tjobs = 0 ;
 ctime = 0 ; 
 iprev = 0 ;
 firstp = 1 ; 
 makespan = 0 ; 


 while (tjobs < jobs) 
   { 
     mrelease = ((long) RAND_MAXI) ; 
     for (i=1;i<=jobs;i++) 
      { if ((schedule[i] == 0) && (release[i] < mrelease)) 
         { mrelease=release[i] ; } } 
     prevtime = ctime ; 
     if (mrelease > ctime) { ctime = mrelease ; }

     iqi = ((long)  -RAND_MAXI) ; 
     candidates = 0 ; 
     for (i=1;i<=jobs;i++) {
       if (schedule[i] == 0)  {
             if (release[i] <= ctime) {
               candidates++ ; 
               the_order[candidates] = i ; 
              }
          }
     }



//  printf("Candidates = %ld\n", candidates) ; 

  aa = 1.0 ;
  bb = 1.0 ; 
  for (i=1;i<=candidates;i++)    { 
      weights[i] = (1.0 / aa) ; 
    }
  tweight = 0.0 ;
  for (i=1;i<=candidates;i++) tweight = tweight + weights[i] ; 
  for (i=1;i<=candidates;i++)     {  
      weights[i] = (weights[i] /  tweight) ; 
    }
  
  tweight = 0.0 ;
  for (i=1;i<=candidates;i++) tweight = tweight + weights[i] ; 

//  y = random_number() ; 
 // printf("y = %f \n",y) ; 
 // y =  y * tweight ; 
  cweight = 0.0 ;
  SELECTED = 0 ;
//  printf("y = %f \n",y) ; 
  iqi = 0 ; 
  for (i=1;i<=candidates;i++)    { 
	  if (tail[the_order[i]] >= iqi) { 
         iqi = tail[the_order[i]] ; 
		 ijob = the_order[i] ; 
	  }
    }
  
 // printf("Selected = %ld iprev = %ld\n",SELECTED,iprev) ; 
 // if (SELECTED == 0) {printf("Error in selection \n") ; exit(1) ; }

      

     tjobs++ ;
     order[tjobs] = ijob ; 
     if (prevtime <  ctime)
       { if ((prevtime + setup_onemachine[iprev][ijob])  > ctime) 
           { ctime = prevtime + setup_onemachine[iprev][ijob] ; }
       } 
     else
       { ctime = ctime + setup_onemachine[iprev][ijob] ; }

     ctime = ctime + pt[ijob] ; 
     if ( makespan < ctime + tail[ijob])  
       { makespan = ctime + tail[ijob] ; }

     iprev = ijob ; 
     schedule[ijob] = 1 ; 
   }

 if (typeo) { LTH1 = (double) makespan ; }
 else { LTH2 = (double)  makespan ; }

/* if (printi) 
   { 
     if (typeo) { printf("LTH (q[i]), Makespan = %ld \n",makespan) ;  }
     else { printf("LTH (q[i]-s[j,i]) Makespan = %ld \n",makespan) ; }  
   }
*/

}

/* ---------------------------------------------------------
  |                                                         |
   ---------------------------------------------------------  */


INSERTION(jobs)
     long jobs ;
{
 long i , j ; 
 long tjobs , ijob , iqi ; 
 long makesp , l , mak ;
 long schedule[MAXJOBS] ;
 long oldorder[MAXJOBS] ;
 long best[MAXJOBS] ;

 for (i=1;i<=jobs;i++)  schedule[i] = 0 ; 
 tjobs = 0 ;

 while (tjobs < jobs) 
   { 
     iqi = ((long) RAND_MAXI ); 
     for (i=1;i<=jobs;i++) 
       { if (!schedule[i])
           {
             if (tail[i] < iqi) 
               {
                iqi = tail[i] ; 
                ijob = i ; 
               }
           }
       }

     tjobs++ ; 
     schedule[ijob] = 1 ; 
     makesp = ((long) RAND_MAXI) ; 

     best[tjobs] = ijob ;      
     for (i=1;i<tjobs;i++) oldorder[i] = order[i] ;
     for (i=tjobs-1;i>=1;i--)
       {
        l=0 ;
        for (j=1;j<i;j++)  { l++ ; order[l] = oldorder[j] ; }
        l++ ; order[l] = ijob ; 
        for (j=i;j<tjobs;j++)  { l++ ; order[l] = oldorder[j] ; }
        SOLUTION(l,&mak) ; 
        if (mak < makesp ) 
         { makesp = mak ; 
           for (j=1;j<=tjobs;j++) best[j] = order[j] ;
         }
      }
     for (j=1;j<=tjobs;j++) order[j] = best[j] ;
   }
 CALCULATE_MAKESPAN(jobs) ; 
 INS = (double) makespan ; 
 if (printi) 
     printf("The insertion makespan is %ld , jobs = %ld\n",makespan,jobs) ; 
}


/* ---------------------------------------------------------
  |                                                         |
   ---------------------------------------------------------  */


BALAS_INSERTION(jobs)
long jobs ;
{
 long i , j ; 
 long tjobs , ijob ; 
 long makesp , l , mak ;
 long schedule[MAXJOBS] ;
 long oldorder[MAXJOBS] ;
 long best[MAXJOBS] ;
 double iqi ;

 for (i=1;i<=jobs;i++)  schedule[i] = 0 ; 
 tjobs = 0 ;

 while (tjobs < jobs) 
   { 
     iqi = 0 ; 
     for (i=1;i<=jobs;i++) 
       { if (!schedule[i])
           {
             if (VALUE[i] > iqi) 
               {
                iqi = VALUE[i] ; 
                ijob = i ; 
               }
           }
       }

     tjobs++ ; 
     schedule[ijob] = 1 ; 
     makesp = ((long) RAND_MAXI) ; 

     best[tjobs] = ijob ;      
     for (i=1;i<tjobs;i++) oldorder[i] = order[i] ;
     for (i=tjobs-1;i>=1;i--)
       {
        l=0 ;
        for (j=1;j<i;j++)  { l++ ; order[l] = oldorder[j] ; }
        l++ ; order[l] = ijob ; 
        for (j=i;j<tjobs;j++)  { l++ ; order[l] = oldorder[j] ; }
        SOLUTION(l,&mak) ; 
        if (mak < makesp )  { 
          makesp = mak ; 
          for (j=1;j<=tjobs;j++) best[j] = order[j] ;
         }
      }
     for (j=1;j<=tjobs;j++) order[j] = best[j] ;
   }
 CALCULATE_MAKESPAN(jobs) ; 
 printf("The BALAS insertion makespan is %ld , jobs = %ld\n",makespan,jobs) ; 
}

/* ---------------------------------------------------------
  | Given a sequence this procedure calculates the makespan |
   ---------------------------------------------------------  */

CALCULATE_MAKESPAN(jobs)
long jobs ;
{
 long i ;
 long jobi ;
 long iprev ; 
 long ctime ;

 for (i=1;i<=jobs;i++) crit[i] = 0 ; 
 makespan = 0 ; 
 ctime = 0 ;
 iprev = 0 ; 

 for (i=1;i<=jobs;i++)
   {
     jobi = order_temp[i] ; 
     ctime = ctime + setup_onemachine[iprev][jobi] ; 
     if (release[jobi] > ctime) 
       { previous[jobi] = 0 ; ctime = release[jobi] ; }
     else { previous[jobi] = iprev ; }

     ctime = ctime + pt[jobi] ;
     if ( (ctime + tail[jobi]) > makespan )
        { ifinal = jobi ;  makespan = ctime + tail[jobi] ; }
     iprev = jobi ; 
   }

   iprev = ifinal ; 
   while (iprev)
    { 
     crit[iprev] = 1 ;
     iprev = previous[iprev] ; 
   }
}

/* ---------------------------------------------------------
  | Given a sequence this procedure calculates the makespan |
  | with delays.                                            |
   ---------------------------------------------------------  */

CALCULATE_DELAYED_MAKESPAN(jobs,delays)
long jobs ;
long *delays ;

{
 long i, j ;
 long jobi ;
 long iprev ; 
 long ctime ;
 long delayMatrix[MAXJOBS][MAXJOBS];
 long visited[MAXJOBS];

 for (i=1;i<=jobs;i++) {crit[i] = 0 ; visited[i] = -999999;}
 visited[0] = -999999;
 for (i=0;i<=jobs;i++)
   for (j=0;j<=jobs;j++)
     delayMatrix[i][j]=0; 
 makespan = 0 ; 
 ctime = 0 ;
 iprev = 0 ; 

 for (i=0; delays[i]>0; i++)
 { for (jobi=delays[i++]; delays[i]>0; i+=2)
     delayMatrix[jobi][delays[i]] = delays[i+1];
 }

 for (i=1;i<=jobs;i++)
   {
     jobi = order_temp[i] ; 
     ctime = ctime + setup_onemachine[iprev][jobi] ;

     if (release[jobi] > ctime) 
       { previous[jobi] = 0 ; ctime = release[jobi] ; }
     else { previous[jobi] = iprev ; }

     for (j=0; j<=jobs; j++)
     { if (visited[j]+delayMatrix[jobi][j] > ctime)
       {
//printf("##Delay %d before %d (%d) causes delay of %d\n",j,jobi,
//delayMatrix[jobi][j],visited[j]+delayMatrix[jobi][j]-ctime);
//previous[jobi] = 0 ; ctime = visited[j]+delayMatrix[jobi][j];
     } }
     visited[jobi] = ctime; 

     ctime = ctime + pt[jobi] ;
     if ( (ctime + tail[jobi]) > makespan )
        { ifinal = jobi ;  makespan = ctime + tail[jobi] ; }
     iprev = jobi ; 
   }

   iprev = ifinal ; 
   while (iprev)
    { 
     crit[iprev] = 1 ;
     iprev = previous[iprev] ; 
   }
}

/*  -----------------------------------------------------------
    ----------------------------------------------------------- */

SOLUTION(jobs,sol)
long jobs ;
long *sol ; 
{
 long i ;
 long jobi ;
 long iprev ; 
 long ctime ;

 ctime = 0 ;
 iprev = 0 ; 
 *sol = 0 ;

 for (i=1;i<=jobs;i++)
   {
     jobi = order[i]; 
     ctime = ctime + setup_onemachine[iprev][jobi] ; 
     if (release[jobi] > ctime) ctime = release[jobi] ; 

     ctime = ctime + pt[jobi] ;
     if ( (ctime + tail[jobi]) > *sol) *sol = ctime + tail[jobi] ; 
     iprev = jobi ; 
   }

}



/*  -----------------------------------------------------------
    ----------------------------------------------------------- */

SOL(jobs,sol)
long jobs ;
long *sol ; 
{
 long i ;
 long jobi ;
 long iprev ; 
 long ctime ;

 ctime = 0 ;
 iprev = 0 ; 
 *sol = 0 ;

 tempos = rooti ;
 for (i=1;i<=jobs;i++)
   {
     jobi   = tempos->index ; 
     tempos = tempos->next ;
     ctime  = ctime + setup_onemachine[iprev][jobi] ; 
     if (release[jobi] > ctime) ctime = release[jobi] ; 

     upper[iprev] = ctime ; 
     lower[jobi] = ctime ; 
     ctime = ctime + pt[jobi] ;
     if ( (ctime + tail[jobi]) > *sol) *sol = ctime + tail[jobi] ; 
     iprev = jobi ; 
   }
 upper[iprev] = ctime ;
}

/*  -----------------------------------------------------------
   | OROPT(jobs) :                                             |
    ----------------------------------------------------------- */

OROPT(jobs,leng)
long jobs ;
long leng; 
{
 long i , j , j1 ;
 long impr , sol , iter  ;

 /* first create the double linked list */

 iter = 0 ; 
 impr = 1 ;
 while (impr)
   {
     iter++ ;
     impr = 0 ;
     temp = (struct job *) NULL ; 
     for (i=1;i<=jobs;i++)
       {
         ele = (struct job *) malloc(sizeof(struct job)) ;
         if (temp == ((struct job *) NULL)) rooti = ele ; 
         point[i] = ele ;
         ele->index = order[i] ;
         if (temp != ((struct job *) NULL)) temp->next = ele ; 
         ele->back = temp ; 
         ele->next = (struct job *) NULL ; 
         temp = ele ; 
       }

    for (leng=jobs;leng>=1;leng--) 
     for (i=2;i<jobs;i++)
       {
        if ((i+leng-1) < jobs)
          {
            (point[i]->back)->next = point[i+leng-1]->next ;
            for (j=2;j<jobs;j++) 
              {
                if ((j <= (i-1)) || (j >= (i+leng+1)))
                  {
                    temp = point[j]->next ;
                    point[j]->next = point[i] ; 
                    point[i+leng-1]->next = temp ; 
                    SOL(jobs,&sol) ;
                    if (sol < UB)
                      {
                        UB = sol ; 
                        impr = 1 ; 
                        ele = rooti ;
                        for (j1=1;j1<=jobs;j1++) 
                          {
                            order[j1] = ele->index ; 
                            ele = ele->next ;
                          }
                      }
                    point[j]->next = temp ;       
                  }      
              }
            point[i-1]->next = point[i] ;
            point[i+leng-1]->next = point[i+leng] ; 
          }
         
       }
   }
/*  printf("Number of Iterations is %ld  \n",iter) ;  */
}



/*  -----------------------------------------------------------
   | TABU_INSERTION(jobs) :                                            |
    ----------------------------------------------------------- */

TABU_INSERTION(jobs)
long jobs ;
{
 long i , j , j1 , k1 ; 
 long sol , iter  ;
 long leng , ub , jobii ; 
 long tabu , tabulength , tabucur ; 
 long tabulist[MAXJOBS] ;

 tabulength = 7 ; 
 tabucur = 0 ; 
 leng = 1 ;
 iter = 0 ; 
 for (i=1;i<MAXJOBS;i++)  tabulist[i] = 0 ;

 while (iter < 1000)
   {
     iter++ ;
     ub = ((long)  RAND_MAXI) ; 
     temp = (struct job *) NULL ; 
     for (i=1;i<=jobs;i++)
       {
         ele = (struct job *) malloc(sizeof(struct job)) ;
         if (temp == ((struct job *) NULL)) rooti = ele ; 
         point[i] = ele ;
         ele->index = order[i] ;
         if (temp != ((struct job *) NULL)) temp->next = ele ; 
         ele->back = temp ; 
         ele->next = (struct job *) NULL ; 
         temp = ele ; 
       }

     for (i=2;i<jobs;i++)
       {
         if ((i+leng-1) < jobs)
           {
            (point[i]->back)->next = point[i+leng-1]->next ;
            for (j=2;j<jobs;j++) 
              {
                if ((j < (i-1)) || (j > (i+leng+1)))
                  {
                    temp = point[j]->next ;
                    point[j]->next = point[i] ; 
                    point[i+leng-1]->next = temp ; 
                    SOL(jobs,&sol) ;

                    tabu = 0 ; 
                    for (k1=1;k1<=tabulength;k1++)
                      if (tabulist[k1] == point[i]->index) tabu = 1 ;

                    if ((sol < ub) && (!tabu))
                      {
                        ub = sol ; 
                        ele = rooti ;
                        jobii = point[i]->index ;
                        if (sol < UB) { UB = sol ; printf("Improvement = %ld \n",UB) ;  }
                        for (j1=1;j1<=jobs;j1++) 
                          {
                            order[j1] = ele->index ; 
                            ele = ele->next ;
                          }
                      }
                    point[j]->next = temp ;       
                  }      
              }
            point[i-1]->next = point[i] ;
            point[i+leng-1]->next = point[i+leng] ; 
          }
       }
    tabucur++ ;
    if (tabucur > tabulength) tabucur = 1 ; 
    tabulist[tabucur] = jobii ;
   }
}

/*  ------------------------------------------------------
   | RANDOM_SOLUTION() : constructs a random solution.    |
    ------------------------------------------------------ */

RANDOM_SOLUTION(jobs)
long jobs ;
{
 long i  , ii , temp  ; 
 double y ; 

 for (i=1;i<=jobs;i++) { order[i] = i ; }
 
 for (i=1;i<=jobs;i++) 
   {
     y = random_number() ; 
     temp = order[i] ;
     ii = ((long) (jobs * y)) + 1 ;
     if ((ii <= 0 ) || ( ii > jobs)) { ii = jobs ; } 
     order[i] = order[ii] ; 
     order[ii] = temp ; 
   }
 CALCULATE_MAKESPAN(jobs) ; 
if (printi) printf("Random Solution = %ld \n",makespan) ; 
}

 

/* ------------------------------------------------------------
  | GENERATE_RANDOM_PROBLEM : creates random  problems for     |
  | the One Machine Scheduling problem with setup_onemachine times.       |
   ------------------------------------------------------------ */

GENERATE_RANDOM_PROBLEM(jobs,k)
     long jobs ;
     long k ;
{
 long  i , j   ; 
 
 double  y ;
 double  maxim  ;

 maxim = jobs*k ; 

 if (YESI) printf("%ld\n",jobs) ; 
 for (i=1;i<=jobs;i++)
  {
     y = random_number();
     release[i] =  y * maxim + 1 ;  

     y = random_number() ;
     pt[i] =  y * pmax + 1  ; 

     y = random_number() ;
     tail[i]  = y * maxim + 1  ; 
     if (YESI) printf("%ld %ld %ld\n",release[i],tail[i],pt[i]) ; 
 }


 for (i=0;i<=jobs;i++) {
  for (j=0;j<=jobs;j++) {
     y = random_number() ;  
     setup_onemachine[i][j] = y * smax + 1 ; 
     if (!j) { setup_onemachine[i][j] = 0 ; } 
    }
   setup_onemachine[i][i] = 9999  ;
 }


 for (i=0;i<=jobs;i++) {
  for (j=0;j<=jobs;j++) {
    if(YESI) printf("%ld ",setup_onemachine[i][j]) ; 
 }
  if (YESI) printf("\n") ; 
}

}



/* ---------------------------------------------------------
  | calculate_lower_bound_SET()                                 |
   --------------------------------------------------------- */

calculate_lower_bound_SET(jobs,max_lb)
long jobs ;
long *max_lb ; 
{ long    i1 , i2 , ik , jobi   ;
 
 
  long total_process ; 
  long z  ; 
 
  long c[10000] ; 

  total_process = 0 ; 
  *max_lb = ((long) -RAND_MAXI );

  /* create the cost matrix and solve the assignment problem */

  c[1] = 0 ;   
  for (i1=1;i1<=jobs;i1++) c[i1+1] = release[i1] ; 

  ik = jobs + 1 ;
  for (i1=1;i1<=jobs;i1++)
    {
      ik =ik + 1   ;  c[ik] = tail[i1] ;           
      for (i2=1;i2<=jobs;i2++)
        { ik = ik + 1 ; 
          c[ik] = setup_onemachine[i1][i2] + pt[i1] ; 
        }
    }
  jobi = jobs + 1 ;
  ASSIGNMENT(jobi,c,&z) ; 
  if (z > *max_lb) *max_lb = z ;
  if (printi)   printf("Lower Bound = %ld \n",*max_lb) ; 
}

/* --------------------------------------------------------------
  | LINDO_FORMULATION()                                          |
   -------------------------------------------------------------- */

LINDO_FORMULATION(jobs)
long jobs ; 
{
  long i , j    ; 
  long row ; 

  row = 0    ; 
  printf("MIN tt \nSUBJECT TO\n",row) ; 
  for (i=1;i<=jobs;i++)
    {
     row = row + 1 ; 
     printf(" %ld) ",row) ;
     printf("t%ld >= %ld \n",i,release[i]) ; 
   }

  for (i=1;i<=jobs;i++)
    {
     row = row + 1 ; 
     printf(" %ld) ",row) ;
     printf("tt - t%ld >= %ld \n",i,pt[i]+tail[i]) ; 
   }

  for (i=1;i<=jobs;i++) 
    {
     for (j=i+1;j<=jobs;j++)
       {
        if (i != j) 
          { 
           row = row + 1 ;
           printf(" %ld) ",row) ;
           printf("t%ld - t%ld + 9999 x%ld%ld >= %ld \n",i,j,i,j,pt[j]+ setup_onemachine[j][i]) ;
           row = row + 1 ;
           printf(" %ld) ",row) ;
           printf("t%ld - t%ld - 9999 x%ld%ld >= %ld \n",j,i,i,j,pt[i]+ setup_onemachine[i][j]-9999) ;
          }
       }
   }

   for (i=1;i<=jobs;i++)
     {
      for (j=i+1;j<=jobs;j++)
        {
            row = row + 1 ;            
            printf(" %ld) ",row) ;
            printf(" x%ld%ld <= 1 \n",i,j) ; 
       }
    }

printf("END\n") ; 

   for (i=1;i<=jobs;i++)
     {
      for (j=i+1;j<=jobs;j++){ printf(" long x%ld%ld  \n",i,j) ; }
    }

}

/* -------------------------------------------------------------
  | ASSIGNMENT() This program solves the assignment problem     |
   ------------------------------------------------------------- */

ASSIGNMENT(n,c,z)
long n ;
long c[10000] ; 
long *z ;
{
  long rlabel[80] , clabel[80] , ys[80] , yt[80] ;
  long pred[80] , row[80] , col[80] , perm[80] ; 
  long sup , i , j ; 
  long nn ; 
  long ik , is ,  cc ,  ui , j0 , vj  ; 
  long u , us , usi ; 
  long length , index , w , ws , wsi , update , ind , isj ; 

  *z = 0 ; 
  sup = 1000000 ; 
  nn = n * n ; 

 for (i=1;i<=n;i++)
 {
    row[i] = 0 ; 
    col[i] = 0 ; 
    pred[i] = 0 ; 
    ys[i] = 0 ; 
    yt[i] = 0 ; 
    }
    ik = 0 ; 

  for (i=1;i<=n;i++)
  { 
   for (j=1;j<=n;j++)
     {
       ik = ik + 1 ; 
       cc = c[ik] ;  
       if (j == 1 ) goto A4  ; 
       if ( ( cc - ui) >= 0 ) goto A3  ; 
    A4: ui = cc ; 
       j0 =  j ; 
    A3 :  ; 
    }  
     
      ys[i] = ui ; 
      if (row[j0] != 0 ) goto A2 ; 
      row[j0] = i ; 
      col[i] = j0 ; 
    A2: ; 
       }

      for (j=1;j<=n;j++)
      {      
       yt[j] = 0 ; 
       if ( row[j] == 0 ) yt[j] = sup ; 
      } 
      ik = 0 ; 

  for (i=1;i<=n;i++)
{
 ui = ys[i]  ; 
  for (j=1;j<=n;j++) 
 { ik = ik + 1 ; 
   vj = yt[j] ; 
   if (vj <= 0) goto A7 ;
   cc = c[ik] - ui ; 
   if (cc >= vj) goto A7 ; 
   yt[j] = cc  ;
   pred[j] = i ;  
   A7: ;  }
}
 
  for (j=1;j<=n;j++)
{ i = pred[j] ; 
  if (i == 0 ) goto A8 ; 
  if (col[i] != 0) goto A8 ; 
  col[i] =  j ; 
  row[j] = i ; 
  A8: ;
  }


 for (i=1;i<=n;i++) 
{
  if (col[i] != 0) goto A9 ; 
  ui = ys[i] ; 
  ik = (i-1) * n ; 
  for (j=1;j<=n;j++) 
    {
      ik = ik + 1 ; 
      if (row[j] != 0) goto A10 ; 
      cc = c[ik] ; 
      if ( (cc -ui-yt[j]) > 0 ) goto A10 ; 
      col[i] = j ;  
      row[j] = i ; 
      goto A9 ; 
   A10: ;  }
   A9: ; 
 } 

/* construction of an optimal assignment */ 

      for (u=1;u<=n;u++)
       { 
        if (col[u] > 0 ) goto A1000 ; 
        us = (u - 1) * n  ; 
        for (i=1;i<=n;i++) 
         {    
          pred[i] = u ; 
          perm[i] = 0 ; 
          rlabel[i] = sup ; 
          usi = us + i ; 
          clabel[i] = c[usi] -ys[u] - yt[i] ; 
        }
       rlabel[u] = 0 ; 
  A105: length = sup ; 

    for (i=1;i<=n;i++)
     {
      if (perm[i] == 1) goto AMAXJOBS ; 
      if (clabel[i] >= length) goto AMAXJOBS ; 
      length = clabel[i] ; 
      index = i ; 
  AMAXJOBS: ;
 }


     if (row[index] <= 0) goto A400 ; 
     perm[index] = 1 ; 
     w = row[index] ; 
     ws = (w-1) * n ; 
     rlabel[w] = length ; 

     for (i=1;i<=n;i++) 
       {
        if (perm[i] == 1) goto A130 ; 
        wsi = ws + 1 ; 
        update = length + c[wsi] -ys[w] -yt[i] ; 
        if (clabel[i] <= update) goto A130 ; 
        clabel[i] = update ; 
        pred[i] = w ;  
  A130 : ;  } 
       goto A105 ; 

  A400: w = pred[index] ; 
      row[index] = w ; 
      ind = col[w] ; 
      col[w] = index ; 
      if (w == u) goto A500 ; 
      index = ind ; 
      goto A400 ; 

  A500: for (i=1;i<=n;i++)
    { if (rlabel[i] == sup) goto A505 ; 
      ys[i] = ys[i] + length - rlabel[i] ; 
  A505 : if (clabel[i] >= length) goto A510 ; 
      yt[i] = yt[i] + clabel[i] - length ; 
      A510: ; }
 A1000: ;}


      *z = 0 ; 
      for (i=1;i<=n;i++)
       {
        is = (i-1) * n ; 
        j = col[i] ; 
        isj = is + j ; 
        *z = *z + c[isj] ; 
       }

}


/* *************************************************************
   ************************************************************* */

UPDATE_SETUP(n,sol,impr,ub,ij,st)
     long n ; 
     long sol ;
     long *impr ;
     long *ub ;
     long ij ; 
     long *st ;
{
 long i ; 
 if (sol < *ub) 
   {
    *ub = sol ;
    for (i=1;i<=n;i++) BEST[i] = order[i] ; 
    *impr = 1;
    *st = ij ; 
  }
}