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.
