I am trying to model a task scheduling with constraints, in order to understand which model or algorithm is better suited to compute an optimal solution.

Suppose I have $n$ jobs with CPU loads presented in Figure below:

CPU loads

Each CPU load features a peak during startup, due to the fact that each job needs to prepare its workspace (variables etc.) before starting to process data.

The cumulative load $CL$ is defined as the sum of all jobs loads at a specific moment.

The CPU is able to run all jobs at the same moment, i.e. the cumulative load $CL$ is sustainable by the CPU, but the CPU prefers to keep the load under a specific threshold, say $\gamma$.

To keep the cumulative load $CL$ below the $\gamma$ threshold for most of the time (ideally always below the threshold), the CPU may anticipate at no cost the start of specific processes, let's say $15ms$, $30ms$, $45ms$ or $60ms$ of anticipation.

My objective function is to minimize the anticipation of the processes startup, and the most important constraint is to keep the cumulative load $CL$ below the $\gamma$ threshold.

How can I model this problem?

  • $\begingroup$ What is your objective function? (What do you which to minimize? The total CPU time ?) $\endgroup$ – Kuifje Apr 7 '16 at 14:32
  • $\begingroup$ I edited my question with objective function and a constraint. The total CPU time may not be minimized, but the idea is to exploit the sustainable load of the CPU below $\gamma$, while anticipating processes startup as little as possible. Thanks $\endgroup$ – user21 Apr 7 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.