An Experienced Learning Genetic Algorithm To Solve The Single Machine Total Weighted Tardiness Scheduling Problem

摘要

In this paper, an experienced learning genetic algorithm (ELGA) is presented in an attempt to solve the single machine total weighted tardiness problem. In the proposed ELGA, a position-job and a job-job matrix, which can be updated over generations by using the exponential smoothing method, are used to build the relationships between jobs and positions according to information on the genes of chromosomes in the generation. Based on the dynamic matrices, an experienced learning (EL) heuristic is developed to produce some potential chromosomes for the GA. In order to evaluate the performance of the ELGA, the solutions obtained by the ELGA were compared with the best known solutions, which appeared on J.E. Beasley's OR-Library Web site. The computational results showed that the ELGA can obtain the best known solutions in a short time. Moreover, the ELGA is robust because one of the performance measures, the standard deviations of the percentage of relative difference in the solutions, is extremely smaller for all experimental runs.