WMS के लिए असतत गणित: कोशिकाओं में वस्तुओं को संपीड़ित करने के लिए एल्गोरिथ्म (भाग 1)

लेख में, हम आपको बताएंगे कि इस समस्या को हल करने के लिए गोदाम में नि: शुल्क कोशिकाओं की कमी और असतत अनुकूलन एल्गोरिदम के विकास की समस्या को कैसे हल किया जाए। हम ऑप्टिमाइज़ेशन समस्या के गणितीय मॉडल को "हम" कैसे बनाएंगे, और एल्गोरिथ्म के लिए इनपुट डेटा को संसाधित करते समय हमें अप्रत्याशित रूप से क्या कठिनाइयों का सामना करना पड़ा, इसके बारे में बात करेंगे।

यदि आप व्यवसाय में गणितीय अनुप्रयोगों में रुचि रखते हैं और आप 5 वीं कक्षा के स्तर पर सूत्रों के कठिन समान परिवर्तनों से डरते नहीं हैं, तो बिल्ली में आपका स्वागत है!

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

परिचयात्मक भाग

यह प्रकाशन लेखों की श्रृंखला को जारी रखता है जिसमें हम गोदाम प्रक्रियाओं में अनुकूलन एल्गोरिदम को लागू करने में अपने सफल अनुभव को साझा करते हैं।

पिछले लेख में गोदाम की बारीकियों का वर्णन किया गया था जिसमें हमने डब्ल्यूएमएस प्रणाली की शुरुआत की थी, और यह भी बताया कि डब्ल्यूएमएस प्रणाली को लागू करने के दौरान हमें माल की खेप के स्टॉक की समस्या को हल करने की आवश्यकता क्यों है, और हमने इसे कैसे किया।

जब हमने अनुकूलन एल्गोरिदम पर एक लेख लिखना समाप्त किया, तो यह बहुत बड़ा हो गया, इसलिए हमने संचित सामग्री को 2 भागों में विभाजित करने का निर्णय लिया:

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

कैसे एक लेख पढ़ने के लिए। यदि आप पिछले लेख को पढ़ते हैं, तो आप तुरंत "मौजूदा समाधानों का अवलोकन" अध्याय पर जा सकते हैं, यदि नहीं, तो नीचे दिए गए स्पॉइलर में हल की जाने वाली समस्या का विवरण।

मौजूदा समाधानों का अवलोकन

हमारे द्वारा विकसित एल्गोरिदम के विवरण पर आगे बढ़ने से पहले, बाजार पर मौजूदा डब्ल्यूएमएस सिस्टम की एक संक्षिप्त समीक्षा करना उचित है जो समान इष्टतम संपीड़न कार्यक्षमता को लागू करते हैं।

सबसे पहले, यह आवश्यक है कि उत्पाद "1C: एंटरप्राइज 8. डब्ल्यूएमएस लॉजिस्टिक्स" पर ध्यान दिया जाए। वेयरहाउस प्रबंधन 4 ”, जो 1 सी द्वारा स्वामित्व और प्रतिकृति है और एक्सिलॉट द्वारा विकसित डब्ल्यूएमएस सिस्टम की चौथी पीढ़ी के अंतर्गत आता है। इस प्रणाली में, संपीड़न कार्यक्षमता घोषित की जाती है, जिसे एक सामान्य सेल में असमान उत्पाद अवशेषों को संयोजित करने के लिए डिज़ाइन किया गया है। यह ध्यान देने योग्य है कि ऐसी प्रणाली में संपीड़न कार्यक्षमता में अन्य विशेषताएं भी शामिल हैं, उदाहरण के लिए, उनकी एबीसी कक्षाओं के अनुसार कोशिकाओं में माल की नियुक्ति को सही करना, लेकिन हम उन पर ध्यान नहीं देंगे।

