Performances of List Scheduling for Set Partition Problems

吳邦一(Bang-Ye Wu) ； 歐秀慧(Hsiu-Hui Ou)

《Journal of Information Science and Engineering》 23卷2期 (2007/03) Pp. 641-647

https://doi.org/10.6688/JISE.2007.23.2.18

並列摘要

An m-partition of a set is a way to distribute the members into m parts. Given a set of positive numbers, an optimal m-partition problem asks for an m-partition optimizing some objective function. List scheduling is an on-line algorithm that has been widely used in scheduling problems. In this paper, we show the tight bounds on the performances of list scheduling for partition problems with the following objective functions: maximizing the minimum part, maximizing the sum of the smallest k parts, minimizing the sum of the largest k parts, and minimizing the ratio of the largest to the smallest part, in which 1≤k＜m.

並列關鍵字

analysis of algorithms ； approximation algorithms ； list scheduling ； partitions ； optimization problems