Veuillez utiliser cette adresse pour citer ce document : https://zone.biblio.laurentian.ca/handle/10219/2762
Titre: The 0 -1 multiple knapsack problem
Auteurs: Shamakhai, Hayat Abdullah
Mots clés: generalized assignment problem;assignment problem;knapsack problem;multiple knapsack problem;branch and bound algorithm;bound and bound algorithm;transportation problem;multiple assignment problem;adapted transportation problem;vogel approximation method;group role assignment problem.
Date publié: 31-mai-2017
Abstrait: In operation research, the Multiple Knapsack Problem (MKP) is classified as a combinatorial optimization problem. It is a particular case of the Generalized Assignment Problem. The MKP has been applied to many applications in naval as well as financial management. There are several methods to solve the Knapsack Problem (KP) and Multiple Knapsack Problem (MKP); in particular the Bound and Bound Algorithm (B&B). The bound and bound method is a modification of the Branch and Bound Algorithm which is defined as a particular tree-search technique for the integer linear programming. It has been used to obtain an optimal solution. In this research, we provide a new approach called the Adapted Transportation Algorithm (ATA) to solve the KP and MKP. The solution results of these methods are presented in this thesis. The Adapted Transportation Algorithm is applied to solve the Multiple Knapsack Problem where the unit profit of the items is dependent on the knapsack. In addition, we will show the link between the Multiple Knapsack Problem (MKP) and the multiple Assignment Problem (MAP). These results open a new field of research in order to solve KP and MKP by using the algorithms developed in transportation.
URI: https://zone.biblio.laurentian.ca/handle/10219/2762
Apparaît dans les collections:Computational Sciences - Master's theses
Master's Theses

Fichiers dans cet item:
Fichier Description TailleFormat 
thesisFINAL-Hayat Shamakhai-3 final correction (1).pdf1.74 MBAdobe PDFThumbnail
Parcourir/Ouvrir


Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.