Finding an Objective Function for Assigning Employees to Sequence Dates

Question

I am using a mixed-integer-program to schedule employees to projects. These projects can have a time window to get completed from a few weeks to a few months.

At the moment I am working in a dimension of dates. Surely, you can argue that a week dimension is more suitable but I want to make the formulation as generic as possible.

In the end, I would like to have my employees scheduled in such a manner, that if an employee is picked he should stay assigned for the project for as long as he is available for sequence dates.

Here is an oversimplified example of how it should look like:

I have three dates 1,2,3

x is the binary decision variable of employee x

• $x_1$ for date 1
• $x_2$ for date 2
• $x_3$ for date 3

analog for employee y with the decision variable y

I know that I have to implement this within my objective function which will have to get maximized. Otherwise, if I use constraints there may be a problem with finding a feasible solution.

What I would like to achieve is the following:

The calculation of the following should look like this if there is employee availability:

Notation: [$x$ and $y$] means that $x$ and $y = 1$

a) [$x_1$ and $x_2$]
b) [$y_1$ and $y_2$]

are greater $>$ than

c) [$x_1$ and $y_2$]
d) [$y_1$ and $x_2$]

and

1. [$x_1$ and $x_2$ and $x_3$]
2. [$y_1$ and $y_2$ and $y_3$]

are strictly greater $>$ than

3. [$x_1$ and $y_2$ and $y_3$]
4. [$y_1$ and $y_2$ and $x_3$]
5. [$x_1$ and $x_2$ and $y_3$]
6. [$y_1$ and $x_2$ and $x_3$]
7. [$x_1$ and $y_2$ and $x_3$]
8. [$y_1$ and $x_2$ and $y_3$]

and

3. [$x_1$ and $y_2$ and $y_3$]
4. [$y_1$ and $y_2$ and $x_3$]
5. [$x_1$ and $x_2$ and $y_3$]
6. [$y_1$ and $x_2$ and $x_3$]

are strictly greater $>$ than

7. [$x_1$ and $y_2$ and $x_3$]
8. [$y_1$ and $x_2$ and $y_3$]

At the moment this is how my objective function would look like:

• $x_1 + y_1 + (x_1 + x_2) + (y_1 + y_2) + (x_1 + x_2 + x_3) + (y_1 + y_2 + y_3)$

For

• $x_1,x_2$ -> 5
• $x_1,y_2$ -> 2
• $x_1,x_2,x_3$ -> 6
• $x_1,x_2,y_3$ -> 4
• $x_1,y_2,y_3$ -> 4
• $x_1,y_2,x_3$ -> 4
• $y_1,x_2,y_3$ -> 4
• $y_1,y_2,x_3$ -> 4

I still have to tweak it since $y_1,x_2,y_3$ should be strictly smaller $<$ than $y_1,y_2,x_3$.

Would this method work?

Update:

I think I could achieve the same, by assigning as few employees as possible to a project for a given task.

Surely, employees could get assigned to dates interchangeably and asymmetrically but within a week this would not matter since it is not relevant which employee is assigned to which date but to which week.

---

Answer 1

I think that if you don't want to introduce additional variables, you will have to use products of them, to give additional value to, say, $x_1 \cdot x_2$. Since theses are all binary variables, you could also linearize the terms yourself (introducing auxiliary variables) and stay in the MIP form.

Maybe it's natural to introduce another dimension to your variables, indicating the duration that a person is assigned to a project.

So $x_{t,d}$ would mean that person $x$ starts at time $t$ and then stays on that project for exactly $d$ time steps. This way, you could give higher weight to the $x_{.,d}$ variables with large $d$.

Answer 2

I think that you want this set of non-linear constraints

$$ \begin{align} \text{first}&\begin{cases}x_1 x_2 > x_1 y_2\\ x_1 x_2 > y_1 x_2\\ y_1 y_2 > x_1 y_2\\ y_1 y_2 > y_1 x_2\end{cases}\\ \text{second}&\begin{cases}x_1 x_2 x_3 > x_1 y_2 y_3\\ x_1 x_2 x_3 > y_1 y_2 x_3\\ x_1 x_2 x_3 > x_1 x_2 y_3\\ x_1 x_2 x_3 > y_1 x_2 x_3\\ x_1 x_2 x_3 > x_1 y_2 x_3\\ x_1 x_2 x_3 > y_1 x_2 y_3\\ y_1 y_2 y_3 > x_1 y_2 y_3\\ y_1 y_2 y_3 > y_1 y_2 x_3\\ y_1 y_2 y_3 > x_1 x_2 y_3\\ y_1 y_2 y_3 > y_1 x_2 x_3\\ y_1 y_2 y_3 > x_1 y_2 x_3\\ y_1 y_2 y_3 > y_1 x_2 y_3\end{cases}\\ \text{third}&\begin{cases}x_1 y_2 y_3 > x_1 y_2 x_3\\ x_1 y_2 y_3 > y_1 x_2 y_3\\ y_1 y_2 x_3 > x_1 y_2 x_3\\ y_1 y_2 x_3 > y_1 x_2 y_3\\ x_1 x_2 y_3 > x_1 y_2 x_3\\ x_1 x_2 y_3 > y_1 x_2 y_3\\ y_1 x_2 x_3 > x_1 y_2 x_3\\ y_1 x_2 x_3 > y_1 x_2 y_3\end{cases} \end{align} $$

and you need to maximize the following function

$$x_1 + y_1 + x_1 + x_2 + y_1 + y_2 + x_1 + x_2 + x_3 + y_1 + y_2 + y_3.$$

You can linearize these non-linear constraints by $z=h_1 h_2$ and $z=h_1 h_2 h_3$. The generalization of this technique is

$$z_{1,\ldots,n}= \prod_{i=1}^{n} h_i$$

then you can replace that as follows

$$ \begin{align} z_{1,\ldots,n} \leq h_i, \quad \forall i\in\{1,\ldots, n\}\\ z_{1,\ldots,n} \geq \sum_{i = 1}^n h_i - n + 1\\ \end{align}. $$

The proof using logical propositions is easy.

You need to remove many redundant constraints such as $x_1 x_2 x_3 > x_1 y_2 x_3$ because you have $x_1 x_2 x_3 > x_1 y_2 y_3$ and $x_1 y_2 y_3 > x_1 y_2 x_3$. The same reason for $x_1 x_2 x_3 > y_1 x_2 y_3$, $y_1 y_2 y_3 > x_1 y_2 x_3$ and $y_1 y_2 y_3 > y_1 x_2 y_3$.