（计算机应用技术专业论文）非紧密衔接工序车间作业调度方法的研究与设计.pdf

哈尔滨理工大学工学硕十学位论文 非紧密衔接工序车间调度方法的研究与设计 摘要 随着高新技术特别是信息技术的迅速发展、客户需求的快速变化及经济 的全球化，企业对加强技术与管理的改进与创新、提高企业的竞争力，提出 了迫切的需求。而生产与运作管理的核心是生产车间调度问题能否高效地获 得优化解，因此，研究生产车间调度问题具有很大的理论意义和现实价值。 论文首先详细介绍了生产车间调度问题的目标、类型及研究现状，并就 该类问题的数学模型与相关算法，如启发式方法、进化算法、邻域搜索法等 进行了探讨，并指出了其存在的不足。然后对当前车间调度研究在现实中的 存在的问题进行了总结并提出非紧密衔接工序调度问题，最后详细阐述了对 于非紧密衔接工序调度问题的解决方法和算法设计方面的研究情况。 针对大多数研究忽视工序间延迟约束和装配约束下车间调度问题的情 况，提出一类非紧密衔接工序调度问题。首先说明了研究解决该类问题的必 要性，构建了它的数学模型，提出标准工序、延迟工序和扩展加工工艺树概 念；然后设计了一种由非紧密衔接工序调度模型转换为紧密衔接工序调度模 型的调度策略，并分析了模型转换后对相应调度算法复杂度的影响：最后用 实例进行了模拟计算，验证了调度策略的可行性和有效性。 在对非紧密衔接工序调度问题进一步研究的基础上，通过对拟关键路径 和最佳适应调度算法进一步完善，设计了一种通过优先调度延迟工序，对标 准工序分批采用拟关键路径法和最佳适应调度法，同时考虑关键设备上标准 工序尽量紧凑的非紧密衔接工序的动态调度算法。并通过实例验证，表明了 所提出的调度算法不仅能够较好地解决更具实际意义的动态非紧密衔接工序 调度问题，而且能够扩展解决动态紧密衔接工序调度问题。 最后，对真实企业生产加工数据运用经典车间调度算法和非紧密衔接工 序车间调度算法进行调度，通过对比分析，进一步验证了非紧密衔接工序调 度策略的可行性与非紧密衔接工序调度算法的优越性。 关键词车间调度；非紧密衔接工序；延迟工序；扩展加工工艺树；拟关键 路径法 哈尔滨理工大学丁学硕i j 学位论文 r e s e a r c ha n dd e s i g no fj o b - - s h o ps c h e d u l i n g m e t h o d so f n o n - c l o s e - jo i n i n go p e r a t i o n s a bs t r a c t w i t hh i g h n e wt e c h n o l o g ye s p e c i a l l yi n f o r m a t i o nt e c h n o l o g yd e v e l o p i n g r a p i d l y , c u s t o m e rd e m a n dc h a n g i n gr a p i d l ya n dt h ee c o n o m i cg l o b a l i z a t i o n ， e n t e r p r i s e ss e tu pau r g e n tc l a i mt oe n h a n c et h ei m p r o v e m e n ta n di n n o v a t i o no f t e c h n o l o g ya n dm a n a g e m e n t t h ec o r eo fp r o d u c t i o na n do p e r a t i o nm a n a g e m e n t i st h a tt h ep r o d u c t i o ns h o ps c h e d u l i n gp r o b l e m sc a ng e tt h eo p t i m a ls o l u t i o n e f f i c i e n t l y , a n dt h e r e f o r et h es t u d yo fj o b - s h o ps c h e d u l i n gp r o b l e mh a si m p o r t a n t t h e o r e t i c a lm e a n i n ga n dp r a c t i c a lv a l u e f i r s tt h eo b j e c t i v e ，t y p ea n dt h ep r e s e n tr e s e a r c ho fj o b s h o ps c h e d u l i n gi s d i s c u s s e di nd e t a i l t h e nm a t h e m a t i c a lm o d e la n dr e l a t i v ea l g o r i t h m so ft h i sk i n d o fp r o b l e ma r ed i s c u s s e d ，s u c ha sh e u r i s t i ca l g o r i t h m ，e v o l u t i o na l g o r i t h m ， d o m a i ns e a r c h a n dt h e i rd i s a d v a n t a g e sa r es h o w n s e c o n dt h ee x i s t e n tp r o b l e m o fj o b s h o ps c h e d u l i n gi np r a c t i c ei ss u m m a r i z e d t h e nt h en o n c l o s e - jo i n i n g o p e r a t i o n ss c h e d u l i n gi sp u tf o r w a r d f i n a l l yt h er e s e a r c ho fm e t h o d sa n dt h e d e s i g no fa l g o r i t h mf o rt h en o n c l o s e - j o i n i n go p e r a t i o n ss c h e d u l i n gi sp r e s e n t e d a i m i n ga tt h es c h e d u l i n gp r o b l e mt h a ti n t e r d e l a y e do p e r a t i o nc o n s t r a i n t s a n da s s e m b l yc o n s t r a i n t sa r en e g l e c t e di nt h ep r a c t i c a lp r o d u c t i o n ，an o n c l o s e j o i n i n gj o b s h o ps c h e d u l i n gp r o b l e mi s p u tf o r w a r d f i r s t l yt h en e c e s s i t yo f s o l v i n gt h i sp r o b l e mi sd e s c r i b e da n dam a t h e m a t i c a lm o d e li s c o n s t r u c t e d t h e c o n c e p t so ft h es t a n d a r do p e r a t i o n s ，t h el a t e n e s so p e r a t i o n sa n dt h ee x p a n s i o n p r o c e s s i n gt r e ea r ep r o p o s e d s e c o n d l yac o n v e r s i o ns t r a t e g y ，w h i c hc o v e r t st h e l a t e n e s sc o n s t r a i n t si n t ot h es e q u e n c ec o n s t r a i n t si sd e s i g n e da n dt h ee f f e c tt h a t t h ee x c h a n g eo fm o d e lh a so nt h ec o m p l e x i t yo fa l g o r i t h mi sa n a l y z e d f i n a l l y ， t h ee x p e r i m e n ts h o w st h a tt h es t r a t e g yi sf e a s i b i l i t ya n de f f e c t i v e o nt h eb a s i so ff u r t h e rs t u d yo fn o n c l o s e - jo i n i n gs c h e d u l i n gp r o b l e m s ，a 哈尔滨理工大学工学硕十学位论文 d y n a m i cj o b - s h o ps c h e d u l i n ga l g o r i t h mw i t hn o n c l o s e - j o i n i n go p e r a t i o n si sp u t f o r w a r db yi m p r o v i n ga l l i e dc r i t i c a lp a t hm e t h o d ( a c p m ) a n db e s tf i ts c h e d u l i n g m e t h o d ( b f s m ) ：t h el a t e n e s so p e r a t i o n sa r es c h e d u l e d6 r s t l y ，a n dt h es t a n d a r d o p e r a t i o n sa r es c h e d u l e db ya c p m a n db f s ma n dt h e ya r ec o m p a c to nt h ek e y m a c h i n ea ss o o na sp o s s i b l e t h ee x p e r i m e n ts h o w st h a tt h ea l g o r i t h mn o to n l y c a ns o l v e d y n a m i cj o b s h o ps c h e d u l i n gp r o b l e m w i t hn o n c l o s e - j o i n i n g o p e r a t i o n s b e t t e rb u ta l s oc a nb ee x p a n d e dt os o l v et h ed y n a m i cj o b s h o p s c h e d u l i n gp r o b l e mw i t hc l o s e - jo i n i n go p e r a t i o n s f i n a l l yt h ed a t ao fp r a c t i c a lp r o d u c t i o ni ne n t e r p r i s ei ss c h e d u l e dw i t ht h e c l a s s i cs c h e d u l i n ga l g o r i t h ma n dt h en o n c l o s e - jo i n i n ga l g o r i t h mr e s p e c t i v e l y t h ee x p e r i m e n ts h o w st h a tt h en o n c l o s e - jo i n i n gs c h e d u l i n gs t r a t e g yi sf e a s i b l e a n dt h en o n - c l o s e - jo i n i n gs c h e d u l i n ga l g o r i t h mi ss u p e r i o r k e y w o r d sj o b s h o ps c h e u d l i n g ，n o n c l o s e - j o i n i n go p e r a t i o n ，l a t e n e s so p e r a t i o n ， e x p a n s i o np r o c e s s i n gt r e e ，a l l i e dc r i t i c a lp a t hm e t h o d i i i 。 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文非紧密衔接工序车间调度方法 的研究与设计，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人 已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文 中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：箕诗 日期：a 修子年弓月日 哈尔滨理工大学硕士学位论文使用授权书 非紧密衔接工序车间调度方法的研究与设计系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨 理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈 尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交 论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密口。 ( 请在以上相应方框内打) 作者签名： 莫诗 日期：加降岁月，日 导师签名： 蚋多 日期：m 年弓月f j 日 哈尔演理t 大学t 学硕i ：学位论文 1 1 研究背景及意义 1 1 1 课题来源 第1 章绪论 本论文“非紧密衔接工序车间调度方法的研究与设计”，来源于黑龙江省 自然科学基金项目( n o f 2 0 0 6 0 8 ) 、黑龙江省教育厅重大科技基金项目 ( n o 1 0 5 1 l z 0 0 0 8 ) ，以及哈尔滨市科技攻关基金项目( n o 2 0 0 5 a a l c g 0 6 1 1 1 ) ，旨在对生产车间调度问题及其高效、快速方法进行较深入系统的研究， 使得调度算法更加实用化。 1 1 2 研究背景 调度问题来源于不同的领域，如柔性制造系统、生产计划、计算机设计、 后勤及通信等，这些问题的共同特性是没有一个有效的算法能在多项式时间内 求出最优解。在生产计划领域中，调度主要是用于调配资源、合理安排作业 顺序，在满足现有生产条件下，使生产成本最小。调度的质量可用不同的目标 函数( 如考虑时间、费用等目标) 来度量。所以，调度( s c h e d u l i n g ) 问题有 时候也称为排序( s e q u e n c i n g ) 问题心引。 车间调度问题是生产制造领域的一个研究热点。车间调度是针对一项可分 解的工作( 如产品制造) ，探讨在尽可能满足约束条件( 如交货期、工艺路 线、资源情况) 的前提下，通过下达生产指令，安排其组成部分( 操作) 使用 哪些资源、其加工时间及加工的先后顺序，以获得产品制造时问或成本的最优 化。随着高新技术特别是信息技术的迅速发展、客户需求的快速变化及经济的 全球化，企业对加强技术与管理的改进与创新、提高企业的竞争力，提出了迫 切的需求。企业之间的激烈竞争促使企业引进了越来越复杂的生产制造系统， 如混流生产、柔性制造系统，这些新系统已产生了一些新的生产作业车间调度 优化问题，这些问题也是企业界迫切需要解决的。而较好的调度方案，不仅能 够优化资源的利用，降低生产成本，而且能够提升企业的生产经营效率和快速 反映能力，从而为企业带来较强的竞争优势。 哈尔滨理t 大学_ t 学硕1 j 学位论文 在理论界，由于许多复杂理论研究( 如数学规划、人工智能、控制理论、 防真技术等) 的发展，已经为生产作业车间调度问题的研究发展积累了丰富的 文献。生产作业车间调度问题作为生产管理的最为困难的问题，而且已证明该 类问题属于n p 难题，调度方案随机器数和工件数的增加而呈指数增长。因 此，对生产作业车间调度问题的研究，吸引了国内外许多学者和实际作业调度 人员的关注。研究生产作业调度问题最初主要采用最优化方法，尽管可以获得 最优解，但计算规模不可能很大，切实用性差。近年来，生物学、模糊数学、 人工智能、神经网络、计算机技术及进化计算的迅速发展，为生产作业车问调 度问题的研究丌辟了写的思路和方向。 1 1 3 研究意义 在企业编制生产作业计划时，经常影响到n 个工件在m 台机器上加工的 顺序问题，即当多个工件经过多台机器加工时，如何安排加工顺序使某些目标 达到最优，这就是m 调度问题。尽管调度问题最早是从生产制造中提出来 的，但并不意味着调度问题仅仅在生产制造中有应用。事实上，调度问题在企 业管理、交通运输、航空航天、医疗卫生等诸多领域都有着广泛的应用。因 此，调度问题中的工件和机器都应理解成抽象的概念，可以代表极为广泛的具 体对象，如服务机构、作业设施和操作人员等统称为“机器”。而被服务的顾 客、任务和零件统称为“工件”。 现代经济r 益强化的竞争趋势和不断的客户定制化的变化需求要求生产者 要重新估计生产制造战略，如更短的产品生产周期和准时生产系统等，利用有 限的资源满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序和 时问，以保证所选择的性能指标最优，能够潜在地提高企业的经济效益，作业 调度问题具有很多实际应用背景，丌发有效而精确的调度算法是调度和优化领 域重要的研究课题。 本课题通过对一般车间调度问题的研究，针对实际装配加工过程中通常存 在工序问延迟约束这一工程事实，提出了非紧密衔接工序调度问题。并通过从 建立问题调度模型入手，分类工序为标准工序和虚拟延迟工序，将工序l 旬的延 迟约束转换为顺序约束，实现了将工序非紧密衔接型调度问题转换为工序紧密 衔接型调度问题并给出一般非紧密衔接工序调度问题的调度策略。最后结合非 紧密衔接工序调度问题的固有特点，给出了求较复杂非紧密衔接工序动态车间 调度问题的可行算法，有一定的理论意义和实用价值。 哈尔滨理t 人学t 学硕 j 学位论文 1 2 相关领域的国内外研究概况 1 2 1 车间调度问题 通常情况下，车间调度问题的数学描述为：设有k 个产品，每个产品的工 序数为a t ，( i _ 1 ，2 固，总工序数n = 亨j ，在m 个设备上加工，要求1 台设备 一 笥= l 在某一时刻只能加工一道工序；一道工序在某一时刻只能被1 台设备加工；l 台设备一旦加工某道工序，则直到该工序加工完毕后，这台设备才i i i i 工其他工 序；每道工序都必须在其前续工序加工完后方可开始加工；当上一道工序完工 后立即送下一道工序加工；每道工序的加工时间已知，且与加工顺序无关；允 许工序之间等待，允许设备在工序达到之前闲置。一个工件在一台机器上的加 工称为一道“工序”，用“加工顺序”表示各台机器上工件加工的先后次 序，加工顺序是作业调度要解决的问题。 车间调度功能是整个企业信息系统的一个重要组成部分。车i 自j 调度结果受 到整个企业的中、长期生产计划的影响，车间调度过程必须考虑库存水平、预 测和资源需求，以对长期资源进行优化。计划功能做出的决策可能对调度有影 响，车白j 调度也需要考虑车间生产现场的状况，另外机器故障、加工时间和交 货期变更等事件都会成为调度的主要影响因素。车| 、日j 调度在生产系统中的位置 及信息流动示意如图1 1 所示。生产调度的结果就是进度计划，进度计划表在 执行过程中，视物资、设备、交货期、优先级等因素的变动进行动态调度h 1 。 当每个工件都有其独特的加工路线时，要确定工件的加工顺序，这属于作 业车间调度( j o bs h o ps c h e d u l i n g ，j s s ) 问题；当所有的加工路线都一致时， 要确定工件的加工顺序，这属于流水作业调度( f l o ws h o ps c h e d u l i n g ，f s s ) 问题；当每个工件的加工路线可任意顺序时，要确定工件的加工川页序，这属于 开放作业( o p e ns h o ps c h e d u l i n g ，0 s s ) 。 从工件加工的机器来看，可以是单机或双机，也可能是多机的；同型号机 器可以是一台；一台机器可以只加工一道工序，也可以加工几道工序；某一道 工序在某一台机器上的加工时间可以是固定的，也可以是模糊的( 加工时间可 能是一个区间) 。 从用户对产品工件的要求来看，交货期可能是固定的，也可能是模糊的 ( 交货期可能是一个区间) 。 哈尔滨理丁大学t 学硕f ：学位论文 l7 l ij “；t 戈i j 、l ：1 1 i j “l 计划 、 | 物年：i 溢求。汁戈i j 、f t e - l 一一一7 ，一一一11 型：型 。 r 弋赢蚕鬲孓 | o , y j 遂，_ ：二毒拳一_ 习誓 蚬场龄沙已l 、厂磊f i l l 。 i ：= ，；i i 为了使生产车间达到均衡生产，减少在制品库存，提高机器利用率，缩短 生产时间，需要对调度( 作业计划) 进行优化。从衡量一个调度优劣的标准 ( 目标函数) 来看，可以采用不同的评价标准，如总流程时间( m a k e s p a n ) 、 平均流程时间、最大交货误期、平均交货误期、交货误期的工件数、平均在制 品库存量、设备利用率和费用指标等，也可以采用几者的组合。 1 2 2 车间调度问题的算法研究 现代车间调度已经不但是技术和工程，而是已形成了一门科学。f 如马克 思所说：“一种科学只有成功地运行数学时，才算达到真正完善的地步”。近 年来，在车间调度研究领域应用了许多数学方法，特别是非经典数学方法及经 典数学的前沿方法，分别归纳如下： 1 启发式规则( h e u r i s t i cs c h e d u l i n gm e t h o d ) ； 2 运筹学方法( o p e r a t i o n sr e s e a r c h ) ； 3 分枝定界法( b r a n c h a n db o u n d ) ； 4 梯度下降法( g r a d i e n tm e t h o d ) ； 5 图论( g r a p ht h e o r y ) ： 6 拉格郎r 松弛算法( l a g r a n g i a nr e l a t i o n ) ； 7 机器学习( m a c h i n el e a r n i n g ) ； 哈尔演理t 人学t 学硕i j 学位论文 8 神经网络( n e u r a ln e t w o r k s ) ； 9 专家系统( 又称基于知识的系统) ( e x p e i r ts y s t e m ，k n o w l e d g eb a s e d s y s t e m s ) ； 1 0 模糊逻辑( f u z z yl o g i c ) ； 1 1 p e t r i 网络 ( p e t r in e t w o r k s ) ： 1 2 多智能体技术( m u l t i a g e n ts y s t e m s ) ； 13 模拟退火算法( s i m u l a t e da n n e a l i n g ) ； 1 4 禁忌搜索方法( t a b us e a r c h ) ： 15 过滤束搜索法( f i l t e r e db e a ms e a r c h ) ； 1 6 遗传算法( g e n e t i ca l g o r i t h m ) ； 1 7 仿真方法( s i m u l a t i o nm e t h o d ) ； 1 8 蚂蚁算法( a n ta l g o r i t h m ) ； 1 9 排队论( q u e u e i n gt h e o r y ) ； 2 0 马尔可夫决策过程( m a r k o vd e c i s i o np r o c e s s ) ； 2 1 系统工程( s y s t e me n g i n e e r i n g ) ； 2 2 组合数学( c o m b i n a t o r i a lm a t h e m a t i c s ) ； 2 3 非经典控制论( n o n c l a s s i c a lc o n t r o lt h e o r y ) ； 2 4 优化理论( o p t o m i z a t i o nt h e o r y ) ； 2 5 混沌理论( c h a o st h e o r y ) ； 2 6 进化规划( e v o l v ep r o g r a m m i n g ) ； 计算复杂性理论表明，多数调度问题都属于n p 难题，目标的搜索涉及解空 间的组合爆炸。运筹学方法、分支定界法和梯度下降等传统方法，或是需要目 标函数的特殊信息，或是复杂度大，或是优化性能差，因而一般只能处理小规 模问题，难以高效高质量地求解复杂问题。在算法研究方面，统计式全局搜索 技术和人工智能方法，例如模拟退火、遗传算法、进化规划和混沌优化等方面 的研究正在增多。由于调度问题的复杂性，单一的算法难以得到理想结果，在 实际应用中，常将多种方法组合起来，形成新的算法，如遗传算法与神经网络 结合，遗传算法与分派规则结合等啼1 。 1 3 本文研究的主要内容 关于生产作业调度问题，已有许多学者从不同的角度进行了研究，但对于 该问题的理解还有很大的差异。作为一项基础性的工作，也是一项很重要的工 哈尔滨理t 大学r 丁学顾 j 学位论文 作，本文在理清该问题的基础上，针对实际生产中经常出现的非紧密衔接工序 调度问题，提出一种将非紧密衔接工序变为紧密衔接工序的转换策略，并通过 对工序问延迟约束的进一步研究，提出标准工序、延迟工序和扩展加工工艺树 概念。通过对拟关键路径法和最佳适应调度法算法进一步完善，设计了一种通 过优先调度延迟工序，对标准工序分批采用拟关键路径法和最佳适应调度法， 同时考虑关键设备上标准工序尽量紧凑的具有非紧密衔接工序的动态调度算 法。本文的内容是这样安排的： 第2 章详细介绍了生产作业调度问题的目标、类型及研究现状，并着重就 车间型作业调度问题的研究现状和该类问题的相关算法。 第3 章提出非紧密衔接工序调度问题，并针对以往车间调度算法忽略非紧 密衔接工序调度，从而导致调度结果不精确这一情况，提出了一种考虑工序间 时间延迟约束的调度策略。实例验证表明，该调度策略可有效的解决非紧密衔 接工序调度问题。 第4 章考虑了多作业加工、作业分批随机到达等动态条件约束下的调度情 况，设计了一种基于拟关键路径法和最佳适应调度法的非紧密衔接工序动态调 度算法。并进行了算法分析和实例的计算机模拟。 第5 章对实际企业生产数据进行调度，通过对比分析改进前后的算法调度 结果，进一步验证非紧密衔接工序调度策略的可行性与调度算法的有效性。 结论，给出本文研究的结论，并讨论进一步研究方向。 哈尔滨理t 入学t 学硕f j 学位论文 2 1 引言 第2 章车间调度问题的理论与方法 调度( s c h e d u l i n g ) 就是为了实现某一目的而对共同使用的资源实行时间 分配哺1 。调度产生的原因在于多项任务共享特定的资源，而有限的资源却无法 以相对于各个单独任务的最优状态同时满足所有任务的处理需求，因而需要寻 求一种优化其中一部分或者整批任务的某种处理性能指标的方案。 人们普遍把c o n w a y 、m a x w e l l 和m i l l e r 三人有关调度的研究工作作为调度 理论研究的f 式开始，他们三人也被人们称为调度理论的奠基人，此后3 0 多 年的调度理论和应用研究都受到他们的影响，2 0 世纪7 0 年代，人们开始注意 并重视调度复杂性问题的研究，提出了用于研究算法有效性和问题难度的计算 时间复杂性理论i ，许多调度问题被证明为n p 完全问题| 9 1 。 调度问题来源于不同的领域，如生产计划、计算机设计、电力传输、军队 作战、交通运输、后勤及通信等。调度一般性的定义是在一段时| 、日j 内，为了完 成一组工作，而相应地分配一套资源。所有调度问题的共同特性是没有一个有 效的算法能在采用多项式的有效时间内求出其最优解，它们都是n p( n o n p o l y n o m i a lc o m p l e t e ) 完全问题。调度问题的复杂性、调度领域知识的多样性 和生产环境的动态性，决定了调度问题的解决单纯依靠人或计算机是难以完成 的，必须把人、人工智能技术、数学规划和计算机有机地结合起来去研究调度 问题。 2 2 车间调度问题概述 车间调度就是对一个可用的加工机床集在时间上进行加工任务集分配，以 满足一个性能指标集。从数学规划的角度看，车间调度问题可表达为在等式或 不等式约束下，对目标函数的优化。典型的车间调度问题包括一个要完成的作 业集( 工件集) ，每个作业由一个操作集( 工序集) 组成，各操作的加工需要 占用机床或其它生产资源( 人员、刀具和辅助资源) ，并且必须按一些可行的 工艺次序进行加工。每台机床可加工工件的若干操作，并且在不同的机床上能 加工的操作集可以不同。调度的目标是将作业合理地安排到各机床以及合理地 哈尔滨理t 大学t 学硕l j 学位论文 使用其它生产资源，并合理安排作业的加工次序和加工时间，在约束条件被满 足，同时优化一些生产性能指标的前提下，使总的加工时间尽可能最短。 调度问题通常涉及到四个基本要素：任务、资源、时间和性能指标，针对 这四个要素，调度的目的可简明地描述为：将任务在资源和时间上进行合理的 分派。其中，“合理”程度的评价是以一个或一组性能指标为依据的。调度问 题所涉及的领域非常广泛，如运输调度、电力调度、水资源调度、操作系统运 行调度、人员调度、项目调度、制造系统生产调度等。由于制造业在经济发展 中所占的举足轻重的地位，使得制造系统的生产调度问题一直是最为引人关注 的研究热点之一。制造系统生产调度问题的核心即是车间作业调度。在经典的 车间作业计划问题中，调度的对象是工序，即零件的加工工序，资源通常指加 工设备或机器。根据这两个要素，通常可以对车间调度进行如图2 1 的划分。 图2 1 车问调度的划分 f i g 2 1p a r t i t i o no fs h o ps c h e d u l i n g 2 2 1 车间作业调度问题描述 设有个作业，每个作业的工序数为圻，- - 1 ，2 ，。总工序数为 n _ ，在m 台设备上加工，其基本约束条件是： i = 1 1 每台设备每次只加工一个工序； 2 每个工序不能同时在多台设备上加工； 3 每个工序的加工顺序预先确定，满足技术要求； 4 每个工序在每台设备上只加工一次； 哈尔滨理t 大学下学硕t 学位论文 5 每一道工序必须在指定的设备上不问断地进行加工直到本工序完成为 止。 表2 1 描述了一个3 作业3 设备的车间作业调度问题实例，在表2 1 中不 仅给出了每一项作业在所有设备上的工艺约束，也给出了在每一个设备上加工 的时间。 表2 1 一个3 作业3 设备的车间作业调度问题的加一1 ：数据 t a b l e2 一li n f o r m a t i o no f3m a c h i n e sa n d3i o b s j s s p 作业名所在设备( 加：时间) 11 ( 3 )2 ( 3 )3 ( 3 ) 2 l ( 2 )3 ( 3 )2 ( 4 ) 32 ( 3 )l ( 2 )3 ( 1 ) 2 2 2 车间调度问题的特点 车间调度问题有以下几个特点： 1 复杂性车间调度问题的复杂性主要表现在生产环境和调度的优化计 算两方面。首先，车间中工件、机器、操作人员和搬运系统之间相互影响、相 互制约。每个工件又要考虑它的加工时间、安装时问和操作顺序等因素，因而 加工环境相当复杂。 其次，在各种条件的综合影响下，车间调度实质上是一个在若干等式和不 等式约束下的组合优化问题，从计算时f n j 复杂度看是一个n p h a r d 问题，随调 度规模的增大，问题可行解的数量呈指数级增加，因而求解非常困难。在现有 计算条件下，一般优化方法对于车间调度问题是低效甚至是无能为力的。 2 多约束性通常情况下，车f n j 调度受到工件工艺路线的约束，各道工 序的先后关系不能颠倒。同时，还受到各种资源的约束，如加工机床、操作工 人、运输小车、刀具以及其它辅助生产工具等。 3 离散性在生产车间中，工件的加工、储存和运输发生在不同的时问e l 和资源上，并且任务的到达、订单的更改、设备的增添和故障等都是离散事 件。因此，车间生产系统可以看作一个典型的离散系统，这样，就可以用数学 规划、离散系统建模与仿真的方式，通过排序理论研究车问调度问题。 4 动态随机性 在真实的车f n j 生产环境中有很多随机和不确定因素，如 工件到达时间的不确定性，实际工件的加工时间也有一定的随机性，而且系统 呛尔滨理t 大学t 学硕i ：学位论文 中常有突发偶然事件，如紧急任务插入、交货期改变、订单被取消、设备故障 或修复等。因此生产调度过程是一个动态的随机的过程。 5 多目标性实际的车间调度问题待优化的性能指标有很多，例如生产 周期、平均流通时间、平均延误率、设备利用率等，而且这些目标之间往往会 发生冲突。作者认为所有的性能指标最终都是为了减少成本，故一个可以适应 不同的任务类型和规模的通用调度系统，应该是基于成本目标的系统。遗憾的 是，迄今为止还没有一个通用并且实用的车间调度系统。 2 2 3 车间调度问题模型 车间调度问题是一个非常复杂的工程问题。近年来，学者们从不同的角度 进行了研究，出现了车间调度模型大致有下面几种： 1 多目标调度( m u l t i - o b j e c t i v ej o bs h o ps c h e d u l i n gp r o b l e m ) ： 2 可变目标调度( a l t e r a b l e o b je c t i v ej o bs h o ps c h e d u l i n gp r o b l e m ) ： 3 多资源调度( m u l t i r e s o u r c ec o n s t r a i n e dj o bs h o ps c h e d u l i n g p r o b l e m ) ： 4 动态调度( j o bs h o ps c h e d u l i n gp r o b l e mi nt h ed y n a m i ce n v i r o n m e n t ) ： 5 多工艺线路的调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t ha l t e r n a t i v e m a c h i n e s ) ； 6 批量生产调度( j o bs h o ps c h e d u l i n gp r o b l e mi nt h eb a t c hp r o c e s s ) ； 7 模糊加工时间调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hf u z z yp r o c e s s i n g t i m e ) ： 8 模糊交货期调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hf u z z yd u e d a t e ) ： 9 准时生产调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hi nj u s ti nt i m e e n v i r o m e n t ) ； l o 成组调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hg r o u pt e c h n o l o g y ) ； 1 1 协同调度( j o bs h o ps c h e d u l i n gp r o b l e mi nh o l o n i cm a n u f a c t u r i n g ) ； 1 2 虚拟制造调度( j o bs h o ps c h e d u l i n gp r o b l e mi nv i r t u a l m a n u f a c t u r i n g ) ： 1 3 敏捷制造调度( j o bs h o ps c h e d u l i n gp r o b l e mi na g i l em a n u f a c t u r i n g ) ； l4 精益生产调度( j o bs h o ps c h e d u l i n gp r o b l e mi nl e a np r o d u c t i o n ) ； 15 多智能体调度( j o bs h o ps c h e d u l i n gp r o b l e mi nm u l t i a g e n t m a n u f a c t u r i n g ) ： 1 0 - 哈尔滨理下大学下学硕l ：学位论文 1 6 分形企业生产调度( j o bs h o ps c h e d u l i n gp r o b l e mi nf r a c t a l e n t e r p r i s e ) ； 从上述调度模型可以看出：调度研究与制造模式的结合非常紧密，随着先 进制造模式的出现，出现了相应的调度模型，如精益生产调度、协同调度、分 形企业生产调度等。但还可以看出，车间调度是一个非常复杂的问题，学者的 研究只集中在某一特定方面，虽然不同的研究方面存在着联系，并有可能采用 相似的研究方法，但尚未形成一套系统的理论。 2 2 4 车间调度问题模型表示法 1 甘特图表示法甘特图是一种车间作业调度问题解的图示方法，以时 间为横坐标，以设备号为纵坐标| 1 仉川。表2 1 中给出的一个3 作业3 设备的车 间作业调度问题用甘特图表示于图2 2 中。在此图中，d ，表示作业，在设备r 上加工，对每一项作业，定义其完成时间为e ，每一个方框代表一个工序 d ，横坐标表示此工序的开始时间s 其水平方向的长度表示此工序的加工 时间p ，。此调度的总的加工时间为1 9 个时间单位。工序q ，在不改变任一设 备上其它工序的先后顺序的前提下可以被提前到以第5 个单位时间开始。 m l m 炳 o268 1 01 2 1 4 1 6 1 8t i n g e 图2 23 作业3 设备的车间作业调度问题一个解的甘特图表示 f i g 2 - 2 g a n t tc h a r to f3m a c h i n e sa n d3j o b s j s s p 2 析取图描述析取图是描述车间作业调度问题的常用工具，对项作 业、m 台设备( 共玎个工序) 的车间作业调度问题，对应的析取图模型为g = ( 彳，e ) 。其中，v 为所有工序构成的顶点集，包括0 和n + l 两个虚拟工 序( 分别表示加工开始和终止) ；具有工艺约束偏序关系的工序对( 作业内部 工序之间的工艺要求) 的集合，称为合取弧的集合a ( 实线) ；在机器k 上相邻 哈尔滨理t 大学t 学硕l j 学位论文 工序对( 表示相邻两工序在机器k 上加工的前后顺序) 的集合，成为析取弧的 集合e ( 虚线) 2 ”1 。 举例说明，如图2 3 ，图g = ( v ，a ，e ) 表示3 作业3 设备的车间作业调 度问题的析取图模型：现在以最大完成时间为指标，那么对车间作业调度问题 的求解就归结为找到各边( 即设备) 上作为优先决策的各操作的一组顺序( 即 走向) ，当同一设备上有多个操作出现冲突时，上述顺序用于决定各操作的先 后，最终得到各操作间没有冲突的一个有向非循环图，而其关键路径长度即为 最大完成时间1 。 o 789 图2 33 作业3 设备车间作业调度问题的析取图表示 f i g 2 - 3d i s j u n c t i v eg r a p ho f3m a c h i n e sa n d3j o b s j s s p 2 2 5 车间调度问题的调度指标 调度指标是评价调度方案优劣的标准。生产调度指标可以是生产周期最 短、成本最低、拖延时间最短、生产切换最少、设备利用率最高、三废最少 等。实际生产调度指标有： 1 调度性能的指标 包括：生产周期、平均流动时间、机床利用率、工人利用率等，其实质是 最大化生产能力以提高经济效益。 2 成本指标 包括：加工费用、工人工资、换线成本、延期罚款和废品损失等。 3 客户满意度指标 包括：延期时间、提前时间和延期工件的数量等。在实际的调度中，一般 以平均流通时l 、日j 最小、制造周期最短、满足交货期为调度日标。 哈尔演理t 人学t 学顾f 学位论文 2 2 6 车间调度问题的分类 车间调度问题的分类，根据研究的侧重点不同有多种分类方式。g r a v e s 依 据研究对象的复杂性对车间调度问题分类n 引，有重要的参考价值。 1 调度对象 车间调度问题按调度对象可分为多种类型，例如工件调度 ( 只考虑工件) 、资源( 如机床、操作人员、机器人、有轨小车、刀具和缓冲 区) 调度等；按制约车间生产能力的资源数量可分为单资源调度( 只考虑系统 中的一种调度