WMS प्रणाली लागू करते समय अलग गणित: एक गोदाम में माल के बैचों का क्लस्टरिंग

लेख में बताया गया है कि कैसे कार्यान्वित किया जाए WMS-सिस्टम, हमें एक गैर-मानक क्लस्टरिंग समस्या को हल करने की आवश्यकता का सामना करना पड़ा और इसे हल करने के लिए हमने कौन से एल्गोरिदम का उपयोग किया। हम आपको बताएंगे कि हमने समस्या को हल करने के लिए एक व्यवस्थित, वैज्ञानिक दृष्टिकोण कैसे लागू किया, हमें किन कठिनाइयों का सामना करना पड़ा और हमने क्या सबक सीखा।

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

प्रक्रियाओं में रुकावट

2018 में, हमने कार्यान्वयन के लिए एक परियोजना पूरी की WMS-चेल्याबिंस्क में कंपनी "ट्रेडिंग हाउस "एलडी" के गोदाम में सिस्टम। हमने 1 कार्यस्थलों के लिए उत्पाद "3सी-लॉजिस्टिक्स: वेयरहाउस मैनेजमेंट 20" लागू किया: ऑपरेटर WMS, स्टोरकीपर, फोर्कलिफ्ट ड्राइवर। औसत गोदाम लगभग 4 हजार एम2 है, कोशिकाओं की संख्या 5000 है और एसकेयू की संख्या 4500 है। गोदाम में 1 किलोग्राम से 400 किलोग्राम तक विभिन्न आकारों के हमारे स्वयं के उत्पादन के बॉल वाल्व संग्रहीत हैं। गोदाम में इन्वेंटरी बैचों में संग्रहित की जाती है, क्योंकि फीफो के अनुसार माल का चयन करने की आवश्यकता होती है।

गोदाम प्रक्रिया स्वचालन योजनाओं को डिजाइन करते समय, हमें गैर-इष्टतम इन्वेंट्री भंडारण की मौजूदा समस्या का सामना करना पड़ा। भंडारण और भंडारण क्रेन की विशिष्टताएं ऐसी हैं कि एक इकाई भंडारण कक्ष में केवल एक बैच की वस्तुएं ही हो सकती हैं। उत्पाद प्रतिदिन गोदाम में पहुंचते हैं और प्रत्येक आगमन एक अलग बैच है। कुल मिलाकर, 1 महीने के गोदाम संचालन के परिणामस्वरूप, 30 अलग-अलग बैच बनाए जाते हैं, इस तथ्य के बावजूद कि प्रत्येक को एक अलग सेल में संग्रहित किया जाना चाहिए। उत्पादों को अक्सर पूरे पैलेट में नहीं, बल्कि टुकड़ों में चुना जाता है, और परिणामस्वरूप, कई कोशिकाओं में टुकड़ा चयन क्षेत्र में निम्नलिखित चित्र देखा जाता है: 1 एम 3 से अधिक की मात्रा वाले सेल में क्रेन के कई टुकड़े होते हैं कोशिका आयतन का 5-10% से कम भाग घेरता है।

चित्र 1. एक सेल में सामान के कई टुकड़ों का फोटो

इससे स्पष्ट है कि भंडारण क्षमता का समुचित उपयोग नहीं हो पा रहा है। आपदा के पैमाने की कल्पना करने के लिए, मैं आंकड़े दे सकता हूं: औसतन, गोदाम के संचालन की विभिन्न अवधियों के दौरान "शून्य" शेष के साथ 1 एम 3 से अधिक की मात्रा वाली ऐसी कोशिकाओं की 100 से 300 कोशिकाएं होती हैं। चूँकि गोदाम अपेक्षाकृत छोटा होता है, मौसम के दौरान जब गोदाम भरा होता है, यह कारक एक "अड़चन" बन जाता है और गोदाम प्रक्रियाओं को बहुत धीमा कर देता है।

समस्या समाधान विचार

एक विचार उत्पन्न हुआ: निकटतम तिथियों वाले बचे हुए बैचों को एक ही बैच में कम कर दिया जाना चाहिए, और एकीकृत बैच वाले ऐसे बचे हुए टुकड़ों को एक सेल में, या कई में एक साथ कॉम्पैक्ट रूप से रखा जाना चाहिए, यदि एक में समायोजित करने के लिए पर्याप्त जगह नहीं है बचे हुए भोजन की पूरी मात्रा.

अंक 2। कोशिकाओं में अवशेषों को संपीड़ित करने की योजना

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

ऐसी समस्या को हल करने की प्रक्रिया को 2 चरणों में विभाजित किया गया है:

• पहले चरण में हमें संपीड़न की तारीख के करीब बैचों के समूह मिलते हैं;
• दूसरे चरण में, बैचों के प्रत्येक समूह के लिए हम कोशिकाओं में शेष माल के सबसे कॉम्पैक्ट प्लेसमेंट की गणना करते हैं।

वर्तमान लेख में हम एल्गोरिदम के पहले चरण पर ध्यान केंद्रित करेंगे, और दूसरे चरण का कवरेज अगले लेख के लिए छोड़ देंगे।

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

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

