शेड्यूलिंग एल्गोरिदम को कैसे गति दें

नमस्ते, प्रिय हभ्रवचन!
निश्चित रूप से आपके काम में आप में से कई शेड्यूलिंग सिद्धांत की समस्याओं से संबंधित एक नियोजन समस्या को हल करने की आवश्यकता पर आए हैं। मैं आपको बताना चाहता हूं कि आप एल्गोरिथ्म को प्रभावित किए बिना इस तरह के कार्यक्रम के काम को कैसे तेज कर सकते हैं।

इन समस्याओं को हल करने के लिए दृष्टिकोणों की एक बड़ी संख्या है, जो विभिन्न अनुमानी, अनुमानित एल्गोरिदम और ब्रूट बल कटौती एल्गोरिदम का उपयोग और संयोजन करके कार्यान्वित की जाती हैं। जीवन में, उनके सभी कार्यान्वयन उद्यम की बारीकियों पर बहुत निर्भर हैं, इसलिए, एक अलग समाधान में देरी किए बिना, हम परिणाम बनाने के लिए समय कम करने के लिए सामान्य चरणों पर विचार करते हैं।
"डाक द्वारा नौकरियों का वितरण" का बहुत महत्वपूर्ण कार्य ले लो। और यह भी कि उपयोगकर्ता जो कार्य का एक सेट बनाता है और इसे नियोजन को भेजता है। और उसे एक - दो विकल्प नहीं, बल्कि दिन के लिए सभी संभव अंतरालों को बाहर लाने की जरूरत है। यानी यह कहना है कि क्या यह संभव है कि यह काम 8 पर सेट हो? और 8.30 बजे? और इसलिए पूरे दिन के लिए।

डेटा संरचना

प्रत्येक पोस्ट को उस कार्य के प्रकार की विशेषता है जो उस पर किया जा सकता है। प्रत्येक पद पर, कार्य अंतराल ज्ञात होता है (अर्थात, समय अवधि जो विराम या अन्य कार्य द्वारा कब्जा नहीं किया जाता है)। प्रत्येक नियोजित कार्य को समय और प्रकार के मानदंड की विशेषता है।

मेरे सर्वर से मुक्त अंतराल के बारे में जानकारी इस तरह एक प्लेट में खींची जाती है:


कार्य निम्नलिखित संरचनाओं की सूची में संग्रहीत हैं:

private class JobTypes { public JobTypes(int jId, TimeSpan time, int type, string job_code = "0") { this.JobId = jId; this.JobRuntime = time; this.JobType = type; this.JobCode = job_code; } public int JobId { get; private set; } public TimeSpan JobRuntime { get; private set; } public int JobType { get; private set; } public string JobCode { get; set; } } 

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

बिल्डबिलिटी चेक

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

 private bool CheckPeriodsAvailable(SchData sch_data) { var jTime = from s in sch_data.jobs group s by new { jType = s.JobType } into g select new { g.Key.jType, qty = g.Sum(s => s.JobRuntime.TotalMinutes) }; var pTime = (from s in (sch_data.BasicData.Tables["MonthFree"]).AsEnumerable() group s by new { jType = s.Field<int>("JobType") } into g select new { g.Key.jType, qty = g.Sum(s => (s.Field<DateTime>("FinTime") - s.Field<DateTime>("StartTime")).TotalMinutes) }).ToList(); foreach (var j in jTime) { double p = pTime.Find(item => item.jType.Equals(j.jType)).qty; if (j.qty > p) return false; } return true; } 

यदि संसाधन अभी भी पाए जाते हैं, तो हम दूसरे चरण पर आगे बढ़ेंगे - खोज को कम करना। यह स्पष्ट है कि न्यूनतम वजन के साथ समाधान एक ऐसा समाधान है जिसमें प्रत्येक प्रकार का काम बिना किसी रुकावट के केवल एक पोस्ट पर किया गया था। जीवन में, यह इस तथ्य में व्यक्त किया जाता है कि सेवा केंद्र में मशीन को एक पोस्ट पर संसाधित किया जाएगा, और कार्यशाला के चारों ओर नहीं खींचा जाएगा। एक संभावना है कि काम बाद में शुरू करना होगा, लेकिन यहां आपको मशीन के हस्तांतरण के वजन के साथ देरी के वजन की तुलना करनी होगी और दो बुराइयों का चयन करना होगा।

पुनरावृत्तियों की संख्या कम करें

