مشكلة تعبئة الصناديق

تُعدّ مسألة تعبئة الصناديق ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} مسألة تحسين ، حيث يجب تعبئة عناصر بأحجام مختلفة في عدد محدود من الصناديق أو الحاويات، لكل منها سعة محددة، بطريقة تُقلّل عدد الصناديق المستخدمة. لهذه المسألة تطبيقات عديدة، مثل تعبئة الحاويات، وتحميل الشاحنات مع مراعاة قيود سعة الوزن، وإنشاء نسخ احتياطية للملفات على الوسائط، وتقسيم بادئة الشبكة إلى شبكات فرعية متعددة، ^{[ 5 ]} ورسم خرائط التكنولوجيا في تصميم رقائق أشباه الموصلات FPGA .

من الناحية الحسابية، تُصنف هذه المسألة ضمن مسائل NP-hard ، وتُصنف مسألة القرار المقابلة لها ، والمتمثلة في تحديد ما إذا كان بالإمكان وضع العناصر في عدد محدد من الصناديق، ضمن مسائل NP-complete . على الرغم من صعوبتها في أسوأ الحالات، إلا أنه يمكن إيجاد حلول مثلى لحالات كبيرة جدًا من هذه المسألة باستخدام خوارزميات متطورة. إضافةً إلى ذلك، توجد العديد من خوارزميات التقريب . على سبيل المثال، توفر خوارزمية "الأولى المناسبة" حلاً سريعًا ولكنه غالبًا ما يكون غير مثالي، حيث تتضمن وضع كل عنصر في أول صندوق يناسبه. تتطلب هذه الخوارزمية زمنًا قدره Θ ( n  log n )، حيث n هو عدد العناصر المراد تعبئتها. يمكن تحسين فعالية الخوارزمية بشكل كبير من خلال فرز قائمة العناصر أولًا بترتيب تنازلي (تُعرف أحيانًا بخوارزمية "الأولى المناسبة التنازلية")، على الرغم من أن هذا لا يضمن بالضرورة الحصول على حل أمثل، وقد يزيد من زمن تشغيل الخوارزمية في حالة القوائم الطويلة. ومع ذلك، من المعروف أنه يوجد دائمًا ترتيب واحد على الأقل للعناصر يسمح لخوارزمية "الأولى المناسبة" بإنتاج حل أمثل. ^{[ 6 ]} 

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

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

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

في كتاب "الحاسوب والاستعصاء" ^{[ 8 ] : 226،} يدرج غاري وجونسون مسألة تعبئة الصناديق تحت المرجع [SR1]. ويعرّفان متغير القرار الخاص بها على النحو التالي.

مثال: مجموعة منتهية${\displaystyle I}$من العناصر، حجم${\displaystyle s(i)\in \mathbb {Z} ^{+}}$لكل${\displaystyle i\in I}$، سعة صندوق عدد صحيح موجب${\displaystyle B}$وعدد صحيح موجب${\displaystyle K}$.

السؤال: هل يوجد تقسيم لـ${\displaystyle I}$إلى مجموعات منفصلة${\displaystyle I_{1},\dots ,I_{K}}$بحيث يكون مجموع أحجام العناصر في كل${\displaystyle I_{j}}$يكون${\displaystyle B}$أو أقل؟

تجدر الإشارة إلى أنه في الأدبيات غالباً ما يتم استخدام تدوين بديل، ولكنه ليس مكافئاً، حيث${\displaystyle B=1}$و${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$لكل${\displaystyle i\in I}$علاوة على ذلك، يهتم البحث في الغالب بصيغة التحسين، التي تطلب أصغر قيمة ممكنة لـ${\displaystyle K}$يكون الحل أمثل إذا كان له أقل قدر من${\displaystyle K}$. ال${\displaystyle K}$قيمة سالبة للحل الأمثل لمجموعة من العناصر${\displaystyle I}$يُرمز إليه بـ${\displaystyle \mathrm {OPT} (I)}$أو فقط${\displaystyle \mathrm {OPT} }$إذا كانت مجموعة العناصر واضحة من السياق.

إحدى الصياغات الممكنة للمسألة باستخدام البرمجة الخطية الصحيحة هي:

تقليل${\displaystyle K=\sum _{j=1}^{n}y_{j}}$
رهناً بـ	${\displaystyle K\geq 1,}$
	${\displaystyle \sum _{i\in I}s(i)x_{ij}\leq By_{j},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle \sum _{j=1}^{n}x_{ij}=1,}$	${\displaystyle \forall i\in I}$
	${\displaystyle y_{j}\in \{0,1\},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\},}$	${\displaystyle \forall i\in I\,\forall j\in \{1,\ldots ,n\}}$

أين${\displaystyle y_{j}=1}$إذا كان ثنائيًا${\displaystyle j}$يتم استخدامه و${\displaystyle x_{ij}=1}$إذا كان العنصر${\displaystyle i}$يتم وضعها في سلة المهملات${\displaystyle j}$[ ^{9 ]​}

تُعتبر مسألة تعبئة الصناديق مسألةً كاملةً من فئة NP . ويمكن إثبات ذلك عن طريق اختزال مسألة التقسيم الثلاثي الكاملة من فئة NP إلى مسألة تعبئة الصناديق. ^{[ 8 ]}

علاوة على ذلك، لا يمكن أن توجد خوارزمية تقريبية بنسبة تقريب مطلقة أصغر من${\displaystyle {\tfrac {3}{2}}}$إلا إذا${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$يمكن إثبات ذلك عن طريق اختزال من مسألة التقسيم : ^{[ 10 ]} بالنظر إلى حالة من مسائل التقسيم حيث يكون مجموع جميع الأرقام المدخلة هو${\displaystyle 2T}$قم بإنشاء نموذج لخوارزمية تعبئة الصناديق حيث يكون حجم الصندوق T. إذا وُجد تقسيم متساوٍ للمدخلات، فإن التعبئة المثلى تتطلب صندوقين؛ لذا، يجب أن تُرجع كل خوارزمية بنسبة تقريب أقل من 3/2 أقل من 3 صناديق، أي صندوقين. في المقابل، إذا لم يكن هناك تقسيم متساوٍ للمدخلات، فإن التعبئة المثلى تتطلب 3 صناديق على الأقل.

من ناحية أخرى، يمكن حل مسألة تعبئة الصناديق في وقت ^شبه متعدد الحدود لأي عدد ثابت من الصناديق K ، ويمكن حلها في وقت متعدد الحدود لأي سعة صندوق ثابتة B. ^{[ 8} ]

لقياس أداء خوارزمية التقريب، هناك نسبتان للتقريب تم أخذهما في الاعتبار في الأدبيات. بالنسبة لقائمة معينة من العناصر${\displaystyle L}$الرقم${\displaystyle A(L)}$يشير إلى عدد الخانات المستخدمة عند استخدام الخوارزمية${\displaystyle A}$يتم تطبيقه على القائمة${\displaystyle L}$، بينما${\displaystyle \mathrm {OPT} (L)}$يشير إلى العدد الأمثل لهذه القائمة. نسبة الأداء في أسوأ الحالات المطلقة${\displaystyle R_{A}}$لخوارزمية${\displaystyle A}$يُعرَّف بأنه

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.}$

من ناحية أخرى، نسبة أسوأ الحالات التقاربية${\displaystyle R_{A}^{\infty }}$يُعرَّف بأنه

${\displaystyle R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.}$

وبعبارة أخرى،${\displaystyle R_{A}^{\infty }}$هو أصغر عدد بحيث يوجد ثابت K، بحيث يكون لجميع القوائم L: ^{[ 4 ]}

${\displaystyle A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K}$.

