Constraint programming and scheduling issues

Question

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.

Answer 1

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.