基于变邻域搜索的热轧圆钢批量调度多目标优化方法
|
摘要
针对热轧圆钢的批量调度问题,考虑实际生产中工艺规程和交货期对轧制单元连续加工的影响,建立了以最小化设备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化目标的数学模型,并设计了一种嵌入EDD规则的变邻域搜索算法.算法首先结合模型的约束特征,采用约束满足技术生成初始解;根据实际生产需求,将最小化设备调整时间作为主要目标,设计变邻域搜索算法实现目标优化,其中,运用混合算子构造邻域结构和局部搜索,并引入模拟退火接受准则来控制迭代过程中产生的新解;同时,为了最小化拖期惩罚和钢种跳跃惩罚,在求解过程中嵌入了EDD规则以及钢种排序规则.实验结果表明,模型和算法是可行且有效的.
A batch scheduling problem of hot-rolled bars was discussed according to the influences of process conditions and due date on the continuous production of rolling units. A mathematical model with three objectives to minimize the setup time,tardiness penalty and steel grade bounce penalty was constructed,and a method of the variable neighborhood search algorithm embedding the earliest due date first( EDD) rule was proposed to solve the model. In consideration of constraints in the model,an initial solution was generated by constraint satisfaction technology. Then,to meet the actual production needs,a variable neighborhood search method was designed to minimize the setup time,which is considered as a primary objective. In this algorithm,a hybrid operator is applied in shaking and local search,and the idea of simulated annealing is introduced to take control of the acceptance of new solutions. Meanwhile,in order to minimize the tardiness penalty and the steel grade bounce penalty,the earliest due date first rule and the steel grade sorting rule are applied. Experiment results show that the model and the algorithm are feasible and effective.
A batch scheduling problem of hot-rolled bars was discussed according to the influences of process conditions and due date on the continuous production of rolling units. A mathematical model with three objectives to minimize the setup time,tardiness penalty and steel grade bounce penalty was constructed,and a method of the variable neighborhood search algorithm embedding the earliest due date first( EDD) rule was proposed to solve the model. In consideration of constraints in the model,an initial solution was generated by constraint satisfaction technology. Then,to meet the actual production needs,a variable neighborhood search method was designed to minimize the setup time,which is considered as a primary objective. In this algorithm,a hybrid operator is applied in shaking and local search,and the idea of simulated annealing is introduced to take control of the acceptance of new solutions. Meanwhile,in order to minimize the tardiness penalty and the steel grade bounce penalty,the earliest due date first rule and the steel grade sorting rule are applied. Experiment results show that the model and the algorithm are feasible and effective.
引文
[1]Liu Q,Bai S H,Lu J H,et al.Production plan schedule for the casting-rolling process in BOF special steel plants.J Univ Sci Technol Beijing,2008,30(5):566(刘青,白素宏,卢军辉,等.转炉特钢流程连铸-轧钢生产排产系统.北京科技大学学报,2008,30(5):566)
[2]Li T K,Guo D F.Model and algorithm for hot-rolling batch plan based on constraint satisfaction.Control Decis,2007,22(4):389(李铁克,郭冬芬.基于约束满足的热轧批量计划模型与算法.控制与决策,2007,22(4):389)
[3]Zhang X J,LüZ M.Refactoring model and generalized method for a type of scheduling problem based on constraint programming method.Comput Eng Appl,2012,48(26):219(张旭君,吕志民.基于约束规划的一类排序问题通用求解方法.计算机工程与应用,2012,48(26):219)
[4]Pan C C,Yang G K.A method of solving a large scale rolling batch scheduling problem in steel production using a variant of column generation.Comput Ind Eng,2009,56(1):165
[5]Yang Y J,Jiang Z Y,Zhang X X.Mathematical model and solving algorithm for the lot planning of slab hot rolling.J Univ Sci Technol Beijing,2012,34(4):457(杨业建,姜泽毅,张欣欣.板坯热轧批量计划数学模型及求解算法.北京科技大学学报,2012,34(4):457)
[6]Liu S X.Model and algorithm for hot rolling batch planning in steel plants.Int J Inf Manage Sci,2010,21(3):247
[7]Jia S J,Yi J,Yang G K,et al.A multi-objective optimisation algorithm for the hot rolling batch scheduling problem.Int J Prod Res,2013,51(3):667
[8]Tang L X,Huang L.Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production.Int J Prod Econ,2007,105(2):357
[9]Li L,Huo J Z.Multi-objective flexible job-shop scheduling problem in steel tubes production.Syst Eng Theory Pract,2009,29(8):117(李琳,霍佳震.钢管生产计划中的多目标柔性Job-shop调度问题.系统工程理论与实践,2009,29(8):117)
[10]Wang X,Yang C H,Qin B.Multi-objective hybrid optimization of lot scheduling for bar mill process.Control Decis,2006,21(9):996(王欣,阳春华,秦斌.棒线材轧制批量调度多目标混合优化.控制与决策,2006,21(9):996)
[11]Roberti R,Toth P.Models and algorithms for the asymmetric traveling salesman problem:an experimental comparison.EURO J Transp Logist,2012,1(1):113
[12]Hansen P,Mladenovi'c N.Variable neighborhood search:principles and applications.Eur J Oper Res,2001,130(3):449
[13]Imran A,Salhi S,Wassan N A.A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem.Eur J Oper Res,2009,197(2):509
[14]Fellows M,Friedrich T,Hermelin D,et al.Constraint satisfaction problems:convexity makes All Different constraints tractable.Theor Comput Sci,2013,472:81
[15]Zhang W X,Li T K.Modelling and algorithm for the slab designing problem based on constraint satisfaction.J Univ Sci Technol Beijing,2011,33(5):641(张文学,李铁克.基于约束满足的板坯设计模型与求解方法.北京科技大学学报,2011,33(5):641)
[16]Hansen P,Mladenovi'c N.First vs.best improvement:an empirical study.Discrete Appl Math,2006,154(5):802
[2]Li T K,Guo D F.Model and algorithm for hot-rolling batch plan based on constraint satisfaction.Control Decis,2007,22(4):389(李铁克,郭冬芬.基于约束满足的热轧批量计划模型与算法.控制与决策,2007,22(4):389)
[3]Zhang X J,LüZ M.Refactoring model and generalized method for a type of scheduling problem based on constraint programming method.Comput Eng Appl,2012,48(26):219(张旭君,吕志民.基于约束规划的一类排序问题通用求解方法.计算机工程与应用,2012,48(26):219)
[4]Pan C C,Yang G K.A method of solving a large scale rolling batch scheduling problem in steel production using a variant of column generation.Comput Ind Eng,2009,56(1):165
[5]Yang Y J,Jiang Z Y,Zhang X X.Mathematical model and solving algorithm for the lot planning of slab hot rolling.J Univ Sci Technol Beijing,2012,34(4):457(杨业建,姜泽毅,张欣欣.板坯热轧批量计划数学模型及求解算法.北京科技大学学报,2012,34(4):457)
[6]Liu S X.Model and algorithm for hot rolling batch planning in steel plants.Int J Inf Manage Sci,2010,21(3):247
[7]Jia S J,Yi J,Yang G K,et al.A multi-objective optimisation algorithm for the hot rolling batch scheduling problem.Int J Prod Res,2013,51(3):667
[8]Tang L X,Huang L.Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production.Int J Prod Econ,2007,105(2):357
[9]Li L,Huo J Z.Multi-objective flexible job-shop scheduling problem in steel tubes production.Syst Eng Theory Pract,2009,29(8):117(李琳,霍佳震.钢管生产计划中的多目标柔性Job-shop调度问题.系统工程理论与实践,2009,29(8):117)
[10]Wang X,Yang C H,Qin B.Multi-objective hybrid optimization of lot scheduling for bar mill process.Control Decis,2006,21(9):996(王欣,阳春华,秦斌.棒线材轧制批量调度多目标混合优化.控制与决策,2006,21(9):996)
[11]Roberti R,Toth P.Models and algorithms for the asymmetric traveling salesman problem:an experimental comparison.EURO J Transp Logist,2012,1(1):113
[12]Hansen P,Mladenovi'c N.Variable neighborhood search:principles and applications.Eur J Oper Res,2001,130(3):449
[13]Imran A,Salhi S,Wassan N A.A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem.Eur J Oper Res,2009,197(2):509
[14]Fellows M,Friedrich T,Hermelin D,et al.Constraint satisfaction problems:convexity makes All Different constraints tractable.Theor Comput Sci,2013,472:81
[15]Zhang W X,Li T K.Modelling and algorithm for the slab designing problem based on constraint satisfaction.J Univ Sci Technol Beijing,2011,33(5):641(张文学,李铁克.基于约束满足的板坯设计模型与求解方法.北京科技大学学报,2011,33(5):641)
[16]Hansen P,Mladenovi'c N.First vs.best improvement:an empirical study.Discrete Appl Math,2006,154(5):802