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

Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (3): 93-99.

• Original Articles • Previous Articles Next Articles

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

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

CLC Number:

03E02

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

References

中国民用航空局飞行标准司. 客舱服务员服务机型数量限制评审指南,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.

k-partitioning problem with items' type restriction

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments