无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。
The market demand for hot-rolled seamless steel tube presents multi-variety and small-batch characteristics, and delivery addresses and delivery time of orders are usually different. In this paper, the problem of hot-rolled order scheduling of seamless steel tube is extracted and defined from actual production. Hot-rolled order scheduling is the process of combining production orders into rolling batches and scheduling rolling batches sequence. In order to meet customer needs and ensure production efficiency and continuity, delivery factors, such as delivery address and delivery time, are introduced to the order scheduling. Moreover, considering delivery requirements and process characteristics, a model for this order scheduling problem is built to optimize the delivery period, ensure concentrated production and distribution, and minimize the total setup time of machines. A two-stage algorithm is provided further. In the first stage, to minimize differences among delivery time and addresses of orders, a hierarchical clustering algorithm is put forward on cohesion policy to cluster orders with the same process constraints and similar delivery requirements, thereby forming an initial rolling plan. In the second stage, a hybrid variable neighborhood search algorithm is presented to improve the initial plan in terms of setup times and earlyness/tardiness. Results of experiments with actual order data show the effectiveness of the model and algorithm. This research has a useful reference for the study of order scheduling problem of other steel products or products involving complex process and delivery constraints.
[1] 王海凤,薛美美,李铁克.基于约束满足的热轧无缝钢管生产排序模型与算法[J].冶金自动化,2013,37(3):39-42.
[2] Tang Lixin, Huang Lin. Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production[J]. International Journal of Production Economics,2007,105(2):357-371.
[3] 李建祥,唐立新,吴会江,等.基于规则的热轧钢管调度[J].钢铁,2004,39(9):39-42.
[4] Li Lin, Huo Jiazhen, Tang Ou. A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production[J].International Journal of Production Research, 2011, 49(15):4679-4700.
[5] Jia Shujin,Yi Jian,Yang Genke,et al. A multi-objective optimisation algorithm for the hot rolling batch scheduling problem[J].International Journal of Production Research,2013,51(3):667-681.
[6] 许绍云,李铁克,王雷,等.考虑机器检修的圆钢热轧批量调度算法[J].计算机集成制造系统, 2014, 20(10):2502-2511.
[7] Jia Shujin, Zhu Jun, Yang Genke,et al. A decomposition-based hierarchical optimization algorithm for hot rolling batch scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2012, 61(5):487-501.
[8] 张文学,李铁克.面向多种生产工艺的冶铸轧一体化批量计划优化[J].计算机集成制造系统,2013,19(6):1296-1303.
[9] 薛羽.仿生智能优化算法及其应用研究[D].南京:南京航空航天大学,2013.
[10] Pan Changchun, Yang Genke. A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation[J]. Computers & Industrial Engineering, 2009, 56(1):165-178..
[11] Everitt B, Landau S, Leese M, et al. Cluster analysis, Wiley series in probabilityand statistics[M]. Chichester, UK:Wiley; 2011.
[12] Daie P, Li S. Hierarchical clustering for structuring supply chain network in case of product variety[J]. Journal of Manufacturing Systems, 2016, 38:77-86.
[13] 段明秀.层次聚类算法的研究及应用[D].长沙:中南大学,2009.
[14] Arroyo J E C, Rafael D S O, Alcione D P O. Multi-objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows[J]. Electronic Notes in Theoretical Computer Science, 2011, 281(1):5-19.
[15] Mladenovic N, Hansen P. Variable neighborhood search[J]. Computers & Operations Research, 1997, 24(11):1097-1100.
[16] Hansen P, Mladenovic N. Variable neighborhood search:Principles and applications[J]. European Journal of Operational Research, 2001, 130(3):449-467.
[17] Xiao Yiyong, Zhao Qiuhong, Kaku I, et al.Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems[J].Engineering Optimization, 2014, 46(4):562-579.
[18] 柏亮,李铁克,王柏琳,等.基于变邻域搜索的热轧圆钢批量调度多目标优化方法[J].工程科学学报,2015,37(1):111-117.
[19] 王雷,许绍云,赵扬,等.有限缓冲区的多节点订单接受模型与算法[J].中国管理科学,2015,23(12):135-141.
[20] Yu V F, Lin S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers and Operations Research, 2015,62:184-196.
[21] Bandyopadhyay S, Saha S, Maulik U, et al. A Simulated annealing-based multiobjective optimization algorithm:AMOSA[J]. IEEE transactions on evolutionary computation, 2008, 12(3):269-283.
