TY - CONF

T1 - Allocating Indivisible Jobs in a Multiprocessor System

AU - Хуторецкий, Александр Борисович

AU - Бредихин, Сергей

N1 - Параллельные вычислительные техноло-гии – XIII международная конференция, ПаВТ'2019, г. Калининград, 2–4 апреля 2019 г. Короткие статьи и описания пла-катов. Челябинск: Издательский центр ЮУрГУ, 2019. 477 с. ISBN 978-5-696-05020-1. С. 444. [Электронный ресурс] URL: http://omega.sp.susu.ru/pavt2019/poster.html

PY - 2019

Y1 - 2019

N2 - We study the problem of distribution a multiprocessor system computing capacity over a fixed time period between jobs. Processors differ by speed; jobs differ by processing time and value. Assuming that jobs are indivisible (preemptions are prohibited), the problem of maximizing the total value of allocated jobs is equivalent to the multiple knapsack problem. In the report, a greedy allocation algorithm is proposed. The relative performance guarantee of the algorithm is 0.5, and its running-time is O(mn), where m is the number of jobs and n is the number of processors.

AB - We study the problem of distribution a multiprocessor system computing capacity over a fixed time period between jobs. Processors differ by speed; jobs differ by processing time and value. Assuming that jobs are indivisible (preemptions are prohibited), the problem of maximizing the total value of allocated jobs is equivalent to the multiple knapsack problem. In the report, a greedy allocation algorithm is proposed. The relative performance guarantee of the algorithm is 0.5, and its running-time is O(mn), where m is the number of jobs and n is the number of processors.

M3 - Poster

SP - 444

EP - 444

ER -