You are here: Home :: Area NEM :: Mathematics

E. Girlich, M. M. Kovalev, V. M. Kotov

A semi on-line algorithm for the partition problem

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/√2 for m ≥ 4 and tends to 1.837 as m → ∞.

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.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 13, 12/2003
Pages: 619 - 625

Show full article (external site)

Show all available items of this journal

 

Area NEM