यदि आप सिस्टम के कोड का विश्लेषण करते हैं "1C: एंटरप्राइज 8. डब्ल्यूएमएस लॉजिस्टिक्स। वेयरहाउस प्रबंधन 4 ”(जो कार्यात्मक के इस हिस्से में खुला है), तो हम निम्नलिखित निष्कर्ष निकाल सकते हैं। अवशिष्ट संपीड़न एल्गोरिथ्म एक बल्कि आदिम रैखिक तर्क को लागू करता है और किसी भी "इष्टतम" संपीड़न की कोई बात नहीं हो सकती है। स्वाभाविक रूप से, वह पार्टियों के क्लस्टरिंग के लिए प्रदान नहीं करता है। इस तरह की प्रणाली के साथ कई ग्राहकों ने संपीड़न योजना के परिणामों के बारे में शिकायत की। उदाहरण के लिए, अक्सर संपीड़न के दौरान व्यवहार में निम्न स्थिति होती है: 100 पीसी। यह शेष सामान को एक सेल से दूसरे सेल में स्थानांतरित करने की योजना है, जहां 1 पीसी झूठ है। माल, हालांकि यह विपरीत करने के लिए समय के संदर्भ में इष्टतम है।

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

किसी समस्या के गणितीय मॉडल की खोज करें

किसी समस्या को हल करने के लिए उच्च-गुणवत्ता वाले एल्गोरिदम को डिजाइन करने के लिए, गणितीय रूप से इस समस्या को स्पष्ट रूप से तैयार करना आवश्यक है, जो हम करेंगे।

कई सेल हैं $$$जे$ जिसमें कुछ सामानों के अवशेष हैं। इसके अलावा, ऐसी कोशिकाओं को दाता कोशिकाएं कहा जाएगा। हम निरूपित करते हैं $$$w_j$ सेल में माल की मात्रा $$$$ $$ $।

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

कई सेल हैं $$$मैं$ जिसमें दाता कोशिकाओं के अवशेष संभावित रूप से रखे जा सकते हैं। ऐसी कोशिकाओं को कंटेनर सेल कहा जाएगा। ये या तो गोदाम में मुफ्त कोशिकाएं हो सकती हैं या विभिन्न प्रकार से दाता कोशिकाएं $$$जे$ । हमेशा बहुत कुछ $$$जे$ का सबसेट है $$$मैं$ ।

प्रत्येक कोशिका के लिए $$$मैं$ बहुत से $$$मैं$ क्षमता सीमा निर्धारित है $$$d_i$ dm3 में मापा जाता है। एक डीएम 3 10 सेमी के पक्षों के साथ एक घन है। गोदाम में संग्रहीत उत्पाद काफी बड़े हैं, इसलिए इस मामले में, इस तरह का विवेक पर्याप्त है।

सबसे कम दूरी का मैट्रिक्स $$$s_ {ij}$ प्रत्येक जोड़ी कोशिकाओं के बीच मीटर में $$$(i, j)$ जहाँ $$$मैं$ और $$$ज$ सेट के हैं $$$मैं$ और $$$जे$ क्रमशः।

हम निरूपित करते हैं $$$S_ {ij}$ सेल से सामान ले जाने के लिए "लागत" $$$मैं$ सेल करने के लिए $$$ज$ । हम निरूपित करते हैं $$$D_i$ कंटेनर चुनने के लिए "लागत" $$$मैं$ इसमें अन्य कोशिकाओं से अवशेषों को स्थानांतरित करने के लिए। कितनी सही और किस माप की इकाइयों में मूल्यों की गणना की जाएगी $$$S_ {ij}$ और $$$D_i$ हम आगे विचार करेंगे (इनपुट डेटा अनुभाग की तैयारी देखें), अब यह कहना पर्याप्त है कि ऐसी मात्रा सीधे मात्राओं के अनुपात में होगी $$$s_ {ij}$ और $$$d_i$ क्रमशः।

द्वारा निरूपित करें $$$x_ {ij}$ एक चर जो सेल के शेष रहने पर 1 मान लेता है $$$ज$ कंटेनर में जाएँ $$$मैं$ , और 0 अन्यथा। द्वारा निरूपित करें $$$y_i$ चर मान 1 अगर कंटेनर $$$मैं$ उत्पाद के अवशेष शामिल हैं, और अन्यथा 0।

