سنخبرك في هذه المقالة كيف قمنا بحل مشكلة نقص الخلايا الحرة في المستودع وتطوير خوارزمية تحسين منفصلة لحل مثل هذه المشكلة. دعونا نتحدث عن كيفية "بناء" النموذج الرياضي لمشكلة التحسين، وعن الصعوبات التي واجهناها بشكل غير متوقع عند معالجة بيانات الإدخال للخوارزمية.
إذا كنت مهتمًا بتطبيقات الرياضيات في مجال الأعمال ولا تخشى تحولات الهوية الصارمة للصيغ في مستوى الصف الخامس، فمرحبًا بك في القطة!
ستكون المقالة مفيدة لأولئك الذين يقومون بالتنفيذ WMS- الأنظمة، التي تعمل في مجال المستودعات أو صناعة لوجستيات الإنتاج، وكذلك المبرمجين المهتمين بتطبيقات الرياضيات في الأعمال التجارية وتحسين العمليات في المؤسسة.
الجزء التمهيدي
يواصل هذا المنشور سلسلة المقالات التي نشارك فيها تجربتنا الناجحة في تنفيذ خوارزميات التحسين في عمليات المستودعات.
В يصف تفاصيل المستودع الذي قمنا بتنفيذه WMS-النظام، ويوضح أيضًا سبب حاجتنا إلى حل مشكلة تجميع دفعات من البضائع المتبقية أثناء التنفيذ WMS-الأنظمة، وكيف فعلنا ذلك.
عندما انتهينا من كتابة المقالة حول خوارزميات التحسين، تبين أنها كبيرة جدًا، لذلك قررنا تقسيم المادة المتراكمة إلى قسمين:
- سنتحدث في الجزء الأول (هذا المقال) عن كيفية "بناء" النموذج الرياضي للمشكلة، وعن الصعوبات الكبيرة التي واجهناها بشكل غير متوقع عند معالجة وتحويل البيانات المدخلة للخوارزمية.
- في الجزء الثاني سننظر بالتفصيل في تنفيذ الخوارزمية في اللغة C + +سنقوم بإجراء تجربة حسابية وتلخيص الخبرة التي اكتسبناها أثناء تنفيذ مثل هذه "التقنيات الذكية" في العمليات التجارية للعميل.
كيف تقرأ مقالا. إذا قرأت المقالة السابقة، فيمكنك الانتقال فورًا إلى الفصل "نظرة عامة على الحلول الحالية"، وإذا لم يكن الأمر كذلك، فإن وصف المشكلة التي يتم حلها موجود في المفسد أدناه.
وصف المشكلة التي يتم حلها في مستودع العميل
اختناق في العمليات
في عام 2018، أكملنا مشروعًا للتنفيذ WMS-الأنظمة في مستودع "بيت التجارة "LD" في تشيليابينسك. قمنا بتنفيذ منتج "1C-Logistics: Warehouse Management 3" لـ 20 مكان عمل: المشغلين WMS، أمناء المخازن، سائقي الرافعات الشوكية. يبلغ متوسط المستودع حوالي 4 آلاف م2، وعدد الخلايا 5000 وعدد وحدات SKU 4500. ويخزن المستودع الصمامات الكروية من إنتاجنا بأحجام مختلفة من 1 كجم إلى 400 كجم. يتم تخزين المخزون في المستودع على دفعات، نظرًا لوجود حاجة لتحديد البضائع وفقًا لنظام FIFO.
أثناء تصميم مخططات أتمتة عمليات المستودعات، واجهنا المشكلة الحالية المتمثلة في تخزين المخزون غير الأمثل. خصوصيات تخزين ووضع الرافعات هي أن خلية تخزين وحدة واحدة يمكن أن تحتوي فقط على عناصر من دفعة واحدة (انظر الشكل 1). تصل المنتجات إلى المستودع يوميا وكل وصول هو دفعة منفصلة. في المجمل، نتيجة لمدة شهر واحد من تشغيل المستودع، يتم إنشاء 1 دفعة منفصلة، على الرغم من ضرورة تخزين كل منها في خلية منفصلة. غالبًا ما يتم اختيار المنتجات ليس في منصات نقالة كاملة، ولكن على شكل قطع، ونتيجة لذلك، في منطقة اختيار القطعة في العديد من الخلايا، يتم ملاحظة الصورة التالية: في خلية يزيد حجمها عن 30 م 1 توجد عدة قطع من الرافعات التي تشغل أقل من 3-5% من حجم الخلية.
الشكل 1. صورة لعدة قطع في الخلية
ومن الواضح أن سعة التخزين لا يتم استخدامها على النحو الأمثل. لتخيل حجم الكارثة، يمكنني تقديم أرقام: في المتوسط، هناك من 1 إلى 3 خلية من هذه الخلايا بحجم يزيد عن 100 متر مكعب مع أرصدة "ضئيلة" خلال فترات مختلفة من تشغيل المستودع. نظرًا لأن المستودع صغير نسبيًا، خلال مواسم ازدحام المستودعات، يصبح هذا العامل "عنق الزجاجة" ويبطئ بشكل كبير عمليات المستودع الخاصة بالقبول والشحن.
فكرة حل المشكلة
نشأت فكرة: يجب تقليل دفعات بقايا الطعام ذات التواريخ الأقرب إلى دفعة واحدة، ويجب وضع بقايا الطعام ذات الدفعة الموحدة بشكل مضغوط معًا في خلية واحدة، أو في عدة خلايا، إذا لم يكن هناك مساحة كافية في خلية واحدة لاستيعاب كامل كمية بقايا الطعام. ويرد مثال على هذا "الضغط" في الشكل 2.
الصورة 2. مخطط لضغط المخلفات في الخلايا
يتيح لك ذلك تقليل مساحة المستودع المشغولة بشكل كبير والتي سيتم استخدامها للبضائع الجديدة التي يتم وضعها. في حالة زيادة التحميل على سعة المستودع، يكون هذا الإجراء ضروريًا للغاية، وإلا فقد لا يكون هناك مساحة خالية كافية لاستيعاب البضائع الجديدة، مما سيؤدي إلى توقف عمليات التنسيب والتجديد في المستودع، ونتيجة لذلك، إلى التوقف عن القبول والشحن. في السابق، قبل تطبيق نظام WMS، تم إجراء مثل هذه العملية يدويًا، وهي غير فعالة، لأن عملية البحث عن الأرصدة المناسبة في الخلايا كانت طويلة جدًا. الآن، مع تقديم نظام WMS، قررنا أتمتة العملية وتسريعها وجعلها ذكية.
تنقسم عملية حل مثل هذه المشكلة إلى مرحلتين:
- في المرحلة الأولى نجد مجموعات من الدفعات قريبة من تاريخ الضغط (مخصصة لهذه المهمة );
- في المرحلة الثانية، لكل مجموعة من الدفعات، نحسب الموضع الأكثر إحكاما للبضائع المتبقية في الخلايا.
في المقالة الحالية سنركز على المرحلة الثانية من الخوارزمية.
مراجعة الحلول الحالية
قبل الانتقال إلى وصف الخوارزميات التي قمنا بتطويرها، من المفيد إجراء لمحة موجزة عن الأنظمة الموجودة بالفعل في السوق WMS، والتي تنفذ وظيفة ضغط مثالية مماثلة.
بادئ ذي بدء، من الضروري ملاحظة المنتج "1C: Enterprise 8.WMS Logistics. إدارة المستودعات 4"، المملوكة والمكررة لشركة 1C وتنتمي إلى الجيل الرابع WMS-الأنظمة التي طورتها شركة AXELOT. يطالب هذا النظام بوظيفة الضغط، والتي تم تصميمها لتوحيد بقايا المنتج المتباينة في خلية واحدة مشتركة. ومن الجدير بالذكر أن وظيفة الضغط في مثل هذا النظام تتضمن أيضًا إمكانيات أخرى، على سبيل المثال، تصحيح وضع البضائع في الخلايا وفقًا لفئاتها ABC، لكننا لن نتوقف عندها.
إذا قمت بتحليل رمز نظام 1C: Enterprise 8.WMS اللوجستي. إدارة المستودعات 4" (وهي مفتوحة في هذا الجزء من الوظيفة)، يمكننا أن نستنتج ما يلي. تطبق خوارزمية الضغط المتبقي منطقًا خطيًا بدائيًا إلى حد ما ولا يمكن الحديث عن أي ضغط "أمثل". وبطبيعة الحال، فإنه لا ينص على تجميع الأحزاب. اشتكى العديد من العملاء الذين طبقوا مثل هذا النظام من نتائج تخطيط الضغط. على سبيل المثال، في كثير من الأحيان في الممارسة العملية أثناء الضغط حدث الوضع التالي: 100 جهاز كمبيوتر شخصى. من المخطط نقل البضائع المتبقية من خلية إلى خلية أخرى حيث توجد قطعة واحدة. البضائع، على الرغم من أنه الأمثل من وجهة نظر استهلاك الوقت للقيام بالعكس.
كما تم الإعلان عن وظيفة ضغط البضائع المتبقية في الخلايا في العديد من البلدان الأجنبية. WMSالأنظمة، ولكن لسوء الحظ، ليس لدينا أي ردود فعل حقيقية حول فعالية الخوارزميات (وهذا سر تجاري)، ناهيك عن فكرة عن عمق منطقها (برمجيات مغلقة المصدر مملوكة)، لذلك لا يمكننا الحكم.
البحث عن نموذج رياضي للمشكلة
من أجل تصميم خوارزميات عالية الجودة لحل مشكلة ما، من الضروري أولاً صياغة هذه المشكلة بشكل واضح رياضيًا، وهو ما سنفعله.
هناك العديد من الخلايا والتي تحتوي على بقايا بعض البضائع. وفيما يلي سنسمي هذه الخلايا بالخلايا المانحة. دعونا نشير حجم البضائع في الخلية $.
من المهم أن نقول أن منتجًا واحدًا فقط من دفعة واحدة، أو عدة دفعات تم دمجها مسبقًا في مجموعة (اقرأ: )، والذي يرجع إلى تفاصيل تخزين وتخزين البضائع. يجب أن تقوم المنتجات المختلفة أو مجموعات الدُفعات المختلفة بتشغيل إجراء الضغط المنفصل الخاص بها.
هناك العديد من الخلايا ، حيث يمكن وضع بقايا الخلايا المانحة. وسوف نسمي هذه الخلايا أيضًا خلايا الحاوية. يمكن أن تكون إما خلايا حرة في المستودع أو خلايا مانحة من مجموعة متنوعة . دائما الكثير هي مجموعة فرعية .
لكل خلية من العديد تم وضع قيود على القدرات ، مقاسة بالدم3. واحد dm3 عبارة عن مكعب بجوانب 10 سم، والمنتجات المخزنة في المستودع كبيرة جدًا، لذا في هذه الحالة يكون هذا التمييز كافيًا.
نظرا لمصفوفة أقصر المسافات بالأمتار بين كل زوج من الخلايا حيث и تنتمي إلى مجموعات и على التوالي.
دعونا نشير "تكاليف" نقل البضائع من الخلية في خلية . دعونا نشير "تكاليف" اختيار الحاوية لنقل بقايا الخلايا الأخرى إليه. كيف بالضبط وبأي وحدات قياس سيتم حساب القيم и سننظر أكثر (انظر قسم إعداد بيانات الإدخال)، في الوقت الحالي يكفي أن نقول أن هذه القيم ستكون متناسبة بشكل مباشر مع القيم и على التوالي.
دعونا نشير بواسطة متغير يأخذ القيمة 1 إذا كان الباقي من الخلية انتقل إلى الحاوية و0 غير ذلك. دعونا نشير بواسطة متغير يأخذ القيمة 1 إذا كانت الحاوية يحتوي على البضائع المتبقية، و 0 خلاف ذلك.
تم ذكر المهمة على النحو التالي: أنت بحاجة إلى العثور على العديد من الحاويات وبالتالي "ربط" الخلايا المانحة بخلايا الحاوية من أجل تقليل الوظيفة
تحت القيود
في المجمل، عند حساب حل المشكلة، فإننا نسعى جاهدين إلى:
- أولاً، لتوفير سعة التخزين؛
- ثانياً، لتوفير وقت أصحاب المتاجر.
القيد الأخير يعني أننا لا نستطيع نقل البضائع إلى حاوية لم نختارها، وبالتالي لم "نتحمل تكاليف" اختيارها. ويعني هذا القيد أيضًا أن حجم البضائع المنقولة من الخلايا إلى الحاوية يجب ألا يتجاوز سعة الحاوية. من خلال حل مشكلة نعني مجموعة من الحاويات وطرق ربط الخلايا المانحة بالحاويات.
هذه الصيغة لمسألة التحسين ليست جديدة، وقد تمت دراستها من قبل العديد من علماء الرياضيات منذ أوائل الثمانينات من القرن الماضي. يوجد في الأدب الأجنبي مشكلتان في التحسين مع نموذج رياضي مناسب: и (سنتحدث عن الاختلافات في المهام لاحقًا). تجدر الإشارة إلى أنه في الأدبيات الرياضية، تمت صياغة هاتين المشكلتين للتحسين من حيث موقع المؤسسات على الأرض، ومن هنا جاء اسم "موقع المنشأة". يعد هذا في الغالب بمثابة تكريم للتقاليد، لأنه لأول مرة جاءت الحاجة إلى حل مثل هذه المشكلات التوافقية من مجال الخدمات اللوجستية، وخاصة من القطاع الصناعي العسكري في الخمسينيات من القرن الماضي. فيما يتعلق بموقع المؤسسة، يتم صياغة هذه المهام على النحو التالي:
- هناك عدد محدود من المدن التي يمكن فيها تحديد مواقع شركات التصنيع (يشار إليها فيما يلي باسم مدن التصنيع). يتم تحديد تكاليف فتح مؤسسة فيها لكل مدينة صناعية، بالإضافة إلى تحديد الطاقة الإنتاجية للمؤسسة المفتوحة فيها.
- هناك مجموعة محدودة من المدن التي يتواجد فيها العملاء فعليًا (يشار إليها فيما يلي باسم مدن العملاء). ولكل مدينة عميلة، يتم تحديد حجم الطلب على المنتجات. للتبسيط، سنفترض أن هناك منتجًا واحدًا فقط تنتجه الشركات ويستهلكه العملاء.
- لكل زوج من الشركة المصنعة للمدينة والعميل للمدينة، يتم تحديد قيمة تكاليف النقل لتسليم الحجم المطلوب من المنتجات من الشركة المصنعة إلى العميل.
أنت بحاجة إلى العثور على المدن التي يمكنك فتح أعمال تجارية فيها وكيفية ربط العملاء بهذه الشركات من أجل:
- كانت التكاليف الإجمالية لفتح المشاريع وتكاليف النقل ضئيلة؛
- ولم يتجاوز حجم الطلب من العملاء المخصصين لأي مؤسسة مفتوحة الطاقة الإنتاجية لتلك المؤسسة.
الآن تجدر الإشارة إلى الفرق الوحيد في هاتين المشكلتين الكلاسيكيتين:
- مشكلة موقع المنشأة ذات المصدر الواحد – يتم إمداد العميل من منشأة مفتوحة واحدة فقط؛
- مشكلة موقع المنشأة متعددة المصادر – يمكن إمداد العميل من عدة منشآت مفتوحة في نفس الوقت.
مثل هذا الاختلاف بين المشكلتين غير مهم للوهلة الأولى، ولكنه في الواقع يؤدي إلى بنية اندماجية مختلفة تمامًا لمثل هذه المشكلات، ونتيجة لذلك، إلى خوارزميات مختلفة تمامًا لحلها. وتظهر الاختلافات بين المهام في الشكل أدناه.
تين. 3. أ) مشكلة موقع المنشأة متعددة المصادر
تين. 3. ب) مشكلة موقع المنشأة ذات المصدر الواحد
كلتا المهمتين - صعب، أي أنه لا توجد خوارزمية دقيقة من شأنها أن تحل مثل هذه المشكلة في زمن متعدد الحدود في حجم البيانات المدخلة. وبعبارة أبسط، فإن جميع الخوارزميات الدقيقة لحل المشكلة ستعمل في وقت أسي، على الرغم من أنها ربما تكون أسرع من البحث الكامل عن الخيارات. منذ المهمة - من الصعب، فإننا سننظر فقط في الاستدلال التقريبي، أي الخوارزميات التي ستحسب باستمرار الحلول القريبة جدًا من الأمثل وستعمل بسرعة كبيرة. إذا كنت مهتمًا بمثل هذه المهمة، فيمكنك العثور على نظرة عامة جيدة باللغة الروسية هنا.
إذا انتقلنا إلى مصطلحات مشكلتنا المتمثلة في الضغط الأمثل للبضائع في الخلايا، فعندئذ:
- المدن العميلة هي خلايا مانحة مع باقي البضائع
- المدن الصناعية – خلايا الحاويات ، حيث من المفترض أن يتم وضع البقايا من الخلايا الأخرى،
- تكاليف النقل - تكاليف الوقت أمين مخزن لنقل حجم البضائع من الخلية المانحة في خلية حاوية ;
- تكاليف فتح مشروع تجاري - تكاليف اختيار الحاوية ، يساوي حجم الخلية الحاوية ، مضروبًا في معامل معين لحفظ الأحجام الحرة (قيمة المعامل تكون دائمًا > 1) (راجع قسم إعداد بيانات الإدخال).
بعد إجراء القياس مع الحلول الكلاسيكية المعروفة للمشكلة، من الضروري الإجابة على سؤال مهم يعتمد عليه اختيار بنية خوارزمية الحل: نقل الباقي من الخلية المانحة ممكن فقط إلى خلية واحدة وحاوية واحدة فقط (Single-Source)، أم أنه من الممكن نقل الباقي إلى عدة خلايا حاوية (Multi-Source)؟
تجدر الإشارة إلى أن كلا الصيغتين للمشكلة تحدثان في الممارسة العملية. نقدم جميع إيجابيات وسلبيات كل إعداد من هذا القبيل أدناه:
| متغير المشكلة | إيجابيات الخيار | سلبيات الخيار |
|---|---|---|
| مصدر واحد | عمليات حركة البضائع المحسوبة باستخدام هذا البديل للمشكلة:
|
|
| متعدد المصادر | عادةً ما تكون عمليات الضغط المحسوبة باستخدام هذا الإصدار من المشكلة أكثر إحكاما بنسبة 10-15% مقارنة بعمليات الضغط المحسوبة باستخدام خيار "المصدر الواحد". لكننا نلاحظ أيضًا أنه كلما قل عدد البقايا في الخلايا المانحة، قل الفرق في الاكتناز | عمليات حركة البضائع المحسوبة باستخدام هذا البديل للمشكلة:
|
الجدول 1. إيجابيات وسلبيات خيارات المصدر الواحد والمصادر المتعددة.
نظرًا لأن خيار المصدر الواحد يتمتع بمزايا أكثر، ومع الأخذ في الاعتبار أيضًا حقيقة أنه كلما قل عدد البقايا في الخلايا المانحة، قل الفرق في درجة ضغط الضغط المحسوب لكلا الخيارين للمشكلة، وقع اختيارنا على خيار المصدر الواحد.
تجدر الإشارة إلى أن حل خيار المصادر المتعددة موجود أيضًا. يوجد عدد كبير من الخوارزميات الفعالة لحلها، ومعظمها يهدف إلى حل عدد من مشكلات النقل. لا توجد أيضًا خوارزميات فعالة فحسب، بل توجد أيضًا خوارزميات أنيقة، على سبيل المثال،
تحضير بيانات الإدخال
قبل البدء في تحليل وتطوير خوارزمية لحل مشكلة ما، من الضروري تحديد البيانات والشكل الذي سنقدمها كمدخلات. لا توجد مشاكل مع حجم البضائع المتبقية في الخلايا المانحة وقدرة خلايا الحاوية، لأن هذا أمر تافه - سيتم قياس هذه الكميات بالمتر المكعب، ولكن مع تكاليف استخدام خلية الحاوية ومصفوفة تكلفة النقل، ليس كل شيء بسيط جدا!
دعونا نلقي نظرة على الحساب أولا تكاليف نقل البضائع من الخلية المانحة إلى الخلية الحاوية. بادئ ذي بدء، من الضروري تحديد وحدات القياس التي سنحسب فيها تكاليف الحركة. الخياران الأكثر وضوحًا هما الأمتار والثواني. ليس من المنطقي حساب تكاليف السفر بالأمتار "الخالصة". دعونا نعرض هذا مع مثال. دع الخلية تقع في الطبقة الأولى، الخلية تمت إزالته بمقدار 30 مترًا ويقع في الطبقة الثانية:
- الانتقال من в أكثر تكلفة من الانتقال من в لأن النزول من الطبقة الثانية (1,5-2 متر من الأرض) أسهل من الصعود إلى الطبقة الثانية، على الرغم من أن المسافة ستكون هي نفسها؛
- نقل 1 جهاز كمبيوتر. البضائع من الخلية в سيكون الأمر أسهل من تحريك 10 قطع. نفس المنتج، على الرغم من أن المسافة ستكون هي نفسها.
من الأفضل مراعاة تكاليف النقل في ثوانٍ، لأن هذا يسمح لك بمراعاة الفرق في المستويات والفرق في كمية البضائع المنقولة. لحساب تكلفة الحركة بالثواني، يجب علينا تحليل عملية الحركة إلى مكونات أولية وأخذ قياسات زمنية لتنفيذ كل مكون أولي.
دع من الخلية التحركات الكمبيوتر. البضائع في الحاوية ... اسمحوا ان - متوسط سرعة حركة العامل في المستودع، مقاسة بالمتر المربع/ الثانية. يترك и - متوسط سرعات العمليات لمرة واحدة تأخذ وتوضع، على التوالي، لحجم بضائع يساوي 4 dm3 (متوسط الحجم الذي يأخذه الموظف في المرة الواحدة في المستودع عند إجراء العمليات). يترك и ارتفاع الخلايا التي يتم منها تنفيذ عمليات الأخذ والوضع، على التوالي. على سبيل المثال، يبلغ متوسط ارتفاع الطبقة الأولى (الأرضية) 1 متر، والطبقة الثانية 2 متر، وما إلى ذلك. ثم تكون صيغة حساب الوقت الإجمالي لإكمال عملية النقل هي التالي:
يوضح الجدول 2 إحصائيات وقت تنفيذ كل عملية أولية، والتي تم جمعها بواسطة موظفي المستودعات، مع مراعاة تفاصيل البضائع المخزنة.
| اسم العملية | تعيين | متوسط |
|---|---|---|
| متوسط سرعة تحرك العامل في المستودع | |
1,5 م / ث |
| متوسط سرعة عملية وضع واحدة (لحجم منتج يبلغ 4 ديسيمتر مكعب) | |
2,4 ثانية |
الجدول 2. متوسط الوقت اللازم لإتمام عمليات المستودع
لقد قررنا طريقة حساب تكاليف النقل. الآن نحن بحاجة إلى معرفة كيفية الحساب تكاليف اختيار خلية الحاوية. كل شيء هنا أكثر تعقيدًا بكثير من تكاليف النقل، للأسباب التالية:
- أولاً، يجب أن تعتمد التكاليف بشكل مباشر على حجم الخلية - من الأفضل وضع نفس حجم المخلفات المنقولة من الخلايا المانحة في حاوية ذات حجم أصغر من الحاوية الكبيرة، بشرط أن يتناسب هذا الحجم تمامًا مع كلتا الحاويتين. وبالتالي، من خلال تقليل إجمالي تكاليف اختيار الحاويات، فإننا نسعى جاهدين لتوفير سعة التخزين المجانية "النادرة" في منطقة الاختيار لإجراء العمليات اللاحقة لوضع البضائع في الخلايا. يوضح الشكل 4 خيارات نقل المخلفات إلى حاويات كبيرة وصغيرة وعواقب خيارات النقل هذه في عمليات المستودعات اللاحقة.
- ثانيًا، نظرًا لأننا نحتاج عند حل المشكلة الأصلية إلى تقليل التكاليف الإجمالية تمامًا، وهذا هو مجموع كل من تكاليف النقل وتكاليف اختيار الحاويات، فإن أحجام الخلايا بالمتر المكعب يجب أن تكون مرتبطة بطريقة ما بالثواني، وهو أبعد ما يكون عن التافهة.
أرز. 4. خيارات نقل بقايا الطعام إلى حاويات ذات سعات مختلفة.
يوضح الشكل 4 باللون الأحمر حجم بقايا الطعام التي لم تعد تتناسب مع الحاوية في المرحلة الثانية من وضع البضائع اللاحقة.
سيساعد ذلك على ربط تكاليف الأمتار المكعبة لاختيار الحاوية بثواني تكاليف نقل المتطلبات التالية للحلول المحسوبة للمشكلة:
- من الضروري أن يتم نقل الأرصدة من الصندوق المتبرع إلى صندوق الحاوية في أي حال إذا كان ذلك يقلل من العدد الإجمالي لصناديق الحاويات التي تحتوي على المنتج.
- من الضروري الحفاظ على التوازن بين حجم الحاويات والوقت المستغرق في التحرك: على سبيل المثال، إذا كان في حل جديد لمشكلة مقارنة بالحل السابق، يكون الكسب في الحجم كبيرًا، ولكن الخسارة في الوقت تكون صغيرة ، فمن الضروري اختيار خيار جديد.
لنبدأ بالمتطلبات الأخيرة. ومن أجل توضيح كلمة "الرصيد" الغامضة، قمنا بإجراء مسح لموظفي المستودعات لمعرفة ما يلي. يجب أن تكون هناك خلية حاوية للحجم ، والتي يتم تخصيص حركة البضائع المتبقية من الخلايا المانحة لها والوقت الإجمالي لهذه الحركة يساوي . يجب أن تكون هناك عدة خيارات بديلة لوضع نفس الكمية من البضائع من نفس الخلايا المانحة في حاويات أخرى، حيث يكون لكل موضع تقديراته الخاصة حيث < и حيث >.
يتم طرح السؤال: ما هو الحد الأدنى للربح في الحجم مقبول، لقيمة خسارة زمنية معينة ؟ دعونا نشرح مع مثال. في البداية، كان من المفترض وضع البقايا في حاوية بحجم 1000 ديسم مكعب (3 م1) وكان وقت النقل 3 ثانية. هناك خيار لوضع البقايا في حاوية أخرى بحجم 70 ديسم مكعب ولمدة 500 ثانية. سؤال: هل نحن مستعدون لقضاء 3 ثانية إضافية من وقت صاحب المتجر في نقل البضائع من أجل توفير 130 ديسيمتر مكعب من الحجم الحر؟ استنادا إلى نتائج مسح موظفي المستودعات، تم تجميع المخطط التالي.
أرز. 5. رسم تخطيطي لاعتماد الحد الأدنى المسموح به من المدخرات في الحجم على زيادة الفرق في وقت التشغيل
وهذا هو، إذا كانت تكاليف الوقت الإضافي 40 ثانية، فنحن مستعدون لقضاءها فقط عندما يكون الربح في الحجم على الأقل 500 dm3. على الرغم من وجود عدم خطية طفيفة في الاعتماد، لتبسيط الحسابات الإضافية سنفترض أن الاعتماد بين الكميات خطي ويوصف بالمتباينة
في الشكل أدناه، نتناول الطرق التالية لوضع البضائع في الحاويات.
أرز. 6. الخيار (أ): حاويتين، الحجم الإجمالي 2 دسم400، الوقت الإجمالي 3 ثانية.
أرز. 6. الخيار (ب): حاويتين، الحجم الإجمالي 2 دسم600، الوقت الإجمالي 3 ثانية.
أرز. 6. الخيار (ج): حاوية واحدة، الحجم الإجمالي 1 دسم400، الوقت الإجمالي 3 ثانية.
الخيار (أ) لاختيار الحاويات أفضل من الخيار الأصلي، حيث أن المتراجحة تحمل: (800-400)/10>=150-120، مما يعني أن 40 >= 30. الخيار (ب) أقل تفضيلاً من الخيار الأصلي الخيار، نظرًا لأن المتراجحة لا تنطبق على: (800-600)/10>=190-150 مما يعني أن 20 >= 40. لكن الخيار (ج) لا يتناسب مع هذا المنطق! دعونا نفكر في هذا الخيار بمزيد من التفصيل. من ناحية، فإن المتباينة (800-400)/10>=200-120، مما يعني أن المتباينة 40 >= 80 غير راضية، مما يشير إلى أن المكاسب في الحجم لا تستحق مثل هذه الخسارة الكبيرة في الوقت المناسب.
ولكن من ناحية أخرى، في هذا الخيار (ج)، لا نقوم فقط بتقليل إجمالي الحجم المشغول، ولكن أيضًا تقليل عدد الخلايا المشغولة، وهو أول متطلبين مهمين للحلول القابلة للحساب للمشكلات المذكورة أعلاه. من الواضح أنه لكي يبدأ تحقيق هذا الشرط، من الضروري إضافة ثابت موجب إلى الجانب الأيسر من المتباينة ، ويجب إضافة مثل هذا الثابت فقط عندما يقل عدد الحاويات. دعونا نتذكر ذلك هو متغير يساوي 1 عندما تكون الحاوية المحدد، و0 عند الحاوية لم يتم اختياره. دعونا نشير - العديد من الحاويات في الحل الأولي و - العديد من الحاويات في الحل الجديد. بشكل عام، ستبدو عدم المساواة الجديدة كما يلي:
تحويل عدم المساواة أعلاه، نحصل على
وبناءً على ذلك، لدينا صيغة لحساب التكلفة الإجمالية بعض الحلول للمشكلة:
ولكن الآن يطرح السؤال: ما القيمة التي يجب أن يكون لها مثل هذا الثابت؟ ؟ من الواضح أن قيمتها يجب أن تكون كبيرة بما يكفي بحيث يتم دائمًا تلبية المطلب الأول لحل المشكلة. يمكنك، بالطبع، أن تأخذ قيمة الثابت تساوي 103 أو 106، لكنني أرغب في تجنب مثل هذه "الأرقام السحرية". إذا أخذنا في الاعتبار تفاصيل تنفيذ عمليات المستودع، فيمكننا حساب العديد من التقديرات العددية المبنية على أسس جيدة لقيمة هذا الثابت.
ودع - المسافة القصوى بين خلايا المستودعات لمنطقة واحدة ABC، تساوي في حالتنا 100 متر - الحد الأقصى لحجم خلية الحاوية في المستودع، يساوي في حالتنا 1000 ديسيمتر مكعب.
الطريقة الأولى لحساب القيمة . لنفكر في موقف حيث توجد حاويتان في الطبقة الأولى، حيث تكون البضائع موجودة بالفعل فعليًا، أي أنها هي نفسها خلايا مانحة، وتكلفة نقل البضائع إلى نفس الخلايا تساوي بشكل طبيعي 2. من الضروري العثور على مثل هذه القيمة للثابت ، حيث سيكون من المفيد دائمًا نقل بقايا الطعام من الحاوية 1 إلى الحاوية 2. استبدال القيم и في المتباينة المذكورة أعلاه نحصل على:
مما يلي
استبدال قيم متوسط الوقت لتنفيذ العمليات الأولية في الصيغة أعلاه نحصل عليها
الطريقة الثانية لحساب القيمة . دعونا نفكر في الوضع الذي يوجد فيه الخلايا المانحة التي من المقرر نقل البضائع منها إلى الحاوية 1. دعنا نشير إلى ذلك - المسافة من الخلية المانحة إلى الحاوية 1. توجد أيضًا الحاوية 2 التي تحتوي بالفعل على بضائع، وحجمها يسمح لك باستيعاب باقي البضائع الخلايا. للتبسيط، سنفترض أن حجم البضائع المنقولة من الخلايا المانحة إلى الحاويات هو نفسه ويساوي . مطلوب العثور على مثل هذه القيمة للثابت ، حيث يتم وضع جميع البقايا من ستكون الخلايا الموجودة في الحاوية 2 دائمًا أكثر ربحية من وضعها في حاويات مختلفة:
تحويل عدم المساواة التي نحصل عليها
من أجل "تعزيز" قيمة الكمية ، فلنفترض ذلك = 0. متوسط عدد الخلايا المشاركة عادة في إجراء ضغط أرصدة المستودعات هو 10. بالتعويض عن القيم المعروفة للكميات، نحصل على القيمة التالية للثابت
نحن نأخذ أكبر قيمة محسوبة لكل خيار، وستكون هذه هي قيمة الكمية لمعلمات المستودع المحددة. الآن، للاكتمال، دعونا نكتب صيغة حساب التكاليف الإجمالية لبعض الحلول الممكنة :
الآن، بعد كل شيء جهود جبارة من خلال تحويل البيانات المدخلة، يمكننا القول أن جميع البيانات المدخلة قد تم تحويلها إلى النموذج المطلوب وهي جاهزة للاستخدام في خوارزمية التحسين.
اختتام
كما تظهر الممارسة، غالبًا ما يتم الاستهانة بتعقيد وأهمية مرحلة إعداد وتحويل بيانات الإدخال للخوارزمية. في هذه المقالة، أولينا الكثير من الاهتمام على وجه التحديد لهذه المرحلة من أجل إظهار أن بيانات الإدخال عالية الجودة والمعدة بذكاء فقط هي التي يمكنها اتخاذ القرارات المحسوبة بواسطة الخوارزمية ذات قيمة حقيقية للعميل. نعم، كان هناك العديد من الاشتقاقات من الصيغ، لكننا حذرناك حتى قبل الكاتا :)
في المقالة التالية، سنصل أخيرًا إلى الغرض من المنشورين السابقين - خوارزمية تحسين منفصلة.
أعدت المقال
رومان شانجين، مبرمج قسم المشاريع،
شركة فيرست بت، تشيليابينسك
المصدر: www.habr.com