SIMULATED ANNEALING ALGORITHMS FOR OPERATION SEQUENCING IN PROCESS PLANNING

摘要

This paper focuses on the operation sequencing problem in process planning, which is thernproblem of determining the sequence of operations required for producing a part with the objective ofrnminimizing the sum of machine, setup and tool change costs. In general, the problem hasrncombinatorial characteristics and complex precedence relations, which makes the problem difficult tornsolve. In this paper, four simulated annealing algorithms, which are different in neighborhoodrngeneration method and local search type, are suggested to obtain good solutions within a reasonablernamount of computation time. Here, the suggested algorithms are combinations of two levels ofrnneighborhood generation methods, i.e., interchange and insertion methods, and two levels of localrnsearch types, i.e., random and best types. To show the performances of the four algorithms,rncomputational experiments were done on randomly generated test problems, and the results show thatrnthe best type algorithms are much better than the random type ones. Also, they give near optimalrnsolutions for small sized problems within a very short computation times.