जॉब शेड्यूलिंग समस्या

Question

मैं ऐसे एप्लिकेशन पर काम कर रहा हूं जहां मुझे घूर्णन अनुसूची पर सदस्यों के लिए स्वचालित रूप से नौकरियां निर्धारित करने की आवश्यकता है। मैं नियमों को समझाने में बहुत अच्छा नहीं हूं, इसलिए यहां कुछ डेटा है:

पद: सोमवार और बुधवार साप्ताहिक जैसे नियमों के साथ नौकरी का शीर्षक।
श्रेणियाँ: पदों का एक सेट
समूह: पदों का एक और सेट। उसी समूह में स्थितियों को उसी दिन
सदस्यों को असाइन नहीं किया जा सकता है: उपयोगकर्ता किसी दिए गए दिनांक पर पदों पर असाइन किए जाते हैं।

महीने में प्रत्येक तारीख के लिए, सदस्यों को पदों (आरोही क्रम में दोनों) को सौंपा जाता है। यदि किसी सदस्य को एक श्रेणी में किसी स्थिति में असाइन किया जाता है, अगली बार उसी श्रेणी में एक स्थिति आती है, तो अगला सदस्य वर्णानुक्रम (या सूची की शुरुआत) असाइन किया जाता है।

सदस्य: एम 1, M2, एम 3, एम 4
श्रेणी सी 1 में पद: P1, P2, पी 3
स्थिति P1 में सदस्य: एम 1, M2, एम 3, एम 4 स्थिति P2 में
सदस्य: एम 1, M2, एम 3
स्थिति पी 2 में सदस्य: एम 1, एम 3, एम 4

यदि एम 1 को पी 1 के लिए असाइन किया गया है, यदि पी 2 अगला आता है, तो एम 2 असाइन किया जाएगा। जटिलता की एक अतिरिक्त परत पेश की जाती है, जहां यदि पी 3 इसके बजाए आता है, तो एम 3 असाइन किया जाता है। सिस्टम को इस तथ्य का ट्रैक रखना है कि एम 2 'छोड़ा गया' था और उपलब्ध होने पर एम 2 को आवंटित करता है, फिर एम 4 को आवंटित करें, या जब तक यह एम 2 उपलब्ध न हो, तब तक प्रतीक्षा करें (यह अतिरिक्त जटिल हो जाता है जब कई 'छोड़े जाते हैं 'सदस्य)।

एक सदस्य को भी छोड़ दिया जाएगा यदि उसने संकेत दिया है कि वह उस तारीख पर उपलब्ध नहीं होगा। सिस्टम को छोड़ने वाले सदस्यों पर प्राथमिकता रखने की आवश्यकता है, किसी भी तरह उन्हें पहचानते समय पहचानें और फिर सूची में अगले तार्किक व्यक्ति पर जाएं। छोड़ने की तिथि के कारण समूहों पर भी छोड़ना समूह पर लागू होता है।

मेरे पास पहले से ही एक अस्थायी [और गन्दा] समाधान है जिसे मैं अब समझ नहीं पा रहा हूं, भले ही मेरे पास प्रत्येक चरण को समझाते हुए बहुत सारी टिप्पणियां हों। इसकी कमजोरियां छोड़ने वाले सदस्यों से निपटने में हैं।

यदि आप कोड करने जा रहे थे तो आप इसके बारे में कैसे जाएंगे? मैं इसे PHP में कार्यान्वित कर रहा हूं लेकिन छद्म कोड भी काम करेगा।

Answer 1

मेरा समाधान: आपको प्राथमिकता क्यूई (जो स्प्लप्रियोरिटीक्यूयू के तहत PHP में उपलब्ध है) की आवश्यकता है। PriorityQueue आपको अवरोही प्राथमिकता वाले तत्व देता है (मानों द्वारा क्रमबद्ध, सबसे छोटा मान सर्वोच्च प्राथमिकता है)।

