#include <stdio.h>

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

long INFEAS(long n)
{
  long i ;
  
  for (i=1;i<=n;i++) if (compl[i] > deadl[i]) return(1) ;
  return(0) ;
}

/*
 *
 */

BINARY(long n,
     long left,
     long right,
     long *optimal_makespan,
     long solve_with_deadlines,
     long *bmksp , 
     long status)
{
  long i  ; 
  long guess ;
  long OPTI ;

  OPTI = 0 ;

  best_mk = ((long) RAND_MAXI)  ; 
  while ((!OPTI) && ((right - left) > 0))   {
    RESTORE_RANDOM_PROBLEM(n) ; 
    guess = (left + right) / 2 ;
    for (i=1;i<=n;i++) tail[i] = MAX(tail[i],(guess-deadl[i])) ; 
    *optimal_makespan = ((long) RAND_MAXI ); 
    onemachine(n,
               optimal_makespan,
               solve_with_deadlines,
               bmksp,
               status) ;  
      if ((*optimal_makespan > guess) && (!(INFEAS(n)))) OPTI = 1 ;
      if (INFEAS(n)) { left = *optimal_makespan ; }
      else { 
        right = *optimal_makespan ;
        if (*optimal_makespan < best_mk) {
          best_mk = *optimal_makespan ;
          for (i=1;i<=n;i++) besti[i] = order[i] ; 
        }
      }
  }

  *optimal_makespan = best_mk ; 
  for (i=1;i<=n;i++) order[i] = besti[i] ; 
}

/* ************************************************************
  *  One machine scheduling problem with release times         *
  *  tails, and delayed precedence constraints.                *
  *  Written by Alkiviadis Vazacopoulos.                       *
  *  Carnegie Mellon University.                               *
  *  Graduate School of Industrial Administration.             *
  *  Pittsburgh. PA 15213                                      *
  *  March 1, 1992.                                            *
  *  Latest version.                                           *
   ************************************************************ */


onemachinelines(long n ,
     long *optimal_makespan ,
     long solve_with_deadlines ,
     long *bmksp ,
     long status ) 
{
  long otail[MAXJOBS] ; 
  long DOWN ; 
  long i ; 
  long BIG , UP ; 
  long infeas ; 

  long INFEAS() ;
  long iteri ;


  STORE_RANDOM_PROBLEM(n) ; 

  BIG = 0 ; 
  UP = 0 ; 
  for (i=1;i<=n;i++) {
      if (deadl[i] > BIG) BIG = deadl[i] ;
      if ((deadl[i]+tail[i]) > UP) UP = deadl[i] + tail[i] ;
      otail[i] = tail[i] ;
    }

  for (i=1;i<=n;i++) { tail[i] = BIG - deadl[i] ; } 
  *optimal_makespan = ((long) RAND_MAXI) ; 

  onemachine(n,
             optimal_makespan,
             solve_with_deadlines,
             bmksp,
             status) ;
   
  infeas = 0 ; 
  INFEASIBLE = 0 ; 
  if (*optimal_makespan > BIG)   { 
      infeas = *optimal_makespan - BIG ;
      *optimal_makespan = *optimal_makespan + infeas * PENALTY ; 
        printf("**** Infeasibility : %ld \n",infeas) ; 
	  if (infeas)   INFEASIBLE = 1; 
      return ;
    }



  best_mk = *optimal_makespan ;
  for (i=1;i<=n;i++) besti[i] = order[i] ; 

  RESTORE_RANDOM_PROBLEM(n) ;
  for (i=1;i<=n;i++) tail[i] = otail[i] ; 
  *optimal_makespan = ((long) RAND_MAXI) ; 
  onemachine(n,
             optimal_makespan,
             solve_with_deadlines,
             bmksp,
             status) ; 

  iteri = 0 ;
  while ((*optimal_makespan <= UP) &&
         (INFEAS(n)) && (iteri < maxiteri)) {
    iteri++ ;
    RESTORE_RANDOM_PROBLEM(n) ;
    for (i=1;i<=n;i++)
      tail[i] = MAX(tail[i],(*optimal_makespan-deadl[i])) ; 
    *optimal_makespan = ((long)  RAND_MAXI ); 
    onemachine(n,
               optimal_makespan,
               solve_with_deadlines,
               bmksp,
               status) ; 
  }
  
  DOWN = *optimal_makespan ;
  if ((INFEAS(n)) && ((UP - *optimal_makespan) > 0)) 
       BINARY(n,
              DOWN , 
              UP,
              optimal_makespan,
              solve_with_deadlines,
              bmksp,
              status) ;

 

}