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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Liuyi Wang, Zongtao He, Chengju Liu, Qijun Chen
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2021
Materias:	Unbalanced assignment problem Assignment problem Ant colony algorithm Combinatorial optimization problem Mutation Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/1a1efaa1d7f541828267e57d6647c521
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:1a1efaa1d7f541828267e57d6647c521
record_format	dspace
spelling	oai:doaj.org-article:1a1efaa1d7f541828267e57d6647c5212021-11-22T04:29:20ZGraph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm2590-037410.1016/j.rinam.2021.100207https://doaj.org/article/1a1efaa1d7f541828267e57d6647c5212021-11-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2590037421000467https://doaj.org/toc/2590-0374In 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.Liuyi WangZongtao HeChengju LiuQijun ChenElsevierarticleUnbalanced assignment problemAssignment problemAnt colony algorithmCombinatorial optimization problemMutationMathematicsQA1-939ENResults in Applied Mathematics, Vol 12, Iss , Pp 100207- (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Unbalanced assignment problem Assignment problem Ant colony algorithm Combinatorial optimization problem Mutation Mathematics QA1-939
spellingShingle	Unbalanced assignment problem Assignment problem Ant colony algorithm Combinatorial optimization problem Mutation Mathematics QA1-939 Liuyi Wang Zongtao He Chengju Liu Qijun Chen Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm
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.
format	article
author	Liuyi Wang Zongtao He Chengju Liu Qijun Chen
author_facet	Liuyi Wang Zongtao He Chengju Liu Qijun Chen
author_sort	Liuyi Wang
title	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_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_sort	graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm
publisher	Elsevier
publishDate	2021
url	https://doaj.org/article/1a1efaa1d7f541828267e57d6647c521
work_keys_str_mv	AT liuyiwang graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm AT zongtaohe graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm AT chengjuliu graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm AT qijunchen graphbasedtwincostmatricesforunbalancedassignmentproblemwithimprovedantcolonyalgorithm
_version_	1718418147355131904

Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm

Ejemplares similares