कार्य निम्नानुसार है : इतने सारे कंटेनरों को खोजना आवश्यक है $$$I ^ *$ और इस प्रकार फ़ंक्शन को कम करने के लिए सेल कंटेनर में दाता कोशिकाओं को "संलग्न" करें

$$

$$\ min {F} = \ _ _ {i \ _ in, ~ j \ _ in} J} ^ {} S_ {ij} \ cdot x_ {ij} + \ sum _ {i_ in I} ^ {{} D_ { i} \ cdot y_ {i}$$

प्रतिबंधों के तहत

$$

$$\ sum _ {j \ _ in J} ^ {} w_ {j} \ cdot x_ {ij} \ leq d_ {i} \ cdot y_ {i}, ~ के लिए ~ हर कोई ~ i \ _ in$$

कुल मिलाकर, समस्या के समाधान की गणना करने के दौरान, हम निम्नलिखित प्रयास करते हैं:

• सबसे पहले, भंडारण क्षमता को बचाने;
• दूसरी बात, दुकानदारों का समय बचाना।

अंतिम प्रतिबंध का मतलब है कि हम उन सामानों को कंटेनर में नहीं ले जा सकते हैं जिन्हें हमने नहीं चुना है, और इसलिए, उनकी पसंद के अनुसार "खर्च नहीं" किया है। इस प्रतिबंध का यह भी अर्थ है कि कोशिकाओं से कंटेनर में ले जाने वाले सामान की मात्रा कंटेनर की क्षमता से अधिक नहीं होनी चाहिए। समस्या के समाधान से हमारा मतलब बहुत सारे कंटेनरों से है $$$I ^ *$ और डोनर कोशिकाओं को कंटेनरों में संलग्न करने के तरीके।

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

• शहरों की एक सीमित संख्या है जहां विनिर्माण उद्यमों का पता लगाना संभव है (इसके बाद शहरों का निर्माण)। प्रत्येक विनिर्माण शहर के लिए, इसमें एक उद्यम खोलने की लागत, साथ ही इसमें खोले गए उद्यम की उत्पादन क्षमता पर प्रतिबंध भी निर्धारित हैं।
• शहरों की एक सीमित संख्या है जहां ग्राहक वास्तव में स्थित हैं (बाद में ग्राहक शहरों के रूप में संदर्भित)। ऐसे प्रत्येक ग्राहक शहर के लिए, उत्पादों की मांग की मात्रा निर्धारित है। सादगी के लिए, हम मानते हैं कि उत्पाद जो उत्पाद बनाते हैं और ग्राहकों का उपभोग करते हैं वह एक है।
• प्रत्येक जोड़ी के लिए, निर्माता शहर और ग्राहक शहर, निर्माता से उत्पादों की आवश्यक मात्रा के वितरण के लिए परिवहन लागत का मूल्य निर्धारित किया जाता है।

यह पता लगाना आवश्यक है कि किन शहरों में उद्यम खोलने हैं और ग्राहकों को ऐसे उद्यमों से कैसे जोड़ा जाए:

• उद्यम खोलने और परिवहन लागत की कुल लागत न्यूनतम थी;
• किसी भी खुले उद्यम से जुड़ी ग्राहक की माँग की मात्रा इस उद्यम की उत्पादन क्षमताओं से अधिक नहीं थी।

अब यह इन दो शास्त्रीय समस्याओं में एकमात्र अंतर का उल्लेख करने योग्य है:

• एकल-स्रोत कैपेसिटेड सुविधा स्थान समस्या - ग्राहक को केवल एक खुले उद्यम से आपूर्ति की जाती है;
• मल्टी-सोर्स कैपेसिटेड सुविधा स्थान समस्या - एक ग्राहक को एक ही समय में कई खुले उद्यमों से आपूर्ति की जा सकती है।

पहली नज़र में दो समस्याओं के बीच ऐसा अंतर नगण्य है, लेकिन, वास्तव में, इस तरह की समस्याओं की एक पूरी तरह से अलग संयोजन संरचना की ओर जाता है और, परिणामस्वरूप, उन्हें हल करने के लिए पूरी तरह से अलग एल्गोरिदम। कार्यों के बीच के अंतर नीचे दिए गए आंकड़े में दिखाए गए हैं।


चित्र 3। क) मल्टी-सोर्स कैपेसिटेड सुविधा स्थान समस्या


