Genetic algorithm for process sequencing modelled as the travelling salesman problem with precedence constraints

This thesis addresses process sequencing subject to precedence constraints which arises as a subproblem in scheduling, planning and routing problems. The process sequencing problem can be modelled as the Travelling Salesman Problem with Precedence Constraints (TSPPC). In the general Travelling Salesman Problem (TSP) scenario, the salesman must travel from city to city; visiting each city exactly once and wishes to minimize the total distance travelled during the tour of all cities. TSPPC is similar in concept to TSP, except that it has a set of precedence constraints to be followed by the salesman. The exact methods that are used to find an optimal solution of the problem are only capable of handling small and medium sizes of instances. Genetic algorithms (GA) are heuristic optimization techniques based on the principles and mechanisms of natural evolution and can be used to solve larger instances and numerous side constraints with optimal or near-optimal solutions. However, the use of a conventional genetic algorithm procedure for TSP, with an order-based representation, might generate invalid candidate solutions when precedence constraints are involved. In this thesis, a new GA procedure is developed which includes chromosome’s repairing strategy based topological sort to handle the precedence constraints and to generate only feasible solution during the evolutionary process. The procedure to select the task in sequence is based on the “earliest position” techniques. This procedure is combined with a roulette wheel selection, linear order crossover and inversion mutation. The effectiveness and the stability of the proposed GA are then evaluated against a wide range of benchmark problems and the solutions are compared with the results obtained from research results published in the relevant literature. The results from the computational experiments demonstrate that the proposed GA procedure developed in this thesis is capable to tackle large-size problem and reach for optimal solutions. The developed GA procedure improved the performance of the algorithm with less number of generations and less convergence time in achieving optimal solutions. The genetic operators used are capable to always introduce new fitter offspring and free from being trapped in a local optimum. Therefore it can be stated that the proposed genetic algorithm is efficient to solve process sequencing modelled as the travelling salesman problem with precedence constraints. This result will greatly help to solve many real world sequencing problems especially in the field of assembly line design and management