WMS का लागि अलग गणित: कक्षहरूमा वस्तुहरू कम्प्रेस गर्ने एल्गोरिदम (भाग 1)

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

यदि तपाइँ व्यवसायमा गणितको अनुप्रयोगहरूमा रुचि राख्नुहुन्छ र तपाइँ 5 औं कक्षाको स्तरमा सूत्रहरूको कठोर पहिचान रूपान्तरणबाट डराउनुहुन्न भने, बिरालोमा स्वागत छ!

लेख लागू गर्नेहरूलाई उपयोगी हुनेछ WMS-प्रणालीहरू, गोदाम वा उत्पादन रसद उद्योगमा काम गर्दछ, साथै प्रोग्रामरहरू जो व्यवसायमा गणितको अनुप्रयोग र उद्यममा प्रक्रियाहरूको अनुकूलनमा रुचि राख्छन्।

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

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

В अघिल्लो लेख हामीले लागू गरेको गोदामको विवरणहरू वर्णन गर्दछ WMS-प्रणाली, र यो पनि बताउँछ कि हामीले कार्यान्वयनको क्रममा बाँकी सामानहरूको क्लस्टरिङ ब्याचको समस्या समाधान गर्न किन आवश्यक थियो। WMS- प्रणालीहरू, र हामीले यो कसरी गर्यौं।

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

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

लेख कसरी पढ्ने। यदि तपाइँ अघिल्लो लेख पढ्नुभयो भने, तपाइँ तुरुन्तै "विद्यमान समाधानहरूको अवलोकन" अध्यायमा जान सक्नुहुन्छ, यदि होइन भने, तलको बिगार्न समस्याको वर्णन छ।

ग्राहकको गोदाममा समाधान भइरहेको समस्याको विवरण

प्रक्रियाहरूमा अवरोध

2018 मा, हामीले कार्यान्वयन गर्न एउटा परियोजना पूरा गर्‍यौं WMS- चेल्याबिन्स्कको गोदाम "ट्रेडिंग हाउस "एलडी" मा प्रणालीहरू। हामीले उत्पादन "1C-लजिस्टिक: वेयरहाउस म्यानेजमेन्ट 3" २० कार्यस्थलहरूका लागि लागू गर्यौं: अपरेटरहरू WMS, स्टोरकीपरहरू, फोर्कलिफ्ट चालकहरू। औसत गोदाम लगभग 4 हजार m2 छ, कोषहरूको संख्या 5000 छ र SKU को संख्या 4500 छ। गोदामले 1 kg देखि 400 kg सम्म विभिन्न आकारको हाम्रो आफ्नै उत्पादनको बल भल्भहरू भण्डार गर्दछ। FIFO अनुसार सामानहरू चयन गर्न आवश्यक भएकोले गोदाममा सूची ब्याचहरूमा भण्डार गरिएको छ।

गोदाम प्रक्रिया स्वचालन योजनाहरूको डिजाइनको क्रममा, हामीले गैर-इष्टतम सूची भण्डारणको अवस्थित समस्याको सामना गर्यौं। भण्डारण र बिछ्याउने क्रेनको विशेषताहरू यस्तो छन् कि एक एकाइ भण्डारण कक्षमा केवल एक ब्याचबाट वस्तुहरू समावेश गर्न सकिन्छ (चित्र 1 हेर्नुहोस्)। उत्पादनहरू दैनिक गोदाममा आइपुग्छन् र प्रत्येक आगमन छुट्टै ब्याच हो। कुलमा, गोदाम सञ्चालनको 1 महिनाको परिणामको रूपमा, 30 अलग ब्याचहरू सिर्जना गरिएका छन्, तथ्यको बावजुद प्रत्येकलाई छुट्टै कक्षमा भण्डारण गर्नुपर्छ। उत्पादनहरू प्रायः सम्पूर्ण प्यालेटहरूमा होइन, तर टुक्राहरूमा चयन गरिन्छ, र परिणाम स्वरूप, धेरै कक्षहरूमा टुक्रा चयन क्षेत्रमा निम्न चित्र अवलोकन गरिन्छ: 1 m3 भन्दा बढी भोल्युम भएको कक्षमा त्यहाँ क्रेनका धेरै टुक्राहरू छन्। सेल भोल्युम को 5-10% भन्दा कम कब्जा।

