1
$\begingroup$

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.

$\endgroup$

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.