Bin Packing

Bin packing مسألة كلاسيكية في أبحاث العمليات: لمجموعة من العناصر (أحجام وأوزان وحجوم متفاوتة)، ضعها في صناديق ذات سعة ثابتة بحيث يُقلَّل العدد الإجمالي للصناديق (الهدف القياسي). دُرست الصيغة أحادية البعد (1D-BPP) — وزن أو طول فقط — بكثرة منذ Johnson (1974). الصيغة ثنائية البعد (2D-BPP) تظهر في القطع ووضع الملصقات. الصيغة ثلاثية البعد (3D-BPP) تظهر في تحميل البالتات والحاويات والشاحنات. لكونها NP-صعبة تعتمد الحلول العملية على أساليب حدسية (first-fit decreasing، best-fit، wall-building) وما-فوق-حدسية (GRASP، tabu، simulated annealing). الامتداد بالقيود العملية الجانبية يُسمى Container Loading Problem (CLP).