चित्र 1. सेलमा धेरै टुक्राहरूको फोटो

भण्डारण क्षमताको सदुपयोग हुन नसकेको स्पष्ट छ । प्रकोपको स्केलको कल्पना गर्न, म तथ्याङ्कहरू दिन सक्छु: औसतमा, गोदाम सञ्चालनको विभिन्न अवधिहरूमा "माइनस्युल" ब्यालेन्सको साथ 1 m3 भन्दा बढी भोल्युमको साथ त्यस्ता कक्षहरूको 100 देखि 300 कक्षहरू छन्। गोदाम तुलनात्मक रूपमा सानो भएकोले, गोदाम व्यस्त मौसमहरूमा यो कारक "अड्चन" बन्छ र स्वीकृति र ढुवानीको गोदाम प्रक्रियाहरूलाई धेरै ढिलो बनाउँछ।

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

एउटा विचार आयो: सबैभन्दा नजिकको मितिहरू भएका बाँकीहरूका ब्याचहरूलाई एक एकल ब्याचमा घटाउनुपर्छ, र एकीकृत ब्याचको साथ त्यस्ता बाँकीहरूलाई एकै कक्षमा कम्प्याक्ट रूपमा एकै ठाउँमा राख्नु पर्छ, वा धेरै ठाउँहरूमा, यदि त्यहाँ पर्याप्त ठाउँ छैन भने। बाँकीको सम्पूर्ण रकम। यस्तो "संकुचन" को एक उदाहरण चित्र 2 मा देखाइएको छ।

चित्र २। कक्षहरूमा अवशेषहरू कम्प्रेस गर्ने योजना

यसले तपाईंलाई ओगटेको गोदाम ठाउँलाई उल्लेखनीय रूपमा कम गर्न अनुमति दिन्छ जुन नयाँ सामानहरू राख्नको लागि प्रयोग गरिनेछ। गोदाम क्षमता ओभरलोड भएको स्थितिमा, यस्तो उपाय अत्यन्त आवश्यक छ, अन्यथा नयाँ सामानहरू समायोजन गर्न पर्याप्त खाली ठाउँ नहुन सक्छ, जसले गोदाम प्रक्रियाहरू प्लेसमेन्ट र पुनःपूर्तिमा रोकिनेछ र नतिजाको रूपमा, स्वीकृति र ढुवानीमा रोक। पहिले, WMS प्रणालीको कार्यान्वयन अघि, यस्तो अपरेशन म्यानुअल रूपमा प्रदर्शन गरिएको थियो, जुन प्रभावकारी थिएन, किनकि कक्षहरूमा उपयुक्त सन्तुलन खोज्ने प्रक्रिया धेरै लामो थियो। अब, WMS प्रणालीको परिचयसँगै, हामीले प्रक्रियालाई स्वचालित बनाउने, यसलाई गति दिने र बुद्धिमानी बनाउने निर्णय गरेका छौं।

यस्तो समस्या समाधान गर्ने प्रक्रिया 2 चरणहरूमा विभाजित छ:

• पहिलो चरणमा हामीले कम्प्रेसनको लागि मितिमा ब्याचहरूको समूहहरू फेला पार्छौं (यस कार्यमा समर्पित अघिल्लो लेख);
• दोस्रो चरणमा, ब्याचहरूको प्रत्येक समूहको लागि हामी कक्षहरूमा बाँकी सामानहरूको सबैभन्दा कम्प्याक्ट प्लेसमेन्ट गणना गर्छौं।

हालको लेखमा हामी एल्गोरिथ्मको दोस्रो चरणमा ध्यान केन्द्रित गर्नेछौं।

अवस्थित समाधानहरूको समीक्षा

