Lagrangian relaxation method for optimizing delay of multiple autonomous guided vehicles

ABSTRACT

In this paper, a scheduling and routing based on AGVs processing and waiting times and the existing paths in a jobshop manufacturing system is proposed. A mathematical formulation is developed to schedule and route multiple AGVs handling jobs to shops so that the total delay of AGVs including the earliness and tardiness is minimized. A Lagrangian relaxation method is developed and a sub-gradient algorithm is composed to update the iterations in the searching process of method. The results show that the method is efficient in larger sizes problems while exact method cannot obtain the solutions in reasonable time. Two different problems are solved using two algorithms of Lagrangian relaxation and linear relaxation. Statistical comparisons showed much better performance of Lagrangian relaxation approach in a negligible run time. For larger sizes that exact method cannot be obtained even in long run times, Lagrangian relaxation approach is useful and efficient.

KEYWORDS:

• Autonomous guided vehicle (AGV)
• path planning
• delay optimization
• Lagrangian relaxation