A Fast Heuristic Algorithm for Ladle Scheduling Based on Vehicle Routing Problem with Time Windows Model

摘要

In the process of steelmaking and continuous casting production, an optimized ladle schedule will greatly reduce energy consumption and improve production. The ladle scheduling problem can be modeled as vehicle routing problem with time windows (VRPTW) and extra constraints. The main extra constraint is that components of the ladle, at the right time, have to be repaired no later than serving certain number of heats. The objective of ladle scheduling problem is minimizing the number of serving ladles and reducing the waiting time between serving two adjacent heats. According to the serving process of ladles, a mathematical model is established to solve this specific problem. In this paper, a three-step heuristic algorithm with time complexity of O(n ~(2)) is proposed, which is based on characteristics of the model and some preliminary experiments. The algorithm has been tested by several practical instances from a steel plant in China. Comparing with the schedules used in actual production, the computational results show that our algorithm optimizes the ladle schedules and solves the problem in less than 1 second, which proves the algorithm’s efficiency.