Standard

A Greedy Algorithm for Jobs Allocation in a Multiprocessor System. / Khutoretskii, Alexandre; Bredikhin, Sergei.

2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 82-85 8880192 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Khutoretskii, A & Bredikhin, S 2019, A Greedy Algorithm for Jobs Allocation in a Multiprocessor System. in 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019., 8880192, 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Institute of Electrical and Electronics Engineers Inc., pp. 82-85, 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Novosibirsk, Russian Federation, 26.08.2019. https://doi.org/10.1109/OPCS.2019.8880192

APA

Khutoretskii, A., & Bredikhin, S. (2019). A Greedy Algorithm for Jobs Allocation in a Multiprocessor System. In 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 (pp. 82-85). [8880192] (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/OPCS.2019.8880192

Vancouver

Khutoretskii A, Bredikhin S. A Greedy Algorithm for Jobs Allocation in a Multiprocessor System. In 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 82-85. 8880192. (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). doi: 10.1109/OPCS.2019.8880192

Author

Khutoretskii, Alexandre ; Bredikhin, Sergei. / A Greedy Algorithm for Jobs Allocation in a Multiprocessor System. 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 82-85 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

BibTeX

@inproceedings{347c6d687fae47d09745a7f98a953887,
title = "A Greedy Algorithm for Jobs Allocation in a Multiprocessor System",
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.",
keywords = "approximation algorithm, approximation ratio, lexicographic ordering, multiple knapsack problem",
author = "Alexandre Khutoretskii and Sergei Bredikhin",
note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 ; Conference date: 26-08-2019 Through 30-08-2019",
year = "2019",
month = aug,
doi = "10.1109/OPCS.2019.8880192",
language = "English",
series = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "82--85",
booktitle = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",
address = "United States",

}

RIS

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 -

ID: 23208984