Problemas de programação e agendamento de restrições

Question

Tenho um problema de restrição que preciso resolver, mas não sabia como modelar o problema:

Tenho 11 funcionários, vou chamá-los de $a$ para $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.

Tenho uma pequena empresa que só pode receber no máximo 8 funcionários.

como posso dividir esses funcionários em grupo para ir para a empresa sabendo que:

• $a$, $b$, $c$, e $d$ devem ir juntos pelo menos 1 vez em 10 dias.

• $g$, $e$, e $f$ devem ir juntos pelo menos 1 vez em 10 dias.

• $h$, $i$, $j$, e $k$ devem ir juntos pelo menos 1 vez em 10 dias.

• e $h$, $i$, $j$, $k$, $c$, $b$ devem ir juntos pelo menos 1 vez em 10 dias.

Além disso, cada funcionário deve ver cada um de seus colegas em um período de 10 dias.

O objetivo é como dividir esses funcionários em 10 dias.

Não sabia como modelar essas restrições para resolver o problema.

Answer 1

Deixar $E$ seja o conjunto de funcionários, e deixe $P$ser o conjunto de períodos. Para$e\in E$ e $p\in P$, deixe a variável de decisão binária $x_{e,p}$ indique se empregado $e$ vai para a empresa no período $p$. Deixar$G$ ser o conjunto de grupos que devem ir juntos pelo menos uma vez, e por $g\in G$, deixar $E_g \subseteq E$ seja o conjunto de funcionários no grupo $g$. Para$g\in G$, deixe a variável de decisão binária $y_{g,p}$ indique se o grupo $g$ está programado no período $p$. As restrições são \ 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 \\ \ final {align} restrição$(1)$reforça a capacidade de 8 funcionários por vez. Limitação$(2)$força cada grupo a aparecer pelo menos uma vez. Limitação$(3)$ impõe $y_{g,p}=1 \implies x_{e,p}=1$.

Em seu exemplo, você identificou quatro grupos de funcionários explicitamente, mas também pode modelar cada par de funcionários como um grupo de tamanho 2.

Você não especificou um objetivo, mas uma escolha natural pode ser minimizar $\sum_{e\in E} \sum_{p\in P} x_{e,p}$. O mínimo acaba sendo 22, e você pode conseguir isso com apenas três períodos.