Model and algorithm of the billet design problem in the production of seamless steel tubes with a single billet size
-
摘要: 無縫鋼管坯料設計是在滿足生產工藝要求下,將客戶訂單鋼管合理地分配到生產原料圓坯的過程.實際生產中的批量原則使得每個鋼管訂單在圓坯中有最小分配重量要求;由于無縫鋼管分配支數必須取整,導致鋼管訂單在圓坯中的分配重量并非連續取值.因此,比起相關的板坯設計問題和裝箱問題,無縫鋼管坯料設計的求解更為復雜.本文給出了無縫鋼管坯料設計問題的一般性描述,并建立了混合整數規劃模型.針對庫存中只有單一尺寸圓坯的情況,簡化了問題模型并且求得了問題的下界.結合問題特點,提出了基于貪婪策略的兩階段啟發式算法,并用實際生產數據和仿真數據驗證了算法求解此類問題具有很好的有效性和穩定性.Abstract: The billet design problem (BDP) in seamless steel tube production is to assign order tubes to billets under process constraints. Because of the batch rule in practical production, each order has a minimum weight of tubes assigned to any billet. Meanwhile, as the number of tubes assigned to a billet must be an integer, the weight of tubes assigned to any billet is not continuous in its domain. Thus, the BDP discussed herein is more difficult to solve than the slab design and bin packing problems. In this study, a multi-objective mix-integer programming model was built based on a generalized description of the BDP, which is proved to be non-deterministic polynomial (NP) hard. For the case with single billet size wherein two objectives in the model are equivalent, a simplified model was set up and the lower bound of the objective could be found. Further, a two-stage heuristic algorithm based on greedy strategy was proposed to solve the problem. Finally, using computational results, it was proved that the algorithm is effective and efficient in solving the BDP.
-
Key words:
- billet design /
- seamless steel tube /
- greedy strategy /
- heuristic algorithm
-
參考文獻
[1] Frisch A M, Miguel I, Walsh T. Modeling a steel mill slab design problem//Proceedings of the IJCAI-01 Workshop on Modeling and Solving Problems with Constraints. Seattle, 2001:39 [2] Hnich B, Kiziltan Z, Miguel I, et al. Hybrid modeling for robust solving. Ann Oper Res, 2004, 130(1):19 [4] Dawande M, Kalagnanam J, Lee H S, et al. The slab-design problem in the steel industry. Interfaces, 2004, 34(3):215 [5] Gargani A, Refalo P. An efficient model and strategy for the steel mill slab design problem//Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming. Berlin, 2007:77 [6] Hentenryck P V, Michel L. The steel mill slab design problem revisited//Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Berlin, 2008:377 [9] Tang L X, Luo J X, Liu J Y. Modelling and a tabu search solution for the slab reallocation problem in the steel industry. Int J Prod Res, 2013, 51(14):4405 [10] Rohlfshagen P, Bullinaria J A. Nature inspired genetic algorithms for hard packing problems. Ann Oper Res, 2010, 179(1):393 [11] Brusco M J, K hn H F, Steinley D. Exact and approximate methods for a one-dimensional minimax bin-packing problem. Ann Oper Res, 2013, 206(1):611 [12] Crainic T G, Perboli G, Rei W, et al. Efficient lower bounds and heuristics for the variable cost and size bin packing problem. Comput Oper Res, 2011, 38(11):1474 [13] Hemmelmayr V, Schmid V, Blum C. Variable neighborhood search for the variable sized bin packing problem. Comput Oper Res, 2012, 39(5):1097 [14] Pereira J. Procedures for the bin packing problem with precedence constraints. Eur J Oper Res, 2016, 250(3):794 [15] Gualandi S, Malucelli F. Constraint programming-based column generation. 4OR Q J Oper Res, 2009, 7(2):113 -
點擊查看大圖
計量
- 文章訪問數: 799
- HTML全文瀏覽量: 224
- PDF下載量: 12
- 被引次數: 0
下載:
