An Exact Algorithm based on Lagrangian Relaxation for the Input-Output Scheduling Problem in Automated Warehouses

摘要

In this paper we consider to solve the Input Output Scheduhng Problem (IOSP) in automated warehouses exactly by bounding procedure and general purpose MTP solver. As the bounding procedure to obtain good lower bound, we examine Lagrangian relaxation based method, that is an application of the first step of the additive bounding procedure for CVRP. Replacing costly column generation with Lagrange dual procedure, we expect to reduce the computation time without loss of the solution accuracy. The results of computational experiments show that our approach works well. That is, for relatively large problem instances, it gives slightly inferior lower bounds more quickly than the existing bounding procedure. We conclude that our approach can lead to an effective exact algorithm by adding other bounding methods. Schedulmg Problem, Capacitated Vehicle Routing.