WMS साठी वेगळे गणित: पेशींमध्ये वस्तू संकुचित करण्यासाठी अल्गोरिदम (भाग 1)

या लेखात आम्ही तुम्हाला सांगू की आम्ही वेअरहाऊसमध्ये मुक्त पेशींच्या कमतरतेची समस्या कशी सोडवली आणि अशा समस्येचे निराकरण करण्यासाठी स्वतंत्र ऑप्टिमायझेशन अल्गोरिदम विकसित केला. आपण ऑप्टिमायझेशन समस्येचे गणितीय मॉडेल कसे "बांधले" याबद्दल आणि अल्गोरिदमसाठी इनपुट डेटावर प्रक्रिया करताना आपल्याला अनपेक्षितपणे आलेल्या अडचणींबद्दल बोलूया.

जर तुम्हाला व्यवसायातील गणिताच्या ऍप्लिकेशन्समध्ये स्वारस्य असेल आणि तुम्हाला 5 व्या इयत्तेच्या स्तरावर सूत्रांच्या कठोर ओळख परिवर्तनाची भीती वाटत नसेल, तर मांजरीमध्ये आपले स्वागत आहे!

अंमलबजावणी करणाऱ्यांना लेख उपयुक्त ठरेल WMS-सिस्टम, वेअरहाऊस किंवा उत्पादन लॉजिस्टिक उद्योगात काम करतात, तसेच व्यवसायातील गणिताच्या अनुप्रयोगांमध्ये आणि एंटरप्राइझमधील प्रक्रियेच्या ऑप्टिमायझेशनमध्ये स्वारस्य असलेले प्रोग्रामर.

प्रास्ताविक भाग

हे प्रकाशन लेखांची मालिका सुरू ठेवते ज्यामध्ये आम्ही वेअरहाऊस प्रक्रियेमध्ये ऑप्टिमायझेशन अल्गोरिदम लागू करण्याचा आमचा यशस्वी अनुभव शेअर करतो.

В मागील लेख आम्ही लागू केलेल्या वेअरहाऊसच्या वैशिष्ट्यांचे वर्णन करते WMS-सिस्टम, आणि अंमलबजावणी दरम्यान उरलेल्या वस्तूंच्या क्लस्टरिंग बॅचची समस्या का सोडवायची हे देखील स्पष्ट करते WMS-सिस्टम आणि आम्ही ते कसे केले.

जेव्हा आम्ही ऑप्टिमायझेशन अल्गोरिदमवर लेख लिहिणे पूर्ण केले, तेव्हा ते खूप मोठे असल्याचे दिसून आले, म्हणून आम्ही जमा केलेली सामग्री 2 भागांमध्ये विभाजित करण्याचा निर्णय घेतला:

• पहिल्या भागात (हा लेख) आम्ही समस्येचे गणितीय मॉडेल कसे "बांधले" याबद्दल आणि अल्गोरिदमसाठी इनपुट डेटावर प्रक्रिया आणि रूपांतरित करताना आम्हाला अनपेक्षितपणे आलेल्या मोठ्या अडचणींबद्दल बोलू.
• दुसऱ्या भागात आपण भाषेतील अल्गोरिदमच्या अंमलबजावणीचा तपशीलवार विचार करू C ++, आम्ही एक संगणकीय प्रयोग आयोजित करू आणि ग्राहकाच्या व्यवसाय प्रक्रियेत अशा "बुद्धिमान तंत्रज्ञान" च्या अंमलबजावणीदरम्यान आम्हाला मिळालेल्या अनुभवाचा सारांश देऊ.

लेख कसा वाचायचा. जर तुम्ही मागील लेख वाचला असेल, तर तुम्ही ताबडतोब "अस्तित्वात असलेल्या उपायांचे विहंगावलोकन" या धड्यावर जाऊ शकता; नसल्यास, समस्येचे निराकरण केले जात असल्याचे वर्णन खाली स्पॉयलरमध्ये आहे.

ग्राहकाच्या गोदामात सोडवल्या जात असलेल्या समस्येचे वर्णन

प्रक्रियेतील अडथळे

2018 मध्ये, आम्ही अंमलबजावणीसाठी एक प्रकल्प पूर्ण केला WMS-चेल्याबिन्स्कमधील वेअरहाऊस “ट्रेडिंग हाऊस “एलडी” मधील सिस्टम. आम्ही 1 कार्यस्थळांसाठी "3C-लॉजिस्टिक्स: वेअरहाऊस मॅनेजमेंट 20" उत्पादन लागू केले: ऑपरेटर WMS, स्टोअरकीपर, फोर्कलिफ्ट चालक. सरासरी गोदाम सुमारे 4 हजार m2 आहे, पेशींची संख्या 5000 आहे आणि SKU ची संख्या 4500 आहे. गोदामात 1 किलो ते 400 किलो पर्यंत विविध आकाराचे आमच्या स्वतःच्या उत्पादनाचे बॉल वाल्व्ह साठवले जातात. वेअरहाऊसमधील इन्व्हेंटरी बॅचमध्ये साठवली जाते, कारण FIFO नुसार माल निवडणे आवश्यक आहे.

वेअरहाऊस प्रक्रिया ऑटोमेशन योजनांच्या डिझाइन दरम्यान, आम्हाला गैर-इष्टतम इन्व्हेंटरी स्टोरेजच्या विद्यमान समस्येचा सामना करावा लागला. क्रेन संचयित करणे आणि घालणे हे वैशिष्ट्य असे आहे की एका युनिट स्टोरेज सेलमध्ये फक्त एका बॅचमधील वस्तू असू शकतात (चित्र 1 पहा). उत्पादने दररोज गोदामात येतात आणि प्रत्येक आगमन स्वतंत्र बॅच असते. एकूण, 1 महिन्याच्या वेअरहाऊस ऑपरेशनच्या परिणामी, प्रत्येक वेगळ्या सेलमध्ये संग्रहित केले जावे हे तथ्य असूनही, 30 स्वतंत्र बॅच तयार केल्या आहेत. उत्पादने बहुतेकदा संपूर्ण पॅलेटमध्ये नव्हे तर तुकड्यांमध्ये निवडली जातात आणि परिणामी, अनेक सेलमधील तुकडा निवड झोनमध्ये खालील चित्र दिसून येते: 1 m3 पेक्षा जास्त आकारमान असलेल्या सेलमध्ये क्रेनचे अनेक तुकडे असतात. सेल व्हॉल्यूमच्या 5-10% पेक्षा कमी व्यापतात.

