УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта


јвтор:  „иркова ё. ¬.
Ќазвание:  ÷ена анархии в задаче максимизации минимальной задержки машин в системе обслуживани€
¬ыпуск:  62
–убрика:  —истемный анализ
√од:  2016
Ѕиблиографи€:  „иркова ё. ¬. ÷ена анархии в задаче максимизации минимальной задержки машин в системе обслуживани€ / ”правление большими системами. ¬ыпуск 62. ћ.: »ѕ” –јЌ, 2016. —.30-59.
 лючевые слова:  система обслуживани€, максимизаци€ минимальной задержки, равновесие по Ќэшу, цена анархии
 лючевые слова (англ.):  Nash equilibrium, cover, maximizing the minimum load, price of anarchy, selfish load balancing
јннотаци€:  »сследуетс€ игра максимизации минимальной задержки системы обслуживани€. »гроки распредел€ют свои задачи различного объема между машинами, различающимис€ скорост€ми обслуживани€.  аждый игрок стремитс€ минимизировать врем€ обслуживани€ своей задачи на выбранной им машине. ¬ыигрышем системы €вл€етс€ минимальна€ среди всех машин задержка. ќптимальным дл€ системы распределением задач по машинам €вл€етс€ такое, где максимизируетс€ наименьша€ среди всех машин задержка. ƒл€ общего случа€ N машин найдена нижн€€ граница цены анархии и дл€ случа€ трех машин найдено ее точное значение. ƒл€ двух машин доказано, что при добавлении в систему новой третьей машины цена анархии не измен€етс€ либо растет. “акже предложен алгоритм вычислени€ точного значени€ цены анархии на примере системы трех машин.
јннотаци€ (англ.):  The maximizing the minimum machine delay game with uniformly related machines is considered. Players choose machines with different speeds to run their jobs trying to minimize jobТs delay, i.e. chosen machineТs completion time. The social payoff is the minimal delay over all machines. For the general case of N machines we find the lower bound for Price of Anarchy (PoA), and for the case of 3 machines we find its exact value. We prove that the PoA either remains the same or increases when an additional third machine is included into the system with two machines. Also we propose a method of computation the PoA value and illustrate it for 3 machines.

в формате PDF
ќбсудить статью в »нтернет-конференции по проблемам управлени€

ѕросмотров: 1238, загрузок: 505, за мес€ц: 12.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены