बाधा प्रोग्रामिंग और शेड्यूलिंग मुद्दे
मुझे एक बाधा समस्या है जिसे मुझे हल करने की आवश्यकता है, लेकिन मुझे नहीं पता था कि समस्या को कैसे हल किया जाए:
मेरे पास 11 कर्मचारी हैं, मैं उनसे नाम लूंगा $a$ सेवा मेरे $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$।
मेरे पास एक छोटी सी कंपनी है जो केवल अधिकतम 8 कर्मचारी प्राप्त कर सकती है।
कंपनी में जाने के लिए मैं इन कर्मचारियों को समूह में कैसे बांट सकता हूं:
$a$, $b$, $c$, तथा $d$ 10 दिनों में कम से कम 1 बार साथ जाना चाहिए।
$g$, $e$, तथा $f$ 10 दिनों में कम से कम 1 बार साथ जाना चाहिए।
$h$, $i$, $j$, तथा $k$ 10 दिनों में कम से कम 1 बार साथ जाना चाहिए।
तथा $h$, $i$, $j$, $k$, $c$, $b$ 10 दिनों में कम से कम 1 बार साथ जाना चाहिए।
इसके अलावा हर कर्मचारी को अपने प्रत्येक सहयोगी को 10 दिनों की अवधि में देखना होगा।
उद्देश्य है कि इन कर्मचारियों को 10 दिनों में कैसे विभाजित किया जाए।
मुझे नहीं पता था कि समस्या को हल करने के लिए इन बाधाओं को कैसे मॉडल किया जाए।
जवाब
लश्कर $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$। बाधाएँ सभी के लिए {start {align} \ sum_ {e \ _ E} x_ {e, p} & \ le 8 && \ text {हैं$p\in P$} \ _ $g\in G$} \ tag2 \\ y_ {g, p} & \ le x_ {e, p} && \ text {सभी के लिए $g\in G$, $p\in P$, $e\in E_g$} \ tag3 \\ \ end {संरेखित करें} बाधा$(1)$एक बार में 8 कर्मचारियों की क्षमता को लागू करता है। बाधा$(2)$प्रत्येक समूह को कम से कम एक बार प्रकट होने के लिए मजबूर करता है। बाधा$(3)$ लागू करता है $y_{g,p}=1 \implies x_{e,p}=1$।
आपके उदाहरण में, आपने स्पष्ट रूप से चार कर्मचारी समूहों की पहचान की है, लेकिन आप प्रत्येक जोड़े को आकार 2 के समूह के रूप में भी जोड़ सकते हैं।
आपने एक उद्देश्य निर्दिष्ट नहीं किया था, लेकिन एक प्राकृतिक विकल्प कम से कम हो सकता है $\sum_{e\in E} \sum_{p\in P} x_{e,p}$। न्यूनतम 22 हो जाता है, और आप केवल तीन अवधियों के साथ इसे प्राप्त कर सकते हैं।