2
$\begingroup$

I have a constraint problem that i need to resolve, but i did not how know to model the problem:

I have 11 employees, i will name them from a to k {a,b,c,d,e,f,g,h,i,j,k}.

I have a small company that can only receive a maximum of 8 employees.

how can I divide these employees in group in order to go to the company knowing that:

  • a, b, c, and d must go together at least 1 time in 10 days.

  • g, e, and f must go together at least 1 time in 10 days.

  • h, i, j, and k must go together at least 1 time in 10 days.

  • and h, i, j, k, c, b, must go together at least 1 time in 10 days.

Furthermore every employee must see every one of his colleagues in 10 days period.

the objective is how to divide these employees on 10 days.

I didn't know how to model these constraints in order to solve the problem

$\endgroup$
  • 1
    $\begingroup$ First determine the decision variables. $\endgroup$ – RobPratt Oct 21 at 14:39
  • $\begingroup$ i think my decision variables will be the employees . they will have two possible values 0 or 1. 1 mean they go the company and 0 mean they will work from home. So my objective will be whose employee will go to the work in a 10 days period. $\endgroup$ – Firas Frikha Oct 21 at 14:45
  • $\begingroup$ You will need to make a binary decision for each employee and each day. $\endgroup$ – RobPratt Oct 21 at 14:53
  • $\begingroup$ @RobPratt Can you explain more please? I didn't get the idea $\endgroup$ – Firas Frikha Oct 21 at 15:00
5
$\begingroup$

Let $E$ be the set of employees, and let $P$ be the set of periods. For $e\in E$ and $p\in P$, let binary decision variable $x_{e,p}$ indicate whether employee $e$ goes to the company in period $p$. Let $G$ be the set of groups that must go together at least once, and for $g\in G$, let $E_g \subseteq E$ be the set of employees in group $g$. For $g\in G$, let binary decision variable $y_{g,p}$ indicate whether group $g$ is scheduled in period $p$. The constraints are \begin{align} \sum_{e\in E} x_{e,p} &\le 8 &&\text{for all $p\in P$} \tag1\\ \sum_{p\in P} y_{g,p} &\ge 1 &&\text{for all $g\in G$} \tag2\\ y_{g,p} &\le x_{e,p} &&\text{for all $g\in G$, $p\in P$, $e\in E_g$} \tag3\\ \end{align} Constraint $(1)$ enforces the capacity of 8 employees at a time. Constraint $(2)$ forces each group to appear at least once. Constraint $(3)$ enforces $y_{g,p}=1 \implies x_{e,p}=1$.

In your example, you identified four employee groups explicitly, but you can also model each pair of employees as a group of size 2.

You did not specify an objective, but a natural choice might be to minimize $\sum_{e\in E} \sum_{p\in P} x_{e,p}$. The minimum turns out to be 22, and you can achieve that with only three periods.

| improve this answer | |
$\endgroup$

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.