（计算机应用技术专业论文）车间调度中瓶颈问题的研究.pdf

哈尔滨理工大学工学硕士学位论文 车间调度中瓶颈问题的研究 摘要 车间作业调度问题( 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 ) 是最一般 的，最复杂的和最具难度的生产调度问题。一般的车间作业调度中，设备资 源约束是每台加工设备只有一台；因而在实际的加工调度中往往会存在对整 个产品加工时间影响较大的瓶颈，对于这种情况，一般的求解方法也往往采 用确定各个工序中工件的加工次序。 解决瓶颈问题的一种简便方法是增加瓶颈设备，现在无论在学术界还是 实际生产中对瓶颈的概念还没有很好的理解，也没有很完善的定义瓶颈的方 法；但解决车间作业调度瓶颈问题的关键不仅是找出瓶颈设备，而且要确定 是通过增加相同设备可最大幅度提高加工效率的可增加瓶颈设备，而判断可 增加瓶颈设备的方法主要是通过判断设备是否有最长加工时间的并行工序。 通过对并行工序的研究，首先提出了一种较快速准确地判断并行工序的 方法。第一步是确定加工工艺图中每一条从树叶到树根的路线，为每个工序 标记它所在的路线号。第二步进行判断，若两个工序存在相同的路线号，则 这两个工序不可以并行加工，不是并行工序；若两个工序的路线号全不相 同，则它们可以并行加工，为并行工序。然后提出了基于并行工序确定可增 加瓶颈设备的算法，得到每台加工设备上的并行工序的个数和并行工序加工 总时间，并行工序加工总时间最大的设备即为可增加瓶颈设备。 此外在一个相互紧密联系的调度系统中，设备的等待和阻塞是相互的； 所以一台设备如果处在加工状态，持续加工的时间越长，该台设备造成其它 加工设备等待或阻塞的可能性越大，因为正在加工的工序很可能就是其它设 备上将要加工工序的紧前工序，所以又提出了将紧前工序作为考虑因素来判 断可增加瓶颈设备的方法。最后分析研究了在动态j o b s h o p 调度中确定可 增加瓶颈设备的问题。 本文提出的方法为解决j o b s h o p 调度的瓶颈问题提供了新的研究思 路，具有理论和现实双重意义。 关键词j o b s h o p 调度；瓶颈；并行工序；可增加瓶颈设备 s t u d yo fb o t t l e n e c kp r o b l e mi nj o b - - s h o ps c h e d u l i n g a bs t r a c t j o b s h o ps c h e d u l i n gp r o b l e mi s t h em o s td i f f i c u l t p r o d u c t i o np r o b l e m w h i c hi st h em o s tc o m p l i c a t e da n dc o m m o n g e n e r a lj o b 。s h o p s c h e d u l i n g p r o b l e ma s s u m e st h a te v e r ym a c h i n ei ss i n g l e ，s ot h e r ei su s u a l l yc e r t a i nk i n do f d e v i c ew h i c ha f f e c t st h et o t a lp r o c e s s i n gt i m eo f p r o d u c t i o nm o s ta n db e c o m e s s c h e d u l i n gb o t t l e n e c ko ft h ew h o l ep r o d u c t i o np r o c e s s i n g t h em e t h o df o r s o l v i n gs u c hi n s t a n c ei su s u a l l yt og e tt h ep r o c e s s i n gs e q u e n c eo fe v e r yo p e r a t i o n a d d i n gt h eb o t t l e n e c kd e v i c ei s as i m p l em e t h o df o rs o l v i n gb o t t l e n e c k p r o b l e m n o wt h ec o n c e p t i o no fb o t t l e n e c kh a sn o tb e e nw e l lu n d e r s t o o d ，a n d t h e r eh a v en o tb e e np e r f e c tm e t h o d sf o rd e f i n i n gb o t t l e n e c ki na c a d e m i aa n di n p r a c t i c e ，b u tt h ek e yp r o b l e mo fj o b s h o ps c h e d u l i n gb o t t l e n e c kp r o b l e mi sn o t o n l y t of i n dt h eb o t t l e n e c kd e v i c eb u ta l s ot oc o n f i r mt h a ti t i ss u c ha n i n c r e a s a b l ed e v i c et h a tt h e p r o c e s s i n ge f f i c i e n c yc a nh a v e a ni m p r e s s i v e p r o m o t i o na f t e ras a m ed e v i c ei sa d d e d f i r s t l y , a na c c u r a t ea n df a s tm e t h o df o rj u d g i n gp a r a l l e lo p e r a t i o n si sp u t f o r w a r db ys t u d y i n gp a r a l l e lo p e r a t i o n s t h ef i r s ts t e pi st on a m ea l lr o u t e sf r o m e v e r yl e a ft ot h er o o tw i t hd i f f e r e n tn u m b e r si nt h ep r o d u c t i o np r o c e s s i n gt r e e a l ln o d e sa r es e a r c h e da n dm a r k e dt h en u m b e r so ft h e i rr e l e v a n tr o u t e s t h e s e c o n ds t e pi st oj u d g ep a r a l l e lo p e r a t i o n i ft w on o d e sh a v eo n eo rm o r es a m e n u m b e r s ，t h et w oo p e r a t i o n sr e l e v a n tt ot h et w on o d e sw i l lh a v et h ec o n s t r m n to f p r e d e c e s s o ra n ds u c c e s s o r , a n dt h e yc a nn o tb ep r o c e s s e dc u r r e n t l y i ft h e i r n u m b e r sa r ec o m p l e t e l yd i f f e r e n t ，t h et w oo p e r a t i o n sr e l e v a n tt ot h et w on o d e s w i l lh a v en ot h ec o n s t r a i n to fp r e d e c e s s o ra n d s u c c e s s o r , a n dt h e yc a nb e p r o c e s s e dc u r r e n t l y s e c o n d l y , t h ea l g o r i t h mo fc o n f i r m i n gt h ei n c r e a s a b l e b o t t l e n e c kd e v i c eb a s e do np a r a l l e lo p e r a t i o n si sp r e s e n t e d t h et o t a lp r o c e s s i n g t i m eo fp a r a l l e lo p e r a t i o n sa n dt h et o t a ln u m b e ro fp a r a l l e lo p e r a t i o n sf o re v e r y d e v i c ew i l lb eg o t t e n ，a n dt h ed e v i c ew i t ht h el o n g e s tt o t a lp r o c e s s i n gt i m eo f p a r a l l e lo p e r a t i o n sw i l lb et h ei n c r e a s a b l eb o t t l e n e c kd e v i c e - l i - i na ni n t e r c o n n e c t e dp r o d u c t i o ns y s t e m ，m a c h i n e sb l o c ka n ds t a r v ee a c h o t h e r t h e1 0 n g e ram a c h i n ei sa c t i v ew i t h o u ti n t e r r u p t i o n ，t h a ti st os a y , t h e p r o c e s s i n gs t a t e ，t h em o r ep r o b a b l ei ti st h a tt h i sm a c h i n eb l o c k so rs t a r v e so t h e r m a c h i n e s ：b e c a u s et h eo p e r a t i o np r o c e s s e di sp o s s i b l yt h ei m m e d i a t ep r e d e c e s s o r o fo t h e ro p e r a t i o n so no t h e rd e v i c e t h e nam e t h o dw h i c ht a k e s i m m e d i a t e p r e d e c e s s o ri n t oa c c o u n ti sp u tf o r w a r d f i n a l l y , t h ep r o b l e mt h a t i st of i n dt h e i n c r e a s i n gb o t t l e n e c kd e v i c ei nd y n a m i cj o b - s h o ps c h e d u l i n gi ss t u d i e d t h em e t h o dp r e s e n t e do f f e r sn e wr e s e a r c ht h o u g h tf o rt h eb o t t l e n e c ko fj o b _ s h o ps c h e d u l i n gp r o b l e m ，w h i c h h a si m p o r t a n tv a l u eb o t hi np r a c t i c ea n dt h e o r y k e y w o r d sjo b s h o ps c h e d u l i n g ，b o t t l e n e c k ，p a r a l l e l o p e r a t i o n ，i n c r e a s a b l e b o t t l e n e c kd e v i c e - i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文车间调度中瓶颈问题的研 究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或 撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明 确方式注明。本声明的法律结果将完全由本人承担。 作者虢办蓼隰孵岁月妒 哈尔滨理工大学硕士学位论文使用授权书 车间调度中瓶颈问题的研究系本人在哈尔滨理工大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工 大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和 电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、 缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密眦 ( 请在以上相应方框内打4 ) 作者签名： 参i 黟眺蝣多 刷程轹母吖 月陟日 日期：沪乡月f 蜘 哈尔滨理t 大学工学硕 ：学位论文 1 1 课题的背景 第1 章绪论 现代企业的很多类型的生产过程中，都存在着调度问题。车间作业调度问 题( 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 ) 是最一般、最复杂和最具难度的生产 调度问题，也是排序问题昭3 1 ，它研究的目的是对生产资源进行优化配置，根 据已知各个生产作业的加工时间及加工设备，在满足约束条件的限制下，使生 产资源得到优化配置，以使生产作业的某项指标( 机器的完工时间、工件流程 时间、延迟时间及生产成本等) 达到最优。 随着科学技术的飞速发展，企业之间的竞争也曰益加剧，多品种、单件小 批生产已逐渐成为当今大多数企业的主要生产模式。j o b s h o p 调度问题是单件 多品种小批量生产的典型数学模型。一般j o b s h o p 调度的资源约束是每种加 工设备一台，所以实际中往往会存在对整个加工总时间影响较大的某种设备， 形成加工调度的瓶颈h 1 ，使得产品的最后完工时间很长，影响了生产的效率。 在这种情况下采用降低成本来提高产品的加工效率已经不能为企业赢得更大的 市场，同时由于设备的单一性，导致了一般j o b s h o p 调度策略无法去解决存 在着的明显的调度瓶颈。 企业的生产规模不断提高，企业为了得到更大的生产效率，需要对调度瓶 颈问题进行分析，通过必要的投资，增加引起调度瓶颈的主要设备嵋1 ，解决调 度瓶颈问题提高加工效率嫡1 。这样如何找出引起调度瓶颈的主要设备就成了关 键问题n 1 ，将此研究成果应用于企业的生产过程当中，对于提高企业竞争力具 有非常重要的现实意义。 1 2 j o b s h o p 调度问题概述 1 2 1 j o b s h o p 调度问题的含义 车间调度问题一般可描述为：有m 台机器，个作业，每个作业有多道 工序，每道工序在某个机器上加工。问题是如何为这些作业分配机床，使某个 生产指标( 如生产周期) 最优呻1 。 哈尔滨理t 大学工学硕士学位论文 每一台机器在某个时刻只能加工某个作业的某道工序，称为占用约束；同 时每个作业只能在上道工序加工完成后才能开始下一道工序的加工，称为顺序 约束旧1 。车间调度问题的决策内容包括分配决策( 作业的加工顺序) 和时间决 策( 作业各工序的加工时间) 以及路径决策( 作业工序各加工设备的分配) 。 总的说来，车间调度就是对一个可用的加工机床集在时间上进行加工任务 集分配，以满足一个性能指标集。典型的车间调度问题包括一个要完成的作业 集( 工件集) ，每个作业由一个操作集( 工序集) 组成，各操作的加工需要占 用机床或其它生产资源( 人员、刀具和辅助资源) ，并且必须按一些可行的工 艺次序进行加工。每台机床可加工工件的若干操作，并且在不同的机床上能加 工的操作集可以不同。调度的目标是将作业合理地安排到各机床以及合理地使 用其它生产资源，并合理安排作业的加工次序和加工时间，使约束条件被满 足，同时优化一些生产性能指标。 1 2 2 j o b s h o p 调度问题的特点 1 复杂性由于加工作业、设备、库场、搬运系统之间的相互影响和制 约，同时考虑到每个作业的到达时问、装卸时间、准备时间、操作顺序、交货 期、操作人员的熟练程度等，因而实际的调度相当复杂。调度问题实质上是在 等式或不等式约束下的组合优化问题，从计算时间复杂度上往往是n p 完全问 题，即随着问题规模的增大，问题可行解的数量呈指数级增长，求解非常困 难，使得一些常规的优化方法往往无能为力。 2 离散性在生产车间中，工件的加工、储存和运输发生在不同的时间 和资源上，并且任务的到达、订单的更改、设备的增添和故障等都是离散事 件。因此，车间生产系统可看作一个典型的离散系统。 3 约束性车间调度问题中资源的数量、缓存容量、工件到达时间及工 件操作顺序等都是约束。 4 动态随机性在实际的生产调度系统中存在很多随机和不确定的因 素，比如新作业的到达，紧急任务的插入，作业的加工时间改变，且常出现一 些实发偶然事件n 叫，如设备的损坏、修复、交货期的改变等。动态事情的发生 可能导致整个系统的性能大大降低，使得原有的调度方案不能继续进行，必须 进行调整使车间性能处于较好的状态。 5 多目标性针对不同的加工任务，实际的车间调度问题待优化的性能 指标有很多，如生产周期、平均流通时间、平均延误率、设备利用率等。 哈尔滨理t 大学工学硕十学位论文 o r a v e s 曾将调度目标分为基于调度费用和调度性能的指标两大类。a l i as 等人 将调度目标分三类：基于作业交货期的副示、基于作业完成时间的目标、基于 生产成本的目标，这些目标之间往往会发生冲突，多目标性导致了如何使车间 调度系统适应不同的任务类型和规模成为车间调度中面临的难题。 1 2 3 车间调度的分类 考虑n 个工件在m 台设备上处理的问题，其中，假设每台设备不能同时处 理两个以上的工件；另一方面，各个工件也不能在两台以上的设备上同时加 工。每台设备上对各个工件的处理称为工序，把每个工序所需的设备使用顺序 称为工艺流程。各个作业的处理时间是预先给定的。最优地完成是指使目标函 数达到最小1 。一般地，根据设备环境的不同，车间作业调度问题可分为以下 三大类。 1 作业车间调度问题( 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 引。在工件技术路线约束和设 备能力约束的双重限制下，j s s p 成为n p 完备问题中最难的问题之一。 2 流水车间调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ，f s s p )在流水 车间中，机器和操作人员通常处理标准的、连续的物流。操作工总是对每批生 产任务进行同样的操作。流水车间一般是大批量生产车间或具有连续生产布局 的车间。车间的布局都是为便于产品流动而设计的。流水车间调度问题是 j s s p 的一个特例，它是在j s s p 的基础上统一了工件流经加工路线，因而比一 般的j s s p 大大简化。 3 开放式车间调度问题( o p e ns h o ps c h e d u l i n gp r o b l e m ，o s s p )在开 放式车间中，工件的加工没有特定的技术路线约束，同一工件各个工序的先后 关系是任意的。在这样的前提下，要获得一个可行调度是相当容易的，然而工 序先后关系的任意性也使可行调度的种类大大增加。当调度规模较大时，要从 可行调度空间中搜索到最优或较优调度仍然非常困难。同时，实际调度中还存 在着混合型车间调度的情况。 哈尔滨理工大学工学硕十学位论文 1 3 j o b s h o p 调度问题的算法 1 3 1 j o b s h o p 调度问题的求解算法 车间生产作业调度问题自提出到现在，学者们应用不同的理论与方法对该 问题进行求解，提出了众多不同的求解算法。最初是集中在整数规划，仿真和 简单的规则上n 3 “引。一般包括以下四种求解算法： 1 数学规划法结合运筹学的基本理论与方法，研究在满足约束条件 下，离散生产系统的任务指派，资源分配等问题，一般通过枚举的方法求解。 在解决整数规划问题的技术中，应用最多的两个技术是分枝定界法和拉格朗日 松弛法。由于调度问题属于n p 问题，计算的复杂性使得数学规划方法的运用 一直受到限制，只能用于求解简单的生产作业调度问题。 2 规则调度法使用调度规则是最传统的方法。因其调度规则简单、易 于实现、计算复杂度低等，所以能够应用于动态实时调度系统中。许多学者在 这方面已进行了探索及大量研究工作，总结了1 1 3 条规则，并将它们按形式分 为了三类：简单规则、复合规则、启发式规则n5 1 。但是近十年的研究表明并不 存在一个全局最优的调度规则，它们的有效性依赖于对特殊性能需求的标准及 生产条件。它是局部优化方法，难以得到全局优化结果，并且不能对得到的结 果进行次优性的定量评估。 3 智能优化算法近年来对生产作业调度问题求解算法研究的主要方 向，结合了进化算法、模拟退火算法、遗传算法、蚁群算法等智能算法，由于 智能优化算法自身求解过程的快速性，使得其在车间生产作业调度问题研究中 占据着主要的方向。 4 离散事件仿真离散事件动态系统( d i s c r e t ee v e n td y n a m i cs y s t e m ， d e d s ) 是指由离散事件按照一定的运行规则，相互作用而导致系统状态演化 的一类动态系统。离散事件驱动状态的演化，而状态演化又导致新的事件的出 现。基于仿真的方法，侧重对系统中运行的逻辑关系的描述，能够对生产调度 方案进行比较评价，分析系统的动态性能，并选择系统的动态结构参数。离散 事件仿真主要用来测试固定的调度算法与分配规则，仿真受仿真模型、仿真方 法及仿真试验数据等多方面因素的制约，使得仿真结果很难反映实际情况，该 方法在车间生产作业调度问题的研究中存在很大的弊端。 哈尔滨理工大学工学硕上学位论文 1 3 2 典型智能优化算法 随着对车间生产作业问题研究的不断深入，对该问题的求解算法主要集中 于智能优化算法。其中代表性的智能优化算法主要包括模拟退火算法、遗传算 法及人工神经网络等。 1 模拟退火模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 的思想最早是由 m e t r o p o l i s 等在19 5 3 年提出的，19 8 3 年k i r k p a t r i c k 等将其用于组合优化问题 的求解。s a 是基于迭代求解策略的一种随机寻优算法，其出发点是基于物理 学中固体物质退火过程与一般组合优化问题之间的相似性。算法在某一初温 下，伴随着温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标 函数的全局最优解。模拟退火算法能够有效地解决大规模的组合优化问题，而 且可以较好地避免局部最优，但算法的收敛速度很慢，这成为s a 进一步应用 的阻力。 2 遗传算法遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 起源于6 0 年代对自 然和人工自适应系统的研究n 6 1 ，并于上世纪7 0 年代由j h o l l a n d 提出基于遗传 算法思想的数学优化方法。g a 是基于“适者生存”的一种高度并行、随机和 自适应的优化算法，它将问题的求解表示成“染色体”，通过对“染色体 群 的不断进化，包括复制、交叉和变异等操作，最终收敛到最适应环境的“染色 体 ，从而求得优化问题的最优解。g a 其已被广泛地应用于机器学习、模式识 别、图像处理及优化控制等领域。但算法还有许多问题需要解决，如算法本身 的参数优化问题，如何避免过早收敛，如何改进操作手段或引入新的操作来提 高算法的效率，遗传算法与其它优化算法的结合问题等。 3 人工神经网络人工神经网络( n e u r a ln e t w o r k ，n n ) 研究至今已有 6 0 年的历史，神经网络由于其大规模并行处理、容错性、自组织和自适应能力 等，已成为解决很多问题的有效工具。神经网络通常指由大量简单神经元互联 而构成的一种计算结构，它在某种程度上可以模拟生物神经网络系统的工作过 程，从而具备解决实际问题的能力。神经网络优化算法利用神经网络中神经元 的协同并行计算能力来构造的优化算法，它将实际问题的优化解与神经网络的 稳定状态相对应，把对实际问题的优化过程映射为神经网络的计算过程。神经 网络被广泛地应用于控制工程、优化计算、模式识别和经济等领域的问题n 7 1 。 上述的优化算法已经被广泛的用于各种工程实际问题的求解，但随着智能 优化算法研究的不断发展，出现了众多新的优化算法，这些优化算法的提出为 各种优化问题求解方法的改进与完善提供了新的手段。 哈尔滨理工大学工学硕上学位论文 1 4 j o b s h o p 调度瓶颈研究现状及发展 1 4 1 j o b s h o p 调度瓶颈研究现状 提高生产效率最有效的方法是定义和消除制造系统的瓶颈，然而无论在学 术界还是实际生产中对瓶颈的概念还没有很好的理解n 引，也没有很完善的定义 方法。通常，瓶颈被理解为整个系统中加工效率最低或在某些情况下，待加工 的工序数量最大的机器。按最优生产技术的定义n 引，所谓瓶颈，指的是实际生 产能力小于或等于生产负荷的资源。但实际上瓶颈的确定必须建立在系统分析 的基础上。 现在还是有一些较好的方法能够用来找到生产系统中的瓶颈，在国外的研 究中有两种比较常用的方法，一种就是衡量不同设备的利用率，有最高利用 率的设备被认为是瓶颈，但是不同设备的利用率经常是很相似的，不能确切地 说哪一台设备是瓶颈，同时该方法仅限于稳定的状态系统；另一个经常用到的 方法是分析加工设备的队列长度抬，在该方法中确定队列长度或等待时间，有 最长的队列或等待时间的设备被认为是瓶颈，该方法有能通过简单比较队列或 等待时间判断出暂时的瓶颈的优点，但同时它也有缺点，因为很多生产实体只 有一个有限的队列或根本没有队列，在这种条件下，队列的长度不能够用来检 测瓶颈；其次，在一个饱和的生产系统中，新的工件的供应超出了系统的容 量，队列的长度不能检测出瓶颈。 上海交通大学自动化研究所的左燕等提出了移动瓶颈机子问题优先级确定 方法引，另外还有转移瓶颈算法堙引，转换瓶颈算法心引，是由一系列的c a r l i e r 解 单机调度问题组成，实际上，在c a r l i e r 算法中，工序被看作是相互独立的， 而实际上一些工序之间可能存在约束关系，从而可能导致产生不可行解。清华 大学的李黎等提出了基于瓶颈分析的优先权调度算法心副，是以优化瓶颈工序为 核心的解决车间调度的启发式算法。 这些方法在某种程度上都是可利用的，也能得到较好的优化结果，但它们 都有一个或多个缺点，是在现有设备资源限制的条件下，对工序调度顺序的确 定，虽然也优化了算法，但由于设备的限制，有时也可能不能解决瓶颈问题， 使生产效率得不到较大的提高，因此车间作业调度( j o b s h o p 调度) 的瓶颈问 题还有待深入研究和完善。 哈尔滨理t 大学工学硕士学位论文 1 4 2 j o b s h o p 调度瓶颈问题的发展趋势 随着经济全球化和信息化的深入发展，为了应对瞬息万变的市场，企业对 生产管理的信息化要求越来越高；尤其是那些生产大型设备的制造企业，产品 的零部件占用资金非常大，它们的生产方式不可能是有库存的现货生产模式， 只能是按订单( m a k et oo r d e r ，m t o ) 的生产模式1 ，同时关键设备的制造能 力直接决定整个企业的制造能力。因此企业往往要求生产计划系统首先在不考 虑其他生产要素的约束情况下，专门配置企业的瓶颈设备资源，以便最大限度 地发挥关键设备的制造能力，从而释放整个企业的最大产能。开发针对订单生 产模式的、面向关键设备资源配置的计划调度系统乜引，其中非标准作业车间调 度问题( n o n s t a n d a r dj o b s h o ps c h e d u l i n gp r o b l e m ，n j s s p ) 乜引，就是放宽了 资源约束条件，能够加工同一道工序的设备不唯一，即有一个机器集，其上的 任意一台机器都能加工该道工序。此类调度问题扩大了寻优空间，增加了问题 的难度，因此是更复杂的组合优化问题。 1 5 本文研究的意义和主要内容 1 5 1 课题来源 本课题来源于黑龙江省自然科学基金( f 2 0 0 6 0 8 ) 、黑龙江省教育厅重大科 学研究项目( 1 0 5 5 1 2 0 0 0 8 ) 、哈尔滨市科技攻关项目( 2 0 0 5a a l c g 0 6 1 1 1 ) 。 1 5 2 本文研究的意义 虽然低成本是衡量一个企业是否具有竞争优势的一个重要标准，但现在采 用降低成本来提高产品的加工效率有时已经不能为企业赢得更大的市场，同时 由于设备的单一性，导致了一般j o b s h o p 调度策略无法去解决存在着的调度 瓶颈。解决制造加工系统中的瓶颈是提高生产效率最有效的方法之一。随着经 济全球化的发展，企业之间竞争日益激烈，企业面临缩短交货期，提高产品质 量，降低成本和改进服务的压力，随着生产规模不断的提高，企业为了得到更 大的生产效率，就要增加必要的设备，但是由于设备的稀缺性和高额的折旧费 用，企业不希望也不可能靠盲目增加现有设备来解决瓶颈矛盾，这时就需要对 调度瓶颈问题进行分析，增加引起调度瓶颈的主要设备，通过增加瓶颈设备来 哈尔滨理工人学工学硕士学位论文 为企业带来更大的经济效益。这样如何找出引起调度瓶颈的主要设备就成了关 键问题，这类问题放宽了资源约束条件，加大了目标解的寻优空间，是实际中 存在的更为广泛的一类调度问题。将本课题的研究成果应用于企业的生产过程 当中，对企业有长远的现实意义。 所以本课题的研究具有重要的理论意义和实用价值。 1 5 3 本文研究的主要内容 本课题研究的重点是：针对企业需要增加必要的设备，但关键是找出可增 加瓶颈设备的问题，对车间作业问题进行研究分析，设计寻找可增加瓶颈设备 的有效算法。归纳起来，主要研究内容如下： 1 研究并行工序，寻找瓶颈设备的一个基础就是确定并行工序，从产品 加工工艺图开始分析，重点研究如何判断并行工序。 2 提出了基于并行工序确定可增加瓶颈设备的算法，判断可增加瓶颈设 备的一个简便方法是判断设备是否有最长的并行工序加工总时间。 3 提出了基于紧前工序确定可增加瓶颈设备的方法。 4 研究分析了在动态j o b s h o p 调度中确定可增加瓶颈设备的问题。 1 6 论文结构 第l 章介绍了j o b s h o p 调度问题的背景、含义、特点及分类，然后给出 了现有的研究j o b s h o p 调度问题的方法以及瓶颈问题的现状及发展趋势，最 后阐述了课题的研究意义，来源以及论文的主要研究内容。 第2 章给出了并行工序的概念，提出了并行工序的判断方法，并给出了实 例，该方法是判断瓶颈设备的基础。 第3 章在并行工序的基础上，提出了一种判断可增加瓶颈设备的算法，给 出了实例验证。 第4 章在第3 章的基础上，提出了重点考虑紧前工序来判断可增加瓶颈设 备的算法，并进行了实例验证。 第5 章在前几章的基础上，研究了在动态j o b s h o p 调度中确定可增加瓶 颈设备的问题。 结论部分对本文进行了总结，并对进一步的研究做出了展望。 哈尔滨理工大学工学硕士学位论文 2 1 引言 第2 章并行工序及其判断 并行加工是指在生产车间中有九个零件需要在某种机床上完成加工任务， 可以完成该工序加工的机床有m 个( 一般m 刀) 。各零件加工时间不一定相 同，但每个机床的加工效率相同心9 1 。标准j o b s h o p 调度具有两类基本约束：工 艺路径约束和加工设备独占性约束啪1 。其中前者要求工件的任意一道工序必须 在其紧前工序完成后才能开始，所以它们的开始加工时间有一定的时序关系； 后者要求工件的任意一道工序必须在一台加工设备上加工，并且一旦工序开始 加工，不能中断。若增加了瓶颈设备，则瓶颈设备和与其相同的设备就可以并 行加工工序，因为j o b s h o p 调度中，某些工序有紧前和紧后的约束，因此， 要研究增加瓶颈设备问题，首先就要研究分析并行工序的问题。 2 2 加工工艺图 一般产品的加工工艺图呈树状形式口，只是边的方向与树相反，于是产品 加工树中出度为零的结点为树根，即为产品加工的最后一道工序，树中入度为 零的结点为树叶，入度大于1 的结点为叉点。 各个工序从整体上虽然彼此都有联系，但是，如果仔细分析，会发现每个 工序都有其自身的特点：如从整个产品工艺图看，是否前后有直接与其联系的 紧前或紧后工序、紧前工序有几个、与最后工序的联系，即属于关联最后工序 的哪个分支；如从产品工艺图的某个分支看，或从产品工艺图的某个分支的分 支看，每个工序都有上面分析的不同特点。 由于每个工序都有不同的特点，因此每个工序对产品加工结束时间所起的 作用不同。如图2 1 为某一产品的加工工艺树，其中方框内分别为： l 产品工序号i j n m 设备号工序加工时间 l 其中a 1 l 为树根结点，它底层的所有工序都是它的前工序，最底层的各个 工序之间的加工不受影响，但在同一支路上的工序则相互之间受到影响，如 a 4 一a 7 一a 卜一a1 ( 卜一a1 】。 哈尔滨理工大学t 学硕士学位论文 l a l1 z z u l l _ 一 l a l 0 i 3 5 a 8 声3 3 0i 龟 a 9 2 4 0 1 a2莲135 i a 3 3 3 0j a 6 2 3 0 甚a 7 3 萧5 趣 l 图2 一l 产品加工工艺树 f i g 2 1p r o c e s s i n gf l o wc h a r to f p r o d u c t i o n 通过对产品加工工艺图仔细的分析与分解，将对产品加工结束时间起关键 作用的工序提炼出来，称它们为关键工序刳，并将关键工序加工顺序在其所需 要的设备上紧凑排序，将关键工序尽早完工；对非关键工序，利用设备加工工 序的并行性，将非关键工序按相应的调度分析，根据工序加工的前后顺序，分 别插入由关键工序在相应设备上加工排序所产生的空闲段中，因此对产品加工 工艺图仔细的分析与分解，结合有效的调度方法，可以缩短产品加工的总时 间，即求出产品加工调度的近优解。 2 3 相关和独立工序调度的数学描述 设有k 个产品，每个产品的工序数为，三= 1 ，2 ，k 。总工序数 = 萎以，在m 台设备上加工，要求： 1 一台设备在某一时刻只能加工一道工序； 2 一道工序在某一时刻只能被一台设备加工； 3 一台设备一旦加工某道工序则直到该工序加工完毕后这台设备才能加 工其它工序； 4 每道工序都必须在其紧前工序加工完后方可开始加工； 5 当上一道工序加工完后立即送下一道工序加工； 6 每道工序的加工时间已知，且与加工顺序无关； 7 允许工序之间等待，允许设备在工序达到之前闲置。 假设加工的产品在除最后工序外只具有唯一紧前、紧后相关工序和独立工 序时，由于产品最后工序的开始加工时间必须等其前面的相关工序和独立工序 哈尔滨理t 大学工学硕上学位论文 加工完毕，所以产品加工时间主要受其最后工序前的唯一紧前，紧后相关工序 和独立工序全部加工完毕时间的影响。假设在最后工序的加工时间不计的情况 下，使得k 个产品全部加工完毕时间为在给定约束条件下的最短值，其数学描 述，见式( 2 1 ) 。 t = m i n m a x t 驴+ g l ，j ( 2 1 ) s j m i n ( t f ，) ，f ，+ l b + g ， i = 1 ，2 ，m 7 = 1 ，2 ，n f 矽m a x ( t l ，+ g ，)当0 是r 叫的紧前工序时 其中为设备f 的第个工序的开始加工时间；g i | ：为设备i 的第个工序的 连续加工时间。 2 4 并行工序定义及判断 2 4 1 并行工序的定义 并行加工是指在生产车间中有九个零件需要在某种机床上完成加工任务， 可以完成该工序加工的机床有m 个( 一般m 甩) 。各零件加工时间不一定相 同，但每个机床的加工效率相同。一般的j o b s h o p 调度问题中要求一台设备 在某一时刻只能加工一道工序；一道工序在某一时刻只能被一台设备加工；一 台设备一旦加工某道工序，则直到该工序加工完毕后，这台设备才能加工其他 工序；每道工序都必须在其紧前工序加工完后，方可开始加工；当上一道工序 加工完后，立即送下一道工序加工；某些工序的开始加工时间有一定的时序关 系。 但有时某些工序之间是可以并行加工的，就是说在某一时刻，某个工序a 的加工不影响另一个工序b 的加工( 若不考虑设备的独占性) ，工序a 加工的同 时工序b 也可以加工，像这样的工序称之为并行工序。 2 4 2 并行工序的判断 一个产品的加工中有相关工序和独立工序n3 。，相关工序的加工不太灵活， 通常是不可以并行的，但不同的相关工序序列加工可以是并行的。另外，严格 哈尔滨理工大学工学硕士学位论文 地说，产品加工无独立工序，只是本文假设在不考虑产品的最后工序情况下， 将不存在紧前或紧后工序的工序称为独立工序i 独立工序的加工特点是不仅可 并行、时间短，而且没有工序开始时间的时间约束，因此具有很强的灵活性。 事实上，在具体的算法中，将两类工序分别采用不同的判断方法不仅简化了算 法，降低了复杂度，而且更充分地考虑了工序在设备上加工的并行性m 1 ，即提高 设备的利用率，又缩短了产品加工的总时间。 通过分析下面给出了判断不同的相关工序，独立工序是否为并行工序的方 法。从每个叶子结点到树根都是一条路线，每一条路线上的所有工序都存在紧 前，紧后工序的关系，加工的顺序是：先加工叶子结点工序，然后是紧连着叶 子结点的第二个工序，依次直到树根结点；不同的路线相当于不同的相关工序 序列，在不同路线上的工序的加工是可以并行的。 根据对产品力n - r _ 工艺树以及上面所有工序的分析，下面给出了判断并行工 序的方法，主要分为两步： 第一步是确定每个叶子工序结点到树根工序结点的路线号：分别为每一条 从叶子到树根的路线命名不同的路线号，例如，叶子口到树根x 的这条路线命 名为1 ；叶子b 到树根z 的路线命名为2 ，依次命名每一条路线。这样，每一条 从叶子到树根的路线都有了一个不同的号。检索每一条路线上的所有工序，每 一个被检索到的工序都被记录下其所在的路线号，例如，在叶子a 到树根x 的 这条路线上检索到工序m ，则m 被标记上该路线号l ，当这条路线1 上的工序 被检索完后，所有在该路线上的工序结点都被标记上路线号l ；很多时候有的 工序可能同时在不同的路线上，但该工序每次被记录的路线号都不被覆盖，全 部保留。 第二步是比较任意两个工序的路线号。检索完产品加工工艺树中所有的工 序，最后每一个工序都被标记了路线号，比较任意两个工序被标记的路线号， 若有一个是相同的，则说明这两个工序有紧前、紧后工序的约束，不能并行加 工；若这两个工序被标记的路线号全不相同，则说明这两个工序没有紧前、紧 后工序的约束，则它们可以并行加工，即为并行工序。例如，工序c 的路线号 为1 ，2 ，5 ，工序d 的路线号为2 ，7 ，工序e 的路线号为3 ；因为工序c 与工序 d 有一个共同的路线号2 ，所以它们不是并行工序；但是工序c 与工序e 没有相 同的路线号，所以它们是并行工序，同理工序d 与工序e 没有相同的路线号， 所以它们也是并行工序。 哈尔滨理t 大学t 学硕士学位论文 2 4 3 实例 i 如图2 2 为产品a 的加工工艺树，方框中的内容分别为：产品工序号i d n 工设备号工序加工时间。 a 8 5 2 5a 9 3 1 3 0 | ia 1 0 1 3 0a 1 1 2 2 5a 1 2 4 2 0a 1 3 2 1 3 5 | | a 1 4 1 3 5a 1 5 2 1 5 a 2 4 ，2 00a 3 ，4 ，1 5l ia 4 ，5 3 0l1a 5 5 2 0ia 6 l ，1 5 图2 - 2 产品a 加工工艺树 f i g 2 - 2p r o c e s s i n gf l o wc h a r to fp r o d u c t i o na 根据给出的并行工序的判断方法，首先是确定每个叶子工序结点到根工序 结点的路线号。从图2 2 可以看出，该加工工艺图有1 1 个叶子结点，从左至 右依次是a 2 、a 0 、a 1 、a 4 、a 1 0 、a 5 、a 6 、a 1 2 、a 7 、a 1 4 、a 1 5 ，所以总 共有1 1 条路线，其中a 2 2 为根结点。从最左端的a 2 开始，a 2 到a 2 2 的路 线号命名为1 ，a 0