Multi-processor based heuristic for multidimensional multiple-choise knapsack problem

Abstract

In this thesis we have devised a multi-processor based heuristic algorithm for the Multi-dimensional Multiple Choice Knapsack Problem (MMKP). MMKP is a variation of the classical 0-1 Knapsack Problem where there are multiple groups of items and more than one resonrce is required by each item. Admission control problem in an Adaptive Multimedia Server System can be mapped to MMKP. The problem is NP-hard which is not feasible for the real time admission control problem. So, heuristic solutions have been developed to solve the MMKP. Among all the heuristics, M-HEU developed by Akbar solves the MMKP achieving a reasonable percentage of optimality. This thesis presents an algorithm based on M-HEU using multiple processors. This algorithm runs in time O(T/p+ f(p») where Tis the time required by the algorithm using single processor, p is the number of processors and j(p), a function of p, is the SYnchronizationoverhead. The worst case analysis of the algorithm and the computation of the optimal number of processors are also done.