An exact algorithm for the unrestricted block relocation problem

هدف از این مطالعه ارائه یک الگوریتم دقیق برای مسئله انتقال مسدودیت محدود با اولویت های متمایز است. در این مشکل، یک منطقه ذخیره سازی در نظر گرفته شده است که بلوک های همان اندازه در عمق در سطوح انباشته شده است. از آنجا که ما می توانیم فقط به بالایی از بلوک دسترسی داشته باشیم، وقتی بلوک های دیگر بازیابی می شوند، انتقال بلوک ها ضروری است. هدف این است که تعداد کل تغییرات لازم برای بازیابی تمام بلوک های یک به یک با توجه به یک سفارش مشخص به حداقل برسد. در نسخه محدود این مشکل، فقط بالای بلوک بالای بلوک هدف قابل جابجایی است. از سوی دیگر، هیچگونه محدودیتی برای مشکل نامحدود اعمال نشده است که در این مطالعه در نظر گرفته شده است. ما همچنین فرض می کنیم که هر بلوک به یک اولویت بازیابی متمایز اختصاص داده شده و دستور العمل بازیابی بلوک ها منحصر به فرد است. برای بهبود کارایی یک الگوریتم شاخه ای و محدود برای این مشکل، ما پیشنهاد خواص سلطه چندگانه را برای حذف گره های غیر ضروری در درخت جستجو می کنیم. علاوه بر این، ما پیشنهاد می کنیم که مرز پایین تر از تعداد کل انتقال ها باشد. اثربخشی الگوریتم دقیق ارائه شده توسط آزمایش های عددی برای نمونه های معیار در ادبیات تایید شده است.