A Decomposition Method for Production Scheduling and AGV Routing Problems by Lagrangian Relaxation with Cut Generation

In this paper, we propose a decompositon method for simultanenous optimization problem of production scheduling and transportation routing for semiconductor fabrication bays. The original problem is decomposed into an upper level subproblem to determine production scheduling and assignment of requests to AGVs and a lower level subproblem to derive a collision-free routing for AGVs. The novel idea of the proposed method is that the upper level subproblem is solved by using Lagrangian relaxation technique incorporating cuts generated from a solution of the lower level subproblem. The algorithm solves successively the upper level problem and the lower level problem until a feasible solution for original problem is derived. The entire search space is reduced by incorporating cuts. The effectiveness of the proposed method is investigated from numerical experiments.