Solving combinatorial optimization problem by using genetic algorithm

S. Abdull-Raza, Tariq

	Solving combinatorial optimization problem by using genetic algorithm
Al-Mustansiriyah Journal of Science
Article 1, Volume 21, Issue 6, 2010, Pages 342-362
Author
Tariq S. Abdull-Raza
Abstract
Many sequencing problems have a combinatorial nature and they are very difficult to solve the optimality within acceptable computation times. When a near optimal solution is acceptable, it is appropriate to use heuristic methods. In this work we consider the problem of scheduling n jobs on a single machine to minimize the total cost of earliness, tardiness, completion time and the number of late jobs . This problem is NP-hard; hence the existence of a polynomial time algorithm for finding an optimal solution is unlikely. In this paper we propose a branch and bound algorithm to solve this problem. The BAB procedure uses dominance properties to reduce the number of sequences that must be considered. Also, we prove some special cases of the problem which leads to optimal solutions. We also apply some local search methods such as: Variable Neighborhood Search (VNS), Simulation Annealing (SA) algorithm, Genetic Algorithm (GA) and hybrid Genetic Algorithm (HGA). Performance of these heuristic methods is evaluated on a large set of test problems; it seems that the performance of (HGA) is the best.

Statistics Article View: 121 PDF Download: 26