Genetic Algorithm for the Single Machine Total Weighted Tardiness Problem

Author

Ferrolho, Antonio ; Crisostomo, Manuel

Author_Institution

Dept. of Electr. Eng., Superior Sch. of Technol. of Viseu

fYear

2006

fDate

18-20 Dec. 2006

Firstpage

17

Lastpage

22

Abstract

Genetic algorithms can provide good solutions for scheduling problems. In this paper we present a genetic algorithm to solve the single machine total weighted tardiness problem, a scheduling problem which is known to be NP-hard. First, we present a new concept of genetic operators for scheduling problems. Then, we present a developed software tool, called HybFlexGA, to examine the performance of various crossover and mutation operators by computing simulations of scheduling problems. Finally, the best genetic operators obtained from our computational tests are applied in the HybFlexGA. The computational results obtained with 40, 50 and 100 jobs show the good performance and the efficiency of the developed HybFlexGA

Keywords

computational complexity; genetic algorithms; scheduling; HybFlexGA; NP-hard problem; genetic algorithm; scheduling problem; single machine total weighted tardiness problem; Biological cells; Computational modeling; Dynamic programming; Genetic algorithms; Genetic mutations; Heuristic algorithms; Processor scheduling; Single machine scheduling; Software tools; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

E-Learning in Industrial Electronics, 2006 1ST IEEE International Conference on

Conference_Location

Hammamet

Print_ISBN

1-4244-0324-3

Electronic_ISBN

1-4244-0324-3

Type

conf

DOI

10.1109/ICELIE.2006.347205

Filename

4152761