1999 热轧调度并行处理策略的多旅行商模型.pdfVIP

1999年 4月 东 北 大 学 学 报 ( 自 然 科 学 版 ) Apr. 1 9 9 9 第 20卷第 2期 Journal of Northeastern U niversity( Natural Science) Vol20, No. 2 热轧调度并行处理策略 的多旅行商模型 唐 立 新 ( 东北大学信息科学与工程学院, 沈阳 110006) 摘 要 研究了钢铁企业热轧工序的生产调度问题对 于热 轧调度, 传 统的研 究和 开发 方法是 采 用串行策略: 一个班次内的轧制单元计划是依次制定 的这种串行 策略实质 是一个贪婪 程序, 所以 可能导致局部最优与这个串行策略相反, 从全局最优观点提出了 一个并行 策略: 能 够同时产 生一 个班次中 的 M 个轧制单元计划使用并行策略, 基于实际生产约束的热 轧调度问题 可以作为 一个 多旅行商模型为了求解这个问题, 多旅行商模型变换为单旅行商模型 关键词 钢铁工业, 热轧生产, 调度, 多旅行商模型 分类号 T P 29 钢铁企业在实际编制热轧生产调度时, 一般 都是从预选池的 N 个任务当中依次编制出 M 个 [ 1, 2] 轧制单 元计划 , 这种策略 为串行策 略文献 [ 3] 模拟业务人员编 制计划的思想, 采用串型策 略, 建立了单旅行商模型但是这种串型策略类似 于贪婪方法, 先编制的计划可能很好, 后编制的计 划可能很差, 即有可能陷入局部最优一个合理的 图 1 一个班次的热轧调度的组成 办法是从 N 个任务池当中同时编制出 M 个轧制 单元计划, 这种方法称并行方法, 这样就把它归结 12 一般 MTSP 问题的描述 为多旅行商问题( M TSP) M TSP 问题叙述如下: 给定 N 个 城市和 M M TSP 为 NP 完备问题, 它是单旅行商问题 个旅行商所有旅行商都从一个固定城市出发, 并 的扩展和延续, 在车辆调度方面, 机器人运筹学、 且最后回到出发点它要求每个城市正好由一个 经济学、管理学、通讯网络系统中存在的大量的多 旅行商访问一次, 每一个旅行商至少访问一个城 市 保证整个环游路线距离最小 问题可以 旅行商问题[ 4] , M TSP [ 5] 变换为单 TSP 问题 1 热轧生产调度的结构和建模策略 13 MTSP 问题和热轧调度之间的区别 热轧调度问题可以归结为