चित्र 3। ख) एकल स्रोत संधारित्र सुविधा स्थान समस्या

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

यदि हम कोशिकाओं में वस्तुओं के इष्टतम संपीड़न की हमारी समस्या की शब्दावली में बदलाव करते हैं, तो:

• ग्राहक शहर दाता कोशिकाएं हैं $$$जे$ माल के अवशेष के साथ,
• विनिर्माण शहर - कंटेनर सेल $$$मैं$ जिसमें यह अन्य कोशिकाओं से अवशेष रखने के लिए माना जाता है,
• परिवहन लागत - समय लागत $$$S_ {ij}$ स्टोर कीपर दाता सेल से माल की मात्रा को स्थानांतरित करने के लिए $$$ज$ कंटेनर सेल के लिए $$$मैं$ ;
• एक उद्यम खोलने की लागत - एक कंटेनर चुनने की लागत $$$D_i$ कंटेनर सेल की मात्रा के बराबर $$$मैं$ मुक्त संस्करणों की अर्थव्यवस्था के एक निश्चित गुणांक से गुणा किया जाता है (गुणांक का मूल्य हमेशा> 1 होता है) (इनपुट डेटा तैयार करने वाला अनुभाग देखें)।

समस्या के प्रसिद्ध शास्त्रीय प्रसव के साथ सादृश्य के बाद, यह महत्वपूर्ण प्रश्न का उत्तर देने के लिए आवश्यक है, जिस पर समाधान एल्गोरिदम की वास्तुकला का विकल्प निर्भर करता है: दाता सेल से अवशेषों की आवाजाही केवल एक और केवल एक कंटेनर (एकल-स्रोत) में संभव है, या अवशेषों की आवाजाही संभव है। कई कंटेनर कोशिकाओं (मल्टी-सोर्स) में?

यह ध्यान देने योग्य है कि व्यवहार में समस्या के दोनों योगों का एक स्थान है। हम नीचे ऐसे प्रत्येक कथन के लिए सभी पेशेवरों और विपक्षों को देते हैं:
तालिका 1. एकल-स्रोत और बहु-स्रोत विकल्पों के पेशेवरों और विपक्ष।

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

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

इनपुट तैयार करना

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

सबसे पहले, हम एक डोनर सेल से कंटेनर सेल में सामान ले जाने की लागत की गणना पर विचार करते हैं। सबसे पहले, यह निर्धारित करना आवश्यक है कि माप की कौन सी इकाइयों में हम चलने की लागत की गणना करेंगे। दो सबसे स्पष्ट विकल्प मीटर और सेकंड हैं। "स्वच्छ" मीटर में, चलने की लागत व्यर्थ है। हम इसे उदाहरण के द्वारा दिखाते हैं। सेल करते हैं $$$ए$ पहली श्रेणी, सेल पर स्थित है $$$को$ हटा दिया गया 30 मीटर और दूसरी श्रेणी पर स्थित है:

• निकल रहा है $$$ए$ में $$$ब$ से अधिक महंगा है $$$ब$ में $$$ए$ , क्योंकि दूसरे स्तर से नीचे गिरना (मंजिल से 1.5-2 मीटर), इसे दूसरे से ऊपर उठाने की तुलना में आसान है, हालांकि दूरी समान होगी;
• 1 पीसी ले जाएँ। सेल से माल $$$ए$ में $$$ब$ यह 10 पीसी स्थानांतरित करने से आसान होगा। एक ही उत्पाद की, हालांकि दूरी समान होगी।

आंदोलन की लागत को सेकंड में ध्यान में रखा जाता है, क्योंकि यह आपको टियर में अंतर और परिवहन किए गए सामान की मात्रा में अंतर को ध्यान में रखने की अनुमति देता है। सेकंड में आंदोलन की लागत का हिसाब करने के लिए, हमें प्राथमिक घटकों पर जाने के संचालन को विघटित करना चाहिए और प्रत्येक प्राथमिक घटक के लिए समय का माप लेना चाहिए।

