Geodesic
A~semi on-line algorithm for the partition problem
Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 133-140.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 
@article{DM_2003_15_4_a9,
     author = {E. Girlikh and M. M. Kovalev and V. M. Kotov},
     title = {A~semi on-line algorithm for the partition problem},
     journal = {Diskretnaya Matematika},
     pages = {133--140},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/}
}
TY  - JOUR
AU  - E. Girlikh
AU  - M. M. Kovalev
AU  - V. M. Kotov
TI  - A~semi on-line algorithm for the partition problem
JO  - Diskretnaya Matematika
PY  - 2003
SP  - 133
EP  - 140
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/
LA  - ru
ID  - DM_2003_15_4_a9
ER  - 
%0 Journal Article
%A E. Girlikh
%A M. M. Kovalev
%A V. M. Kotov
%T A~semi on-line algorithm for the partition problem
%J Diskretnaya Matematika
%D 2003
%P 133-140
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/
%G ru
%F DM_2003_15_4_a9
E. Girlikh; M. M. Kovalev; V. M. Kotov. A~semi on-line algorithm for the partition problem. Diskretnaya Matematika, Tome 15 (2003) no. 4, pp. 133-140. http://geodesic.mathdoc.fr/item/DM_2003_15_4_a9/

[1] Graham R. L., “Bounds for certain multiprocessor anomalies”, Bell System Tech., 45 (1966), 1563–1581

[2] Graham R. L., Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17, 1969 | MR

[3] Coffman E. G., Garey M. R., Johnson D. S., “An application of bin-packing to multiprocessor scheduling”, SIAM J. Comput., 7 (1978), 1–17 | DOI | MR | Zbl

[4] Hochbaum D. S., Shmoys D., “Using dual appriximation algorithms for scheduling problems: theoretical and practical results”, J. ACM, 34 (1987), 144–162 | DOI | MR

[5] Bartal Y., Karloff H., Rabany Y., Inform. Process. Lett., 50 (1994), 113–116 | DOI | MR | Zbl

[6] Faigle U., Kern W., Turán G., “On the performance of on-line algorithms for particular problems”, Acta Cycern., 9 (1989), 107–119 | MR | Zbl

[7] Albers S., “Better bounds for online scheduling”, Proc. 29th Annual ACM Symp. Theory Computing, 1997, 130–139 | MR

[8] Grove E. F., “Online binpacking problem with lookahead”, Proc. 6th Annual ACM–SIAM Symp. Discrete Algorithms, 1995, 430–436 | Zbl

[9] Mao W., Kincaid R. K., “A look-ahead heuristic for scheduling jobs with release dates on a single machine”, Comp. Operat. Res., 10 (1994), 1041–1050 | DOI | Zbl

[10] Kellerer H., Kotov V., Speranza M. G., Tuza Z., “Semi on-line algorithms for the partition problem”, Operat. Res. Lett., 21 (1997), 235–242 | DOI | MR | Zbl