Authors
Paulo M França, Alexandre Mendes, Pablo Moscato
Publication date
2001/7/1
Journal
European Journal of Operational Research
Volume
132
Issue
1
Pages
224-242
Publisher
North-Holland
Description
In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics.
Total citations
Scholar articles
PM França, A Mendes, P Moscato - European Journal of Operational Research, 2001