An improved TSP with precedence constraint algorithm for assembly line sequencing problem / Mohd Fadzil Faisae Bin Ab. Rashid

Thesis (Master of Engineering (Manufacturing)) -- Universiti Malaysia Pahang - 2007

Traveling salesman problem with precedence constraint (TSPPC) involves finding an optimal route for visiting a number of cities exactly once by following a set of precedence constraint. In manufacturing, TSPPC can be used to model assembly line sequencing problem. The existing algorithms are incapable to solve TSPPC because complexity of precedence constraint. Using the existing algorithms, the optimal solution to the TSPPC cannot be obtained within reasonable computational time for large size problem. The main research objective is to propose an efficient algorithm to solve TSPPC. The algorithm must be efficient to generate optimal solution with less number of generations. Moreover, the algorithm must also have faster iteration time which will provide the optimal solution in a shorter time. The existing algorithm generate priority factor instead of sequence of solution as chromosome. As a result, the process of searching optimal solution becomes more difficult because of unpredictable changes of sequence when a particular string in chromosome is changed. Different with existing algorithm, the proposed algorithm directly generates sequence of solution as chromosome. Therefore, the optimal solution is easier to be generated because genetic algorithm directly being applied on sequence of solution. The proposed algorithm is compared with two existing algorithms through computer numerical experiments in term of number of generation and iteration time to generate optimal solution. All algorithms are coded into computer using MAT LAB Version 7.0. The performance of algorithms is tested on three case studies involving process sequencing problem. Compare with existing algorithm, numerical experiment results show that the proposed algorithm was able to generate optimal solution with less number of generations between 36.5% until 87.5% for the three case studies. The iteration time were also reduced between 58.2% until 98.2%. As a conclusion, an efficient algorithm to solve TSPPC was successfully developed and tested. The proposed algorithm will greatly help solving TSPPC, especially for assembly line sequencing problem. -Author