A 3/2-approximation algorithm for k(i)-partitioning

作者：Kellerer Hans^*; Kotov Vladimir

来源：Operations Research Letters, 2011, 39(5): 359-362.

DOI：10.1016/j.orl.2011.06.005

• Scheduling
• Parallel machines
• Partition problem
• Worst-case analysis

We consider the multiprocessor scheduling problem with the objective of minimizing the makespan such that the number of items on each machine does not exceed a machine dependent cardinality limit. We present an elementary approximation algorithm with worst-case performance ratio 3/2 and running time linear in the number of items.

• 出版日期2011-9