A Hybrid Evolutionary Algorithm for Solving Flexible Job Shop Scheduling Problem

Document Type : Original Article


1 Institute of Statistical Studies & Research

2 Higher Technological Institute, Tenth of Ramadan city.


This paper presents an Evolutionary Algorithm (EA) to solve the flexible job shop scheduling problem,
especially minimizing the makespan. A hybrid algorithm is introduced for solving flexible job shop scheduling problem.
The proposed algorithm consists of three sequential stages. The first stage is a new technique for initializing feasible
solutions, is used as initial population for the second stage. The second stage uses genetic algorithm to improve the
solutions that have been found in the first stage. The final stage uses tabu search to improve the best solution that has
been found by genetic algorithm. The Job Shop Scheduling Problem (JSSP) is an NP-hard combinatorial optimization
problem that has long challenged researchers. A schedule is a mapping of operations to time slots on the machines. The
makespan is the maximum completion time of the jobs. One of the objectives of the JSSP is to find a schedule that
minimizes the makespan. Some problems from references are solved using the proposed algorithm and an implementation study is presented. The implementation study shows the efficiency of the proposed algorithm.