The equilibrium generalized assignment problem and genetic algorithm |
| |
Authors: | Linzhong Liu Haibo MuYubo Song Haiyan LuoXiaojing Li Fang Wu |
| |
Institution: | a School of Traffic & Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China b Mechatronic Technology Institute, Lanzhou Jiaotong University, Lanzhou 730070, China |
| |
Abstract: | The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP. |
| |
Keywords: | Assignment problem Equilibrium optimization Generalized assignment problem Genetic algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|