नियोजन प्रक्रिया की शुरुआत से पहले, सभी कार्यों को कार्य के क्रम में एकल ब्लॉकों में जोड़ा जाता है, प्रकार द्वारा समूहीकृत किया जाता है। यदि कार्य की स्थिति कार्यों की निर्भरता के बारे में नहीं कहती है (यानी, वह काम i + 2 i + 1 समाप्त होने से पहले पूरा नहीं किया जा सकता है), तो हम प्रकार से प्रारंभिक कार्य को हल करते हैं। प्रत्येक ब्लॉक की अवधि को ब्लॉक में शामिल सभी कार्यों की कुल अवधि के बराबर माना जाता है।
इस प्रकार, सबसे सरल मामले में, 20 छोटे काम नहीं, लेकिन एक लंबे एक को योजना के लिए भेजा जाएगा। निष्पादन समय में अंतर के बारे में ऊपर बताया गया था। संयुक्त कार्य के लिए सभी देखे गए रास्तों को निर्णय वृक्ष में सहेजा जाना चाहिए यदि परिणाम नकारात्मक है, तो आपको धीरे-धीरे समूहीकरण घनत्व को कम करना होगा और खोज क्षेत्र से उन रास्तों को हटाना होगा जो पहले ही पेड़ में जुड़ चुके हैं।
जैसे ही न्यूनतम वांछित वजन के साथ रास्ता मिल जाता है, हम खोज प्रक्रिया को रोक देंगे और समूह को अलग-अलग कार्यों में वापस विभाजित करेंगे, ताकि किस समय किस काम के बारे में जानकारी पेश की जा सके।

 private List<PeriodElems> SeparateSch(List<PeriodElems> resultList, List<JobTypes> jobs, DataTable PostsData) { int j = 0; while (j < resultList.Count) { if (((j) < jobs.Count) && (resultList[j].time > jobs[j].JobRuntime) && (resultList[j].type == jobs[j].JobType)) { PeriodElems ins_elem = resultList[j].Clone(); // ,         var periods = from item in (PostsData).AsEnumerable() where item.Field<int>("PostId") == resultList[j].post_id && ( (item.Field<DateTime>("StartTime") <= resultList[j].start && item.Field<DateTime>("FinTime") > resultList[j].start) || (item.Field<DateTime>("StartTime") > resultList[j].start && item.Field<DateTime>("FinTime") < resultList[j].fin) || (item.Field<DateTime>("StartTime") < resultList[j].fin && item.Field<DateTime>("FinTime") >= resultList[j].fin) ) select item; DataView OldMonthRows = periods.AsDataView<DataRow>(); if (OldMonthRows.Count == 0) { return null; } //    -  ok,  ,   . TimeSpan shift_time = OldMonthRows.Count == 1 ? jobs[j].JobRuntime : GetShiftTime(jobs[j].JobRuntime, OldMonthRows, DateTime.Parse(OldMonthRows[0]["FinTime"].ToString()) - resultList[j].start); //           -    TimeSpan delta = DateTime.Parse(OldMonthRows[0]["StartTime"].ToString()) - ins_elem.start; if (delta > TimeSpan.Zero) { resultList[j].start += delta; resultList[j].fin += delta; } ins_elem.start = resultList[j].fin = resultList[j].start + shift_time; if (!ins_elem.start.Equals(ins_elem.fin)) resultList.Insert(j + 1, ins_elem); } j++; } return resultList; } 

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

 private TimeSpan GetShiftTime(TimeSpan jTime, DataView OldMonthRows, TimeSpan fndTime) { TimeSpan sftTime = jTime; if (OldMonthRows.Count > 0) { //,     . if (fndTime < sftTime) { sftTime = fndTime + TimeSpan.FromMinutes(Convert.ToInt32(OldMonthRows[0]["TimeToNext"])); for (int per_numb_s = 1; per_numb_s < OldMonthRows.Count - 1; per_numb_s++) { if (fndTime >= jTime) break; fndTime += Convert.ToDateTime(OldMonthRows[per_numb_s]["FinTime"]) - Convert.ToDateTime(OldMonthRows[per_numb_s]["StartTime"]); sftTime += Convert.ToDateTime(OldMonthRows[per_numb_s]["FinTime"]) - Convert.ToDateTime(OldMonthRows[per_numb_s]["StartTime"]) + TimeSpan.FromMinutes(Convert.ToInt32(OldMonthRows[per_numb_s]["TimeToNext"])); } sftTime += jTime - fndTime; } } return sftTime; } 

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