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.