خوارزمية التخزين التالي المناسب للصندوق

خوارزمية الـ (Next-Fit) هي خوارزمية من خوارزميات الـ (Online) وتستخدم لحل مسألة تعبئة الصناديق (Bin Packing Problem) والتي تهدف إلى تعبئة عناصر مختلفة الحجم في صناديق متساوية السعة ، بحيث نستخدم أقل عدد ممكن من الصناديق .

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

1) يتم تحديد صندوق أولي فارغ لتخزين العناصر .

2) عند وصول عنصر ما من القائمة ، نقوم بفحص حجم العنصر ، ومدى ملائمته للمساحة المتبقية من الصندوق الذي تم تحديده في الخطوة (1) :

أ‌)  فإذا كانت المساحة كافية ، وضعناه في الصندوق .

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

3) يتم تكرار هذه العملية لكل العناصر .

هذه الخوارزمية تعتبر خوارزمية ذات مساحة محدودة ، بمعنى أنها تتطلب أن يكون هناك فقط صندوقاً واحداً مفتوحاً في أي وقت من تنفيذها ، وقد وضعت هذه الخوارزمية من قبل (David S. Johnson) في رسالته للدكتوراه عام 1973 في معهد ماساتشوستس للتقنية (MIT) .