توضح المقالة كيفية التنفيذ WMS-النظام، واجهنا الحاجة إلى حل مشكلة التجميع غير القياسية وما هي الخوارزميات التي استخدمناها لحلها. سنخبرك كيف طبقنا منهجًا علميًا منظمًا لحل المشكلة، وما هي الصعوبات التي واجهناها وما هي الدروس التي تعلمناها.
يبدأ هذا المنشور بسلسلة من المقالات التي نشارك فيها تجربتنا الناجحة في تنفيذ خوارزميات التحسين في عمليات المستودعات. الغرض من سلسلة المقالات هو تعريف الجمهور بأنواع مشاكل التحسين لعمليات المستودعات التي تنشأ في أي مستودع متوسط وكبير تقريبًا، وكذلك التحدث عن تجربتنا في حل مثل هذه المشكلات والمزالق التي واجهناها على طول الطريق . ستكون المقالات مفيدة لأولئك الذين يعملون في صناعة الخدمات اللوجستية للمستودعات، وتنفيذها WMS- الأنظمة، وكذلك المبرمجين المهتمين بتطبيقات الرياضيات في الأعمال التجارية وتحسين العمليات في المؤسسة.
اختناق في العمليات
في عام 2018، أكملنا مشروعًا للتنفيذ WMS-أنظمة في مستودع شركة "Trading House "LD" في تشيليابينسك. قمنا بتنفيذ منتج "1C-Logistics: Warehouse Management 3" لـ 20 مكان عمل: المشغلين WMS، أمناء المخازن، سائقي الرافعات الشوكية. يبلغ متوسط المستودع حوالي 4 آلاف م2، وعدد الخلايا 5000 وعدد وحدات SKU 4500. ويخزن المستودع الصمامات الكروية من إنتاجنا بأحجام مختلفة من 1 كجم إلى 400 كجم. يتم تخزين المخزون في المستودع على دفعات، نظرًا لوجود حاجة لتحديد البضائع وفقًا لنظام FIFO.
عند تصميم مخططات أتمتة عمليات المستودعات، واجهنا المشكلة الحالية المتمثلة في تخزين المخزون غير الأمثل. إن تفاصيل رافعات التخزين والتستيف هي أن خلية تخزين وحدة واحدة يمكن أن تحتوي فقط على عناصر من دفعة واحدة. تصل المنتجات إلى المستودع يوميا وكل وصول هو دفعة منفصلة. في المجمل، نتيجة لمدة شهر واحد من تشغيل المستودع، يتم إنشاء 1 دفعة منفصلة، على الرغم من ضرورة تخزين كل منها في خلية منفصلة. غالبًا ما يتم اختيار المنتجات ليس في منصات نقالة كاملة، ولكن على شكل قطع، ونتيجة لذلك، في منطقة اختيار القطعة في العديد من الخلايا، يتم ملاحظة الصورة التالية: في خلية يزيد حجمها عن 30 م 1 توجد عدة قطع من الرافعات التي تشغل أقل من 3-5% من حجم الخلية.
الشكل 1. صورة لعدة قطع من البضائع في الخلية
ومن الواضح أن سعة التخزين لا يتم استخدامها على النحو الأمثل. لتخيل حجم الكارثة، يمكنني تقديم أرقام: في المتوسط، هناك من 1 إلى 3 خلية من هذه الخلايا بحجم يزيد عن 100 متر مكعب مع أرصدة "ضئيلة" خلال فترات مختلفة من تشغيل المستودع. نظرًا لأن المستودع صغير نسبيًا، خلال مواسم ازدحام المستودعات، يصبح هذا العامل "عنق الزجاجة" ويبطئ عمليات المستودعات بشكل كبير.
فكرة حل المشكلة
نشأت فكرة: يجب تقليل دفعات بقايا الطعام ذات التواريخ الأقرب إلى دفعة واحدة، ويجب وضع بقايا الطعام ذات الدفعة الموحدة بشكل مضغوط معًا في خلية واحدة، أو في عدة خلايا، إذا لم يكن هناك مساحة كافية في خلية واحدة لاستيعاب كامل كمية بقايا الطعام.
الصورة 2. مخطط لضغط المخلفات في الخلايا
يتيح لك ذلك تقليل مساحة المستودع المشغولة بشكل كبير والتي سيتم استخدامها للبضائع الجديدة التي يتم وضعها. في الحالة التي تكون فيها سعة المستودع مثقلة، يكون هذا الإجراء ضروريا للغاية، وإلا فقد لا يكون هناك ببساطة مساحة حرة كافية لاستيعاب البضائع الجديدة، الأمر الذي سيؤدي إلى توقف عمليات وضع المستودعات وتجديدها. سابقا قبل التنفيذ WMS- قامت الأنظمة بهذه العملية يدوياً، وهي عملية غير فعالة، حيث أن عملية البحث عن البقايا المناسبة في الخلايا كانت طويلة جداً. الآن، مع تقديم نظام WMS، قررنا أتمتة العملية وتسريعها وجعلها ذكية.
تنقسم عملية حل مثل هذه المشكلة إلى مرحلتين:
- في المرحلة الأولى نجد مجموعات من الدفعات متقاربة في تاريخ الضغط؛
- في المرحلة الثانية، لكل مجموعة من الدفعات، نحسب الموضع الأكثر إحكاما للبضائع المتبقية في الخلايا.
سنركز في المقالة الحالية على المرحلة الأولى من الخوارزمية، ونترك تغطية المرحلة الثانية للمقالة التالية.
البحث عن نموذج رياضي للمشكلة
قبل أن نجلس لكتابة التعليمات البرمجية وإعادة اختراع العجلة، قررنا التعامل مع هذه المشكلة بشكل علمي، أي: صياغتها رياضيًا، واختزالها إلى مشكلة تحسين منفصلة معروفة واستخدام الخوارزميات الموجودة الفعالة لحلها، أو أخذ هذه الخوارزميات الموجودة كأساس وتعديلها لتتوافق مع تفاصيل المشكلة العملية التي يتم حلها.
نظرًا لأنه من الواضح أن صياغة الأعمال للمشكلة تترتب على أننا نتعامل مع المجموعات، فسوف نقوم بصياغة مثل هذه المشكلة من حيث نظرية المجموعات.
ودع – مجموعة كافة الدفعات المتبقية من منتج معين في المستودع. يترك - نظرا لثابت الأيام. يترك - مجموعة فرعية من الدُفعات، حيث لا يتجاوز الفرق في التواريخ لجميع أزواج الدُفعات في المجموعة الفرعية ثابتًا . نحن بحاجة إلى العثور على الحد الأدنى لعدد المجموعات الفرعية المنفصلة ، بحيث تكون جميع المجموعات الفرعية مجتمعة من شأنها أن تعطي الكثير .
بمعنى آخر، نحن بحاجة إلى إيجاد مجموعات أو مجموعات من الأطراف المتشابهة، حيث يتم تحديد معيار التشابه بالثابت . تذكرنا هذه المهمة بمشكلة التجميع المعروفة. من المهم أن نقول إن المشكلة قيد النظر تختلف عن مشكلة التجميع حيث أن مشكلتنا لها شرط محدد بدقة لمعيار تشابه عناصر المجموعة، والذي يحدده الثابت ولكن في مشكلة التجميع لا يوجد مثل هذا الشرط. يمكن العثور على بيان مشكلة التجميع والمعلومات حول هذه المشكلة
لذلك، تمكنا من صياغة المشكلة وإيجاد مشكلة كلاسيكية بصيغة مماثلة. والآن لا بد من النظر في الخوارزميات المعروفة لحلها، حتى لا نعيد اختراع العجلة، بل نأخذ أفضل الممارسات ونطبقها. لحل مشكلة التجميع، قمنا بدراسة الخوارزميات الأكثر شعبية، وهي: -وسائل - الوسائل، خوارزمية تحديد المكونات المتصلة، خوارزمية الشجرة الممتدة الدنيا. يمكن العثور على وصف وتحليل لهذه الخوارزميات
لحل مشكلتنا، خوارزميات التجميع - يعني و -الوسائل غير قابلة للتطبيق على الإطلاق، حيث أن عدد المجموعات غير معروف مسبقًا وهذه الخوارزميات لا تأخذ في الاعتبار قيد الأيام الثابتة. تم تجاهل مثل هذه الخوارزميات في البداية من الاعتبار.
لحل مشكلتنا، تعد خوارزمية تحديد المكونات المتصلة والحد الأدنى من خوارزمية الشجرة الممتدة أكثر ملاءمة، ولكن، كما اتضح، لا يمكن تطبيقها "مباشرة" على المشكلة التي يتم حلها والحصول على حل جيد. لشرح ذلك، دعونا نفكر في منطق تشغيل مثل هذه الخوارزميات فيما يتعلق بمشكلتنا.
النظر في الرسم البياني ، حيث تكون القمم هي مجموعة الأطراف ، والحافة بين القمم и له وزن يساوي فرق الأيام بين الدفعات и . في خوارزمية تحديد المكونات المتصلة، يتم تحديد معلمة الإدخال حيث ، وفي الرسم البياني تتم إزالة جميع الحواف التي يكون وزنها أكبر . يبقى فقط أقرب أزواج من الكائنات متصلة. الهدف من الخوارزمية هو تحديد مثل هذه القيمة ، حيث "يتفكك" الرسم البياني إلى عدة مكونات متصلة، حيث ستفي الأطراف التي تنتمي إلى هذه المكونات بمعيار التشابه الخاص بنا، والذي يحدده الثابت . المكونات الناتجة هي مجموعات.
يتم إنشاء خوارزمية الحد الأدنى للشجرة الممتدة أولاً على الرسم البياني الحد الأدنى من الشجرة الممتدة، ثم تتم إزالة الحواف ذات الوزن الأعلى بشكل تسلسلي حتى "يتفكك" الرسم البياني إلى عدة مكونات متصلة، حيث ستفي الأطراف التي تنتمي إلى هذه المكونات أيضًا بمعيار التشابه الخاص بنا. المكونات الناتجة ستكون مجموعات.
عند استخدام مثل هذه الخوارزميات لحل المشكلة قيد النظر، قد تنشأ حالة كما في الشكل 3.
الشكل 3. تطبيق خوارزميات التجميع على المشكلة التي يتم حلها
لنفترض أن الثابت لدينا للفرق بين أيام الدفعة هو 20 يومًا. رسم بياني تم تصويره في شكل مكاني لسهولة الإدراك البصري. أنتجت كلتا الخوارزميتين حلاً ثلاثي المجموعات، والذي يمكن تحسينه بسهولة من خلال الجمع بين الدُفعات الموضوعة في مجموعات منفصلة مع بعضها البعض! ومن الواضح أن مثل هذه الخوارزميات تحتاج إلى تعديل لتتناسب مع تفاصيل المشكلة التي يتم حلها، وتطبيقها في شكلها النقي لحل مشكلتنا سوف يعطي نتائج سيئة.
لذلك، قبل أن نبدأ في كتابة التعليمات البرمجية لخوارزميات الرسم البياني المعدلة لمهمتنا وإعادة اختراع دراجتنا الخاصة (التي يمكننا بالفعل تمييز الخطوط العريضة للعجلات المربعة في الصور الظلية لها)، قررنا مرة أخرى التعامل مع هذه المشكلة علميًا، وهي: حاول اختصارها إلى تحسين مشكلة منفصلة أخرى، على أمل إمكانية تطبيق الخوارزميات الحالية لحلها دون تعديلات.
لقد نجح بحث آخر عن مشكلة كلاسيكية مماثلة! لقد نجحنا في العثور على مشكلة تحسين منفصلة، تتطابق صياغتها 1 في 1 مع صياغة مشكلتنا. تبين أن هذه المهمة ضبط مشكلة التغطية. دعونا نقدم صياغة المشكلة فيما يتعلق بتفاصيلنا.
هناك مجموعة محدودة والأسرة لجميع مجموعاتها الفرعية المنفصلة من الأطراف، بحيث يكون الفرق في التواريخ لجميع أزواج الأطراف في كل مجموعة فرعية من العائلة لا يتجاوز الثوابت . الغطاء يسمى عائلة الأقل قوة، التي تنتمي إليها عناصرها ، بحيث يكون اتحاد المجموعات من العائلة يجب أن تعطي مجموعة من جميع الأطراف .
يمكن العثور على تحليل مفصل لهذه المشكلة и يمكن العثور على خيارات أخرى للتطبيق العملي لمشكلة التغطية وتعديلاتها
خوارزمية لحل المشكلة
لقد قررنا النموذج الرياضي للمشكلة التي يتعين حلها. الآن دعونا نلقي نظرة على الخوارزمية لحلها. مجموعات فرعية من العائلة يمكن العثور عليها بسهولة عن طريق الإجراء التالي.
- ترتيب دفعات من مجموعة بالترتيب التنازلي لتواريخهم.
- ابحث عن الحد الأدنى والحد الأقصى لتواريخ الدفعة.
- لكل يوم من الحد الأدنى للتاريخ إلى الحد الأقصى، ابحث عن جميع الدفعات التي تختلف تواريخها عن ليس أكثر من (لذلك القيمة من الأفضل أن تأخذ الرقم الزوجي).
منطق الإجراء لتشكيل عائلة من المجموعات في يتم عرض الأيام في الشكل 4.
الشكل 4. تشكيل مجموعات فرعية من الأحزاب
هذا الإجراء ليس ضروريا للجميع قم بمراجعة جميع الدفعات الأخرى وتحقق من الفرق في تواريخها أو من القيمة الحالية تحرك يسارًا أو يمينًا حتى تجد دفعة يختلف تاريخها عن بأكثر من نصف قيمة الثابت. جميع العناصر اللاحقة، عند التحرك إلى اليمين وإلى اليسار، لن تكون مثيرة للاهتمام بالنسبة لنا، لأن الفرق في الأيام سيزداد بالنسبة لهم فقط، حيث تم ترتيب العناصر الموجودة في المصفوفة في البداية. سيوفر هذا النهج الوقت بشكل كبير عندما يكون عدد الأطراف وانتشار مواعيدها كبيرًا بشكل ملحوظ.
مشكلة تغطية المجموعة هي -صعب، مما يعني عدم وجود خوارزمية سريعة (مع وقت تشغيل يساوي متعدد الحدود لبيانات الإدخال) وخوارزمية دقيقة لحلها. لذلك، لحل مشكلة تغطية المجموعة، تم اختيار خوارزمية جشعة سريعة، وهي بالطبع ليست دقيقة، ولكن لها المزايا التالية:
- بالنسبة للمشكلات الصغيرة الحجم (وهذه هي حالتنا بالضبط)، يتم حساب الحلول القريبة جدًا من الحل الأمثل. مع زيادة حجم المشكلة، تتدهور جودة الحل، ولكن ببطء شديد؛
- من السهل جدًا تنفيذه؛
- سريع، حيث أن تقدير وقت التشغيل هو .
تختار الخوارزمية الجشعة المجموعات بناءً على القاعدة التالية: في كل مرحلة، يتم تحديد مجموعة تغطي الحد الأقصى لعدد العناصر التي لم تتم تغطيتها بعد. يمكن العثور على وصف تفصيلي للخوارزمية والكود الكاذب الخاص بها
لم يتم إجراء مقارنة بين دقة هذه الخوارزمية الجشعة على بيانات الاختبار الخاصة بالمشكلة التي يتم حلها مع الخوارزميات المعروفة الأخرى، مثل الخوارزمية الجشعة الاحتمالية، وخوارزمية مستعمرة النمل، وما إلى ذلك. يمكن العثور على نتائج مقارنة هذه الخوارزميات بالبيانات العشوائية المولدة
تنفيذ وتنفيذ الخوارزمية
تم تنفيذ هذه الخوارزمية باللغة 1S وتم تضمينه في معالجة خارجية تسمى "Residue Compression" والتي تم توصيلها بها WMS-نظام. لم ننفذ الخوارزمية في اللغة C ++ واستخدامه من مكون أصلي خارجي، والذي سيكون أكثر صحة، لأن سرعة الكود أقل C + + مرات وفي بعض الأمثلة أسرع بعشرات المرات من سرعة التعليمات البرمجية المماثلة 1S. على اللسان 1S تم تنفيذ الخوارزمية لتوفير وقت التطوير وسهولة تصحيح الأخطاء في قاعدة الإنتاج الخاصة بالعميل. يتم عرض نتيجة الخوارزمية في الشكل 5.
الشكل 5. معالجة "ضغط" المخلفات
يوضح الشكل 5 أنه في المستودع المحدد، يتم تقسيم الأرصدة الحالية للبضائع في خلايا التخزين إلى مجموعات، تختلف فيها تواريخ دفعات البضائع عن بعضها البعض بما لا يزيد عن 30 يومًا. نظرًا لأن العميل يقوم بإنتاج وتخزين الصمامات الكروية المعدنية في المستودع، والتي يتم حساب مدة صلاحيتها بالسنوات، فيمكن إهمال هذا الاختلاف في التاريخ. لاحظ أن هذه المعالجة تُستخدم حاليًا بشكل منهجي في الإنتاج والمشغلين WMS تأكيد نوعية جيدة من التجمعات الحزبية.
الاستنتاجات والاستمرار
الخبرة الرئيسية التي اكتسبناها من حل مثل هذه المشكلة العملية هي تأكيد فعالية استخدام النموذج: الرياضيات. عرض المشكلة حصيرة الشهيرة. نموذج خوارزمية معروفة خوارزمية مع الأخذ بعين الاعتبار تفاصيل المشكلة. لقد كان التحسين المنفصل موجودًا منذ أكثر من 300 عام، وخلال هذا الوقت تمكن الناس من التفكير في الكثير من المشكلات وتجميع الكثير من الخبرة في حلها. بادئ ذي بدء، من الأفضل اللجوء إلى هذه التجربة، وعندها فقط ابدأ في إعادة اختراع العجلة.
في المقالة التالية، سنواصل قصة خوارزميات التحسين وننظر إلى الأكثر إثارة للاهتمام والأكثر تعقيدًا: خوارزمية "الضغط" الأمثل لبقايا الخلايا، والتي تستخدم البيانات الواردة من خوارزمية التجميع المجمعة كمدخلات.
أعدت المقال
رومان شانجين، مبرمج قسم المشاريع،
أول شركة BIT، تشيليابينسك
المصدر: www.habr.com