Topic
• 3 replies
• Latest Post - ‏2013-08-05T07:17:08Z by PhilippeLaborie
Nathalie
2 Posts

# Pinned topic Scheduling of moldable jobs

‏2013-07-30T10:55:55Z |

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?

Best wishes,
Nathalie

• PhilippeLaborie
45 Posts

#### Re: Scheduling of moldable jobs

‏2013-08-05T07:17:08Z
• Nathalie
• ‏2013-08-04T17:47:49Z

Dear Philippe,

thanks a lot for your reply: that was exactly, what I needed for the first step. I was running your example in the last two days with 16 threads until it run out of memory. Is there a possibility to reduce the search space even more? For example by introducing time steps or are there other possibilities?

Best wishes,
Nathalie

Hello,

It is very possible that  CP Optimizer cannot prove optimality for this problem. In general, providing optimality proofs for general scheduling problems is something very difficult. Here, even if the problem is small, the search space is not reduced very much by propagation because the objective function is a weighted sum. You can try to increase the inference level of cumul functions in the engine but it probably won't be enough to prove optimality in reasonable time:

execute {
cp.param.CumulFunctionInferenceLevel = "Extended";
}

In general, the best will be to use a time limit or any other type of limit to stop the search and return the best incumbent solution:

execute {
cp.param.TimeLimit = 30;
}

Philippe

• PhilippeLaborie
45 Posts

#### Re: Scheduling of moldable jobs

‏2013-07-30T14:09:31Z

Hello,

I may be missing something but it seems to me you over-constrain and complexify the problem by seeing it as a 2D packing problem. If cores are identified by indexes 1,2,3,...,n, you implicitly impose that a job has to use contiguous cores (for instance {3,4,5} and not {3,4,6}) which is probably not required in the real problem.

I would just model the problem as a "classical" scheduling problem where cores are a cumulative resource and each job requires a certain number of cores. This is easy to model with the notion of cumulFunction in CP Optimizer.

Here is the corresponding model:

using CP;

int nCores = 8;
int QueueLength = 2050000;
int nJobs  = 39;
range jobs = 1..nJobs;

int RunTimes[jobs] = [297372, 297456,...];
int NumberOfProcesses[jobs] = [6, 6, ...];

dvar interval job[i in jobs] optional in 0..QueueLength size RunTimes[i];

cumulFunction coreUsage = sum(i in jobs) pulse(job[i], NumberOfProcesses[i]);

maximize sum(i in jobs) presenceOf(job[i])*RunTimes[i]*NumberOfProcesses[i];
subject to {
coreUsage <= nCores;
}

CP Optimizer fastly computes some solutions that use most of the cores over the schedule horizon.

Philippe

• Nathalie
2 Posts

#### Re: Scheduling of moldable jobs

‏2013-08-04T17:47:49Z

Hello,

I may be missing something but it seems to me you over-constrain and complexify the problem by seeing it as a 2D packing problem. If cores are identified by indexes 1,2,3,...,n, you implicitly impose that a job has to use contiguous cores (for instance {3,4,5} and not {3,4,6}) which is probably not required in the real problem.

I would just model the problem as a "classical" scheduling problem where cores are a cumulative resource and each job requires a certain number of cores. This is easy to model with the notion of cumulFunction in CP Optimizer.

Here is the corresponding model:

using CP;

int nCores = 8;
int QueueLength = 2050000;
int nJobs  = 39;
range jobs = 1..nJobs;

int RunTimes[jobs] = [297372, 297456,...];
int NumberOfProcesses[jobs] = [6, 6, ...];

dvar interval job[i in jobs] optional in 0..QueueLength size RunTimes[i];

cumulFunction coreUsage = sum(i in jobs) pulse(job[i], NumberOfProcesses[i]);

maximize sum(i in jobs) presenceOf(job[i])*RunTimes[i]*NumberOfProcesses[i];
subject to {
coreUsage <= nCores;
}

CP Optimizer fastly computes some solutions that use most of the cores over the schedule horizon.

Philippe

Dear Philippe,

thanks a lot for your reply: that was exactly, what I needed for the first step. I was running your example in the last two days with 16 threads until it run out of memory. Is there a possibility to reduce the search space even more? For example by introducing time steps or are there other possibilities?

Best wishes,
Nathalie

• PhilippeLaborie
45 Posts

#### Re: Scheduling of moldable jobs

‏2013-08-05T07:17:08Z
• Nathalie
• ‏2013-08-04T17:47:49Z

Dear Philippe,

thanks a lot for your reply: that was exactly, what I needed for the first step. I was running your example in the last two days with 16 threads until it run out of memory. Is there a possibility to reduce the search space even more? For example by introducing time steps or are there other possibilities?

Best wishes,
Nathalie

Hello,

It is very possible that  CP Optimizer cannot prove optimality for this problem. In general, providing optimality proofs for general scheduling problems is something very difficult. Here, even if the problem is small, the search space is not reduced very much by propagation because the objective function is a weighted sum. You can try to increase the inference level of cumul functions in the engine but it probably won't be enough to prove optimality in reasonable time:

execute {
cp.param.CumulFunctionInferenceLevel = "Extended";
}

In general, the best will be to use a time limit or any other type of limit to stop the search and return the best incumbent solution:

execute {
cp.param.TimeLimit = 30;
}

Philippe