प्रत्येक सदस्य को असाइन किया गया मान मिलता है।यह मान एन अंकों के साथ एक ASCII संख्या है (आप सुविधा के लिए 8 अंकों का उपयोग कर सकते हैं), शून्य से एन पदों से भरा हुआ है। उसके बाद आप नाम नाम जोड़ते हैं।

• एम 1 मूल्य:: 99999Albert P1, P2, पी 3
• M2 मूल्य: 99999Susi P1, P2
• एम 3 मूल्य तुम भी (एन = 5) उपलब्ध पदों

  तो प्रत्येक सदस्य के लिए जोड़ : 99 999 बॉब पी 1, पी 3

इससे सदस्यों को प्राथमिकता और नाम से सॉर्ट करना आसान हो जाता है।

तैयारी:

एक धूप दिन। आप किसी दिए गए दिन के लिए असाइन की गई स्थिति और एक श्रेणी पुनर्प्राप्त कर रहे हैं। प्रत्येक सदस्य एक लंबी सूची में भरा हुआ है। प्रत्येक सदस्य जो काम पर नहीं दिख रहा है वह लोड नहीं होता है, लेकिन उसका मूल्य शून्य से कम हो जाता है। बॉब यहां नहीं है, इसलिए इसका नया मूल्य 99 997 बॉब हो जाता है। इसका मतलब है कि बॉब अगली बार स्वचालित रूप से चुना जाएगा। अन्य सभी सदस्यों को अपना मूल्य शून्य से कम हो जाता है। (उपयोग SplObjectStorage)

एक विशिष्ट दिवस के लिए सौंपा पदों मैप की जाती हैं:

P1-> एम 1, M2, एम 3, एम 4 आदि P2-> आदि

मानचित्र केवल पदों में शामिल है जो इस दिन असाइन किया जाना चाहिए।

फ़िल्टर: आपको समूह को देखना चाहिए और मानचित्र पर किसी भी स्थिति को हटा देना चाहिए जिसे इस दिन असाइन नहीं किया जा सकता है। आपका समूह विवरण थोड़ा अस्पष्ट है।

असाइन:

• आप सदस्यों जो सूची से
• निकालें उपलब्ध सदस्यों के स्थान को भरने कर सकते हैं की
• प्राप्त सूची निर्दिष्ट करके PriorityQueue
• स्थिति निरुपित में लाना स्थिति चुनें PriorityQueue से निकालें() द्वारा (सही असाइनमेंट स्वचालित रूप से किया जाता है)। प्रत्येक सदस्य जो सौंपा गया है उसे एक से बढ़ाया जाएगा (इसलिए यदि आप यहां हैं और काम कर रहे हैं तो कमी और वृद्धि स्तर)। यदि आप यहां हैं और किसी भी कारण से किसी स्थिति के लिए असाइन नहीं किए गए हैं, तो आपको एक छोटा सा जुर्माना मिलता है। यदि आप यहां नहीं हैं, तो आपको दो का दंड मिलता है।
• पूरा होने के बाद बाकी सदस्यों की सूची पर फिर से, डाल PQueue स्पष्ट और अगले काम के साथ जारी है।

चेतावनियां:

• आप हमेशा एक पद के लिए पर्याप्त लोग हैं कि सावधान रहना चाहिए।

Answer 2

uff। मैं आपको विवरण का पालन नहीं करता, लेकिन इसी तरह की स्थितियों में मैंने इस तरह की समस्या को हल करने के लिए एसक्यूएल का उपयोग किया है। यदि आप PHP का उपयोग कर रहे हैं तो मुझे लगता है कि आपके पास एसक्यूएल उपलब्ध है।

जो मैं सुझाव दूंगा कि यह जानकारी तालिकाओं के एक सेट में संग्रहीत करने का तरीका ढूंढ रही है और फिर यह काम कर रहा है कि एसक्यूएल क्वेरी आपको वह उत्तर देती है जो आप चाहते हैं। अक्सर प्रक्रियात्मक भाषा में एसक्यूएल में करना बहुत आसान होता है।

