High-multiplicity bin packing
ہائی ملٹی پلیسیٹی بن پیکنگ بن پیکنگ کے مسئلے کا ایک خاص معاملہ ہے، جس میں مختلف آئٹم سائز کی تعداد کم ہوتی ہے، جبکہ ہر سائز کی اشیاء کی تعداد بڑی ہوتی ہے۔ اگرچہ عام بن پیکنگ کا مسئلہ این پی ہارڈ ہے، لیکن اعلی ضرب کی ترتیب کو کثیر الجہتی وقت میں حل کیا جاسکتا ہے، یہ فرض کرتے ہوئے کہ مختلف سائز کی تعداد ایک مقررہ مستقل ہے۔ دشواری کی تعریف دشواری کے لیے ان پٹ مثبت عدد ہیں: d-مختلف سائز کی تعداد (جسے مسئلہ کا طول و عرض بھی کہا جاتا ہے) ؛ B-بن کی صلاحیت۔ s1،.، sd-سائز۔ سائز کے ویکٹر کو 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 ڈبے استعمال ہوتے ہیں۔ ترتیب ایک ترتیب آئٹمز کا ایک مجموعہ ہے جو ایک ہی ڈبے میں فٹ ہو سکتا ہے۔ اس کی نمائندگی ڈی انٹیجرز کے ویکٹر کے ذریعے کی جا سکتی ہے، جو ترتیب میں مختلف سائز کی ضرب کو ظاہر کرتا ہے۔ رسمی طور پر، ہر کنفیگریشن c کے لیے ہم ایک انٹیجر ویکٹر کی وضاحت کرتے ہیں۔ AC = AC, 1,., AC, d اس طرح کہ AC ≤ n اور AC·s ≤ B۔ مندرجہ بالا مثال میں، ترتیبات میں سے ایک c = {30,40,40} ہے، کیونکہ 1 * 30+2 * 40 ≤120 ہے۔ اس کا متعلقہ ویکٹر AC = (1,2) ہے۔ دیگر ترتیب ویکٹر (4,0)، (3,0)، (2,0)، (2,1)، (1,1)، (1,2)، (0,1)، (0,2)، (0,3) ہیں۔ اگر ہمارے پاس سائز 3 کی صرف تین اشیاء ہوتیں، تو ہم (4,0) ترتیب استعمال نہیں کر سکتے تھے۔ ترتیب لکیری پروگرام کا استعمال کرتے ہوئے مسئلہ پیش کرنا ممکن ہے: ہر ترتیب c کے لیے، ایک متغیر xc ہوتا ہے، جو ڈبوں کی تعداد کو ظاہر کرتا ہے جس میں c استعمال ہوتا ہے۔ استعمال شدہ ڈبوں کی کل تعداد محض تمام ترتیبات پر xc کا مجموعہ ہے، جسے 1·x سے ظاہر کیا جاتا ہے۔ ہر سائز سے استعمال ہونے والی آئٹمز کی کل تعداد تمام ترتیبات پر ویکٹروں AC·XC کا مجموعہ ہے۔ پھر، مسئلہ 1·X کو اس طرح کم کرنا ہے کہ تمام ترتیبات C پر AC·XC کا مجموعہ کم از کم n ہو، تاکہ تمام آئٹمز پیک ہوں۔ الگورتھم بنیادی الگورتھم فرض کریں کہ سب سے پہلے تمام آئٹمز بڑی ہیں، یعنی ہر ایس آئی کم از کم کسی حصے e> 0 کے لیے e·B ہے۔ پھر، ہر ڈبے میں آئٹمز کی کل تعداد زیادہ سے زیادہ 1/e ہے، لہذا ترتیب کی کل تعداد زیادہ سے زیادہ d1/e ہے۔ ہر ترتیب زیادہ سے زیادہ n اوقات میں ظاہر ہوتی ہے۔ لہذا، چیک کرنے کے لیے زیادہ تر امتزاج موجود ہیں۔ ہر امتزاج کے لیے، ہمیں d رکاوٹوں (ہر سائز کے لیے ایک) کو چیک کرنا ہوگا، لہذا رن ٹائم ہے، جو n میں کثیر الجہتی ہے جب d، e مستقل ہیں۔ اس الگورتھم کے ساتھ بنیادی مسئلہ (اس حقیقت کے علاوہ کہ یہ صرف اس وقت کام کرتا ہے جب آئٹمز بڑے ہوتے ہیں) یہ ہے کہ اس کا رن ٹائم n میں کثیر الجہتی ہوتا ہے، لیکن ان پٹ کی لمبائی (بائنری نمائندگی میں) لاگ (V) میں لکیری ہوتی ہے، جو لاگ (n) کی شدت کی ترتیب کا ہوتا ہے۔ ان پٹ سائز میں رن ٹائم کثیر الجہتی فلپی اور اگنیٹس نے ایک الگورتھم پیش کیا جو زیادہ سے زیادہ او پی ٹی + ڈی-2 ڈبوں کے ساتھ وقت او (پولی (لاگ وی)) میں حل تلاش کرتا ہے۔ خاص طور پر، d = 2 مختلف سائز کے لیے، ان کا الگورتھم وقت O (لاگ V) میں ایک بہترین حل تلاش کرتا ہے۔ گومنس اور روتھوس نے کسی بھی فکسڈ ڈی کے لیے ایک الگورتھم پیش کیا، جو اس وقت بہترین حل تلاش کرتا ہے جب تمام اعداد بائنری انکوڈنگ میں دیے جاتے ہیں۔ ان کا الگورتھم مندرجہ ذیل مسئلے کو حل کرتا ہے: دو ڈی جہتی پولی ٹاپس P اور Q کو دیکھتے ہوئے، P میں انٹیجر پوائنٹس کی کم از کم تعداد تلاش کریں جن کا مجموعہ Q میں ہے۔ ان کا الگورتھم وقت پر چلتا ہے۔ ان کے الگورتھم کو دیگر مسائل کے مطابق ڈھالا جا سکتا ہے، جیسے کہ یکساں مشینوں کا شیڈولنگ اور مختلف رکاوٹوں کے ساتھ غیر متعلقہ مشینوں کا شیڈولنگ۔ عام بن پیکنگ کے مسئلے کے لیے کئی تخمینہ الگورتھم مندرجہ ذیل اسکیم کا استعمال کرتے ہیں: آئٹمز کو "چھوٹے" (ای بی سے چھوٹے، کچھ حصے کے لیے ای ان (0,1)) اور "بڑے" (کم از کم ای بی) میں الگ کریں۔ بڑی آئٹمز کو پہلے ہینڈل کریں: آئٹم کے سائز کو کسی نہ کسی طرح گول کریں، تاکہ مختلف سائز کی تعداد زیادہ سے زیادہ کچھ مستقل رہے۔ چھوٹی چھوٹی اشیاء کو لالچ سے مختص کریں، جیسے۔ نیکسٹ فٹ بن پیکنگ کے ساتھ۔ اگر کوئی نیا ڈبہ نہیں بنایا جاتا ہے، تو ہم کام کر چکے ہیں۔ اگر نئے ڈبے بنائے جاتے ہیں، تو اس کا مطلب یہ ہے کہ تمام ڈبے (شاید آخری کے علاوہ) کم از کم (1-ای) بی تک بھرے ہوئے ہیں۔ لہذا، ڈبوں کی تعداد زیادہ سے زیادہ او پی ٹی/(1-ای) + 1 ≤ (1 + 2 ای) او پی ٹی + 1 ہے۔ الگورتھم اس بات میں مختلف ہیں کہ وہ مثال کو کس طرح گول کرتے ہیں۔ لکیری راؤنڈنگ لیوکر اور ڈی لا ویگا نے انکولی ان پٹ راؤنڈنگ کا خیال ایجاد کیا۔ آئٹمز کو ان کے سائز کے لحاظ سے آرڈر کریں، اور انہیں 1/e2 کارڈینالیٹی ne2 کے گروپوں میں گروپ کریں۔ ہر گروپ میں، سائز کو اوپر کی طرف گروپ میں زیادہ سے زیادہ سائز تک گول کریں۔ اب، صرف d = 1/e2 مختلف سائز ہیں۔ گول مثال کا حل اصل مثال کے لیے بھی ممکن ہے، لیکن ڈبوں کی تعداد ضرورت سے زیادہ ہو سکتی ہے۔ نقصان کی مقدار طے کرنے کے لیے، پچھلے گروپ میں زیادہ سے زیادہ سائز تک گول کردہ مثال پر غور کریں (پہلا گروپ 0 تک گول کیا گیا ہے)۔ گول نیچے کی مثال D تقریبا گول اپ مثال U کے برابر ہے، سوائے اس کے کہ D میں کچھ ne2 صفر ہیں جبکہ U میں اس کے بجائے کچھ ne2 بڑی اشیاء ہیں ؛ لیکن ان کا سائز زیادہ سے زیادہ B ہے۔ لہذا، یو کو زیادہ سے زیادہ این ای 2 ڈبے ڈی سے زیادہ درکار ہوتے ہیں۔ چونکہ ڈی کو زیادہ سے زیادہ کم ڈبے کی ضرورت ہوتی ہے، اس لیے ہمیں وہ ڈبے (یو) ≤ او پی ٹی + این ای 2 ملتے ہیں، یعنی، ہمارے پاس ایک اضافی غلطی ہے جسے ای کا انتخاب کرکے اتنا ہی چھوٹا بنایا جا سکتا ہے جتنا ہم چاہتے ہیں۔ اگر تمام اشیاء بڑی ہیں (کم از کم ای بی سائز کی)، تو او پی ٹی میں ہر ڈبے میں زیادہ سے زیادہ 1/ای آئٹمز (کم از کم ای بی سائز کی) ہوتی ہیں، لہذا او پی ٹی کم از کم این ہونا چاہیے۔ لہذا، ڈبے (یو) ≤ (1 + ای) او پی ٹی۔ چھوٹی چھوٹی چیزوں کو سنبھالنے کے بعد، ہم زیادہ سے زیادہ حاصل کرتے ہیں۔ جیومیٹرک راؤنڈنگ کرمارکر اور کارپ ایک زیادہ موثر راؤنڈنگ کا طریقہ پیش کرتے ہیں جسے وہ جیومیٹرک راؤنڈنگ کہتے ہیں (ڈی-لا-ویگا اور لیوکر کی لکیری راؤنڈنگ کے برعکس)۔ ان اختراعات کی بنیاد پر، وہ اور میں رن ٹائم کثیر الجہتی کے ساتھ ایک الگورتھم پیش کرتے ہیں۔ ان کا الگورتھم زیادہ سے زیادہ سائز کے ساتھ حل تلاش کرتا ہے۔ بہتری اس تکنیک کو بعد میں کئی مصنفین نے بہتر بنایا: روتھوس نے ایک الگورتھم پیش کیا جو زیادہ سے زیادہ سائز کے ساتھ حل پیدا کرتا ہے۔ ہوبرگ اور روتھوس نے زیادہ سے زیادہ سائز کے ساتھ حل پیدا کرنے کے لیے اس الگورتھم کو بہتر بنایا۔ الگورتھم بے ترتیب ہے، اور اس کا رننگ ٹائم آئٹمز کی کل تعداد میں کثیر الجہتی ہے۔ اسٹاک کاٹنے کا مسئلہ بھی دیکھیں-اعلی ضرب والے ڈبے کی پیکنگ کی طرح، لیکن مقصد ڈبے کی تعداد کے بجائے ہر ڈبے میں ضائع ہونے والی جگہ کی کل مقدار کو کم کرنا ہے۔ مزید برآں، کچھ اقسام میں، ہر سائز کی اشیاء کی تعداد طے نہیں ہوتی ہے، لیکن کچھ دی گئی نچلی اور اوپری حدود کے درمیان منتقل ہو سکتی ہے۔ حوالہ جات بن پیکنگ