हामीले विकास गरेका एल्गोरिदमहरूको विवरणमा जानु अघि, यो बजारमा पहिले नै अवस्थित प्रणालीहरूको संक्षिप्त सिंहावलोकन सञ्चालन गर्न लायक छ। WMS, जसले समान इष्टतम कम्प्रेसन कार्यक्षमता लागू गर्दछ।

सबै भन्दा पहिले, यो उत्पादन नोट गर्न आवश्यक छ "1C: उद्यम 8. WMS रसद। गोदाम व्यवस्थापन 4", जुन 1C द्वारा स्वामित्व र प्रतिलिपि गरिएको छ र चौथो पुस्ताको हो। WMS- AXELOT द्वारा विकसित प्रणाली। यो प्रणालीले कम्प्रेसन कार्यक्षमता दावी गर्दछ, जुन भिन्न उत्पादनलाई एक साझा कक्षमा एकजुट गर्न डिजाइन गरिएको हो। यो उल्लेख गर्न लायक छ कि यस्तो प्रणालीमा कम्प्रेसन कार्यक्षमताले अन्य सम्भावनाहरू पनि समावेश गर्दछ, उदाहरणका लागि, तिनीहरूको एबीसी वर्गहरू अनुसार कक्षहरूमा सामानहरूको प्लेसमेन्ट सच्याउन, तर हामी तिनीहरूमा बस्ने छैनौं।

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

साथै, सेलहरूमा बाँकी सामानहरू कम्प्रेस गर्ने कार्यक्षमता धेरै विदेशी देशहरूमा घोषित गरिएको छ। WMS-प्रणालीहरू, तर, दुर्भाग्यवश, हामीसँग एल्गोरिदमहरूको प्रभावकारितामा कुनै वास्तविक प्रतिक्रिया छैन (यो एक व्यापार गोप्य हो), तिनीहरूको तर्क (स्वामित्व बन्द-स्रोत सफ्टवेयर) को गहिराइको बारेमा धेरै कम विचार, त्यसैले हामी न्याय गर्न सक्दैनौं।

समस्याको गणितीय मोडेल खोज्नुहोस्

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

त्यहाँ धेरै कोशिकाहरू छन् , जसमा केहि सामानहरु को अवशेष समावेश छ। निम्नमा, हामी त्यस्ता कोशिकाहरूलाई डोनर सेलहरू भन्नेछौं। बुझौं सेल मा सामान को मात्रा $.

यो भन्नु महत्त्वपूर्ण छ कि एउटा ब्याचको केवल एउटा उत्पादन, वा धेरै ब्याचहरू पहिले क्लस्टरमा जोडिएको थियो (पढ्नुहोस्: अघिल्लो लेख), जुन सामानको भण्डारण र भण्डारणको विशिष्टताको कारण हो। बिभिन्न उत्पादनहरू वा विभिन्न ब्याच क्लस्टरहरूले आफ्नै छुट्टै कम्प्रेसन प्रक्रिया चलाउनु पर्छ।

त्यहाँ धेरै कोशिकाहरू छन् , जसमा दाता कोषका अवशेषहरू सम्भावित रूपमा राख्न सकिन्छ। हामी त्यस्ता सेलहरूलाई कन्टेनर सेलहरू कल गर्नेछौं। यी या त गोदाममा मुक्त कक्षहरू वा विभिन्न प्रकारका दाता कक्षहरू हुन सक्छन् । सधैं प्रशस्त एक उपसमूह छ .

प्रत्येक सेल को लागी धेरैबाट क्षमता प्रतिबन्धहरू सेट गरिएको छ , dm3 मा मापन। एक dm3 10 सेन्टिमिटर को पक्षहरु संग एक घन हो, गोदाम मा भण्डारण उत्पादनहरु धेरै ठूला छन्, त्यसैले यस्तो discretization पर्याप्त छ।

सबैभन्दा छोटो दूरीको म्याट्रिक्स दिइएको छ कोषहरूको प्रत्येक जोडी बीचको मिटरमा कहाँ и सेटहरूसँग सम्बन्धित छ и क्रमशः।

