Research On Space-time Modelings And Approximate Dynamic Programming Algorithms For Slab Stack Shuffling Problem

The slab yard is an intermediate buffer connecting the steelmaking-continuous casting and hot rolling production.Slab stack shuffling is to relocate slabs which need to be shuffled when retrieving target slabs.Excessive shuffling will reduce the crane utilization,prolong the retrieving time of target slabs,and even affect the normal production of hot rolling process.Reasonable slab shuffling scheme can decrease the times of slab shuffling,reduce logistics cost and improve the logistics equipment utilization.Therefore,it is of great practical value to study the optimization problem of slab stack shuffling to reduce the logistics cost of steel enterprises.Different from the existing modeling and solving methods,a time-space network model is established in this thesis because of the strong time-space coupling characteristics in the process of shuffling.Due to the dynamic characteristics of slab relocation at each stage,and the fact that the scale of the state increases exponentially with the number of required slabs,an approximate dynamic programming algorithm is proposed.The main work of this thesis is as follows:1)The time-space network model is established.Based on the time-space coupling characters of slab stack shuffling,the time-space network structure is constructed,in which the retrieval stage is regarded as time axis and stack structure is regarded as spatial axis.The nodes in the network represent the storage status in the yard,and the arc between nodes indicates the movement of the slab.By describing the nodes from different angles,directly-described and indirectly-described time-space network models are established respectively.The experimental results indicate that the time-space network model can provide tighter lower bound than the existing models.2)An approximate dynamic programming algorithm is proposed.For large-scale problem,an approximate dynamic programming algorithm is proposed considering the dynamic characteristics of the problem and the curse of dimensionality brought by the increase of required slabs.According to the influence of re-shuffling slabs' relocation decisions on subsequent shuffling times,the value function approximations in view of slabs and stacks are formulated.Based on the characteristics of different value function approximations,three types of solutions are designed to solve the sub-problems during the algorithm procedure,including a linear programming model,a dynamic programming algorithm and a heuristic algorithm combined with dynamic programming algorithm,with the corresponding update strategy of value function.The experimental results indicate that the proposed approximate dynamic programming algorithm can obtain better solutions in effective time compared with the existing methods.3)Based on the proposed time-space network model and approximate dynamic programming algorithm,a decision support system for the optimization of slab stack shuffling problem is designed and developed.The system can automatically produce the shuffling scheme,and realize manual modification and result evaluation etc.