Evolutionary algorithms whit studs and random immigrants to solve E/T scheduling problems

Abstract

The study of earliness and tardiness penalties in scheduling is a relatively recent area of research. In the past, traditionally the emphasis was put on regular measures that are nondecreasing in job completion times such as makespan, mean lateness, percentage of tardy jobs or mean tardiness. Current trends in manufacturing is focussed in just-in-time production which emphasize policies discouraging earliness as well as tardiness. Evolutionary algorithms have been successfully applied to solve scheduling problems. New trends to enhance evolutionary algorithms introduced (MCMP) a multirecombinative approach allowing multiple-crossovers-on-multiple-parents (more than two) parents. MCMP-SRI is a novel MCMP variant, which considers the inclusion of a stud-breeding individual in a pool of random immigrant parents. Members of this mating pool subsequently undergo multiple crossover operations. This paper describes implementation details and the performance of MCMP-SRI for a set of single machine scheduling instances with a common due date.