/*

09/10/01

This is the default encoding 
of the job shop problem.

PRECONDITIONS:

1.  ILOG Scheduler 5.0;
2.  Data file in the following format.
    The first line contains two numbers: number of jobs
    and number of machines. The subsequent lines
    (one for each job) contain m pairs of numbers,
    where m is the number of operations in a job.
    Each pair consists of the number of machine
    required by an operation and the duration of this
    operation.
3.  Limit on execution time in seconds.

POSTCONDITIONS:

1.  Schedule with the makespan 
    obtained by binary search starting from
    the lower bound found by propagation and 
    upper bound found by opportunistic scheduling. 

*/


#include <ilsched/iloscheduler.h>
 

ILOSTLBEGIN 
const IloInt MaxSize = 400; //20x20
IloInt ResourceNumbers06[]; 
IloInt Durations06[]; 
IloInt ResourceNumbers10[]; 
IloInt Durations10[]; 
IloInt ResourceNumbers20[]; 
IloInt Durations20[]; 
IloInt* resourceNumbers; 
IloInt* durations; 
IloInt numberOfJobs,numberOfResources; 
IloInt TimeLimit; 
 
///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM DEFINITION
//
///////////////////////////////////////////////////////////////////////////////
 
class NbUnrankedExt {
private:
  IlcInt _nbOfUnranked;

public:
  NbUnrankedExt() :_nbOfUnranked(0) {};
  ~NbUnrankedExt(){};
  void setValue(IlcInt nbOfUnranked) {
    _nbOfUnranked = nbOfUnranked;
  }
  IlcInt getValue() const {
    return _nbOfUnranked;
  }
};
IloModel
DefineModel(IloEnv& env,
            IloInt numberOfJobs,
            IloInt numberOfResources,        
            IloInt* resourceNumbers,
            IloInt* durations,
            IloNumVar& makespan)
{
  IloModel model(env);

  /* CREATE THE MAKESPAN VARIABLE. */
  IloInt numberOfActivities = numberOfJobs * numberOfResources;
  IloInt horizon = 0;
  IloInt k;

  for (k = 0; k < numberOfActivities; k++)
    horizon += durations[k];

  makespan = IloNumVar(env, 0, horizon, ILOINT);

  /* CREATE THE RESOURCES. */
  IloSchedulerEnv schedEnv(env);
  schedEnv.getResourceParam().setCapacityEnforcement(IloMediumHigh);
  schedEnv.getResourceParam().setPrecedenceEnforcement(IloMediumHigh);

  IloInt j;
  IloUnaryResource *resources = 
    new (env) IloUnaryResource[numberOfResources];
  for (j = 0; j < numberOfResources; j++)
    resources[j] = IloUnaryResource(env);

  /* CREATE THE ACTIVITIES. */
  char buffer[128];
  k = 0;
  IloInt i;
  for (i = 0; i < numberOfJobs; i++) {
    IloActivity previousActivity;
    for (j = 0; j < numberOfResources; j++) {
      IloActivity activity(env, durations[k]);
      sprintf(buffer, "J%dS%dR%d", i, j, resourceNumbers[k]);
      activity.setName(buffer);

      IloResourceConstraint rct = 
        activity.requires(resources[resourceNumbers[k]]);
      NbUnrankedExt* nbOfUnranked = 
        new (env) NbUnrankedExt();
      rct.setObject(nbOfUnranked);
      model.add(rct);

      if (j != 0)
        model.add(activity.startsAfterEnd(previousActivity));
      previousActivity = activity;
      k++;
    }
    model.add(previousActivity.endsBefore(makespan));
  }

  /* RETURN THE MODEL. */
  return model;
}


///////////////////////////////////////////////////////////////////////////////
//
// PRINTING OF SOLUTIONS
//
///////////////////////////////////////////////////////////////////////////////

void
PrintSolution(const IloSolver& solver)
{
  IlcScheduler scheduler(solver);
  IloEnv env = solver.getEnv();
  for(IloIterator<IloActivity> ite(env); ite.ok(); ++ite)
    solver.out() << scheduler.getActivity(*ite) << endl;
}

///////////////////////////////////////////////////////////////////////////////
//
// PROBLEM SOLVING
//
///////////////////////////////////////////////////////////////////////////////
 
IlcInt GetNumberOfUnranked(const IlcResourceConstraint& rct) {
  /* RETURN NUMBER OF UNRANKED W.R.T. RCT */
  IlcInt nb = 0;
  for (IlcResourceConstraintIterator ite(rct, IlcUnranked);
       ite.ok(); ++ite)
    nb++;
  return nb;
}

