An effective backtracking search algorithm for multi-objective flexible job shop scheduling considering new job arrivals and energy consumption

摘要

This work addresses the flexible job shop scheduling problem considering new job arrivals, which is a common occurrence in real-world manufacturing enterprises. With growing concerns regarding the increasing energy consumption and the advent of green manufacturing, it is essential to consider energy-related objectives in scheduling. Hence, we formulate a mathematical model for the flexible job shop scheduling problem considering new job arrivals and turn on/off strategy with an objective to minimize the makespan, energy consumption, and instability. We address this problem by using an improved backtracking search algorithm. We propose an effective crossover operator to improve the algorithm's search ability and prevent premature convergence. A slack-based insertion rescheduling strategy is developed to handle new job insertions in the schedule. Taguchi analysis is employed to identify the best combination of algorithm parameters. Finally, we generate new benchmark instances for the flexible job shop scheduling problem with new job arrivals. We validate the superior performance of the proposed insertion strategy and the algorithm in terms of solution quality through comprehensive experiments.