مشكلة تقليص المخزون

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

تستطيع آلة الورق إنتاج عدد غير محدود من اللفائف الرئيسية (الضخمة)،  يبلغ عرض كل منها 5600 مم. يجب قص العناصر الـ 13 التالية، الموضحة في الجدول أدناه.

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

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

عرض	#أغراض
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

حل

يوجد 308 نمطًا ممكنًا لهذه الحالة الصغيرة. يتطلب الحل الأمثل 73 لفة رئيسية مع نسبة هدر تبلغ 0.401%؛ ويمكن إثبات حسابيًا أن الحد الأدنى لعدد الأنماط مع هذا المستوى من الهدر هو 10. كما يمكن حساب وجود 19 حلًا مختلفًا، كل منها يحتوي على 10 أنماط ونسبة هدر تبلغ 0.401%، ويظهر أحد هذه الحلول أدناه وفي الصورة.

تكرار	محتويات
2	1820 + 1820 + 1820
3	1380 + 2150 + 1930
12	1380 + 2150 + 2050
7	1380 + 2100 + 2100
12	2200 + 1820 + 1560
8	2200 + 1520 + 1880
1	1520 + 1930 + 2150
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

يمكن تصنيف مشاكل تقطيع المواد الخام بعدة طرق. ^{[ 1 ]} إحدى هذه الطرق هي بُعد عملية التقطيع: يوضح المثال أعلاه مشكلة أحادية البُعد (1D)؛ وتظهر تطبيقات صناعية أخرى للمشكلة أحادية البُعد عند تقطيع الأنابيب والكابلات وقضبان الصلب. أما المشاكل ثنائية البُعد (2D) فتُصادف في صناعة الأثاث والملابس والزجاج. وعندما يكون شكل المنتج الرئيسي أو الأجزاء المطلوبة غير منتظم (وهو وضع شائع في صناعات الجلود والمنسوجات والمعادن)، يُشار إلى هذه الحالة بمشكلة التداخل .

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

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

• تُصنع هذه العملية على مرحلتين، حيث تُعالج اللفائف المنتجة في المرحلة الأولى مرة ثانية. على سبيل المثال، تُصنع جميع القرطاسية المكتبية (مثل مقاس A4 في أوروبا، ومقاس Letter في الولايات المتحدة) بهذه الطريقة. تكمن الصعوبة في أن آلات المرحلة الثانية أضيق من آلات المرحلة الأولى. يُعد الاستخدام الأمثل لكلا مرحلتي الإنتاج أمرًا بالغ الأهمية (من منظور استهلاك الطاقة والمواد)، وما يُعد فعالًا في المرحلة الأولى قد يكون غير فعال في المرحلة الثانية، مما يؤدي إلى مفاضلات. يُعد الفيلم المعدني (المستخدم في تغليف الوجبات الخفيفة)، وبثق البلاستيك على الورق (المستخدم في تغليف السوائل ، مثل علب العصير) أمثلة أخرى على هذه العملية.
• قيود اللفّ حيث تخضع عملية التقطيع لقيود مادية أو منطقية: من القيود الشائعة جدًا أن عدد سكاكين التقطيع المتاحة محدود، بحيث لا تتجاوز الأنماط الممكنة عددًا أقصى من اللفات. ونظرًا لعدم توحيد معايير آلات اللفّ، تظهر قيود أخرى كثيرة.
• ومن الأمثلة على متطلبات العميل عندما لا يمكن تلبية طلب معين من أي من موضعي الحافة: وذلك لأن حواف الصفيحة تميل إلى أن يكون لها اختلافات أكبر في السماكة، ويمكن أن تكون بعض التطبيقات حساسة للغاية لهذه الاختلافات.
• من أمثلة مشاكل الجودة وجود عيوب في اللفة الرئيسية تستدعي قصها. يجب تحسين استخدام المواد باهظة الثمن ذات خصائص الجودة العالية، مثل ورق التصوير الفوتوغرافي أو التايفك، بعناية فائقة لتقليل المساحة المهدرة إلى أدنى حد.
• تنشأ مشاكل تعدد الآلات عندما يمكن إنتاج الطلبات على أكثر من آلة، وتختلف هذه الآلات في عرضها. عمومًا، يُحسّن توفر أكثر من عرض واحد للأسطوانة الرئيسية من تقليل الهدر بشكل ملحوظ؛ ولكن عمليًا، قد يلزم مراعاة قيود إضافية لتقسيم الطلبات.
• توجد أيضًا مشكلة شبه مستمرة، حيث لا يشترط أن تكون اللفائف المنتجة بنفس القطر، بل يمكن أن تختلف ضمن نطاق معين. يحدث هذا عادةً مع طلبات الألواح. تُعرف هذه المشكلة أحيانًا باسم مشكلة البعد ونصف . يظهر هذا النوع أيضًا في إنتاج الورق المقوى المموج ، حيث يُطلق عليه، بشكلٍ مُربك نوعًا ما، مشكلة جدولة آلة التمويج .
• نظراً لأن بعض آلات صناعة الورق ضيقة نسبياً مقارنةً بالمنتجات المطلوبة، فقد استثمرت بعض الشركات في عملية ثانوية تُعرف باسم " التشذيب " (أو "لحام اللفائف ")، حيث يتم فيها وصل بكرتين (ناتجتين عن شق البكرات الكبيرة الأصلية) جنباً إلى جنب (مع تداخل بسيط) لتكوين لفة أعرض. ويؤدي إنتاج بكرات أضيق في العملية الأساسية إلى تقليل الفاقد الإجمالي. ^{[ 2 ]}
• في صناعة المعادن، يتمثل أحد الاختلافات الرئيسية في أن اللفائف الرئيسية تُنتج عادةً في وقت مبكر، وتختلف عمومًا عن بعضها البعض (من حيث العرض والطول). ولذلك، توجد أوجه تشابه مع مشكلة الآلات المتعددة المذكورة سابقًا. ويُؤدي وجود اختلافات في الطول إلى مشكلة ثنائية الأبعاد، لأن الهدر قد يحدث في كل من العرض والطول.
• تُعدّ مسألة المقصلة مسألة ثنائية الأبعاد أخرى تتمثل في تقطيع الصفائح إلى مستطيلات بأحجام محددة، ولكن يُسمح فقط بالقطع التي تمتد على كامل عرض كل صفيحة. ويمكن إيجاد تطبيقات صناعية لهذه المسألة في صناعة الزجاج.

• تُعرف مشكلة تقطيع المخزون، والمتمثلة في تحديد أفضل حجم رئيسي يلبي الطلب المحدد في الحالة أحادية البعد، بمشكلة التشكيلة . ^{[ 3 ]}

صاغ كانتوروفيتش مسألة مخزون القطع لأول مرة عام 1939. ^{[ 4 ]} وفي عام 1951، قبل انتشار الحواسيب على نطاق واسع، اقترح كل من ل. ف. كانتوروفيتش وف. أ. زالغالر ^{[ 5 ]} حل مشكلة الاستخدام الأمثل للمواد في مرحلة القطع باستخدام البرمجة الخطية. عُرفت التقنية المقترحة لاحقًا باسم طريقة توليد الأعمدة .

تبدأ الصيغة القياسية لمسألة تقطيع المخزون (ولكنها ليست الصيغة الوحيدة) بقائمة من m طلب، يتطلب كل منها${\displaystyle q_{j}}$قطع، حيث${\displaystyle j=1,\ldots ,m}$ثم نقوم بإنشاء قائمة بجميع التوليفات الممكنة للقطع (والتي تسمى غالبًا "الأنماط" أو "التكوينات"). ليكن${\displaystyle C}$ليكن عدد تلك الأنماط. نربط بكل نمط متغيرًا صحيحًا موجبًا${\displaystyle x_{i}}$، مما يمثل عدد مرات تكرار النمط${\displaystyle i}$يُستخدم، حيث${\displaystyle i=1,\ldots ,C}$إذن، يكون برنامج الأعداد الصحيحة الخطي كما يلي:

${\displaystyle \min \sum _{i=1}^{C}c_{i}x_{i}}$

${\displaystyle {\text{st}}\sum _{i=1}^{C}a_{ij}x_{i}\geq q_{j},\quad \quad \forall j=1,\dots ,m}$

${\displaystyle x_{i}\geq 0}$عدد صحيح

أين${\displaystyle a_{ij}}$عدد مرات الطلب${\displaystyle j}$يظهر في النمط${\displaystyle i}$و${\displaystyle c_{i}}$تكلفة (غالباً ما تكون هدراً) النمط${\displaystyle i}$قد تؤدي طبيعة قيود الكمية الدقيقة إلى خصائص رياضية مختلفة بشكل طفيف. قيود الكمية في الصيغة المذكورة أعلاه هي قيود دنيا (يجب إنتاج الكمية المحددة على الأقل من كل طلب، وربما أكثر).

متى${\displaystyle c_{i}=1}$، الهدف هو تقليل عدد العناصر الرئيسية المستخدمة، وإذا تم استبدال قيد الكمية المراد إنتاجها بالمساواة، فإنه يسمى مشكلة تعبئة الصناديق .

الصيغة الأكثر عمومية لها قيود ثنائية الجانب (وفي هذه الحالة قد يستهلك حل الحد الأدنى من النفايات أكثر من الحد الأدنى لعدد العناصر الرئيسية):

