Structural and extremal properties of the hot rolling batches precedence graph. (English) Zbl 1396.90034

Summary: In this paper we study structural properties and properties of maximal paths of the hot rolling batches precedence graph. The hot rolling batches precedence graph arises in the problem of planning and scheduling of a hot strip mill load. Slab batches are selected and sequenced in turns. Basic technological restrictions on batch sequencing in turns are represented by the rolling batches precedence graph. Some fundamental structural properties of this graphs are stated such as the local block structure and the maximal paths structure. Motivation and overview of the result application potential are also provided.


90B30 Production models
90C35 Programming involving graphs or networks
Full Text: DOI MNR


[1] [1] Balas E., “The prize collecting travelling salesman problem”, Networks, 19:6 (1989), 621- 636 · Zbl 0676.90089
[2] [2] Balas E., Clarence H.M., “Combinatorial optimization in steel rolling”, Workshop on Combinatorial Optimization in Science and Technology, 1991
[3] [3] Cowling P., Rezig W., “Integration of continuous caster and hot strip mill planning for steel production”, J. of Scheduling, 3:4 (2000), 185-208 · Zbl 0962.90016
[4] [4] Harary F., Graph Theory, Addison-Wesley, Reading, MA, 1969, 274 pp.
[5] [5] Chen X., Wan, W.-S. and Xu, X.-H., “Modeling rolling batch planning as vehicle routing problem with time windows”, Computers & Operations Research, 25:12 (1998), 1127-1136 · Zbl 1042.90606
[6] [6] Vakula I.A., Leonova S.I., “On building hot rolling turns”, Contemporary problems in mathematics and its applications: 45-th International Youth School-Conference: Proc., IMM UrB RAS, USU, Ekaterinburg, 2014, 164-166 (in Russian)
[7] [7] Vakula I.A., Leonova S.I., “Hot rolling planning problem”, Mathematical programming and applications: XV-th All-Russian Conference: Abstr., IMM UrB RAS, USU, Ekaterinburg, 2015, 77-78 (in Russian)
[8] [8] Lixin Tang, Jiyin Liu, Aiying Rong, Zihou Yang, “A review of planning and scheduling systems and methods for integrated steel production”, European J. of Operational Research, 133:1 (2001), 1-20 · Zbl 0988.90503
[9] [9] Xianpeng Wang, Lixin Tang, “Integration of batching and scheduling for hot rolling production in the steel industry”, The International J. of Advanced Manufacturing Technology, 36 (2008), 431-441
[10] [10] Shixin Liu, “Model and Algorithm for Hot Rolling Batch Planning in Steel Plants”, International J. of Information and Management Sciences, 21:3 (2010), 247-263 · Zbl 1202.90185
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.