Kendala masalah pemrograman dan penjadwalan

Question

Saya memiliki masalah kendala yang perlu saya selesaikan, tetapi saya tidak tahu cara memodelkan masalah:

Saya memiliki 11 karyawan, saya akan menyebutkan nama mereka $a$ untuk $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.

Saya memiliki perusahaan kecil yang hanya dapat menerima maksimal 8 karyawan.

bagaimana saya bisa membagi karyawan ini dalam kelompok untuk pergi ke perusahaan dengan mengetahui bahwa:

• $a$, $b$, $c$, dan $d$ harus pergi bersama setidaknya 1 kali dalam 10 hari.

• $g$, $e$, dan $f$ harus pergi bersama setidaknya 1 kali dalam 10 hari.

• $h$, $i$, $j$, dan $k$ harus pergi bersama setidaknya 1 kali dalam 10 hari.

• dan $h$, $i$, $j$, $k$, $c$, $b$ harus pergi bersama setidaknya 1 kali dalam 10 hari.

Selain itu, setiap karyawan harus melihat semua rekannya dalam jangka waktu 10 hari.

Tujuannya adalah bagaimana membagi karyawan ini dalam 10 hari.

Saya tidak tahu bagaimana memodelkan kendala ini untuk memecahkan masalah.

Answer 1

Membiarkan $E$ menjadi kumpulan karyawan, dan biarkan $P$menjadi himpunan periode. Untuk$e\in E$ dan $p\in P$, biarkan variabel keputusan biner $x_{e,p}$ tunjukkan apakah karyawan $e$ pergi ke perusahaan pada periode tertentu $p$. Membiarkan$G$ menjadi kumpulan kelompok yang harus pergi bersama setidaknya sekali, dan untuk $g\in G$, biarkan $E_g \subseteq E$ jadilah kumpulan karyawan dalam kelompok $g$. Untuk$g\in G$, biarkan variabel keputusan biner $y_{g,p}$ tunjukkan apakah grup $g$ dijadwalkan dalam periode $p$. Batasannya adalah \ begin {align} \ sum_ {e \ in E} x_ {e, p} & \ le 8 && \ text {untuk semua$p\in P$} \ tag1 \\ \ sum_ {p \ in P} y_ {g, p} & \ ge 1 && \ text {untuk semua $g\in G$} \ tag2 \\ y_ {g, p} & \ le x_ {e, p} && \ text {untuk semua $g\in G$, $p\in P$, $e\in E_g$} \ TAG3 \\ \ end {menyelaraskan} Kendala$(1)$memberlakukan kapasitas 8 karyawan sekaligus. Paksaan$(2)$memaksa setiap kelompok untuk muncul setidaknya sekali. Paksaan$(3)$ menegakkan $y_{g,p}=1 \implies x_{e,p}=1$.

Dalam contoh Anda, Anda mengidentifikasi empat grup karyawan secara eksplisit, tetapi Anda juga dapat mencontohkan setiap pasangan karyawan sebagai grup berukuran 2.

Anda tidak menentukan tujuan, tetapi pilihan yang wajar mungkin untuk meminimalkan $\sum_{e\in E} \sum_{p\in P} x_{e,p}$. Jumlah minimumnya adalah 22, dan Anda dapat mencapainya hanya dengan tiga periode.