A hybrid genetic algorithm with a neighborhood function for flexible job shop scheduling

摘要

One of the most important issues of manufacturing systems optimization is scheduling. In fact, it plays a great role in reducing the production time and minimizing the required resources for production. Recently, due to the furious competition between companies, manufacturers are pushed to ensure products of high quality with a minimum amount of resources. In addition to that, they should satisfy the deadline of theirs customers. The Flexible Job Shop Scheduling Problem (FJSSP) is a very popular pattern in the real manufacturing systems. This problem is a generalization of the Classical Job Shop problem (JSP). FJJSP is called flexible because a machine can perform many types of operations. Each job in FJSSP has its own production sequence, composed of a set of operations. However, each machine can execute one operation at the same time. The problem is how to ensure the achievement of all jobs in the shortest time (Makespan). A hybrid genetic algorithm (HGA) to solve FJSSP is proposed. An Improved Tabu Search (ITS) algorithm with an original neighborhood function is designed, to improve the performance of GA. The approach was tested and validated using one of the most known benchmarks. The effectiveness of the proposed approach is proved by tests.