Single Machine Total Weighted Tardiness Problem with Genetic Algorithms

Author

Ferrolho, António ; Crisóstomo, Manuel

Author_Institution

Super. Sch. of Technol. of the Polytech. Inst. of Viseu, Viseu

fYear

2007

fDate

13-16 May 2007

Firstpage

1

Lastpage

8

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 software tool; NP-hard problem; genetic algorithms; scheduling problems; single machine total weighted tardiness problem; Biological cells; Computational modeling; Genetic algorithms; Genetic engineering; Genetic mutations; Heuristic algorithms; Processor scheduling; Robots; Single machine scheduling; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Systems and Applications, 2007. AICCSA '07. IEEE/ACS International Conference on

Conference_Location

Amman

Print_ISBN

1-4244-1030-4

Electronic_ISBN

1-4244-1031-2

Type

conf

DOI

10.1109/AICCSA.2007.370857

Filename

4230932