सेल से करते हैं $$$ज$ चाल $$$N_j$ पीसी। कंटेनर के लिए माल $$$मैं$ । चलो $$$S_ {रन}$ - गोदाम में कर्मचारी की औसत गति, मीटर / एस में मापा जाता है। चलो $$$S_ {मिलता है}$ और $$$S_ {डाल}$ - सामानों की मात्रा के लिए क्रमशः ४ डीएम ३ के बराबर माल लेने के लिए परिचालनों के एक एकल निष्पादन की औसत गति (औसत मात्रा जो गोदाम में एक कर्मचारी संचालन के दौरान १ बार लेता है)। चलो $$$H_ {मिलता है}$ और $$$H_ {डाल}$ उन कोशिकाओं की ऊँचाई जिनसे ऑपरेशन किए जाते हैं, तदनुसार ली जाती हैं। उदाहरण के लिए, पहली टियर (मंजिल) की औसत ऊंचाई 1 मीटर, दूसरी टियर 2 मीटर, आदि है। फिर चाल ऑपरेशन को पूरा करने के लिए कुल समय की गणना करने का सूत्र $$$T_ {ij}$ निम्नलिखित:

$$

$$T_ {ij} = \ left (N_ {j} \ cdot \ frac {w_ {j}} {4} \ right) \ cdot S_ {get} \ cdot H_ {get} + s_ {idot} \ cdot S_ { रन} + \ लेफ्ट (N_ {j} \ cdot \ frac {w_ {j}} {4} \ right) \ cdot S_ {put} \ cdot H_ {put}। $$$

तालिका 2 गोदाम कर्मचारियों द्वारा संग्रहीत प्रत्येक प्राथमिक संचालन के निष्पादन समय के आंकड़ों को दर्शाती है, संग्रहीत सामान की बारीकियों को ध्यान में रखते हुए।
तालिका 2. गोदाम संचालन करने का औसत समय

निर्णय की लागत की गणना की विधि के साथ। अब आपको यह पता लगाने की आवश्यकता है कि कंटेनर सेल चुनने की लागत की गणना कैसे करें। यहां, सब कुछ बहुत अधिक जटिल है, जो लागत की तुलना में अधिक जटिल है, क्योंकि:

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

अंजीर। 4. अवशेषों को विभिन्न क्षमताओं के कंटेनरों में स्थानांतरित करने के विकल्प।

चित्रा 4 अवशेषों की मात्रा को दर्शाता है जो बाद के सामानों के प्लेसमेंट के दूसरे चरण में कंटेनर में फिट नहीं होते हैं।

समस्या के लिए गणना किए गए समाधानों के लिए निम्नलिखित आवश्यकताएं परिवहन लागत के सेकंड के साथ कंटेनर लागत के घन मीटर को जोड़ने में मदद करेंगी:

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

चलो आखिरी आवश्यकता से शुरू करते हैं। अस्पष्ट शब्द "बैलेंस" को निर्दिष्ट करने के लिए, हमने निम्नलिखित पता लगाने के लिए गोदाम कर्मचारियों का एक सर्वेक्षण किया। सेल कंटेनर की मात्रा होने दें$$$d_0$ , जिसमें दाता कोशिकाओं से माल के अवशेष के आंदोलन को सौंपा गया है और इस तरह के आंदोलन का कुल समय है $$$T_0$ । मान लीजिए कि एक ही दाता कोशिकाओं से समान मात्रा में सामान को अन्य कंटेनरों में रखने के लिए कई वैकल्पिक विकल्प हैं, जहां प्रत्येक प्लेसमेंट की अपनी रेटिंग है $$$d_1$ जहाँ $$$d_1$ < $$$d_0$ और $$$T_1$ जहाँ $$$T_1$ > $$$T_0$ ।

