7
$\begingroup$

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

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

and

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

are strictly greater $>$ than

  1. [$x_1$ and $y_2$ and $x_3$]
  2. [$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.


$\endgroup$
2
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I guess $h_i$ is the equivalent of $x_i$ or $y_i$ right? Furthermore, if the constraints, e.g., $z_1 = x_1\cdot x_2\cdot x_3 < x_1\cdot x_2\cdot y_3 = z_2$ are implemented, wouldn't only the following objective function be adequate: $x_1 + x_2 + x_3 + y_1 + y_2 + y_3$? $\endgroup$ – Georgios Sep 12 at 16:23
  • $\begingroup$ @Georgios to explain this method, $$ \begin{align} z_1\leq x_1\\ z_1\leq x_2\\ z_1\leq x_3\\ z_2\leq x_1\\ z_2\leq x_2\\ z_2\leq y_3\\ z_1\geq x_1 +x_2 +x_3 -2\\ z_1\geq x_1 +x_2 +y_3 -2\\ z_1 > z_2 \end{align} $$ In my opinion, is better to replace $y_1 = x_4$, $y_2=x_5$ and $y_3=x_6$ to simplify the building of this constraints. The variables $x_i$ and $y_i$ are still in the set of constraints. Thus the objective function is adequate. $\endgroup$ – Alexandre Frias Sep 12 at 17:27
  • $\begingroup$ I think you eant to say $z_1 = x_1\cdot x_2\cdot x_3 > x_1\cdot x_2\cdot y_3 = z_2$ not $z_1 = x_1\cdot x_2\cdot x_3 < x_1\cdot x_2\cdot y_3 = z_2$ $\endgroup$ – Alexandre Frias Sep 12 at 17:29
  • $\begingroup$ \begin{align} z_{1,2,3}\leq x_1\\ z_{1,2,3}\leq x_2\\ z_{1,2,3}\leq x_3\\ z_{1,2,6}\leq x_1\\ z_{1,2,6}\leq x_2\\ z_{1,2,6}\leq x_6\\ z_{1,2,3}\geq x_1 +x_2 +x_3 -2\\ z_{1,2,6}\geq x_1 +x_2 +x_6 -2\\ z_{1,2,3} > z_{1,2,6} \end{align} $\endgroup$ – Alexandre Frias Sep 12 at 17:43
  • 1
    $\begingroup$ Yes exactly my bad. Concerning the objective function, wouldn't only the following objective function be adequate: x1+x2+x3+y1+y2+y3? $\endgroup$ – Georgios Sep 13 at 6:52
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I do not mind using additional help variables. I would avoid using products of decision variables since this would make the problem more complex. Do you have suggested links for the linearization part with the auxiliary variables? $\endgroup$ – Georgios Sep 6 at 13:56
  • $\begingroup$ Your last suggestion may work though. How would I write the constraint to fulfill the demand? $$\sum \limits_{e,a,b} x_{e,j,a,b} \geq n_{j,x,y}\quad\forall j,x,y$$ with $n$: the demand in employees; $e$: employee; $j$: project; $a$: start date for employee; $b$: end date for employee; $x$: start date project; $y$: end date project? This formulation is not fully correct. How does the solver know that there are blocks of dates for a project such as 06.09 to 16.09? How could I add all the different available employee blocks to fulfill the example time frame written above? $\endgroup$ – Georgios Sep 6 at 14:00
  • $\begingroup$ @Georgios, I'm not sure what your subscript $x$ and $y$ mean, in the context of $n$. It does not matter which employee fulfills the demand, right? $\endgroup$ – Robert Schwarz Sep 6 at 14:47
  • $\begingroup$ Your constraint looks fine, you just need to filter the sum to only contain those $a$ and $b$ that match the time index of the project demand. So, let's say that project $j$ will start at time $t_s$ and end at $t_e$. Then you would add one inequality for each time step $t$ in $[t_s, t_e]$: $\sum\limits_{e, a \le t \le b} x_{e,j,a,b} \ge n_{j,t}$ $\endgroup$ – Robert Schwarz Sep 6 at 14:52
  • $\begingroup$ $x$ and $y$ as already stated, are the start date of the project, e.g. 06.09. and end date of the project, e.g. 16.09. apparently I misunderstood your $x_{t,d}$ variable. Unfortunately, I do not get your $n_{j,t}$ notation. You narrow the demand $n$ to one date $t$? Also, I guess you mean that $t_s \leq a \leq b \leq t_e$ holds? Then $a \leq t \leq b$ for $x_{e,j,a,b}$ does not make sense to me. $\endgroup$ – Georgios Sep 6 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.