2
$\begingroup$

I have a scheduling problem. 20 hours of work load should be assigned to different days (max 4 days are available and the capacity of ech day is 8 hours max) $\sum_i h_i = 20$

$0 \leq h_i \leq 8$

enter image description here

The following picture shows the desirable and undesirable ways of assignment. How can I mathematically formulate it as MILP to use minimum number of days and fill them from left to right (using all capacity) ?

enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ No, $ℎ_1≥ℎ_2≥ℎ_3≥ℎ_4$ will allow 8 6 4 2 which is using 4 days instead of 8 8 4 (3 days) $\endgroup$
    – Optimization team
    Commented Aug 11, 2023 at 16:08
  • $\begingroup$ What if you don't define $h_4$ given that you know that you will need exactly $\big\lceil \frac{20}{8} \big\rceil=3$ days? And minimize the maximum slack $8-h_i$ with constraints $h_1\ge h_2 \ge h_3$. $\endgroup$
    – Kuifje
    Commented Aug 11, 2023 at 17:42
  • $\begingroup$ @Kuifje I think the OP wants a formulation that does not require an objective because these constraints are part of a larger problem that has its own objective. $\endgroup$
    – RobPratt
    Commented Aug 11, 2023 at 17:48
  • $\begingroup$ Also, minimizing the maximum slack subject to $\sum_i h_i=20$, $h_1 \ge h_2 \ge h_3$, and $h_4=0$ would yield $h_1=h_2=h_3=20/3$, which violates the desired rules. $\endgroup$
    – RobPratt
    Commented Aug 11, 2023 at 18:01

4 Answers 4

Reset to default
3
$\begingroup$

You want to enforce $h_i > 0 \implies h_{i-1} = 8$. You can do so by introducing binary variables $x_i$ and the following constraints: \begin{align} h_i > 0 &\implies x_i = 1 \\ x_i = 1 &\implies h_{i-1} = 8 \end{align} which you can linearize as: \begin{align} h_i &\le 8 x_i \\ 8 - h_{i-1} &\le 8(1-x_i) \end{align} More compactly: $$8 x_{i+1} \le h_i \le 8 x_i$$

The exact total workload should be distributed in different days :

$$\sum_i h_i =20$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ No, not all days can be 8 h, the sum of them should be 20h, so the last one will be 4 $\endgroup$
    – Optimization team
    Commented Aug 11, 2023 at 16:45
  • $\begingroup$ I don’t understand your comment. My formulation does not force all days to be 8. Note the $i$ versus $i-1$ subscripts. $\endgroup$
    – RobPratt
    Commented Aug 11, 2023 at 16:59
  • $\begingroup$ Thanks Rob. I had misunderstood your answer. I think it is correct $\endgroup$
    – Optimization team
    Commented Aug 11, 2023 at 17:33
1
$\begingroup$

$ -20x_i \le 20-\sum_{d}^{i-1} h_d - 8 \le 20(1-x_i)$

$ 8(1-x_i) \le h_i \le 20-\sum_{d}^{i-1} h_d $

where $x_i$ is a binary

Improve this answer
$\endgroup$
1
$\begingroup$

If the work load can be discretized, you could model this like a bin packing problem.

If the time granularity is for example the hour, let $x_{ij}$ be a binary variable that takes value $1$ if and only if hour $i$ is assigned to day $j$. And let $y_j$ be a binary variable that takes value $1$ if day $j$ is "used".

You want to minimize $\sum_j y_j$ subject to:

  • Each hour must be assigned to a day: $$ \sum_{j} x_{ij}=1 \quad \forall i $$
  • Each day has a maximum of $8$ hours available: $$ \sum_{i} x_{ij}\le 8y_j \quad \forall j $$
  • Day $j$ cannot be used if day $j-1$ is not: $$ y_j \le y_{j-1} \quad \forall j>1 $$
  • Capacity must be saturated before using a new day: $$ \sum_i x_{ij}\ge 8y_{j+1} \quad \forall j\neq 4 $$
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, @Kuifje. It is definitely very similar to the bin-packing problem. $\endgroup$
    – A.Omidi
    Commented Aug 12, 2023 at 19:34
0
$\begingroup$

\begin{array}{ll} \text{minimize} & \sum_{i} y_i \\ \text{subject to} \\ & \sum_{i} h_i = 20 \\ & h_i \ge h_{i+1}, \forall i \in \{1,2,3\} \\ & 8y_i \ge h_i, \forall i \\ & h_i \le 8, \forall i \\ & y_i \in \{0,1\} , \forall i\\ & h_i \ge 0, \forall i \end{array}

That should be worked!

The following picture is the result from SCIP. enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Your formulation allows $h_i=20/3$ for all $i$. $\endgroup$
    – RobPratt
    Commented Sep 5, 2023 at 15:32
  • $\begingroup$ @RobPratt Thanks for your remind. I think there are two ways can avoid this problem. First way is you proposed before. Second one is introducing another binary variables which meaning whether exist any remaining capacity or not. And adding new terms in objective function to minimize it. However, I think the first modeling technique would more efficient. $\endgroup$
    – ytsao
    Commented Sep 5, 2023 at 16: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.