University of Leicester


Genetic Algorithms in Combinatorial Optimisation

Associated Researchers: Dr. S. Yang.

A Genetic Algorithm (GA) is an adaptive search technique based on the principles of natural evolution. GAs iteratively apply genetic operators for selection, crossover, mutation and reproduction on a given population to improve its average fitness generation by generation. GAs have been successfully used to solve many combinatorial optimization problems, such as the Traveling Salesman Problem (TSP), the Assignment problem, and the Knapsack problem.

Our research in this area is primarily concerned with using GAs and other heristic algorithms to solve different combinatorial optimization problems, especially the production scheduling problems. Production scheduling is the allocation of resources over time to perform a collection of tasks. Of all kinds of production scheduling problems, the Job Shop Scheduling problem (JSS) is one of the most complicated and typical. It aims to allocate a given set of machines to precess a given set of jobs with certain restrict constraints in order to optimize certain criterion. Usually JSS problem is NP-complete, it is very hard to find its optimal solution. Researchers have turned to search its near-optimal solutions with all kind of hybrid heuristic algorithms. Our present research focuses on combining GAs with other approaches, such as Simulated Annealing (SA), Tabu Search (TS), and Neural Network, to solve the JSS problem and the Open Shop Scheduling problem.

This work comes under the general heading of Algorithm Engineering.

University of Leicester 15th December 2000. Last modified: 6th August 2003, 13:13:46.
Informatics Web Maintainer. This document has been approved by the Head of Department.