A heuristic genetic algorithm for flowshop scheduling

Author

Chakraborty, Uday K. ; Lah, D. ; Chakraborty, Mandira

Author_Institution

Dept. of Math. & Comput. Sci., Missouri Univ., St. Louis, MO, USA

fYear

2001

fDate

19-22 June 2001

Firstpage

313

Abstract

Flowshop scheduling deals with determining the optimum sequence of jobs to be processed on several machines so as to satisfy some scheduling criterion. It is NP-complete. Heuristic algorithms use problem-specific information to yield a good working solution. Genetic algorithms are stochastic, adaptive, general-purpose search heuristics based on concepts of natural evolution. We have developed a new heuristic genetic algorithm (NGA) which combines the good features of both the GA and heuristic search. The NGA is run on several problems and its performance is compared with that of the conventional genetic algorithm and the well-known NEH heuristic. The NGA is seen to perform better in almost all instances.

Keywords

computational complexity; genetic algorithms; heuristic programming; scheduling; search problems; NEH heuristic; NGA; NP-complete; flowshop scheduling; heuristic genetic algorithm; heuristic search; job processing; natural evolution; optimum sequence; problem-specific information; scheduling criterion; stochastic adaptive general-purpose search heuristics; Computer science; Evolution (biology); Genetic algorithms; Genetic mutations; Heuristic algorithms; Mathematics; Mechanical engineering; Polynomials; Processor scheduling; Stochastic processes;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Technology Interfaces, 2001. ITI 2001. Proceedings of the 23rd International Conference on

ISSN

1330-1012

Print_ISBN

953-96769-3-2

Type

conf

DOI

10.1109/ITI.2001.938035

Filename

938035