सवाल यह है: वॉल्यूम में न्यूनतम लाभ क्या है $$$d_0-d_1$ समय की हानि के लिए स्वीकार्य मूल्य $$$T_1-T_0$ ?आइए एक उदाहरण से स्पष्ट करें। प्रारंभ में, अवशेषों को 1000 dm3 (1 m3) मात्रा के कंटेनर में रखा जाना चाहिए था और यात्रा का समय 70 सेकंड था। 500 डीएम 3 के एक कंटेनर में अवशेषों को रखने और 130 सेकंड के समय का एक विकल्प है। प्रश्न: क्या हम मुफ्त में ५०० dm3 बचाने के लिए दुकानदार के अतिरिक्त ६० सेकंड का समय व्यतीत करने के लिए तैयार हैं? गोदाम कर्मचारियों के एक सर्वेक्षण के आधार पर, निम्नलिखित चार्ट संकलित किया गया था।


अंजीर। 5. ऑपरेशन समय में अंतर में वृद्धि पर न्यूनतम स्वीकार्य मात्रा बचत की निर्भरता का आरेख।

यही है, अगर अतिरिक्त समय की लागत 40 सेकंड है, तो हम उन्हें केवल तब खर्च करने के लिए तैयार हैं जब मात्रा में लाभ कम से कम 500 dm3 हो। इस तथ्य के बावजूद कि आगे की गणना की सादगी के लिए, निर्भरता में थोड़ी सी असावधानी देखी जाती है, हम मानते हैं कि मात्राओं के बीच निर्भरता रैखिक है और असमानता द्वारा वर्णित है

$$

$$\frac{d_{0}-d_{1}}{10} \geq T_{1}-T_{0}$$

नीचे दिए गए आंकड़े में, हम कंटेनरों में सामान रखने के निम्नलिखित तरीकों पर विचार करते हैं।


अंजीर। 6. विकल्प (ए): 2 कंटेनर, कुल मात्रा 400 डीएम 3, कुल समय 150 सेकंड।

अंजीर। 6. विकल्प (बी): 2 कंटेनर, कुल मात्रा 600 डीएम 3, कुल समय 190 सेकंड।

अंजीर। 6. विकल्प (ओं): 1 कंटेनर, कुल मात्रा 400 dm3, कुल समय 200 सेकंड।

कंटेनरों की पसंद का विकल्प (ए) मूल विकल्प की तुलना में अधिक बेहतर है, क्योंकि असमानता रखती है: (800-400) / 10> = 150-120, जिसका अर्थ है 40> = 30. विकल्प (बी) मूल विकल्प से कम पसंद किया जाता है। , क्योंकि असमानता पकड़ में नहीं आती है: (800-600) / 10> = 190-150, जिसका अर्थ है 20> = 40. लेकिन विकल्प (c) इस तर्क में फिट नहीं होता है! इस विकल्प पर अधिक विस्तार से विचार करें। एक तरफ, असमानता (800-400) / 10> = 200-120, जिसका अर्थ है कि असमानता 40> = 80 पूरी नहीं हुई है, जो इंगित करता है कि मात्रा में लाभ समय में इतने बड़े नुकसान के लायक नहीं है।

लेकिन दूसरी ओर, इस विकल्प (सी) में, हम न केवल कुल कब्जे की मात्रा को कम करते हैं, बल्कि कब्जे वाली कोशिकाओं की संख्या को भी कम करते हैं, जो ऊपर सूचीबद्ध समस्याओं के लिए गणना किए गए समाधानों के लिए दो महत्वपूर्ण आवश्यकताओं में से पहला है। जाहिर है, इस आवश्यकता को पूरा करने के लिए शुरू करने के लिए, असमानता के बाईं ओर कुछ सकारात्मक निरंतर जोड़ना आवश्यक है $$$कास्ट$ , और कंटेनर की संख्या कम होने पर ही इस तरह की निरंतरता को जोड़ने की आवश्यकता होती है। उसको याद करो $$$y_i$ कंटेनर के 1 के बराबर एक चर है $$$मैं$ चयनित, और जब कंटेनर $$$मैं$ चयनित नहीं है। निरूपित, $$$I_0$ - मूल समाधान में कई कंटेनर और $$$I_1$ - नए समाधान में बहुत सारे कंटेनर। सामान्य शब्दों में, नई असमानता इस तरह दिखाई देगी:

