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

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?

Many thanks in advance for your help!

Best wishes,
Nathalie

 

  • PhilippeLaborie
    PhilippeLaborie
    17 Posts
    ACCEPTED ANSWER

    Re: Scheduling of moldable jobs

    ‏2013-07-30T14:09:31Z  in response to Nathalie

    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
      Nathalie
      2 Posts
      ACCEPTED ANSWER

      Re: Scheduling of moldable jobs

      ‏2013-08-04T17:47:49Z  in response to PhilippeLaborie

      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
        PhilippeLaborie
        17 Posts
        ACCEPTED ANSWER

        Re: Scheduling of moldable jobs

        ‏2013-08-05T07:17:08Z  in response to 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