بالإضافة إلى ذلك، يمكن حصر القوائم بتلك التي يكون حجم جميع عناصرها على الأكثر${\displaystyle \alpha }$بالنسبة لهذه القوائم، يُشار إلى نسب الأداء ذات الحجم المحدود بـ${\displaystyle R_{A}({\text{size}}\leq \alpha )}$و${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )}$.

يمكن تصنيف خوارزميات التقريب لتعبئة الصناديق إلى فئتين:

1. تعتمد هذه الطرق الاستدلالية على الإنترنت على ترتيب العناصر ووضعها واحدة تلو الأخرى داخل الصناديق. كما يمكن تطبيق هذه الطرق الاستدلالية على النسخة غير المتصلة بالإنترنت من هذه المشكلة.
2. تُعدّ الطرق الاستدلالية غير المتصلة بالإنترنت، التي تُعدّل قائمة العناصر المُعطاة، على سبيل المثال عن طريق فرز العناصر حسب الحجم، غير قابلة للتطبيق على النسخة المتصلة بالإنترنت من هذه المشكلة. ومع ذلك، فإنها تتمتع بضمان تقريب مُحسّن مع الحفاظ على ميزة انخفاض تعقيدها الزمني. ومن بين الفئات الفرعية للطرق الاستدلالية غير المتصلة بالإنترنت، مخططات التقريب التقاربي. تتمتع هذه الخوارزميات بضمان تقريب من الشكل التالي:${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$بالنسبة لثابت ما قد يعتمد على${\displaystyle 1/\varepsilon }$. لحجم كبير بشكل تعسفي${\displaystyle \mathrm {OPT} (L)}$تقترب هذه الخوارزميات بشكل تعسفي من${\displaystyle \mathrm {OPT} (L)}$ومع ذلك، فإن هذا يأتي على حساب زيادة (كبيرة) في تعقيد الوقت مقارنة بالأساليب الاستدلالية.

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

جدول المقارنة

الخوارزمية	ضمان التقريب	قائمة أسوأ الحالات${\displaystyle L}$	التعقيد الزمني
اللياقة التالية (NF)	${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$[ 11 ]	${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$[ 11 ]	${\displaystyle {\mathcal {O}}(|L|)}$
اللياقة البدنية الأولية (FF)	${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$[ 13 ]	${\displaystyle FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$[ 13 ]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[ 11 ]
الأنسب (BF)	${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$[ 14 ]	${\displaystyle BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$[ 14 ]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[ 11 ]
أسوأ ملاءمة (WF)	${\displaystyle WF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$[ 11 ]	${\displaystyle WF(L)=2\cdot \mathrm {OPT} (L)-2}$[ 11 ]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[ 11 ]
شبه أسوأ ملاءمة (AWF)	${\displaystyle R_{AWF}^{\infty }\leq 17/10}$[ 11 ]	${\displaystyle R_{AWF}^{\infty }=17/10}$[ 11 ]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[ 11 ]
Refined-First-Fit (RFF)	${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$[ 15 ]	${\displaystyle RFF(L)=(5/3)\mathrm {OPT} (L)+1/3}$(ل${\displaystyle \mathrm {OPT} (L)=6k+1}$) [ 15 ]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[ 15 ]
التوافقي-ك (Hk)	${\displaystyle R_{Hk}^{\infty }\leq 1.69103}$ل${\displaystyle k\rightarrow \infty }$[ 16 ]	${\displaystyle R_{Hk}^{\infty }\geq 1.69103}$[ 16 ]	${\displaystyle {\mathcal {O}}(|L|\log(|L|)}$[ 16 ]
التوافقيات المحسّنة (RH)	${\displaystyle R_{RH}^{\infty }\leq 373/228\approx 1.63597}$[ 16 ]		${\displaystyle {\mathcal {O}}(|L|)}$[ 16 ]
التوافقي المعدل (MH)	${\displaystyle R_{MH}^{\infty }\leq 538/33\approx 1.61562}$[ 21 ]
التوافقي المعدل 2 (MH2)	${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217}$[ 21 ]
التوافقي + 1 (H+1)		${\displaystyle R_{H+1}^{\infty }\geq 1.59217}$[ 22 ]
التوافقي ++ (H++)	${\displaystyle R_{H++}^{\infty }\leq 1.58889}$[ 22 ]	${\displaystyle R_{H++}^{\infty }\geq 1.58333}$[ 22 ]

في النسخة غير المتصلة بالإنترنت من عملية تعبئة الصناديق، يمكن للخوارزمية رؤية جميع العناصر قبل البدء في وضعها في الصناديق. وهذا يسمح بتحقيق نسب تقريب محسّنة.

جدول المقارنة

الخوارزمية	ضمان التقريب	أسوأ سيناريو
خوارزمية التناقص التدريجي للتوافق الأول (FFD)	${\displaystyle \mathrm {FFD} (I)\leq {\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$[ 23 ]	${\displaystyle \mathrm {FFD} (I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$[ 23 ]
خوارزمية التناقص التدريجي المعدلة (MFFD)	${\displaystyle \mathrm {MFFD} (I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$[ 28 ]	${\displaystyle R_{\mathrm {MFFD} }^{\infty }\geq {\frac {71}{60}}}$[ 27 ]
كارماركار وكارب	${\displaystyle \mathrm {KK} (I)\leq \mathrm {OPT} (I)+O(\log ^{2}{\mathrm {OPT} (I)})}$[ 33 ]
روثفوس	${\displaystyle \mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)}\log \log {\mathrm {OPT} (I)})}$[ 31 ]
هوبرغ وروثفوس	${\displaystyle \mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)})}$[ 32 ]

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

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

هناك نوع مختلف من تعبئة الصناديق حيث توجد قيود على عدد العناصر في الصناديق: يمكن أن يحتوي كل صندوق على k عنصر على الأكثر، لعدد صحيح ثابت k .

• قدّم كراوس وشين وشويتمان ^{[ 46 ]} هذه المشكلة كنوع من أنواع جدولة المهام المثلى : جهاز كمبيوتر مزود بـ k معالج. هناك n مهمة تستغرق وحدة زمنية واحدة (1)، ولكن بمتطلبات ذاكرة مختلفة. تُعتبر كل وحدة زمنية بمثابة خانة واحدة. الهدف هو استخدام أقل عدد ممكن من الخانات (الوحدات الزمنية)، مع ضمان تشغيل k مهمة على الأكثر في كل خانة. وقدّموا عدة خوارزميات استدلالية لإيجاد حل باستخدام عدد لا يتجاوز k مهمة.${\displaystyle 2\mathrm {OPT} }$صناديق القمامة.
• يقدم كيليرر وبفيرشي ^{[ 47 ]} خوارزمية ذات وقت تشغيل${\displaystyle O(n^{2}\log {n})}$، الذي يجد حلاً بحد أقصى${\displaystyle \left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil }$صناديق. تقوم خوارزميتهم بإجراء بحث ثنائي عن الخيار الأمثل. لكل قيمة m يتم البحث عنها ، تحاول تعبئة العناصر في 3 m /2 صناديق.

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

• درس أنيلي وبراميل وسيمتشي-ليفي ^{[ 48 ]} حالةً يكون فيها تكلفة الحاوية دالة مقعرة لعدد العناصر الموجودة فيها. والهدف هو تقليل التكلفة الإجمالية بدلاً من عدد الحاويات. وقد أظهروا أن خوارزمية تعبئة الحاويات المتزايدة التالية تحقق نسبة تقريبية قصوى في أسوأ الحالات لا تتجاوز 7/4، ونسبة تقارب قصوى تبلغ 1.691 لأي ​​دالة تكلفة مقعرة ورتيبة.
• درس كوهين، وكيلر، وميروكني، وزاديموغادام ^{[ 49 ]} حالةً يكون فيها حجم العناصر غير معروف مسبقًا، ولكنه متغير عشوائي . وهذا شائعٌ بشكل خاص في بيئات الحوسبة السحابية . فبينما يوجد حدٌ أقصى لكمية الموارد التي يحتاجها مستخدمٌ معين، فإن معظم المستخدمين يستخدمون أقل بكثير من السعة المتاحة. لذلك، قد يحقق مدير السحابة مكاسب كبيرة من خلال زيادة طفيفة في الالتزام . وهذا يُؤدي إلى نوعٍ مُختلف من تعبئة الحاويات مع قيود احتمالية : يجب أن يكون احتمال أن يكون مجموع الأحجام في كل حاوية على الأكثر B على الأقل p ، حيث p ثابت (تتوافق تعبئة الحاويات القياسية مع p = 1). وقد أظهروا أنه، في ظل افتراضات بسيطة، تُكافئ هذه المشكلة مشكلة تعبئة الحاويات شبه المعيارية ، حيث لا يساوي "الحمل" في كل حاوية مجموع العناصر، بل يساوي دالة شبه معيارية مُعينة له.

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

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

في مسألة تعبئة الصناديق المتجهة ، يُمثل كل عنصر متجهًا، كما أن حجم كل صندوق هو متجه أيضًا. لنفترض أن حجم الصندوق هو${\displaystyle w}$ويكون مجموع المتجهات في الصندوق${\displaystyle v}$إذاً، فإن الشرط هو أن${\displaystyle \forall i,v_{i}\leq w_{i}}$[ ^{50 ]​}

في مسألة تعبئة الصناديق العكسية ، ^{[ 51 ]} يكون كل من عدد الصناديق وأحجامها ثابتًا، بينما يمكن تغيير أحجام العناصر. والهدف هو تحقيق أقل قدر من التغيير في متجه أحجام العناصر بحيث يمكن تعبئة جميع العناصر في العدد المحدد من الصناديق.

في مسألة تعبئة الصناديق ذات الموارد القصوى ^{[ 52 ]} ، يتمثل الهدف في زيادة عدد الصناديق المستخدمة إلى أقصى حد، بحيث لا يتسع أي عنصر من صندوق لاحق في صندوق سابق، وذلك وفقًا لترتيب معين للصناديق. أما في المسألة الثنائية، فيكون عدد الصناديق ثابتًا، ويكون الهدف هو تقليل العدد الإجمالي أو الحجم الإجمالي للعناصر الموضوعة في الصناديق، بحيث لا يتسع أي عنصر متبقٍ في صندوق فارغ.

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

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

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

في مسألة تعبئة الصناديق الأنانية ، يمثل كل عنصر لاعبًا يرغب في تقليل تكلفته. ^{[ 54 ]}

يوجد أيضاً نوع مختلف من تعبئة الصناديق حيث لا يكون الهدف من تقليل التكلفة هو عدد الصناديق، بل دالة مقعرة معينة لعدد العناصر في كل صندوق. ^{[ 48 ]}

في مجال الخدمات اللوجستية والتجارة الإلكترونية ، يُعد التعبئة ثلاثية الأبعاد أساس "التعبئة في الكراتين"، حيث يقوم البرنامج باختيار كرتونة الشحن وترتيب التعبئة المناسب لمجموعة من العناصر؛ وتشمل المشكلات الصناعية ذات الصلة الوثيقة تحميل الحاويات والمنصات. ^{[ 55 ]}

وتشمل المتغيرات الأخرى تعبئة الصناديق ثنائية الأبعاد، ^{[ 56 ]} وتعبئة الصناديق ثلاثية الأبعاد ، ^{[ 57 ]} وتعبئة الصناديق مع التسليم ، ^{[ 58 ]}

• BPPLIB - مكتبة تضم استطلاعات، ورموز، ومعايير، ومولدات، وحلول، ومراجع.