अंजीर 1. सेलमधील अनेक तुकड्यांचा फोटो

साठवण क्षमतेचा योग्य वापर होत नसल्याचे स्पष्ट झाले आहे. आपत्तीच्या प्रमाणाची कल्पना करण्यासाठी, मी आकडे देऊ शकतो: वेअरहाऊसच्या ऑपरेशनच्या वेगवेगळ्या कालावधीत "वजा" शिल्लक असलेल्या 1 एम 3 पेक्षा जास्त व्हॉल्यूम असलेल्या अशा पेशींचे सरासरी 100 ते 300 पेशी असतात. वेअरहाऊस तुलनेने लहान असल्याने, वेअरहाऊसच्या व्यस्त हंगामात हा घटक "अडथळा" बनतो आणि स्वीकृती आणि शिपमेंटच्या गोदामातील प्रक्रिया मोठ्या प्रमाणात मंदावते.

समस्येचे निराकरण करण्याची कल्पना

एक कल्पना उद्भवली: सर्वात जवळच्या तारखांसह उरलेल्या बॅचचे तुकडे कमी केले जावेत आणि अशा युनिफाइड बॅचसह अशा उरलेल्या तुकड्या एका सेलमध्ये एकत्रितपणे एकत्रित केल्या पाहिजेत किंवा अनेक ठिकाणी, जर एखाद्यामध्ये पुरेशी जागा नसेल तर. उरलेली संपूर्ण रक्कम. अशा "कंप्रेशन" चे उदाहरण आकृती 2 मध्ये दर्शविले आहे.

अंजीर.2. पेशींमधील अवशेष संकुचित करण्यासाठी योजना

हे तुम्हाला व्यापलेल्या वेअरहाऊसची जागा लक्षणीयरीत्या कमी करण्यास अनुमती देते जी नवीन वस्तू ठेवण्यासाठी वापरली जाईल. गोदामाची क्षमता ओव्हरलोड असलेल्या परिस्थितीत, असे उपाय करणे अत्यंत आवश्यक आहे, अन्यथा नवीन माल सामावून घेण्यासाठी पुरेशी मोकळी जागा असू शकत नाही, ज्यामुळे गोदामातील प्लेसमेंट आणि पुन्हा भरण्याची प्रक्रिया थांबेल आणि परिणामी, स्वीकृती आणि शिपमेंट थांबवण्यासाठी. पूर्वी, डब्ल्यूएमएस सिस्टमच्या अंमलबजावणीपूर्वी, असे ऑपरेशन व्यक्तिचलितपणे केले जात होते, जे अप्रभावी होते, कारण पेशींमध्ये योग्य शिल्लक शोधण्याची प्रक्रिया खूप लांब होती. आता, डब्ल्यूएमएस प्रणाली सुरू केल्याने, आम्ही प्रक्रिया स्वयंचलित करण्याचा निर्णय घेतला, ती वेगवान बनविली आणि ती बुद्धिमान बनविली.

अशा समस्येचे निराकरण करण्याची प्रक्रिया 2 टप्प्यात विभागली गेली आहे:

• पहिल्या टप्प्यावर, आम्हांला कॉम्प्रेशनच्या तारखेत बॅचचे गट आढळतात (या कार्यासाठी समर्पित मागील लेख);
• दुसऱ्या टप्प्यावर, बॅचच्या प्रत्येक गटासाठी आम्ही सेलमधील उर्वरित वस्तूंच्या सर्वात कॉम्पॅक्ट प्लेसमेंटची गणना करतो.

सध्याच्या लेखात आपण अल्गोरिदमच्या दुसऱ्या टप्प्यावर लक्ष केंद्रित करू.

विद्यमान उपायांचे पुनरावलोकन

आम्ही विकसित केलेल्या अल्गोरिदमच्या वर्णनाकडे जाण्यापूर्वी, बाजारात आधीपासून अस्तित्वात असलेल्या सिस्टमचे संक्षिप्त विहंगावलोकन करणे योग्य आहे. WMS, जे समान इष्टतम कॉम्प्रेशन कार्यक्षमता लागू करते.

सर्व प्रथम, उत्पादन लक्षात घेणे आवश्यक आहे “1C: Enterprise 8. WMS Logistics. वेअरहाऊस मॅनेजमेंट 4", जे 1C च्या मालकीचे आणि प्रतिरूपित आहे आणि चौथ्या पिढीचे आहे WMS- AXELOT ने विकसित केलेली प्रणाली. ही प्रणाली कॉम्प्रेशन फंक्शनॅलिटीचा दावा करते, जी एका सामान्य सेलमध्ये असमान उत्पादनाचे अवशेष एकत्र करण्यासाठी डिझाइन केलेले आहे. हे लक्षात घेण्यासारखे आहे की अशा प्रणालीतील कॉम्प्रेशन कार्यक्षमतेमध्ये इतर शक्यता देखील समाविष्ट आहेत, उदाहरणार्थ, त्यांच्या एबीसी वर्गांनुसार सेलमध्ये वस्तूंचे स्थान दुरुस्त करणे, परंतु आम्ही त्यावर लक्ष ठेवणार नाही.

जर तुम्ही 1C च्या कोडचे विश्लेषण केले: Enterprise 8. WMS लॉजिस्टिक सिस्टम. वेअरहाऊस व्यवस्थापन 4" (जे कार्यक्षमतेच्या या भागात खुले आहे), आम्ही खालील निष्कर्ष काढू शकतो. अवशिष्ट कॉम्प्रेशन अल्गोरिदम एक ऐवजी आदिम रेखीय तर्क लागू करते आणि कोणत्याही "इष्टतम" कॉम्प्रेशनबद्दल कोणतीही चर्चा होऊ शकत नाही. स्वाभाविकच, ते पक्षांच्या क्लस्टरिंगची तरतूद करत नाही. अशी प्रणाली लागू केलेल्या अनेक ग्राहकांनी कॉम्प्रेशन प्लॅनिंगच्या परिणामांबद्दल तक्रार केली. उदाहरणार्थ, बहुतेकदा कॉम्प्रेशन दरम्यान सराव मध्ये खालील परिस्थिती उद्भवली: 100 पीसी. उर्वरित माल एका सेलमधून दुसऱ्या सेलमध्ये हलविण्याची योजना आहे, जिथे 1 तुकडा स्थित आहे. वस्तू, जरी वेळ वापरण्याच्या दृष्टिकोनातून उलट करणे इष्टतम आहे.

तसेच, सेलमधील उर्वरित वस्तू संकुचित करण्याची कार्यक्षमता अनेक परदेशी देशांमध्ये घोषित केली जाते. WMS-सिस्टम, परंतु, दुर्दैवाने, अल्गोरिदमच्या परिणामकारकतेबद्दल आमच्याकडे कोणताही वास्तविक अभिप्राय नाही (हे एक व्यापार रहस्य आहे), त्यांच्या तर्कशास्त्राच्या (मालकीचे बंद-स्रोत सॉफ्टवेअर) च्या खोलीबद्दल फारच कमी कल्पना आहे, म्हणून आम्ही न्याय करू शकत नाही.

समस्येचे गणितीय मॉडेल शोधा

समस्येचे निराकरण करण्यासाठी उच्च-गुणवत्तेचे अल्गोरिदम डिझाइन करण्यासाठी, प्रथम ही समस्या गणितीयदृष्ट्या स्पष्टपणे तयार करणे आवश्यक आहे, जे आपण करू.

अनेक पेशी आहेत , ज्यामध्ये काही वस्तूंचे अवशेष आहेत. पुढे काय, आपण अशा पेशींना दाता पेशी म्हणू. चला सूचित करूया सेलमधील वस्तूंचे प्रमाण $.

हे सांगणे महत्त्वाचे आहे की एका बॅचचे फक्त एक उत्पादन, किंवा अनेक बॅचेस पूर्वी क्लस्टरमध्ये एकत्र केले होते (वाचा: मागील लेख), जे वस्तूंच्या स्टोरेज आणि स्टोरेजच्या वैशिष्ट्यांमुळे आहे. भिन्न उत्पादने किंवा भिन्न बॅच क्लस्टर्सने त्यांची स्वतःची स्वतंत्र कॉम्प्रेशन प्रक्रिया चालविली पाहिजे.

अनेक पेशी आहेत , ज्यामध्ये दात्याच्या पेशींचे अवशेष संभाव्यपणे ठेवले जाऊ शकतात. अशा पेशींना आपण पुढे कंटेनर पेशी म्हणू. हे एकतर वेअरहाऊसमधील विनामूल्य पेशी किंवा विविध प्रकारचे दाता पेशी असू शकतात . नेहमी भरपूर उपसंच आहे .

प्रत्येक सेलसाठी अनेकांकडून क्षमतेवर बंधने घालण्यात आली आहेत , dm3 मध्ये मोजले. एक dm3 10 सेमी बाजू असलेला घन आहे. वेअरहाऊसमध्ये साठवलेली उत्पादने खूप मोठी आहेत, म्हणून या प्रकरणात असे विवेक पुरेसे आहे.

सर्वात कमी अंतराचे मॅट्रिक्स दिले पेशींच्या प्रत्येक जोडीमधील मीटरमध्ये कुठे и सेटशी संबंधित и अनुक्रमे

चला सूचित करूया सेलमधून वस्तू हलविण्याचा “खर्च” सेलला . चला सूचित करूया कंटेनर निवडण्यासाठी "खर्च". इतर पेशींमधील अवशेष त्यामध्ये हलविण्यासाठी. मापनाच्या कोणत्या युनिट्समध्ये नेमके कसे आणि कोणते मूल्य मोजले जातील и आम्ही पुढे विचार करू (इनपुट डेटा तयार करणारा विभाग पहा), आता असे म्हणणे पुरेसे आहे की अशी मूल्ये थेट मूल्यांच्या प्रमाणात असतील. и अनुक्रमे

द्वारे सूचित करूया एक व्हेरिएबल जे सेलमधून उर्वरित असल्यास मूल्य 1 घेते कंटेनरमध्ये हलविले , आणि 0 अन्यथा. द्वारे सूचित करूया व्हेरिएबल जे कंटेनर असल्यास 1 मूल्य घेते उर्वरित वस्तूंचा समावेश आहे आणि 0 अन्यथा.

कार्य खालीलप्रमाणे सांगितले आहे: तुम्हाला बरेच कंटेनर शोधण्याची आवश्यकता आहे आणि अशा प्रकारे फंक्शन कमी करण्यासाठी दाता पेशींना कंटेनर पेशींशी “संलग्न” करा

निर्बंध अंतर्गत

एकूणच, समस्येच्या निराकरणाची गणना करताना, आम्ही प्रयत्न करतो:

• प्रथम, साठवण क्षमता वाचवण्यासाठी;
• दुसरे म्हणजे, दुकानदारांचा वेळ वाचवण्यासाठी.

शेवटच्या निर्बंधाचा अर्थ असा आहे की आम्ही निवडलेल्या कंटेनरमध्ये आम्ही माल हलवू शकत नाही आणि म्हणून ते निवडण्यासाठी "खर्च" घेतला नाही. या निर्बंधाचा अर्थ असा आहे की सेल्समधून कंटेनरमध्ये हलविलेल्या वस्तूंचे प्रमाण कंटेनरच्या क्षमतेपेक्षा जास्त नसावे. समस्येचे निराकरण करून आम्ही कंटेनरचा संच समजतो आणि कंटेनरमध्ये दात्याच्या पेशी जोडण्याच्या पद्धती.

ऑप्टिमायझेशन समस्येचे हे सूत्र नवीन नाही आणि गेल्या शतकाच्या 80 च्या दशकाच्या सुरुवातीपासून अनेक गणितज्ञांनी त्याचा अभ्यास केला आहे. परदेशी साहित्यात योग्य गणितीय मॉडेलसह 2 ऑप्टिमायझेशन समस्या आहेत: सिंगल-सोर्स कॅपेसिटेटेड सुविधा स्थान समस्या и मल्टी-सोर्स कॅपेसिटेटेड सुविधा स्थान समस्या (आम्ही नंतर कार्यांमधील फरकांबद्दल बोलू). हे सांगण्यासारखे आहे की गणितीय साहित्यात, अशा दोन ऑप्टिमायझेशन समस्यांचे सूत्रीकरण जमिनीवर असलेल्या उद्योगांच्या स्थानाच्या संदर्भात तयार केले जाते, म्हणून त्यांना "सुविधा स्थान" असे नाव देण्यात आले आहे. बहुतेक भागांसाठी, ही परंपरेला श्रद्धांजली आहे, कारण पहिल्यांदाच अशा एकत्रित समस्या सोडवण्याची गरज लॉजिस्टिकच्या क्षेत्रातून आली, बहुतेक गेल्या शतकाच्या 50 च्या दशकात लष्करी-औद्योगिक क्षेत्रातून. एंटरप्राइझ स्थानाच्या दृष्टीने, अशी कार्ये खालीलप्रमाणे तयार केली जातात:

• अशी अनेक शहरे आहेत जिथे उत्पादन उद्योग शोधणे शक्य आहे (यापुढे मॅन्युफॅक्चरिंग शहरे म्हणून संदर्भित). प्रत्येक मॅन्युफॅक्चरिंग शहरासाठी, त्यात एंटरप्राइझ उघडण्याची किंमत निर्दिष्ट केली आहे, तसेच त्यामध्ये उघडलेल्या एंटरप्राइझच्या उत्पादन क्षमतेवर मर्यादा आहे.
• तेथे शहरांचा एक मर्यादित संच आहे जेथे ग्राहक प्रत्यक्षात स्थित आहेत (यापुढे ग्राहक शहरे म्हणून संदर्भित). अशा प्रत्येक ग्राहक शहरासाठी, उत्पादनांच्या मागणीचे प्रमाण निर्दिष्ट केले आहे. साधेपणासाठी, आम्ही असे गृहीत धरू की असे एकच उत्पादन आहे जे एंटरप्राइजेसद्वारे उत्पादित केले जाते आणि ग्राहक वापरतात.
• शहर-निर्माता आणि शहर-क्लायंटच्या प्रत्येक जोडीसाठी, निर्मात्याकडून क्लायंटला उत्पादनांची आवश्यक मात्रा वितरीत करण्यासाठी वाहतूक खर्चाचे मूल्य निर्दिष्ट केले आहे.

तुम्हाला कोणत्या शहरांमध्ये व्यवसाय उघडायचे आणि ग्राहकांना अशा व्यवसायांशी कसे जोडायचे ते शोधणे आवश्यक आहे:

• उपक्रम उघडण्याचे एकूण खर्च आणि वाहतूक खर्च कमीत कमी होते;
• कोणत्याही खुल्या एंटरप्राइझला नियुक्त केलेल्या ग्राहकांकडून मागणीचे प्रमाण त्या एंटरप्राइझच्या उत्पादन क्षमतेपेक्षा जास्त नव्हते.

आता या दोन शास्त्रीय समस्यांमधील फरक लक्षात घेण्यासारखे आहे:

• सिंगल-सोर्स कॅपॅसिटेटेड फॅसिलिटी लोकेशन प्रॉब्लेम - क्लायंटला फक्त एका ओपन फॅसिलिटीमधून पुरवठा केला जातो;
• मल्टी-सोर्स कॅपॅसिटेटेड फॅसिलिटी लोकेशन प्रॉब्लेम – क्लायंटला एकाच वेळी अनेक खुल्या सुविधांमधून पुरवठा केला जाऊ शकतो.

दोन समस्यांमधील असा फरक पहिल्या दृष्टीक्षेपात क्षुल्लक आहे, परंतु, खरं तर, अशा समस्यांच्या पूर्णपणे भिन्न संयोजन संरचना आणि परिणामी, त्यांचे निराकरण करण्यासाठी पूर्णपणे भिन्न अल्गोरिदम बनवते. कार्यांमधील फरक खालील आकृतीमध्ये दर्शविला आहे.

अंजीर.3. अ) बहु-स्रोत क्षमता असलेल्या सुविधा स्थान समस्या

अंजीर.3. b) सिंगल-सोर्स कॅपॅसिटेटेड सुविधा स्थान समस्या

दोन्ही कार्ये -कठीण, म्हणजे, इनपुट डेटाच्या आकारात बहुपदी वेळेत अशा समस्येचे निराकरण करणारे कोणतेही अचूक अल्गोरिदम नाही. सोप्या शब्दात, समस्येचे निराकरण करण्यासाठी सर्व अचूक अल्गोरिदम घातांकीय वेळेत कार्य करतील, जरी कदाचित पर्यायांच्या संपूर्ण शोधापेक्षा वेगवान असेल. कार्य पासून -कठीण, मग आम्ही फक्त अंदाजे ह्युरिस्टिक्सचा विचार करू, म्हणजे अल्गोरिदम जे सातत्याने इष्टतमच्या अगदी जवळ असलेल्या सोल्यूशन्सची गणना करतील आणि खूप लवकर कार्य करतील. आपल्याला अशा कार्यात स्वारस्य असल्यास, आपण येथे रशियन भाषेत एक चांगले विहंगावलोकन शोधू शकता.

जर आपण सेलमधील वस्तूंच्या इष्टतम कॉम्प्रेशनच्या आमच्या समस्येच्या शब्दावलीकडे वळलो, तर:

• ग्राहक शहरे दाता पेशी आहेत उर्वरित मालासह,
• उत्पादन शहरे - कंटेनर सेल , ज्यामध्ये इतर पेशींचे अवशेष ठेवायचे आहेत,
• वाहतूक खर्च - वेळ खर्च दाता सेलमधून मालाची मात्रा हलविण्यासाठी स्टोअरकीपर कंटेनर सेलमध्ये ;
• व्यवसाय उघडण्याचा खर्च - कंटेनर निवडण्याचा खर्च , कंटेनर सेलच्या व्हॉल्यूमच्या समान , मुक्त व्हॉल्यूम जतन करण्यासाठी विशिष्ट गुणांकाने गुणाकार केला (गुणांकाचे मूल्य नेहमी > 1 असते) (इनपुट डेटा तयार करणारा विभाग पहा).

