schedulingconstraint-programmingminizinc

Task scheduling on multiple facilities - cumulative 'var opt error'


I'm having trouble with an implementation of the following CP formulation (full formulation of the problem can be found here (page 4/16))

CP formulation of the problem

My implementation seems like code below, but I'm having struggle with following error: MiniZinc: type error: no function or predicate with this signature found: 'comulative(array[int] of var opt int,array[int] of var opt int,array[int] of var opt int,int)'.

This is because array comprehension is affected by some var, in this case variable x.

Do you have any suggestions how to make cumulative constraint working with option variables or any possible workaround?

include "cumulative.mzn";
include "element.mzn";

int: numJ; % number of tasks
int: numI; % number of facilities

% Tasks
set of int: Tasks = 1..numJ;

% Facilities
set of int: Facilities = 1..numI;

% Max consumptions of facilities
array[Facilities] of int: C;

array[Tasks] of int: d; % due times
array[Tasks] of int: r; % release times
array[Facilities, Tasks] of int: c; % c[i,j] = consumption of task j at facility i
array[Facilities, Tasks] of int: p; % p[i,j] = processing time of task i at facility j
array[Facilities, Tasks] of int: F; % F[i,j] = fixed cost paid when task j is assigned to facility i

% start time's domain is an interval <0, maximum of due times>
array[Tasks] of var 0..max(d): s;

% assign task to a facility
% x[3] = 1 --> task 3 is assigned to facility 1
array[Tasks] of var 1..numI: x;

% something like a temporary processing time
% im not really sure about this
array[Tasks] of var 0..max(p): u;

constraint forall(j in Tasks)(
  element(
    x[j],
    [p[i,j] | i in Facilities],
    u[j]
  )
);


constraint forall(i in Facilities)(
  comulative(
    [s[j] | j in Tasks where x[j] == i],
    [p[i,j] | j in Tasks where x[j] == i],
    [c[i,j] | j in Tasks where x[j] == i],
    C[i]
  )
);




% A task cant start before its release time
constraint forall(j in Tasks)(s[j] >= r[j]);
% A task cant run longer than its due time
constraint forall(j in Tasks)(s[j] <= d[j] - u[j]);

% Minimize total cost
solve minimize sum(j in Tasks)(F[x[j],j]);

output [ "start: ", "\n", show(s), "\n", "facility: ", "\n" , show(x) , "\n"];

Simple data set:

C = [8, 8, 6, 5];

numJ = 12;
numI = 4;
r = [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2];

d = [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3];

c = [|8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, |8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, |6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, |5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, |];

p = [|1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |];

F = [|0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, |1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, |1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, |1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, |];

Solution

  • Even though you mentioned that you've found a solution, here's a version that use cumulative (opt version in "cumulative_opt.mzn").

    include "globals.mzn"; % includes the file "cumulative_opt.mzn"
    % ....
    
    constraint forall(i in Facilities)(
        cumulative(
        % [s[j] | j in Tasks where x[j] == i], % original
        % [p[i,j] | j in Tasks where x[j] == i], % original
        % [c[i,j] | j in Tasks where x[j] == i], % original
    
        [s[j] | j in Tasks where x[j] == i],
        [p[i,j] | j in Tasks], % <-- no condition clause here
        [c[i,j] | j in Tasks], % <-- no condition clause here
        C[i]
     )
    );