EFFICIENT GENERATION OF NEAR OPTIMAL INITIAL POPULATIONS TO ENHANCE GENETIC ALGORITHMS FOR JOB-SHOP SCHEDULING

Abstract

This paper presents an efficient method of enhancing genetic algorithms (GAs) for solving the Job-Shop Scheduling Problem (JSSP), by generating near optimal initial populations. Since the choice of the initial population has a high impact on the speed of the evolution and the quality of the final results, we focused on generating its individuals using genetically evolved priority dispatching rules. Our experiments show a significant increase in quality and speed of scheduling with GAs, and in some cases the evolved priority rules alone determined better solutions then the GA itself. The analyzed reference GA uses Giffler & Thompson (GT) heuristic and priority lists. To speed up the generation of priority rules, we have used a "weighted sum of priority rules" formula that revealed significantly better performances than Genetic Programming (GP). For evaluation of the proposed algorithm, the well known benchmark data sets from Fisher & Thompson (F&T) and Laurence Kramer (LA) have been used.