समस्येच्या सुप्रसिद्ध शास्त्रीय सोल्यूशन्सशी साधर्म्य तयार केल्यावर, एका महत्त्वाच्या प्रश्नाचे उत्तर देणे आवश्यक आहे ज्यावर सोल्यूशन अल्गोरिदमच्या आर्किटेक्चरची निवड अवलंबून असते: दाता सेलमधून उर्वरित भाग हलविणे केवळ एकच शक्य आहे. आणि फक्त एक कंटेनर (एकल-स्रोत), किंवा उर्वरित अनेक कंटेनर सेलमध्ये (मल्टी-सोर्स) हलवणे शक्य आहे का?

हे लक्षात घेण्यासारखे आहे की व्यवहारात समस्येचे दोन्ही फॉर्म्युलेशन होतात. आम्ही खाली अशा प्रत्येक सेटिंगसाठी सर्व साधक आणि बाधक सादर करतो:

समस्या प्रकार	पर्यायाचे फायदे	पर्यायाचे तोटे
एकल-स्रोत	समस्येचा हा प्रकार वापरून वस्तूंच्या हालचालींची गणना केली जाते: स्टोअरकीपरच्या भागावर कमी नियंत्रण आवश्यक आहे (एका सेलमधून सर्व काही घेतले, दुसर्‍या कंटेनर सेलमध्ये सर्व काही ठेवा), जे जोखीम दूर करते: "सेलमध्ये ठेवा" ऑपरेशन्स करताना वस्तूंच्या प्रमाणाची पुनर्गणना करताना त्रुटी; TSD मध्ये पुनर्गणना केलेले प्रमाण प्रविष्ट करताना त्रुटी; “पुट इन सेल” ऑपरेशन्स करत असताना वस्तूंची संख्या पुन्हा मोजण्यासाठी आणि त्यांना TSD मध्ये टाकण्यासाठी वेळ लागत नाही.
बहु-स्रोत	"सिंगल-सोर्स" पर्याय वापरून गणना केलेल्या कॉम्प्रेशनच्या तुलनेत समस्येच्या या आवृत्तीचा वापर करून गणना केलेले कॉम्प्रेशन्स सामान्यतः 10-15% अधिक कॉम्पॅक्ट असतात. परंतु आम्ही हे देखील लक्षात घेतो की दात्याच्या पेशींमध्ये अवशेषांची संख्या जितकी कमी असेल तितका कॉम्पॅक्टनेसमधील फरक कमी असेल.	समस्येचा हा प्रकार वापरून वस्तूंच्या हालचालींची गणना केली जाते: स्टोअरकीपरच्या भागावर अधिक नियंत्रण आवश्यक आहे (प्रत्येक नियोजित कंटेनर सेलमध्ये हलविलेल्या मालाच्या प्रमाणाची पुनर्गणना करणे आवश्यक आहे), जे वस्तूंच्या प्रमाणाची पुनर्गणना करताना आणि TSD मध्ये डेटा प्रविष्ट करताना त्रुटींचा धोका दूर करते. सेलमध्ये ठेवा" ऑपरेशन्स “पुट इन सेल” ऑपरेशन्स करत असताना वस्तूंची संख्या पुन्हा मोजण्यासाठी वेळ लागतो "सेलमध्ये ठेवा" ऑपरेशन्स करताना "ओव्हरहेड" (थांबा, पॅलेटवर जा, कंटेनर सेलचा बारकोड स्कॅन करा) यासाठी वेळ लागतो. काहीवेळा अल्गोरिदम मोठ्या संख्येने कंटेनर सेलमध्ये जवळजवळ पूर्ण पॅलेटचे प्रमाण "विभाजित" करू शकते ज्यात आधीपासूनच योग्य उत्पादन आहे, जे ग्राहकाच्या दृष्टिकोनातून अस्वीकार्य होते.

तक्ता 1. एकल-स्रोत आणि बहु-स्रोत पर्यायांचे साधक आणि बाधक.

एकल-स्रोत पर्यायाचे अधिक फायदे असल्याने आणि दाता पेशींमधील अवशेषांची संख्या जितकी लहान असेल तितकी ही वस्तुस्थिती लक्षात घेऊन, समस्येच्या दोन्ही प्रकारांसाठी मोजल्या जाणार्‍या कॉम्प्रेशन कॉम्पॅक्टनेसच्या प्रमाणात कमी फरक असल्याने, आमची निवड यावर पडली. एकल-स्रोत पर्याय. स्रोत.

हे सांगण्यासारखे आहे की मल्टी-सोर्स पर्यायाचे समाधान देखील होते. याचे निराकरण करण्यासाठी मोठ्या संख्येने प्रभावी अल्गोरिदम आहेत, त्यापैकी बहुतेक वाहतूक समस्यांचे निराकरण करण्यासाठी खाली येतात. केवळ कार्यक्षम अल्गोरिदम नाहीत तर मोहक देखील आहेत, उदाहरणार्थ, येथे.

इनपुट डेटा तयार करत आहे

एखाद्या समस्येचे निराकरण करण्यासाठी अल्गोरिदमचे विश्लेषण करणे आणि विकसित करणे सुरू करण्यापूर्वी, आपण कोणता डेटा आणि कोणत्या स्वरूपात इनपुट म्हणून फीड करू हे ठरवणे आवश्यक आहे. देणगीदार पेशींमध्ये उरलेल्या वस्तूंचे प्रमाण आणि कंटेनर पेशींच्या क्षमतेमध्ये कोणतीही अडचण नाही, कारण हे क्षुल्लक आहे - असे प्रमाण एम 3 मध्ये मोजले जाईल, परंतु कंटेनर सेल वापरण्याच्या खर्चासह आणि फिरत्या खर्चाच्या मॅट्रिक्ससह, सर्वकाही नाही. खूप सोपे आहे!

