Model and Algorithm for Hot Rolling Batch Planning in Steel Plants

10.6186/IJIMS.2010.21.3.2

Shi-Xin Liu

Flow Shop Problem ； Hot Rolling Batch Planning ； Prize Collecting Vehicle Routing Problem (PCVRP) ； Decomposition-Coordination Ant Colony System (DCACS) ； Local Search

International Journal of Information and Management Sciences

21：3（2010 / 09 / 01）

247 - 264

英文

In many iron-steel plants, hot rolling batch planning is usually considered the bottleneck of production operation management. Consequently, the hot rolling batch planning problems (HRBPPs) have been attracting considerable attention among researchers and practitioners, and numerous models and algorithms were developed. However, most of the models are single objective focused. While in practice, production managers consider more than one objective. In this paper, a multi-objective prize collecting vehicle routing problem (PCVRP) model is formulated to solve the HRBPPs, and a decomposition-coordination ant colony system (DCACS) is designed. Firstly, the DCACS divides the candidate slabs into multiple groups which have similar profiles, then it solves each group as a prize collecting traveling salesman problem (PCTSP) and merges the solutions of the PCTSPs to construct a complete solution for the PCVRP. After obtaining the complete solution the DCACS applies a local search procedure to improve it. The above processes are iterated until the stop criterion is met. Taking twenty practical HRBPPs as instances, the model and algorithm are tested for performances. Computational results show that the model and algorithm outperform human-machine coordination method.

1. Balas, E.(1989).The prize collecting traveling salesman problem.Networks,19(6),621-636.
2. Bullnheimer, B.,Hartl, R. F.,Strauss, C.(1999).An improved ant system algorithm for the vehicle routing problem.Annals of Operations Research,89(0),319-328.
3. Chen, A.-L.,Yang, G.-K.,Wu, Z.-M.(2008).Production scheduling optimization algorithm for the hot rolling processes.International Journal of Production Research,46(7),1955-1973.
4. Chen, X.,Wan, W.-S.,Xu, X.-H.(1998).Modeling rolling batch planning as vehicle routing problem with time windows.Computers & Operations Research,25(12),1127-1136.
5. Cowling, P.(1995).Optimization in Industry (Ch: Optimization in steel hot rolling).New York:Wiley.
6. Dorigo, M.,Maniezzo, V.,Colorni, A.(1996).The ant system: Optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man, and Cybernetics-Part B,26(1),29-41.
7. Dorigo, M.,Stutzle, T.(2004).Ant Colony Optimization..MIT Press.
8. Eswaramurthy, V. P.,Tamilarasi, A.(2009).Hybridization of ant colony optimization strategies in tabu search for solving job shop scheduling problems.International Journal of Information and Management Sciences,20(2),173-189.
9. Gambardella, L.M.,Taillard, E.,Agazzi, G.(1999).MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows.New Ideas in Optimization.
10. Kosiba, E. D.,Wright, J. R.(1992).Discrete event sequence as a traveling salesman problem.Computers in Industry,19(3),317-327.
11. Laporte, G.(1992).The vehicle routing problem: an overview of exact and approximate algorithms.European Journal of Operational Research,59(3),345-358.
12. Liu, Q.,Xu, J.(2008).A study on vehicle routing problem in the delivery of fresh agricultural products under random fuzzy environment.International Journal of Information and Management Sciences,19(4),673-690.
13. Liu, S.,Tang, J.,Song, J.(2006).Order-planning model and algorithm for manufacturing steel sheets.International Journal of Production Economics,100(1),30-43.
14. Lopez, L.,Carter, M. W.,Gendreau, M.(1998).The hot strip mill production scheduling problem: A tabu search approach.European Journal of Operational Research,106(2-3),317-335.
15. Reimann, M.,Doerner, K.,Hartl, R. F.(2004).D-Ants: Savings Based Ants divide and conquer the vehicle routing problem.Computers & Operations Research,31(4),563-591.
16. Taillard, E.,Badeau, P.,Gendreau, M.,Guertin, F.,Potvin, J. Y.(1997).A tabu search heuristic for the vehicle routing problem with soft time windows.Transportation Science,31(2),170-186.
17. Tamura, R.,Nagai, M.,Nakagawa, Y.,Tanizaki, T.,Nakajima, H.(1998).Synchronized scheduling method in manufacturing steel sheets.Opl. Res.,5(3),189-199.
18. Tang, L.,Liu, J.,Rong, A.,Yang, Z.(2000).A mathematical programming model for scheduling steelmaking-continuous casting production.European Journal of Operational Research,120(2),423-435.
19. Tang, L.,Liu, J.,Rong, A.,Yang, Z.(2001).A review of planning and scheduling systems and methods for integrated steel production.European Journal of Operational Research,133(1),1-20.
20. Tang, L.,Liu, J.,Rong, A.,Yang, Z.(2000).A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex.European Journal of Operational Research,124(2),267-282.
21. Zhang, T.,Zhang, Y.,Liu, S.(2008).A mixed integer programming model and improved genetic algorithm for order planning of iron-steel plants.Information and Management Sciences,19(3),413-435.
22. Zhao, J.,Wang, W.,Liu, Q.-L.,Wang, Z.-G.,Shi, P.(2009).A two-stage scheduling method for hot rolling and its application.Control Engineering Practice,17(6),629-641.