| Abstract: | This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time. |
