工程科学学报，第37卷，第1期：111117,2015年1月 Chinese Journal of Engineering,Vol.37,No.1:111-117,January 2015 DOI:10.13374/j.issn2095-9389.2015.01.017:http://journals.ustb.edu.cn 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 柏 亮12)区，李铁克12》，王柏琳12》，许绍云12)，董广静2) 1)北京科技大学东凌经济管理学院，北京1000832)钢铁生产制造执行系统技术教有部工程研究中心，北京100083 ☒通信作者，E-mail:bailiang908@139.com 摘要针对热轧圆钢的批量调度问题，考虑实际生产中工艺规程和交货期对轧制单元连续加工的影响，建立了以最小化设 备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化目标的数学模型，并设计了一种嵌入EDD规则的变邻域搜索算法.算法首 先结合模型的约束特征，采用约束满足技术生成初始解：根据实际生产需求，将最小化设备调整时间作为主要目标，设计变邻 域搜索算法实现目标优化，其中，运用混合算子构造邻域结构和局部搜索，并引入模拟退火接受准则来控制迭代过程中产生 的新解：同时，为了最小化拖期惩罚和钢种跳跃惩罚，在求解过程中嵌入了EDD规则以及钢种排序规则.实验结果表明，模型 和算法是可行且有效的 关键词热轧：调度：变邻域搜索：多目标优化：约束满足问题 分类号F273.1 Variable neighborhood search based multi-objective optimization method for batch scheduling of hot-rolled bars BAI Liang LI Tie-ke,WANG Bai-in XU Shao-yun DONG Guang jing 1)Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron Steel Production (the Ministry of Education),Beijing 100083,China Corresponding author,E-mail:bailiang908@139.com ABSTRACT 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 sha- king 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. KEY WORDS hot rolling:scheduling:variable neighborhood search:multi-objective optimization:constraint satisfaction problems 在整个钢铁生产过程中，热轧不仅是生产成品、直即为了保证产品质量、降低生产成本和提高生产效率， 接创造经济效益的瓶颈工序，而且是衔接炼钢、连铸和 一般以热轧为核心，将具有相同特性的销售订单进行 冷轧的关键工序.热轧阶段是典型的批量生产过程， 合理的归并与拆分，得到在热轧生产过程中连续不允 收稿日期：2013-11-26 基金项目：国家自然科学基金资助项目(71231001)：中央高校基本科研业务费专项资金资助项目(FRF-SD一2011B,FRF-SD-12O12B):教 育部博士学科点专项科研基金资助项目(20100006110006)工程科学学报，第 37 卷，第 1 期: 111--117，2015 年 1 月 Chinese Journal of Engineering，Vol． 37，No． 1: 111--117，January 2015 DOI: 10． 13374 /j． issn2095--9389． 2015． 01． 017; http: / /journals． ustb． edu． cn 基于变邻域搜索的热轧圆钢批量调度多目标优化方法 柏 亮1，2) ，李铁克1，2) ，王柏琳1，2) ，许绍云1，2) ，董广静1，2) 1) 北京科技大学东凌经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083  通信作者，E-mail: bailiang908@ 139． com 摘 要 针对热轧圆钢的批量调度问题，考虑实际生产中工艺规程和交货期对轧制单元连续加工的影响，建立了以最小化设 备调整时间、拖期生产惩罚和钢种跳跃惩罚为优化目标的数学模型，并设计了一种嵌入 EDD 规则的变邻域搜索算法． 算法首 先结合模型的约束特征，采用约束满足技术生成初始解; 根据实际生产需求，将最小化设备调整时间作为主要目标，设计变邻 域搜索算法实现目标优化，其中，运用混合算子构造邻域结构和局部搜索，并引入模拟退火接受准则来控制迭代过程中产生 的新解; 同时，为了最小化拖期惩罚和钢种跳跃惩罚，在求解过程中嵌入了 EDD 规则以及钢种排序规则． 实验结果表明，模型 和算法是可行且有效的． 关键词 热轧; 调度; 变邻域搜索; 多目标优化; 约束满足问题 分类号 F273. 1 Variable neighborhood search based multi-objective optimization method for batch scheduling of hot-rolled bars BAI Liang1，2)  ，LI Tie-ke1，2) ，WANG Bai-lin1，2) ，XU Shao-yun1，2) ，DONG Guang-jing1，2) 1) Donlinks School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China 2) Engineering Ｒesearch Center of MES Technology for Iron ＆ Steel Production ( the Ministry of Education) ，Beijing 100083，China  Corresponding author，E-mail: bailiang908@ 139． com ABSTＲACT 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 sha￾king 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． KEY WOＲDS hot rolling; scheduling; variable neighborhood search; multi-objective optimization; constraint satisfaction problems 收稿日期: 2013--11--26 基金项目: 国家自然科学基金资助项目( 71231001) ; 中央高校基本科研业务费专项资金资助项目( FＲF--SD--12--011B，FＲF--SD--12--012B) ; 教 育部博士学科点专项科研基金资助项目( 20100006110006) 在整个钢铁生产过程中，热轧不仅是生产成品、直 接创造经济效益的瓶颈工序，而且是衔接炼钢、连铸和 冷轧的关键工序． 热轧阶段是典型的批量生产过程， 即为了保证产品质量、降低生产成本和提高生产效率， 一般以热轧为核心，将具有相同特性的销售订单进行 合理的归并与拆分，得到在热轧生产过程中连续不允