An Iterative Algorithm for Solving the Multiple Knapsack Assignment Problem
Dahmani Isma  1@  , Meriem Ferroum  1@  , Mhand Hifi  2@  
1 : AMCD-RO, Département de RO, USTHB, Algérie
2 : Eco-Procédés Optimisation et Aide à la Décision - UR UPJV 4669
Université de Picardie Jules Verne : UR4669

In this paper, an approximate method is proposed for solving a multiple knapsack assignment problem(PMKAP)  An instance of PMKAP is characterized by a set of items, and a set of knapsacks. Each item j is characterized with its nonnegative profit and nonnegative weight w. Each knapsack is characterized by a nonnegative weight c. However, items are divided into mutually disjoint subsets of items Sk. The goal of the problem is to determine the assignment of all knapsacks to each subset, and to fill knapsacks with items in that subset, so as to maximize the total profit related to the selected items. The iterative algorithm combines descent procedure  with several strategies for anhancing the quality of the solutions. The preliminary experimentation showed that the proposed approach remains competitive, where new bounds have been reached.


Personnes connectées : 5 Vie privée
Chargement...