बुझौं सेलबाट सामान सार्ने "लागत" सेल गर्न । बुझौं कन्टेनर छनोटको "लागत" यसमा अन्य कक्षहरूबाट अवशेषहरू सार्न। कसरी र मापन को एकाइहरु मा मान गणना गरिनेछ и हामी थप विचार गर्नेछौं (इनपुट डेटा तयार गर्ने खण्ड हेर्नुहोस्), अहिलेको लागि यो भन्न पर्याप्त छ कि त्यस्ता मानहरू मानहरूसँग प्रत्यक्ष समानुपातिक हुनेछन्। и क्रमशः।

द्वारा बुझाउनुहोस् यदि सेलबाट बाँकी छ भने मान १ लिने चल कन्टेनरमा सारियो , र ० अन्यथा। द्वारा बुझाउनुहोस् एउटा चर जसले मान १ लिन्छ यदि कन्टेनर बाँकी सामानहरू समावेश गर्दछ, र ० अन्यथा।

कार्य निम्नानुसार उल्लेख गरिएको छ: तपाईंले धेरै कन्टेनरहरू फेला पार्न आवश्यक छ र यसरी कार्यलाई न्यूनीकरण गर्न कन्टेनर कक्षहरूमा डोनर सेलहरूलाई "संलग्न" गर्नुहोस्

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

कुलमा, समस्याको समाधान गणना गर्दा, हामी प्रयास गर्छौं:

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

अन्तिम प्रतिबन्धको अर्थ हामीले छनौट नगरेको कन्टेनरमा सामान सार्न सक्दैनौं, र त्यसकारण यसलाई छनोट गर्नको लागि "लागत" लागेन। यो प्रतिबन्धको मतलब यो पनि हो कि कक्षहरूबाट कन्टेनरमा सारिएको सामानको मात्रा कन्टेनरको क्षमता भन्दा बढी हुनु हुँदैन। समस्या समाधान गरेर हामीले कन्टेनरहरूको सेटलाई बुझाउँछौं र कन्टेनरहरूमा डोनर सेलहरू संलग्न गर्ने तरिकाहरू।

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

• त्यहाँ सीमित संख्यामा शहरहरू छन् जहाँ सम्भावित रूपमा निर्माण उद्यमहरू पत्ता लगाउन सम्भव छ (यसपछि निर्माण शहरहरू भनिन्छ)। प्रत्येक निर्माण सहरको लागि, यसमा उद्यम खोल्ने लागतहरू निर्दिष्ट गरिएको छ, साथै यसमा खोलिएको उद्यमको उत्पादन क्षमतामा सीमितता।
• त्यहाँ सहरहरूको एक सीमित सेट छ जहाँ ग्राहकहरू वास्तवमा अवस्थित छन् (यसपछि ग्राहक शहरहरू भनिन्छ)। प्रत्येक यस्तो ग्राहक शहर को लागी, उत्पादनहरु को लागी मांग को मात्रा निर्दिष्ट गरिएको छ। सादगीको लागि, हामी मान्नेछौं कि त्यहाँ एउटा मात्र उत्पादन हो जुन उद्यमहरू द्वारा उत्पादन गरिन्छ र ग्राहकहरूले उपभोग गर्दछ।
• शहर-निर्माता र शहर-ग्राहकको प्रत्येक जोडीको लागि, निर्माताबाट ग्राहकलाई उत्पादनहरूको आवश्यक मात्रा प्रदान गर्नको लागि यातायात लागतको मूल्य निर्दिष्ट गरिएको छ।

तपाईंले कुन शहरहरूमा व्यवसायहरू खोल्ने र ग्राहकहरूलाई त्यस्ता व्यवसायहरूमा कसरी संलग्न गर्ने भनेर पत्ता लगाउन आवश्यक छ:

• खोल्ने उद्यमहरूको कुल लागत र यातायात लागत न्यूनतम थियो;
• कुनै पनि खुला उद्यमलाई तोकिएको ग्राहकहरूबाट मागको मात्रा त्यो उद्यमको उत्पादन क्षमता भन्दा बढी थिएन।

अब यी दुई शास्त्रीय समस्याहरूमा मात्र फरक उल्लेख गर्न लायक छ:

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

