Problemas de programación y programación de restricciones
Tengo un problema de restricción que necesito resolver, pero no sabía cómo modelar el problema:
Tengo 11 empleados, los nombraré de $a$ a $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.
Tengo una pequeña empresa que solo puede recibir un máximo de 8 empleados.
¿Cómo puedo dividir a estos empleados en grupo para ir a la empresa sabiendo que:
$a$, $b$, $c$, y $d$ deben ir juntos al menos 1 vez en 10 días.
$g$, $e$, y $f$ deben ir juntos al menos 1 vez en 10 días.
$h$, $i$, $j$, y $k$ deben ir juntos al menos 1 vez en 10 días.
y $h$, $i$, $j$, $k$, $c$, $b$ deben ir juntos al menos 1 vez en 10 días.
Además, cada empleado debe ver a cada uno de sus colegas en un período de 10 días.
El objetivo es cómo dividir a estos empleados en 10 días.
No sabía cómo modelar estas restricciones para resolver el problema.
Respuestas
Dejar $E$ ser el conjunto de empleados, y dejar $P$ser el conjunto de períodos. Para$e\in E$ y $p\in P$, vamos a la variable de decisión binaria $x_{e,p}$ indicar si empleado $e$ va a la empresa en el período $p$. Dejar$G$ ser el conjunto de grupos que deben ir juntos al menos una vez, y para $g\in G$, dejar $E_g \subseteq E$ ser el conjunto de empleados en grupo $g$. Para$g\in G$, vamos a la variable de decisión binaria $y_{g,p}$ indicar si grupo $g$ está programado en el período $p$. Las restricciones son \ begin {align} \ sum_ {e \ in E} x_ {e, p} & \ le 8 && \ text {para todos$p\in P$} \ tag1 \\ \ sum_ {p \ in P} y_ {g, p} & \ ge 1 && \ text {para todos $g\in G$} \ tag2 \\ y_ {g, p} & \ le x_ {e, p} && \ text {para todos $g\in G$, $p\in P$, $e\in E_g$} \ tag3 \\ \ end {align} Restricción$(1)$refuerza la capacidad de 8 empleados a la vez. Restricción$(2)$obliga a cada grupo a aparecer al menos una vez. Restricción$(3)$ hace cumplir $y_{g,p}=1 \implies x_{e,p}=1$.
En su ejemplo, identificó explícitamente cuatro grupos de empleados, pero también puede modelar cada par de empleados como un grupo de tamaño 2.
No especificó un objetivo, pero una opción natural podría ser minimizar $\sum_{e\in E} \sum_{p\in P} x_{e,p}$. El mínimo resulta ser 22, y puedes lograrlo con solo tres períodos.