Problèmes de programmation et de planification par contraintes

Question

J'ai un problème de contrainte que je dois résoudre, mais je ne savais pas comment modéliser le problème:

J'ai 11 employés, je les nommerai d'après $a$ à $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.

J'ai une petite entreprise qui ne peut accueillir que 8 employés au maximum.

comment répartir ces salariés en groupe pour aller dans l'entreprise en sachant que:

• $a$, $b$, $c$, et $d$ doit aller ensemble au moins 1 fois en 10 jours.

• $g$, $e$, et $f$ doit aller ensemble au moins 1 fois en 10 jours.

• $h$, $i$, $j$, et $k$ doit aller ensemble au moins 1 fois en 10 jours.

• et $h$, $i$, $j$, $k$, $c$, $b$ doit aller ensemble au moins 1 fois en 10 jours.

De plus, chaque employé doit voir chacun de ses collègues dans un délai de 10 jours.

L'objectif est de répartir ces salariés sur 10 jours.

Je ne savais pas modéliser ces contraintes pour résoudre le problème.

Answer 1

Laisser $E$ être l'ensemble des employés, et laissez $P$être l'ensemble des périodes. Pour$e\in E$ et $p\in P$, laissez la variable de décision binaire $x_{e,p}$ indiquer si l'employé $e$ va à l'entreprise en période $p$. Laisser$G$ être l'ensemble des groupes qui doivent aller ensemble au moins une fois, et pour $g\in G$, laisser $E_g \subseteq E$ être l'ensemble des employés du groupe $g$. Pour$g\in G$, laissez la variable de décision binaire $y_{g,p}$ indiquer si le groupe $g$ est programmé dans la période $p$. Les contraintes sont \ begin {align} \ sum_ {e \ in E} x_ {e, p} & \ le 8 && \ text {pour tous$p\in P$} \ tag1 \\ \ sum_ {p \ in P} y_ {g, p} & \ ge 1 && \ text {pour tous $g\in G$} \ tag2 \\ y_ {g, p} & \ le x_ {e, p} && \ text {pour tous $g\in G$, $p\in P$, $e\in E_g$} \ tag3 \\ \ end {align} Contrainte$(1)$renforce la capacité de 8 employés à la fois. Contrainte$(2)$force chaque groupe à apparaître au moins une fois. Contrainte$(3)$ applique $y_{g,p}=1 \implies x_{e,p}=1$.

Dans votre exemple, vous avez identifié explicitement quatre groupes d'employés, mais vous pouvez également modéliser chaque paire d'employés comme un groupe de taille 2.

Vous n'avez pas spécifié d'objectif, mais un choix naturel pourrait être de minimiser $\sum_{e\in E} \sum_{p\in P} x_{e,p}$. Le minimum s'avère être 22, et vous pouvez y parvenir avec seulement trois périodes.