प्रथम गणना पाहू वस्तू हलविण्याचा खर्च दाता सेल पासून कंटेनर सेल पर्यंत. सर्व प्रथम, मोजमापाच्या कोणत्या युनिट्समध्ये आपण हालचालींच्या खर्चाची गणना करू हे ठरविणे आवश्यक आहे. दोन सर्वात स्पष्ट पर्याय मीटर आणि सेकंद आहेत. "शुद्ध" मीटरमध्ये प्रवास खर्च मोजण्यात काही अर्थ नाही. हे उदाहरणासह दाखवू. सेल द्या पहिल्या स्तरावर स्थित, सेल 30 मीटरने काढले आणि दुसऱ्या स्तरावर स्थित:

• पासून हलवत आहे в येथून जाण्यापेक्षा अधिक महाग в , दुसऱ्या स्तरावरून खाली जाणे (मजल्यापासून 1,5-2 मीटर) दुसऱ्या स्तरावर जाण्यापेक्षा सोपे आहे, जरी अंतर समान असेल;
• 1 पीसी हलवा. सेलमधील वस्तू в 10 तुकडे हलवण्यापेक्षा हे सोपे होईल. समान उत्पादन, जरी अंतर समान असेल.

सेकंदात हलविण्याच्या खर्चाचा विचार करणे अधिक चांगले आहे, कारण हे आपल्याला स्तरांमधील फरक आणि माल हलवण्याच्या प्रमाणात फरक दोन्ही विचारात घेण्यास अनुमती देते. सेकंदात हालचालीची किंमत मोजण्यासाठी, आम्ही हालचाली ऑपरेशनचे प्राथमिक घटकांमध्ये विघटन केले पाहिजे आणि प्रत्येक प्राथमिक घटकाच्या अंमलबजावणीसाठी वेळ मोजला पाहिजे.

सेलमधून द्या हालचाल पीसी. कंटेनर मध्ये माल ... असू द्या - वेअरहाऊसमधील कामगाराच्या हालचालीचा सरासरी वेग, m/sec मध्ये मोजला जातो. द्या и - एक-वेळच्या ऑपरेशन्सची सरासरी गती, अनुक्रमे 4 dm3 (ऑपरेशन करताना एखाद्या गोदामात एका वेळी घेतलेल्या सरासरी व्हॉल्यूम) मालाच्या व्हॉल्यूमसाठी घेते आणि ठेवते. द्या и सेलची उंची ज्यामधून अनुक्रमे टेक आणि पुट ऑपरेशन केले जातात. उदाहरणार्थ, पहिल्या स्तराची (मजला) सरासरी उंची 1 मीटर आहे, द्वितीय श्रेणी 2 मीटर आहे इ. मग मूव्ह ऑपरेशन पूर्ण करण्यासाठी एकूण वेळ मोजण्याचे सूत्र आहे पुढे:

सारणी 2 संग्रहित वस्तूंचे तपशील लक्षात घेऊन, वेअरहाऊस कर्मचार्‍यांनी गोळा केलेल्या प्रत्येक प्राथमिक ऑपरेशनच्या अंमलबजावणीच्या वेळेची आकडेवारी दर्शविते.

ऑपरेशनचे नाव	पदनाम	मीन
गोदामाभोवती फिरणाऱ्या कामगाराचा सरासरी वेग		१७.३४ मी/से
ठेवण्यासाठी एका ऑपरेशनची सरासरी गती (4 dm3 उत्पादनाच्या व्हॉल्यूमसाठी)		2,4 सेकंद

तक्ता 2. वेअरहाऊस ऑपरेशन्स पूर्ण करण्यासाठी सरासरी वेळ

आम्ही हलविण्याच्या खर्चाची गणना करण्याच्या पद्धतीवर निर्णय घेतला आहे. आता आपल्याला गणना कशी करायची हे शोधण्याची आवश्यकता आहे कंटेनर सेल निवडण्याचा खर्च. येथे सर्व काही हलत्या खर्चापेक्षा खूपच क्लिष्ट आहे, कारण:

• सर्वप्रथम, खर्च थेट सेलच्या व्हॉल्यूमवर अवलंबून असावा - दाता पेशींमधून हस्तांतरित केलेल्या अवशेषांची समान मात्रा मोठ्या कंटेनरपेक्षा लहान व्हॉल्यूमच्या कंटेनरमध्ये ठेवली जाते, बशर्ते की अशी मात्रा दोन्ही कंटेनरमध्ये पूर्णपणे बसेल. अशाप्रकारे, कंटेनर निवडण्याचा एकूण खर्च कमी करून, सेलमध्ये वस्तू ठेवण्याचे पुढील ऑपरेशन्स करण्यासाठी आम्ही निवड क्षेत्रामध्ये "दुर्मिळ" विनामूल्य स्टोरेज क्षमता वाचवण्याचा प्रयत्न करतो. आकृती 4 मोठ्या आणि लहान कंटेनरमध्ये अवशेष हस्तांतरित करण्याचे पर्याय आणि त्यानंतरच्या वेअरहाऊस ऑपरेशन्समध्ये या हस्तांतरण पर्यायांचे परिणाम दर्शविते.
• दुसरे म्हणजे, मूळ समस्येचे निराकरण करताना आपल्याला एकूण खर्च कमी करणे आवश्यक आहे, आणि हे हलवण्याच्या खर्चाची आणि कंटेनर निवडण्याच्या खर्चाची बेरीज आहे, तर घनमीटरमधील सेलची मात्रा काही सेकंदांशी जोडली जाणे आवश्यक आहे, जे क्षुल्लक पासून दूर आहे.

तांदूळ. 4. उरलेले पदार्थ वेगवेगळ्या क्षमतेच्या कंटेनरमध्ये हलवण्याचे पर्याय.

आकृती 4 नंतरच्या वस्तू ठेवण्याच्या दुस-या टप्प्यावर कंटेनरमध्ये बसत नसलेल्या उरलेल्या वस्तूंचे प्रमाण लाल रंगात दाखवते.