दुई समस्याहरू बीचको यस्तो भिन्नता पहिलो नजरमा नगण्य छ, तर, वास्तवमा, त्यस्ता समस्याहरूको पूर्णतया फरक संयोजन संरचनामा जान्छ र परिणामको रूपमा, तिनीहरूलाई समाधान गर्न पूर्ण रूपमा फरक एल्गोरिदमहरू। कार्यहरू बीचको भिन्नतालाई तलको चित्रमा देखाइएको छ।

चित्र ३. क) बहु-स्रोत क्षमतायुक्त सुविधा स्थान समस्या

चित्र ३. ख) एकल-स्रोत क्षमतायुक्त सुविधा स्थान समस्या

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

यदि हामी कक्षहरूमा सामानहरूको इष्टतम सङ्कुचनको हाम्रो समस्याको शब्दावलीमा परिवर्तन गर्छौं, तब:

• ग्राहक शहरहरू डोनर सेलहरू हुन् बाँकी सामान संग,
• निर्माण शहरहरू - कन्टेनर सेलहरू , जसमा अन्य कक्षहरूबाट बाँकी राखिएको मानिन्छ,
• यातायात लागत - समय लागत दाता सेलबाट सामानको मात्रा सार्न स्टोरकीपर कन्टेनर सेलमा ;
• व्यवसाय खोल्ने लागत - कन्टेनर छनौट गर्ने लागत , कन्टेनर सेल को भोल्युम बराबर , नि:शुल्क भोल्युमहरू बचत गर्नको लागि निश्चित गुणांकद्वारा गुणा गरियो (गुणकको मान सधैं > 1 हो) (इनपुट डेटा तयार गर्ने खण्ड हेर्नुहोस्)।

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

यो ध्यान दिन लायक छ कि व्यवहार मा समस्या को दुवै सूत्रहरु स्थान लिन्छ। हामी तल त्यस्ता प्रत्येक सेटिङका ​​लागि सबै फाइदा र विपक्षहरू प्रस्तुत गर्दछौं:

तालिका 1. एकल-स्रोत र बहु-स्रोत विकल्पहरूको फाइदा र विपक्ष।

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

यो भन्न लायक छ कि बहु-स्रोत विकल्प को समाधान पनि ठाउँ लिन्छ। यसलाई समाधान गर्नको लागि त्यहाँ धेरै संख्यामा प्रभावकारी एल्गोरिदमहरू छन्, जसमध्ये धेरै जसो यातायात समस्याहरू समाधान गर्न आउँछन्। त्यहाँ कुशल एल्गोरिदमहरू मात्र छैनन्, तर सुरुचिपूर्ण पनि छन्, उदाहरणका लागि, यहाँ।

इनपुट डेटा तयार गर्दै

विश्लेषण गर्न र समस्या समाधान गर्न एल्गोरिथ्म विकास गर्न सुरु गर्नु अघि, कुन डाटा र कुन फारममा हामीले यसलाई इनपुटको रूपमा फिड गर्ने भनेर निर्णय गर्न आवश्यक छ। डोनर सेलहरूमा बाँकी सामानहरूको मात्रा र कन्टेनर सेलहरूको क्षमतामा कुनै समस्या छैन, किनकि यो मामूली छ - त्यस्ता मात्राहरू m3 मा मापन गरिनेछ, तर कन्टेनर सेल र चलिरहेको लागत म्याट्रिक्स प्रयोग गर्ने लागतहरू, सबै कुरा होइन। धेरै सरल छ!

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

• बाट सर्दै в बाट सार्नु भन्दा महँगो в , दोस्रो तहबाट तल जान (तलबाट 1,5-2 मिटर) दोस्रोमा जानु भन्दा सजिलो छ, यद्यपि दूरी समान हुनेछ;
• 1 पीसी सार्नुहोस्। सेलबाट सामानहरू в यो 10 टुक्रा सार्न भन्दा सजिलो हुनेछ। समान उत्पादन, यद्यपि दूरी समान हुनेछ।

