0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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:

enter image description here

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.
$\endgroup$
3
  • $\begingroup$ What is the set $M$? Is it pre-determined to have some upper limit? What if you don't know the upper limit $M$? $\endgroup$ Aug 31, 2023 at 7:55
  • $\begingroup$ @underdog987, yes. $\endgroup$
    – A.Omidi
    Aug 31, 2023 at 10:31
  • $\begingroup$ You should define an upper bound and let the solver decides how many machines will require. $\endgroup$
    – A.Omidi
    Aug 31, 2023 at 10:33

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.