Adding problem-specific knowledge in evolutionary algorithms to solve W-T scheduling problems

Abstract

In a production system it is usual to stress minimum tardiness to achieve higher client satisfaction. According to the client relevance, job processing costs and requirements, and various other considerations, a weight is assigned to each job. An important, non-trivial, problem is to minimize weighted tardiness. Evolutionary algorithms (EAs) have been proved as efficient tools to solve scheduling problems. Latest improvements in EAs have been developed by means of multirecombination, a method which allows multiple exchange of genetic material between individuals of the mating pool. As EAs are blind search methods this paper proposes to insert problem-specific-knowledge by recombining potential solutions (individuals of the evolving population) with seeds, which are solutions provided by other heuristics specifically intended to solve the scheduling problem under study. In this work we describe two main approaches where seeds are inserted either in the initial population or as a part of every mating pool during evolution. Both methods were contrasted for a set of problem instances extracted from the OR-Library. An outline of the weighted tardiness problem in a single machine environment, details of implementation and results are discussed.