This article is cited in 2 papers

A semi on-line algorithm for the partition problem

E. Girlikh, M. M. Kovalev, V. M. Kotov


Abstract: The distribution of jobs in a system with $m$ identical parallel processors which minimises the load of the maximally loaded processor is an NP-hard problem. Many approximate algorithms are developed for this problem, but for the version of the problem where the jobs arrive and must be treated on-line there is no algorithm possessing the guaranteed estimate which is less than $1+1/\sqrt 2$ for $m\geq 4$ and tends to $1{.}837$ as $m\to\infty$.
In this paper, we consider the version of the problem where jobs arrive one by one and must be treated on-line under the additional condition that the total duration of the jobs is known. For this version of the problem we suggest an algorithm with the guaranteed estimate equal to $5/3$.

UDC: 519.7

Received: 18.01.2001

DOI: 10.4213/dm222

 English version: Discrete Mathematics and Applications, 2003, 13:6, 619–625

Bibliographic databases:

• 
•