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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Trans Tech Publications, Switzerland
2014
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/6671/1/fkp-2014-noraini-process_sequencing_model_abs_only.pdf |
| _version_ | 1825821815058989056 |
|---|---|
| author | N. M., Razali |
| author_facet | N. M., Razali |
| author_sort | N. M., Razali |
| collection | UMP |
| 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. |
| first_indexed | 2024-03-06T11:47:13Z |
| format | Article |
| id | UMPir6671 |
| institution | Universiti Malaysia Pahang |
| language | English |
| last_indexed | 2024-03-06T11:47:13Z |
| publishDate | 2014 |
| publisher | Trans Tech Publications, Switzerland |
| record_format | dspace |
| spelling | UMPir66712015-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. (Published) http://www.scientific.net/AMM.575.843 DOI: 10.4028/www.scientific.net/AMM.575.843 |
| spellingShingle | QA75 Electronic computers. Computer science N. M., Razali Process Sequencing Modeled as TSP with Precedence Constraints - A Genetic Algorithm Approach |
| title | 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_short | 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 |
| topic | QA75 Electronic computers. Computer science |
| url | http://umpir.ump.edu.my/id/eprint/6671/1/fkp-2014-noraini-process_sequencing_model_abs_only.pdf |
| work_keys_str_mv | AT nmrazali processsequencingmodeledastspwithprecedenceconstraintsageneticalgorithmapproach |