حساب قائمة القطع بأقل كمية من النفايات المقطوعة

Question

أنا أعمل في مشروع حيث أقوم بإنتاج قائمة قطع الألمنيوم.

تأتي سحبات الألمنيوم بأطوال 5 أمتار.

لدي قائمة بالأطوال الأصغر التي يجب قطعها من أطوال 5 أمتار من سحب الألمنيوم.

يجب قطع الأطوال الأصغر بالترتيب الذي ينتج عنه أقل كمية من النفايات المقطوعة من أطوال 5 أمتار من سحب الألمنيوم.

أقوم حاليًا بطلب قائمة القطع بطريقة يتم فيها قطع الأطوال الأصغر بشكل عام أولاً والأقصر من الأطوال الأصغر يتم قطعه أخيرًا.الاستثناء لهذه القاعدة هو عندما لا يتناسب الطول الأقصر مع ما تبقى من طول 5 أمتار من سحب الألومنيوم، فإنني أستخدم أطول طول أقصر يناسب.

يبدو أن هذا ينتج قائمة قطع فعالة للغاية (قليل جدًا من النفايات المقطوعة) ولا يستغرق حسابها وقتًا طويلاً.ومع ذلك، أتصور أنه على الرغم من أن قائمة القطع موجودة جداً كفاءة، فإنه ليس بالضرورة معظم فعال.

هل يعرف أحد طريقة لحساب قائمة القطع الأكثر كفاءة والتي يمكن حسابها في فترة زمنية معقولة؟

يحرر:شكرًا على الإجابات، سأستمر في استخدام النهج "الجشع" حيث يبدو أنه يقوم بعمل جيد جدًا (ينفذ أي محاولات بشرية لإنشاء قائمة قطع فعالة) وهو سريع جدًا.

Answer 1

هذه مشكلة كلاسيكية يصعب حلها بكفاءة.الخوارزمية التي تصفها تبدو وكأنها خوارزمية الجشع.ألق نظرة على مقالة ويكيبيديا هذه لمزيد من المعلومات: مشكلة قطع المخزون

Answer 2

أخشى أنه لا توجد أفكار محددة حول هذه المشكلة - ولكن يمكنك البحث في "الخوارزمية الجينية"(الذي سوف يذهب شئ ما مثله)...

ضع الأطوال المراد قطعها بترتيب عشوائي وأعط هذا الطلب درجة بناءً على مدى جودة تطابقه مع الحل المثالي (0٪ هدر، على الأرجح).

ثم قم بإجراء تعديلات عشوائية بشكل متكرر على الترتيب وأعد تسجيله.إذا كانت النتيجة أعلى، والتخلص من النتيجة.إذا كانت النتيجة أقل، احتفظ بها واستخدمها كأساس لحسابك التالي.استمر حتى تحصل على درجاتك ضمن الحدود المقبولة.

Answer 3

ما وصفته يصنف بالفعل على أنه أ قطع المخزون مشكلة، كما حركة بهلوانية بالدراجة المذكور، وليس أ بن التعبئة المشكلة لأنك تحاول تقليل النفايات (مجموع بقايا الطعام) بدلاً من عدد عمليات البثق المستخدمة.

قد يكون من الصعب جدًا حل هاتين المشكلتين، ولكن من المرجح أن تمنحك خوارزمية "الأفضل ملاءمة" التي ذكرتها (باستخدام أطول "طول صغير" يناسب البثق الحالي) إجابات جيدة جدًا وبتعقيد منخفض جدًا.

Answer 4

في الواقع، نظرًا لأن حجم المادة ثابت، ولكن الطلبات ليست كذلك، فهذه مشكلة في تعبئة الصناديق.

مرة أخرى، ويكيبيديا للإنقاذ!

(شيء قد أضطر إلى البحث عنه في العمل أيضًا، لذا حسنًا!)

Answer 5

هذه مشكلة مثيرة للاهتمام لأنني أفترض أنها تعتمد على كمية كل طول تقوم بإنتاجه.إذا كانت جميعها بنفس الكمية ويمكنك الحصول على كل طول مختلف في قذف واحد بطول 5 أمتار، فلديك الحل الأمثل.

ومع ذلك، إذا لم تتناسب جميعها مع قذف واحد، فستكون لديك مشكلة أكبر.للحفاظ على نفس القدر من القطع لكل طول، تحتاج إلى حساب عدد الأطوال (ليس بالضرورة بالترتيب) التي يمكن احتواؤها على قذف واحد ثم ترتيب كل قذف.

Answer 6

لقد كنت أعاني من هذه المشكلة بالضبط (طول مشكلتي هو 6 أمتار) هنا أيضًا.

الحل الذي أعمل عليه قبيح بعض الشيء، لكنني لا أقبل الحل الذي تقدمه.دعني أشرح:

حجم المخزون 5 م

يحتاج إلى قطع الأحجام (1 من كل):

**3,5

1

1,5**

الحل الخاص بك:

3,5 | 1 مع هدر 0,5

1,5 مع ما تبقى من 3,5

ترى المشكلة؟

الحل الذي أعمل عليه -> القوة الغاشمة

1- اختبر كل الحلول الممكنة

2- ترتيب الحل بواسطة نفاياتهم

3- اختيار الحل الأمثل

4- قم بإزالة العناصر الموجودة في الحل من "الكون"

5 - انتقل إلى 1

أعلم أن الأمر يستغرق وقتًا طويلاً (لكنني أستغرق ساعة و 30 دقيقة لتناول طعام الغداء ...لذا...:))

أنا حقًا بحاجة إلى الحل الأمثل (أقوم بالحل الأمثل تقريبًا يدويًا (+-) في Excel) ليس فقط لأنني مهووس ولكن أيضًا المنتج ليس رخيصًا.

إذا كان لدى أي شخص حل أفضل وسهل فأنا أحبه