제약 프로그래밍 및 스케줄링 문제

Question

해결해야 할 제약 문제가 있지만 문제를 모델링하는 방법을 알지 못했습니다.

저는 11 명의 직원이 있습니다. $a$ ...에 $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.

최대 8 명의 직원 만받을 수있는 작은 회사가 있습니다.

회사에 가기 위해이 직원들을 어떻게 그룹으로 나눌 수 있습니까?

• $a$, $b$, $c$, 및 $d$ 10 일에 한 번 이상 함께 가야합니다.

• $g$, $e$, 및 $f$ 10 일에 한 번 이상 함께 가야합니다.

• $h$, $i$, $j$, 및 $k$ 10 일에 한 번 이상 함께 가야합니다.

• 과 $h$, $i$, $j$, $k$, $c$, $b$ 10 일에 한 번 이상 함께 가야합니다.

또한 모든 직원은 10 일 동안 모든 동료를 만나야합니다.

목표는 이러한 직원을 10 일로 나누는 방법입니다.

문제를 해결하기 위해 이러한 제약 조건을 모델링하는 방법을 몰랐습니다.

Answer 1

허락하다 $E$ 직원들의 집합이되고 $P$기간의 집합입니다. 에 대한$e\in E$ 과 $p\in P$, 이진 결정 변수 $x_{e,p}$ 직원 여부 표시 $e$ 기간 내에 회사에 간다 $p$. 허락하다$G$ 적어도 한 번은 함께 가야하는 그룹의 집합이어야합니다. $g\in G$, 허락하다 $E_g \subseteq E$ 그룹의 직원이되다 $g$. 에 대한$g\in G$, 이진 결정 변수 $y_{g,p}$ 그룹 여부 표시 $g$ 기간에 예정 $p$. 제약 조건은 \ 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 {모두 용 $g\in G$} \ tag2 \\ y_ {g, p} & \ le x_ {e, p} && \ text {모두 용 $g\in G$, $p\in P$, $e\in E_g$} \ tag3 \\ \ end {align} 제약$(1)$한 번에 8 명의 직원을 수용합니다. 강제$(2)$각 그룹이 한 번 이상 나타나도록합니다. 강제$(3)$ 시행 $y_{g,p}=1 \implies x_{e,p}=1$.

예에서는 4 개의 직원 그룹을 명시 적으로 식별했지만 각 직원 쌍을 크기 2의 그룹으로 모델링 할 수도 있습니다.

목표를 지정하지 않았지만 자연스러운 선택은 최소화하는 것입니다. $\sum_{e\in E} \sum_{p\in P} x_{e,p}$. 최소값은 22로 밝혀졌고 3 개의 기간으로이를 달성 할 수 있습니다.