An Improved Monkey Search Algorithm to Solve the Flexible Job Shop Scheduling Problems With Makespan Objective

Flexible Job Shop Scheduling

The FJSP was first addressed by Brucker and Schile, 1990. They developed a polynomial algorithm to solve the FJSP with two jobs. They also proposed hierarchical approaches and integrated approaches to solve the FJSP with many jobs. However, the exact algorithms could be used to solve only smaller problem instances. The real problems are larger in nature and hence they cannot be solved by the exact algorithms. A new neighbourhood structure was proposed by Dauzère-Pérès and Paulli (1997) to solve the FJSP. The TS algorithm was suggested by them for re-sequencing and rearranging the operation. Zhang and Gen (2005) proposed a multistage operation based GA to deal with the FJSP. Gao et al. (2006) presented a General Particle Swarm Optimization (GPSO) algorithm for solving FJSP. In the proposed GPSO, crossover and mutation operations in the Genetic Algorithm were incorporated to exchange the information and search randomly. In addition, the Tabu Search (TS) was also used for the local search. The performance of the proposed algorithm was demonstrated with the benchmark problems.

Fattahi et al. (2007) developed a mathematical model and heuristic procedures to solve the FJSP. Tabu search (TS) and simulated annealing (SA) are the heuristics proposed by them. They also addressed six different algorithms to solve the FJSP. They considered both integrated and hierarchical approaches in their research. Gao et al. (2008) proposed a hybrid GA and variable neighbourhood descent (HGVND) algorithm to solve the FJSP. Two local search procedures were introduced by them. The proposed algorithm was tested on 181 benchmark problems and the effectiveness of the algorithm was proved. Pezzella et al. (2008) presented a GA to solve the FJSP by developing different strategies to generate the initial population, selection and reproduction. They compared the results, with other GAs and TS algorithms.