Originally posted by: PreranaJ

Hi,

We are trying to compare MIP vs CP performance for scheduling jobs. CP solution is stuck at same objective value for long time before giving the next better objective value. It is very far from optimal solution (I know the optimal value because of MIP). Is there any way to modify the algorithm or tune the engine to not spend a lot of time on the same objective value?

 

 

#CPOptimizer
#DecisionOptimization

Originally posted by: PhilippeLaborie

Hello,

The first thing to do to improve performance of a CPO model is (lust like for MIP), to try to improve the formulation of the problem. In your case, could you summarise your problem and how you modelled it in CPO? Alternatively, you could export your problem as a .cpo file and attach it so that we can have a look.

Regards,

Philippe

 

#CPOptimizer
#DecisionOptimization

Originally posted by: PreranaJ

Hi Philipee,

 

Thank you for your reply. 

 

The scheduling problem is as follows - There are n jobs which are to be scheduled on m workcenters. There are two types of operations a job has to undergo - 1. Assembly 2.Testing. 

Testing workcenters are different from assembly workcenters. A job can need either  one workcenter or two workcenters or three workcenters for an operation.

Hard Constraints - Testing of the job should happen immediately after the assembly. A workcenter can process only one job at a time. Few jobs have a fixed starting time. 

Objective - Schedule all jobs and Minimize number of early jobs, late jobs, moved jobs, etc

 

The way I modeled it - I consider two separate jobs for assembly and testing. So if I have 100 jobs to schedule, I will have 200 jobs (considering testing and assembly) interval variables. Also every combination of job and workcenters thats allowed is an interval decision variable. 

 

Here is the model - 

 

/*********************************************
 * OPL 12.6.2.0 Model
 * Author: Prerana
 * Creation Date: Oct 9, 2016 at 11:12:42 PM
 *********************************************/
using CP;
range booleanValues = 0..1;

execute settings{
//cp.param.TimeLimit = 1000;
}
tuple Tjobs
{
key int jobID;
string jobdescription;
string jobpropertyID;
string jobpropertyType;
string AssmTestType;
int Early ;
int SRD ;
int Deadline; 
int CurrentSolution ;
int Edit;
int Lock ;
int isAssembly;
int StartDeadline;
int jobtime;
};

{Tjobs} jobs with isAssembly in booleanValues = ...;

tuple Tworkcenter
{
key int WorkcenterID;
string WorkcenterDescription;
int WorkcenterTypeIsAssembly;
int usage;
};

{Tworkcenter} workCenters with WorkcenterTypeIsAssembly in booleanValues =...;

tuple Tjobduration
{
Tjobs jobID;
Tworkcenter workCenterID1;
Tworkcenter workCenterID2;
Tworkcenter workCenterID3;
int duration; 
};
{Tjobduration} jobDuration with jobID in jobs,workCenterID1 in workCenters ,workCenterID2 in workCenters ,workCenterID3 in workCenters = ...;

tuple Tdependentjobs
{
Tjobs jobID1;
Tjobs jobID2;
}
{Tdependentjobs} dependentJobs with jobID1 in jobs, jobID2 in jobs = ...;

tuple TWorkCenterJobAssignment {
  int jobId;
  int workCenterId1;
  int workCenterId2;
  int workCenterId3;
  float jobStartTime;
  float jobFinishTime;
};

{TWorkCenterJobAssignment} workCenterJobAssignment;
{Tjobs} assemblyjobs = {c| c in jobs: c.isAssembly == 1};
{Tjobs} testjobs = {c| c in jobs: c.isAssembly == 0};
{Tjobs} assemblynoneditablejobs = {c| c in jobs: c.isAssembly == 1 && c.Edit == 0};

//preprocessing of data
int Duration[j in jobDuration]= j.duration;
int earlystartTime[w in jobDuration] = w.jobID.StartDeadline;
int H = 100;
int JobTime [j in jobs] = j.jobtime;

// declaraing decision variables

dvar interval nJobs [j in jobs]  size JobTime[j] ;

dvar interval altWcJob [w in jobDuration] optional in earlystartTime[w]..H size Duration[w]    ; 

dvar sequence workcenter[k in workCenters] in all
(w in jobDuration: w.workCenterID1.WorkcenterID == k.WorkcenterID || w.workCenterID2.WorkcenterID == k.WorkcenterID || w.workCenterID3.WorkcenterID == k.WorkcenterID)altWcJob[w]; 

// calculation of decision expressions for objective value

//Distance from SRD
dexpr float DistanceFromSRD = sum (j in jobs: j.isAssembly == 0)abs(endOf(nJobs[j])-presenceOf(nJobs[j])*(j.SRD));

//Distance from the deadline
dexpr float DistanceFromDeadline = sum (j in jobs: j.isAssembly == 0)abs(endOf(nJobs[j])-presenceOf(nJobs[j])*(j.Deadline));

//Sum of Early Jobs
dexpr float SumofEarlyJobs = sum(j in assemblyjobs) (maxl(j.Early - startOf(nJobs[j]),0)/maxl(j.Early - startOf(nJobs[j]),0.1));

//Sum of Late Jobs
dexpr float SumofLateJobs = sum(j in testjobs)(maxl(endOf(nJobs[j]) - j.Deadline,0)/maxl(endOf(nJobs[j]) - j.Deadline,0.1));

//Sum of NonEdit Jobs That are Moved
dexpr float SumofNonEditJobsMoved = sum(j in assemblynoneditablejobs)abs(startOf(nJobs[j]) - j.CurrentSolution)/maxl(abs(startOf(nJobs[j]) - j.CurrentSolution),0.1);

//Total WorkcenterUsage
dexpr float WorkcenterUsage =  sum(w in jobDuration)(presenceOf(altWcJob[w])*w.workCenterID1.usage);

// Objective function
minimize (0.1*DistanceFromSRD + 0.2*DistanceFromDeadline + 10*SumofEarlyJobs + 200*SumofLateJobs + 50*SumofNonEditJobsMoved + 0.01*WorkcenterUsage); //- noJobschedule;//(Add penalty)

subject to {
    // for alternative options present for job and machine
    forall(j in jobs)    
      CT1: alternative(nJobs[j], all ( w in jobDuration: j.jobID == w.jobID.jobID)altWcJob[w]);
    
        
    // no overlap constraint: Every workcenter can run only one job at a time 
    forall(w in workCenters)
      {
      CT2: noOverlap(workcenter[w]);
       }                  
       
    //Start testing of job immediately after assembly
    forall(j in jobs:j.isAssembly == 1, j1 in jobs: j1.jobID == j.jobID + 1000)
      {
        CT3_5: startOf(nJobs[j1]) == endOf(nJobs[j]);     
       }    
    
    //Fixed Lock Jobs(Hard Constraint)
    forall(j in jobs: j.Lock == 1 && j.isAssembly == 1)
      CT3: startOf(nJobs[j]) == j.CurrentSolution;    
      
          
    //EndTime of Job Less than 30 + deadline
    forall(j in jobs: j.isAssembly == 0)
      CT31: endOf(nJobs[j]) <= j.Deadline + 30;    
    }

    

execute writeresults
{
for(var w in jobDuration)
    {
        if (altWcJob[w].end > 0)
        {
            workCenterJobAssignment.add(w.jobID.jobID,w.workCenterID1.WorkcenterID, w.workCenterID2.WorkcenterID,w.workCenterID3.WorkcenterID,altWcJob[w].start,altWcJob[w].end);    
            writeln (w.jobID.jobID+" "+w.workCenterID1.WorkcenterID+" "+w.workCenterID2.WorkcenterID+" "+w.workCenterID3.WorkcenterID+" "+altWcJob[w].start+" "+altWcJob[w].end)
            
        }            
    
    }

}

        

 

