| 有元素类型约束的k-划分问题研究 |
| |
| 引用本文： | 任庆娟,许保光.有元素类型约束的k-划分问题研究[J].运筹学学报,2012,16(3):93-99. |
| |
| 作者姓名： | 任庆娟 许保光 |
| |
| 作者单位： | 1. 中国科学技术大学
2. 中国科学院科技政策与管理科学研究所 |
| |
| 摘 要： | 研究有元素类型约束且每个元素权重为正数的k-集合划分问题，元素类型约束指k-划分后每个集合所包含的元素的类型均不同. 该问题是对k-划分问题(k-partitioning problem)的一个拓展，在一人可拥有多技能执照的行业有广泛的应用背景. 提出基于LPT算法思想的贪婪算法，并得出以下结论: k≤2, 该算法给出最优解: k>2, 最坏情况下的性能比为2-m-1, 这里m指待分配集合的数量.
|
| 关 键 词： | k-划分问题 元素类型约束 LPT 最坏情况性能比 |
| 收稿时间： | 2011-12-26 |
| 修稿时间： | 2012-06-07 |
k-partitioning problem with items' type restriction |
| |
| REN Qingjuan
,
XU Baoguang.k-partitioning problem with items' type restriction[J].OR Transactions,2012,16(3):93-99. |
| |
| Authors: | REN Qingjuan XU Baoguang |
| |
| Affiliation: | 1. Department of Management, University of Science and Technology of China 2. Institute of Policy and Management, Chinese Academy of Sciences |
| |
| Abstract: | 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. |
| |
| Keywords: | k-partitioning problem items' type restriction LPT worst-case performance ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