${\displaystyle q_{j}\leq \sum _{i=1}^{n}a_{ij}x_{i}\leq Q_{j},\quad \quad \forall j=1,\dots ,m}$

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

بشكل عام، يزداد عدد الأنماط الممكنة بشكل أُسّي كدالة لعدد الطلبات (m) . ومع ازدياد عدد الطلبات، قد يصبح من غير العملي حصر جميع أنماط القطع الممكنة.

يستخدم نهج بديل توليد الأعمدة المؤجل . تحل هذه الطريقة مشكلة تقطيع المخزون بالبدء ببضعة أنماط فقط، ثم تولد أنماطًا إضافية عند الحاجة. في الحالة أحادية البعد، تُضاف الأنماط الجديدة بحل مسألة تحسين مساعدة تُسمى مسألة حقيبة الظهر ، باستخدام معلومات المتغير المزدوج من البرنامج الخطي . توجد طرق معروفة لحل مسألة حقيبة الظهر، مثل التفرع والتقييد والبرمجة الديناميكية . يمكن أن تكون طريقة توليد الأعمدة المؤجل أكثر كفاءة من الطريقة الأصلية، خاصةً مع ازدياد حجم المسألة. وقد طوّر جيلمور وجوموري نهج توليد الأعمدة المطبق على مشكلة تقطيع المخزون في سلسلة من الأبحاث المنشورة في ستينيات القرن الماضي. ^{[ 6 ] [ 7 ]} أثبت جيلمور وجوموري أن هذا النهج يضمن التقارب نحو الحل الأمثل (الجزئي)، دون الحاجة إلى حصر جميع الأنماط الممكنة مسبقًا.

من عيوب طريقة جيلمور وجوموري الأصلية أنها لا تتعامل مع الأعداد الصحيحة، لذا قد يحتوي الحل على كسور، مثلاً، يجب إنتاج نمط معين 3.67 مرة. غالباً ما لا يُجدي التقريب لأقرب عدد صحيح، إذ قد يؤدي إلى حل دون المستوى الأمثل و/أو إنتاج بعض الطلبات بكميات أقل أو أكثر من اللازم (وربما عدم جدوى الحل في حال وجود قيود على الطلب من كلا الجانبين). يتم التغلب على هذا القيد في الخوارزميات الحديثة، التي تستطيع حل مسائل كبيرة جداً (أكبر عموماً من تلك التي تُصادف في الواقع العملي ^{[ 8 ] [ 9 ]} ) وصولاً إلى الحل الأمثل (بمعنى إيجاد حلول بأقل قدر من الهدر).

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

• مشكلة الحد الأدنى لعدد الأنماط: إيجاد حل بأقل عدد من الأنماط ضمن حلول الحد الأدنى من الهدر. تُعدّ هذه مشكلة بالغة الصعوبة، حتى مع معرفة الهدر. ^{[ 10 ] [ 11 ] [ 12 ]} هناك فرضية مفادها أن أي حالة أحادية البعد مقيدة بالمساواة، ذات n حجمًا، لها على الأقل حل واحد بأقل هدر، لا يتجاوز عدد أنماطه n + 1. وقد دُحضت هذه الفرضية لأول مرة في أبريل 2020 بمثال ذي 9 أحجام يتطلب 11 نمطًا. ^{[ 13 ]}
• مشكلة الحد الأدنى من المكدس: تتعلق هذه المشكلة بترتيب الأنماط بحيث لا يكون هناك عدد كبير جدًا من الطلبات غير المكتملة في أي وقت. وقد ظلت هذه المشكلة مفتوحة حتى عام 2007، عندما نُشرت خوارزمية فعالة تعتمد على البرمجة الديناميكية. ^{[ 14 ]}
• مسألة الحد الأدنى لعدد تغييرات السكاكين (للمسألة أحادية البعد): تتعلق هذه المسألة بترتيب الأنماط وتبديلها لتقليل عدد مرات تحريك سكاكين القطع. وهي حالة خاصة من مسألة البائع المتجول المعممة .

• تعبئة الصناديق ذات التعددية العالية
• برنامج التكوين الخطي

• شفاتال، ف. (1983). البرمجة الخطية . دبليو إتش فريمان. رقم ISBN 978-0-7167-1587-0.
• حاتم بن عمر، جي إم فاليريو دي كارفاليو، مشاكل قطع المخزون في توليد الأعمدة، حرره جاي ديساولنييه، جاك ديروسير، وماريوس إم سولومون، سبرينغر، 2005، XVI، ISBN 0-387-25485-4
• م. ديلورم، م. إيوري، س. مارتيلو، مشاكل تعبئة الصناديق وتقطيع المخزون: نماذج رياضية وخوارزميات دقيقة ، المجلة الأوروبية لبحوث العمليات 2016، 255، 1-20، doi : 10.1016/j.ejor.2016.04.030