Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm
In this paper, we are interested in the unbalanced assignment problem with constraints to agents. The modified Hungarian algorithm with dummy tasks and agents are most common methods to solve the unbalanced problem. However, it is impractical in the real scenarios sometimes since some tasks are unas...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2021-11-01
|
| Series: | Results in Applied Mathematics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2590037421000467 |
| _version_ | 1818856527518236672 |
|---|---|
| author | Liuyi Wang Zongtao He Chengju Liu Qijun Chen |
| author_facet | Liuyi Wang Zongtao He Chengju Liu Qijun Chen |
| author_sort | Liuyi Wang |
| collection | DOAJ |
| description | In this paper, we are interested in the unbalanced assignment problem with constraints to agents. The modified Hungarian algorithm with dummy tasks and agents are most common methods to solve the unbalanced problem. However, it is impractical in the real scenarios sometimes since some tasks are unassigned actually using the above method. Instead, we propose a graph based twin cost matrices method with improved ant colony optimization algorithm to solve the assignment problem elegantly and uniformly. We start from the generation of the twin cost matrices, and modify the ant colony algorithm to be capable to assign tasks to agents with different numbers. Random mutation is conducted for the stable pheromones to help the ant colony keep diversity during the operation. Experiments demonstrates that using our proposed method to solve the unbalanced assignment problem can stably obtain better results than previous methods. |
| first_indexed | 2024-12-19T08:25:55Z |
| format | Article |
| id | doaj.art-1a1efaa1d7f541828267e57d6647c521 |
| institution | Directory Open Access Journal |
| issn | 2590-0374 |
| language | English |
| last_indexed | 2024-12-19T08:25:55Z |
| publishDate | 2021-11-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Results in Applied Mathematics |
| spelling | doaj.art-1a1efaa1d7f541828267e57d6647c5212022-12-21T20:29:17ZengElsevierResults in Applied Mathematics2590-03742021-11-0112100207Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithmLiuyi Wang0Zongtao He1Chengju Liu2Qijun Chen3Department of Control Science and Engineering, Tongji University, Shanghai, 201804, ChinaDepartment of Control Science and Engineering, Tongji University, Shanghai, 201804, ChinaCorresponding author.; Department of Control Science and Engineering, Tongji University, Shanghai, 201804, ChinaDepartment of Control Science and Engineering, Tongji University, Shanghai, 201804, ChinaIn this paper, we are interested in the unbalanced assignment problem with constraints to agents. The modified Hungarian algorithm with dummy tasks and agents are most common methods to solve the unbalanced problem. However, it is impractical in the real scenarios sometimes since some tasks are unassigned actually using the above method. Instead, we propose a graph based twin cost matrices method with improved ant colony optimization algorithm to solve the assignment problem elegantly and uniformly. We start from the generation of the twin cost matrices, and modify the ant colony algorithm to be capable to assign tasks to agents with different numbers. Random mutation is conducted for the stable pheromones to help the ant colony keep diversity during the operation. Experiments demonstrates that using our proposed method to solve the unbalanced assignment problem can stably obtain better results than previous methods.http://www.sciencedirect.com/science/article/pii/S2590037421000467Unbalanced assignment problemAssignment problemAnt colony algorithmCombinatorial optimization problemMutation |
| spellingShingle | Liuyi Wang Zongtao He Chengju Liu Qijun Chen Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm Results in Applied Mathematics Unbalanced assignment problem Assignment problem Ant colony algorithm Combinatorial optimization problem Mutation |
| title | Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm |
| title_full | Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm |
| title_fullStr | Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm |
| title_full_unstemmed | Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm |
| title_short | Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm |
| title_sort | graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm |
| topic | Unbalanced assignment problem Assignment problem Ant colony algorithm Combinatorial optimization problem Mutation |
| url | http://www.sciencedirect.com/science/article/pii/S2590037421000467 |
| work_keys_str_mv | AT liuyiwang graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm AT zongtaohe graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm AT chengjuliu graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm AT qijunchen graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm |