Solving the assignment problem using genetic algorithm and simulated annealing

被引：0

作者：

Sahu, Anshuman ^{[1
]}

Tapadar, Rudrajit ^{[2
]}

机构：

[1] Motilal Nehru Natl Inst Technol, Prod & Ind Engn, Allahabad, Uttar Pradesh, India

[2] Motilal Nehru Natl Inst Technol, Comp Sci & Engn, Allahabad, Uttar Pradesh, India

来源：

IMECS 2006: INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS | 2006年

关键词：

assignment problem; genetic algorithm; Newtonian cooling schedule; partially matched crossover (PMX); simulated annealing;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The paper attempts to solve the generalized "Assignment problem" through genetic algorithm and simulated annealing. The generalized assignment problem is basically the "N men- N jobs" problem where a single job can be assigned to only one person in such a way that the overall cost of assignment is minimized. While solving this problem through genetic algorithm (GA), a unique encoding scheme is used together with Partially Matched Crossover (PMX). The population size can also be varied in each iteration. In simulated annealing (SA) method, an exponential cooling schedule based on Newtonian cooling process is employed and experimentation is done on choosing the number of iterations (in) at each step. The source codes for the above have been developed in C language and compiled in GCC. Several test cases have been taken and the results obtained from both the methods have been tabulated and compared against the results obtained by coding in AMPL.

引用

页码：762 / +

页数：2