TY - GEN

T1 - A Greedy Algorithm for Jobs Allocation in a Multiprocessor System

AU - Khutoretskii, Alexandre

AU - Bredikhin, Sergei

N1 - Publisher Copyright: © 2019 IEEE.

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

KW - approximation algorithm

KW - approximation ratio

KW - lexicographic ordering

KW - multiple knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=85078044075&partnerID=8YFLogxK

U2 - 10.1109/OPCS.2019.8880192

DO - 10.1109/OPCS.2019.8880192

M3 - Conference contribution

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

SP - 82

EP - 85

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

PB - Institute of Electrical and Electronics Engineers Inc.

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

Y2 - 26 August 2019 through 30 August 2019

ER -