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

运筹学学报 ›› 2012, Vol. 16 ›› Issue (3): 93-99.

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

任庆娟^1,2, 许保光²

1. 中国科学技术大学
2. 中国科学院科技政策与管理科学研究所

收稿日期:2011-12-26 修回日期:2012-06-07 出版日期:2012-09-15 发布日期:2012-09-18
通讯作者: 任庆娟 E-mail:rqj21@126.com

k-partitioning problem with items' type restriction

REN Qingjuan^1,2, XU Baoguang²

1. Department of Management, University of Science and Technology of China 2. Institute of Policy and Management, Chinese Academy of Sciences

Received:2011-12-26 Revised:2012-06-07 Online:2012-09-15 Published:2012-09-18
Contact: REN Qingjuan E-mail:rqj21@126.com

摘要/Abstract

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

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

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.

Key words: k-partitioning problem, items' type restriction, LPT, worst-case performance ratio

中图分类号:

03E02

任庆娟,许保光. 有元素类型约束的k-划分问题研究[J]. 运筹学学报, 2012, 16(3): 93-99.

REN Qingjuan, XU Baoguang. k-partitioning problem with items' type restriction[J]. Operations Research Transactions, 2012, 16(3): 93-99.

参考文献

中国民用航空局飞行标准司. 客舱服务员服务机型数量限制评审指南,2010.

Dell'Amico M., Martello S. Bounds for the cardinality constrained P|.|C_{max} problem[J]. Journal of Scheduling, 2001, 4: 123-138.
Baker K.R. Introduction to Sequencing and Scheduling [M]. Wiley, New York, 1974,ISBN: 0471045551.
Graham R.L. Bounds on Multiprocessing Timing Anomalies [J]. SIAM Journal on Applied Mathematics, 1969, 17(2): 416-429.
Feo T., Goldschmidit O., Khellaf M. One-Half Approximation Algorithms for the k-Partition Problem[J]. Operations Research, 1992, 40(1): S170-S173.
Babel L., Kellerer H., Kotov V. The k-partitioning problem[J]. Mathematical Methods of Operations Research, 1998, 47(1): 59-82.

He Y., Tan Z.Y., Zhu J., Yao E. K-Partitioning problems for Maximizing the Minimum Load[J]. Computers and Mathematics with Applications, 2003, 46: 1671-1681.
Wu B., Yao E. K-Partitioning problems with partition matroid constraint[J]. Theoretical Computer Science, 2007, 374: 41-48.
Kellerer H., Woeginger G. A tight bound for 3-partitioning[J]. Discrete Applied Mathematics, 1993, 45: 249-259.

Michiel W., Korst J., Aarts E., Leeuwen J. Performance ratios for the differencing method applied to balanced number partition problem[J]. In Symposium on Theoretical Aspects of Computer Science, 2003, 583-595.
Zhang J.L., Kyrialos M, HweeHwa P. Heuristic Algorithms for Balanced Multi-Way Number Partitioning[J]. Proceeding of the Twenty-Second International Joint Conference on Artificial Intelligence, 2011, 693-698.

Dell'Amico M., Lori M., Martello S. Heuristic algorithms and scatter search for the cardinality constrained P|.|C_{max} problem [J]. Journal of Heuristics, 2004, 169-204.

Chi Z., Wang G., Liu X., Liu J. Approximating scheduling machines with capacity constraints[J]. in: Proceedings of the Third International Frontiers of Algorithmic Workshop, 2009, 283-292.

Saha B., Srinivasan A. A new approximation technique for resource-allocation problems[J]. in: Proceedings of the First Annual Symposium on Innovations in Computer Science, 2010, 342-357.

Kellerer H., Kotov V. A 3/2-approximation algorithm for k_{i}-partitioning[J]. Operations Research letters, 2011, 39: 359-362.