Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach

This study addresses process sequencing subject to precedence constraints which arises as a sub-problem in scheduling, planning and routing problems. The process sequencing problem can be modeled as the travelling salesman problem with precedence constraints (TSPPC). In this study a new genetic algorithm (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 “earliest position” techniques. This procedure is combined with roulette wheel selection, linear order crossover and inversion mutation. The effectiveness and the stability of the proposed GA are then evaluated against benchmark problems and the solutions are compared with the results obtained from research results published in the relevant literature. The developed GA procedure improved the performance of the algorithm with less number of generations and less convergence time in achieving optimal solutions. This result will greatly help to solve many real world sequencing problems especially in the field of assembly line design and management