Blocking job shop cell scheduling with automated guided vehicles

The blocking job shop(BJS) problem is an extension of job shop problem with no buffer constraints, means after completed on the current machine, the job remains on it until the next machine becomes available. This paper addresses an extension of BJS problem, which takes into account transferring job between different machines by limited number of automated guided vehicles (AGV), called BJS-AGV problem. To deal with BJS-AGV problem, an integer nonlinear programming(INLP) model is proposed to describe BJS-AGV problem. A two stage heuristic algorithm combining an improving timetabling method and local search is proposed to solve BJS-AGV problem. Computation results are presented for testing a set of benchmark instances, some of instances are enlarged by transportation time between different machines. The results show the effectiveness of the proposed two stage algorithm.