A memetic algorithm for the total tardiness single machine scheduling problem

A memetic algorithm for the total tardiness single machine scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20021165
Country: Netherlands
Volume: 132
Issue: 1
Start Page Number: 224
End Page Number: 242
Publication Date: Jul 2001
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.