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 algo...

Full description

Bibliographic Details
Main Author:	N. M., Razali
Format:	Article
Language:	English
Published:	Trans Tech Publications, Switzerland 2014
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://umpir.ump.edu.my/id/eprint/6671/ http://umpir.ump.edu.my/id/eprint/6671/ http://umpir.ump.edu.my/id/eprint/6671/ http://umpir.ump.edu.my/id/eprint/6671/1/fkp-2014-noraini-process_sequencing_model_abs_only.pdf

id	ump-6671
recordtype	eprints
spelling	ump-66712015-03-03T09:31:54Z http://umpir.ump.edu.my/id/eprint/6671/ Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach N. M., Razali QA75 Electronic computers. Computer science 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. Trans Tech Publications, Switzerland 2014-04-04 Article PeerReviewed application/pdf en http://umpir.ump.edu.my/id/eprint/6671/1/fkp-2014-noraini-process_sequencing_model_abs_only.pdf 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 http://www.scientific.net/AMM.575.843 DOI: 10.4028/www.scientific.net/AMM.575.843
repository_type	Digital Repository
institution_category	Local University
institution	Universiti Malaysia Pahang
building	UMP Institutional Repository
collection	Online Access
language	English
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science N. M., Razali Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach
description	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.
format	Article
author	N. M., Razali
author_facet	N. M., Razali
author_sort	N. M., Razali
title	Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach
title_short	Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach
title_full	Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach
title_fullStr	Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach
title_full_unstemmed	Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach
title_sort	process sequencing modeled as tsp with precedence constraints - a genetic algorithm approach
publisher	Trans Tech Publications, Switzerland
publishDate	2014
url	http://umpir.ump.edu.my/id/eprint/6671/ http://umpir.ump.edu.my/id/eprint/6671/ http://umpir.ump.edu.my/id/eprint/6671/ http://umpir.ump.edu.my/id/eprint/6671/1/fkp-2014-noraini-process_sequencing_model_abs_only.pdf
first_indexed	2023-09-18T22:02:39Z
last_indexed	2023-09-18T22:02:39Z
_version_	1777414501509890048

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

Similar Items