#CPOptimizer
#DecisionOptimization

Originally posted by: PhilippeLaborie

Hello,
I think the modelization of decision variables and constraints is ok.
Instead of:
  startOf(nJobs[j1]) == endOf(nJobs[j]); 
You could use:
  endAtStart(nJobs[j],nJobs[j1]);
Which is directly handled by the engine as a temporal constraint.
Note that your formulation will automatically be reformulated as the second form at presolve, 
so it should not change the performance very much, but if possible it is always good to provide the most efficient formulation.

In fact, what could be improved is the formulation of the objective expressions. 

The first thing is that I do not really understand is the formulation of the earli (same for late and non-edit moved jobs) costs:

//Sum of Late Jobs
dexpr float SumofLateJobs = sum(j in testjobs) ( maxl(endOf(nJobs[j])-j.Deadline,0) / maxl(endOf(nJobs[j])-j.Deadline,0.1) );

This expression is 0 if the job ends before j.Deadline an 1 if it ends after, so why not just use: 
dexpr int SumofLateJobs = sum(j in testjobs) (endOf(nJobs[j]) > j.Deadline);
That would propagate better in the engine.

In fact, more generally, you should try to factorize the start and end expressions in the global objective, and also to exploit the "absence value" in expressions on interval variables when possible.

Except for the WorkcenterUsage, all the other costs are temporal costs expressed on the start and end of jobs nJobs[j].

Let's take the example of the part of the cost that depends on end time:

// Distance from SRD
dexpr float DistanceFromSRD = sum (j in jobs: j.isAssembly == 0) abs(endOf(nJobs[j])-presenceOf(nJobs[j])*(j.SRD));
// Distance from the deadline
dexpr float DistanceFromDeadline = sum (j in jobs: j.isAssembly == 0) abs(endOf(nJobs[j])-presenceOf(nJobs[j])*(j.Deadline));
// Sum of Late Jobs
dexpr float SumofLateJobs = sum(j in testjobs) (maxl(endOf(nJobs[j]) - j.Deadline,0)/maxl(endOf(nJobs[j]) - j.Deadline,0.1));

minimize (0.1*DistanceFromSRD + 0.2*DistanceFromDeadline + 200*SumofLateJobs + ...;

You could model all these 3 terms as the sum of a piecewise linear function evaluated at the end time of nJobs[j], with a specific value when nJobs[j] is absent (well, here it is declared as always being present in your model, but as you mention presenceOf(nJobs[j]), I suspect that it could be optional):

pwlFunction F[j in Jobs] = // Define function
float C[j in Jobs] = // Define non-execution cost (if needed)

dexpr float endCost = sum(j in jobs) endEval(nJobs[j],F[j],C[j]);

And you could do something similar for the cost expressions on the start:

//Sum of Early Jobs
dexpr float SumofEarlyJobs = sum(j in assemblyjobs) (maxl(j.Early - startOf(nJobs[j]),0)/maxl(j.Early - startOf(nJobs[j]),0.1));

//Sum of NonEdit Jobs That are Moved
dexpr float SumofNonEditJobsMoved = sum(j in assemblynoneditablejobs)abs(startOf(nJobs[j]) - j.CurrentSolution)/maxl(abs(startOf(nJobs[j]) - j.CurrentSolution),0.1);

Also, one additional remark suggested by the form of the objective function: 

minimize (0.1*DistanceFromSRD + 0.2*DistanceFromDeadline + 10*SumofEarlyJobs + 200*SumofLateJobs + 50*SumofNonEditJobsMoved + 0.01*WorkcenterUsage); //- noJobschedule;//(Add penalty)

If the objective can be decomposed in some lexicographical form (first minimize cost1, then for a given cost1, minimize cost2, etc.), then you could use a lexicographical objective in CPO, see staticLex(cost1,cost2,...). 

If the above does not help, could you also attach one data instance so that we can run your model, together with the objective value found by the MIP? 

#CPOptimizer
#DecisionOptimization