# Scheduling tasks to minimize the total number of utilized cores

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?

• What constraint violations would you allow? Early release? Late completion? Not performing a task at all?
– prubin
Feb 18, 2023 at 17:17
• @prubin I have send you an email Feb 18, 2023 at 19:35
• 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.
– prubin
Feb 18, 2023 at 23:38
• @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) Feb 19, 2023 at 0:59

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$$

• 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 Feb 18, 2023 at 19:11
• Also doesn't your approach scale pretty bad? As I am interested in something which gives more close to polynomial solution Feb 18, 2023 at 19:22
• 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. Feb 18, 2023 at 20:58