A New Heuristic Method for Solving Joint Job Shop Scheduling of Production and Maintenance

摘要

Many heuristics and intelligent methods have been proposed and applied in order to solve the Job Shop Scheduling Problems (JSSP). Several researches have so far been interested in solving the production planning in JSSP and few of them have focused on solving production scheduling with the presence of maintenance tasks. This paper presents a new heuristic method (NHGA) that includes two new techniques. The first, is a Modified Genetic Algorithm (MGA) which is inspired from the different steps of standard Genetic Algorithms (GA). Practically, when the GA is used, usually many steps, such as crossover and mutation, are based on random choices. The idea of MGA technique is to enhance the random character of such choices through guiding the steps of GA in a logical procedure, while following at each generation and each step the most plausible solutions to solve the JSS problem with maintenance periods. Henceforth, the new modifications reported in the MGA take into consideration the initial population, selection, crossover, mutation and the running mechanism of the algorithm. This has been sustained by a second technique called Heuristic Displacement of Genes (HDG) such a technique would take as an objective improving the obtained solutions of JSSP. The technique NHGA has been tested on many benchmarks, and compared with standard GA and other recent methods. The obtained results actually shed light on the efficiency of our new heuristic method.