Scheduling: Tasks changing the state of the executing machine

Question

I have a scheduling problem in which machines consume their battery when executing tasks and charge their battery when not executing tasks. A single task has to be executed in one go (no recharging pauses). Battery consumption/charging happens at a fixed rate. Tasks have a fixed interval and the goal is to maximize the number of executed tasks.

I'm want to model this problem with constraint programming, in which I have basic knowledge. The problem is that no scheduling examples that I have encountered have tasks that alter the state of the executing machine (which determines when that machine can accept a subsequent task).

How would one model such a problem (specifically the consumption/charging part)? Is it suitable for constraint programming at all?

Answer 1

In OptaPlanner, I'd start from the task assigning example and use a shadow variable to track the remaining battery level of every task. Then a simple constraint can check if it's ok to schedule that task on that machine:

from(Task.class)
.filter(task -> task.getRemainingBatteryLevel() < task.getRequiredBatteryLevel())
.penalize("Battery", ofHard(1));

Answer 2

In CP Optimizer, I would use "typeOfPrev/Next" expressions to track the level of the battery at the endpoints (start and end) of the activities on the resource.

Here is a simple example on just one machine (in OPL but you can write the same model in Java, Python or C++). I assumed the battery consumption/production rate is 1. Activities are optional, have specific time-windows and the objective is to maximize the number of executed activities:

int N = 1000; // Number of activities
int C = 100;  // Battery capacity
int H = 30*N;

// Random data
execute {
  Opl.srand(1);
}
int D[i in 1..N] = 1+rand(50);
int S[i in 1..N] = rand(H - (H div 10));
int E[i in 1..N] = S[i]+D[i]+rand(H div 10);

dvar interval x[i in 1..N] optional in S[i]..E[i] size D[i]; // Optional activities x[i]
dvar int le[i in 0..N] in 0..C; // Battery level at the end of x[i]

dvar sequence seq in all(i in 1..N) x[i] types all(i in 1..N) i; // sequence of activities on the machine

execute {
  var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq)); 
}

maximize sum(i in 1..N) presenceOf(x[i]);
subject to {
  noOverlap(seq);
  le[0]==0;
  forall (i in 1..N) {
    le[i] == minl(C, le[typeOfPrev(seq,x[i],0)] + (startOf(x[i],D[i])-endOfPrev(seq,x[i],0)))-D[i];
    // When x[i] is absent, by the above constraint: le[i]=0
  }
}

Note that on this type of problem, it can be useful to use search phases on the sequence variables so that the default search will work on sequencing the interval variables of the sequences before fixing their actual start/end values.

Of course, I suppose that your problem is more complex and these batteries must be integrated in a more complex scheduling problem. So in order to be more realistic, I tried for fun to add these battery constraints on all the machines of a "classical" job-shop scheduling problem. The only change is to add the 'le' variables on each operation on the machines. On this tiny instance, CP Optimizer proves optimality of the solution (with makespan 79).

int nbJobs = 6;
int nbMchs = 6;

range Jobs = 1..nbJobs;
range Mchs = 1..nbMchs; 
// Mchs is used both to index machines and operation position in job

tuple Operation {
  int mch; // Machine
  int pt;  // Processing time
};

Operation Ops[Jobs][Mchs] = [
 [ <6,4>, <2,3>, <5,3>, <4,2>, <1,1>, <3,2> ],
 [ <2,3>, <1,8>, <6,7>, <3,2>, <5,9>, <4,3> ],
 [ <4,1>, <5,9>, <2,9>, <1,7>, <6,5>, <3,5> ],
 [ <4,8>, <5,2>, <2,1>, <6,7>, <3,8>, <1,9> ],
 [ <2,6>, <4,2>, <5,5>, <6,5>, <1,3>, <3,1> ],
 [ <5,10>, <3,4>, <1,4>, <4,3>, <2,2>, <6,3> ]
];

int C = 10; // Battery capacity

int O[j in Jobs][m in Mchs] = first({o | o in Mchs : Ops[j][o].mch == m}); // Operation of job j on machine m

dvar interval op[j in Jobs][o in Mchs] size Ops[j][o].pt;
dvar sequence mchs[m in Mchs] 
  in    all(j in Jobs, o in Mchs : Ops[j][o].mch == m) op[j][o]
  types all(j in Jobs, o in Mchs : Ops[j][o].mch == m) j;
          
dvar int le[m in Mchs][j in 0..nbJobs] in 0..C; // Battery level at the end of operation of job j on machine m

minimize max(j in Jobs) endOf(op[j][nbMchs]);
subject to {
  forall (m in Mchs) {
    le[m][0] == 0;
    noOverlap(mchs[m]);
    forall (j in Jobs) {
      le[m][j] == minl(C, le[m][typeOfPrev(mchs[m],op[j][O[j][m]],0)] + (startOf(op[j][O[j][m]])-endOfPrev(mchs[m],op[j][O[j][m]],0)))-Ops[j][O[j][m]].pt;
    }      
  }    
  forall (j in Jobs, o in 1..nbMchs-1)
    endBeforeStart(op[j][o], op[j][o+1]);
}