（系统工程专业论文）VLSN在带有模糊交货期的单机调度问题中的应用.pdf

东北大学硕士论文摘要 摘要 本文讨论了带有模糊交货期的单机调度问题，目标函数是总加权满 意程度最大化。带有模糊交货期的单机调度问题的条件假设如下：n 个 工件以，以，。要在一台机器上加工，机器每次只能加工一个工件，工件 之间不具有优先关系，在开始阶段所有的工件都可以加工，并且工件一 旦被加工，不允许中断，工件的加工时问依次为p 。，p ：，n ，交货期依 次为( d l ，d 。+ q ) ，( 吐，畋+ p 2 ) ，( 以，以+ g 。) ，权值依次为嵋，k ，完成时 间为c l ，c 2 ，e ，对于每个工件根据它的完成时间定义一个满意程度 ( c ，) ，目标函数为m f l t x w ，芦( c ，) ，这是一个n p - 难问题，我们用启发式 。 面。 算法寻找近优解。本文对模糊集在带有模糊交货期调度中的应用作了综 述，在i s h i b u c h i1 9 】的基础上讨论了在一定条件下，总加权满意程度最大 化与加权拖期最小化之间的关系。提出了在一定条件下，带有模糊交货 期单机调度问题中的统治规则，两个定理和三个推论。介绍了大规模邻 域构造的基本思想，并证明基于交换和单向插入所构造的两种邻域是指 数邻域，即大规模邻域。讨论了大规模邻域对于解的质量改进的作用及 其基于动态规划思想的求解方法d y n a s e a r c h 。并举例说明大规模邻域与 传统邻域之间的区别。也即是大规模邻域的优点。实现了两种d y n a s e a r e h 算法。通过例题对大规模邻域求解的算法d y n a s e a r c h 的步骤进行了说明。 为了得到更好的解。把d y n a s e a r c h 算法与迭代局域搜索算法相结合，即 是迭代d y n a s e a r c h 算法。对于迭代局域搜索算法中的扰动策略即在k i c k 策略中引入了误差限制，对k i c k 后的满足限制条件的点进行局域搜索， 否则重新进行k i c k 的思想，实验表明这种思想还是有一定作用的。本文 还讨论了把统治规则与局域搜索相结合的两种方式：( 1 ) 对初始解应用 统治规则，改善初始解的性能：( 2 ) 对k i c k 后的点应用统治规则。 通过实验表明，统治规则与初始解的结合对解的质量在不增加计算 时间的情况下有明显的改善；嵌入统治规则的k i c k 迭代算法在不影响解 的质量的情况下能够减少程序的运行时间；基于交换d y n a s e a r e h 邻域的 l l 东北大学硕士学位论文摘要 i l s 算法比基于插入d y n a s e a r c h 邻域的i l s 算法好，并优于此问题的以 交换为邻域的多初始点改进算法。 关键词单机调度交换插入模糊交货期加权满意程度 统治规则大规模邻域动态规划d y n a s e a r c h 迭代局域搜索接受准则多点改进算法 1 1 1 东北大学硕士论文a b s t r a c t a b s t r a c t t h ep a p e ri sar e s e a r c ho ns i n g l em a c h i n es c h e d u l i n gp r o b l e mw i t h f u z z yd u e - d a t e s t om a x i m i z et h et o t a l w e i g h t e d s a t i s f a c t i o nl e v e l w e c o n s i d e rt h e p r o b l e m o f s c h e d u l i n g 行j o b s f o r p r o c e s s i n g w i t h o u t i n t e r r u p t i o n ，o nas i n g l em a c h i n et h a tc a np r o c e s so n l yo n ej o ba tat i m e f o re a c hj o bj o i 。j ，2 ，玎) ，l e tp jb e t h e p r o c e s s i n gt i m e ，面b e t h e s a t i s f a c t o r yd u ed a t e ，e jb e t h eo p t i m i s md u ed a t e ，白b et h ec o m p l e t i o nt i m e a n d w jb et h eb e n e f i to c c u r r e df o re a c hu n i to f s a t i s f a c t i o nl e v e l e a c h j o b h a sa s a t i s f a c t o r y l e v e l p ( c jj f o ri t s c o m p l e t i o n t i m e t h eo b j e c t i v e + n f u n c t i o ni st om a x i m i z et h et o t a l w e i g h t e ds a t i s f a c t o r y l e v e l w j u ( c j ) ， j z l w h i c hi sn p - h a r d i nt h i sp a p e r ，t h er e l a t i o nb e t w e e nt h em a x i m i z a t i o no f t o t a lw e i g h t e ds a t i s f a c t i o na n dt h em i n i m i z a t i o no ft o t a lw e i g h t e dt a r d i n e s s u n d e rs o m ec o n d i t i o ni sd i s c u s s e db a s e do ni s h i b u c h i 【9 1 t h e r ei 。sa l s oa n a n a l y s i sa n ds u r v e yo nt h ea p p l i c a t i o no ff u z z ys e t si nf u z z yd u ed a t e si nt h e p a p e r i nt h i s p a p e r w ep r o p o s et w od o m i n a n c er u l e sf o rt h e s i n g l e m a c h i n ef u z z ys c h e d u l i n gp r o b l e ma sw e l l ，a n dg e tt h r e ed e d u c t i o n so ni t m o r e o v e r , t h ep a p e ri n t r o d u c e ss o m ef u n d a m e n t a lc o n c e p t so ft h em e t h o di n w h i c ht h ev e r yl a r g es c a l en e i g h b o r h o o d ( v l s n ) i sc o n s t r u c t e d ，a n dp r o v e s t h a tt h es i z eo ft h e n e i g h b o r h o o d i s e x p o n e n t i a l ，w h i c h m e a n st h e n e i g h b o r h o o d i s v e r yl a r g e f u r t h e r m o r e ，t h ep a p e rp r e s e n t s t h e d y n a s e a r c ha l g o r i t h mw h i c hi sb a s e d o nd y n a m i cp r o g r a m m i n gt os e a r c ht h e l o c a l o p t i m a l s o l u t i o no ft h e n e i g h b o r h o o d ，a n ds h o w st h ed i f f e r e n c e s b e t w e e nt h ev l s na n dt h et r a d i t i o n a ln e i g h b o r h o o db yan u m e r i ce x a m p l e ， w h i c hi st h ea d v a n t a g eo fv l s n i na d d i t i o n ，t h e r ei sa ni l l u s t r a t i o no ft h e d y n a s e a r c ha l g o r i t h mb ya ne x a m p l ei nt h ep a p e r t oi m p r o v et h eq u a l i t y o ft h e s o l u t i o n ，w e f i r s tc o m b i n et h e d y n a s e a r c ha l g o r i t h mw i t hi t e r a t e d l o c a ls e a r c hi nw h i c ht h ek i c k s t r a t e g y i s e m b e d d e d ，a n dt h i s k i n do f 东北大学硕士学位论文a b s t r a c t a l g o r i t h mh a s b e e nn a m e di t e r a t e d d y n a s e a r c hi n s o m ep a p e r s t h e nw e c o m b i n et h ed o m i n a n c er u l ew i t ht h ei t e r a t e dd y n a s e a r c ha l g o r i t h mt h r o u g h t h et h r e ef o l l o w i n gm e t h o d sa sw e l l ：1 ) a p p l y i n gd o m i n a n c er u l et ot h e i n i t i a ls o l u t i o n ；2 ) a p p l y i n gd o m i n a n c er u l et ot h es o l u t i o nk i c k e d t h er e s u l t so fe x p e r i m e n t ss h o wt h a tt h ef i r s tc o m b i n a t i o ni s v e r y u s e f u lt oi m p r o v et h eq u a l i t yo ft h ef i n a ls o l u t i o nw i t h o u ti n c r e a s i n gt h e o p e r a t i o nt i m e ，a n dt h es e c o n do n ec a nr e d u c et h et i m ec o n s u m e db yt h e p r o g r a m w i t h o u t d e c r e a s i n g t h e q u a l i t y o fs o l u t i o n s t h e r ei sa l s oa c o m p a r i s o n o ft h ei t e r a t e d d y n a s e a r c h a n dm u l t i - s t a r t i m p r o v e m e n t a l g o r i t h m ，a n di ts h o w s t h a tt h ef o r m e ri sp r i o rt ot h el a t t e r k e yw o r d s ：f u z z yd u ed a t e s ，d y n a s e a r c hs w a p ，i n s e r t ，d o m i n a c er u l e ， v e r yl a r g e s c a l en e i g h b o r h o o d ( v l s n ) ，d y n a s e a r c h ，i t e r a t e dl o c a ls e a r c h ， w e i g h t e d s a t i s f a c t i o n l e v e l ，a c c e p t a n c er u l e ，r a n d o m k i c k ，i t e r a t e d d y n a s e a r e h ，m u l t i s t a r ta l g o r i t h m v 东北大学硕士学位论文 声明 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意! 本人签名：7 娶形浼 日期：垆中2 f 东北大学硕士学位论文第一章绪论 第一章绪论 自从z a d e h ! 】先生在1 9 6 5 年发表第一篇关于模糊集的论文以来， 模糊集合已经被广泛的应用于各个领域，从那时起已经有7 0 0 0 多篇关于 模糊集的论文、报告、专刊和书籍出版。旱些时候，人们关于模糊集的 研究还是属于用模糊集来描述人们认知过程中的不确定性。现在，模糊 集已经应用到工程、商业、医药科学和自然科学等领域。过去几年里， 模糊集已经成功地应用于生产管理领域。模糊集已经被看作是一种建模、 求解问题的很重要的技巧。有很多研究者把模糊集用于解决调度问题。 1 1 问题的来源及研究目的 本论文的研究课题来源于国家自然科学基金项目基于v l s n 的智 能i l s 优化方法及其在调度中的应用研究( 6 0 2 7 4 0 4 9 ) 。 本论文的目的是研究带有模糊交货期的单机调度问题，目标函数是 总加权满意程度最大化。并把v l s n 应用于该问题。完成了两种v l s n 的算法，并与统治规则相结合，改进算法的性能。最后对算法进行了分 析和比较。 1 2 单机调度问题 调度问题是运筹学的一个分支。其主要目的是在满足一定的技术与 资源约束的条件下对操作的排序，按照排序的次序给操作分配资源和时 间，使某个预定目标达到最优或近优。调度问题主要集中在车间的计划 与调度方面，许多学者作了大量研究，出了不少的研究成果。制造系统 的生产调度是针对一项可分解的工作( 如产品制造) ，探讨在尽可能满足 约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过下达生产指 令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加工的先后顺 序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问 题常被称为排序问题或资源分配问题。自从2 0 世纪5 0 年代，j o h n s o n 1 东北大学硕士学位论文第一章绪论 第一次提出了求解流水车间两台机器下排序问题最优解的法则，计算机 和制造系统的调度问题已经成为广泛研究的主题。但是根据具体应用背 景的不同，调度理论的应用范围已经超越了计算机和制造系统，而涉及 到农业、医疗业、运输业和航天业等领域。调度的对象也由开始的机器 上的加工工序拓展为交通中的运输工具、学校中的课程、医院中的病床 或手术，及c p u 处理中的进程。 调度问题在各行各业的广泛应用引起了人们的浓厚若趣，在运筹学、 应用数学、计算机科学、生产管理科学、人工智能以及工程科学等领域， 大量新的文献不断涌现1 2 ，由此可见调度研究的重要性。随着科学技术 日新月异的变化和社会经济的发展，在一定程度上决定生产经营过程能 否稳定高效运转的调度问题的复杂性和重要性不断提高。 实际情况中经常有这样的情况：一些待完成的工作需要在唯一的加 工设备资源上完成。机器一次只能处理一项工作，各工作之间是相互独 立的。在一台机器上进行工作的调度在理论和实际问题中都具有重要意 义。研究单机问题的理论是理解更大规模的多机调度问题性质的重要模 块。研究单机问题的排序方法对研究复杂问题的有指导性作用，并且为 处理复杂的排序闯题提供了近似算法。 实际上，单台机器的排序问题也是存在的。例如，一组工人修理几 台损坏了的机器。几艘轮船等待停靠一个码如一个考生要做几道考题， 几个人等待一台机器复印资料等，都可以归结为单台机器排序问题。在 工业生产中，也存在类似的问题。如，一台进行流程式生产的工厂，每 次只能生产一种产品。这种情况可以看作单台机器的排序问题。对于有 多台机器的工厂或车间，往往有一台关键车床。它的作用的发挥，会直 接影响到全厂产品的生产。这时，整个工厂或车间生产安排问题的焦点 就在这台关键车床上。这也是可以按单台机器的排序问题来考虑。 1 3 模糊模型的作用 在任何一门学科中，模糊模型的作用【2 6 1 究竟是什么呢? 贝尔曼 ( r e b e l l e m a n ) 在1 9 7 3 年作了一个极好的回答： 东北大学硕士学位论文第一章绪论 “要想确切地描绘任何现实的物理状态，事实上是办不到的。这是 个公认的并经过检验的事实。因此，描述( 对于通讯，作决定，推而 广之对于人的一切活动都是不可少的) 的主要问题是：减少必然会有的 不确切性，使它达到无关紧要的程度。为了把整个问题描述得详尽，我 们必须在准确和简明之间取得平衡，既减少复杂性而又不过于简单化”。 哥根( j a g o g u e n ) 在1 9 7 4 年说得更加准确：“描述的不确切性并不是 坏事，相反，倒是件好事，它能用较少的代价传送足够的信息，并能对 复杂事物作出高效率的判断和处理。也就是说，不确切性有助于提高效 率。” 产生上述看法的原因，是由于系统日益复杂，不可能精确地描述它， 因此产生了所谓互克性原理。这里，我们从扎台( l a z a d e h ) 1 9 7 3 年的一 篇论文中摘录一段话来说明。 “从本质上说，互克性原理的要旨是：当系统日益复杂，人们对它 作精密而有意义的描述的能力将相应地降低，以至达到精密性和有意义 ( 或适用性) 成为两个几乎互相排斥的特征的地步。在这种意义下，对 人文系统特性精密的数量化描绘，对现实世界中社会的、政治的、经济 的以及其他形式的问题，都不会产生多大的适用性。这里说的人或指个 人或指一群人。” 模糊集之所以成为模拟和分析决策系统的一种方法，是由于模糊集 能够在质量和数量上模拟模型中的模糊性和不确定性，从而引起了生产 管理研究者的极大兴趣。一些研究者指出了模糊集在以下领域具有极大 的潜力：新产品的开发，设备的选址和布局，生产调度和管理，库存管 理，质量和费用的效益分析。同时他们也指出模糊集应用于生产管理的 三个主要原因：首先是决策者对于所研究问题的认识存在着模糊性和不 确定性；其次，在生产管理中，需要考虑的模型的目标，决策变量，约 束和参数可能存在不确定性和无法准确计算；第三，由于人们的偏见和 主观意愿使得可用信息的质量和数量变得模糊和不确定。所阻模糊集可 以成为生产管理研究中的描述性和说明性的模型之间的桥梁。 那么，为什么用模糊集而不是概率来表示这种不确定性呢? 这是因 3 东她走学磺士学蓥谤文第一毒毖谶 为： 薹毙，嚣予调凄审憋不磷定娃参数，热粟其处避方法是剩燃嘏率摸 型即概率分布来攒述不确定的参数，在这种情况下，计算和优化这些模 蘩燕菲鬻醒露魏，著羹簿手不礁定参数，炎有透避对嚣受上静穴爨豹数 据进行分析观察，才能得到它的概率分布。但是。对于莱些新产品，豉 禳多皇产戆产瑟，一黧不确定参数戆壤率努毒是笼法确囊靛。这鞋，哭 能用其他方法来处理这种模裂。 其次，模鞋集帮穰率是霹令不瓣黪禳念。摸颧幢莲辫攀耱零龛是穰 糊的，而概率怒指事物的发生与否怒不确定的。如：日常生活中，经常 翳瓣嚣莱莱盘镪瑟懿禽金量灸霉争9 9 ，藏霹浚理解凳该梅菇羼予缝金熬 稷度为9 9 9 9 ，即是一个模糊集；而如果换成该饰品怒纯金的概率为 9 9 9 9 ，+ 这蓑怒嚣今不弼鹃概念。 最舞，模糊集痘用于调度问题已经带来很大的方便，并且为广大研 究者接受。 1 4 模糊集在调度海燕睾豹庭用 m a r i al i t o i u ! 司提剃，模糊集在调度巾豹戏翅裔搿个方越： 1 ) 模型。尽管调度意味精确定住，但在调度中一般存在不确定耐。 模耧集溺寒整理互雩孛蠢馨模裁约寨条姊，模糊魏王对越，模糖交赞期等等。 2 ) 求解确定性模溅。基平模糊逻辑的谶似推骥用来建立专家系统。 m a r i nl i t o i u 6 】在德戆文章串髭模赣数建溺予实辩谡发鞫嚣，撼述熬 一时间和交货期等的不确定性，为了求解模型，引入了调度的满意水平 稼必癸瓣添数寒簸毽工律翡攒赣交赞裳饔模耧燕王鼹溪，劳提出了寻我 最好优先权分配的算法。 t a d a h i k om u r a t ae t e 淄讨论了滚永车霾瓣繁畜搂赣交贷麓懿多套蠢 的调度阀题。禚该篇文章中，作者所讨论的多目标问题怒部分工件考 虑捷蓠，攘鬻惩镶，男舔分藩建藏鬻惩弱；律者月三囊形模赣数狂砉搽 彤模糊数分别袭示提前，拖期釉拖期问题的模糊交货期，浆用了一个参数 p 来决定满意永平静隶属函数静形状，彳乍者讨论了模糊交货精闳怒静嚣 东北大学硕士学位论文第一章绪论 个目标函数，最小满意程度最大化和总加权满意程度最大化，并指出最 小满意程度最大化问题存在的问题及其解决的方法。 i s h i ie t a l i s 研究了两个带有模糊交货期的调度问题。该文章中的模 糊交货期采用右梯形模糊数来表示。模糊交货期定义为线性函数表示工 件完成时间的满意水平。其第一个模型是，个工件，2 台机器的开放车间 的调度问题，目标函数是对所有工件的满意程度中的最小值和机器速度 所产生的费用寻找每台机器的最优速度和工件的最优调度。第二个问题 是n 个工件，m 台同构机器的开放车间的调度问题，目标函数是最小化最 大工件拖期。 i s h i b u c h ie ta 1 【9 】讨论了流水车间带有模糊交货期的遗传算法和邻域 搜索算法，模糊调度问题和一般调度问题的关系，指出许多一般诃度闯 题可以用模糊调度的方法重新加以讨论，并且指出最大化总满意程度问 题要比最大化最小满意程度问题复杂得多。i s h i b u c h ie t a l 还讨论了用非 线性函数表示工件完成时间的满意程度，目标函数是最大化最小满意程 度。 h a ne ta l 讨论了一个工件的单机最大延期问题。其中工件带有模糊交 货期并且机器速度是可控的。目标函数是找到一个最优调度和机器加工 工件时的速度使得由于所有工件的完成时间所造成的不满意程度和机器 的速度的费用之和达到最小。用线性函数表示工件完成时间的满意程度。 机器速度的费用定义为电力和，或劳动。并用多项式算法求解。 对于具有模糊交货期的单机调度问题。主要有两个目标函数：一是 最小满意程度最大化问题，即 m a x m i n g c j j j 其中 c ) 表示工件完成时间的满意程度。 另一个是总加权满意程度最大化问题，即在做决策的时候，决策者 需向不同的商家提供产品，根据不同商家酌定货量、付款方式、顾客信 誉等可以把产品即待加工的工件赋以不同的权值为w ，w 2 c 。决策者 的目标是使所有商家的加权满意程度之和最大，即最大化总加权满意程 度。用式子表示为 5 东北大学硕士学位论文第一章绪论 m a x w j # ( c ) j = l ， 在著作排序论【2 7 1 中，讨论了单台机器模糊交货期的排序问题的 两个问题：一是最小满意度最大化的排序问题；另一个是带权总满意度 的最大化问题。对于最小满意度最大化的排序问题引用t a d a 的结果给出 了t a d a 算法，并指出用t a d a 算法所得到的工件的排序是最优排序。同 时，他们也讨论了最大不满意度最小化问题并引用t a n k a 和v l a c h 的结 果，给出了该问题的l a w l a r 算法，他们指出在所有工件的交货期都相同 时，即具有公共交货期时最大不满意度最小化问题是n p 难的，在一般 情况下，该问题是强n p 难的。对于带权总满意度的最大化问题，他们 讨论了特殊情况所有工件的交货期相同、加工时间相同时的求最优解的 分配规则，并指苎：带权总不满意度的最小化问题当所有工件的加工时间 不全相等时是n p 难的。他们还介绍了流水车间的排序问题的i s h i b u c h i 和m u t a t e 的遗传算法。一些研究者指出随着在模糊集理论基础上发展起 来的模糊推理和模糊控制等得到越来越广泛的应用，它们成为信息科学 和系统科学研究的热点，模糊排序是值得引起关注的一种新型排序。 6 东北大学硕士学位论文第二章带有模糊交货期的单机调度问题的数学模型 第二章带有模糊交货期的单机调度问题 的数学模型 本章讨论了带有模糊交货期的单机调度的数学模型，用右梯形模糊 数来表示模糊交货期，讨论了拖期惩罚和加权满意程度之间的关系。 2 1 单机调度模型 单机调度问题是调度问题中相对简单的一类调度问题，并且有很大 的实际意义，如在一个大的系统中存在一台瓶颈机，它的运行情况直援 影响到整个系统的运行，从而可以把该系统看作是1 个单机调度问题， 使问题得到简化，减小了问题的复杂性。 一般的单机调度问题是指：n 个工件 ，以，j 。要在一台机器上加 工，工件之间不具有优先关系，在开始阶段所有的工件都可以加工，并 且工件一旦被加工，不允许中断，工件的加工时间依次为p ，p 2 ，n ， 交货期依次为d l , d 2 ，以，权值依次为w i ，w 2 ，w n ，完成时间为 c 。，c ：，c 。，机器每次只能加工一个工件。 对于非模糊调度问题，如果工件的完成时间小于或等于工件的交货 期，就认为决策者满意，就说满意程度是1 ，如果发生拖期，就不满意， 满意程度是0 。 这时我们可以定义满意程度的隶属函数来表示： ， f 1 ，c d 髟户1 0 c d 但是，在实际问题中，有许多时候并不是这样，在未发生拖期时， 用满意程度是1 表示满意，当发生拖期时，随着完成时间的延长，满意 程度逐渐下降，直至最后满意程度为0 。即是所谓的模糊交货期问题。 为了与这个实际情况相符合，我们引进模糊集。 我们用模糊集来定义工件完成时间的满意程度的隶属函数，或称为 满意程度，或称为满意水平，图形如2 1 所示 7 东北大学硕士学位论文第二章带有模糊交货期的单机调度问题的数学模型 1 图2 1 右梯形模糊数 f i g 2 1r i g h tt r a p e z o i d a lf u z z yn u m b e r 图2 1 所示的模糊数是右梯形模糊数( t - n u m b e r s ) ，这个模糊数最早 由z i m m e r m a n n 2 2 1 给出定义，记为0 ，j + e ) ，这里d 称为满意交货期，d + e 称为乐观交货期 2 5 1 ，完成时间的满意程度的函数表达式为： 五= 乒( c ) = l ，c d p 0 c d d c s d + e d + p 0 ，所以定理成立。 3 ) 对于第五种情况，此时有第i 个工件的开始加工时问f 满足 以o ) 一p 。o ) 一p 。c ，) t d o ( 0 一办o ) 一儿，隐含着以“) - d o ( 0 ，此时式( 1 ) 左端 项小于0 ，( 1 ) 不成立，所以工件盯o ) 在盯( f ) 之前而从表中也可以直接 得到a 。 0 ，所以定理成立。 4 ) 对于第六种情况，此时工件盯c ，) 无论是否与工件盯( f ) 交换都发生 拖期，工件盯o ) 不发生拖期，即有第f 个工件的开始加工时间，满足 t d 一( 一) 一p 。( 一) 一p 一“) 且d 。( j ) 一p 口 t 这时定理中的( 3 1 ) 式的左端 。，wo。)。if，一!垡l必=赢(r+办。，+po,-ao(o)(opp o o ) o ，即( 3 1 ) 式不成立，ip a o )je a o ) p o “ 此时，f ：一堑p 。) o ，所以工件仃( ，) 在盯o ) 之前； 所以t 件盯( ，) 在仃( f ) 之前；从而定理成立。 5 ) 对于第七种情况，此时有第f 个工件的开始加工时间r 满足 m a x p o o ) 一p ，o ) 一p ，“) ，d o 一p 。( i ) 一p ，( j ) 蔓f m i n d ，( 。) 一p 。( i ) ，d o ( j ) - p ，) j 此时( 4 ) 式 ，= 等( f + p c ( o + p o o ) - d 一( o ) 一等h 也旷，) 由定理条件，若( 1 ) 成立，即 坠f 1 一虹型竺丛 上址f l 一虹匹尘进1 可得 p 一( f ) p 一( ，) i p o )j8 a “) p 一“) l p o ) 等h 矿m 咄，) 等( ，一圳j ) 所以a 。0 ，从而工件口( f ) 应在盯o ) 之前，定理成立；反之，若( 1 ) 不成立， 同理可得a 。0 ，所以工件盯( ，) 在盯( f ) 之前，定理仍然成立。 6 1 对于第八种情况。此时有第f 个工件的开始加t 时间f 满足 m a x d ，o ) 一p ，( ，) 一p ，【，) ，d o o ) 一p o ( i ) 一p 。( ，) ，且， d o o ) 一p 。， 则 铲等h 咖啊) 一等， 这时定理中( 1 ) 的条件 监一f 1 一虹正兰丛 上址f l 一亟症卫丛 p 一( 一) p 口o ) 【p 一( j )je o o ) p “j ) l p 。“) j 变为 东北大学硕士学位论文第三章单机模糊调度的统治规则 旦f 1 一鳋三幽 # 一o ) 儿( f ) l 岛 k “) e a “) 几f ， 即 等h ，吨，) 哿， 所以。0 ，从而工件盯( f ) 应在盯( ，) 之前，定理成立。 7 ) 对于第十一种情况，此时工件盯( f ) 无论是否与工件仃【，) 交换都发 生拖期，工件盯o ) 不发生拖期，即有第f 个工件的开始加q - 时间f 满足 t 以( ，) 一p ，( ，) 一p 。( j ) 且d 。( 。) 一p 。( ，) o e ，( 。) p 。( 。) i p o )je 一( o p a ( t ) 而右端 蒜 t 一掣p _ 嚣( f + p 州吨) ) o 。 。 p ，f f ) 所以工件盯( ) 在盯c ，) 之前；所以工件d o ) 在盯c ，) 之前；从而定理成立。 8 ) 对于第十五种情况，第f 个工件的开始加工时间f 满足 m a ) 【 d ，o ) 一p 。( 。) ，d ，( ) 一p ，( ，) 一p 。“) ) t d ：“) 一p 。o ) 此时，当( 3 1 ) 成立时 一塑l f l 一虹业 上址f l 一虹卫兰进 e ，( ，) p ，( j ) l p 一“)j 。a ( ，) p a ( j ) ip o )j 1 4 东北大学硕士学位论文第三章单机模糊调度的统治规则 所以有 等等g 嘲。+ 胁一) 而 岛2 老e 锄+ 确一) 岽( f 咖嘞) 嵩9 蝴锄一) 即 岛2 等黝老。咖+ 胁一) 所以a g 0 所以工件盯( f ) 在盯( ，) 之前：当定理的条件( 3 1 ) 不成立时，钆o ， 1 - 件盯c ，) 在工件盯o ) 之前；所以定理成立。 9 ) 对于第十六种情况，此时第f 个t 件的开始加工对嗣r 满足 m a x d ，o ) 一p ，o ) ，d ，“) 一凡“) ) ! ，l p t p i e j p j 由于e ，= e j ；e ，所以导兰，从而，p o ， p p ， 所以，推论1 成立。 推论2 ：如果存在一个所有工件的满意程度都小于1 的最优调度， 则按2 l 的非增顺序捧列工件，可得到这样的最优调度。 p i e i 证明：反复应用推论l ，即可得到推论2 。 推论3 ：如果有一个工件的加工时间p ，满足d 。s p ，s d ，+ e 且具有最 大的l 值，则至少有一个最优调度使该工件捧在第一个位置。 p | e i 证明：假设工件盯( 七) 具有上述性质。用反证法，假设所有的最优调 度都没有把工件盯( 七) 排在第一个位置，考虑这些最优调度中盯( 七) 位置在 最前面的最优调度，不妨设为盯。设盯中在盯o ) 之前的工件为口o ) 。 若工件盯o ) 的满意程度小于1 ，则由推论2 和假设可知必有 塑：兰d l ，这时交换仃( f ) 和叮 ) 的位置，设得到的工件次序为氏， p a 0 ) p ，0 )p 一耻) p f t ) 则民和盯有相同的总加权满意程度，证明如下： 这时 1 6 东北大学硕士学位论文 第三章单机模糊调度的统治规则 色2 等( f 嘲旷咄”) 嵩。嘲”+ 蛳一) 嵩。撬嘞) 一等( f + 枷嗍”一) 即 2 等啪嵩脚 由于 鉴地：羔垡2 e ，o ) p 一( i )p 。恤) p ，恤) 所以a 。= 0 ，所以工件次序为最优调度，且盯g ) 在盯( f ) 之前，这与 盯 ) 排在最前面的假设矛盾a 若工件盯( f ) 的满意程度为1 ，即有t + p ，o ) 以o ) 考虑交换仃( 七) 和盯( f ) ， 则交换后仃( f ) 的满意程度必小于1 ，否则，与盯是最优调度矛盾，仍设得 到的t 件次序为o o 。这时 2 等( f 一) 嵩f + 啪一) 岽( f + 蛳咖一) 即 气2 等( f 蝴蝴一) 专蛳 由于 羔盟s 鉴垡! ， 8 口( f ) p 一( r )e 一“) 儿( ) 所以 又由于 等肌，一等岍0 ， 掣( r + p 刑一以( j ) ) o e 口( r ) 。 所以a ms o ，由于盯是最优调度，所以口= o ，从而，c r o 也是最优调 东北大学硕士学位论文第三章单机模糊调度的统治规则 度，且盯 ) 在盯( f ) 之前，这与盯q ) 排在最前面的假设相矛盾。 所以，推论3 成立。 定理3 2 如果4 = d ，p = p ( f = 1 , 2 棚) ，当相邻两个工件盯( f ) 和 盯o ) u = f + 1 ) 满足( f + 1 ) p w _ l ，与定理l 的证明过程 1 e l e i 相似，仅仅考虑交换第i 个和第_ ，个位置工件，此时，对序列中其他工件 的完成时间没有影响，所以，交换前后的工件次序的好与坏，完全取决 于( 3 4 ) 式中的。是大于0 还是小于0 。由于工件的加工时间与交货期都 是相同的，所以无论哪个工件在前，第i 个和第，个工件的完成时间都是 相同的，第i 个位置工件的完成时间为咖，第，个位置工件的完成时间 为( i + 1 ) p ，此时在表3 1 中，只有第l 、6 、1 6 三种情况有可能，分别记 为a 1 ，a 2 ，a 3 ，其余情况是不可能的。下面针对于这三种情况分别作 讨论。 在a 1 条件下，显然有( 冲1 ) p d 又分为以 下三种情况： a 2 b 1 ：( f + 1 ) p d + p f ，且( f + 1 ) p d + 勺i a 2 8 2 ：d + e x ( f + 1 ) p d + 勺： a 2 8 3 ：d + 印 d + e j 分别讨论如下： 在a 2 8 1 条件下，两个工件无论怎样的次序，前面的工件的完成时 间都小于满意交货期，而后面的工件的完成时间大于满意交货期并且小 于乐观交货期。这时， 东北大学硕士学位论文第三章单机模糊调度的统治规则 。= w 。+ 1 一盥i ! ：；型 一( 吩+ 坼1 一半 ) ：i 兰一旦l ( ( f + l 扫一d ) 0 l qp 所以，i 在，前优于，在i 前，此时定理成立。 在a 2 8 2 条件下，不满足定理条件，去掉。 在a 2 8 3 条件下，排在前面的工件的完成时间小于满意交货期，工 件，在i 后面时，其完成时间大于乐观交货期，工件i 在_ ，后面时，其完 成时间，小于乐观交货期。这时， ，= w 。+ w j * 0 - ( 一+ 1 一掣 = 詈m + l b d ) 一叶 詈e i - 叶 o 所以，定理成立。 在a 2 8 4 条件下，不满足定理条件，去掉。 在a 3 条件下，有咖 d ，又分为以下四种情况： a 3 8 1 ：i p d + e iai p d + e j ； a 3 8 2 ：d + e j 咖 d + p ，； a 3 8 3 ：d + e ， i p d + e j ；( 不满足定理条件，去掉) a 3 8 4 ：d + e j i p ，且d + e l i p ，( 不满足定理条件，去掉) 其中a 3 8 3 和a 3 8 4 这两种情况不满足定理条件，去掉，只考虑a 3 8 1 和a 3 8 2 两种情况。 在a 3 8 1 条件下，又分为四种情况： a 3 8 1 c 1 ：( f + 1 ) p d + p f ，且( f + 1 ) p d + e j ； a 3 8 1 c 2 ：d + e j ( i + 1 ) p d + e j ，( 不满足定理条件，去掉) 。 在a 3 8 1 c 1 条件下，此时两个工件无论哪个在前，哪个在后，它们 的完成时间都大于满意交货期，小于乐观交货期。这时 1 9 东北大学硕士学位论文第三章单机模糊调度的统治规则 铲( 一一等 + _ ( t 一半m 一等卜i ( - 一半 ：j 兰一兰i p 0 le fe j 所以，定理成立。 在a 3 8 2 条件下，这时，把其中矛盾和不符合定理条件的情况去掉， 只有一种情况：d + e j ( i + 1 ) p d + p j ；此时，工件，无论在哪个位置，其完 成时间都大于乐观交货期，而工件i 无论在哪个位置，其完成时间都大 于满意交货期，小于乐观交货期，所以，应该有f 在，前，定理成立。 综上所述，对于满足定理条件的相邻两个工件，定理是成立的。 说明：定理3 2 中的条件( f + 1 ) p d + q ( f = 1 , 2 ，万一1 ) 是非常重要的， 如果这个条件不满足，则定理就不成立。 举一个例子说明。设有1 5 个工件，p = 1 0 0 。d = 1 0 0 0 ，令f - l l ，j = 1 2 ，