Here we review the main results in the area of semi-on-line bin packing. Then we present a new lower bound for the asymptotic competitive ratio of any on-line bin packing algorithm which knows the optimum value in adv...
详细信息
Here we review the main results in the area of semi-on-line bin packing. Then we present a new lower bound for the asymptotic competitive ratio of any on-line bin packing algorithm which knows the optimum value in advance.
We are given a set of identical machines and a sequence of jobs, the sum of whose weights is known in advance. The jobs are to be assigned on-line to one of the machines and the objective is to minimize the makespan. ...
详细信息
We are given a set of identical machines and a sequence of jobs, the sum of whose weights is known in advance. The jobs are to be assigned on-line to one of the machines and the objective is to minimize the makespan. An algorithm with performance ratio 1.6 and a lower bound of 1.5 is presented. These results improve on the recent results by Azar and Regev, who proposed an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论