Geodesic
On the Geometry of Multiprocessor Distributions
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Discrete geometry and geometry of numbers, Tome 239 (2002), pp. 323-331
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

An algorithm for solving the linear programming problem known as the multiprocessor distribution (or scheduling) problem is suggested. The problem is to distribute a given set of tasks among given processors so as to minimize the load time of the most loaded processor. Dividing the tasks into parts and distributing the parts among different processors is allowed. The algorithm constructed uses the specifics of the multiprocessor distribution problem and can therefore operate substantially more efficiently than the general linear programming algorithm. The author was unable to answer the question about the polynomiality of the algorithm. 
@article{TM_2002_239_a21,
     author = {E. V. Shchepin},
     title = {On the {Geometry} of {Multiprocessor} {Distributions}},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {323--331},
     year = {2002},
     volume = {239},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2002_239_a21/}
}
TY  - JOUR
AU  - E. V. Shchepin
TI  - On the Geometry of Multiprocessor Distributions
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2002
SP  - 323
EP  - 331
VL  - 239
UR  - http://geodesic.mathdoc.fr/item/TM_2002_239_a21/
LA  - ru
ID  - TM_2002_239_a21
ER  - 
%0 Journal Article
%A E. V. Shchepin
%T On the Geometry of Multiprocessor Distributions
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2002
%P 323-331
%V 239
%U http://geodesic.mathdoc.fr/item/TM_2002_239_a21/
%G ru
%F TM_2002_239_a21
E. V. Shchepin. On the Geometry of Multiprocessor Distributions. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Discrete geometry and geometry of numbers, Tome 239 (2002), pp. 323-331. http://geodesic.mathdoc.fr/item/TM_2002_239_a21/

[1] Papadimitriu Kh., Staiglits K., Kombinatornaya optimizatsiya. Algoritmy i slozhnost, Mir, M., 1985 | MR

[2] Potts C. N., “Analysis of a linear programming heuristic for scheduling unrelated parallel machines”, Discr. Appl. Math., 10 (1985), 155–164 | DOI | MR | Zbl

[3] Shchepin E. V., Vakhania N., “Task distributions on multiprocessor systems”, Lect. Notes Comput. Sci., 187, 2000, 112–125

[4] Lenstra J. K., Shmoys D. B., Tardos E., “Approximation algorithms for scheduling unrelated parallel machines”, Math. Programm. A., 46 (1990), 259–271 | DOI | MR | Zbl

[5] Plotkin S. A., Shmoys D. B., Tardos E., “Fast appproximation algorithms for fractional packing and covering problems”, Math. Oper. Res., 20:2 (1995), 257–301 | DOI | MR | Zbl