# How to minimize number of machines required to serve tasks, and return the schedules for each machine?

The problem I'm trying to solve is the following:

• Given $$t\in \{1,2,3....T\}$$ tasks, integer.
• Tasks have release times $$r_t$$ and deadlines $$d_t$$, and processing times $$p_t$$, all continuous, real-valued.
• Minimize the number of machines required to process the tasks, assuming all machines are identical, and pre-emption is not allowed, and machines can only process one job at a time.
• Also, the schedule itself should be returned - not just the minimum number of machines.

What would be an equivalent MIP or MILP for this problem?

I've seen a similar question however, their problem is much more simple for two reasons:

1. The schedule need not be returned
2. Time is discrete.

EDIT: If it makes the problem easier, I'm okay with a solution that has discrete time intervals, but it's not clear to me whether that makes the MILP formulation easier or more difficult.

• Is there a maximum total time? If not, the optimal solution is always one machine. Aug 30, 2023 at 12:09
• @Reinderien In the worst case, the time windows are so restrictive that each task needs its own machine. Aug 30, 2023 at 12:41

The problem you are facing is a variant of parallel machine scheduling problems with some limitations like release time, due date, and also unknown identical machines. This problem can be modeled as a mixed integer program as follows:

\begin{align*} \ min\ Z = &\ Cmax + \sum_{m} Nbmachines_{m} \\ &\text{s.t.} \\ &\ \sum_{m} x_{j,m} = 1 \quad \forall j \in T \quad (1)\\ &\ \sum_{j} x_{j,m} p_{j} \leq AvailableDuration*Nbmachines_{m} \quad \forall m \in M \quad (2)\\ &\ start_{j} \geq r_{j} \quad \forall j \in T \quad (3)\\ &\ start_{j} + p_{j} \leq Cmax \quad \forall j \in T \quad (4)\\ &\ start_{j} + p_{j} = finish_{j}\quad \forall j \in T \quad (5)\\ &\ finish_{j} \leq d_{j} \quad \forall j \in T \quad (6)\\ &\ (x_{i,m} \land x_{j,m}) \implies ((start_{i} + p_{i} \leq start_{j}) \lor (start_{j} + p_{j} \leq start_{i})) \quad \forall i, j \in T, m \in M: i \lt j \quad (7)\\ &\ x_{j,m} \in \mathbb{B}, Nbmachines_{m} \in \mathbb{B}, start_{j}, finish_{j} \in \mathbb{R}^+\\ \end{align*}

I tried the following example:

jobs = {"j01", "j02", "j03", "j04", "j05", "j06"};
machines = {"machine_1", "machine_2", "machine_3", "machine_4"};
p[jobs] = [4, 9, 7, 5, 5, 4];
r[jobs] = [61, 59, 0, 21, 6, 0];
d[jobs] = [65, 80, 20, 40, 15, 10];
available_duration = 100;


and the results would be:

Some points:

• The lower bound on the available_duration without having the precedence constraint should be $$Max(p_{j}+r_{j}) \quad \forall j \in T$$.
• The due date is already calculated in the simplest form while in the real situation almost comes with an appropriate penalty in the objective function.
• There is no need to predetermine the overlap between the tasks.
• Time index formulation usually provides a tighter lower bound, while adding a huge number of binary variables when the scale of the problem increases. In this case, usually, it needs to have a solving paradigm like the decomposition method.
• What is the set $M$? Is it pre-determined to have some upper limit? What if you don't know the upper limit $M$? Aug 31, 2023 at 7:55
• @underdog987, yes. Aug 31, 2023 at 10:31
• You should define an upper bound and let the solver decides how many machines will require. Aug 31, 2023 at 10:33