चूँकि यह स्पष्ट रूप से उस समस्या के व्यावसायिक सूत्रीकरण का अनुसरण करता है जिसे हम सेट से निपट रहे हैं, हम सेट सिद्धांत के संदर्भ में ऐसी समस्या तैयार करेंगे।

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

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

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

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

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

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

विचाराधीन समस्या को हल करने के लिए ऐसे एल्गोरिदम का उपयोग करते समय, चित्र 3 जैसी स्थिति उत्पन्न हो सकती है।

चित्र 3. हल ​​की जा रही समस्या के लिए क्लस्टरिंग एल्गोरिदम का अनुप्रयोग

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

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

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

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

इस समस्या का विस्तृत विश्लेषण पाया जा सकता है यहां и यहाँ. कवरिंग समस्या और उसके संशोधनों के व्यावहारिक अनुप्रयोग के लिए अन्य विकल्प पाए जा सकते हैं यहाँ.

समस्या को हल करने के लिए एल्गोरिदम

हमने हल की जाने वाली समस्या का गणितीय मॉडल तय कर लिया है। अब इसे हल करने के लिए एल्गोरिदम पर नजर डालते हैं। सबसेट परिवार से निम्नलिखित प्रक्रिया द्वारा आसानी से पाया जा सकता है।

1. एक सेट से बैच व्यवस्थित करें उनकी तिथियों के घटते क्रम में।
2. न्यूनतम और अधिकतम बैच तिथियाँ ज्ञात करें।
3. हर दिन के लिए न्यूनतम तिथि से अधिकतम तक, उन सभी बैचों को ढूंढें जिनकी तिथियां भिन्न हैं से अधिक नहीं (तो मूल्य सम संख्या लेना बेहतर है)।

समुच्चयों का परिवार बनाने की प्रक्रिया का तर्क में दिन चित्र 4 में प्रस्तुत किये गये हैं।

चित्र.4. पार्टियों के उपसमुच्चय का गठन

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

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

• छोटे आकार की समस्याओं के लिए (और यह बिल्कुल हमारा मामला है), यह उन समाधानों की गणना करता है जो इष्टतम के काफी करीब हैं। जैसे-जैसे समस्या का आकार बढ़ता है, समाधान की गुणवत्ता ख़राब होती जाती है, लेकिन फिर भी धीरे-धीरे;
• लागू करना बहुत आसान है;
• तेज़, चूँकि इसके चलने के समय का अनुमान है .

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

अन्य ज्ञात एल्गोरिदम, जैसे संभाव्य लालची एल्गोरिदम, चींटी कॉलोनी एल्गोरिदम इत्यादि के साथ हल की जा रही समस्या के परीक्षण डेटा पर ऐसे लालची एल्गोरिदम की सटीकता की तुलना नहीं की गई है। उत्पन्न यादृच्छिक डेटा पर ऐसे एल्गोरिदम की तुलना के परिणाम पाए जा सकते हैं काम पर।

एल्गोरिथम का कार्यान्वयन और कार्यान्वयन

यह एल्गोरिथम भाषा में लागू किया गया था 1S और इसे "अवशेष संपीड़न" नामक एक बाहरी प्रसंस्करण में शामिल किया गया था, जो इससे जुड़ा था WMS-प्रणाली। हमने भाषा में एल्गोरिदम लागू नहीं किया सी ++ और इसे बाहरी मूल घटक से उपयोग करें, जो अधिक सही होगा, क्योंकि कोड की गति कम है सी + + कई बार और कुछ उदाहरणों में तो समान कोड की गति से भी दसियों गुना तेज 1S. जीभ पर 1S एल्गोरिदम को विकास के समय को बचाने और ग्राहक के उत्पादन आधार पर डिबगिंग में आसानी के लिए लागू किया गया था। एल्गोरिथम का परिणाम चित्र 5 में प्रस्तुत किया गया है।

चित्र.5. अवशेषों को "संपीड़ित" करने के लिए प्रसंस्करण

चित्र 5 से पता चलता है कि निर्दिष्ट गोदाम में, भंडारण कक्षों में माल की वर्तमान शेष राशि को समूहों में विभाजित किया गया है, जिसके भीतर माल बैचों की तारीखें एक दूसरे से 30 दिनों से अधिक भिन्न नहीं होती हैं। चूंकि ग्राहक गोदाम में मेटल बॉल वाल्व का उत्पादन और भंडारण करता है, जिसकी शेल्फ लाइफ की गणना वर्षों में की जाती है, ऐसे तारीख अंतर को नजरअंदाज किया जा सकता है। ध्यान दें कि ऐसी प्रोसेसिंग वर्तमान में उत्पादन और ऑपरेटरों में व्यवस्थित रूप से उपयोग की जाती है WMS पार्टी क्लस्टरिंग की अच्छी गुणवत्ता की पुष्टि करें।

निष्कर्ष और निरंतरता

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

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

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

स्रोत: www.habr.com