3-PARTITIONING CONTAINING KERNELS - COMPLEXITY AND HEURISTIC

Let G = {g(1), g(2) ,..., gm}U{t(1), t(2) ,..., t(n)} be a list of ite ms with nonnegative weights assigned and k greater than or equal to 2 be an integer. The objective is to find an assignment of the items to the bins such that all g(i) (called kernels) are assigned to different bins, such that no bin contains more than k items, and such that the maximum weight assigned to any bin becomes minimum. In this paper, we first prove that the problem is NP-complete in the strong sense for an y k greater than or equal to 3. As heuristic for this problem, we use a modified version of the famous LPT-algorithm for multiprocessor sche duling, and we show a worst case bound of 3/2 - 1/2m for k = 3.