सेकेन्डमा सार्न लागतहरू विचार गर्नु राम्रो हुन्छ, किनकि यसले तपाईंलाई स्तरहरूमा भिन्नता र सामानको मात्रामा भिन्नता दुवैलाई ध्यानमा राख्न अनुमति दिन्छ। सेकेन्डमा आन्दोलनको लागतको लागि खातामा, हामीले आन्दोलन सञ्चालनलाई प्राथमिक घटकहरूमा विघटन गर्नुपर्छ र प्रत्येक प्राथमिक घटकको कार्यान्वयनको लागि समय मापन लिनुपर्छ।

सेलबाट दिनुहोस् चाल पीसी। कन्टेनरमा सामान । दिनुहोस् - गोदाममा कामदारको आन्दोलनको औसत गति, m/sec मा मापन। दिनुहोस् и - 4 dm3 बराबरको सामानको भोल्युमको लागि क्रमशः एक-पटक सञ्चालनको औसत गति लिन्छ र राख्छ (एक कर्मचारीले गोदाममा सञ्चालन गर्दा एक समयमा लिने औसत भोल्युम)। दिनुहोस् и सेलहरूको उचाइ जसबाट टेक र पुट अपरेशनहरू क्रमशः गरिन्छ। उदाहरणका लागि, पहिलो टियर (फ्लोर) को औसत उचाइ 1 मिटर हो, दोस्रो टियर 2 मिटर हो, आदि। त्यसपछि चाल सञ्चालन पूरा गर्न कुल समय गणनाको लागि सूत्र हो अर्को:

तालिका २ ले गोदामका कर्मचारीहरूद्वारा सङ्कलन गरेको प्रत्येक प्रारम्भिक सञ्चालनको कार्यान्वयन समयको तथ्याङ्कहरू देखाउँछ, भण्डार गरिएका सामानहरूको विवरणहरूलाई ध्यानमा राखेर।

सञ्चालनको नाम	पदनाम	अर्थ
गोदाम वरिपरि घुम्ने कामदारको औसत गति		१२ मि/सेकेन्ड
राख्नको लागि एक अपरेशनको औसत गति (4 dm3 को उत्पादन भोल्युमको लागि)		2,4 सेकेन्ड

तालिका २. गोदाम सञ्चालन पूरा गर्नको लागि औसत समय

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

• सर्वप्रथम, लागतहरू सेलको भोल्युममा सीधै निर्भर हुनुपर्छ - दाता कक्षहरूबाट हस्तान्तरण गरिएका अवशेषहरूको समान मात्रालाई ठूलो कन्टेनरमा भन्दा सानो भोल्युमको कन्टेनरमा राम्रोसँग राखिन्छ, यदि त्यस्तो भोल्युम दुबै कन्टेनरहरूमा पूर्ण रूपमा फिट हुन्छ। यसरी, कन्टेनरहरू छनोट गर्ने कुल लागतहरू न्यूनीकरण गरेर, हामी सेलहरूमा सामानहरू राख्ने पछिका कार्यहरू गर्न चयन क्षेत्रमा "कमजोर" नि: शुल्क भण्डारण क्षमता बचत गर्न प्रयास गर्छौं। चित्र 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) हामीले कुल ओगटेड भोल्युम मात्र घटाउँदैन, तर ओगटेड सेलहरूको संख्या पनि घटाउँछौं, जुन माथि सूचीबद्ध समस्याहरूको गणनायोग्य समाधानको लागि दुई महत्त्वपूर्ण आवश्यकताहरूमध्ये पहिलो हो। स्पष्ट रूपमा, यो आवश्यकता पूरा हुन सुरु गर्नको लागि, असमानताको बायाँ छेउमा केही सकारात्मक स्थिरता थप्न आवश्यक छ। , र कन्टेनरहरूको संख्या घट्दा मात्र यस्तो स्थिरता थप्न आवश्यक छ। हामी तपाईंलाई त्यो सम्झना गरौं कन्टेनर हुँदा १ को बराबर चर हो चयन गरिएको, र कन्टेनर हुँदा ० चयन गरिएको छैन। हामी संकेत गरौं - प्रारम्भिक समाधानमा धेरै कन्टेनरहरू र - नयाँ समाधानमा धेरै कन्टेनरहरू। सामान्यतया, नयाँ असमानता यस्तो देखिन्छ:

