Dear all,

I want to use CP Optimizer for a scheduling problem and I need some help:

The scheduling problem deals with jobs, which can be executed with an arbitrary number of processes (moldable jobs). They do no scale linearly, such that the product runtime*numberOfProcesses slightly increases with ascending number of processes. A job can be interpreted as a rectangle, where the x dimension presents the number of processes and y dimension corresponds to the run time. A node is available for a certain period of time and provides a certain number of cores. This defines the maximum capacity of the schedule. Within a schedule jobs can be arbitrarily placed: there are no dependencies and the aim is to place as many jobs as possible. I want to sort the jobs depending on their number of processes and place them via the bottom left algorithm. Afterwards I want to modify the number of processes for each job in order to see whether more jobs can be placed within the schedule or not.

I started first with a little exercise (I used therefore sched_square.mod example). In this little exercise I do not modify the number of processes of the jobs; The array of runtimes and number of processes are already sorted and then the items shall be placed within a schedule

I wrote the following code:

using CP;

int nCores = 8;

int QueueLength = 2050000;

int nJobs = 39;

range jobs = 1..nJobs;

int RunTimes[jobs] = [297372, 297456, 297138, 297852, 304158, 298332, 304854, 294180, 296646, 297456, 297762, 299640, 295416, 295478, 306992, 274804, 290384, 320218, 306992, 278392, 320012, 267350, 253830, 253830, 315286, 283656, 876715, 412004, 874491, 886845, 880158, 869362, 842265, 377214, 873191, 896248, 885849, 889995, 751149];

int NumberOfProcesses[jobs] = [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];

dvar interval x[s in jobs] optional size NumberOfProcesses[s];

dvar interval y[s in jobs] optional size RunTimes[s];

execute {

var f = cp.factory;

cp.setSearchPhases(f.searchPhase(x),

f.searchPhase(y));

};

maximize sum(i in jobs) (endOf(y[i]) - startOf(y[i])) * (endOf(x[i])-startOf(x[i]));

subject to {

// place the first job in the bottom left corner and each following jobs should be either placed next to the right or on the top of the current job

startOf(x[1]) == 0;

endOf(x[1]) == NumberOfProcesses[1];

startOf(y[1]) == 0;

endOf(y[1]) == RunTimes[1];

forall(i in 1..nJobs-1)

(endOf(x[i]) <= startOf(x[i+1]) || endOf(y[i]) <= startOf(y[i+1]));

// constraints for the boundaries

forall( i in jobs){

presenceOf(x[i]) == presenceOf(y[i]);

startOf(x[i]) <= (nCores - NumberOfProcesses[i]) && endOf(x[i]) <= nCores;

startOf(y[i]) <= (QueueLength - RunTimes[i]) && endOf(y[i]) <= QueueLength;

}

// total capacity cannot be exceeded

sum(i in jobs) ((endOf(y[i]) - startOf(y[i])) * (endOf(x[i])-startOf(x[i]))) <= (nCores * QueueLength);

/* //non overlapping contraint

forall(ordered i, j in jobs)

endOf(x[i]) <= startOf(x[j]) ||

endOf(x[j]) <= startOf(x[i]) ||

endOf(y[i]) <= startOf(y[j]) ||

endOf(y[j]) <= startOf(y[i]);*/

When using the non overlapping constraint,

forall(ordered i, j in jobs

endOf(x[i]) <= startOf(x[j]) ||

endOf(x[j]) <= startOf(x[i]) ||

endOf(y[i]) <= startOf(y[j]) ||

endOf(y[j]) <= startOf(y[i]);

the code runs several days until it crashes. So I want to reduce the calculation time and just place the jobs with bottom left algorithm and I defined the following constraint:

startOf(x[1]) == 0;

endOf(x[1]) == x[1];

startOf(y[1]) == 0;

endOf(y[1]) == y[1];

forall(i in jobs, j in jobs: j > i )

(endOf(x[i]) <= startOf(x[j]) || endOf(y[i]) <= startOf(y[j]));

I always get the error that the model does not have a solution. Can someone explain me why?

Furthermore I want to know how i can extend the model for the given scheduling problem? I am not very familiar with CP Optimizer, so I don't know which kind of constructs are supported. I was considering to add two more decision variables:

dvar interval JobDetails1[s in min..nCores] size JobRunTimes[s],

dvar interval JobDetails2[s in min..nCores] size s,

which describe the interval of number of processes within which a job can be executed and the correspondent runtimes.

The solver should then modify the number of processes of each job and define their position within the schedule. Is there a way to assign a variable to another variable? Something like:

dvar interval x[j on jobs] optional size JobDetails1[j]

dvar interval y[j on jobs] optional size JobDetails2[j]

Is there a way how to model this problem differently? Is such a problem anyway feasible with CP optimizer?

Many thanks in advance for your help!

Best wishes,

Nathalie