IlcInt GetOpportunity(const IlcScheduler& scheduler,
                      const IlcResourceConstraint& srct1,
                      const IlcResourceConstraint& srct2) {

  IlcActivity act1 = srct1.getActivity();
  IlcActivity act2 = srct2.getActivity();

  IlcInt smin1 = act1.getStartMin();
  IlcInt smax1 = act1.getStartMax();
  IlcInt emin1 = act1.getEndMin();
  IlcInt emax1 = act1.getEndMax();
  IlcInt smin2 = act2.getStartMin();
  IlcInt smax2 = act2.getStartMax();
  IlcInt emin2 = act2.getEndMin();
  IlcInt emax2 = act2.getEndMax();

  /* DOMAIN DELTA WHEN RCT1 RANKED BEFORE RCT2 */
  IlcInt deltaEnd12   = ((emax1 < smax2) ? OL : emax1 - smax2);
  IlcInt deltaStart12 = ((smin2 > emin1) ? OL : emin1 - smin2);
  IlcInt delta12      = deltaEnd12 + deltaStart12;

  /* DOMAIN DELTA WHEN RCT2 RANKED BEFORE RCT1 */
  IlcInt deltaEnd21   = ((emax2 < smax1) ? OL : emax2 - smax1);
  IlcInt deltaStart21 = ((smin1 > emin2) ? OL : emin2 - smin1);
  IlcInt delta21      = deltaEnd21 + deltaStart21;

  /* MINIMAL NUMBER OF UNRANKED RESOURCE CONSTRAINTS */
  IlcInt nbUrkd1   = ((NbUnrankedExt*)(scheduler.getExtractable(srct1).getObject()))->getValue();
  IlcInt nbUrkd2   = ((NbUnrankedExt*)(scheduler.getExtractable(srct2).getObject()))->getValue();
  IlcInt minNbUrkd = (nbUrkd1 <= nbUrkd2) ? nbUrkd1 : nbUrkd2;
  
  /* RETURN MEASURE OF OPPORTUNITY */
  return (minNbUrkd * (delta12 - delta21));
}

IlcBool 
SelectMostOpportunisticConflict(IlcScheduler& schedule,
                                IlcResourceConstraint& selectedRct1,
                                IlcResourceConstraint& selectedRct2) {
  
  IlcBool existsConflict = IlcFalse;

  IlcInt oppMaxAbs = -1;
  IlcInt oppMax = 0;
  IlcInt opp;
  
  for (IlcUnaryResourceIterator ires(schedule); ires.ok(); ++ires) {
    IlcUnaryResource resource = (*ires);
    if (resource.hasPrecedenceGraphConstraint() &&
        !resource.isRanked()) {

      /* FOR EACH RESOURCE CONSTRAINT, COMPUTE AND STORE THE NUMBER OF
         RESOURCE CONSTRAINTS UNRANKED W.R.T. IT */
      for (IlcResourceConstraintIterator irct(resource); 
           irct.ok(); ++irct) {
        IlcResourceConstraint rct = (*irct);
        if (!rct.isRanked())
          ((NbUnrankedExt*)schedule.getExtractable(rct).getObject())->
            setValue(GetNumberOfUnranked(rct));
     }
      
      /* SELECT MOST OPPORTUNISTIC PAIR OF RESOURCE CONSTRAINT */
      for (IlcResourceConstraintIterator isrct1(resource); 
           isrct1.ok(); ++isrct1) {
        IlcResourceConstraint srct1 = (*isrct1);
        if (!srct1.isRanked()) {
          for (IlcResourceConstraintIterator isrct2(srct1, IlcUnranked);
               isrct2.ok(); ++isrct2) {
            IlcResourceConstraint srct2 = (*isrct2);
      opp = GetOpportunity(schedule, srct1, srct2);
      if (oppMaxAbs < IloAbs(opp)) {
              existsConflict = IlcTrue;
              oppMaxAbs      = IlcAbs(opp);
              oppMax         = opp;
              selectedRct1   = srct1;
              selectedRct2   = srct2;
            }
          }
        }
      }
    }
  }
  
  /* SELECT WHICH BRANCH WILL BE CHOSEN FIRST AMONG RCT1 << RCT2 AND
     RCT2 << RCT1 */
  if (existsConflict && (0 < oppMax)) {
    IlcResourceConstraint tmpRct = selectedRct1;
    selectedRct1 = selectedRct2;
    selectedRct2 = tmpRct;
  }
  
  return existsConflict;
}

ILOCPGOAL0(SolveConflicts) {
  IloSolver s = getSolver();
  IlcScheduler scheduler = IlcScheduler(s);

  IlcResourceConstraint srct1;
  IlcResourceConstraint srct2;
  if (SelectMostOpportunisticConflict(scheduler, srct1, srct2))
    return IlcAnd(IlcTrySetSuccessor(srct1, srct2), this);

  return 0;
}
void
SetMakespanInitialBounds(IloSolver& solver, 
                         IloNumVar& makespan)
{
  IloGoal goal;
  /* SET MAKESPAN LOWER BOUND AND RESTART */
  goal = IloGoalTrue(solver.getEnv());
  solver.solve(goal);
  makespan.setLb(solver.getMin(makespan));

  /* SOLVE WITH GOAL SOLVECONFLICTS */
  goal = SolveConflicts(solver.getEnv());
  solver.solve(goal);

  /* SET MAKESPAN UPPER BOUND */
  makespan.setUb(solver.getMin(makespan));
  solver.out() << "Solution with makespan " << makespan.getUb() << endl; 
  solver.printInformation();
}

void
Dichotomize(IloModel& model,
            IloSolver& solver,
            const IloNumVar& makespan)
{
  /* GET MAKESPAN INITIAL BOUNDS */
  IloNum min = makespan.getLb();
  IloNum max = makespan.getUb();

  /* OPTIMIZE. */
  IloGoal goal = IloRankForward(solver.getEnv(), makespan,
                                IloSelResMinLocalSlack,
                                IloSelFirstRCMinStartMax);
  while (min < max) {
    IloNum value = IloFloor((min + max) / 2);
    IloConstraint ct = (makespan <= value);
    model.add(ct);
    if (solver.solve(IloLimitSearch(solver.getEnv(), goal, IloTimeLimit(solver.getEnv(), TimeLimit)))) {
      max = solver.getMin(makespan);
      solver.out() << "Solution with makespan " << max << endl; 
	  solver.printInformation();
    }
    else {
      solver.out() << "Failure with makespan " << value << endl;
      min = value + 1;
    }

    model.remove(ct);
  }

  /* RECOMPUTE THE OPTIMAL SOLUTION. THIS STEP COULD BE AVOIDED IF
     SOLUTIONS WERE STORED AS PART OF THE OPTIMIZATION PROCESS. */
  model.add(makespan == max);
  solver.solve(goal);
}
///////////////////////////////////////////////////////////////////////////////
//
// MAIN FUNCTION
//
///////////////////////////////////////////////////////////////////////////////

void
InitParameters(int argc,
               char** argv,
               IloInt& numberOfJobs,
               IloInt& numberOfResources,                    
               IloInt*& resourceNumbers,
               IloInt*& durations)
{
	if (argc!=3) { 
		cout<<"Usage: <filename>.exe <datafile_name> TimeLimit <s>"<<endl; 
		exit(1); 
	} 
 
	ifstream fin; 
	ofstream fout; 
	fin.open(argv[1],ios::in); 
	TimeLimit = atoi(argv[2]); 
 
	fin>>numberOfJobs; 
	fin>>numberOfResources; 
	cout<<"numberOfJobs = "<<numberOfJobs<<endl; 
	cout<<"numberOfResources = "<<numberOfResources<<endl; 
	cout<<endl; 
    IloInt index=0; 
	for (int i=0;i<numberOfJobs;i++) { 
		for (int j=0;j<numberOfResources;j++) { 
			fin>>resourceNumbers[index]; 
			fin>>durations[index]; 
			index++; 
		} 
	} 
}

int main(int argc, char** argv)
{
  try {
    IloEnv env;
    
	resourceNumbers = new IloInt[MaxSize];  
	durations = new IloInt[MaxSize];  
 
	for (int i=0;i<MaxSize;i++) { 
		resourceNumbers[i] = 0; 
		durations[i] = 0; 
	} 
	 
    InitParameters(argc,
                   argv,
                   numberOfJobs,
                   numberOfResources,
                   resourceNumbers,
                   durations); 
    IloNumVar makespan;
    IloModel model = DefineModel(env,
                                 numberOfJobs,
                                 numberOfResources,
                                 resourceNumbers,
                                 durations,
                                 makespan);
    IloSolver solver(model);
    SetMakespanInitialBounds(solver, makespan);
    Dichotomize(model, solver, makespan);
    PrintSolution(solver);
    solver.printInformation();
    env.end();
  }
  catch (IloException& exc) {
    cout << exc << endl;
  }

  return 0;
}