有元素类型约束的k-划分问题研究

k-partitioning problem with items' type restriction

研究有元素类型约束且每个元素权重为正数的κ-集合划分问题,元素类型约束指κ-划分后每个集合所包含的元素的类型均不同,该问题是对κ-划分问题(κ-partitioning problem)的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景,提出基于LPT算法思想的贪婪算法,并得出以下结论:κ≤2,该算法给出最优解:κ>2,最坏情况下的性能比为2-m^(-1),这里m指待分配集合的数量。

We consider a k-partitioning problem with items＇ type restriction. Items＇ type restriction means each set containing k distinct types＇ items. This problem is in fact an extended k-partitioning problem, and has a wide application in the industry where one person can hold multi-skill licenses. For solving it we propose a greedy algorithm and obtain the following conclusions： k ≤ 2, greedy algorithm get an optimal solution; k 〉 2, the performance ratio is 2 - m^-1.