छोड़े गए भाग के लिए, उदाहरण के लिए, आपके पास एक कॉलम हो सकता है जो रिकॉर्ड करता है जब किसी को अंतिम बार असाइन किया गया था, और उसके बाद ऑर्डर करें (ताकि आप उस व्यक्ति को चुन सकें जिसे लंबे समय तक असाइन नहीं किया गया हो)। वैकल्पिक रूप से, आपके पास कॉलम और ऑर्डर के रूप में छोड़े गए समय की संख्या हो सकती है।

Answer 3

मुझे क्या लगता है कि 'एम' सदस्य और 'एन' पद हैं।

श्रेणी: पदों का एक समूह - एक सदस्य जो श्रेणी में एक पद सौंपा गया है, वह दूसरा नहीं हो सकता है?

समूह: पदों का एक समूह - एक ही समूह में स्थितियों को अलग-अलग दिनों में असाइन किया जाना चाहिए।

अंतिम बात, स्थिति में सदस्यों की एक सूची है जो इसे भर सकते हैं।

इसे डेटा-संरचना बिंदु से देखकर, सदस्यों को एक लिंक्ड सूची में डाल दें - प्रत्येक सदस्य को [स्थिति, दिन] की एक अतिरिक्त सूची होनी चाहिए जिसे अंत में सौंपा गया है। फिर, प्रत्येक स्थिति के लिए, उन सदस्यों के संदर्भों की एक सूची है जो उस स्थिति को भर सकते हैं। श्रेणियों को संदर्भ के लिए संदर्भों की एक और सूची के रूप में कार्यान्वित करें कि किस श्रेणी में यह है।

वास्तविक असाइनमेंट: एक दिन काउंटर = 0 है, और पदों के माध्यम से पुनरावृत्त करें। प्रत्येक स्थिति पी के लिए, सदस्यों को भरें जो इसे भर सकते हैं। एक सदस्य एम स्थिति अगर भर सकते हैं:

• किसी भी पद पर वे P2 पी
• किसी भी पद पर वे दिन के साथ P2 भरी है के साथ एक वर्ग का हिस्सा नहीं है भरी है = daycounter के साथ एक समूह का हिस्सा नहीं है पी

यदि वह स्थिति भर सकता है, तो [स्थिति, दिन] जोड़ी सदस्य में जोड़ दी जाती है, और सदस्य का नोड सूची के अंत में स्थानांतरित हो जाता है (यही कारण है कि संदर्भ आवश्यक हैं - सभी नोड स्थानांतरित होने के बावजूद संदर्भ अभी भी मान्य हैं)। यह सुनिश्चित करता है कि 'छोड़े गए' सदस्यों को सर्वोच्च प्राथमिकता दी जाती है, और जिन सदस्यों को नहीं पहुंचाया गया था उन्हें अगली सर्वोच्च प्राथमिकता दी गई थी।

एक बार स्थिति भरने के बाद, अगली स्थिति पर जाएं। यदि स्थिति किसी समूह को पहले से असाइन की गई स्थिति के साथ साझा करती है, तो इसे छोड़ दें, जब तक कि आप दिन 1 पर जितनी स्थिति दे सकें, तब तक सभी पदों के माध्यम से पुनरावृत्ति न करें। फिर, दिन काउंटर बढ़ाएं और 2 दिन के लिए दोहराएं। यह आपको देना चाहिए सभी नौकरियों के लिए अधिकतम असाइनमेंट (अधिकतम के बारे में सुनिश्चित नहीं)।

युक्ति: सूची को पार करने से रोकने के लिए सदस्य सूची के अंत में किसी सदस्य को स्थानांतरित करते समय, अंत में संदर्भ रखें - अगली स्थिति के लिए, आपको शुरुआत से ही शुरुआत करना होगा, इसलिए वहां पूरी बात से कोई बात नहीं चल रही है।