Bu yazıda sizə anbarda pulsuz hüceyrələrin olmaması problemini necə həll etdiyimizi və belə bir problemi həll etmək üçün diskret optimallaşdırma alqoritminin inkişaf etdirildiyini söyləyəcəyik. Optimallaşdırma məsələsinin riyazi modelini necə “qurduğumuzdan” və alqoritm üçün giriş məlumatlarını emal edərkən gözlənilmədən qarşılaşdığımız çətinliklərdən danışaq.
Riyaziyyatın biznesdə tətbiqləri ilə maraqlanırsınızsa və 5-ci sinif səviyyəsində düsturların sərt şəxsiyyət çevrilməsindən qorxmursunuzsa, o zaman pişiyə xoş gəlmisiniz!
Məqalə həyata keçirənlər üçün faydalı olacaq WMS-sistemlər, anbar və ya istehsal logistikası sənayesində işləyir, o cümlədən biznesdə riyaziyyatın tətbiqi və müəssisədə proseslərin optimallaşdırılması ilə maraqlanan proqramçılar.
Giriş hissəsi
Bu nəşr anbar proseslərində optimallaşdırma alqoritmlərinin tətbiqi üzrə uğurlu təcrübəmizi paylaşdığımız məqalələr silsiləsini davam etdirir.
В həyata keçirdiyimiz anbarın xüsusiyyətlərini təsvir edir WMS-sistem, həmçinin icra zamanı qalan malların partiyalarının qruplaşdırılması problemini niyə həll etməli olduğumuzu izah edir. WMS-sistemlər və bunu necə etdik.
Optimallaşdırma alqoritmləri haqqında məqaləni yazmağı bitirdikdə, çox böyük olduğu ortaya çıxdı, buna görə də yığılmış materialı 2 hissəyə bölmək qərarına gəldik:
- Birinci hissədə (bu məqalə) problemin riyazi modelini necə “qurduğumuz” və alqoritm üçün giriş məlumatlarının işlənməsi və çevrilməsi zamanı gözlənilmədən qarşılaşdığımız böyük çətinliklərdən danışacağıq.
- İkinci hissədə alqoritmin dildə həyata keçirilməsini ətraflı nəzərdən keçirəcəyik C + +, biz hesablama təcrübəsi keçirəcəyik və müştərinin biznes proseslərində bu cür “ağıllı texnologiyaların” tətbiqi zamanı əldə etdiyimiz təcrübəni ümumiləşdirəcəyik.
Bir məqaləni necə oxumaq olar. Əvvəlki məqaləni oxusanız, dərhal "Mövcud həllərin icmalı" bölməsinə keçə bilərsiniz, yoxsa, həll olunan problemin təsviri aşağıdakı spoylerdədir.
Müştərinin anbarında həll olunan problemin təsviri
Proseslərdə darboğaz
2018-ci ildə həyata keçirmək üçün bir layihəni tamamladıq WMS-Çelyabinskdəki "LD Ticarət Evi" anbarında sistemlər. Biz 1 iş yeri üçün “3C-Logistics: Anbar İdarəetmə 20” məhsulunu tətbiq etdik: operatorlar WMS, anbardarlar, forklift sürücüləri. Orta anbar təxminən 4 min m2, hücrələrin sayı 5000 və SKU sayı 4500-dür. Anbarda 1 kq-dan 400 kq-a qədər müxtəlif ölçülü öz istehsalımız olan kürə klapanları saxlanılır. Anbardakı inventar partiyalarda saxlanılır, çünki FIFO-ya uyğun olaraq malların seçilməsinə ehtiyac var.
Anbar proseslərinin avtomatlaşdırılması sxemlərinin layihələndirilməsi zamanı biz inventarların qeyri-optimal saxlanması ilə bağlı mövcud problemlə qarşılaşdıq. Kranların saxlanması və qoyulmasının xüsusiyyətləri elədir ki, bir vahid saxlama kamerasında yalnız bir partiyadan olan əşyalar ola bilər (bax. Şəkil 1). Məhsullar anbara gündəlik gəlir və hər gəliş ayrı partiyadır. Ümumilikdə, 1 aylıq anbar istismarı nəticəsində hər birinin ayrıca kamerada saxlanmasına baxmayaraq, 30 ayrı partiya yaradılır. Məhsullar çox vaxt bütöv paletlərdə deyil, parçalarla seçilir və nəticədə bir çox hüceyrədə parça seçim zonasında aşağıdakı şəkil müşahidə olunur: həcmi 1 m3-dən çox olan bir hücrədə bir neçə kran parçası var. hüceyrə həcminin 5-10%-dən azını tutur.
Şək 1. Hüceyrədəki bir neçə parçanın şəkli
Aydındır ki, saxlama qabiliyyəti optimal şəkildə istifadə edilmir. Fəlakətin miqyasını təsəvvür etmək üçün rəqəmlər verə bilərəm: orta hesabla, anbarın fəaliyyətinin müxtəlif dövrlərində həcmi 1 m3-dən çox olan "kiçik" balanslı belə hüceyrələrin 100-dən 300-ə qədər hüceyrəsi var. Anbar nisbətən kiçik olduğundan, anbarın məşğul olduğu mövsümlərdə bu amil “darboğaz”a çevrilir və anbarın qəbulu və göndərilməsi proseslərini xeyli ləngidir.
Problemin həlli ideyası
Fikir yarandı: ən yaxın tarixləri olan qalıqların partiyaları bir partiyaya endirilməli və vahid partiya ilə belə qalıqlar kompakt şəkildə bir kamerada və ya bir kamerada kifayət qədər yer yoxdursa, bir neçə yerə yerləşdirilməlidir. qalıqların bütün miqdarı. Belə bir "sıxılma" nümunəsi Şəkil 2-də göstərilmişdir.
Şəkil 2. Hüceyrələrdə qalıqların sıxılması sxemi
Bu, yerləşdirilən yeni mallar üçün istifadə ediləcək işğal edilmiş anbar sahəsini əhəmiyyətli dərəcədə azaltmağa imkan verir. Anbar tutumunun həddindən artıq yükləndiyi bir vəziyyətdə belə bir tədbir son dərəcə zəruridir, əks halda yeni malların yerləşdirilməsi üçün kifayət qədər boş yer olmaya bilər ki, bu da anbarın yerləşdirilməsi və doldurulması proseslərinin dayanmasına səbəb olacaq və nəticədə, qəbulu və göndərilməsini dayandırmaq. Əvvəllər, WMS sisteminin tətbiqindən əvvəl belə bir əməliyyat əl ilə həyata keçirilirdi, bu da səmərəsiz idi, çünki hüceyrələrdə uyğun balansların axtarışı prosesi olduqca uzun idi. İndi WMS sisteminin tətbiqi ilə biz prosesi avtomatlaşdırmaq, sürətləndirmək və ağıllı etmək qərarına gəldik.
Belə bir problemin həlli prosesi 2 mərhələyə bölünür:
- birinci mərhələdə sıxılma tarixinə yaxın olan qruplar tapırıq (bu tapşırığa həsr olunmuşdur );
- ikinci mərhələdə, hər bir partiya qrupu üçün hüceyrələrdə qalan malların ən yığcam yerləşdirilməsini hesablayırıq.
Hazırkı məqalədə alqoritmin ikinci mərhələsinə diqqət yetirəcəyik.
Mövcud həllərin nəzərdən keçirilməsi
Hazırladığımız alqoritmlərin təsvirinə keçməzdən əvvəl artıq bazarda mövcud olan sistemlərin qısa icmalını aparmağa dəyər. WMSoxşar optimal sıxılma funksiyasını həyata keçirən .
İlk növbədə “1C: Enterprise 8. WMS Logistics” məhsulunu qeyd etmək lazımdır. 4C-yə məxsus və təkrarlanan və dördüncü nəslə aid olan anbar idarəçiliyi 1" WMS-AXELOT tərəfindən hazırlanmış sistemlər. Bu sistem fərqli məhsul qalıqlarını bir ümumi hüceyrədə birləşdirmək üçün nəzərdə tutulmuş sıxılma funksiyasını iddia edir. Qeyd etmək lazımdır ki, belə bir sistemdəki sıxılma funksionallığı digər imkanları da əhatə edir, məsələn, malların ABC siniflərinə uyğun olaraq hüceyrələrdə yerləşdirilməsini düzəltmək, lakin biz onların üzərində dayanmayacağıq.
1C kodunu təhlil etsəniz: Enterprise 8. WMS Logistics sistemi. Anbarın idarə edilməsi 4" (funksionallığın bu hissəsində açıqdır), aşağıdakıları yekunlaşdıra bilərik. Qalıq sıxılma alqoritmi kifayət qədər primitiv xətti məntiqi həyata keçirir və heç bir “optimal” sıxılmadan söhbət gedə bilməz. Təbii ki, partiyaların qruplaşmasını nəzərdə tutmur. Belə bir sistem tətbiq edən bir neçə müştəri sıxılma planlaşdırmasının nəticələrindən şikayətləndi. Məsələn, sıxılma zamanı praktikada tez-tez aşağıdakı vəziyyət yarandı: 100 ədəd. Qalan malların 1 ədədin yerləşdiyi bir kameradan digər kameraya keçirilməsi nəzərdə tutulur. mallar, baxmayaraq ki, bunun əksini etmək vaxt sərfi baxımından optimaldır.
Həmçinin, kameralarda qalan malların sıxılması funksionallığı bir çox xarici ölkələrdə bəyan edilmişdir. WMS-sistemlər, lakin təəssüf ki, alqoritmlərin effektivliyi (bu kommersiya sirridir) haqqında heç bir real rəyimiz yoxdur, onların məntiqinin dərinliyi (mülkiyyət qapalı mənbəli proqram təminatı) haqqında heç bir fikrimiz yoxdur, buna görə də mühakimə edə bilmərik.
Problemin riyazi modelini axtarın
Problemin həlli üçün yüksək keyfiyyətli alqoritmlər tərtib etmək üçün ilk növbədə bu problemi riyazi şəkildə aydın şəkildə formalaşdırmaq lazımdır, biz bunu edəcəyik.
Çox sayda hüceyrə var , içərisində bəzi malların qalıqları var. Bundan sonra belə hüceyrələri donor hüceyrələr adlandıracağıq. işarə edək hüceyrədəki malların həcmi $.
Bir partiyanın yalnız bir məhsulunun və ya əvvəllər klasterə birləşdirilən bir neçə partiyanın (oxu: ), malların saxlanması və saxlanması xüsusiyyətləri ilə əlaqədardır. Fərqli məhsullar və ya müxtəlif toplu qruplar öz ayrıca sıxılma prosedurunu həyata keçirməlidir.
Çox sayda hüceyrə var , donor hüceyrələrdən olan qalıqların potensial olaraq yerləşdirilə biləcəyi. Daha sonra belə hüceyrələri konteyner hüceyrələri adlandıracağıq. Bunlar ya anbardakı sərbəst hüceyrələr, ya da müxtəlif donor hüceyrələr ola bilər . Həmişə bol alt çoxluqdur .
Hər bir hüceyrə üçün çoxlarından Tutum məhdudiyyətləri müəyyən edilmişdir , dm3 ilə ölçülür. Bir dm3 tərəfləri 10 sm olan bir kubdur.Anbarda saxlanılan məhsullar kifayət qədər böyükdür, buna görə də bu halda belə diskretləşmə kifayət qədər kifayətdir.
Ən qısa məsafələrin matrisi verilmişdir hər bir hüceyrə cütü arasında metrlə Hara и dəstlərə aiddir и müvafiq.
işarə edək malların hüceyrədən daşınması "xərcləri" hüceyrəyə . işarə edək konteyner seçmək üçün "xərclər" digər hüceyrələrdən qalıqları ona köçürmək. Dəyərlərin necə dəqiq və hansı ölçü vahidlərində hesablanacağı и daha ətraflı nəzərdən keçirəcəyik (giriş məlumatlarının hazırlanması bölməsinə baxın), hələlik bu cür dəyərlərin dəyərlərlə birbaşa mütənasib olacağını söyləmək kifayətdir. и müvafiq.
ilə işarə edək qalıq xanadandırsa, 1 qiymətini alan dəyişən konteynerə köçürüldü , və başqa halda 0. ilə işarə edək konteyner varsa 1 dəyərini alan dəyişən qalan malları ehtiva edir və 0 başqa.
Tapşırıq aşağıdakı kimi ifadə edilir: çoxlu konteyner tapmaq lazımdır və beləliklə, funksiyanı minimuma endirmək üçün donor hüceyrələri konteyner hüceyrələrinə “birləşdirir”
məhdudiyyətlər altında
Ümumilikdə, problemin həllini hesablayarkən, çalışırıq:
- birincisi, saxlama qabiliyyətinə qənaət etmək;
- ikincisi, anbardarların vaxtına qənaət etmək.
Son məhdudiyyət o deməkdir ki, biz malları seçmədiyimiz konteynerə daşıya bilmərik və buna görə də onu seçmək üçün “xərc çəkməmişik”. Bu məhdudiyyət həm də o deməkdir ki, kameralardan konteynerə daşınan malların həcmi konteynerin tutumundan artıq olmamalıdır. Problemin həlli dedikdə biz qablar toplusunu nəzərdə tuturuq və donor hüceyrələrinin konteynerlərə yapışdırılması üsulları.
Optimallaşdırma probleminin bu formalaşdırılması yeni deyil və ötən əsrin 80-ci illərinin əvvəllərindən bir çox riyaziyyatçılar tərəfindən öyrənilmişdir. Xarici ədəbiyyatda uyğun riyazi model ilə 2 optimallaşdırma problemi var: и (tapşırıqlardakı fərqlər haqqında daha sonra danışacağıq). Qeyd etmək lazımdır ki, riyazi ədəbiyyatda belə iki optimallaşdırma məsələsinin tərtibi müəssisələrin yerdə yerləşməsi baxımından tərtib edilir, buna görə də “Obyektin yeri” adı verilmişdir. Əksər hallarda bu, ənənəyə hörmətdir, çünki ilk dəfə bu cür kombinator problemlərini həll etmək zərurəti keçən əsrin 50-ci illərində logistika sahəsindən, əsasən hərbi-sənaye sektorundan yaranmışdır. Müəssisənin yerləşməsi baxımından belə vəzifələr aşağıdakı kimi tərtib edilir:
- İstehsal müəssisələrinin (bundan sonra istehsalat şəhərləri adlandırılacaq) yerləşdirilməsinin potensial olaraq mümkün olduğu məhdud sayda şəhərlər var. Hər bir istehsal şəhəri üçün orada bir müəssisənin açılması xərcləri, habelə orada açılan müəssisənin istehsal gücünə məhdudiyyət göstərilir.
- Müştərilərin həqiqətən yerləşdiyi məhdud şəhərlər dəsti var (bundan sonra müştəri şəhərləri adlandırılacaq). Hər bir belə müştəri şəhəri üçün məhsullara tələbatın həcmi müəyyən edilir. Sadəlik üçün, müəssisələr tərəfindən istehsal olunan və müştərilər tərəfindən istehlak edilən yalnız bir məhsul olduğunu fərz edəcəyik.
- Hər bir şəhər-istehsalçı və şəhər-müştəri cütü üçün tələb olunan həcmdə məhsulun istehsalçıdan müştəriyə çatdırılması üçün nəqliyyat xərclərinin dəyəri göstərilir.
Aşağıdakıları etmək üçün hansı şəhərlərdə biznes açmaq və müştəriləri bu cür müəssisələrə necə bağlamaq lazım olduğunu tapmaq lazımdır:
- Müəssisələrin açılması və nəqliyyat xərclərinin ümumi xərcləri minimal idi;
- Hər hansı açıq müəssisəyə təyin edilmiş müştərilərdən tələbatın həcmi həmin müəssisənin istehsal gücündən çox deyildi.
İndi bu iki klassik problemin yeganə fərqini qeyd etmək lazımdır:
- Tək Mənbədən Tutumlu Obyektin Yerləşdirmə Problemi – müştəri yalnız bir açıq obyektdən təchiz edilir;
- Çox Mənbəli Tutumlu Obyektin Yerləşdirmə Problemi – müştəri eyni vaxtda bir neçə açıq obyektdən təchiz oluna bilər.
İki məsələ arasında belə fərq ilk baxışda əhəmiyyətsiz olsa da, əslində belə məsələlərin tamam başqa kombinator quruluşuna və nəticədə onların həlli üçün tamamilə fərqli alqoritmlərə gətirib çıxarır. Tapşırıqlar arasındakı fərqlər aşağıdakı şəkildə göstərilmişdir.
şək.3. a) Çox Mənbəli Tutumlu Obyektin Yerləşdirmə Problemi
şək.3. b) Tək Mənbədən Tutumlu Obyektin Yerləşdirmə Problemi
Hər iki vəzifə -çətin, yəni daxil edilən verilənlərin ölçüsündə zaman polinomunda belə bir problemi həll edəcək dəqiq alqoritm yoxdur. Daha sadə sözlərlə desək, problemin həlli üçün bütün dəqiq alqoritmlər eksponensial zamanda işləyəcək, baxmayaraq ki, variantların tam axtarışından daha sürətli. Tapşırıqdan bəri -çətindirsə, onda biz yalnız təxmini evristikanı, yəni optimala çox yaxın həlləri ardıcıl hesablayacaq və kifayət qədər tez işləyəcək alqoritmləri nəzərdən keçirəcəyik. Əgər belə bir tapşırıqla maraqlanırsınızsa, burada rus dilində yaxşı icmal tapa bilərsiniz.
Hüceyrələrdə malların optimal sıxılması problemimizin terminologiyasına keçsək, onda:
- müştəri şəhərləri donor hüceyrələrdir qalan mallarla,
- istehsal şəhərləri - konteyner hüceyrələri , digər hüceyrələrin qalıqlarının yerləşdirilməli olduğu,
- nəqliyyat xərcləri - vaxt xərcləri malların həcmini donor hüceyrədən köçürmək üçün anbardar konteyner hüceyrəsinə ;
- biznesin açılması xərcləri - konteyner seçmək xərcləri , konteyner hüceyrəsinin həcminə bərabərdir , sərbəst həcmlərə qənaət etmək üçün müəyyən bir əmsalla vurulur (əmsalın dəyəri həmişə > 1-dir) (giriş məlumatlarının hazırlanması bölməsinə baxın).
Məsələnin məşhur klassik həlləri ilə bənzətmə aparıldıqdan sonra həll alqoritminin arxitekturasının seçilməsindən asılı olan mühüm suala cavab vermək lazımdır: qalıqları donor hüceyrədən yalnız birinə köçürmək mümkündür. və yalnız bir konteyner (Tək Mənbə), yoxsa qalıqları bir neçə konteyner hücrəsinə (Çox Mənbə) köçürmək mümkündürmü?
Qeyd etmək lazımdır ki, praktikada problemin hər iki formalaşdırılması baş verir. Aşağıda hər bir belə parametr üçün bütün müsbət və mənfi cəhətləri təqdim edirik:
| Problemli variant | Seçimlərin üstünlükləri | Seçimlərin mənfi cəhətləri |
|---|---|---|
| Tək Mənbə | Problemin bu variantından istifadə etməklə hesablanmış malların daşınması əməliyyatları:
|
|
| Çox Mənbə | Problemin bu versiyası ilə hesablanmış sıxılmalar adətən “Tək Mənbə” seçimi ilə hesablanmış sıxılmalarla müqayisədə 10-15% daha yığcamdır. Ancaq onu da qeyd edirik ki, donor hüceyrələrində qalıqların sayı nə qədər az olarsa, kompaktlıq fərqi də o qədər az olar. | Problemin bu variantından istifadə etməklə hesablanmış malların daşınması əməliyyatları:
|
Cədvəl 1. Tək Mənbə və Çox Mənbə seçimlərinin müsbət və mənfi cəhətləri.
Tək Mənbə variantının daha çox üstünlükləri olduğundan, həmçinin donor hüceyrələrində qalıqların sayı nə qədər az olarsa, problemin hər iki variantı üçün hesablanmış sıxılma yığcamlıq dərəcəsindəki fərq bir o qədər kiçik olduğunu nəzərə alaraq seçimimizə düşdü. Tək Mənbə seçimi. Mənbə.
Çoxmənbəli seçimin həllinin də baş verdiyini söyləmək lazımdır. Onun həlli üçün çoxlu sayda effektiv alqoritmlər mövcuddur ki, onların da əksəriyyəti bir sıra nəqliyyat problemlərinin həllinə aiddir. Yalnız səmərəli alqoritmlər deyil, həm də zəriflər var, məsələn,
Daxiletmə məlumatlarının hazırlanması
Problemi həll etmək üçün bir alqoritmi təhlil etməyə və inkişaf etdirməyə başlamazdan əvvəl, hansı məlumatları və hansı formada onu giriş kimi qidalandıracağımıza qərar vermək lazımdır. Donor hüceyrələrində qalan malların həcmi və konteyner hüceyrələrinin tutumu ilə bağlı heç bir problem yoxdur, çünki bu, əhəmiyyətsizdir - belə miqdarlar m3 ilə ölçüləcək, lakin konteyner hüceyrəsi və daşınan xərc matrisinin istifadəsi xərcləri ilə, hər şey deyil. çox sadədir!
Əvvəlcə hesablamaya baxaq malların daşınması xərcləri donor hüceyrədən konteyner hüceyrəsinə. İlk növbədə, hərəkət xərclərini hansı ölçü vahidlərində hesablayacağımıza qərar vermək lazımdır. Ən açıq iki seçim metr və saniyədir. Səyahət xərclərini "təmiz" sayğaclarla hesablamaq mənasızdır. Bunu bir nümunə ilə göstərək. Hüceyrəyə icazə verin birinci pillədə, hücrədə yerləşir 30 metr qaldırıldı və ikinci pillədə yerləşir:
- dən köçür в köçməkdən daha bahadır в , çünki ikinci pillədən enmək (döşəmədən 1,5-2 metr) ikinciyə qalxmaqdan daha asandır, baxmayaraq ki, məsafə eyni olacaq;
- 1 ədəd köçürün. hüceyrədən gələn mallar в 10 ədəd hərəkət etməkdən daha asan olacaq. məsafə eyni olsa da eyni məhsul.
Hərəkət xərclərini saniyələr ərzində nəzərdən keçirmək daha yaxşıdır, çünki bu, həm səviyyə fərqini, həm də daşınan malların miqdarındakı fərqi nəzərə almağa imkan verir. Hərəkətin dəyərini saniyələrlə hesablamaq üçün biz hərəkət əməliyyatını elementar komponentlərə ayırmalı və hər bir elementar komponentin yerinə yetirilməsi üçün vaxt ölçmə aparmalıyıq.
Hüceyrədən icazə verin hərəkət edir PC. konteynerdə mallar ... Qoyun – anbarda işçinin orta hərəkət sürəti, m/san ilə ölçülür. Qoy и - birdəfəlik əməliyyatların orta sürəti, müvafiq olaraq, 4 dm3-ə bərabər olan malların həcmi üçün alınır və qoyulur (işçinin əməliyyatları yerinə yetirərkən anbarda bir anda götürdüyü orta həcm). Qoy и müvafiq olaraq alma və yerləşdirmə əməliyyatlarının aparıldığı xanaların hündürlüyü. Məsələn, birinci yarusun (mərtəbənin) orta hündürlüyü 1 m, ikinci yarusun 2 m və s. Sonra hərəkət əməliyyatını tamamlamaq üçün ümumi vaxtı hesablamaq üçün düstur belədir sonrakı:
Cədvəl 2-də saxlanılan malların xüsusiyyətləri nəzərə alınmaqla anbar işçiləri tərəfindən toplanan hər bir elementar əməliyyatın icra müddəti üzrə statistik məlumatlar verilmişdir.
| əməliyyatın adı | Işarə | Orta |
|---|---|---|
| Anbar ətrafında hərəkət edən işçinin orta sürəti | |
1,5 m/s |
| Bir əməliyyatın orta sürəti (4 dm3 məhsul üçün) | |
2,4 saniyə |
Cədvəl 2. Anbar əməliyyatlarının başa çatdırılması üçün orta vaxt
Köçürülmə xərclərinin hesablanması üsuluna qərar verdik. İndi necə hesablayacağımızı başa düşməliyik konteyner hüceyrəsinin seçilməsi xərcləri. Burada hər şey köçürmə xərcləri ilə müqayisədə daha mürəkkəbdir, çünki:
- birincisi, xərclər hüceyrənin həcmindən birbaşa asılı olmalıdır - donor hüceyrələrindən köçürülən qalıqların eyni həcmi, bu həcm hər iki konteynerə tamamilə uyğun olması şərtilə, böyük bir konteynerə nisbətən daha kiçik həcmli bir qabda daha yaxşı yerləşdirilir. . Beləliklə, konteynerlərin seçilməsi ilə bağlı ümumi xərcləri minimuma endirməklə, malların kameralara yerləşdirilməsi üzrə sonrakı əməliyyatları yerinə yetirmək üçün seçim zonasında “qıt” pulsuz saxlama qabiliyyətinə qənaət etməyə çalışırıq. Şəkil 4 qalıqların böyük və kiçik konteynerlərə köçürülməsi variantlarını və sonrakı anbar əməliyyatlarında bu köçürmə variantlarının nəticələrini nümayiş etdirir.
- ikincisi, orijinal problemi həll edərkən biz tam olaraq ümumi xərcləri minimuma endirməliyik və bu, həm daşınma xərclərinin, həm də konteynerlərin seçilməsi xərclərinin cəmi olduğundan, kubmetrdəki hüceyrə həcmini bir şəkildə saniyələrlə əlaqələndirmək lazımdır, mənasızlıqdan uzaq olan.
düyü. 4. Qalıqları müxtəlif tutumlu qablara daşımaq üçün seçimlər.
Şəkil 4, sonrakı malların yerləşdirilməsinin ikinci mərhələsində artıq konteynerə sığmayan qalıqların həcmini qırmızı rənglə göstərir.
Bu, problemin hesablanmış həlləri üçün aşağıdakı tələbləri köçürmək üçün bir neçə saniyəlik xərclər ilə konteyner seçmək üçün xərclərin kubmetrlərini əlaqələndirməyə kömək edəcəkdir:
- Donor zibil qutusundan qalıqların konteyner zibil qutusuna köçürülməsi zəruridir, əgər bu, məhsulu ehtiva edən konteyner qutularının ümumi sayını azaldırsa.
- Konteynerlərin həcmi ilə hərəkətə sərf olunan vaxt arasında tarazlığı saxlamaq lazımdır: məsələn, əgər problemin yeni həllində əvvəlki həlllə müqayisədə həcmdə qazanc böyükdür, lakin zaman itkisi azdırsa. , onda yeni variant seçmək lazımdır.
Son tələbdən başlayaq. Birmənalı olmayan “balans” sözünə aydınlıq gətirmək üçün aşağıdakıları öyrənmək üçün anbar işçiləri arasında sorğu keçirdik. Həcmi olan bir konteyner hüceyrəsi olsun , donor hüceyrələrdən qalan malların hərəkətinin təyin edildiyi və belə hərəkətin ümumi vaxtı bərabərdir . Eyni donor hüceyrələrdən eyni miqdarda malların hər yerləşdirmənin öz hesablamalarına malik olduğu digər konteynerlərə yerləşdirilməsi üçün bir neçə alternativ variant olsun. Hara < и Hara >.
Sual verilir: həcmdə minimum qazanc nədir müəyyən vaxt itkisi dəyəri üçün məqbuldur ? Bir misalla izah edək. Əvvəlcə qalıqların həcmi 1000 dm3 (1 m3) olan konteynerə yerləşdirilməli idi və ötürülmə müddəti 70 saniyə idi. Qalıqları həcmi 500 dm3 və müddəti 130 saniyə olan başqa bir qaba yerləşdirmək imkanı var. Sual: 60 dm500 boş həcmə qənaət etmək üçün anbardarın vaxtının əlavə 3 saniyəsini malın daşınmasına sərf etməyə hazırıqmı? Anbar işçilərinin sorğusunun nəticələrinə əsasən aşağıdakı diaqram tərtib edilmişdir.
düyü. 5. Minimum icazə verilən həcm qənaətinin istismar müddətindəki fərqin artımından asılılığının diaqramı
Yəni əlavə vaxt xərcləri 40 saniyədirsə, onda biz onları yalnız həcmdə qazanc ən azı 500 dm3 olduqda sərf etməyə hazırıq. Asılılıqda bir qədər qeyri-xətti olmasına baxmayaraq, sonrakı hesablamaların sadəliyi üçün kəmiyyətlər arasındakı asılılığın xətti olduğunu və bərabərsizliklə təsvir edildiyini güman edəcəyik.
Aşağıdakı şəkildə malların konteynerlərə yerləşdirilməsinin aşağıdakı üsullarını nəzərdən keçiririk.
düyü. 6. Variant (a): 2 konteyner, ümumi həcmi 400 dm3, ümumi vaxt 150 san.
düyü. 6. Variant (b): 2 konteyner, ümumi həcmi 600 dm3, ümumi vaxt 190 san.
düyü. 6. Variant (c): 1 konteyner, ümumi həcmi 400 dm3, ümumi vaxt 200 san.
Konteynerlərin seçilməsi üçün (a) variantı orijinal variantdan daha üstündür, çünki bərabərsizlik yerinə yetirilir: (800-400)/10>=150-120, bu da 40 >= 30 deməkdir. Variant (b) orijinaldan daha az üstünlük təşkil edir. variant , çünki bərabərsizlik yerinə yetirilmir: (800-600)/10>=190-150 ki, 20 >= 40 deməkdir. Lakin (c) variantı belə məntiqə uyğun gəlmir! Bu seçimi daha ətraflı nəzərdən keçirək. Bir tərəfdən (800-400)/10>=200-120 bərabərsizliyi, yəni 40 >= 80 bərabərsizliyi təmin edilmir, bu, həcm qazancının zamanla belə böyük itkiyə dəymədiyini göstərir.
Ancaq digər tərəfdən, bu variantda (c) biz yalnız ümumi işğal edilmiş həcmi azaltmaqla yanaşı, yuxarıda sadalanan problemlərin hesablana bilən həlli üçün iki vacib tələbdən birincisi olan işğal edilmiş hüceyrələrin sayını da azaldırıq. Aydındır ki, bu tələbin yerinə yetirilməyə başlaması üçün bərabərsizliyin sol tərəfinə müəyyən müsbət sabit əlavə etmək lazımdır. , və belə bir sabiti yalnız qabların sayı azaldıqda əlavə etmək lazımdır. Bunu xatırladaq konteyner olduqda 1-ə bərabər dəyişəndir seçilmiş və konteyner olduqda 0 seçilməyib. işarə edək – ilkin məhlulda çoxlu qablar və – yeni məhlulda çoxlu konteynerlər. Ümumiyyətlə, yeni bərabərsizlik belə görünəcək:
Yuxarıdakı bərabərsizliyi çevirərək, alırıq
Buna əsaslanaraq, ümumi dəyəri hesablamaq üçün bir düsturumuz var problemin bəzi həlli:
Amma indi sual yaranır: belə bir sabit hansı dəyərə malik olmalıdır? ? Aydındır ki, onun dəyəri kifayət qədər böyük olmalıdır ki, problemin həlli üçün ilk tələb həmişə yerinə yetirilsin. Əlbəttə ki, sabitin qiymətini 103 və ya 106-ya bərabər götürə bilərsiniz, amma mən belə "sehrli nömrələrdən" qaçmaq istərdim. Anbar əməliyyatlarının yerinə yetirilməsinin xüsusiyyətlərini nəzərə alsaq, belə bir sabitin dəyərinin bir neçə əsaslı ədədi təxminlərini hesablaya bilərik.
Qoy – bir ABC zonasının anbar hücrələri arasındakı maksimum məsafə, bizim vəziyyətimizdə 100 m-ə bərabərdir. – anbardakı konteyner hüceyrəsinin maksimum həcmi, bizim vəziyyətimizdə 1000 dm3-ə bərabərdir.
Dəyəri hesablamağın ilk yolu . Elə bir vəziyyəti nəzərdən keçirək ki, birinci pillədə 2 konteyner var, orada mallar artıq fiziki olaraq yerləşir, yəni onlar özləri donor hüceyrələrdir və malı eyni hücrələrə daşımaq xərcləri təbii olaraq 0-a bərabərdir. sabit üçün belə bir qiymət tapmaq lazımdır , burada qalıqları həmişə konteyner 1-dən 2-ci qaba köçürmək faydalı olardı. Dəyərləri əvəz etmək и Yuxarıda verilmiş bərabərsizlikdə alırıq:
ondan irəli gəlir
Elementar əməliyyatların yerinə yetirilməsi üçün orta vaxtın dəyərlərini yuxarıdakı düsturla əvəz edərək əldə edirik
Dəyəri hesablamaq üçün ikinci yol . Var olan bir vəziyyəti nəzərdən keçirək malların konteynerə daşınması planlaşdırılan donor hüceyrələri 1. İşarə edək – donor hüceyrədən məsafə 1-ci konteynerə. Həmçinin 2-ci konteyner də var ki, orada artıq mallar var və onun həcmi qalanları yerləşdirməyə imkan verir. hüceyrələr. Sadəlik üçün, donor hüceyrələrdən konteynerlərə köçürülən malların həcminin eyni və bərabər olduğunu fərz edəcəyik. . Sabitin belə qiymətini tapmaq tələb olunur , buradan bütün qalıqların yerləşdirilməsi 2-ci konteynerdəki hüceyrələri müxtəlif qablara yerləşdirməkdənsə həmişə daha sərfəli olardı:
Aldığımız bərabərsizliyi çevirərək
Kəmiyyətin dəyərini "gücləndirmək" üçün , bunu fərz edək = 0. Adətən anbar qalıqlarının sıxılması prosedurunda iştirak edən hüceyrələrin orta sayı 10-dur. Kəmiyyətlərin məlum dəyərlərini əvəz etməklə, sabitin aşağıdakı dəyərinə sahibik.
Hər seçim üçün hesablanmış ən böyük dəyəri götürürük, bu kəmiyyətin dəyəri olacaqdır verilmiş anbar parametrləri üçün. İndi tamlıq üçün ümumi xərclərin hesablanması formulunu yazaq bəzi mümkün həll üçün :
İndi, axır Herkül səyləri Giriş verilənlərini transformasiya etməklə deyə bilərik ki, bütün daxil edilən verilənlər istənilən formaya çevrilib və optimallaşdırma alqoritmində istifadəyə hazırdır.
Nəticə
Təcrübədən göründüyü kimi, alqoritm üçün giriş məlumatlarının hazırlanması və çevrilməsi mərhələsinin mürəkkəbliyi və əhəmiyyəti çox vaxt lazımınca qiymətləndirilmir. Bu yazıda, yalnız yüksək keyfiyyətli və ağıllı şəkildə hazırlanmış giriş məlumatlarının alqoritm tərəfindən hesablanmış qərarları müştəri üçün həqiqətən dəyərli edə biləcəyini göstərmək üçün bu mərhələyə xüsusi diqqət yetirdik. Bəli, düsturların çoxlu törəmələri var idi, amma biz sizi katadan əvvəl də xəbərdar etmişdik :)
Növbəti məqalədə nəhayət, əvvəlki 2 nəşrin nə üçün nəzərdə tutulduğuna - diskret optimallaşdırma alqoritminə gələcəyik.
Məqaləni hazırladı
Roman Şangin, layihələr şöbəsinin proqramçısı,
Birinci Bit şirkəti, Çelyabinsk
Mənbə: www.habr.com