A Greedy Algorithm for Jobs Allocation in a Multiprocessor System

Alexandre Khutoretskii, Sergei Bredikhin

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages82-85
Number of pages4
ISBN (Electronic)9781728129860
DOIs
Publication statusPublished - Aug 2019
Event15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 - Novosibirsk, Russian Federation
Duration: 26 Aug 201930 Aug 2019

Publication series

Name2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Conference

Conference15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019
CountryRussian Federation
CityNovosibirsk
Period26.08.201930.08.2019

Keywords

  • approximation algorithm
  • approximation ratio
  • lexicographic ordering
  • multiple knapsack problem

Fingerprint

Dive into the research topics of 'A Greedy Algorithm for Jobs Allocation in a Multiprocessor System'. Together they form a unique fingerprint.

Cite this