（计算机应用技术专业论文）炼钢连铸调度计划编制优化方法的研究.pdf

， 、 青岛科技大学研究生学位论文 炼钢一连铸调度计划编制优化方法的研究 摘要 炼钢连铸生产调度水平是衡量钢铁企业生产管理水平的重要指标之一。合理 安排炼钢连铸生产作业计划与调度是确保钢铁生产物流通畅、资源合理利用，提 高设备利用率，提升生产系统的整体运行效率，降低物耗、能耗及成本，增加企 业利润和企业竞争实力的重要途径。 以炼钢连铸生产调度计划编制问题为研究对象，并针对炼钢一连铸生产过程 的单重精炼和多重精炼问题，分别采用遗传算法和数学规划优化方法对其进行深 入的研究。针对简单遗传算法存在的早熟和局部收敛等不足，提出了一种基于分 段实数矩阵编码、基因分段交叉操作和交叉变异概率自适应选择的改进遗传算 法，有效地解决了一般钢厂生产同级钢种的单重精炼生产过程的炼钢连铸生产调 度问题。针对大型钢铁企业存在着多重精炼的生产工艺过程，提出了炼钢一连铸 生产调度计划编制问题的分解策略，将调度问题分解成两个子问题，一个是设备 指派问题，一个是冲突解消问题。通过建立基于动态规划的数学模型对炉次计划 进行有效的指派，为每个炉次确定出最佳的生产路径。根据连铸开浇时间、各设 备处理时间和运输时间可求解一个粗调度计划，但这个粗调度计划可能存在冲 突，不能应用到实际生产中去。根据生产工艺约束和生产目标，建立线性规划数 学模型来解消粗调度表中的冲突，并得到一个可行的调度计划方案。通过某大型 钢铁企业实际生产数据的仿真验证，表明了该方法的合理性和有效性，为有关技 术的进一步完善、发展和开发提供一定的理论基础和实践方法。 度炼钢连铸改进遗传算法动态规划线性规划 炼钢连铸调度计划编制优化方法的研究 t h er e s e a r c ho ns t e e l n l n 呵g c o n t n 哪o u s c a s t i n gs c h e d u l i n gp l a n n i n g o p t i z a t i o n 匝t h o d a b s t r a c t s t e e l m a k i n g - c o n t i n u o u sc a s t i n gp r o d u c t i o n s c h e d u l i n gl e v e li s o n eo ft h e i m p o r t a n ti n d i c a t o r st om e a s u r et h el e v e lo fi r o na n ds t e e le n t e r p r i s ep r o d u c t i o n m a n a g e m e n t m a k i n gar e a s o n a b l es c h e d u l i n gp l a ni sa ni m p o r t a n tw a yt oe n s u r e s m o o t hp r o d u c t i o na n dr a t i o n a lu o fr e s o u r c e s ，i m p r o v ee q u i p m e n tu t i l i z a t i o n , t h e r e b ye n h a n c et h e o v e r a l le f f i c i e n c y o fp r o d u c t i o n s y s t e m s ，r e d u c e m a t e r i a l c o n s u m p t i o n , e n e r g yc o n s u m p t i o n a n dc o s t s ，i n c r e a s et h ep r o f i ta n dc o m p e t i t i v e n e s s i nt h i sp a p e r , t h es t e e l m a k i n g c o n t i n u o u sc a s t i n g s c h e d u l i n ga n dp l a n n i n g o p t i m i z a t i o np r o b l e mi sr e g a r d e da st h er e s e a r c ho b j e c t , f o rs t e e l m a k i n g - c o n t i n u o u s c a s t i n gp r o c e s so fs i n g l ea n dm u l t i p l er e f i n i n gp r o b l e m s ，r e s p e c t i v e l yu s eg e n e t i c a l g o r i t h m a n dm a t h e m a t i c a l p r o g r a m m i n go p t i m i z a t i o n m e t h o dt oc o n d u c tt h e i n - d e p t hs t u d y f o rt h ee x i s t e n c eo fp r e m a t u r ea n dl o c a lc o n v e r g e n c eo fs i m p l eg e n e t i c a l g o r i t h m ，w ep r o p o s eag e n e t i ca l g o r i t h mi m p r o v e dt h r o u g hr e a lm a t r i xc o d i n g ，g e n e c r o s s - s e c t i o no p e r a t i o na n da d a p t i v es e l e c t i o no fc r o s s o v e ra n dm u t a t i o np r o b a b i l i t y , w h i c he f f e c t i v e l ys o l v e st h es t e e l m a k i n ga n dc o n t i n u o u sc a s t i n gp r o d u c t i o ns c h e d u l i n g p r o b l e mo fs i n g l er e f i n i n gp r o c e s s 、析t i lt h es a m es t e e l f a c i n g 、析t l lt h ep r o b l e mo f m u l t i p l er e f i n i n gp r o d u c t i o np r o c e s si nl a r g e s c a l ei r o na n ds t e e le n t e r p r i s e ，w e p r o p o s ead e c o m p o s i t i o ns t r a t e g yo fs t e e l m a k i n g c o n t i n u o u sc a s t i n gp r o d u c t i o n s c h e d u l i n gp r o b l e m ，d e c o m p o s et h es c h e d u l i n gp r o b l e mi n t ot w os u b - p r o b l e m s ，o n ei s m a c h i n ea s s i g n m e n tp r o b l e m ，a n dt h eo t h e ri sc o n f l i c te l i m i n a t i o np r o b l e m t h r o u g h t h ee s t a b l i s h m e n to fam a t h e m a t i c a lm o d e lb a s e do nd y n a m i cp r o g r a m m i n g , w e e f f e c t i v e l ya s s i g nt h em a c h i n e s ，a n dd e t e r m i n et h eb e s tp a t ho fe a c hc h a r g e a c c o r d i n g t ot h ec a s t i n gt i m e ，t h em a c h i n ep r o c e s s i n gt i m ea n ds h i p p i n gt i m e ，ar o u g hs c h e d u l i n g p l a nc a nb eo b t a i n e d ，b u ti tm a yb en o ta p p l i e dt oa c t u a lp r o d u c t i o nf o r t h ee x i s t e n c eo f m a c h i n ec o n f l i c t s a c c o r d i n gt ot e c h n o l o g yc o n s t r a i n t sa n dp r o d u c t i o nt a r g e t s ，w e e s t a b l i s hal i n e a rp r o g r a m m i n gm a t h e m a t i c a lm o d e lt oe l i m i n a t et h ec o n f l i c t s ，a n dt h e n g e taw o r k a b l es c h e d u l i n gp l a n t h er e s u l t ss i m u l a t e db yal a r g ei r o na n ds t e e l p r o d u c t i o nd a t as h o wt h a tt h ep r o p o s e dm e t h o di sf e a s i b l ea n de f f e c t i v e i tp r o v i d e sa t h e o r e t i c a lb a s i sa n dp r a c t i c a lm e t h o d sf o rf u r t h e ri m p r o v e m e n ta n dd e v e l o p m e n t i i i 度计划编制优化方法的研究 目录 方法的研究i 1 1 1 ： ： ： 3 1 3 4 生产调度问题优化的主要目标4 1 3 5 生产调度问题的优化方法5 1 3 6 现行调度方法存在的不足1 0 1 4 炼钢一连铸生产调度的研究现状1 1 1 4 1 炼钢一连铸生产调度国外研究现状1 1 1 4 2 炼钢一连铸生产调度国内研究现状1 2 1 4 3 炼钢一连铸生产调度存在的问题1 3 1 5 本论文研究内容与章节安排1 4 2 炼钢一连铸生产调度描述1 5 2 1 引言1 5 2 2 炼钢一连铸生产调度定义和术语1 5 2 3 炼钢一连铸生产工艺流程1 6 2 4 炼钢一连铸生产工艺约束1 8 2 5 炼钢一连铸生产调度的特点1 9 2 6 炼钢一连铸生产调度过程的建模2 0 2 7 本章小结2 2 3 基于改进遗传算法的炼钢一连铸单重精炼调度优化问题的研究2 3 3 1 引言2 3 3 2 遗传算法的基本思想2 3 3 3 遗传算法的操作流程2 4 3 4 遗传算法的操作设计2 5 3 4 1 编码2 6 3 4 2 适应度函数2 6 i v 青岛科技大学研究生学位论文 3 4 3 算法参数2 6 3 4 4 遗传操作2 7 3 4 5 算法终止条件2 8 3 5 遗传算法的特点2 8 3 6 改进遗传算法求解炼钢一连铸单重精炼调度问题2 9 3 6 1 问题描述2 9 3 6 2 数学模型2 9 3 6 3 染色体表示3 l 3 6 4 适应度函数3 3 3 6 5 选择操作3 4 3 6 6 交叉操作。3 4 3 6 7 变异操作3 5 3 6 8 仿真实例3 6 3 7 本章小结3 9 4 基于数学规划的炼钢一连铸多重精炼调度优化问题的研究4 0 4 1 引言4 0 4 2 动态规划方法简述4 0 4 2 1 动态规划方法的特点4 l 4 2 2 动态规划的基本方程4 l 4 2 3 动态规划方法的求解步骤4 3 4 3 动态规划方法解决炼钢一连铸的设备指派问题4 4 4 3 1 设备指派问题描述4 4 4 3 2 设备指派数学模型4 5 4 3 3 仿真实例4 7 4 4 线性规划方法简述5 5 4 4 1 线性规划的基本概念5 5 4 4 2 线性规划的标准形式5 6 4 4 3 线性规划模型的建立与求解5 6 4 4 4 线性规划方法的优点和不足5 7 4 5 基于线性规划的冲突解消5 7 4 5 1 符号定义5 8 4 5 2 生产条件5 8 4 5 3 生产约束5 8 4 5 4 优化目标5 9 v 炼钢连铸调度计划编制优化方法的研究 致谢6 7 攻读学位期间发表的学术论文6 8 独创性声明6 9 v i 9 9 1i鹃羽吼娌斛 型例 一 一 一 青岛科技大学研究生学位论文 1 1 引言 1 绪论 随着科学技术的日益发展，生产规模的日益扩大，复杂性越来越高，市场竞 争也越来越激烈，对企业的管理和对生产过程的监控都提出了更高的要求。在激 烈的市场竞争中，为了保证生产的高效稳定运行，为了获得最大的经济效益，原 本简单、局部、常规的控制和仅靠经验的管理已经不能满足现代生产要求了，企 业管理者目前面临的问题是：如何根据市场上原料供应和市场需求的变化进行经 营决策和组织生产；如何在生产计划不变的情况下对生产过程进行优化，以便最 大限度地提高生产效率；如何在生产工艺进步的前提下进行管理决策，使企业产 生最大的经济效益。生产计划制定与调度过程的优化作为现代生产制造业管理的 关键和核心技术，逐渐成为了人们研究的热点问题。 炼钢一连铸生产是离散和连续相混合的流程式生产过程，而流程系统的生产 调度是一个多任务、多目标、多约束、具有不确定性的n p 难题【l 】，是钢铁企业 生产循环中的关键环节。生产调度的制定既受到市场需求变化的影响，又要受到 生产执行过程中的实时信息的制约。如何合理的制定钢厂实际生产调度计划，缩 短计划作业的编制时间和工序间的等待时间，将有利于提高设备的利用率，保持 工序衔接紧密和生产物流畅通，这也是提高企业竞争实力，获得经济效益的有效 途径之一。所以，研究适合钢铁企业实际生产情况的优化调度方法具有十分重要 的现实意义。 1 2 课题研究背景和意义 市场经济环境下，面对竞争激烈的外部市场，企业必须要通过加强内部生产 管理来提高市场竞争力。与国外相比，国内钢铁行业在生产技术、装备和管理手 段上都比较落后，难以适应市场的需求变化。许多企业虽然引进了一些关键的生 产设备，但由于缺乏科学、合理的整体生产计划，导致这些关键设备的潜能并没 有全部释放出来。通过构建自己的生产调度系统，实现集中优化调度管理，可以 改变过去由于人工编制生产计划，多层管理造成的不合理、效率低下的状况。 随着钢铁生产的发展以及用户需求的不断扩大，一个十分严峻的问题摆在了 钢铁生产管理者面前，就是在不断提高产量的同时，如何不断提高质量、效率， 炼钢连铸调度计划编制优化方法的研究 缩短交货周期，确保用户产品质量和交货期的需求。如何保证铁水、钢水的温度、 时间、成分等都符合各工序的要求，如何保证各工序之间的物流平衡，如何保证 设备的利用率、提高作业率等都是炼钢调度当前迫切需要解决的问题。由于钢厂 生产的复杂性、不确定性，采用单一的方法难于有效解决生产调度问题，集成调 度方法是解决钢铁生产调度问题的新途径。 炼钢连铸作为钢铁生产的核心工序，其生产调度水平的高低直接影响整个企 业的生产效率和生产效益。目前，许多钢厂对炼钢连铸生产过程的调度都是基于 人工和经验的。由于高温钢水不允许长时间停留，现场对调度时间的要求很苛刻； 如果在生产过程中出现了异常，调度人员很难在短时间内做出合理的调度，这样 就容易造成物流堵塞或设备闲置，严重时还会造成钢水冻结、连铸断浇，影响炼 钢连铸生产的顺畅运行等一系列后果。为此，如何利用有效的方法快速生成调度 计划表，合理地调度炼钢连铸实际生产计划，将大大缩短计划作业的编制时间和 工序间的等待时间，有利于提高连铸水平和加工设备的利用率，取得显著的经济 效益，这是目前国内钢厂迫切需要解决的问题。所以，将经典调度理论与实际生 产相结合，寻求合适的建模与优化调度方法具有重要的理论意义和实用价值，这 也是本文的研究意义所在。 1 3 生产调度问题概述 1 3 1 生产调度问题的描述 生产调度问题一般可以描述为：针对某项可分解的计划，在一定的约束条件 下，如何安排其组成部分的所占用资源、加工时间及先后顺序，以达到产品制造 时间或者成本最优等目标。具体描述如下： 现有n 个工件，需要将其安排到m 个设备上加工，问题是如何将n 个工件 合理地分派到m i 个设备上，确定工件在每台机器上的最优加工顺序，并满足如 下生产工艺约束条件： ( 1 ) 每台机器同一时刻只能加工一个工件； ( 2 ) 一个工件不能同时在不同的机器上加工； ( 3 ) 使生产的某一性能指标( 如：等待时间，最大流程时间达到最小等) 或综合指标达到最小或最大。 1 3 2 生产调度问题的特点 生产调度作为生产管理最为困难的问题，它具有以下几个共有的特点： 2 青岛科技大学研究生学位论文 ( 1 ) 复杂性：由于实际生产过程中各任务、各工序之间是相互影响、相互作 用的，生产工艺的多样性加上约束条件的不确定性都会导致调度问题规模的增 加，调度方案的选择和求解调度问题的难度也越来越高，使得调度问题成为多任 务、多约束、多目标、随机不确定性的优化问题，这已被证明是n p h a r d 问题【2 l 。 ( 2 ) 不确定性：生产调度的不确定性主要体现在它的随机性和模糊性上。它 主要包括系统固有的不确定性、生产过程中产生的不确定性、外部环境的不确定 性和离散的不确定性四种【3 l 。生产设备加工时间的不确定性、物料运输的随机性 及设备故障的偶发性等，这些不确定性往往严重影响生产计划和生产调度方案的 正常执行，使得调度问题也被称为随机优化问题。 ( 3 ) 多约束性 像人力、设备、原材料等生产资源的数量、市场的供求变化、产品的生产期 和交货期以及产品的生产工艺流程等都是约束。众多的约束限制更增加了调度问 题的建模和求解的难度。 “) 多目标性 生产调度的目标有很多，如最短生产周期、最小提前拖期惩罚、最高设备利 用率、最大生产利润等，要使各个目标都达到最优往往是很困难的。 1 3 3 生产调度问题的分类 生产调度按照不同的分类标准，有不同的分类方式，主要有以下几种分类方 式： 1 ) 按系统处理的复杂性：可分为单机调度、多机调度、流水车间调度、作 业车间调度。 单机调度指的是所有工件都要在指定的单台机器上加工完成，即单机排序问 题；多机指的是完成某种功能的机器不止一台；流水车间调度是指所有工件的加 工路径完全一致，这样，整个生产过程如同流水线一样，工件依次从流水线的一 端进入，从另一端流出；作业车间里的机器设备的布局可以是任意的，因此工件 的加工路径也是任意的，并且各工件的工序和数量也是任意的【4 】。 2 ) 按调度环境的特点：可分为静态调度和动态调度。 静态调度是指待加工的工件、设备、加工时间等都是固定不变的，在生产过 程中全部待加工的工件都要全部到位，不考虑工件在加工过程中出现的意外扰动 状况，如工件的交货期提前或拖后、设备突然故障、紧急的任务更改等等：而动 态调度是指加工工件、相关资源、相关参数等都是随时间变化的，要求考虑到工 件在加工过程中可能发生的各种意外扰动情况。 3 炼钢连铸调度计划编制优化方法的研究 3 ) 资源约束种类和数量：可分为单资源车间调度和多资源车间调度。 资源车间调度指车间的生产加工能力只受一种资源的制约，一般指在车间生 产中，设备的数量不能满足所有可加工的工序在同一时刻被加工的要求。多资源 车间调度是指同时有两种或两种以上的生产资源条件制约着生产车间的生产能 力，多资源车间调度问题是最复杂的一种。 4 ) 按是否考虑不确定性因素：可分为确定性调度和不确定性的调度两类。 确定性调度是指调度中所用的参数都是确定的数值，建立的数学模型较为简 单，处理起来也比较简单，但适用的范围较小。不确定性调度是指生产过程中的 某些参数不是固定不变的，而是与实际生产过程中的相关时间、温度等变化有关。 1 3 4 生产调度问题优化的主要目标 多目标性是生产调度问题的一个显著特点，生产调度问题的目标一般主要包 含两大类，一类是基于经济指标，另一类是基于性能指标的。在多层高级调度结 构中，高层的生产计划通常需要基于经济的目标函数，这类指标通常在理论研究 中涉及较少；低层的调度需要完成任务的排序与调度，通常是基于性能的调度目 标，这类指标是学者研究的主要内容，实际生产调度的性能指标大致可以归结为 三类： 1 ) 最大能力指标，包括最大生产率、最短生产周期等，调度问题的主要目 标为提高生产设备的利用率、缩短产品的生产周期，使工厂生产能力最大。因此， 这类生产调度问题可以称为最大能力调度问题。体现该类性能指标的主要有生产 所有产品所需要的总时间即为最小；产品的生产流程时间，即产品完全通过生产 过程所需要的时间最小；设备的使用效率最高。它们可使过程的资源利用率与生 产率最大，这类指标是也最常见、最普遍的调度目标。 2 ) 成本指标，包括最大利润、最大收益、最小化运行费用、最小投资等， 其中收益指产品的销售收入，运行费用包括库存成本、生产成本和缺货损失。 3 、1 客户满意度指标，包括最短的延迟，最小提前或者拖后惩罚，平均延迟 时间最小等，延迟时间为产品的生产完成时间与交货期之差，只取正值。 本文所研究的炼钢连铸生产调度问题分别针对不同的生产情况，确立了如下 优化指标： l 、1 以最小化流程时间为指标，运用改进遗传算法编制出可行的炼钢连铸生 产作业计划。 2 1 以最小化炉次计划时间为指标，利用动态规划方法解决炼钢连铸的设备 指派问题。 4 取得一定成果。现有研究方法主要有数学规划方法、仿真模型方法、人工智能方 法、计算智能算法、人机交互方法和混合优化方法六大类，如图1 1 所示。各类 方法在钢铁生产作业计划与调度中都得到不同程度地研究与应用，其中，基于智 能的方法和基于算法改进的方法研究较多。 1 3 5 1 数学规划方法 数学规划方法是将生产作业计划及调度优化问题归结为在等式或不等式的 约束下，对一个或多个目标函数进行的优化，通常用混合整数线性规划优化模型 ( m i l p ) 或混合整数非线性规划优化模型( m i n l p ) 来描述。数学规划方法在任务分 配和排序上有良好的全局性，所有的选择能同时进行，因此可以保证求解问题的 全局优化。 ( 1 ) 动态规划法 动态规划既是一种建模方法也是一种优化方法。动态规划思想是将待求解的 问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的 解。动态规划算法主要研究解决多阶段决策过程的最优化问题，将求解分成多阶 段进行，求出的不但是全过程的解，而且包括其子过程的一族解。该算法是一种 全局优化方法，统筹全局，把它应用到生产调度领域，不但可以避免传统加工中 按经验安排工艺路线时的局部优化问题，又可以在整个时间段上把一个全局解的 问题分解为一系列在各个时间段上的局部优化问题。正是由于这种优越性，关于 动态规划在生产调度问题中的研究也越来越多。1 9 6 2 年，h e l d 等人将动态规划方 法应用到生产调度问题上，使动态规划成功地解决了生产计划、资源分配等问题 【卯。在韩国的一个小型钢铁厂，为了能短时间内生成一周的生产调度计划，提高 连铸比和板坯直送率，p a r k 等利用动态规划方法为建立了基于有限缓冲空间的冶、 铸、轧一体化生产调度模型【6 】；文献【7 】为解决单机调度问题建立了以提前期和拖 期惩罚费用最小为目标的动态规划模型，并采用对状态空间松弛的方法对其进行 求解；文献 8 】提出向前递推和向后递推的动态规划算法来解决流水车间调度问 题，并给出了适用哪种算法的问题特征。 炼钢连铸调度计划编制优化方法的研究 图l l 生产调度方法的分类图 f i g 1 - 1c l a s s i f i c a t i o nc h a r to ft h ep r o d u c t i o ns c h e d u l i n gm e t h o d ( 2 ) 分枝定界法 分枝定界法是将调度问题的所有可行解动态的表示成“树的形式，通过将 线性规划问题减少上界和增大下界的办法，实现对树进行搜索以寻找调度问题的 最优解。分枝定界法的研究重点为提高分枝和定界的策略，p a r k 等利用分支定界 算法解决了带交货期约束的产品调度问题，能在可接受的计算时间内能找到优化 解【9 】。 ( 3 ) 拉氏松弛法 拉氏松弛法在可行的时间范围内能对复杂的规划问题提供比较好的次优解， 6 青岛科技大学研究生学位论文 并对解的次优性进行定量评估，使之成为解决复杂车间调度问题的一种重要方 法。唐立新等建立炼钢连铸生产调度整数规划数学模型并采用拉格朗日松弛法进 行求解，能快速得到合适的生产作业计划【i 们。 1 3 5 2 仿真模型方法 仿真模型方法通过对实际生产环境的建模来模拟实际生产过程，并通过仿真 模型采集数据，避开了对复杂制造流程计划与调度问题进行理论分析的困难，能 对实际生产进行性能、状态等方面的分析，成为了一种解决复杂调度问题的有效 方法。 ( 1 ) p e t r i 网模型方法 p e t r i 网作为一种图形建模工具，不但可以表示和分析实际生产加工过程的并 发和分布，还可以表示多个作业共享资源时发生的冲突现象，具有很强的建模能 力。李霄峰等以炼钢连铸生产为背景，首先运用赋时弧有色p e t r i 网建立各设备 的动态调度模型，进而获得整个生产的动态调度模型，并针对该模型提出一种启 发式调度算法来实现炼钢连铸生产过程的仿真【i 。用p e t r i 网进行建模，需要把 各种事件以及事件间的关系在模型结构中体现出来，这样就会导致模型复杂度高 且可重用性不强；在建模时的简化则会导致实际生产与模型的设计不相符，模拟 或仿真失效，难以实现对真实过程的准确模拟。 ( 2 ) 细胞自动机炼钢生产物流仿真模型方法 细胞自动机炼钢生产物流仿真模型是借助细胞自动机“自下而上的建模思 想，用工件、工位、规则来描述炼钢生产物流系统【1 2 1 。该模型研究尚处于起步阶 段，但相关研究表明该模型能有效地模拟复杂的生产制造流程，体现炼钢生产物 流系统的特征，通过仿真可对生产调度问题进行深入研究。 1 3 5 3 人工智能方法 人工智能方法是指用人工的方法使机器具有与人类智慧类似的判断、推理、 学习、识别、问题求解等功能。人工智能技术是解决调度问题的有效方法，包括 的主要方法有基于知识、规则的方法、神经网络、m u l t i a g e n t 算法等i l 引。 ( 1 ) 基于知识、规则的方法 基于知识、规则的方法通常是将知识和现场各种约束表示成知识或规则，在 应用过程中根据实际生产情况以及目标选择相应的知识或规则解决问题，它主要 包括启发式方法和专家系统。 启发式方法 启发式方法的本质是根据各个生产任务和操作的优先级顺序选择合适的任 务和操作，具有简单、快捷、易于实现、能在合理时间内生成比较满意的解等优 点，因此在实际调度中应用比较广泛。启发式规则在生产计划与调度优化问题中 7 炼钢连铸调度计划编制优化方法的研究 常被称为调度规则，并在很早以前就开始研究。文献【1 4 】研究了采用基于炉次 派规则和冲突消解规则的启发式算法来解决炼钢连铸生产调度问题，能得到较 的调度方案。启发式方法通常仅对一个目标提供可行解，对整体性能的把握和 见能力较差，因而在实际应用中启发式规则常常与其它方法结合使用，利用其 方法根据具体情况来选择合适的规则。 专家系统 专家系统通常将领域知识和现场的各种约束表示成知识库，然后按照现场实 情况从知识库中产生调度方案，它能对意外情况采取相应的对策。专家系统在 铁工业的生产调度中占有很重要的地位，并出现了一些较成熟的调度专家系统 i s i s 和o p i s 等；在专家系统的应用中，知识获取是“瓶颈，且系统好坏依 赖于领域模型、知识表示以及对约束的满足程度，当问题偏离知识领域时系统的 性能将急剧下降。 ( 2 ) 神经网络 神经网络能进行大规模的并行处理，具有很强的容错性、自组织和自适应能 力。王万良等对作业车间调度问题的换位矩阵表示法进行了改进，提出了改进的 h o p f i e l d 神经网络作业车间调度方法【l5 1 。但神经网络用于调度问题研究时为保证 调度效果，就需要大量训练样本和较长的训练时间，这样对结果就缺乏解释能力， 且存在算法复杂性大，结构参数难以确定，难以表达多知识等问题。 ( 3 ) m u l t i - a g e n t 算法 m u l t i a g e n t 方法是将每个小单元看作一个小智能体，通过各个智能体之间的 协商来完成一定的功能。它能很好处理单元间存在大量交互作用的问题，对于复 杂问题运行弹性强、实时性强、可靠性高。m u l t i a g e n t 方法为解决复杂制造过程 的生产调度问题提供了灵活、高效的解决方案，已成为智能制造领域的研究热点 和重要方法【1 酗，并开始用于钢厂的炼钢连铸生产调度问题的研究【1 7 1 。m u l t i a g e n t 方法的局限性在于各a g e n t 的构建受建模人员的经验制约，且各a g e n t 之间合适 的协商机制也较难建立。 1 3 5 4 计算智能算法 随着计算机技术以及并行计算的发展，许多基于模拟自然界的某些演化机制 的计算智能方法被广泛应用于生产调度问题研究中，并取得了很好效果。 ( 1 ) 禁忌搜索算法( t a b us e a r c h ，简称t s ) t s 最早由o l o v e r 提出，是对人类智力过程的一种模拟【l 引。它扩展了局部邻 域搜索能力，是一种具有记忆功能的全局逐步优化算法。目前t s 已经在生产调 度、交通运输、电子电路设计等诸多领域得到应用。孙福权等将t s 应用于钢厂 生产调度的浇次计划制定中，缩短了生产周期和降低了能耗【1 9 1 。禁忌搜索算法中， 8 青岛科技大学研究生学位论文 初始解的优劣对算法的收敛速度影响较大。 ( 2 ) 模拟退火算法( s i m u l a t e d a n n e a l i n g ，简称s a ) s a 思想是在某一初始温度下，伴随温度参数的不断下降，结合概率突跳性 在解之间随机寻找目标函数的全局最优解。宁树实等提出了一种炼钢连铸生产计 划一体化编制方法，通过建立炉次计划和浇次计划的数学模型，分别采用多目标 模拟退火算法和变邻域搜索算法求解次和浇次计划问题，最后得到一体化生产计 划 2 0 l 。但随着生产作业计划与调度问题规模增加，s a 的收敛速度迅速减慢。 ( 3 ) 遗传算法( g e n e t i c a l g o f i t h m ，简称g a ) 美国m i c h i g a n 大学的j h h o l a n d 2 l j 于本世纪末提出了一种新的并行优化搜索 方法：遗传算法，它是一种基于进化论中自然选择、优胜劣汰、适者生存和物种 遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化搜索。由于 g a 原理和操作简单，通用性强，不受限制条件的制约，且具有隐含并行性和全 局搜索能力，在机器学习、模式识别、控制工程、优化等领域，尤其是在生产调 度领域得到广泛的应用。 g a 是一种基于适者生存思想的高度并行、随机的自适应优化算法。通过种 群的更新进化，容易快速找到优化解，且易与其它算法相结合。由于种种优越性， 近年来，它在钢铁铁生产中的应用最为广泛。王万良等采用双倍体遗传算法来求 解模糊流水车间调度问题，得到较好的调度方案瞄】：崔建双等建立钢铁生产混合 流水车间调度模型，利用工序和工件混合编码的改良遗传算法求解得到近优的生 产作业计划，提高了作业计划的精度和效率四】。但遗传算法的适应函数较难选取， 随着问题复杂度增加，解的搜索空间迅速增大，搜索时间增长，并可能出现早熟 收敛。 ( 4 ) 蚁群算法( a n tc o l o n y a l g o r i t h m ，简称a c a ) a c a 是最近几年才发展起来的智能搜索算法，它有较强的通用性、并行性、 鲁棒性，且易与其它算法结合。用蚁群算法研究生产调度领域时，一般将生产调 度问题转化为类似于j o b s h o p 问题析取图的解构造图，调度方案是通过确定在同 一机器上加工的各工序顺序来得到的【2 4 】。但蚁群算法的计算时间长、易出现停滞 现象，“信息素 分配的合理性直接影响搜索效率。 ( 5 ) 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) p s o 算法是受鸟群觅食行为的启发而提出的，算法的核心部分是采用速度 位置搜索模型【2 5 1 。该算法具有基于种群的全局搜索能力，是一种更高效的并行搜 索算法。粒子群算法是新兴的算法，理论方面还不够成熟，但目前已经广泛应用 于函数优化、计划和调度问题等领域。粒子群算法在算法早期存在精度较低、易 发散，而后期存在收敛速度明显变慢等缺点。 9 了更好地解 热点，通过 的优势，弥 补各自的缺点，使应用范围更广、适应性更强，达到高度优化的目标。曾齐红将 启发式方法与遗传算法有机结合起来求解炼钢连铸的浇次排序问剐2 7 】；崔志华等 将遗传算法与禁忌搜索算法集成，设计了一种基于t a b u 搜索策略的非线性遗传 算子来求解连铸生产调度的数学模型，并得到了最优解1 2 引。 1 3 6 现行调度方法存在的不足 上述各种调度算法得到国内外学者的广泛研究，并在实际生产中得到不同程 度地应用，解决了部分生产实际中的生产作业计划与调度优化问题，大大改善了 企业的生产管理方式、提高生产效率和降低生产成本。但是，理论研究还存在一 定的局限，主要表现在以下几个方面： ( 1 ) 模型抽象与生产实际的差距 研究生产作业计划与调度优化问题时，一般以问题抽象而来的数学模型为基 础，再寻求模型的求解算法。建模时，往往需要对真实环境进行大量简化，由于 问题简化的程度和模型抽象的合理性决定了所建数学模型与实际生产过程的相 似度，所以过于简化的数学模型就难以符合复杂的实际生产环境，编制出的生产 作业计划和调度方案就难以满足实际生产要求。 ( 2 ) 调度算法与调度问题复杂性的差距 虽然针对生产调度问题的调度算法已经有很多并取得不错效果，但由于实际 生产调度的随机性和不确定性导致调度问题的n p 性质，简单算法通常不能在调 度实时性和解的优化效果等方面很好地解决调度问题，因此，有必要在原有调度 算法基础上继续进行深入研究，从而获得求解速度快且能得到可执行的优化解的 调度算法。 1 0 青岛科技大学研究生学位论文 ( 3 ) 模型和算法的适应性不强，应用中存在局限性 在生产作业计划与调度优化理论研究中，一般针对特定问题建模后再设计相 应的求解算法，使得模型有较强的结构化特征，而且算法也存在一定的适用范围 限制。因此，当生产环境或应用对象的生产工艺发生变化时，原先设计好的模型 和算法不具备适应动态变化生产环境的能力。 因此，深入研究生产作业计划与调度优化问题的主要特征因素，结合实际生 产环境建立真实的生产调度的数学模型是很有必要的；另外，还要考虑调度问题 实时性和解的优化效果满意度来寻找合适的调度算法来求解数学模型；此外，在 建模、算法设计和系统实现时，必须结合行业背景、工艺约束等实际情况来考虑 模型和算法的适用性和可行性。 1 4 炼钢连铸生产调度的研究现状 1 4 1 炼钢连铸生产调度国外研究现状 由于制定合理的炼钢连铸生产计划与调度，对于物流生产的稳定运行，提高 生产率和设备利用率，降低能耗有重要作用，能极大提高劳动生产率，带来显著 的经济效益，国际上极为重视这一课题的研究。 n u m 8 0 等用人工智能和人机交互结合的方法解决炼钢连铸调度问题，d o m 等提出了基于f u z z y 集合和人工智能相结合的方法研究炼钢连铸调度问题l 2 9 1 。奥 地利g m b h 钢厂提出了炼钢连铸调度的建模关键因素，并对炉次在各机器上的分 配给出了调度模式【3 0 】。 日本京滨钢铁厂的协同生产调度系统s c h e p l a n1 3 1 1 根据上级系统的计划数据 和标准数据，利用人工智能和人机交互技术，由调度机、知识库和用户接口生成 调度计划，根据实际生产情况产生各阶段调度方案，在日本京滨钢铁厂得到广泛 应用，极大提高了生产效率。 韩国浦项钢铁公司的光阳钢铁厂研发了综合过程与调度系统h i p a s s 3 2 1 ，该 系统能够从铁水处理到轧制成材全过程进行一体化管理，能为企业生产制定出多 层生产计划，最后编制出各工序的详细作业计划。 a i s 公司研发的s t e e lp l a n n e r 套件可根据连铸规则自动生成连铸计划，制定 生产计划，进行供应链管理，为生产调度提供辅助决策，已在2 7 个国家中的4 0 多个钢厂得到应用，提高了生产效率，降低了生产成本【3 3 】。 国外除上述介绍的生产计划与调度系统外，还有日本五大钢铁公司( 新日铁、 日本钢管、住友、川崎、神户) 的钢铁厂建立的支持热装热送的集成化计算机生 炼钢连铸调度计划编制优化方法的研究 理系统：日本住友和歌山钢铁厂合作开发的用于实现连铸作业调度计划编制 的专家系统；澳大利亚b h p 钢铁公司开发的交互调度和实施生产监控智能调 统i s a 等等。 总之，国外的钢铁调度水平已经日臻成熟，先进的一体化管理极大的提高了 的生产效率和生产效益。 炼钢连铸生产调度国内研究现状 我国对炼钢连铸生产调度问题的研究起步比较晚，随着生产和技术水平的不 高，从系统和整体的角度考虑钢厂的计划优化越来越重要，国内很多学者在 面进行了研究。 在理论研究上，东北大学徐心和教授结合我国具体情况，对炼钢连铸热轧 一体化管理的内容、条件、意义以及国外情况进行了系统的阐述【3 4 1 。针对炼钢一 连铸调度中的机器冲突问题，唐立新建立了基于准时制调度思想的数学模型，经 过变换，将非线性规划问题转化为线性规划问题，用标准线性规划方程进行求解， 使这一模型能够应用于实际生产【3 5 l 。清华大学韩曾晋采用一种区段赋时弧有色 p e 仃i 网，建立了一个炼钢连铸生产过程的实时调度模型，基于这一模型，既可 以仿真整个生产过程，又可以分析实时生产调度策略p 6 j 。庞哈利