Distributed Algorithm for Solving the Bottleneck Assignment Problem
| Autor: | Chris Manzie, Mitchell Khoo, Tony A. Wood, Iman Shames |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Computer science Multi-agent system 02 engineering and technology Bottleneck 020901 industrial engineering & automation Distributed algorithm 0202 electrical engineering electronic engineering information engineering Task analysis Bipartite graph 020201 artificial intelligence & image processing Resource management Greedy algorithm Assignment problem |
| Zdroj: | CDC |
| DOI: | 10.1109/cdc40024.2019.9028897 |
| Popis: | Assignment problems are found in multiagent systems, where there is a need to allocate multiple tasks to agents. The bottleneck assignment problem (BAP) is an assignment problem where the objective is to minimise the worst individual cost in the assignment. Distributed algorithms for assignments with other objectives have been proposed, yet to date no distributed algorithm for the BAP exists. This paper addresses this gap; we develop a novel distributed algorithm that solves the BAP optimally. The algorithm does not require a centralised decision-maker having access to all information from each agent, which is an advantage over existing algorithms for solving the BAP. We use numerical simulations to compare the optimality of the proposed algorithm against a greedy assignment-finding algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|