An improved backtracking search algorithm for the flexible job shop rescheduling problem with new job insertions

In real-world environments, production schedules are subject to several disruptions. Hence it is essential to account for these disruptions while constructing the production schedules. This work considers the flexible job-shop rescheduling problem (FJSRP) considering new job insertions. An improved discrete backtracking search algorithm and a slack-based inserting rescheduling strategy are proposed to address this problem considering makespan as objective. A set of heuristics is used to generate a diverse initial population. An order-preserving crossover and a mutation operator is developed to balance the exploitation and exploration. A transfer criterion is utilised to employ the information of the past population. The algorithm's exploitation capability is enhanced by employing a local search technique. Extensive computational work is performed on well-known benchmark instances. Computational results demonstrate the superiority of the proposed approach as well as the rescheduling strategy. [Received: 7 July 2020; Accepted: 27 January 2021]