The problem consists of a set of tasks requiring some resource from renewable resource pool. The goal is to complete all tasks in the given planning horizon, so that the number of resource used is minimised. The main constraint is no overlap of tasks for the same resource.
The code below does not scale well if I increase the number of tasks.
There should be a simple optimal solution: to allocate the resource 1 to 15 to all tasks. But the solver seems to struggle to find it when n_tasks is higher than say 1000. I have tried a number of things with the search annotations, but no breakthrough so far.
Here is the model and data:
n_tasks = 3000;
duration = [1 | i in 1..n_tasks];
n_resources = 35;
number_resource_needed = [15 | i in 1..n_tasks];
t_max = 18000;
include "cumulative.mzn";
%-----------------------------------------------------------------------------%
% MODEL PARAMETERS
% Tasks
int: n_tasks; % The number of tasks
set of int: Tasks = 1..n_tasks; % The set of all tasks
array[Tasks] of int : duration ; % The task durations
% Resources
int: n_resources;
set of int: Resources = 1..n_resources;
array[Tasks] of int: number_resource_needed; % The resource requirements
% Maximum duration
int: t_max;
%~~~~~~~~~~~~~~~~~
% MODEL VARIABLES.
%~~~~~~~~~~~~~~~~~
array [Tasks] of var 1..t_max: start; % The start times
array[Tasks, Resources] of var 0..1: resource_allocation; %Selection of resources per task.
%~~~~~~~~~~~~~~~~~
% CONSTRAINTS
%~~~~~~~~~~~~~~~~~
% Number of Resources per Task constraint
constraint forall(t in Tasks) (
sum(r in Resources) (resource_allocation[t, r]) = number_resource_needed[t]
);
% Constraint allocated to only one task at a time
constraint forall(r in Resources)(
cumulative(start, duration, [resource_allocation[t, r] | t in Tasks], 1)
);
var int: objective = sum(r in Resources) (r * max([resource_allocation[t, r] | t in Tasks]));
var int: nb_active_workers = sum(r in Resources) (max([resource_allocation[t, r] | t in Tasks]));
% solve minimize objective;
solve :: seq_search([
int_search(resource_allocation, input_order, indomain_max),
int_search(start, input_order, indomain_min),
])
minimize objective;
output ["objective = \(objective) \n"];
output ["nb_active_workers = \(nb_active_workers) \n"];
I have used Chuffed, and different options.
My results:
n_tasks = 100, optimal found in 34s
n_tasks = 500, optimal found in 3m 43s
n_tasks = 3000, first solution 2m 40s, optimal not found at 4m 00s
I would like to see a first solution faster, and also the optimal faster.