$$

$$\ sum _ {i \ _ I_ {0}} ^ {} \ frac {d_ {i}} {10} + कांस्टेंट \ _ \ _ \ _ I_ {0}} ^ {} y_ {i} में - {लेफ्ट (\ _ _ {I_ in I_ {1}} ^ {} \ frac {d_ {i}} {10} + कांस्टेंट \ _ \ _ \ _ I_ {1}} ^ {} y_ {i} \ right) \ geq T_ {1} -T_ {0}$$

ऊपर असमानता को बदलने, हम प्राप्त करते हैं

$$

$$\ sum _ {i \ _ I_ {0}} ^ {} \ frac {d_ {i}} {10} + कांस्टेंट \ _ \ _ \ _ I_ {0}} ^ {} y_ {i} में + T_ {0} \ _ geq \ sum _ {i_ in I_ {1}} ^ {} \ frac {d_ {i}} {10} + कांस्टेंट \ _ \ _ I_ {1}} ^ {{Y_ {i} + T_ {1}$$

इसके आधार पर, हमारे पास कुल लागत की गणना करने का एक सूत्र है $$$F_k$ समस्या का कुछ हल:

$$

$$F_ {k} = \ sum _ {i_ in I_ {k}} ^ {} \ _ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ _ in_ {k}} ^ {} } y_ {i} + T_ {k}।$$

लेकिन अब सवाल उठता है : ऐसे स्थिरांक का क्या मूल्य होना चाहिए? $$$कास्ट$ ? जाहिर है, इसका मूल्य काफी बड़ा होना चाहिए ताकि समस्या के समाधान के लिए पहली आवश्यकता हमेशा पूरी हो। आप निश्चित रूप से 10 ³ या 10 ^{6 के} बराबर निरंतर मूल्य ले सकते हैं, लेकिन मैं इस तरह के "मैजिक नंबरों" से बचना चाहूंगा। यदि हम गोदाम संचालन करने की बारीकियों पर विचार करते हैं, तो हम ऐसे स्थिरांक के परिमाण के कई अच्छी तरह से स्थापित संख्यात्मक अनुमानों की गणना कर सकते हैं।

चलो $$$S_ {अधिकतम}$ - एक क्षेत्र एबीसी के गोदाम की कोशिकाओं के बीच अधिकतम दूरी, हमारे मामले में 100 मीटर के बराबर है $$$d_ {अधिकतम}$ - गोदाम में सेल कंटेनर की अधिकतम मात्रा, हमारे मामले में 1000 dm3 के बराबर।

मूल्य की गणना करने का पहला तरीका $$$कास्ट$ । उस स्थिति पर विचार करें जब पहली टियर पर 2 कंटेनर होते हैं जिसमें माल पहले से ही भौतिक रूप से स्थित होता है, अर्थात, वे स्वयं दाता कोशिकाएं हैं, और सामान को एक ही कोशिकाओं में ले जाने की लागत स्वाभाविक रूप से 0. है, इस तरह के एक निरंतर मूल्य को खोजने के लिए आवश्यक है $$$कास्ट$ जिसमें हमेशा कंटेनर 1 से कंटेनर 2 के अवशेषों को स्थानांतरित करना लाभप्रद होगा। मूल्यों को प्रतिस्थापित करना $$$S_ {अधिकतम}$ और $$$d_ {अधिकतम}$ ऊपर असमानता में, हम प्राप्त करते हैं:

$$

