An evolutionary approach to the job-shop scheduling problem

Author

Kim, Gyoung H. ; Lee, C. S George

Author_Institution

Sch. of Electr. Eng., Purdue Univ., West Lafayette, IN, USA

fYear

1994

fDate

8-13 May 1994

Firstpage

501

Abstract

This paper focuses on the heuristic hybridization and the genetic search as a methodology to develop a computationally efficient heuristic for the job-shop scheduling problem (JSP). In order to adapt the JSP to a genetic algorithm (GA), the ASGPL (Active-Schedule Generation with a Priority-List) algorithm with a hopping scheme was proposed, and using a GA, an iterative schedule improvement procedure called EVIS (Evolutionary Intracell Scheduler) was designed. The genetic search in EVIS was parallelized with a model of subpopulations and migration. Without implementing any problem-tailored heuristic for the job-shop scheduling problem, EVIS was able to find optimal solutions to a number of different problem instances in reasonable computation time

Keywords

genetic algorithms; iterative methods; production control; production engineering computing; search problems; EVIS; Evolutionary Intracell Scheduler; active schedule generation; genetic algorithm; genetic search; heuristic hybridization; hopping scheme; iterative schedule; job-shop scheduling; priority list; problem-tailored heuristic; Algorithm design and analysis; Approximation algorithms; Cost function; Genetic algorithms; Heuristic algorithms; Intelligent manufacturing systems; Iterative algorithms; Job shop scheduling; Processor scheduling; Scheduling algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on

Conference_Location

San Diego, CA

Print_ISBN

0-8186-5330-2

Type

conf

DOI

10.1109/ROBOT.1994.351249

Filename

351249