माथिको असमानतालाई रूपान्तरण गर्दै, हामीले पाउँछौं

यसको आधारमा, हामीसँग कुल लागत गणनाको लागि सूत्र छ समस्या को केहि समाधान:

तर अहिले प्रश्न उठेको छ: यस्तो स्थिरांकको के मान हुनुपर्छ? ? स्पष्ट रूपमा, यसको मूल्य पर्याप्त ठूलो हुनुपर्छ ताकि समस्याको समाधानको लागि पहिलो आवश्यकता सधैं पूरा हुन्छ। तपाईले, अवश्य पनि, 103 वा 106 बराबरको स्थिरको मान लिन सक्नुहुन्छ, तर म त्यस्ता "जादुई संख्याहरू" लाई बेवास्ता गर्न चाहन्छु। यदि हामीले गोदाम सञ्चालन गर्ने विशिष्टताहरू विचार गर्छौं भने, हामी यस्तो स्थिरताको मूल्यको धेरै राम्रोसँग स्थापित संख्यात्मक अनुमानहरू गणना गर्न सक्छौं।

गरौं - एक क्षेत्र ABC को गोदाम कक्षहरू बीचको अधिकतम दूरी, हाम्रो मामला मा 100 मिटर - गोदाममा कन्टेनर सेलको अधिकतम मात्रा, हाम्रो मामलामा 1000 dm3 बराबर।

मूल्य गणना गर्न पहिलो तरिका । एउटा अवस्थालाई विचार गरौं जहाँ पहिलो टियरमा 2 कन्टेनरहरू छन्, जसमा सामानहरू पहिले नै भौतिक रूपमा अवस्थित छन्, अर्थात्, तिनीहरू आफैं दाता कक्षहरू हुन्, र समान कक्षहरूमा सामानहरू सार्ने लागत स्वाभाविक रूपमा ० बराबर हुन्छ। स्थिरका लागि यस्तो मान फेला पार्न आवश्यक छ , जसमा यो सँधै कन्टेनर 1 बाट कन्टेनर 2 मा बाचिएको सार्न लाभदायक हुनेछ। मान प्रतिस्थापन и माथि दिइएको असमानतामा हामीले पाउँछौं:

जसबाट यो पछ्याउँछ

हामीले माथिको सूत्रमा प्रारम्भिक कार्यहरू प्रदर्शन गर्नको लागि औसत समयको मानहरू प्रतिस्थापन गर्दै

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

हामीले पाएको असमानतालाई रूपान्तरण गर्दै

मात्रा को मान "सुदृढ" गर्न को लागी , मानौं = 0. गोदाम ब्यालेन्स कम्प्रेस गर्ने प्रक्रियामा सामान्यतया संलग्न कक्षहरूको औसत संख्या 10 हो। परिमाणहरूको ज्ञात मानहरू प्रतिस्थापन गर्दै, हामीसँग स्थिरको निम्न मान छ।

हामी प्रत्येक विकल्पको लागि गणना गरिएको सबैभन्दा ठूलो मान लिन्छौं, यो मात्राको मूल्य हुनेछ दिइएको गोदाम प्यारामिटरहरूको लागि। अब, पूर्णताको लागि, कुल लागत गणनाको लागि सूत्र लेखौं केहि सम्भावित समाधान को लागी :

अब, आखिर टाइटानिक प्रयासहरू इनपुट डेटा रूपान्तरण गरेर, हामी भन्न सक्छौं कि सबै इनपुट डेटा इच्छित फारममा रूपान्तरण गरिएको छ र अनुकूलन एल्गोरिथ्ममा प्रयोगको लागि तयार छ।

निष्कर्षमा

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

अर्को लेखमा हामी अन्ततः 2 अघिल्लो प्रकाशनहरू के उद्देश्यका लागि थिए - एक अलग अनुकूलन एल्गोरिदममा आउनेछौं।

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

स्रोत: www.habr.com