A Flexible Genetic Algorithm for Job Shop Scheduling with Fixed and Multiple Routes

M. Adel El-Baz
Assistant Professor, Industrial and Systems Engineering Department,
Faculty of Engineering, Zagazig University, Egypt
E-mail: elbaza@mail2world.com

ABSTRACT

This paper describes a flexible Genetic Algorithm (GA) to solve the general form of the job shop-scheduling problem that is characterized by fixed routes as well as multiple routes and flexible machines. Fixed routes mean that there is only one route designed for each part and only one machine assigned for each operation. Multiple routes and flexible machines mean that each part can be processed through alternative routings. Also, there are several machines for each machine type. Because the flexibility of the proposed GA, the algorithm remains unchanged and only a computational algorithm is modified to accommodate both cases. The proposed genetic algorithm chromosome coding and genetic operators are presented. A minimum makespan objective function is used to define code fitness. A proposed scheduling rule is integrated into the process of genetic evaluation to improve the solution performance. The algorithm is proved to be effective and efficient by comparing it with some other methods through experimental results. Test problems indicate that the proposed algorithm is capable of identifying good solution with consistency of execution times as the problem complexity grows.





To read the full article,
please log in:
If you haven't registered already,
you can do so for free:

© Copyright 2000-2003 Professor F.R. Hall & Dr I. Oraifige, University of Wolverhampton.