1
$\begingroup$

I currently have a scheduling algorithm which computes an approximate solution, say S, for the nominal scenario of a given problem instance, say N. Given that N changes in a way and becomes infeasible, I want to reuse S and complement it in a way so that:

  1. The method is able to compute a solution (by relaxing some of the constraints)
  2. The new solution violates a minimum amount of constraints.

The new problem essentially becomes the following: We have a set of tasks, each task with release time, deadline, duration, and a set of time slots. We can assign tasks to run in parallel and they are pre-emptible. Objective is to assign the tasks in a way that minimizes the total number of cores used.

Is someone aware of such scheduling problem in the literature or any suggestions how to address it?

$\endgroup$
4
  • $\begingroup$ What constraint violations would you allow? Early release? Late completion? Not performing a task at all? $\endgroup$
    – prubin
    Feb 18, 2023 at 17:17
  • $\begingroup$ @prubin I have send you an email $\endgroup$
    – Pia MiA
    Feb 18, 2023 at 19:35
  • $\begingroup$ I have not received it. I any case, it would be better to edit the question to clarify what constraint violations you have in mind. $\endgroup$
    – prubin
    Feb 18, 2023 at 23:38
  • $\begingroup$ @prubin you allow for more tasks to be scheduled in parallel and essentially becomes the problem I’ve mentioned above. I seek a good approximate approach (quicker than a IP) $\endgroup$
    – Pia MiA
    Feb 19, 2023 at 0:59

1 Answer 1

1
$\begingroup$

It sounds like a job scheduling problem. So say set of Tasks, $Z$, Time slots/cores $ T$. Define a continuous variable $ 0 \le x_{zt} \le 1$ that tracks units of task $z$ assigned to time slot $t$. Assuming each task can be broken down into smaller units and they must sum up to 1.
You may need a binary variable $ y_{z,t}$ to track time slots alloted to task for the duration. And a continuous var $ \delta$ to track maximum number of task units per time slot.

Then constraints like
$ \sum_t x_{z,t} = 1 $
$ y_{z,t} \le x_{z,t} \le My_{z,t}$
$ \sum_t y_{z,t} = D_z$

<you can have additional constraints for release here. am putting whatever you've posted>

$ \sum_z x_{z,t} \le \delta \ \ \forall t$: getting maximum of units in a time slot

Then min $\delta$

$\endgroup$
3
  • $\begingroup$ The cores is essentially how many units of a task we allow to be placed in the same timeslot and we don't have a limit for it but we seek the minimal possible number $\endgroup$
    – Pia MiA
    Feb 18, 2023 at 19:11
  • $\begingroup$ Also doesn't your approach scale pretty bad? As I am interested in something which gives more close to polynomial solution $\endgroup$
    – Pia MiA
    Feb 18, 2023 at 19:22
  • $\begingroup$ Ok edited it. Binary vars will make it NP-Hard but I am not sure if there's any other way to track time slots for task duration. $\endgroup$ Feb 18, 2023 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.