Thek-partitioning problem |
| |
| Authors: | Luitpold Babel Hans Kellerer Vladimir Kotov |
| |
| Institution: | (1) Institut für Mathematik, Technische Universität München, Arcisstraße 21, D-80290 München, Germany;(2) Institut für Statistik, Ökonometrie und Operations Research, Universität Graz, Universitätsstraße 15, A-8010 Graz, Austria;(3) Faculty of Applied Mathematics and Computer Science, University of Minsk, 220080 Minsk, Byelarussia |
| |
| Abstract: | Thek-partitioning problem is defined as follows: Given a set of items {I
1,I
2,...,I
n} where itemIj is of weightwj  0, find a partitionS
1,S
2,...,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. |
| |
| Keywords: | partition multiprocessor scheduling worst-case |
| 本文献已被 SpringerLink 等数据库收录！ |
|
