（机械制造及其自动化专业论文）多目标多约束环境下的生产计划与作业调度方法研究.pdf

东华大学硕十学位论文 摘要 摘要 随着计算机技术和互联网技术的快速发展，全球采购市场的逐步形成，个性 化、多品种、少批量制造的比例越来越高。然而，有关统计资料表明，在多品种 小批量的机械制造过程中，9 5 时间消耗在等待、运输等非加工中，即大量在制 品占据了制造企业的大量时空，一方面设备利用率非常低下，另一方面形成了大 量的资金积压。因此，在越来越大的市场竞争压力下，企业如何充分利用有限资 源，提高产品质量、降低生产成本，并快速响应市场变得极其重要。在现代制造 系统中，生产计划与作业调度是企业生产经营与管理的核心之一，尤其是复杂、 柔性制造系统能否取得预期经济效益的关键技术之一。生产计划与作业调度的目 的在于通过对制造资源和物流的合理规划、调度与控制，提高制造资源的利用率、 缩短制造周期、减少在制品、降低库存，实现多品种、少批量的高质量、低成本、 高效率柔性生产。 然而，大多数现有生产计划与作业调度方法都对实际制造环境作了大量的简 化，即所研究的作业调度方法与系统和实际应用尚有较大距离。因此，综合考虑 企业不同制造周期的多目标( 最短的制造周期、最大的资源利用率、最小的制造成 本等) ，多约束( 交货期、柔性工艺路线、工序时间及毛坯到达时间等) 问题，研制 实用的生产计划与作业调度系统变得极为迫切和必要。 本文针对多品种小批量生产模式使作业调度规模急剧增加问题，提出了基于 主生产计划，通过生产资源平衡优化方法构造生产线和柔性生产单元，解决大规 模的柔性工艺路线选择，充分利用企业的其他信息，结合生产资源的实际生产情 况，给出有效的作业调度方案。本文试图从解决多品种小批量的柔性作业调度实 际应用性出发，根据不同类型车间，研究了对应的多目标多约束的作业调度。 本文完成的工作有如下：基于资源平衡优化的作业调度问题描述与建模。针 对不同车间类型建立作业调度的问题描述与数学模型。包括对多目标多约束作业 调度问题的描述，解决柔性大规模作业调度生产能力平衡模型的描述，多目标多 约束环境下作业调度模型的建立等；多目标多约束环境下作业调度关键算法的 研究。考虑最大完工时间函数、等待时间函数、交货期等不同的目标函数，实现 t 东华大学硕上学位论文摘要 基于工艺路线、有限生产资源等多约束的调度。在f l o ws h o p 调度研究中，使用启 发式规则与遗传算法实现资源优化与作业调度的结合；在j o bs h o p 调度研究中， 运用遗传算法实现多目标柔性工艺路线的作业调度。原型系统的实现。运用标 准测试案例与工程实际案例对原型系统进行测试，体现了生产资源平衡优化方法 在解决大规模作业调度中的作用。 关键词：生产计划，作业调度，启发式规则，遗传算法 东华大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t e ra n di n t e r a c tt e c h n o l o g y , 勰w e l l 蠲 g l o b a lp r o c u r e m e n tt a k i n gs h a p e l y , m a n u f a c t u r i n gw i t hs m a l lb a t c ha n dv a r i o u st y p e s i sb e i n go nt h er i s e h o w e v e r , s t a t i s t i c ss h o wt h a tu pt o9 5 t i m eh a sb e e ns p e n to n d e l i v e r ya n dt r a n s p o r t a t i o n ，w h i c hm e a r l st h a tag r e a td e a lo fp r o d u c t si np r o c e s s s u c h c i r c u m s t a n c ec a u s e st w op r o b l e m s f i r s t l y , i to c c u p i e sm a s s i v et i m ea n ds p a c eo f m a n u f a c t u r i n ge n t e r p r i s e s 。s e c o n d l y , t h ec a s hd o e s n tg oa r o u n de f f i c i e n t l y t h e r e f o r e , i ti se x t r e m e l ye s s e n t i a lf o re n t e r p r i s e st op a yf u l la t t e n t i o no nh o wt om a k eg o o db s o o fl i m i t e dr e s o u r c e s ，t oi m p r o v ep r o d u c tq u a l i t y , t or e d u c ec o s ta n dm a k ei m m e d i a t e r e s p o n s et o m a r k e tr e q u i r e m e n t su n d e rp r e s s u r eo ff i e r c e l ym a r k e tc o m p e t i t i o n p r o d u c t i o np l a n n i n ga n ds c h e d u l i n gi st h ec o r eo fp r o d u c t i o na n dm a r k e t i n g m a n a g e m e n ta sw e l la st h ek e yt e c h n o l o g yw h i c hd e t e r m i n e sa n t i c i p a t e dp r o f i t si n c o m p l i c a t e df l e x i b l em a n u f a c t u r i n gs y s t e m t h ep u r p o s eo fi ti st oi n c r e a s e t h e r e s o u r c eu t i l i z a t i o nr a t e ，t os h o r t e nm a n u f a c t u r i n gp e r i o d s ，t or e d u c es t a c ki n p r o d u c i n ga n dt od e c l i n ei n v e n t o r yb yr e a s o n a b l es c h e d u l i n ga n dc o n t r o lw h i c hl e a d s t ob e t t e rq u a l i t y , l o w e rc o s ta n dh i g h e re f f i c i e n c y h o w e v e r , m o s tm e t h o d so fp r o d u c t i o np l a n n i n ga n ds c h e d u l i n gh a v es i m p l i f i e d r e a l t i m em a n u f a c t u r i n gs e t t i n g s ，w h i c hl e a d sag a pb e t w e e np r o t o t y p es y s t e ma n di t s a p p l i c a t i o n h e n c e , i ti su r g e n ta n dn e c e s s a r yt od e v e l o pap r o d u c t i o np l a n n i n ga n d s c h e d u l i n gs y s t e mt h a tc o u l db eu s e di nr e a ll i f ew i t l lac o m p r e h e n s i v et h r o u g ho f m u l t i p l eo b j e c t i v e s t h et h e s i sa i m st od e v e l o pa ne f f e c t i v ep r o d u c t i o ns c h e d u l i n gs o l u t i o ni n c o m b i n a t i o no fr e a l l i f es i t u a t i o n ，i nf o r mo fs t r u c t u r i n gp r o d u c t i o nl i v ea n df l e x i b l e p r o d u c t i o nu n i tb ym e a n so fb a l a n c i n ga n do p t i m i z i n gp r o d u c t i o nr e s o u r c e sa c c o r d i n g t op r o d u c t i o np l a n n i n g t h em a i nt a s k so ft h et h e s i sa r e 勰f o l l o w s ： 东华大学硕士学位论文 a b s t r a c t s t u d y i n ga n df o r m a l i z i n gt h em o d e l so ft h er e s o u r c eo p t i m i z a t i o nb a l a n c e , t w o d i f f e r e n tt y p e so fw o r k s h o p sa r ed e s c r i b e d , i n c l u d i n gj o bs h o ps c h e d u l i n ga n df l o w s h o ps c h e d u l i n g i no r d e rt og e to p t i m i z a t i o n , t h i st h e s i sh a su s e ds o m ea l g o r i t h m s ， c o n s i d e r i n gm u l t i - p r o d u c t i o nc a p a c i t ym o d e li nl a r g e s c a l ef l e x i b l es c h e d u l i n g i nt h ef l o ws h o ps t u d y , c o m b i n i n gh e u r i s t i c sr u l e sa n dg a ，w h i l ei nt h ej o bs h o p s t u d y , u s i n gg a t os o l v et h em u l t i - p r o c e s ss c h e d u l i n gp r o b l e m t h ea u t h o rd e v e l o p e d p r o t o t y p es y s t e mu s i n gt h ec o m p u t e rl a n g u a g ec 撑a n db a s e do n n e tp l a t f o r m a tl a s t , t h i st h e s i su s e sc a s es t u d ya n d t w oe x a m p l e st ot e s tt h ea l g o r i t h m sa n dt h es o f t w a r e s y s t e m t h er e s u l t sh a v ed e m o n s t r a t e dt h e v a l i d a t i o no fo p t i m i z a t i o nm e t h o do f p r o d u c t i o nr e s o u r c eb a l a n c ea n ds h o w nt h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d st o s o l v et h el a r g e - s c a l ep r o b l e m s k e yw o r d s ：p r o d u c t i o np l a n n i n g ，s c h e d u l i n g , h e u r i s t i c sr u l e s ，g a i i 东华大学硕上学位论文 多目标多约束环境下的生产计划与作业调度方法研究 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导 下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写。我对所写的内容负 责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名：杵极 日期：口罗年；月日 东华大学硕士学位论文多目标多约束环境下的生产计划与作业调度方法研究 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部 门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密口。 学位论文作者签名：许 日期：为胡年3 月日 荔 指导教师签名：毒孟乞 日期：年月 日 东华大学硕上学位论文第l 章绪论 i i 引言 第1 章绪论 生产计划与作业调度是企业生产经营中的核心任务，是企业赢得效益和发展 的关键。近2 0 年来，国际生产工程学会( c i r p ) 曾总结了4 0 种先进的制造模式，无 论哪一种制造模式都是以优化的生产计划与作业调度为基础1 。 据统计，多品种小批量生产的9 5 9 6 的时间消耗在非切削过程中嘲。因此，开展 实用的、面向制造资源的生产计划与作业调度( p r o d u c t i o np l a n n i n ga n ds c h e d u l i n g p p s ) 研究与实践变得尤为重要。随着资源因素重要性的提升，很多学者开 始研究面向生产资源的作业调度，如曾相戈、韩伯棠日1 研究了一种求解带夹具或 模具资源约束的并行机器多目标调度问题的遗传算法；鞠全勇，朱剑英等h 1 研究 了机床设备、操作工人双资源多工艺路线作业车间模糊调度问题等等。但多资源 约束的作业调度，如果不能解决资源之间的平衡问题，同样影响作业调度的实际 应用。 多品种小批量的生产模式使生产计划与作业调度问题变得极为复杂。该模式 下企业的产品种类多、批量小、生产重复度低、工艺过程经常变更、生产计划的 稳定性较差1 ，这就迫切需要一个能满足实际要求的作业调度系统。在多品种小 批量生产的车间生产作业调度问题的研究中，文献 6 介绍了转移瓶颈方法( t h e s h i f t i n gb o t t l e n e c kp r o c e d u r e ) 考虑了运输时间、多资源约束等实际因素在单 件生产车间的应用，文献 8 研究了多品种小批量生产环境下的柔性调度，但仍 然存在条件比较苛刻、计算量大等缺点，不适合实际的生产应用。 现有的e r p 、m r p - i i 等企业信息系统生产流程模块大多以人工干预为主，不能 很好地投入车间生产应用。近年来，我国已花费了数十亿美元引进e r p 、m r p i i 等软件，但都因为没有车间级的基础生产技术( 特别是优化的调度技术) 的支持， 在企业内部形成了一个无法协调、贯通的“信息孤岛，而没能得到有效应用。 就目前e r p 系统的研究来看，虽然有许多用于能力平衡的方案，如通过增加工时、 添置设备而提高能力，或寻找外协、推迟工期而减少负荷等等。但是，大多数e r p 系统缺少对这些调整方案的支持设施，使用户面对复杂的企业资源，对调整方案 的选择及调整幅度的确定无据可依，在很大程度上影响了e r p 对企业管理能力的 东华大学硕士学位论文第1 覃绪论 发挥扫3 。 有效调度方优化技术的研究和应用，己经成为先进制造技术实践的基础和关 键，所以对它的研究与应用具有重要的理论和使用价值。调度的目的是针对一项 可分解的工作( 如产品生产) ，探讨在一定的约束条件下( 如工艺约束) ，为每个加 工对象确定加工路径、时间、机器和操作等，以获得产品制造时间或成本的最优 化。任何生产企业如果能充分安排好作业调度，对于提高生产系统的最优性、提 高经济效益，有着极大的作用。车间作业调度作为生产管理的最为困难的问题， 而且业界证明车间作业调度问题属于n p 难题，随着机器数和工件数的增加，调度 方案呈指数增长n0 1 。而实际应用中的周期调度问题远比案例库的规模大并且复 杂，因此，作业调度在解决企业的实际运行问题中，存在很大的障碍。作业调度理 论和方法的研究虽然已经有5 0 多年的历史，但是从理论研究到实际应用之间仍 然存在着很大的距离，经典调度理论在实际应用中的效果并不理想。企业软件应 用的现状还是停留在案例库调度，或者简化调度模型后的情况下实现。对车间作 业调度问题的研究，吸引了国内外许多学者和实际车间作业调度人员的关注。 车间作业调度问题的研究不仅具有重要的理论意义，而且还有相当大的实 用价值删。这是由于：一方面，车间作业调度问题的研究不仅可以推动相关 算法的研究，如模拟退火算法，遗传算法，神经网络，人工智能等，而且还能 在此基础上提出新的算法，这为其他领域类似问题的解决提供了条件和手段： 另一方面，车间作业调度问题的解决本身具有实际意义，一个好的车间作业调 度方案不仅可以降低生产成本，而且可以提高企业产品的准时交货能力，从而 增强企业的竞争力。研究表明调度方案随着机器数和工件数的增加，呈指数增 长。因此，如何在不影响调度优化结果的前提下减少调度方案规模，解决生产 实际中的多品种小批量调度问题是当前迫切要解决的难题。 1 2 生产计划与作业调度问题的研究状况综述 1 2 1 生产计划与作业调度问题的概述 从上个世纪初开始，作业调度问题就被看作是一个很独特的问题。在形成调 度和计划部门以前，曾有一段时间，许多工厂不知道零件的加工从什么时候开始， 2 东华大学硕士学位论文第1 章绪论 不知道零件正在什么地方被加工，也不知道零件在厂房中是如何运作的，更不知 道它将在什么时候结束。当时，工厂中的混乱状况如h e m e r s o n n u 所描述： “世界上绝大多数的工业工厂所处的文明阶段，就如同草原上的老式运货 车和大篷车：它们准备好了就出发，没有人知道它们何时到达目的地，也没有人 知道它们在哪里，更没有人知道它们选择了哪条路。” 之所以会发生这些现象，主要是因为生产资源受到了制约和没有办法优化利 用有效资源导致的。设想，有n 个不同的零件，就至少有n 条不同的工艺加工路线， 如果有足够多的机床设备和其他生产资源分配给每条工艺加工路线，即每一条工 序独立占用一台机床设备和相应的生产资源，那么一切都会井然有序，也就不存 在调度问题。但是，对于企业主来说，这样必定会造成资源浪费和制造成本的增 加：于是出现了零件和相应的工序数量多于机床设备和其他生产资源的情况，调 度问题也就自然而然的出现了。 生产计划与作业调度问题就是在时间合理配置系统的有限资源，以满足特 定目标的要求。典型的作业调度问题包括一个待加工零件集合，每个零件包括 一个工序集合，各工序需要占用机床等生产资源，并且要按照一定的工艺路线 进行加工不同机床加工的工序可以不同调度的目的就是为零件合理地分配机床 等资源，并合理地安排加工时间，在满足约束条件的同时，使一些指标最优。 作业调度问题主要有以下几个特点1 2 】： ( 1 ) 复杂性：车间中工件、机器和搬运系统之间相互影响、相互作用。每个 工件又要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂。调 度问题是在等式或不等式约束下求指标的优化，在计算量上往往是n p 完全问 题，随着问题规模的增大，其计算量急剧增加，使得些常规的方法无能为力， 对于这一点己经证明。 ( 2 ) 高动态随机性：制造系统得加工环境是不断变化的，在运行过程中会遇 到多种随机干扰，故作业调度过程是一个动态的随机过程。 ( 3 ) 多目标性：实际的作业调度问题是多目标的，并且这些目标之间往往会 发生冲突 6 1 。 ( 4 ) 多约束性：作业调度受到多种加工资源的制约如制造设备( 机床、相关 工具与设备) 、操作人员、原材料( 半成品) 、运输小车、刀具以及其它辅助生产 3 东华大学硕士学位论文第1 章绪论 工具等。 根据研究的侧重点不同可将作业调度问题分为以下几类： 1 基于资源约束种数和数量的划分 ( 1 ) 单资源作业调度( s i n g l er e s o u r c ec o n s t r a i n e d ) ：考虑一种资源制约 生产能力。在绝大多数的相关科技文献中m 射，大多只考虑车床的种类及数量。 ( 2 ) 双资源作业调度( d u a lr e s o u r c ec o n s t r a i n e d ) ：同时有两种资源制约 着车间的生产能力n 删。机床设备往往是制约资源之一，车间有时会缺乏有经验 或一技之长的工人，也有可能某种类型的刀具数量有限，因此这两种资源可以是 机床设备和工人或刀具h 1 。这种情况表现形式之一，就是工人数量少于机床设备 的数量。车间中也常常会发生一些辅助资源有限的情况，如一个车间只有一辆或 两辆自动物料运输车( a u t o m a t e dg u i d e dv e h i c l e ，a g v ) ，然而需要同时传送的 零件数量可能较多，在这种情况下，自动物料运送车也会成为制约车间提高生产 能力的一个重要因素。同理，奇缺的刀具、夹具以及运送零件的叉车、吊车和货 盘等都可能成为第二个制约资源。 ( 3 ) 多资源作业调度( m u l t i p l er e s o u r c ec o n s t r a i n e d ) ：同时有两种以上 的生产所需资源制约着车间的生产能力n h 耵。这些资源包括员工、机床设备、机 器人、物料运送系统和辅助资源，如货盘、夹具和刀具等。单资源作业调度是双 资源作业调度的特例，双资源作业调度又是多资源作业调度的特例。所以多资源 作业调度问题是最复杂的一种。 2 基于工艺流程及设备布局的分类 ( 1 ) 流水作业调度( f l o ws h o p ) ：在这种车间中，每个零件都有相同的加工 路径。这样，机床设备的布局如同流水线一样，零件一次从流水线的一端进入， 最后从另一端流出。 ( 2 ) 非流水作业调度( j o bs h o p ) ：在这种车间中，机床设备的布局可以是任 意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意 的。这是一种最一般的作业调度形式。 ( 3 ) 开放作业调度( o p e ns h o p ) ：每个零件的工序之间的加工顺序是任意的。 零件的加工可以从任何一道工序开始，在任何一道工序结束。 ( 4 ) 单作业调度( s i n g l es h o p ) ：在这种车间中，每个零件只能有一道工序。 4 东华大学硕十学位论文第1 章绪论 3 考虑干扰与否的分类 ( 1 ) 静态作业调度( s t a t i cs c h e d u li n g ) ：所有的零件在开始调度时刻已经 准备就绪。车间的调度不考虑零件在加工过程中出现的意外情况，如机床突然损 坏、零件的交货期提前、有更紧迫的零件要求被加工等等。 ( 2 ) 动态作业调度( d y n a m i cs c h e d u l i n g ) ：车间的调度要求考虑零件在加工 过程中出现的各种意外情况。这种调度方式要求调度能随时相应车间能力的变 化，在有突发事件出现后，能立即根据当时的车间加工能力，对待加工的零件重 新展开调度，以确保在任何时候，都能保持车间的加工性能指标处于最优或次优 状态n 钔。 1 2 2 支持车间作业调度的方法研究 一般的调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度 问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性进 行分判1 7 1 。由于实际中生产环境是千差万别的，那么一个调度算法就应该根据 其是否能适合对应的生产环境的重要特征进行评估。在对调度问题进行研究的 方法上，最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度结 果不理想就是难以解决复杂的问题。 随着各种新的相关学科与优化技术的建立与发展，在调度领域也出现了许 多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁忌搜索法等，使 得调度问题的研究方法向多元化方向发展n 蝴1 。经过5 0 多年的发展，作业调度 问题出现了多种研究方法，总结如下： ( 1 ) 基于启发式规则的方法7 由于启发式规则计算复杂度低、易于实现，故在生产中得到了广泛的应用。 但启发式规则一般不具备全局优化的特点嘲。常用的启发式规则可分为简单规 则、复合规则、启发式规则三类。y i m 、l e e 洲使用p e t r i 网络和启发式规则用 于求解柔性制造系统多目标调度问题。 ( 2 ) 分枝定界法 因为分枝定界法可为部分路径计算很强的下界，所以它是求解调度问题比较有 效的方法。文献 2 5 提出了使用分枝定界算法解决越库物流调度问题的精确求 解，并表明了分枝定界算法可以有效求解多达4 0 个货物品种的准时制配送问题： 5 东华大学硕十学位论文 第1 章绪论 但是对于较大规模的调度问题，分枝定界法需要较多的时间。 ( 3 ) 拉格郎日松弛算法 拉式松弛算法能为复杂的规划问题提供好的次优解，并对解的次优性进行定 量评估，所以成为解决调度问题的一种重要方法。文献 2 6 将拉格朗日松弛法应 用于电力系统优化调度，将系统中部分约束条件用拉格朗日乘子加权，放入目标 函数中考虑，可以将复杂的原问题拆分成各个机组的子问题，并基于一种两层结 构求解，大大降低了计算的复杂度。但与分枝定界法相比，拉式算法更耗时 2 刀。 ( 4 ) 动态规划 动态规划是求解小规模调度问题的有效算法，但它对组合的需要随问题规模 的扩大呈指数增长，以至不能求解大规模调度问题。文献 2 8 通过求解动态规划 模型，获得电网建设的最优投资规模和投资时机。 ( 5 ) 多智能体方法 由于单的专家系统处理问题的能力有限，不少学者提出多智能体方法来解决 调度问题。文献 3 2 用多智能体结构的分布式决策方法对f m s 进行了动态研究。 ( 6 ) 人工神经网络 h o p f i e l d 申经网络模型的出现为解决调度问题开辟了一条新途径，但由于涉 及的变量太多，计算效率低，很难解决实际调度问题伽1 。 ( 7 ) 模拟退火 模拟退火将组合优化问题与统计力学的热平衡问题类比，通过模拟退火过 程。可找到全局最优解。文献 3 3 用模拟退火方法解决了流水车间的排序问题。 但它的收敛速度慢，很难用于实时动态调度环境。 ( 8 ) 禁忌搜索方法 禁忌搜索是由6 1 0 v e r 提出的用于解决组合优化问题的一种高级启发式方法。 t a i l a r d 提出了解决流水作业调度问题的禁忌搜索算法 3 4 - 3 6 。由于禁忌搜索的应 用需要较多的技巧，故在作业调度中的应用较少。 ( 9 ) 仿真调度方法 仿真模型可以描述和定量评估复杂的制造系统，为实际调度采用合适的调度 算法提供依据。文献 3 9 针对半导体制造行业，提出了一种仿真调度方法来辅助 调度员进行生产作业计划的编制，但应用仿真进行作业调度的费用高，仿真的准 6 东华大学硕士学位论文第1 章绪论 确性受程序员判断能力和技能的限制，并且很难从特殊的试验中提炼出一般规 律。 ( 1 0 ) 遗传算法 遗传算法成为近年来解决作业调度问题的最主要方法。曾相戈，韩伯棠1 运 用遗传算法解决了一种求解带资源约束的并行机器多目标调度问题。与其它方 法相比，遗传算法的优越性主要表现在：搜索过程中不易陷入局部最优，能以 极大的概率找到全局最优解：具有并行性，非常适合于大规模并行分布处理；易 于与别的技术( 如神经网络、启发式规则等) 相结合，形成性能更优的算法，但 遗传算法的搜索效率低、易过早收敛【删。 1 2 3 实用生产计划与作业调度亟待解决的问题 近年来，车间作业调度问题的研究向更实用的方向发展，主要表现在以下面 几个方面“： ( 1 ) 面向多目标多约束的调度 多目标调度问题引起了越来越多学者的关注。主要研究方法包括以下三种： 采用先验偏好信息的方法，即在求解问题之前，获取决策者的偏好信息。 譬如，c a v a l i e r i 和g a i a r d e l l i t 4 3 】先通过调查，得到了综合目标与生产周期和平 均延误时间之间的函数关系，然后按综合目标搜索最优调度。d a g l i 和s c h i e r h o l t 【删用神经网络把多个目标映射成一个综合指标。由于调度问题非常复杂，取得 准确的“先验偏好信息是很难的，所以得到的结果往往不能反映决策者的真正 偏好。 采用后验偏好信息的方法，即直接根据问题的性质和结构求出部分以至 全部非劣解，再由决策者选择一个最满意解。基于这种思想，p o n n a m b a l a m 等【4 5 】 用该方法研究了作业调度问题，证明了该算法的有效性。但当非劣解数目较多 时，如何从中选择最满意解仍然是个有待决策的问题。 逐步取得偏好信息的方法。在决策过程中，决策者通过与辅助决策系统 对话，来加深自己的认识，辅助决策系统则根据决策者新的认识重新搜索解空 间，对话和搜索过程不断进行，直到找到最优解。文献 4 0 采用了这种方法。 这种方法更符合车间的实际情况。当然，方法的性能取决于决策者提供局部偏 好信息的准确性，不能保证在有限对话次数内求得满意解。 7 东华大学硕十学位论文第l 章绪论 ( 2 ) 滚动式生产计划与充分利用制造资源动态调度 作业调度过程是一个动态过程，车间的生产能力不仅会受到机床的制约，还 会受到工人和辅助工具的制约。文献 4 3 研究了动态调度问题。n e l s o n 嘞1 提出了 滚动调度策略，研究了零件周期性到达的调度问题。s a b u n c u o g l u 眵研究了再调 度周期对调度目标的影响，提出了可变再调度周期的方法。y a m a m o t o 提出了事件 驱动再调度策略，可以在机床发生故障时生成完整的调度。h o l t h a u s 脚1 研究了机 床故障发生的频率对调度性能的影响。上述研究都认为动态调度方法得到的结果 要优于静态调度得到的结果。由于周期再调度策略不能及时响应突发事件，而事 件驱动再调度策略对未来事件缺乏预见性，c h u r c h 和u z s o y 瞄3 1 提出了周期和事件 驱动的混合策略，即当有突发事件发生时立即进行调度，其它时间每隔一个固定 周期进行再调度，研究表明这种调度策略要优于前两种策略。 ( 3 ) 信息集成与共享环境下作业调度 工艺路线规划与作业调度是生产车间的两个关键任务。所谓路径规划就是根据 指定的目标，找出最合适的加工工序和加工路线：而作业调度则是根据给定的工 艺路线为工件在时间上分配加工资源【5 4 ，5 5 1 。在以前的大多数研究中，工艺路线的 优化与作业调度的优化是分开进行的，这导致了加工系统生产效率低，缺乏灵活 性。因此，有些学者【槔5 7 】提出了把工艺路线规划与作业调度集成在一起的工作方 法，即为工件保留尽可能多的工艺路线，调度时根据车间的动态情况来选择一条 最佳的路线来加工，通过调查认为这种方法能使生产周期、机床设备利用率等指 标得到重大改善，这种方法能提高车间的生产能力嘲1 。 ( 4 ) 以综合利益为目标的调度 在大多数文献中，采用生产周期、平均流动时间等时间指标来评价调度方案。 尽管这些指标在一定程度上反映了调度方案的优劣，但它们都没有涉及到管理人 员最关心的问题，例如零件的收益、总生产成本、在线库存费用、工件拖期损失 等。而作业调度优化的目的，就是选择一个能给生产车间带来最大经济利益的调 度方案。因此，有些学者【i l 】采用经济指标研究调度问题，其中调度净现值指标 得到了较为广泛的应用，文献 6 0 研究了在采用滚动窗口调度策略的动态调度 中，以调度净现值为评价指标时，各种启发式规则的性能。文献 6 1 表明最近发 展起来的s p tc r 规则得到的调度结果优于其它的启发式规则，文献 6 2 表明s p t 8 东华大学硕上学位论文第1 章绪论 c r 规则的鲁棒性要优于其它的启发式规则。 ( 5 ) 满足j i t 生产制造的调度 随着j i t 的成功应用，人们越来越注重j i t 作业调度问题。r o a c h 研究了装配 线上的j i t 调度问题，提出了模拟退火与遗传算法相结合的调度算法。陈伟达【6 9 】 建立了一个j i t 作业调度模型，提出了模拟退火方法与启发式式规则相结合的调 度算法。李霄锋【7 0 】采用反向仿真的方法研究7 j i t 作业调度问题。陈志龙【7 1 1 对最 近j i t 调度的研究情况进行了总结，认为j i t 调度的研究模型过于简单，应向更实 用的方向发展。 ( 6 ) 基于成组技术的调度 成组技术的就是根据作业、机床之间的相似性将它们各自分组，利用组内的 相似性来提高生产率。文献 7 1 中提出一种分解策略，先将作业进行分批，然后 再通过随机组合每批作业的子调度来构成整体调度。 ( 7 ) 人机交互调度 人机协同的交互策略为解决调度问题提供了一个新的手段。文献 7 2 提出了 一种图形化动态调整炼钢连铸计划的人机交互调度方法，可以极大地提高计划编 制的效率，并保证计划的规范性。 1 2 4 作业调度研究的发展趋势及存在的问题 面对越来越多的多品种小批量生产，作业调度面临的大部分问题都具有相 当复杂性，虽然对作业调度的研究已有几十年历史，但至今尚未形成一套系统 的方法和理论，理论研究与实际应用之间还存在着很大的差距。实际应用中的 调度方法能够响应系统的动态变化，但不能保证得到好的调度一些理论上的最 优调度方法能够提供最优调度。由于实际调度方案计算复杂性大，很多调度停 留在对案例库的研究上，并且忽略了很多实际因素，离应用还有较大的差距。 在实际作业调度中，车间计划与作业调度往往是分层进行的，但这可能造 成计划在实际调度中的不可行问题，如何将计划与调度结合考虑，以求总体的 优化也是需要进一步研究的。另外，还有很多有待进一步研究的问题，比如实 际作业调度的多目标性等。调度理论、方法与应用的研究是一项非常艰巨的工 作，目前人们还在进行各种各样的探索性研究工作。 针对作业调度系统的日益复杂性，目前作业调度问题的研究形成了下列一 9 东华大学硕十学位论文第l 章绪论 些策略和研究趋势【7 3 1 。 ( 1 ) 并行或分布策略：适合不同车间控制结构与高度问题复杂性的实际需 要，不少学者提出并行或分布策略来解决调度问题。 ( 2 ) 分解与成组策略：利用分解生产计划或成组技术( g r o u pt e c h n o l o g y , 简 称g t ) 的调度策略可以大大降低问题的复杂性和规模，求得调度问题的较优解， 同时优化系统的一些性能指标。近年来或独立制造岛的应用实践便是一个明显 的例证。 ( 3 ) 人机协同策略：调度问题的性质、现有研究方法的缺陷以及人类独特 的思维能力决定了人机协同策略的生命力。大量的研究成果表明人机协同交互 的策略可以减少系统的搜索空间，可在有限的时间、背景知识条件下解决困难 的问题。 ( 4 ) 实时或动态重调度策略：车间制造过程的随时性、不确定性需要不断 地进行重调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策 略有周期调度、连续调度、事件驱动调度、周期与事件驱动混合调度、周期与 连续调度混合的策略等。 ( 5 ) 生产计划与调度集成策略：生产计划与调度的集成研究具有全局优化 的特征，也符合先进制造模式的思想，同时提高了生产系统的柔性。 ( 6 ) 多目标权衡决策：实际调度问题是多目标的，且这些目标往往相互冲 突，如何对调度系统的不同目标进行权衡分析，实现多目标调度是作业调度问 题的一个值得研究的方向。 ( 7 ) 异地作业调度策略：作为敏捷制造( a g i l em a n u f a c t u r i n g ，简称a m ) 模式 的关键技术之一，异地作业调度己成为近期的研究热点。国家8 6 3 c i m s 专题 也已把此项研究列入重点研究领域予以支持。 总之，对作业调度领域这一具有难特性的研究，随着应用数学理论的进一 步发展，必然朝着集成化、柔性化、多目标化、动态实用化、高度次优化方向 深入进行。 1 3 课题的研究目标与研究内容 随着全球市场的形成和人们对个性化的需求，多品种小批量生产已占据越来 1 0 东华大学硕上学位论文第1 章绪论 越多的比例。更多的企业采用柔性工艺路线，从而提高资源的利用率，降低产品 的生产成本。但在大规模生产过程中，柔性工艺路线给调度人员带来了更多的调 度方案，同时也增加了调度的难度。如何解决大规模的柔性工艺路线选择? 如何 根据企业在不同生产周期的订单任务、目标要求和制造资源等实际情况，给出有 效的生产计划与作业调度方案? 本文研究是在这一现实背景下展开的，试图从解 决多品种小批量的柔性作业调度实际应用性出发，根据不同类型车间，研究了对 应的多目标多约束的生产计划与作业调度。运用复杂问题分块细化思想，将大规 模的作业调度问题按目标选择的不同细分为几个较小规模的调度问题，降低因为 柔性多工艺方案而导致的调度爆炸现象，解决大规模的柔性作业调度问题的实际 应用性。 1 3 1 研究目标 从面向多品种小批量大规模的车间作业调度出发，研究和探索面向不同车间 类型，基于资源平衡优化多目标多约束的作业调度系统，力图充分利用不同制造 环境下的各种生产资源。实现作业调度周期任务的均衡分配；针对f l o ws h o p 车 间，运用启发式规则实现柔性生产线能力平衡，完成不同生产线上工位负荷的均 衡分配；完成柔性工艺路线车间生产资源优化。实现多目标多约束作业调度，将 生产任务下放到具体设备、具体工人并确定相应的加工设备与加工时间，以甘特 图与生产清单下放至生产车间；提升企业的柔性制造能力与综合竞争力。 1 3 2 课题研究内容 本课题的主要研究内容有：实用生产计划与作业调度系统的需求分析和 建模；多目标多约束生产计划与作业调度问题的策略研究；生产计划与 作业调度系统的关键算法研究；实用生产计划与作业调度系统相关模块的研 匍i 。 l l 东华大学硕士学位论文第l 章绪论 1 4 论文的章节安排 图1 - 1 章节安排 第一章：绪论。介绍了生产计划与作业调度研究背景与意义，以及生产计划 与作业调度问题的国内外研究现状；并对本课题的研究内容与目标等作了阐 述。 第二章：生产计划与作业调度问题的描述与建模。对生产计划与作业调度问 题进行描述与数学建模，并阐述了整个系统的功能模型、数据流模型等。 第三章：多目标多约束环境下生产计划与作业调度关键算法的研究与实现。 研究了生产线能力平衡启发式规则与柔性生产单元资源优化的遗传算法，应 用遗传算法实现多目标的作业调度。 第四章：柔性f l o ws h o p 生产能力平衡与作业调度系统的研制。实现系统的周 期任务规划模块、生产线能力平衡模块与多目标多约束作业调度模块三个核 心模块的研制，并应用标准测试案例与工程实际案例进行了测试。 第五章：大规模j o bs h o p 生产资源平衡优化与作业调度系统的研制。基于柔 性工艺路线，实现生产单元的资源平衡优化与作业调度，应用案例库中的例 1 2 东华大学硕士学位论文第1 章绪论 子进行了测试，表明应用柔性生产单元的资源平衡优化方法细化大规模作业 调度问题。 第六章：总结与展望。总结了本文的主要工作，指出了进一步研究的课题。 东华大学硕十学位论文第2 章生产计划与作业调度问题的描述与建模 第2 章生产计划与作业调度问题描述与建模 2 1 问题提出 生产计划与作业调度问题就是在时间上合理配置系统的有限资源，以满足特定 目标要求。典型的作业调度问题包括一个待加工零件集合，每个零件包括一个工序 集合，各工序需要占用机床等生产资源，并且要按照一定的工艺路线进行加工，不 同机床加工的工序可以按不同调度的目的为零件合理地分配机床等资源，并合理地 安排加工时间，在满足约束条件的同时，使一些指标最优【_ 7 4 1 。为了全面考虑生产资 源的合理利用情况，作业调度系统需要和e r p 系统、c a p p 系统、订单管理系统、 产品结构b o m 等基本信息集成。与c a p p 集成的同时，加上实际作业调度中的产 品规模远大于案例库中的实例，随着生产过程中机器数和工件数的增加，调度方案 呈指数增长，严重影响调度效率。而且在实际生产中，产品趋于多品种小批量，每 种产品数量较少，品种繁多，此时的作业调度问题就成为大规模的调度问题。为了 将大规模问题细化，克服作业调度的指数效率问题，提出生产计划与作业调度模块 的有机结合。在生产计划中设计周期任务均衡模块与生产能力平衡模块，作业调度 模块根据基于能平衡的生产计划( 具体零部件、车间生产线或生产单元的生产计划) ， 也即为原来企业级主生产计划和车间作业调度之间的一种基于车间级制造资源能 力平衡的生产计划。其目的在于根据主生产计划进一步确定车间生产线、生产单元 等的生产任务