High-multiplicity bin packing
উচ্চ-গুণমান বিন প্যাকিং বিন প্যাকিং সমস্যার একটি বিশেষ ক্ষেত্রে, যেখানে বিভিন্ন আকারের আইটেমের সংখ্যা কম, এবং প্রতিটি আকারের আইটেমের সংখ্যা বেশি। যদিও সাধারণ বিন-প্যাকিং সমস্যাটি এনপি-হার্ড, উচ্চ-গুণমান সেটিংটি বহুপদী সময়ে সমাধান করা যেতে পারে, ধরে নেওয়া যায় যে বিভিন্ন আকারের সংখ্যা একটি নির্দিষ্ট ধ্রুবক। সমস্যার সংজ্ঞা সমস্যার ইনপুটগুলি ধনাত্মক পূর্ণসংখ্যাঃ ডি-বিভিন্ন আকারের সংখ্যা (যাকে সমস্যার মাত্রাও বলা হয়); বি-বিন ক্ষমতা। এস1,., এসডি-মাপ। আকারের ভেক্টরকে s. n1,., nd-গুণ দ্বারা চিহ্নিত করা হয়; ni হল সাই আকারের আইটেমের সংখ্যা। গুণের ভেক্টরকে n দ্বারা চিহ্নিত করা হয়. n বস্তুর মোট সংখ্যাকে বোঝায়, অর্থাৎ, n = n1 +. + nd। V সমস্যার বর্ণনায় প্রদর্শিত বৃহত্তম পূর্ণসংখ্যাকে বোঝায়, অর্থাৎ, V = সর্বোচ্চ (s1,., sd, n1,., nd, B) আউটপুট হল একটি প্যাকিং-বিনগুলিতে আইটেমগুলির একটি অ্যাসাইনমেন্ট, যাতে প্রতিটি বিন-এ আইটেমগুলির মোট আকার সর্বাধিক B হয় এবং এর সাপেক্ষে, বিনগুলির সংখ্যা যতটা সম্ভব ছোট হয়। উদাহরণস্বরূপঃ ধরুন d = 2, s1 = 30, s2 = 40, n1 = n2 = 5, B = 120। সুতরাং আকার সহ n = 10 টি আইটেম রয়েছেঃ 30,30,30,30,30,40,40,40,40,40। তারপর, একটি সম্ভাব্য প্যাকিং হলঃ {30,30,30,30}, {40,40,40}, {30,40,40}, যা 3 টি বিন ব্যবহার করে। কনফিগারেশন একটি কনফিগারেশন হল এমন আইটেমগুলির একটি সেট যা একটি একক বিন-এ ফিট করতে পারে। এটি ডি পূর্ণসংখ্যার একটি ভেক্টর দ্বারা প্রতিনিধিত্ব করা যেতে পারে, যা বিন্যাসে বিভিন্ন আকারের গুণকে নির্দেশ করে। আনুষ্ঠানিকভাবে, প্রতিটি বিন্যাস সি-এর জন্য আমরা একটি পূর্ণসংখ্যা ভেক্টর এসি = এসি, 1,., এসি, ডি এমনভাবে সংজ্ঞায়িত করি যাতে এসি ≤ এন এবং এসি·এস ≤ বি। উপরের উদাহরণে, কনফিগারেশনগুলির মধ্যে একটি হল c = {30,40,40}, যেহেতু 1 * 30+2 * 40 ≤120। এর সংশ্লিষ্ট ভেক্টর হল এসি = (1,2)। অন্যান্য বিন্যাস ভেক্টরগুলি হল (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1), (0,2), (0,3)। যদি আমাদের কাছে 3 আকারের মাত্র তিনটি আইটেম থাকত, তাহলে আমরা (4,0) কনফিগারেশন ব্যবহার করতে পারতাম না। কনফিগারেশন লিনিয়ার প্রোগ্রাম ব্যবহার করে সমস্যাটি উপস্থাপন করা সম্ভবঃ প্রতিটি কনফিগারেশন সি-এর জন্য, একটি পরিবর্তনশীল এক্সসি রয়েছে, যা সি ব্যবহার করা হয় এমন বিনগুলির সংখ্যা নির্দেশ করে। ব্যবহৃত বিনগুলির মোট সংখ্যা কেবল সমস্ত কনফিগারেশনের উপর xc-এর যোগফল, যা 1·x দ্বারা চিহ্নিত করা হয়। প্রতিটি আকার থেকে ব্যবহৃত আইটেমগুলির মোট সংখ্যা হল সমস্ত কনফিগারেশনের উপর ভেক্টরের সমষ্টি c। তারপর, সমস্যাটি হল 1·x-কে এমনভাবে কমিয়ে আনা যাতে সমস্ত কনফিগারেশন c-এর উপর ac·xc-এর যোগফল কমপক্ষে n হয়, যাতে সমস্ত আইটেমগুলি প্যাক করা হয়। অ্যালগরিদম মৌলিক অ্যালগরিদম ধরুন প্রথমে মনে করুন যে সমস্ত আইটেম বড়, অর্থাৎ প্রতিটি এসআই কিছু ভগ্নাংশের জন্য কমপক্ষে e·B হয়। তারপর, প্রতিটি বিন-এ মোট আইটেমের সংখ্যা সর্বাধিক 1/ই, তাই কনফিগারেশনের মোট সংখ্যা সর্বাধিক ডি1/ই। প্রতিটি কনফিগারেশন সর্বাধিক n বার প্রদর্শিত হয়। অতএব, পরীক্ষা করার জন্য বেশিরভাগ সংমিশ্রণ রয়েছে। প্রতিটি সংমিশ্রণের জন্য, আমাদের d সীমাবদ্ধতাগুলি (প্রতিটি আকারের জন্য একটি) পরীক্ষা করতে হবে, তাই রান-টাইম হল, যা n-এ বহুপদী যখন d, e ধ্রুবক। এই অ্যালগরিদমের প্রধান সমস্যা হল (এই বিষয়টি ছাড়াও যে এটি কেবল তখনই কাজ করে যখন আইটেমগুলি বড় হয়) যে এর রানটাইম এন-এ বহুপদী, তবে ইনপুটের দৈর্ঘ্য (বাইনারি উপস্থাপনায়) লগ (ভি)-এ রৈখিক, যা লগ (এন)-এর মাত্রার ক্রমের। ইনপুট আকারে রান-টাইম বহুপদী ফিলিপ্পি এবং এগ্নেটিস একটি অ্যালগরিদম উপস্থাপন করেছে যা O (পলি (লগ ভি)) সময়ে সর্বাধিক ওপিটি + ডি-2 বিন দিয়ে একটি সমাধান খুঁজে পায়। বিশেষ করে, ডি = 2 বিভিন্ন মাপের জন্য, তাদের অ্যালগরিদম ও (লগ ভি) সময়ে একটি সর্বোত্তম সমাধান খুঁজে পায়। গোম্যানস এবং রথভোস যে কোনও নির্দিষ্ট ডি-এর জন্য একটি অ্যালগরিদম উপস্থাপন করেছিলেন, যা সমস্ত সংখ্যা বাইনারি এনকোডিংয়ে দেওয়া হলে সর্বোত্তম সমাধান খুঁজে পায়। তাদের অ্যালগরিদম নিম্নলিখিত সমস্যার সমাধান করেঃ দুটি ডি-মাত্রিক পলিটোপ পি এবং কিউ দেওয়া হলে, পি-তে সর্বনিম্ন সংখ্যক পূর্ণসংখ্যা বিন্দু খুঁজে বের করুন যার যোগফল কিউ-তে রয়েছে। তাদের অ্যালগরিদম সময়মতো চলে। তাদের অ্যালগরিদম অন্যান্য সমস্যার সাথে খাপ খাইয়ে নেওয়া যেতে পারে, যেমন আইডেন্টিকাল-মেশিন সময়সূচী এবং বিভিন্ন সীমাবদ্ধতার সাথে সম্পর্কহীন-মেশিন সময়সূচী। সাধারণ বিন-প্যাকিং সমস্যার জন্য বেশ কয়েকটি আনুমানিক অ্যালগরিদম নিম্নলিখিত স্কিমটি ব্যবহার করেঃ আইটেমগুলিকে "ছোট" (ইবি-র চেয়ে ছোট, কিছু ভগ্নাংশের জন্য ই (0,1)) এবং "বড়" (কমপক্ষে ইবি)-তে পৃথক করুন। প্রথমে বড় জিনিসগুলি পরিচালনা করুনঃ জিনিসের আকার এমনভাবে বৃত্তাকার করুন, যাতে বিভিন্ন আকারের সংখ্যা সর্বাধিক কিছু স্থির থাকে। লোভের সাথে ছোট জিনিসগুলি বরাদ্দ করুন, যেমন। পরবর্তী মাপের বিন প্যাকিং সহ। যদি কোনও নতুন বিন তৈরি না করা হয়, তাহলে আমাদের কাজ শেষ। যদি নতুন বিন তৈরি করা হয়, তার মানে হল যে সমস্ত বিন (সম্ভবত শেষটি ছাড়া) কমপক্ষে (1-ই) বি পর্যন্ত পূর্ণ। অতএব, বিনগুলির সংখ্যা সর্বাধিক ওপিটি/(1-ই) + 1 ≤ (1 + 2ই) ওপিটি + 1। অ্যালগরিদমগুলি কীভাবে উদাহরণটিকে বৃত্তাকার করে তার মধ্যে পার্থক্য রয়েছে। লিনিয়ার রাউন্ডিং লুয়েকার এবং ডি-লা-ভেগা অভিযোজিত ইনপুট রাউন্ডিংয়ের ধারণাটি উদ্ভাবন করেছিলেন। আইটেমগুলিকে তাদের আকার অনুসারে অর্ডার করুন এবং সেগুলিকে 1/ই2 কার্ডিনালিটি এনই2 গ্রুপে ভাগ করুন। প্রতিটি গ্রুপে, গ্রুপের আকারগুলি উপরের দিকে সর্বোচ্চ আকার পর্যন্ত বৃত্তাকার করুন। এখন, শুধুমাত্র d = 1/e2 বিভিন্ন আকার রয়েছে। বৃত্তাকার দৃষ্টান্তের সমাধান মূল দৃষ্টান্তের জন্যও সম্ভব, তবে বিনগুলির সংখ্যা প্রয়োজনের চেয়ে বেশি হতে পারে। ক্ষতির পরিমাণ নির্ধারণের জন্য, উদাহরণটি পূর্ববর্তী গ্রুপের সর্বোচ্চ আকারের দিকে বিবেচনা করুন (প্রথম গ্রুপটি 0-তে বৃত্তাকার করা হয়েছে)। বৃত্তাকার-ডাউন উদাহরণ D প্রায় বৃত্তাকার-আপ উদাহরণ U-এর সমান, D-তে কিছু ne2 শূন্য থাকে এবং U-তে কিছু ne2 বড় আইটেম থাকে; তবে তাদের আকার সর্বাধিক B হয়। অতএব, ইউ-এর জন্য সর্বাধিক ডি-এর চেয়ে এনই2 বেশি বিন প্রয়োজন। যেহেতু ডি-এর জন্য সর্বোত্তমের চেয়ে কম বিন প্রয়োজন, তাই আমরা সেই বিন (ইউ) ≤ ওপিটি + এনই2 পাই, অর্থাৎ, আমাদের একটি যোগাত্মক ত্রুটি রয়েছে যা ই বেছে নেওয়ার মাধ্যমে আমরা যতটা চাই ততটা ছোট করা যেতে পারে। যদি সমস্ত আইটেম বড় হয় (কমপক্ষে ইবি আকারের), তবে ওপিটি-র প্রতিটি বিন সর্বাধিক 1/ই আইটেম (কমপক্ষে ইবি আকারের) ধারণ করে, তাই ওপিটি অবশ্যই কমপক্ষে এন হতে হবে। অতএব, বিন (ইউ) ≤ (1 + ই) ওপিটি। ছোট জিনিসগুলি পরিচালনা করার পরে, আমরা সর্বাধিক পাই। জ্যামিতিক বৃত্তাকার কর্মকার এবং কার্প একটি আরও কার্যকর বৃত্তাকার পদ্ধতি উপস্থাপন করে যাকে তারা জ্যামিতিক বৃত্তাকার বলে (ডি-লা-ভেগা এবং লুয়েকারের রৈখিক বৃত্তাকারের বিপরীতে)। এই উদ্ভাবনের উপর ভিত্তি করে, তারা এবং-এ রান-টাইম পলিনোমিয়াল সহ একটি অ্যালগরিদম উপস্থাপন করে। তাদের অ্যালগরিদম সর্বাধিক আকারের একটি সমাধান খুঁজে পায়। উন্নতি এই কৌশলটি পরে বেশ কয়েকজন লেখক দ্বারা উন্নত করা হয়েছিলঃ রথভোস একটি অ্যালগরিদম উপস্থাপন করেছিলেন যা সর্বাধিক আকারের সাথে একটি সমাধান তৈরি করে। হোবারগ এবং রথভোস এই অ্যালগরিদমটি উন্নত করে সর্বাধিক আকারের সাথে একটি সমাধান তৈরি করেন। অ্যালগরিদমটি এলোমেলোভাবে তৈরি করা হয়েছে এবং এর চলমান সময়টি মোট আইটেমের সংখ্যার মধ্যে বহুপদী। আরও দেখুন কাটিং স্টক সমস্যা-উচ্চ-গুণমান বিন-প্যাকিংয়ের মতো, তবে লক্ষ্য হল প্রতিটি বিন-এ বর্জ্য জায়গার মোট পরিমাণ হ্রাস করা, বিন-এর সংখ্যার পরিবর্তে। উপরন্তু, কিছু বৈচিত্র্যে, প্রতিটি আকারের আইটেমের সংখ্যা নির্দিষ্ট নয়, তবে কিছু প্রদত্ত নিম্ন এবং উপরের সীমার মধ্যে যেতে পারে। রেফারেন্স বিন প্যাকিং