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

k-partitioning problem with items' type restriction

作　　者：任庆娟[1,2] 许保光[2] 

机构地区：[1]中国科学技术大学管理学院,合肥230026 [2]中国科学院科技政策与管理科学研究所,北京100190

出　　处：《运筹学学报》2012年第3期93-99,共7页Operations Research Transactions

摘　　要：研究有元素类型约束且每个元素权重为正数的κ-集合划分问题,元素类型约束指κ-划分后每个集合所包含的元素的类型均不同,该问题是对κ-划分问题(κ-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.

关 键 词：k-划分问题 元素类型约束 LPT 最坏情况性能比 

分 类 号：O224[理学—运筹学与控制论]