शेड्यूलिंग कक्षाओं में आंकड़े

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

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

इसलिए, कक्षाओं की एक साप्ताहिक अनुसूची बनाने के लिए कंप्यूटर को सिखाना आवश्यक था, और यथासंभव सर्वोत्तम। खोज स्थान के पैमाने को महसूस करते हुए, उन्होंने सबसे अच्छा विकल्प खोजने का लक्ष्य निर्धारित नहीं किया। पहले आपको यह निर्धारित करने की आवश्यकता है कि क्या वर्ग हैं और क्या अच्छा है और क्या बुरा है। निम्नलिखित मॉडल को चुना गया था जिसके लिए ऐसा इनपुट डेटा:
- एक सप्ताह में दिनों की संख्या
- प्रति दिन पाठ की संख्या
- शिक्षकों की सूची
- समूहों, उपसमूहों और धाराओं की सूची
- एक विशेष प्रकार के लिए दर्शकों की संख्या
- कार्यों के समूहों का एक समूह (कक्षाएं):

• कब्जे
• प्रोफ़ेसर
• धारा या समूह
• दर्शकों का प्रकार
• वर्गों के इस समूह में कक्षाओं की संख्या
• समय, अगर निर्देशक एक निश्चित समय पर "सबक" इस पाठ को स्थापित करना चाहता है

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



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

पुनश्च। बाद में, जब मैंने पेजरैंक के बारे में सुना, तो मुझे लगा कि इसमें कुछ ऐसा ही है।