A Greedy Algorithm for Jobs Allocation in a Multiprocessor System

Alexandre Khutoretskii, Sergei Bredikhin

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

We present a greedy 0.5-approximation algorithm for allocation indivisible jobs in a multiprocessor system. The algorithm uses an ordering of processors according to the non-decreasing of size, and two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/ size ratio. These orderings create two lexicographic orderings on the set I × J (here I is the set of jobs and J is the set of processors). Based on these lexicographic orderings, the algorithm creates an admissible allocation by looking through the pairs (i,j) ∈ I × J in the corresponding order and allocating the job i to processor j if this job is not allocated yet and can be allocated to processor j. The algorithm chooses the best of the two obtained solutions. This algorithm is 0.5-approximate and has running time O(mn) (without sorting), where m and n are the sizes of the sets I and J correspondingly.

Язык оригиналаанглийский
Название основной публикации2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
ИздательInstitute of Electrical and Electronics Engineers Inc.
Страницы82-85
Число страниц4
ISBN (электронное издание)9781728129860
DOI
СостояниеОпубликовано - авг 2019
Событие15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 - Novosibirsk, Российская Федерация
Продолжительность: 26 авг 201930 авг 2019

Серия публикаций

Название2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Конференция

Конференция15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
СтранаРоссийская Федерация
ГородNovosibirsk
Период26.08.201930.08.2019

Fingerprint Подробные сведения о темах исследования «A Greedy Algorithm for Jobs Allocation in a Multiprocessor System». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать