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 | Taille | Format | |
---|---|---|---|---|
thesisFINAL-Hayat Shamakhai-3 final correction (1).pdf | 1.74 MB | Adobe PDF | Parcourir/Ouvrir |
Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.