A hybrid problem perturbation and genetic algorithm for the flexible job-shop scheduling problem

One of the important and classical problems for production systems is the scheduling. Furthermore, one of the most general states of the scheduling problems in production systems is the flexible job-shop scheduling problem (FJSP). The main difference of the flexible job-shop scheduling problems from the regular job-shop scheduling problems is that in the flexible job-shop, we assume that an operation of a job can be performed in several alternative work centers, while in the regular job-shop case an operation can only be performed in a single work center. In order to optimize the result for this important problem, which is considered in NP-hard class, it becomes impossible to solve or long time periods are required for a solution. In this study, we suggest a hybrid meta heuristic for FJSP with the objective of minimizing the makespan. Our algorithm has three stages; a problem perturbation heuristic, a genetic meta algorithm, and a local improvement phase. The perturbation heuristic aims at producing a high quality initial generation of solutions for the genetic algorithm. While producing the initial generation, schedules are formed by means of priority rules by making positive negative changes on processing times of the operations with the perturbation heuristic. The genetic algorithm improves the generations of solutions subsequently and finally a local search phase at the end tries to further improve the solution found in the last generation. Our hybrid meta heuristic which is collated by the approaches we suggested and by the others in the literature is tried on the test problems from the literature and is observed that it works efficiently.