A memetic algorithm for the flexible job shop scheduling problem with job priority

For the flexible job shop scheduling problem, previous research has focused predominantly on operation and machine related constraints, while assuming that the jobs have no constraints. In real-world manufacturing systems, however, production scheduling with job priority is very common and is of concern to production managers. The purpose of this research is to present a multi-objective flexible job shop scheduling problem with job priority (MO-FJSPJP), aiming to minimize the makespan, total tardiness and completion time of priority jobs simultaneously. A new memetic algorithm (MA) is designed to solve the proposed MO-FJSPJP. In the proposed MA, a well-designed new chromosome encoding method (NCEM) is constructed to obtain a good initial population. A new effective local search approach (LSA) is proposed to improve the MA’s convergence speed and fully exploit its solution space. Computational experiments conducted confirm the effectiveness of the NCEM and LSA, and show that the MA is able to easily obtain better solutions for about 90% of the tested 88 challenging problem instances compared to two other well-known algorithms, demonstrating its superior performance on both solution quality and computational efficiency. The proposed MO-FJSPJP is expected to be useful for production managers in considering job priority when scheduling their operations, and the proposed MA is effective in solving this MO-FJSPJP.