AGV Scheduling of Material Handling Systems

Summary

• Developed a novel fault-tolerant AGV fleet management framework and tool.

• AGVs are modelled as Timed Discrete Event Systems.

• Schedules are synthesized in an incremental manner.

• Paths are plotted for each AGV in priority order.

• High priority AGVs are treated as moving obstacles for low priority AGVs.

Contributions

For AGV fleet management, we have developed two different strategies.

Heuristic scheduling

The first one is a heuristic strategy, which includes the following functional modules.

The Task Dispatching module ranks work order based on urgency. The AGV Path Planning module generates shortest paths with collision avoidance. The Battery Recharge Management module utilizes a threshold-based rule to decide which AGV should go for recharging. The Fault tolerant dynamic replanning module tackling changes in AGV count and battery level.

Real-time scheduling

The second strategy is based on real-time optimization.

A generic mathematical programming formulation is developed to capture key operational constraints in a typical AGV production system, and allows users to adjust the cost function according to their actual needs.

Ensure real-time problem solvability Use a receding horizon strategy and a metaheuristic method Easily handle typical system and user requirement changes Facilitate fault tolerance and real-time responsiveness via fast replanning

AGV fleet management tool

An AGV fleet management tool is developed featuring the following functional modules.

System construction module that allows users to add various components such as wall, machine, load port, AGV, charging station, waypoints and links. AGV dispatching algorithm library Data visualization module Real-time scheduling module

Data visualization tool

The data visualization module allows users to monitor the real time data of AGV battery level, load port stock level and work order completion status etc.

Real-time data monitor: Component tooltip AGV battery level monitor Load port stock level monitor Work order completion status monitor

Peerformance analysis tool: Summary report on the utilization rate of individual AGVs Summary report on the charging stations state analysis Evaluate the effectiveness of various AGV dispatching/scheduling strategies Determine the best portfolio of AGV fleets, the best routing method and the best charging policy …

Dynamic planning architecture

To illustrate the effectiveness of two aforementioned AGV dispatching and scheduling strategies in real operations, a separate disturbance generator module has also been developed to simulate real operational environments.

In field operations, when there is any external disturbance on AGVs or machines, the disturbance message will be sent to the AGV Fleet Management tool via MQTT (an IoT protocol) which may trigger system replanning afterwards.

AGV change Machine change Task change …

References

1. D. Deplano, S. Ware, R. Su, A. Giua. (2017). A heuristic algorithm to optimize execu- tion time of multi-robotic path. Proc. 13th IEEE International Conference on Control and Automation, pp. 909-914, Ohrid.

2. S. Ware, R. Su. (2017). An application of incremental scheduling to a cluster photolithog- raphy tool. Proc. IFAC World Congress 2017, pp. 1137-1143, Toulouse.

3. Hagebring, Fredrik and Wigström, Oskar and Lennartson, Bengt and Ware, Simon Ian and Su, Rong, “Comparing MILP, CP, and A* for multiple stacker crane scheduling.” Discrete Event Systems (WODES), 2016 IEEE 13th International Workshop: 63-70.

4. Ware, Simon and Su, Rong, “Incremental scheduling of discrete event systems.” Discrete Event Systems (WODES), 2016 IEEE 13th International Workshop: 147-152

5. S. Sami, L. Lin, A. Shehabinia, R. Su. (2014). Discrete-event based vehicle dispatching and scheduling in multicommodity transportations. In Proc. 13th International Conference on Control, Automation, Robotics and Vision, pp. 169-174, Singapore.