（管理科学与工程专业论文）钢铁行业的pjssp研究及其软件求解.pdf

摘要 摘要 生产调度以生产作业计划为依据，围绕企业的生产经营目标，从生产全局 出发，结合生产流程的实际情况和生产能力，进行优化排产，合理调配物料和 能源，调整各装置间物流的分配，协调和均衡各装置的生产，使各生产环节能 有效配合和紧密衔接，形成并传达优化调度指令，确保生产均衡、稳定、安全、 长周期地进行，以保证企业生产作业计划的完成。而随着钢铁企业信息化的深 入，迫切需要符合企业生产调度流程的模型和算法，为生产决策提供支持。 本文首先对从生产调度理论，j o b - s h o p 调度问题以及钢铁行业中的生产调 度问题三个方面进行简明综述和国内外现状介绍。然后针对国内大型钢铁企业 钢管冷加工区生产调度的实际问题，在生产连续、库存限制、部分人工调度的 情况下，提出利用离敌化时间的方法，将该问题抽象成可中断的j o b s h o p 问题， 并分别用数学规划方法和启发式方法进行模型和算法研究。 根据冷加工区的生产约束条件( 库存、部分人工调度、连续生产等) ，以中 断次数最少为目标建立了混合整数规划模型，并利用i l o g 公司c p l e x 软件包对 算例进行编程求解。但是有时候由于部分人工调度的原因造成约束条件无法满 足，导致无法找到可行解。针对这种情况，通过将部分人工调度转化成目标和 约束条件来改进数学模型，并提出了启发式方法来求解：首先建立启发式算法 的一系列调度规则，再根据调度核心即占优规则设计调度算法。该算法还有改 进的必要，提出了改进后的二阶段启发式算法，第一阶段根据四种调度规则( 基 于j o b 最初顺序，基于s p t ，基于e r t ，基于e d d ) 来优先调度约束最松弛的 产区；第二阶段和启发式算法类似。用改进后启发式算法得到的结果比较理想。 然后对同一算例，三种算法得到的六组调度结果进行了租略评价，最终得到结 论：对于该问题，解决方案最好的是改进后启发式算法( s p t ) ；数学规划( i l o g c r i l e x ) 和改进启发式算法( e d d ) 次之，而改进启发式算法( e r t ) 也比较理想，但是 改进启发式算法( j o b 顺序) 和启发式算法最差。 最后，对现有工作进行了总结和对进一步研究方向进行了简要的展望。 关键词：钢管生产，可中断j o b s h o p 调度问题，数学规划，启发式算法，软件 求解 a b s t r a c t a b s t r a c t a c c o r d i n gt ot h ej o bp l a n ，a i m i n ga te n t e r p r i s e sb u s i n e s sa n dw h e na l lc o m e s t o a l l ，p r o d u c t i o ns c h e d u l i n gc o m b i n e sr e a lp r o d u c t i o np r o c e s sa n dr e c e n tp r o d u c t i o n c a p a c i t yt oo p t i m i z et h ep r o d u e t i o np l a na n dt oc o n t r o lm a t e r i a l sa n de n e r yt o c o o r d i n a t e t h ed e l i v e r ya m o n gt h em a c h i n e ss ot h a ti tc a nm a k et h ep r o d u c t i o n b a l a n c e da n dc o n c e r t e do na l lt h em a c h i n e sa n dp r o d u c t i o np h a s e se f f e c t i v e l y c o n n e c t e da n dt i g h t l yl i n k e du p t h e r e f o r eu n d e rt h eo p t i m i z e di n s t r u c t i o n , t h e p r o d u c t i o np r o c e s sw o u l db eb a n l a n e e d ，s t a b l ea n ds a f ei nal o n gt e r n l w i t ht h e d e e p e n i n go fi n f o r m a t i o n i z a t i o ni nt h ei r o na n ds t e e li n d u s t r y , t h e s ee n t e r p r i s e sr e a l l y n e e dt h em o d e l sa n da l g o r i t h m si nl i n ew i t ht h e i rp r o d u c t i o np r o c e s st os u p p o r tf o r p r o d u c t i o nd e c i s i o n s f i r s t l yt h i sp a p e rb r i e f l yr e v i e w e dt h ed o m e s t i ca n df o r e i g nr e s e a r c hs t a t u sq u o i nl i g h io fp r o d u c t i o ns c h e d u l i n gt h e o r y , j o b - s h o ps c h e d u l i n gp r o b l e m sa n dt h e s c h e d u l i n gp r o b l e m si ni r o na n ds t e e li n d u s t r y a n ds e c o n d l y 、i t l lr e g a r dt ot h er e a l p r o b l e mi nt h ep r o d u c t i o no fs t e e lp i p e so fal a r g ed o m e s t i ci r o na n ds t e e le n t e r p r i s e ， u n d e rt h ec o n s i d e r a t i o no fc o n t i n u o u sp r o d u c t i o n ，i n v e n t o r yr e s t r i c t i o na n dp a r t i a l m a n u a ls c h e d u l i n g ，t h ep r o b l e mi sa b s t r a c t e di n t oap r e e m p t i v ej o b s h o ps c h e d u l i n g p r o b l e mb yt i m es l i c i n g a n dt h e nt h ep r o b l e m sm o d e l sa n da l g o r i t h m sw e r e r e s e a r c h e ds e p e r a t i v e l yi nm a t h e m a t i c a lp r o g r a m m i n ga n dh e u r i s t i cm e t h o d a c c o r d i n gt ot h ep r o d u c t i o nc o n s t r a i n t s ( s t o r a g e ，p a r t i a lm a n u a ls c h e d u l i n g ， c o n s e c u t i v ep r o d u c i n g ) a n db ya i m i n ga tt h em i n i m u mp r e e m p t i v e t i m e s ，a m i x e d i n t e g e rp r o g r a m m i n gm o d e lw a se s t a b l i s h e da n dc o u l db es o l v e db yu t i l i z i n g i l o gc p l e xs o r w a r ep a c k a g e h o w e v e r , b e c a u s eo f t h ep a r t i a lm a n u a ls c h e d u l i n g ， s o m e t i m e st h ef e a s i b l es o l u t i o nc a n n o tb ef o u n d t h e nt h eh e u r i s t i cm e t h o dw a sp u t f o r w a r da r e rc h a n g i n gt h em o d e l sa i ma n dc o n s t r a i n t s a sf o rt h eh e u r i s t i ca l g o r i t h m ， s o m er u l e sw e r es u m m e du pa n dah e u r i s t i cm g o f i t h mw a sd e v e l o p e d t h es o l u t i o n w a sr e c e p t a b l eb u ti ts t i l ln e e d e di m p r o v i n g t h e ni nt h ei m p r o v e dt w o - p h a s e h e u r i s t i ca l g o r i t h m , f o u rr u l e s ( b a s e do nj o bs e q u e n c e ，s p t e r ta n de d d ) w e r e 垒! 里型_-。_-_-。_-_-。-。_。_。_。_。1。 a p p l i e dt os c h e d u l et h es l a c k e s tp r o d u c t i o nl i n es e p c r a t i v e l yf o r t h ef i r s tp h a s ea n dt h e c 0 玎do f l ew a ss i m i l a rt ot h eh e u r i s t i ca l g o r i t h m t h es o l u t i o n sw e 心m o r ei d e a l w h a t sm o r e ，a p p l i e dt ot h e & a m ec a s ee x a m p l e ，t h es i xs o l u t i o n sg a i n e db yt h r e e a l g o r i t h m sw e r ec o m p a r e du n d e rr o u g he v a l u a t i o na n d t h ec o n c l u s i o nw a st h a tt h e b e s to n ew a si m p r o v e dh e u r i s t i ca l g o r i t h m ( s p t ) ；t h eb e t t e ro n e sw e r em a t h e m a t i c a l p r o g r a m m i n g ( i l o gc p l e x ) a n di m p r o v e dh e u r i s t i ca l g o r i t h m ( e d d ) a sw e l l ；a n d t h e ni m p r o v e dh e u r i s t i ca l g o r i t h m ( e r d ；t h ew o r s t 毗i m p r o v e dh e u r i s t i c a l g o r i t h m ( j o bs e q ：1 1 跖c 旬a n dh e u r i s t i ca l g o r i t h m f i n a l l y , t h ec o n c l u s i o ni sm a d ea n dt h ep r o b l e m sr e q u i r i n gf u r t h e rs t u d i e sa r c b r i e f l yd i s c u s s e d k e yw o r d s ：s t e e l p i p ep r o d u c t i o n , p r e e m p t i v el o b - s h 0 9s c h e d u l i n g p r o b l e m , m a t h e m a t i c a lp r o g r a m m i n gm e t h o d ，h e u r i s t i ca l g o r i t h m , s o f t w a r e s o l u t i o n i i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 糊一躲钭麟 矽孑年l 弓月i 移日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 沙子年弓月i 移f 1 岛纽 f 众 第1 章绪论 1 1 研究背景 第1 章绪论 生产计划与调度是企业生产运作管理的核心问题，计划的合理性直接决定 了企业的生产效益。目前许多大型企业已经建立了较完善的信息系统，对生产 状况进行全面的监控，但由于缺乏科学的理论和有效的工具，计划和调度仍然 停留在手工阶段，而制定计划和调度决策时要考虑的因素很多，约束条件复杂， 工作量极大，使计划人员只能疲于应付，以实现计划的优化。因此在信息系统 中运用科学的调度理论和模型为计划人员提供决策支持已成为当务之急。 本文的课题来源是上海市科学技术委员会的科研计划项目“任务可中断的 j o b s h o p 调度问题模型、算法研究与应用”，依托上海宝山钢铁股份有限公司的 钢管厂管理信息系统钢管高级生产计划与排程系统( a p s 系统) 项目。 调度( s c h e d u l i n g ) 是指为工作任务合理分配资源和时间，这是一个决策过 程，存在一个或多个优化目标。在制造型企业中，调度对于提高生产效率起着 至关重要的作用。企业根据目标市场的经营状况制定中期如月生产计划后，计 划人员要根据本月的生产任务和机器设备情况，排定生产任务在各设备上的生 产顺序，以满足交货期、设备产能等约束，并实现生产连续均衡，减少中间库 存等优化目标。 根据设备情况，调度问题分为单机、并行机、f l o w - s h o p 、j o b - s h o p 等，而 j o b - s h o p 调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，简称j s s p ) 是其中最复杂的 一类问题，它是许多实际生产调度问题的简化模型，是一个典型的n p - h a r d 问题， 也是目前研究最广泛的一类典型调度问题。j s s p 研究n 个任务在m 台机器上的 加工，每个任务由多个操作( o p e r a t i o n ) 构成，已知各操作的加工时间和在各 机器上的次序约束，要求确定各任务在各机器上的加工开始和完成时间以及加 工次序，使总加工时间( m a k e s p a n ) 等指标达到最优。j s s p 按照任务在加工过 程中是否可中断，又可分为任务可中断型( p r e e m p t i v ej o b - s h o ps c h e d u l i n g p r o b l e m ，简称p j s s p ) 和不可中断型( n o n p r e e m p t i v ej o b - s h o ps c h e d u l i n g p r o b l e m ，简称n p j s s p ) 。 第1 章绪论 选择钢铁行业的p j s s p 作为研究对象，主要是基于以下两方面的原因： i ) p j s s p 理论基础研究比较少，需要完善。由于任务不可中断是调度问题的 基本形式，已有的研究主要是针对n p j s s p ，如a d a m s 等( 1 9 8 8 ) 提出的s h i f t i n g b o t t l e n e c k 算法，c h e n g 等( 1 9 9 6 ，1 9 9 9 ) 研究的遗传算法以及c a s e a ue t 等( 1 9 9 5 ) ， n u i j t e n 等0 9 9 6 ) 等研究的约束规划方法。任务可中断时，j s s p 不再是简单的排 定各操作在各机器上的加工顺序，而是为各操作合理分配加工时间，使生产连 续均衡。目前有e w af i g i e l s k a ( 1 9 9 9 ) 提出用二阶段的列生成技术与遗传算法来解 决可中断i o b 在无关并行机上的调度问题；y o u n gs uy o n 等( 2 0 0 2 ) 提出了遗传算 法分别结合模糊逻辑运算器或调度规则的方法；b a p t i s t e 等( 2 0 0 1 ) 提出了p j s s p 的约束规划方法，并且没有考虑中间库存、生产连续等生产实际中常见的约束； e a k c o r a 等( 2 0 0 4 ) 提出了启发式的方法。因此有待进一步深化。 2 ) 市场应用前景广阔，潜在效益巨大。在制造企业特别是钢铁制造企业中大 量的生产调度问题可以抽象为p j s s p ，随着这些企业信息化的深入，迫切需要符 合企业实际的模型和算法为生产决策提供支持。目前在钢铁企业中熟加工区的 轧批排序和冷加工区的生产调度都还停留在手工操作水平上，尽管生产计划的 编制有一套较完整的规则，但由于计划过程中存在着大量的人工协调和资源平 衡，计算工作量非常大，有限的人力使得协调和平衡的准确性及效果大打折扣。 目前许多大型钢铁企业已经建立了较完善的信息系统，对生产状况进行全面的 监控，但计划和调度仍然停留在手工阶段，因此钢铁行业中的p j s s p 研究有着 广泛的应用前景。 1 2 研究思路 论文研究思路是针对钢铁行业中的p j s s p 河题进行抽象，根据其优化目标， 约束条件等建立合适的数学模型，对该数学模型用适当的算法进行求解，最后 对不同的算法进行比较和检验。因此研究思路可以用图1 1 表示： 第1 章绪论 1 2 1p j s s p 模型 图1 1 研究思路 ( 1 ) 约束描述方法。可以用混合整数规划( m i p ) 模型来描述p j s s p ，在 模型中如果采用合理的约束描述方法则能有效的缩小解空间，否则会导致增加 大量辅助变量，使求解更加困难。 ( 2 ) 优化目标。实际问题中可能存在多个优化目标，有的可能是一致的， 有的则相互冲突，必须分析各目标之间的关系，选择一个合理的目标以便于求 解，或者将其他目标转化为约束条件。 ( 3 ) 占优规则。对p j s s p 问题及模型进行深入研究，寻找占优解的必要条 件来划分解空间，使搜索范围控制在占优解空间内，是求解n p h a r d 问题的有效 方法。 1 2 2p j s s p 算法 ( 1 ) m i p 算法。随着对m i p 研究的深入，分支割平面( b r a n c h - c u t ) 等算 法已成为求解组合优化问题的一种重要方法，为提高算法的有效性，往往需要 第1 章绪论 在分支过程中加入占优规则等启发式规则，以缩小搜索范围，提高搜索速度。 ( 2 ) 启发式算法。针对实际问题研究启发式算法，并进行逐步改进。 1 3 本文的整体框架 本文将从理论研究和现状分析入手，并针对钢铁行业生产中的实际问题进 行研究，把理论应用到实践中，本文的整体框架见图1 2 。 在第二章中，从生产调度理论，j o b s h o p 调度问题以及钢铁行业中的生产 调度三个方面进行简明综述，现状分析和理论研究。 第三章针对钢铁行业实际生产调度问题进行模型和算法上的研究。在满足 各约束条件下建立数学模型，实现其在冷加工区各工序的生产调度，使各工序 生产任务饱满、平衡，并且转换时间少。再针对数学模型进行混合整数规划算 法和启发式算法研究。 由于实际问题的规模比较大，求解要借助于一些软件，在第四章中先介绍 所用到的优化软件和编程工具，再详细说明工具的设计和结果。 在得到结果的基础上，第五章将模型和算法应用于实际的算例中，用同一 组数据进行检验和比较，得到不同算法的检验和比较结果。 第六章进行总结和展望。 图1 2 本文的整体框架 4 第2 章生产调度与实践综述 第2 章生产调度理论与实践综述 2 1 生产调度理论概述 生产调度跟在产品制造的整个时间内有效资源分配有关。每当一组通用的 资源劳力，材料以及设备必须被用来在同一段时间里制成各种不同的 产品时，就会发生调度问题。粗略地讲，调度就是按时把工作任务分配给资源 的过程。而调度的目的就在于要找到指定并编排出利用这些共用资源的次序的 方法以便适应生产约束，将生产成本降到最低。 各种实用的和理论方面的考虑已经提起了人们对新的生产调度方法的兴趣。 首当其冲的要数制造出商品的越来越具竞争性的世界市场。通过提高资源生产 率或相关操作管理方面的效率，较好的生产调度就显示出有竞争力的优越性。 竞争还推动了人们采用由下降的成本和工业计算机及机器人能力的增加所形成 的采用先进技术和资金充足的新型制造系统。最引人注目的新的制造技术，莫 过于自动化的，灵活的计算机集成制造系统( c o m p u t e r i n t e g r a t e d m a n u f a c t u r i n g s y s t e m , 缩写为c i m s ) 。现在生产调度已经成为c i m s 研究领域生产管理的核心内 容和关键技术。 早在1 9 5 4 年，j o h n s o n 对两台机床的f l o ws h o p 型调度问题进行了研究后， 便开始了对调度问题的广泛研究。由于调度问题的复杂性，导致不同的研究者 从不同的角度研究某一方面的问题，产生了许多的调度问题的类型和方法，并 随着对各类调度问题研究的深入及各种交叉学科的发展，涌现出了许多新的调 度理论与方法。在对调度问题进行研究的方法上。最初是集中在运筹学的整数 规划、仿真和简单的规则上，随着各种新的相关学科与优化技术的建立与发展， 在调度领域也出现了许多新的优化方法，比如遗传算法、模拟退火法、禁忌搜 索法等，使得调度问题的研究方法向多元化方向发展。 调度问题，根据加工系统的复杂度，可分为单机、多台并行机、f l o ws h o p 、 j o bs h o p 等。单机调度问题是所有的操作任务都在单台机器上完成，为此存在任 务的优化排队问题，对于单机调度比较有代表性的见文献【1 , 2 , 3 】；多台并行机的调 第2 章生产调度与实践综述 度问题更复杂，因而优化问题更突出，文献 4 , 5 1 研究了多台并行机的调度；f l o w s h o p 型问题假设所有作业都在同样的设备上a n ：l ：，并有一致的加工操作和加工 顺序，文献1 6 j 研究了f l o ws h o p 问题；j o bs h o p 问题是比较复杂的调度类型，并 不限制作业的操作的加工设备，并允许一个作业加工具有不同的加工路径。而 现代生产调度问题大多是j o bs h o p 类型。 生产调度方法可分为精确方法和近似方法。其中精确方法包括分支定界方 法，数学规划法等，精确方法由于要求在多项式时间内得到最优调度，适用于 问题很小的情况，对于大规模问题，往往需要相当长的时间，因此限制了精确 方法在大规模调度问题上的使用：近似方法包括优先分配规则( 目前常用的优先 分配规则有s p t 、l p t 、l w k r 、m w k r 、f i f o 、l i f o 、e d d 等) 、基于移动瓶 颈的启发式方法、领域搜索方法( 模拟退火算法、禁忌搜索算法、遗传算法等) 、 人工智能方法( 神经网络方法、混沌搜索、专家系统) 等，近似方法适用于大规模 调度问题，但是容易陷入局部最优解中。 2 2j s s p 综述 j s s p 是n t h a r d 问题，也是最难解的组合优化问题之一，不能在多项式时 间内用一个有效算法求出其最优解。当今经济日益全球化的竞争趋势和不断变 化的用户需求要求生产者要重新制定生产制造策略，如更短的产品生产周期， 更少的库存，更完善的信息系统等，而利用有限的资源满足被加工任务的各种 约束，并确定任务在相关设备上的加工顺序和时间，以保证所选择的性能指标 最优，能够潜在地提高企业的经济效益，j s s p 生产环境基本满足现在经济和用 户的需求，因此j s s p 具有很多实际应用背景。 j s s p 按照任务在加工过程中是否可中断，又可分为不可中断型( n p j s s p ) 和任务可中断型( p j s s p ) 。 2 2 1n p j s s p 现有研究 目前国内外的文献对j o b - s h o p 问题的研究主要集中在n p j s s p 上。 6 第2 章生产调度与实践综述 针对目前已有的对求解的理论方法总结归纳为以下三部分： 2 2 1 1 运筹学方法 运筹学对生产调度中的基本问题，如单桃、并行机器、f l o ws h o p ，j o bs h o p 等都进行了深入的研究，形成了许多重要的理论方法，是解决生产实际中复杂 问题的基础，总体看来对于调度的运筹学方法主要集中在整数规划：基于启发 式规则的方法；动态规划法等方面。j o b s h o p 调度问题可以用运筹学中的一些方 法如整数规划法、混合整数规划法和动态规划法来描述求解，具体包括的研究 方法有分支定界法，分支与支配方法，波浪形切面法，动态规划，整数规划和 拉格前日乘子方法。运用运筹学方法求解的已有方法主要是将调度问题简化为 数学规划模型，采用基于枚举思想的分支定界法或动态规划算法进行解决调度 最优化或近优化问题，文献【o l 等提出了不同的分支定界法。j a c k s o n ( 1 9 5 6 ) 提出 了两台机器上无作业循环情况下的最小完工时间的求解公式；l o m n i e k i c ( 1 9 6 5 ) 用分支定界法技术在j o bs h o p 中用来求解加工时间最小化的问题；a d a m s ，b a l a s 和z a w a e k ( 1 9 8 8 ) 提出著名的瓶颈转移启发式算法，c a r l i e r ( 1 9 8 2 ) 用这种算法来 求解单一机器的调度问题。运用混合整数规划对调度问题进行求解是比较普遍 的，在整数规划中，应用最多的是分支定界法和拉氏松弛法。前者是一种枚举 方法，对于较大的调度问题，要花费很大的时问，其主要存在的问题是整数约 束，为了克服这个问题，产生了拉氏松弛法，它删除了整数约束而相应地加入 代价。由于其在可行的时间里能对复杂的规划问题提供很好的次优解，并能对 解的次优性进行评估，近来成为解决复杂车间调度问题的一种重要方法。解决 j o b s h o p 问题的整数规划( 1 p ) 模型最初由b a k e r 提出，需要考虑两类约束：工件 工序的前后约束和工序的非堵塞约束。 2 2 1 2 局域搜索方法 由于j o b - s h o p 调度问题的复杂性，解空间的复杂性，该类问题的求解方法需 要运用启发式方法。求解调度问题的启发式方法是基于邻域搜索策略发展起来 7 第2 章生产调度与实践综述 “1 1 1 ，启发式并不企图在多项式时间内求得最优解，而是在计算时间和调度效 果上8 0 进行折衷。下面是三种有代表性的启发式方法： 1 模拟退火( s a ) s a 是基于m e m ec a r l o 迭代求解的一种全局概率型搜索算法，是一种串行优 化算法，其收敛性要求初温应足够高，使解空间各状态能以几乎相同的概率出 现。v a nl a a r h o o v e n 等【1 2 】提出对于j o b s h o p 调度问题，邻域函数的重要标志是相 邻关键操作工序处理顺序的改变。且必须服从在同一机器上处理的工序条件。 k o l o n k o 1 3 1 证明标准的j o b s h o p 调度的邻域具有非对称性，且由于s a 的弱收敛 性，提出了在s a 基础上结合g a 的混合启发式。文酬14 1 利用s a 以一定的概率 接受较差个体的性质，结合遗传算法而改进了选择机制，使收敛速度有所提高。 近期在调度问题研究领域的一大趋势是将不同的邻域搜索法结合形成混合启发 式。 2 禁忌搜索( t s l t s 是6 1 0 v e 一”1 提出的模拟智能过程的一种具有记忆功能的全局逐步优化算 法，对变动的调度在其可行解的所有空间中进行搜寻。通过设置禁忌表，避免 陷入局部最优或重复过去的搜索，利用中、长期的存储机制进行强化和多样化 搜索。对于j o b s h o p 调度问题，l a g u n a 等 1 6 , 1 刀提出三个基于简单移动的t s 调度策 略。 t a i l l a r d l l 8 】结合加速搜索策略防止重复计算工序的开始时间，提出一种快速 估值策略，但只对半活动调度有效。而n o w i c k i 等1 1 9 l 考虑到解的质量和计算时间， 结合t a i l l a r d t l 8 1 的t s 算法，在v a nl a a r h o o v e n 习邻域的基础上，把单个关键路径 分割为不同块，应用于严格限制的邻域中，计算效率大大提高。 3 遗传算法( 6 a ) 遗传算法是h o i l a n d 基于自然遗传进化的绝对模型提出的并行搜索机制1 2 0 1 ， g a 的5 个要素是编码、适应值函数、初始种群、遗传算子和参数设置。由于对 j o b - s h o p i 周度问题要考虑工序的前后约束和非堵塞约束，使得染色体的编码表示 8 第2 章生产调度与实践综述 非常重要。如果编码不当，会在遗传算子操作时产生不可行解，失去了交叉或 变异算子的有效性。c h e n g 等 创】把编码表示分为两类共9 种。d a v i s t 2 2 1 首先基于优 先表的阕接编码表示求解j o b s l t o p 讽度，f a l k e n a u c r 等叫哭i l 利用把工序编码为字 符串的方法。t a m a k l 2 4 1 基于非连接图的间接编码，其染色体用非连接边顺序表 的二进制串表示。b e a n 2 5 】采用随机键表示法，每个基因由两部分组成：整数部 分表示机器的分配，分数部分以非减顺序排列的( 0 ，1 ) 之间的随机数来确定每个 机器上的工序。曹承煜等【2 6 】提出结合拉氏松弛法的遗传算法，能够克服震荡并 缦小计算量。纪树新等1 2 7 l 对j o b s h o p 调度应用连锁基因编码法与遗传进化算子相 结合，显示算法的可行性。王海英等【2 8 】采用定界遗传算法与逆序调度策略，在 收敛速度上有所提高。上述启发式算法相对比较简单、计算效率高、算法灵活 多变。但启发式算法也有明显不足之处，即有可能出现所产生的解比全局最优 解差很多的情况，而且差的程度总是不够明确。 2 2 ，1 3 约束规捌方法 约束规划是以解决组合优化问题为目标的范式。通常情况下，解决组合优化 问题是通过将其描述为一个或多个约束满足问题实现的。通俗的说，一个c s p ( 约束满足问题) 可以描述为一组变量，每一变量的一组可能值，还有各个变 量之阀的一组约束。某一变量的可能值组被称为该变量的域，变量之间的某一 约束表明了变量可以取那些值组合。约束可以明确的阐述，比如数学公式，也 可以模糊阐述，这时每一约束都表达为满足这一约束的数值组。 在通过变量和约束定义问题的过程里，实践中约束规划工具的使用者拥有 一组已经界定的约束( 比如整数约束，集合约束，调度约束) ，以及相应的传播 公式。局部原理对于已经界定的约束的实际操作至关重要。因为该原理表明， 约束传播公式可以用于所有相似约束适用的情况中。这些c p ( 约束规划) 工具 为利用相应的传播公式界定了新约束提供了众多方法，这些方法随即可以完美 的应用于事先界定的约束中广泛应用于调度理论的分类是由g r a h a m 提出的， 其它学者还有l a w l c r 、l e n s t r a 、r j n n o o yk a n 。在各种技术中，有边缘找寻，指 的是一种分支定界技术和分支规划。 9 第2 章生产调度与实践综述 2 2 2p j s s p 现有研究 针对p j s s p 的研究比较少，从目前的文献资料来看，研究方法主要有约束 规划，遗传算法和启发式方法。 c l a u d el ep a p e 和p h i l i p p eb a p t i s t e 在可中断调度中有比较深入的研究。 p h i l i p p eb a p t i s t d 2 9 】研究了在可中断的情况下，最小化超期完工数量的问题，提 出了新的动态规划算法，它的时间和空间复杂度分别是o ( n 4 ) 和0 ( n 2 ) ；p h i l i p p e b a p t i s t e 笔；1 3 0 】提出了针对p j s s p 的基于约束的分支定界算法；c l a u d el ep a p e 等o 】 介绍了c l a j i 也s c h e d u l e 。一个针对可中断和不可中断调度的约束规划库； c l a u d e l e p a p e 等p 2 】介绍了约束传播算法在可中断调度中的实验性研究。 y o u n gs u m 则研究了遗传算法在同时考虑可中断和不可中断调度模型中 的应用。y o u n gs uy u n 等p 剐提出了种新的遗传算法，然后再由该算法与常规排 序规$ t j ( s p t , e d d ) 相结合形成混合遗传算法，通过实验得出混合遗传算法( e d d ) 的效果最优。y o u n gs uy u n 洋i 提出新的遗传算法结合模糊逻辑控制嚣来进行求 解。 e w af i g i e l s k a 3 5 l 提出t - - - 阶段启发方法，首先在不考虑转换成本的情况下用 列生成技术最小化完工时间，得到一个最初调度排序，然后用遗传算法对该调 度排序结果来屉小化总转换成本。e a k c o r a 等口6 j 提出了在有顺序约束的前提下把 可中断任务分配给弹性资源的方法，基于计算每个任务的惩罚指数。作为时间 函数来分配任务给资源，然后用数学规划方法最小化惩罚。 2 3 钢铁行业中的生产调度问题 在全球钢铁行业竞争日益激烈的情况下，人们开始注重钢铁企业内部生产 管理。而生产调度是生产管理的核心内容和关键技术科学地制定生产调度方 案对提高企业生产效率和生产效益有着至关重要的影响。同时当今信息技术发 展迅猛，国内外的钢铁行业逐渐实施信息系统，用先进的计划和调度系统来辅 助生产调度。国内外的学者针对钢铁企业生产调度理论、方法和应用进行多方 面的研究，针对该行业中的各种阀透从不同的角度，用不同的方法进行建模和 求解。 l o 第2 章生产调度与实践综述 2 3 1 钢铁行业生产调度问题的分类 国内外学者对生产调度问题的分类方法很多，主要有以下几种： 1 根据钢铁行业生产系统的复杂性，生产调度可以分为单机调度、并行机 调度、j o b s h o p 调度、f l o w - s h o p 调度、o p e n s h o p 调度和混合f l o w - s h o p 调度 等。此类分组方式也是基于调度问题的组织方式。在此基础上，很多学者研究 了大量的调度模型和算法，在理论研究中，将钢铁行业的调度问题抽象为 j o b - s h o p 调度问题、f l o w s h o p 调度问题和混合f l o w s h o p 调度问题比较多。 2 根据生产环境的特点，可将调度分为确定性调度和随机性调度。前者是 指参数等是己知的、确定的量；而后者的有关参数是随机的量。钢铁行业中的 调度问题大多是随机性调度。 3 根据任务或工件的特征，可将调度分为静态调度和动态调度。静态调度 指进行一次调度后，各任务或工件被确定，在以后的生产过程中不再改变；而 动态调度是指任务或工件依次进入待加工状态，不断进入加工，不断离开，同 时还要考虑作业环境中不断出现的不可预测的动态扰动。相对于静态调度而言， 动态调度更强调实时性、在线性和自适应性。而钢铁行业中的调度问题因为生 产工艺复杂，生产设备众多，还需考虑各种设备故障等情况，一般都属于动态 调度。 4 根据工件属性的特征，调度问题分为工件转移型调度和设备转移型调度。 目前大部分钢铁企业调度的工件体积、重量相对生产设备来说比较小，所以大 多属于工件转移调度类型。 钢铁行业的生产调度问题往往都是由j o b s h o p 、f l o w - s h o p 、混合f l o w - s h o p 型等基本调度类型组合而成，基于随机性的、动态性的、工件转移的。 2 3 2 钢铁行业生产调度综述 生产调度理论和方法的研究已经有5 0 多年的历史，但是经典调度理论与实 际调度问题之间还是存在着鸿沟，徐俊刚掣”】( 2 0 0 4 2 ) 指出了当前实际生产调 度需要考虑的各种因素，例举了数学规划、启发式搜索、系统仿真、人工智能、 计算智能、实时智能等生产调度方法的典型应用，并且介绍了典型生产调度系 统和工具包，总结了8 个未来研究方向，对生产调度领域的今后研究工作提出 了5 点建议。唐立新、杨自厚 3 s 1 分析阐述了钢铁企业在计算机集成制造系统下 第2 章生产调度与实践综述 的生产计划与调度问题分类。唐立新【3 9 】综述了他们在钢铁生产计划与调度的理 论与方法方面的研究成果，钱晓龙等【4 0 】研究了动态调度，将对其的研究方法分 为两类进行介绍：一类是传统方法，包括最优化方法、启发式方法和仿真方法 等；另一类是智能方法，包括专家系统、神经网络、智能搜索以及m u l t i a g e n t 等，分析了各种方法的优缺点，并指出今后的研究热点将是各种方法结合的研 究和m u l t i a g e n t ，研究应以在实际中应用的调度系统为重点；常春光等1 4 l j 则以 钢铁企业生产为背景，进一步研究其有效的动态调度方案，在描述了其特点后 在理论方面具体介绍了基于模型、智能、人机交互方法，分析了各种方法问交 叉组合的方式：在实践应用方面研究工程实现模式。提出了基于m e s 的钢铁生 产动态调度四维一体综合集成的新模式。i k c r a i 9 1 4 2 j 等对钢铁生产中的连铸自动 化提出设想，综述了在该行业中的控制技术及其典型应用，讨论了实施控制技 术的重要部分辅助技术，生产计划和调度，计算机辅助质量控制，提出了整合 铸造自动化系统和钢铁厂生产系统的重要性。唐立新等m 对集成钢铁生产的计 划调度系统和方法进行了综述，首先比较了现代集成的炼钢、连铸和熟轧工艺 ( s m c c f i r ) 和传统的冷装生产过程和生产管理问题，然后对用于s m c c h r 生产的计划调度系统和方法进行了综述，最后讨论了该领域中的进一步研究的 关键问题。 2 3 3 钢铁行韭生产调度问题模型和算法 在钢铁行业中有许多问题需要解决，从日前的文献来看，国内外学者研究 的主要问题集中在以下几个方面中，学者们从不同的角度抽象问题，用不同的 方法进行建模，用不同的算法进行求解： 3 1 蔗锕- 连铸问曩 炼钢连铸生产过程是现代钢铁企业的核心工序。转炉把从高炉炼得的铁水 进一步冶炼为钢水，在精炼炉进行精炼以保证钢水的化学成分和温度，然后在 连铸机浇注成各种尺寸外形的板坯，供给下游生产工序或用户。s a t os 等m 1 、 l a r r yb 等1 4 5 1 研究了考虑炼钢连铸生产工艺基本要求的调度模型；唐立新等脚】 分析了炼钢一连铸生产调度问题的体系结构；文f j 伟等1 4 玎利用统一建模语言( u m l ) 对炼钢连铸生产调度系统的静态结构和动态行为进行了研究；方宇炜等1 48 1 提出 了基于p e t r i 网炼钢一连铸实时调度方法；李霄峰等1 4 9 1 提出了炼钢连铸系统的动 第2 章生产调度与实践综述 态调度模型及其启发式算法；刘光航等【5 0 】以实际工程项目为背景，在满足连续 浇注约束条件下，考虑了炉次的设备指派和作业排序，建立了混合整数线性规 划模型，并提出了面向实际应用的启发式算法；郭冬芬等似l 建立了闯题的约束 满足模型，将其归结为最小化操作开工时间偏移的调度问题，在求解过程中通 过冲突检查和冲突修正算法来得到最终解。汪开忠等【5 2 】对马钢第一炼钢厂的炼 钢、精炼、连铸工序时间参数分析研究