Optimization of On-Site Slab Logistics in Steel Production
Project director: | Prof. Dr. Rolf H. Möhring |
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany | |
Tel: +49 (0)30 - 314 24594 | |
e-mail: rolf.moehring[at]math.tu-berlin.de | |
Researchers: | Felix G. König |
Dr. Marco E. Lübbecke | |
Dr. Guido Schäfer | |
Dr. Ines Spenke | |
emails: {fkoenig, m.luebbecke, schaefer, spenke}[at]math.tu-berlin.de | |
for address, see above | |
Cooperation partners: | |
Problem Description
In integrated steel production, steel is casted in a 24/7 operation in slabs, bars of up to 12 meters length and 30 tons weight. These are rolled to sheet metal in a following batch process. Each slab is assigned to a customer order before it is even casted, and is, thus, individual. The rolling at later points in time is in a given order which (also because of technical reasons) typically differs considerably from the casting sequence. In between, slabs are brought by cranes to a storage area where they are piled up on stacks (for up to several days). If slabs are needed much later (several weeks), they may leave the socalled hot-buffer and can be temporarily stored in a much larger cold-buffer. In both cases, the number of stacks and their height is limited.
In the hot-buffer, ideally, slabs should be stored in such a way that they are readily available according to the planned batch sequence of the rolling process (each batch may request several dozens of slabs in a given order). This conflicts with the limited space, the casting sequence, and the complicating fact, that slabs exiting a strand caster have to be moved away within tight time windows. Time is less crucial in the cold-buffer, but the system inherent non-conformity of input and output sequences becomes much more visible. Obviously, the buffers constitute a major bottleneck, and a high productivity is desired.
Hardness
Due to the slabs' differences in length, width, temperature and material, they may not be arbitrarily stacked on top of each other. Long slabs for instance may not be placed on top of much shorter ones because doing so would impair the stability of the whole stack. These stacking constraints significantly complicate the task of computing an optimal sequence of crane transports. In fact, we have proven the problem to decide whether slabs may leave the buffer in a certain order at all to be PSPACE-complete. Thus, one cannot even hope to find an efficient approximation algorithm for the problem.
State Space Exploration
In view of the complexity of the problem mentioned above, the only hope to find good practical solutions for this stacking problem are smart heuristic approaches. We define a state space graph the nodes of which correspond to all possible configurations of slabs on stacks in the buffer at any point in time. Nodes are connected by a directed edge if the target state can be reached from the source state by one crane transport. The node corresponding to the initial buffer state and time is our starting point, and any node corresponding to a state in which all slabs of the current batch have left the buffer is a target node. Now in a certain sense, short paths from the starting point to a target node correspond to good transport sequences.
Obviously, the resulting graph is huge, so we cannot even generate a significant part of it. Thus, we dynamically create only small parts of it using a combination of a valuation function and a set of priority rules to decide which states we deem interesting.
Lower Bounds
In order to asses the quality of our heuristic solutions, we have devised a mixed integer program (MIP) formulation of a special combinatorial relaxation of the problem. Quite surprisingly, we were able to solve the resulting MIPs to (near) optimality. The computed solution values prove that our solutions are within 15-25 % of a theoretical optimum for all tested instances. We have reason to believe that our solutions are actually even better than that.
References
[1] |
Felix G. König, Marco E. Lübbecke, Rolf H. Möhring, Guido Schäfer, and Ines Spenke Solutions to Real-World Instances of PSPACE-Complete Stacking In Proceedings of the 15th Annual European Symposium on Algorithms (ESA '07), volume 4698 of Lecture Notes in Computer Science, pp. 729-740, Springer, 2007. Preprint 004-2007 |