$$\ frac {d_ {अधिकतम}} {10} + कांस्टेंट जिक S_ {अधिकतम} \ cdot s_ {रन} + \ frac {d_ {अधिकतम}} {4} \ left (s_ {get) + s {{पु}} $$$

इस प्रकार है

$$

$$Const \ geq S_ {max} \ cdot s_ {run} + d_ {max} \ left (\ frac {s_ {get} + s_ {put}} {4} - \ frac {1} {10} / सही) ।$$

उपरोक्त सूत्र में प्राथमिक संचालन के औसत निष्पादन समय के मूल्यों को प्रतिस्थापित करते हुए, हम प्राप्त करते हैं

$$

$$Const \ geq 100 \ cdot 1.5 + 1000 \ left (\ frac {9} {10} \ right) \ rightarrow Const \ geq 1050.$$

मूल्य की गणना करने का दूसरा तरीका $$$कास्ट$ । ऐसी स्थिति पर विचार करें जहां पर है $$$एन$ डोनर सेल्स जिसमें से माल को कंटेनर में ले जाने की योजना है। डेनेट $$$S_ {1j}$ - डोनर सेल से दूरी $$$ज$ कंटेनर 1. कंटेनर 2 भी है, जिसमें पहले से ही सामान हैं, और जिसकी मात्रा आपको शेष को समायोजित करने की अनुमति देती है $$$एन$ कोशिकाओं। सादगी के लिए, हम मान लेंगे कि डोनर सेल से कंटेनरों तक ले जाने वाले सामान की मात्रा समान और बराबर है $$$d_ {अधिकतम} / N$ । ऐसे निरंतर मूल्य को खोजने के लिए आवश्यक है $$$कास्ट$ जिस पर सभी अवशेषों की नियुक्ति $$$एन$ कंटेनर 2 में कोशिकाएं हमेशा विभिन्न कंटेनरों में रखने से अधिक लाभदायक होंगी:

$$

$$2 \ cdot \ frac {d_ {अधिकतम}} {10} +2 \ cdot Const + N \ left (S_ {1j} \ cdot s_ {रन} + \ frac {d_ {max}} {4 \ _ cdot N} \ _ बाएं (s_ {get} + s_ {put} \ right) \ right) \ geq \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ qquad \ fquad \ drac {d_ {max}} {} 10} + कॉन्स्टेंट + एन \ cdot \ left (S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \ left (s_ {get} + s_ {put \ _ \ _) ) \ _)$$

हमें जो विषमता मिलती है, उसे बदलना

$$

$$\ frac {d_ {अधिकतम}} {10} + कॉन्स्ट + एन \ _ कॉड S_ {1j} \ cdot s_ {रन} \ geq N \ cdot S_ {मैक्स} \ cdot s_ {रन} राइटर्सरो कॉन्स्टेंट \ geq N \ _ cdot s_ {run} \ left (S_ {max} -S_ {1j} \ right) - \ frac {d_ {max}} {10}। $$$

मात्रा के मूल्य को "मजबूत" करने के लिए $$$कास्ट$ , हम यह मान लेते हैं $$$S_ {1j}$ = 0. स्टॉक बैलेंस को संपीड़ित करने की प्रक्रिया में शामिल होने वाली कोशिकाओं की औसत संख्या 10. है। मात्राओं के ज्ञात मूल्यों को प्रतिस्थापित करना, हमारे पास निम्नलिखित निरंतर मूल्य हैं

$$

$$Const \ geq 10 \ cdot 1.5 \ cdot 100- \ frac {1000} {10} \ rightarrow कॉन्स्टेंट \ geq 1400.$$

हम प्रत्येक विकल्प के लिए गणना की गई सबसे बड़ी कीमत लेते हैं, यह मूल्य होगा $$$कास्ट$ दिए गए गोदाम मापदंडों के लिए। अब पूर्णता के लिए, हम कुल लागतों की गणना के लिए सूत्र लिखते हैं $$$F_k$ कुछ संभव समाधान के लिए $$$k$ :

$$

$$F_ {k} = \ _ _ _ I_ {k}} में ^ {} \ frac {d_ {i}} {10} +1400 \ cdot \ sum _ {i \ _ in_ {k}} ^ {} } y_ {i} + T_ {k}।$$

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

निष्कर्ष

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

अगले लेख में, हम अंत में वही आएंगे जो पिछले 2 प्रकाशनों ने सोचा था - असतत अनुकूलन एल्गोरिथम।

एक लेख तैयार किया
रोमन शगिन, प्रोग्रामर, परियोजना विभाग,
पहली बिट कंपनी, चेल्याबिंस्क