مشكلة التقسيم الصناعي

Question

نحن نتحدث عن مصنع المنتجات المعدنية.توجد آلة تقوم بتقطيع القضبان الحديدية الطويلة إلى أجزاء أصغر تُستخدم لاحقًا في صنع منتجات متنوعة.

على سبيل المثال، لدي متطلبات لإنتاج أشرطة بالطول والكمية التالية:2 قطعة من 248 مم ، 5 من 1150 مم ، 6 من 2843 مم ، 3 من 3621 ملم.

هذا هو إخراج التقسيم.

على جانب الإدخال ، لدي (مرة أخرى على سبيل المثال) 3 أشرطة من 2500 مم ، 2 قضبان من 5000 مم ، 6 أشرطة من 8000 مم و 3 أشرطة من 10000 مم.

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

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

هل لديك أي تلميحات؟

Answer 1

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

وكيفية حلها؟ بعد كنت قادرا على معرفة النموذج الذي سيكون من الأفضل أن يدعو بعض مختلطة حلالا البرمجة صحيح. ولقد استخدمت سابقا LPSolve 5.5

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

Answer 2

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

Answer 3

والبرمجة الخطية هي صديقك. انظر http://en.wikipedia.org/wiki/Linear_programming بشكل عام، وخصوصا، ، http://en.wikipedia.org/wiki/Linear_programming#Uses و < وأ href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" يختلط = "نوفولو noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms .

Answer 4

ويبدو أنها مماثلة لمشكلة حقيبة (أعرف أن تكون سيئة حقا) لقد وجدت هذا على DADS NIST (مرجعى) أسهل للوصول الى من ACM للدول غير الأعضاء في <أ href = "HTTP: //www.itl .nist.gov / div897 / sqg / الآباء / HTML / binpacking.html "يختلط =" نوفولو noreferrer "> بن التعبئة