I have a scheduling problem that I am not sure is a known variant with known algorithms. It does appear like bin packing problem at first, but after imposing the constraints, I am not sure what it becomes.

There are $n$ atomic Jobs, $J_1, J_2, ... J_n$, each with same length, say 1-hour.

These jobs have weighs, $w_1, w_2, w_3, ... w_n$

The scheduling time is divided into interval of same length (1-hour) $t_1, t_2, ... t_T$

During each scheduling interval, $t_i$, a set of Jobs can be run in parallel as long as their total weight remains at or below a constraint $C$ .

(If we were just required to schedule these jobs and finish everything at the earliest possible time, this would exactly be a regular bin-packing problem.)

However, we have a release time and deadline constraint on the jobs as follows:

For each job, such as $J_i$, there are two set of constraints:

  • $H_{i,j}$ => The maximum number of times job $i$ can be executed in time interval $t_1$ to $t_j$
  • $L_{i,j}$ => The minimum number of times job $i$ should be executed in time interval $t_1$ to $t_j$

In other words, each Job must be run multiple times but should respect the above constraints.

It might be helpful to note that, for a given $i$ (that is for a given job), the $H_{i,j}$ and $L_{i,j}$ are staircase functions with constant width.

The problem is to check if it is possible to schedule the jobs (into the time slots $t_1, t_2, ... t_T$ by satisfying the above constraints)

Does this problem sound familiar?

Thank you.


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.