کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478131 1446025 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Upper and lower bounding procedures for the multiple knapsack assignment problem
ترجمه فارسی عنوان
رویه های محدود کننده بالا و پایین برای مشکل انتساب چندگانه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• We formulate the multiple knapsack assignment problem as an extended problem.
• We propose three types of upper-bounding procedures and show their coincidence.
• These upper-bound algorithms cause a procedure to obtain approximate solutions.
• Our approximate algorithm can solve larger instances quickly and accurately.

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 237, Issue 2, 1 September 2014, Pages 440–447
نویسندگان
, ,