کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6892516 | 1445449 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact algorithm for the Blocks Relocation Problem with new lower bounds
ترجمه فارسی عنوان
یک الگوریتم دقیق برای حل مساله بلوک با مرزهای پایینی جدید
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بلوک مشکل انتقال. مشکل انتقال بطری، الگوریتم های دقیق مرزهای پایین،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
The Blocks Relocation Problem is an important problem in storage systems. An input instance for it consists of a set of blocks distributed in stacks where each block is identified by a retrieval number and each stack has a same maximum height limit. The objective is to retrieve all the blocks respecting their retrieval order and performing the minimum number of relocations. Only blocks at the top of a stack can be moved: either a block is retrieved, if it has the highest retrieval priority among the stacked blocks, or it is relocated to the top of another stack. Solving this problem is critical in storage systems because it saves operational time and resources. In this paper, we present two new lower bounds for the number of relocations of an optimal solution. We implemented an exact iterative deepening A* algorithm using these new proposed lower bounds and other well-known lower bounds from the literature. We performed several computational experiments to show that the new lower bounds improve the performance of the exact algorithm, solving to optimality more instances than when using other lower bounds when given the same amount of time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 99, November 2018, Pages 206-217
Journal: Computers & Operations Research - Volume 99, November 2018, Pages 206-217
نویسندگان
Kent E. Yucra Quispe, Carla N. Lintzmayer, Eduardo C. Xavier,