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

• Original Articles • Previous Articles     Next Articles

k-partitioning problem with items' type restriction

REN Qingjuan1,2, XU Baoguang2   

  1. 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: 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: