2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ At the moment, I am not sure about CP but, are you trying to add a battery consumption constraint based on the task required consumption? For example suppose, each task has a specific battery consumption that the whole needs should be less equal than the machine's battery capacity. $\endgroup$ – A.Omidi Mar 11 at 9:02
  • $\begingroup$ I think it's more complex than that. A task can only be executed on a machine if the battery level of that machine (at the start time of the task) is at least X. What makes it hard to model for me is that X depends on which tasks has been executed earlier on that machine. For example, TaskA drains the battery to 30, TaskB starts 20 minutes later and requires 50 battery. 20 minutes charging increases the battery by 10. Thus, TaskB can't be scheduled on that machine (since 30+10 is smaller than 50). $\endgroup$ – minisu Mar 11 at 10:23
3
$\begingroup$

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));
$\endgroup$
2
  • 1
    $\begingroup$ That are some quality resources, much appreciated! $\endgroup$ – minisu Mar 11 at 16:13
  • $\begingroup$ You're welcome :) We don't have an example that's exactly what you need, so it will still involve some modeling work. $\endgroup$ – Geoffrey De Smet Mar 11 at 17:24
2
$\begingroup$

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]);
}

Optimal solution with makespan 79

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.