HYBRID GENETIC ALGORITHM FOR FLEXIBLE JOB-SHOP SCHEDULING PROBLEM

摘要

Recently, the development of advanced technologies and the furious competition between manufactures contributed to increase the consumers demand. In fact, Manufactures are pushed to output products with low production cost and to deliver them to consumers on time. Scheduling is how to use optimally the limited resources to ensure final products quickly. Flexible job shop scheduling problem (FJSSP) is one of the most popular scheduling problems existing in practice. In this paper, we propose a new efficient hybrid genetic algorithm for FJSSP. This problem is considered as a generalization of the traditional job shop problem (JSSP). The difference between JSSP and FJSSP is that a machine can perform different types of manufacturing operations in FJSSP. Each job, in FJSSP has its own production sequence composed of some elementary manufacturing operations. However each machine can execute just one operation at the same time. The problem is how to schedule all jobs in the shortest time (Makespan). To solve this problem, we propose a hybrid genetic algorithm based on Taboo search (TS). These two Meta heuristics are well combined to provide solutions of high quality. The approach was tested and validated using one of the most known benchmarks. The obtained results were compared with other methods.