# How to fill the days in sequence?

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

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) ?

• No, $ℎ_1≥ℎ_2≥ℎ_3≥ℎ_4$ will allow 8 6 4 2 which is using 4 days instead of 8 8 4 (3 days) Aug 11 at 16:08
• 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$. Aug 11 at 17:42
• @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. Aug 11 at 17:48
• 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. Aug 11 at 18:01

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

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

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

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$$
• Thanks, @Kuifje. It is definitely very similar to the bin-packing problem. Aug 12 at 19:34

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

• Your formulation allows $h_i=20/3$ for all $i$. Sep 5 at 15:32
• @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. Sep 5 at 16:33