Scheduling of no buffer job shop cells with blocking constraints and automated guided vehicles

The blocking job shop (BJS) problem is an extension of a job shop problem with no buffer constraints. It means that after a job is completed on the current machine, it remains on that machine until the next machine becomes available. This paper addresses an extension of the BJS problem, which takes into account transferring jobs between different machines using a limited number of automated guided vehicles (AGV), called a BJS-AGV problem. Two integer non-linear programming (INLP) models are proposed. A two-stage heuristic algorithm that combines an improving timetabling method and a local search is proposed to solve the BJS-AGV problem. A neighborhood structure in the local search is proposed based on a disjunctive graph model. According to the characteristics of the BJS-AGV problem, four principles are proposed to guarantee the feasibility of the search neighborhood. Computation results are presented for a set of benchmarking tests, some of which are enlarged by transportation times between different machines. The numerical results show the effectiveness of the proposed two-stage algorithm.