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

N. M., Razali (2014) Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach. Applied Mechanics and Materials, 575. pp. 843-847. ISSN 1662-7482. (Published)


Download (547kB)


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.

Item Type: Article
Additional Information: Dr. Noraini Mohd Razali (N.M. Razali)
Uncontrolled Keywords: Genetic Algorithm (GA); Precedence constraints; Process sequencing; Traveling salesman problem
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty/Division: Faculty of Manufacturing Engineering
Depositing User: Dr Noraini Mohd Razali
Date Deposited: 26 Sep 2014 05:56
Last Modified: 03 Mar 2015 09:31
Download Statistic: View Download Statistics

Actions (login required)

View Item View Item