Originally posted by: SystemAdmin

[Optimizatron said:]

I need some genious help... working on a model which schedules jobs with the goal of minimizing resource usage, while meeting job time windows.  My formulation is below... seems like it should work, but I have a syntax error telling me that I can't use the dvar for job starting time to define a summation range (in the first constraint).  Any workarounds or alternative formulations for this?

int numJobs = ...;
range Jobs = 1..numJobs;
int numPeriods = ...;
range Periods = 1..numPeriods;
int earliestStart[Jobs] = ...;
int latestStart[Jobs] = ...;
int serviceTime[Jobs] = ...;

dvar boolean startJob[Jobs][Periods];
dvar boolean busyResource[Jobs][Periods];
dexpr int startTime[j in Jobs][t in Periods] = t*startJob[j][t];

minimize maxl (sum (t in Periods, j in Jobs)busyResource[j][t]);

subject to  {
       
        forall (j in Jobs)
        sum (t in Periods:startTime[j][t]<=t<=t+serviceTime[j]+1) busyResource[j][t]== serviceTime[j];<br />       
        forall (j in Jobs)
        sum (t in Periods:earliestStart[j]<=t<=latestStart[j])startJob[j][t]==1;<br />
};

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

[dgravot@noos.fr said:]

Hello,

You can't use a decision variable (or expression) as an indexer or a filter.
Looking at your model, I have the feeling all the job are to be executed . Indeed, the second constraint forces you to choose a startTime in the time window for each job, then the job will consume a fix amount of resource from its start till start+serviceTime . Therefore, there is simply nothing to optimize !

Usually for this kind of scheduling problem, one is interested in the earliest completion time of the latest job to be executed, or some other objectives (earliness, tardiness, number of completed jobs if not all of them can be processed), with respect to limited resources. Since in your model, you do not have resource, why don't you schedule all the jobs at their earliest start ?

You may take interest in reading ILOG surveys on comparing CP and MILP approaches for detailed scheduling . I think there is some document or presentation (unfortunately the link seems broken today) on http://www.ilog.com/products/cpoptimizer/ .

Hope this helps
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

[jfk said:]

Hello,
0. indeed as David stated, you can't use variable in a filter of a range. The range has to be computable at model extraction time.
1. the dexpr int startTime[j in Jobs][t in Periods] = t*startJob[j][t]; would say that the condition startTime[j ][t] <=t; is to have 1<=startJob[j][t] what you can post as a constraint separately; and t<=t+serviceTime[j]+1 is always true if serviceTime is positive...<br />2. you can't sum up busyReseource since it is a boolean, so turn it into a 0..1 variable then it works
3. well, maxl is for ints or floats, besides it can be used in script not in a model (I didn't get the logic why you would use maximization for a sum... the sum gives 1 value, then on what set do you want to get the maximal value?)... I guess you want to minimize the makespan and this is the reason you created startTime expression (the later you start the higher (t) value it gets. Then simply you can sum up and minimize it. Or as David said you can minimize the latest finishing job (create a "variable" that is upperbound on every job: post constraint like ...<="variable" and then minimize this "variable")<br />
a working code:

int numJobs = ...;
range Jobs = 1..numJobs;
int numPeriods = ...;
range Periods = 1..numPeriods;
int earliestStart[Jobs] = ...;
int latestStart[Jobs] = ...;
int serviceTime[Jobs] = ...;

dvar int startJob[Jobs][Periods] in 0..1;
dvar int busyResource[Jobs][Periods] in 0..1;
dexpr int startTime[j in Jobs][t in Periods] = t*startJob[j][t];

minimize
  sum(j in Jobs, t in Periods) startTime[j][t];

subject to  {
  forall(j in Jobs)
      sum(t in Periods) busyResource[j][t] == serviceTime[j];
 
  forall (j in Jobs)
      sum (t in Periods: earliestStart[j]<=t<=latestStart[j]) startJob[j][t]==1;<br />};


4. David rightfully points you to CP Optimizers since scheduling problems usually can be solved much more efficiently with CPO then with math programming approaches. you can find lots of scheduling examples (in OPL6.x) - starting with sched... - in the distribution.

I hope it helps

cheers

#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

[dgravot@noos.fr said:]

Hello,

You can calculate the resource usage at any time point of your horizon, and then minimize it through the max or the sum over the horizon.

a MILP approach :


int numJobs = ...;
range Jobs = 1..numJobs;
int numPeriods = ...;
range Periods = 1..numPeriods;
int earliestStart[Jobs] = ...;
int latestStart[Jobs] = ...;
int serviceTime[Jobs] = ...;

dvar int startJob[Jobs][Periods] in 0..1;
dvar int+ resUsage[Periods];

minimize
  sum(t in Periods) resUsage[t];

subject to  {
  forall(t in Periods)//each job j that begins from t-serviceTime[j]+1 till t use one unit of resource at time t
      resUsage[t] == sum(j in Jobs,t2 in maxl(0,t-serviceTime[j]+1)..t) startJob[j][t2];
 
  forall (j in Jobs)
  {
      sum (t in Periods: earliestStart[j]<=t<=latestStart[j]) startJob[j][t]==1;<br />      forall(t in Periods : earliestStart[j]>t || t>latestStart[j]) startJob[j][t]==0;
  }
};


then a CP approach is more elegant and less consuming since you don't need to sample the horizon, creating far more less variables. However, you probably have to write a script around this model in order to iterate over a parameter in order to minimize the resource usage. Indeed minimize a "cumulFunction" is not allowed.


using CP;

int numJobs = ...;
range Jobs = 1..numJobs;
int numPeriods = ...;
int earliestStart[Jobs] = ...;
int latestStart[Jobs] = ...;
int serviceTime[Jobs] = ...;

dvar interval job[j in Jobs] size serviceTime[j];
cumulFunction resUsage = sum(j in Jobs) pulse(job[j],1);

int boundValue = ...;//to be decreased in a loop

subject to  {
  resUsage <= boundValue;<br /> 
  forall(j in Jobs)
      earliestStart[j] <= startOf(job[j]) <= latestStart[j];<br />};

#DecisionOptimization
#MathematicalProgramming-General