Next-fit-decreasing bin packing
নেক্সট-ফিট-ডিক্রিজিং (এন. এফ. ডি) হল বিন প্যাকিংয়ের জন্য একটি অ্যালগরিদম। এর ইনপুট হল বিভিন্ন আকারের আইটেমের একটি তালিকা। এর আউটপুট হল একটি প্যাকিং-নির্দিষ্ট ক্ষমতার বিনগুলিতে আইটেমগুলির একটি বিভাজন, যাতে প্রতিটি বিন-এ আইটেমগুলির আকারের যোগফল সর্বাধিক ক্ষমতা হয়। আদর্শভাবে, আমরা যতটা সম্ভব কম বিন ব্যবহার করতে চাই, তবে বিনগুলির সংখ্যা হ্রাস করা একটি এনপি-হার্ড সমস্যা। এন. এফ. ডি অ্যালগরিদম নিম্নলিখিত হিউরিস্টিক ব্যবহার করেঃ আইটেমগুলিকে বৃহত্তম থেকে ক্ষুদ্রতম পর্যন্ত অর্ডার করুন। একটি খালি বিন শুরু করুন এবং এটিকে "খোলা বিন" বলুন। প্রতিটি জিনিসের জন্য, এটি খোলা বিনটিতে ফিট করতে পারে কিনা তা পরীক্ষা করুনঃ যদি এটি ফিট করে তবে নতুন আইটেমটি এতে রাখুন। অন্যথায়, বর্তমান বিনটি বন্ধ করুন, একটি নতুন বিন খুলুন এবং বর্তমান আইটেমটি এর ভিতরে রাখুন। সংক্ষেপেঃ এন. এফ. ডি অবরোহী আকারের পণ্য অর্ডার করে, এবং তারপর পরবর্তী মাপের বিন প্যাকিং কল করে। পারফরম্যান্স আপার বাউন্ড বেকার এবং কফম্যান প্রমাণ করেছেন যে, প্রতিটি পূর্ণসংখ্যা r-এর জন্য, যখন সমস্ত আইটেমের আকার সর্বাধিক 1/r হয়, তখন RFD-এর অ্যাসিম্পটোটিক আনুমানিক অনুপাত সন্তুষ্ট হয়, যেখানে এমন একটি ক্রম যার প্রথম উপাদানগুলি প্রায় 1.69103,1.42312,1.30238। বিশেষ করে, r = 1 গ্রহণ করলে তা বোঝা যায়। পরে, এন. এফ. ডি-ও সম্ভাব্যভাবে বিশ্লেষণ করা হয়েছে। ভেরিয়েন্টস নেক্সট-ফিট একটি তালিকা এবং তার বিপরীতটি একই সংখ্যক বিনে প্যাক করে। অতএব, নেক্সট-ফিট-ইনক্রিজিং-এর পারফরম্যান্স নেক্সট-ফিট-ডিক্রিজিং-এর মতোই। তবে, সাধারণ খরচের কাঠামো থাকলে নেক্সট-ফিট-ইনক্রিজিং আরও ভাল কাজ করে। রেফারেন্স বিন প্যাকিং