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

Authors: Rylan H. Caldeira; A. Gnanavelbabu

Addresses: Department of Industrial Engineering, CEG Campus, Anna University, Chennai 600025, India ' Department of Industrial Engineering, CEG Campus, Anna University, Chennai 600025, India

Abstract: 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]

Keywords: backtracking search algorithm; flexible job shop rescheduling problem; job insertion; local search technique; rescheduling strategy.

DOI: 10.1504/EJIE.2022.119365

European Journal of Industrial Engineering, 2022 Vol.16 No.1, pp.41 - 70

Received: 07 Jul 2020
Accepted: 27 Jan 2021
Published online: 01 Dec 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article