RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Guidelines for authors License agreement Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Trudy MIAN: Year: Volume: Issue: Page: Find

 Tr. Mat. Inst. Steklova, 2002, Volume 239, Pages 323–331 (Mi tm377)

On the Geometry of Multiprocessor Distributions

E. V. Shchepin

Steklov Mathematical Institute, Russian Academy of Sciences

Abstract: 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.

Full text: PDF file (174 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2002, 239, 306–314

Bibliographic databases:
UDC: 519.17+519.85

Citation: E. V. Shchepin, “On the Geometry of Multiprocessor Distributions”, Discrete geometry and geometry of numbers, Collected papers. Dedicated to the 70th birthday of professor Sergei Sergeevich Ryshkov, Tr. Mat. Inst. Steklova, 239, Nauka, MAIK «Nauka/Inteperiodika», M., 2002, 323–331; Proc. Steklov Inst. Math., 239 (2002), 306–314

Citation in format AMSBIB
\Bibitem{Shc02} \by E.~V.~Shchepin \paper On the Geometry of Multiprocessor Distributions \inbook Discrete geometry and geometry of numbers \bookinfo Collected papers. Dedicated to the 70th birthday of professor Sergei Sergeevich Ryshkov \serial Tr. Mat. Inst. Steklova \yr 2002 \vol 239 \pages 323--331 \publ Nauka, MAIK «Nauka/Inteperiodika» \publaddr M. \mathnet{http://mi.mathnet.ru/tm377} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1975153} \zmath{https://zbmath.org/?q=an:1069.68031} \transl \jour Proc. Steklov Inst. Math. \yr 2002 \vol 239 \pages 306--314 

• http://mi.mathnet.ru/eng/tm377
• http://mi.mathnet.ru/eng/tm/v239/p323

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. E. V. Shchepin, “On the complexity of constructing multiprocessor little-preemptive schedules”, Proc. Steklov Inst. Math., 290:1 (2015), 166–177
•  Number of views: This page: 195 Full text: 72 References: 31