कंटेनर निवडण्यासाठी लागणार्‍या क्यूबिक मीटरच्या खर्चास काही सेकंदांच्या खर्चाशी जोडण्यात मदत होईल, ज्यामुळे समस्येच्या गणना केलेल्या उपायांसाठी खालील आवश्यकता हलविल्या जातील:

• यामुळे उत्पादन असलेल्या कंटेनर डब्यांची एकूण संख्या कमी झाल्यास दाता बिनमधील शिल्लक कोणत्याही परिस्थितीत कंटेनर बिनमध्ये हलवणे आवश्यक आहे.
• कंटेनरचे प्रमाण आणि हालचाल करण्यात घालवलेला वेळ यांच्यात संतुलन राखणे आवश्यक आहे: उदाहरणार्थ, मागील सोल्यूशनच्या तुलनेत एखाद्या समस्येच्या नवीन निराकरणामध्ये, व्हॉल्यूममध्ये वाढ मोठी आहे, परंतु वेळेत होणारा तोटा कमी आहे. , नंतर नवीन पर्याय निवडणे आवश्यक आहे.

चला शेवटच्या गरजेपासून सुरुवात करूया. अस्पष्ट शब्द "शिल्लक" स्पष्ट करण्यासाठी आम्ही खालील गोष्टी शोधण्यासाठी गोदाम कर्मचार्‍यांचे सर्वेक्षण केले. व्हॉल्यूमचा एक कंटेनर सेल असू द्या , ज्याला दाता पेशींमधून उरलेल्या मालाची हालचाल नियुक्त केली जाते आणि अशा हालचालीचा एकूण वेळ समान असतो . समान दाता पेशींमधून समान प्रमाणात वस्तू इतर कंटेनरमध्ये ठेवण्यासाठी अनेक पर्यायी पर्याय असू द्या, जेथे प्रत्येक प्लेसमेंटचे स्वतःचे अंदाज आहेत कुठे < и कुठे >.

प्रश्न विचारला जातो: व्हॉल्यूममध्ये किमान नफा काय आहे स्वीकार्य, दिलेल्या वेळेच्या नुकसान मूल्यासाठी ? उदाहरणासह स्पष्ट करू. सुरुवातीला, अवशेष 1000 dm3 (1 m3) च्या व्हॉल्यूम असलेल्या कंटेनरमध्ये ठेवायचे होते आणि हस्तांतरणाची वेळ 70 सेकंद होती. अवशेष दुसऱ्या कंटेनरमध्ये 500 dm3 आणि 130 सेकंदांच्या वेळेसह ठेवण्याचा पर्याय आहे. प्रश्न: 60 dm500 विनामूल्य व्हॉल्यूम वाचवण्यासाठी आम्ही स्टोअरकीपरच्या अतिरिक्त 3 सेकंदांचा वेळ वस्तू हलवण्यासाठी खर्च करण्यास तयार आहोत का? गोदाम कर्मचार्‍यांच्या सर्वेक्षणाच्या परिणामांवर आधारित, खालील आकृती संकलित केली गेली.

तांदूळ. 5. ऑपरेशनच्या वेळेतील फरकाच्या वाढीवर किमान स्वीकार्य व्हॉल्यूम बचतीच्या अवलंबनाचे आकृती

म्हणजेच, जर अतिरिक्त वेळ खर्च 40 सेकंद असेल, तर आम्ही ते फक्त तेव्हाच खर्च करण्यास तयार आहोत जेव्हा व्हॉल्यूममधील वाढ किमान 500 dm3 असेल. अवलंबित्वामध्ये थोडीशी अरेखीयता असली तरीही, पुढील गणनांच्या साधेपणासाठी आम्ही असे गृहीत धरू की परिमाणांमधील अवलंबित्व रेषीय आहे आणि असमानतेद्वारे वर्णन केले आहे.

खालील चित्रात, आम्ही कंटेनरमध्ये माल ठेवण्याच्या खालील पद्धतींचा विचार करतो.

तांदूळ. 6. पर्याय (a): 2 कंटेनर, एकूण खंड 400 dm3, एकूण वेळ 150 से.

तांदूळ. 6. पर्याय (b): 2 कंटेनर, एकूण खंड 600 dm3, एकूण वेळ 190 सेकंद.

तांदूळ. 6. पर्याय (c): 1 कंटेनर, एकूण खंड 400 dm3, एकूण वेळ 200 सेकंद.

कंटेनर निवडण्यासाठी पर्याय (a) मूळ पर्यायापेक्षा अधिक श्रेयस्कर आहे, कारण असमानता धारण करते: (800-400)/10>=150-120, ज्याचा अर्थ 40 >= 30 आहे. पर्याय (b) मूळपेक्षा कमी श्रेयस्कर आहे पर्याय , कारण असमानता धारण करत नाही: (800-600)/10>=190-150 म्हणजे 20 >= 40. पण पर्याय (c) अशा तर्कात बसत नाही! चला या पर्यायाचा अधिक तपशीलवार विचार करूया. एकीकडे, असमानता (800-400)/10>=200-120, ज्याचा अर्थ असमानता 40 >= 80 समाधानी नाही, जे सूचित करते की व्हॉल्यूममधील वाढ वेळेत एवढ्या मोठ्या नुकसानास योग्य नाही.

परंतु दुसरीकडे, या पर्यायामध्ये (c) आम्ही केवळ एकूण व्यापलेले खंड कमी करत नाही, तर व्यापलेल्या पेशींची संख्या देखील कमी करतो, जी वर सूचीबद्ध केलेल्या समस्यांच्या गणनायोग्य निराकरणासाठी दोन महत्त्वाच्या आवश्यकतांपैकी पहिली आहे. अर्थात, ही आवश्यकता पूर्ण होण्यासाठी, असमानतेच्या डाव्या बाजूला काही सकारात्मक स्थिरांक जोडणे आवश्यक आहे. , आणि कंटेनरची संख्या कमी झाल्यावरच अशी स्थिरता जोडणे आवश्यक आहे. त्याची आठवण करून द्या कंटेनर असताना 1 च्या बरोबरीचे व्हेरिएबल आहे निवडलेले, आणि कंटेनर असताना 0 निवडले नाही. आपण सूचित करू - प्रारंभिक सोल्युशनमध्ये अनेक कंटेनर आणि - नवीन सोल्यूशनमध्ये बरेच कंटेनर. सर्वसाधारणपणे, नवीन असमानता यासारखी दिसेल:

वरील असमानतेचे रूपांतर, आम्हाला मिळते

यावर आधारित, आमच्याकडे एकूण खर्चाची गणना करण्यासाठी एक सूत्र आहे समस्येवर काही उपाय:

पण आता प्रश्न निर्माण झाला आहे: अशा स्थिरांकाचे मूल्य काय असावे? ? अर्थात, त्याचे मूल्य पुरेसे मोठे असणे आवश्यक आहे जेणेकरून समस्येचे निराकरण करण्यासाठी प्रथम आवश्यकता नेहमी पूर्ण होईल. तुम्ही अर्थातच स्थिरांकाचे मूल्य 103 किंवा 106 च्या बरोबरीने घेऊ शकता, परंतु मला अशा "जादूची संख्या" टाळायची आहे. जर आपण वेअरहाऊस ऑपरेशन्स करण्याच्या वैशिष्ट्यांचा विचार केला तर, अशा स्थिरांकाच्या मूल्याचे अनेक सुस्थापित संख्यात्मक अंदाज आम्ही काढू शकतो.

असू द्या - एका झोन ABC च्या वेअरहाऊस सेलमधील कमाल अंतर, आमच्या बाबतीत 100 मी. - वेअरहाऊसमधील कंटेनर सेलची कमाल मात्रा, आमच्या बाबतीत 1000 dm3 च्या बरोबरीची.

मूल्य मोजण्याचा पहिला मार्ग . चला अशा परिस्थितीचा विचार करूया जेथे पहिल्या स्तरावर 2 कंटेनर आहेत, ज्यामध्ये वस्तू आधीपासूनच भौतिकरित्या स्थित आहेत, म्हणजेच ते स्वतःच दाता पेशी आहेत आणि त्याच पेशींमध्ये माल हलवण्याची किंमत नैसर्गिकरित्या 0 च्या बरोबरीची आहे. स्थिरांकासाठी असे मूल्य शोधणे आवश्यक आहे , ज्यामध्ये कंटेनर 1 मधून कंटेनर 2 मध्ये उरलेले नेहमी हलवणे फायदेशीर ठरेल. मूल्ये बदलणे и वर दिलेल्या असमानतेमध्ये आम्हाला मिळते:

ज्यावरून ते अनुसरण करते

वरील सूत्रामध्ये प्राथमिक ऑपरेशन्स करण्यासाठी सरासरी वेळेची मूल्ये बदलणे आम्हाला मिळते

मूल्य मोजण्याचा दुसरा मार्ग . तेथे आहे अशा परिस्थितीचा विचार करूया दाता पेशी ज्यामधून माल कंटेनरमध्ये हलविण्याची योजना आहे 1. आपण दर्शवूया - दात्याच्या पेशीपासून अंतर कंटेनर 1. येथे कंटेनर 2 देखील आहे, ज्यामध्ये आधीपासूनच माल आहे आणि ज्याची मात्रा तुम्हाला उर्वरित सर्व सामावून घेण्यास अनुमती देते पेशी साधेपणासाठी, आम्ही असे गृहीत धरू की दाता पेशींमधून कंटेनरमध्ये हलविलेल्या वस्तूंचे प्रमाण समान आणि समान आहे. . स्थिरांकाचे असे मूल्य शोधणे आवश्यक आहे , ज्यामध्ये सर्व उरलेल्या स्थानांची नियुक्ती कंटेनर 2 मधील पेशी वेगवेगळ्या कंटेनरमध्ये ठेवण्यापेक्षा नेहमीच अधिक फायदेशीर असतात:

आपल्याला मिळालेल्या असमानतेचे रूपांतर

प्रमाणाचे मूल्य "मजबूत" करण्यासाठी , असे गृहीत धरूया = 0. वेअरहाऊस बॅलन्स संकुचित करण्याच्या प्रक्रियेत सामील असलेल्या सेलची सरासरी संख्या 10 आहे. परिमाणांची ज्ञात मूल्ये बदलून, आमच्याकडे स्थिरांकाचे खालील मूल्य आहे

आम्ही प्रत्येक पर्यायासाठी गणना केलेले सर्वात मोठे मूल्य घेतो, हे प्रमाणाचे मूल्य असेल दिलेल्या वेअरहाऊस पॅरामीटर्ससाठी. आता, पूर्णतेसाठी, एकूण खर्च मोजण्याचे सूत्र लिहू काही व्यवहार्य उपायासाठी :

आता, सर्व केल्यानंतर कठोर प्रयत्न इनपुट डेटाचे रूपांतर करून, आम्ही असे म्हणू शकतो की सर्व इनपुट डेटा इच्छित फॉर्ममध्ये रूपांतरित केला गेला आहे आणि ऑप्टिमायझेशन अल्गोरिदममध्ये वापरण्यासाठी तयार आहे.

निष्कर्ष

सराव दर्शविल्याप्रमाणे, अल्गोरिदमसाठी इनपुट डेटा तयार करण्याच्या आणि बदलण्याच्या टप्प्याची जटिलता आणि महत्त्व अनेकदा कमी लेखले जाते. या लेखात, केवळ उच्च-गुणवत्तेचा आणि हुशारीने तयार केलेला इनपुट डेटाच अल्गोरिदमद्वारे मोजले जाणारे निर्णय क्लायंटसाठी खरोखरच मौल्यवान बनवू शकतो हे दर्शविण्यासाठी आम्ही या टप्प्यावर विशेष लक्ष दिले आहे. होय, सूत्रांची अनेक व्युत्पत्ती होती, परंतु आम्ही तुम्हाला काटापूर्वीच चेतावणी दिली होती :)

पुढील लेखात आपण शेवटी या 2 मागील प्रकाशने कशासाठी उद्देशित होत्या - एक स्वतंत्र ऑप्टिमायझेशन अल्गोरिदम.

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

स्त्रोत: www.habr.com