Scientific publications

Chirkova J.V.

Maximizing the Minimum Processor Load with Linear Externalities

// Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2021. Communications in Computer and Information Science, vol 1476. Springer, Cham. Strekalovsky A., Kochetov Y., Gruzdeva T., Orlov A. (eds), 2021. Pp. 147-162

Keywords: Nash equilibrium, Cover, Maximizing the minimum load, Price of anarchy, Linear externalities

We consider the maximizing the minimum processor delay game on uniformly related processors with linear externalities. Externalities allow taking into account the influence of all loaded processors on each processor performance, unlike the model without externalities this problem has not been considered before. A set of jobs is to be assigned to a set of processors with different delay functions depending on their own loads and also loads on other processors. Jobs choose processors to minimize their own delays, while the system the social payoff of a schedule is the minimum delay among all processors, i.e. cover. For the case of two processors in this model the Nash equilibrium existence is proven and the expression for the Price of Anarchy is obtained. Also we show that the Price of Anarchy is limited in contrast to the initial model without externalities.

URL: https://link.springer.com/chapter/10.1007%2F978-3-030-86433-0_10

DOI: 10.1007/978-3-030-86433-0_10

Indexed at Scopus

Last modified: September 30, 2022