Thek-partitioning problem

Abstract

Thek-partitioning problem is defined as follows: Given a set of items {I ₁,I ₂,...,I _n} where itemIj is of weightwj ≥ 0, find a partitionS ₁,S ₂,...,S _m of this set with ¦S _i ¦ =k such that the maximum weight of all subsetsS _i is minimal,k-partitioning is strongly related to the classical multiprocessor scheduling problem of minimizing the makespan on identical machines. This paper provides suitable tools for the construction of algorithms which solve exactly the problem. Several approximation algorithms are presented for this NP-hard problem. The worst-case behavior of the algorithms is analyzed. The best of these algorithms achieves a performance bound of 4/3.