Title :
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
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;
Conference_Titel :
Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-5330-2
DOI :
10.1109/ROBOT.1994.351249
