A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem

In recent years there has been a great increase of interest in the job shop scheduling problem (JSSP) from both practical and theoretical points of view. This is due to the large amount of computational effort usually required in the solution of the problem. Several heuristics that lead to near-optimal solutions in reasonably short times have been developed to solve this problem. Among the heuristics, one of the most successful approaches is the shifting bottleneck heuristic (SBH) which is a disjunctive graph-based decomposition method. Recently, the reentrant job shop has emerged as a new type of manufacturing shop. This problem is important because the assumption that each job visits each machine only once is often violated in practice. The principle characteristic of a reentrant job shop is that a certain job may visit a specific machine or a set of machines more than once during the process flow. In this study, a modified shifting bottleneck heuristic (MSBH) is proposed to solve the reentrant job shop scheduling problem (RJSSP) for makespan minimization objective. Furthermore, a modified rolling horizon procedure (MRHP) is proposed to decompose large job shops. Finally, various comparative experiments and an application study in a textile factory have been carried out to evaluate the performance of both the MSBH and the MRHP. Keywords: Reentrant Job Shop Scheduling Problem, Shifting Bottleneck Heuristic, Rolling Horizon Procedure, Makespan Minimization.