（概率论与数理统计专业论文）几类工件加工时间可变的单机排序问题的讨论.pdf

，。_tj 苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 一本学位论文属 在年一月解密后适用本规定。 非涉密论文叼 论文作者签名： 壹绪薨 日期： 趁2 垒。垒：fl 导师签名：e l 期：竺里 2 ：笙： r 几类工件加工时间可变的单机排序问题的讨论 摘要 摘要 排序问题是一类重要的组合最优化问题。本文包括五个部分。第一章引言介 绍排序问题的一些背景知识。第二章对工件加工时间与开工时间有关的恶化效应 的情形，研究目标函数分别是最大完工时间和总完工时间的单机成组排序问题， 并分别给出了问题1p o ( a + b t ) ，g 丁，sic 衄和1p v ( a + b t ) ，g 丁，si q 的最优解。 第三章讨论同时具有学习和恶化效应的单机排序问题：工件的加工时间是工件开 工时间和工件加工位置的函数：p j 【，l = p j c t ( t ) a 卜1 ，并分别对目标函数是 z c 册，z w j c ，c 岁k 的问题给出了多项式时间算法。第四章讨论工件加 工时间具有学习和恶化效应并且安装时间具有恶化效应的单机排序问题，并给出 r - ! 、1 + 乙研，】 了多项式时间算法；m 牛m - v 时间是露，】= 所( ) q ，吨，安装时间是 p o + 所 s 巾】：o ，s 加】：y r - i 研a ，】，分别对目标函数是z c 眦，q ，g 厶戡，乃) 的排 l - i 序问题给出了多项式时间算法。第五章综述了论文的结果以及提出一些今后研究 工作的展望。 关键词：单机排序；多项式时间算法；学习效应；恶化效应；成组技术；安装时 间 作者：于绪芬 指导教师：闻振卫 a b s t r a c ts o m es i n g l e - m a c h i n es c h e d u l i n gp r o b l e m sw i t hv a r i a b l ep r o c e s s i n gt i m e s ， - _ l _ _ _ _ _ - _ _ - - _ _ l _ - _ _ _ _ _ - _ _ - - - _ - 一- _ 一h - _ _ _ i - _ - _ _ _ _ - _ - - _ _ _ _ - - - _ _ _ _ _ - _ _ _ _ - - _ _ _ _ _ _ _ _ _ - _ - - _ - _ _ - _ _ - - _ _ - _ _ _ _ _ _ _ i 一 s o m e 。1 。：h i n es c h e d u l i n gproblemsomes i n g l e - m a c h i n es c l l e o u l l n gp r o b l e m s w i t hv a r i a b l ep r o c e s s i n gt i me s a b s t r a c t s c h e d u l i n gp r o b l e mi so n eo ft h ei m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s t h i st h e s i sc o n s i s t so ff i v ep a r t s c h a p t e ro n ei n t r o d u c e ss o m eb a c k g r o u n di n f o r m a t i o n o ft h e s c h e d u l i n gp r o b l e m c h a p t e rt w oi n v e s t i g a t e s s e v e r a ls i n g l e - m a c h i n eg r o u p s c h e d u l i n gp r o b l e m sr e s p e c t i v e l ym i n i m i z i n gm a k e s p a na n dt o t a lc o m p l e t i o nt i m ew i t h l i n e a rp r o c e s s i n gt i m e w i t hr e s p e c tt o s t a r t t i m e o p t i m a ls o l u t i o n s o fp r o b l e m s ip o ( a + b t ) ，g t ，sic 眦a n d1p v ( a + b t ) ，g t ，si q a r e g i v e n c h a p t e r t h r e e d i s c u s s e ss i n g l e - m a c h i n es c h e d u l i n gp r o b l e m s 、析t l ll e a r n i n ge f f e c ta n dd e t e r i o r a t i o n t h ej o b p r o c e s s i n gt i m ei s 岛【，】= p j a ( t ) a 1 a n dt h e o b j e c t i v e f u n c t i o ni s z l ，zw ，c j ，gk c h a p t e rf o u r d i s c u s s e ss i n g l e - m a c h i n es c h e d u l i n g p r o b l e m sw i t hl e a r n i n ge f f e c ta n dd e t e r i o r a t i o ni n c l u d i n gd e t e r i o r a t i v es e t u pt i m e sa n d d e r i v e s p o l y n o m i a l - t i m e o p t i m a l s o l u t i o n s t h e j o bp r o c e s s i n g t i m ei s r - i 露，】= 乃( 风+ 研，】 + 研 i = 1 r - i ) q ，d 2 t h es e t u p t i m ei s s 巾】= 0 ，s m l = 7 p 【f 】a a n dt h e i = 1 。b j e c t i v e f u n c t i 。ni s z c 凇，e w , c j ，q k ) i n s u m m a r yo ft h et h e s i s ，a sw e l la sf u t u r ep r o s p e c t sf o rf u r t h e rr e s e a r c hw o r k k e y w o r d s ：s i n g l e m a c h i n es c h e d u l i n g ；p o l y n o m i a lt i m ea l g o r i t h m ；l e a r n i n ge f f e c t ； d e t e r i o r a t i o n ；g r o u pt e c h n o l o g y ；s e t u pt i m e s - 1 1 w r i t t e nb yy ux u f e n s u p e r v i s e db yp r o f w e nz h e n w e i 目录 第一章引言! 1 1 1 排序问题简介1 1 2 论文各部分主要内容4 第二章具有恶化效应的单机成组排序问题：5 21 1 引言及问题的描述5 2 2 问题( 1 ) 的求解6 2 3 问题( 2 ) 的求解：1 0 第三章具有学习和恶化效应的单机排序问题1 3 3 ：1 引言及问题的描述：1 3 3 2 问题1l 珊，】= p j g ( t ) a 卜1i 的求解一1 4 3 3 问题1p j 【，】= p j g ( t ) a 卜1i 吩q 的求解1 5 3 4 i h 题1 p y 【，】= p j g ( t ) a 1 i 厶僦的求解1 7 第四章具有学习和恶化效应并带有安装时间的单机排序问题1 9 4 1 引言及问题的描述1 9 4 2i h - 题1i p 会r 】，s m 】ic m 拭的求解2 2 4 3 问题lip 盒，】，q 【，】i c j 的求解2 3 j = l 4 4 问题1 l 露r 】，s 【，】l k 的求解2 4 4 5 问题1i p 加a j , s y l r l 羔1 = 1 乃印求解。- 2 5 第五章总结与展望2 8 参考文献：2 9 致谢3 2 几类单机上加工时间可变的排序问题的讨论第一章引言 第一章引言 1 1 排序问题简介 排序问题是组合最优化这门学科的一个重要组成部分，有着重要理论意义和 广泛实际背景。排序问题产生的背景最初是机械制造，后来被生产管理、计算机 系统和运输调度等领域广泛应用。如今生产计划调度，信息处理，公用事业管理 等许多方面都要用到排序的理论和方法，同时排序问题与理论计算机科学、离散 数学等学科都存在着紧密的联系。 1 1 1 排序问题 概括地说，排序是利用一些机器( 如设备、计算机等资源) ，在执行某些任务( 如 产品加工、程序运算等) 时，在某些限制条件下( 如工件的到达时间、完工截止时 间、优先约束、资源约束、机器对加工时间的影响等) ，寻找最优加工方式使某个 或某些目标函数达到最优。目标函数通常是对加工时间的长短、处理机的利用率 等的描述。它是“投入最少，产出最优”的一种系统优化过程。由于排序问题最 早是在机器制造领域中提出来的，因而排序问题各要素的描述沿用了机器制造中 的术语。机器( m a c h i n e ) 、工件o o b ) 和目标函数( o b j e c t i v ef u n c t i o n ) 是各种排序问题 的三要素。 1 1 2 排序模型的三参数表示法 c o n w a y 等j k ( 1 9 6 7 ) 1 1 最先提出了排序问题的四参数法表示，后来g r a h a m 等 人( 1 9 7 9 ) 网改用三参数法表示并至今仍在沿用：口i iy ，其中，碱表示机器的数 量、类型和环境；础表示工件的性质、加工要求和限制，资源的种类、数量和 对加工的影响等约束条件；煳表示要优化的目标函数。关于排序问题这三个域的 详细内容可参看【2 】。 1 1 3 排序的类型 排序问题可以分为排序的理论部分和应用部分。其理论部分又可分为经典排 序和现代排序两大类。现代排序的特征突破了经典排序的基本假设，正逐渐成为 1 第一章引言几类工件加工时问可变的单机排序问题的讨论 排序研究的主流方向。经典排序有四个基本特征： ( 1 ) 资源类型( 如加工工件的机器) 冶机器在任何时刻最多只能加工一个 工件，且一个工件在任何时刻至多在一台机器上加工。作为推广，有成组 分批排序、同时加工排序、不同时开工排序和资源受限排序等。 ( 2 ) 确定性决定排序问题实例的所有参数都是事先知道和完全确定的。这 一性质的推广有可控排序、随机排序、模糊排序、在线排序和半在线排序 等。 ( 3 ) 可运算性排序问题通常都是在可以运算和计算的程度上进行的。若考 虑实际应用中的情况和因素，那是属于应用排序问题，如人员排序、智能 排序等。 ( 4 ) 单目标和正则性( 单) 目标函数是工件完工时间的非降函数，即所谓正 则目标函数。这方面的推广有多目标函数、准时排序和窗时排序等。 现代排序是对经典排序的基本特征进行推广而产生的。现代排序的特征是突 破了经典排序的基本假设，并且现代排序正逐渐成为排序研究的主流方向。 一 排序问题还有多种其他分类法。例如，有静态( s t a t i c ) 排序和动态( d y n a m i c ) 排 序的分类；有随机性( s t o c h a s t i c ) 排序和确定性( d e t e r m i n i s t i c ) 排序的分类；又如按 处理机类型和环境分类，有单机( s i n g l em a c h i n e0 1 s i n g l ep r o c e s s o r ) 排序和多机 ( m u l t i p r o c e s s o r ) 排序；多机又进一步可分为平行机( p a r a l l e lm a c h i n e ) 和多类型机 ( d e d i c a t e dm a c h i n e ) ，还有柔性流水作业( f l e x i b l ef l o ws h o p ) 。 多类机指的是m 个处理器具有不同的功能。在多类机环境中，各个工件需要 在不同的处理机上加工。在这种情况下，把工件称为作业( j o b ) 。设有工件集 ，= “，以，以 ，每个作业以有吩道工序巧力，巧d ，巧”，工序是指作业在某处 理机上被加工的这部分工作。 如果每个作业都需要在每个处理机上加工( 即n j = m ，j f = 1 ，2 ，刀) ，而且每个 作业的工序的顺序也相同，即每台处理机上工件的加工顺序相同，把这种多类机 的环境称为同顺序作业或流水作业( f l o ws h i p ) 。 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序在机器上加 工，把它称为自由自由或开放作业( o p e ns h i p ) 。 1 1 4 排序问题中本文所使用的符号 下面对排序问题的常用符号作一简单的说明： 2 几类工件加工时间可变的单机排序问题的讨论 第一章引言 j ，一一第，个工件 g 第f 个分组 p ，一一工件，的基本加工时间 d ，工件，的工期或截止期限 s ，一一工件- ，的安装时间 既一一第j 组中的第个工件的基本加工时间 乃【，】表示工件排在第，个位置的加工时间 w j 一一工件j ，的优先因子( 权) c ，一一工件j ，的完工时间 c m 舣_ 时间表长( 最大完工时间) ，即c m 状= m a x g ) 它等于最后一个被加 工完工件的完工时间，小的时间表长意味着机器高的利用效率。 q ，w ，c 广。总完工时间，加权总完工时间。 上m 。广最大延迟，即三m 觚= m a x 与 ，其中与= 0 一弓是工件，的延迟时间。 巧一( 加权) 总误工时间，其中乃= m a x 0 一巧，0 。 1 1 5 排序问题的求解 排序问题是一类重要的组合最优化问题。由于排序问题中处理机和工件( 或 任务) 个数都是有限的，从而排序问题的求解就是从有限多个可行解中找出一个 最优解，使目标函数达到极小。在排序问题中，把可行解称为可行排序( f e a s i b l e s c h e d u l i n g ) ，最优解称为最优排序( o p t i m a ls c h e d u l i n g ) 。求解排序问题的基本思路 是：应用或借鉴求解其它组合优化问题的方法，充分利用排序问题本身的特殊性 质，来找出满足约束条件的最优排序。有些排序问题可直接转化成其它的组合最 优化问题来求解。对于具有多项式时间算法的排序问题，要尽可能地找出空间复 杂性和时间复杂性尽可能好的算法。所谓空间复杂性是指算法所占存储的多少， 时间复杂性指的是计算时间的长短，它们都是问题输入规模的函数。 对于一个排序问题，首先要用复杂性理论对它进行分析，看它是属于pf 司题 还是n p 难问题。以便知道求解此问题的难度。若它是p 问题，则求解此类问题 就是寻找计算量尽可能小的多项式时间算法；若它是n p 难问题，则大致有两种 基本方法：一是用分枝定界法、动态规划法等巧妙的枚举来求出它的最优排序。 这类算法计算量大，只能对规模较小的问题才可实施；另一种方法是求出它的近 第一章引言几类工件加工时间可变的单机排序问题的讨论 似最优排序，各种局部搜索法和启发式算法，分析误差是使用这类方法不可缺少 的工作，也是最困难的工作。这类算法计算量小，并能满足一定的实际需要。对 于尚不知是否存在多项式时间算法的排序问题，也可以用启发式算法得到近似最 优排序或针对它的一些特殊情形设计最优算法。 1 2 论文各部分主要内容介绍 第二章对工件加工时间与开工时间有关的恶化效应的情形，研究了目标函数 分别是最大完工时间与总完工时间的成组排序问题。各组间存在安装时间s ，并 且每个s 是一个大于零的固定常数，扛1 ，2 ，m 。工件加工时间具有和开工时间 t 有关的恶化效应。文中分别给出了求问题1p o ( a + b t ) ，g t ，si 和 1 p o ( a + b t ) ，g r ，sl q 最优解的多项式算法。 第三章讨论了同时具有学习和恶化效应的单机排序问题。工件的实际加工时 间是工件开工时间和工件加工位置的函数：马f ，】= p j a ( t ) c t 卜1 ，其中恶化因子口o ) 为凸的非减函数( 口( f ) 0 ) 。文中给出了目标函数分别是最大完工时间，加权总 完工时间，最大延迟问题的多项式算法。 第四章研究了工件加工时间同时具有学习和恶化效应并带有恶化安装时间的 1 1 岛+ 己研，】 单机排序问题。工件实际加工时间具有形式力，】= 乃卜 ) 口1 ，吩，其中 p n + 乙p l 口， 0 ，口： 0 为恶化因子和学习因子，表示工件，在排序中的位置，安装时间 、 r 一1 是s 巾】= 0 ，s m l = 7 p 【1 a ，其中o 0 ，匆 0 ，并得出了最大完工时间的最有算法。赵传立【lo 】等还研究了更为复杂 的非线性加工时间恶化排序问题，1l 马+ a j f ( t ) l q ，1ip j + a j f ( t ) ik ，其中 第二章具有恶化效应的单机成组排序问题几类工件加工时间可变的单机排序问题的讨论 f ( t ) 是单调增加非线性函数。赵传立【1 1 】等人对具有恶化效应的模型 p j = p n ( a + b t ) ，目标为最大完工时间，总完工时间和最大延迟的单机排序问题 给出了多项式时间算法。 本文在文 1 1 】的基础上考虑增加了成组条件的模型，对于组间存在安装时间 的单机排序问题，证明了问题1ip o ( a + b t ) ，g 丁，siq 雒和1 p u ( a + b t ) ，g r ，si q 是多项式可解的，同时给出了多项式算法。 问题的描述，假定，有力个工件要在一台机器上加工；机器一次只能加工一 个工件，且工件的加工不可中断；所有工件均( 在时刻o ) 已就绪，但第一个加 工的工件必须在时刻t o ( t o o ) 开工；刀个工件分别属于m 组g l ，g 2 ，g 埘，第f 组 g ，包含胁个工件：以l ，以2 ，厶( 刀= 啊+ + ) ；同组的工件必须放在起接连 加工，组内工件间无空闲时间；每组前存在一个安装时间墨，其中墨是个大于 零的固定常数，江1 ，2 ，所。工件加工时间具有和开工时间，有关的恶化效应。 第g 组中的工件厶的实际加工时间为p v ( a + b t ) ，f 一是工件无的开工时间， 口 0 ，b 0 ，p u 是给定常数( p v 叫做工件的基本加工时间) ，扛l ，2 ，朋， _ ，= 1 ，2 。目标函数分别为极小化最大完工时间和总完工时间。用三参数表示 法将问题记为： l l p # ( a + b t ) ，g t ，si ( 1 ) 1 慨( 口+ 吣g t ，s ii q ( 2 ) 2 2 问题( 1 ) 的求解 引理2 1 川对于问题1l 马( 口+ 所) i c 懈，最大完工时间与工件加工顺序无关，并 且，如果第一个工件的开工时间是t o ，则最大完工时间为： c 腿心i 以，以，以) = 乇+ + 纸) 6 扣1 q ，b ) k = l 其中( 马，见) 表示在a ，见中选取所有可能的k 个元的乘积再将他们相加 几类工件加工时间可变的单机排序问题的讨论 第二章具有恶化效应的单机成组排序问题 - - _ _ _ _ _ _ _ _ _ _ _ - _ - _ - _ _ _ _ _ _ _ _ - _ 一_ - - _ - _ _ _ _ _ - _ - _ _ _ _ - - - _ _ _ _ _ _ _ _ _ - - _ 一 得到的和值。 证明：见文献【1 1 】定理1 。 ： 定理2 1对于最大完工时间问题1ip o ( a + b t ) ，g t ，slc 傩，存在一个最优排序， 满足： ( 1 ) 组内工件任意排列； ( 2 ) 工件组之间按照s f 递增排序。其中c 伪k ( 易 ，) 意义与引理2 1 相同。 证明：假设在某排序万= ( 以。，以：，以川；以，以也；厶) 中，组g f 的开 工时间是f ，则由引理2 1 可知，组g f 的完工时间是： 撸 - c 觑= f + + 所) 胪_ 1 1 ，) ，即与组内工件顺序无关。 k = l 假定在万中，组g 排在组g ，的紧前面，即两组相邻有 上三l 一 吩 七 卿1 c ：也。”，取) + 吩 k = ll = l 假设r 是万中工件组g j 的开始时间，我们交换组q 与q 的顺序，其余各组相对位 置保持不变，得到万= ( ，q ，q ，) ，则有： 在万中组q 和组q 的第七个工件的完工时间分别为： 七 ，= 吒+ 墨+ 【口+ 6 ( + s ) 6 - 1 c i ( p , 歌) = l 而在万中组q 和组g ，的第七个工件的完工时间分别是： 、- 、 岛 ，i q 卜 6 七闰 吩 + s - - - d+口+ 墨 +f = q 膳 p p pq 一 护 七蚓 d + 0 6+口+ +f = 几类工件加工时间可变的单机排序问题的讨论第二章具有恶化效应的单机成组排序问题 q 。+ 墨+ 【口+ 乡( + s ) 善6 卜1 0 l ( p n ，既) 于是： 一打，n ， c 珐+ c p 一c = 刀，( f + s f ) + 【口+ b ( s ， 【口+ b ( c ，嘶+ 【口+ = ( ，2 ，一刀) f + n s c j 。， 七 i ；1 ， ，七 c 让 k ，。1 b 1 - 1 c ：( p ，l ，p 膻) + 刀j ( c 帆+ s j ) + bj - 1 c ：( p 1 ，p 业) 一刀( f + s j ) 一 b l - l c ：( p b t - l c ：( p n ，p 膻) ，p j k ) 一咒，( c 。 ，= 1 = 仁+ 陋+ 哆+ r 粥喜q 慨，) ) 6 善n l = s ：+ 陋+ 觚+ f ) 】q ，) l6 l t=l川一t=1 ，p 膻) + s f ) b l - l c ：( p 儿，p 雎) 一 p 小蝇卅，耖锄，叫障b e s + + 扶s + f ) 】6 扣1 c 乏魄，如) i i 扫li li = l 厂 = 1 6 lk = l，砂乃峙 o t - j c ：( p ，p j k ) 一 671c：c乃，z，k，r，!， 6 - 棚 州础吩 s + 陋+ 6 ( s 这与排序万是最优的矛盾，即引理得证。 l l 6 ，。1 c ：慨l ，p j , ) + n j 卜 一 一 几 1 j、， f+ 1 _ j、， s 。 1 j、， f+s ，- ， 6+口 -_。l n p，- ， ，七 c 卜 6 。m 心 s+ 加 c ，一， 6 r6+ ， ， p c ， 聆一 f6 嘶 ， ， p c6 瑚 闰 闭闰 h 跏 ” 竹 嗡 如 。厶心 、， 闰蹦 6 第二章具有恶化效应的单机成组排序问题 几类工件加工时间可变的单机排序问题的讨论 弓! 理2 3 】。对于问题1i 乃 + b t ) ie c ，工件按乡彳+ 印，) 非减顺序排列可得 最优序。 证明：由参考文献【1 1 】中定理2 的结论容易得到。 定理2 2 对于带安装时间的成组问题1i 岛 + 厨) ，g t , s ，i c ：，存在最优排序满 足： ct ，组内工件按孑+ 助驴) 非减顺序排列； ( 2 ) 工件组之间按 嘶 墨“口+ b ( s i + f ) b k - l c 。k ( p n ，p 砚) 】 一排列。 证明：由引理2 2 和2 3 可直接得到结论，结论证得。 非减顺序 聆+ 髓pp，i f 七 c 卜 6 七埘嘶心 6 几类工件加工时间可变的单机排序问题的讨论第三章同时具有学习和恶化效应的单机排序问题 第三章同时具有学习和恶化效应的单机排序问题 3 1 引言及问题的描述 在经典排序理论中，工件的实际加工时间没有考虑与工件的加工位置的关系。 然而，在许多的实践过程中，如在加工车间里工人连续加工相同或类似工件时， 被加工的工件越往后处理所需时间越少，这种现象称之为具有( 与位置有关的) 学习效应。w r i g h t t l 2 】首次把学习效应的概念引入到排序理论中来。学习效应理论虽 然早在7 0 年前就被应用于生产实践，但应用于排序问题的研究还是近些年提出 来。b i s k u p 1 3 】第一次把学习效应引入到排序机器环境，即工件越往后加工其加工 所需时间越小。他提出的工件加工模型为p j r = p j r 口，其中p j ，口o 分别为 工件- 厂，的正常加工时间，实际加工的位置和所具有的学习效应因子。在单机条件 下，他研究了目标函数为极小化完工时间之和的问题，得到了工件按s p t 规则所 0 获得的序为最优序类似文献参见【1 4 】和【1 5 】等。程明宝【1 6 】研究了另一个具有学习 效应流水作业排序模型，p 扣= p ，口1 ，0 口1 。恶化效应概念第二章引言中已经 介绍过。后来l e e 【l 刀研究了同时带有学习和恶化效应的单机排序问题：工件，的实 际加工时间分别是乃【，】= 吩护口和所【，】= ( 风+ a j t ) r 4 ，1 7 1 0 ，t 0 ，其中，是工件 巧所排的位置，目标函数分别是最大时间表长，总加权完工时间和最大延迟，并得 到了多项式算法。从那以后，人们对同时具有学习和恶化效应的排序问题产生兴 趣。学习与恶化效应在当今管理科学的许多领域都有应用，在文献中也已经进行 了大量广泛的研究。w a n ga n dc h e n g d s 对加工时间是p 舯1 = ( p + 口，f ) ，4 的单机排序 问题做了一系列研究。w a n g 和c h e n g d 9 , 2 0 硼：究了在具有学习效应与恶化效应的单 机和流水机环境下有关时间表长，总加权完工时间和最大延迟问题并给出了多项 式解法。w r i n g 2 1 】给出了实际加工时间为p 【，1 = p ，( 口( f ) + ，口) 时目标函数为总完工 时间和总完工时间平方和的解法。x u eh u a n g 2 2 】等给出了实际加工时间为 丝 p j 【r 】= p j ( 1 + 研】) 口口卜1 时最大完工时间，总加权完工时间，最大延迟问题的最 优排序算法。本章考虑了单机排序模型p j = p j g ( t ) a 卜1 ( = 1 ，2 ，刀) 。 第三章同时具有学习和恶化效应的单机排序问题几类工件加工时间可变的单机排序问题的讨论 问题的描述，设有刀个工件以，以，以需要在同一台机器上加工；每个工件 均在在时刻0 已就绪；若工件的排在位置厂且开工时间是f ，那么工件的实 际加工时间为乃【，】= p j g ( t ) a 卜1 ( _ ，= l ，2 ，刀) ，其中g ( ，) 为恶化因子并且g ( f ) 是 r 的非负非减凸函数，口( 0 ，1 ) 为学习因子。用三参数法本章讨论的问题表示为： lf 乃f ，】= p j g ( t ) a 卜1if ，厂 c m 缸，吩q ，g ，k 。 我们先给出一个引理。 引理3 1 设g ( x ) 是一个可微的凸函数，且o 五 而 恐，则存在卣，乞，使 g ( x 2 ) 一g ( x 1 ) = 9 7 ( 缶) ( 恐一而) ( x a 当 恐) ， g ( 玛) 一g ( 五) = 9 7 ( 岛) ( 玛一)( 五 磊 毛) ， g ( 磊) sg ( 乞) 。 证明：由l a g r a n g e 中值定理易知，存在卣( 五 螽 恐) ，彘( 西 受 毛) ，使得 g ( 屯) 一g ( x a ) = 9 7 ( 磊) ( 恐一西) ，g ( x 3 ) 一g ( ) = g ( 彘) ( 墨一而) ， 对于五 屯 乃；设万中工件z 在时刻岛开始加工。则有： e ( 刀) = t o + p , g ( t o ) a 卜1 c _ ，( r c ) = t o + p , g ( t o ) a ：- 1 + 易g ( f o + 露甙f o ) 矿1 ) 几类工件加工时问可变的单机排序问题的讨论 第三章同时具有学习和恶化效应的单机排序问题 交换工件以和得到一个新排序万，在万中： c ，( ) = t o + p j a ( t o ) a h c ( 万7 ) = t o + p j a ( t o ) a 卜1 + p , a ( t o + p j a ( t o ) a “1 于是： q 一弓伪= 心+ 乃酏) 十辟酏也酏) 矽】一 阮+ 露酏矿+ 易酏+ b 酏矽】 = 眩砒磁碱+ 露砒矽】+ 瞻酏+ b 酏矽噌砒) 】 = 哆酏+ 乃酏矽一辟酏矽一马酏+ 露酏矽 + 瞻酏+ 马酏矽一露酏矽+ 尼酏) 一露酏 = p j g ( t o ) ( d - 1 一) 一露酏x 一) + 眈酏矽一易酏嘲酏) 矽】 + 喃酏+ 只砒矽一忍酏矽】 = g ( 乇x - 1 一) ( 毋一层) + 乃饿) ( _ 纪g ( 乞) c ) + p 盛毫佘p t 窘迫d 岫 = g ( t o x d - 一) ( 乃一忍) - i ? 鹏c 尹。1 瓶必螽) 一默色) 】 其中o 卣 乃，0 参 p j ，由引理3 1 可知，g ( 当) g ( 彘) ，又0 p j 及加工时间与权重一致性易知觑 乃，又由o 乃， 分别排在第，- 和r + 1 个位置，并设工件，在时刻岛开始加工。 那么，g ( 万) = t o + b g ( f o ) 口，_ 1 c j ( 刀- ) = t o + p , g ( t o ) w - 1 + p ，g ( t o + p , g ( t o ) a z - 1 ) 交换i 件以和，得到一个新的排序万，在万中 一( 万) = t o + p j g ( t o ) a 卜1 ：c ：( 万7 ) = 岛+ p s g ( t o ) a 卜1 + p , g ( t o + p 2 9 ( t o ) a 卜1 ) 口7 由n 所得c f ( 万) q ( ) 又由定理1 可知q ( 刀) c j 仞) 故有口( 万) q ( 万) ，g ( 万) 口( 万) 于是万7 比万更优，这与万是最优排序相矛盾。 即按马非减顺序排列可得到问题最优排序。 3 4 问题l b ，】= 马g o ) f 厶眦的求解 定理3 4 对于问题1 i 砌，】= 乃g o ) 一1 l 厶僦，如果工件的加工时间和工期存在一 致性关系，即z 嘭只 嘭。我们交换工件z 和的位置得到一个新排序万，由于易 乃 第三章同时具有学习和登垡鍪窒竺皇垫塑壁塑垦 丛耋三竺垫三堕旦里垄塑兰垫垫壁塑里塑塑丝 - _ - - _ _ - _ - _ _ _ l - 一一一 及定理3 1 的证明过程，得到q ( 刀) c 仞) 。 从而， 厶( ) = c ；( ) 一c j i c ：( 力一巧= 弓( 功厶僦( 力 弓( 力= e ( ) 一哆e ( 力一哆= 弓k ( 万) 对任意七f ，j ，显然有厶( ) 厶仞) 厶姒( 万) 故k ( 力k ( 力。定理证毕。 推论3 4 对于问题1 f 乃【，1 = p j g ( t ) a 7 一，乃= p i k 就，按工件的工期乃非减顺序 排列可以得到最优排序( 即e d d 规则) 。 推论3 5 对于问题1 l 乃【，】= 乃g ( f ) 口川，乃= d i k ，按工件的工期乃非减顺序 排列可以得到最优排序( 即即r 规则) 。 推论3 6 对于问题1 i 乃p 1 = p j g ( t ) o t ”1 ，嘭= 慨l k ，按工件的工期乃非减顺序 排列可以得到最优排序( 即e d d 规则) 。 几类工件加工时间可变的单机排序问题的讨论 第四苹加工具有学习的单机排序问题 第四章加工具有学习与恶化效应且安装 具有恶化效应的单机排序问题 4 1 引言及问题的描述 学习与恶化效应相关的概念在本文第二、三章中已经详细的介绍过。第二类 加工时间恶化问题是由于工件在加工顺序中的延后而使得加工时间恶化的排序问 题。近几年来对于工件实际加工时间不仅与工件加工位置有关并且还于已完工工 件的基本加工时间有关的排序问题的模型也已得到很多人的关注与研究。x u e r - 1 h u a n g 2 3 1 等人研究了工件实际加工时间为：砌，】= 乃( 1 + p c ，1 ) 4 口1 的单机排序模 i - ! 型，其中a l ，o _ l ，a 2 o ，分别给出了目标函数是最大 i = 1i = 1 时间表长，总加权完工时间和最大延迟时的多项式时间算法。c h i n c h i aw u 【2 6 1 类似的研究了工件实际加工时间为p j , = p j i1+研，】研，】l，啦，alo，a2 0 q o 哆 o 给出了目 标函数的多项式时间算法。在有些加工问题中，每个工件加工时需要一定的安装 时间。文献【2 8 】讨论亍安装时间为常数情况下的排序问题，并得到了的多项式算 第四章加工具有学习的单机排序问题 几类工件加工时间可变的单机排序问题的讨论 ? 法。对于安装时间与已完工工件的加工时间有关的情形，文献 2 9 1 对问题给出了 多项式算法。这些排序问题的新模型主要存在于高科技的制造业中，并且由大量 的工件组成的一批电子工件，当这组工件被安装到集成电路板上时，他们只能被 机器连续力n q - - 。当机器加工任何一个这样的工件时，就会对其他已就绪但未加工 的工件产生不利的影响，其原因是当电流流过集成电路板时，机器也在工作。在 机器加工一个新的工件之前，需要进行一个调整操作，即安装时间；集成电路板 上的所有工件被机器加工完时，则完成了整个制造过程。这种模型更具有实际意 义。t c e c h e n g t 3 0 】等人研究了带有恶化效应安装时间的排序模型 厂 ，一1 、a i 1i 乃【，】= p jl 1 + l o g p t ，】l ，啦，l 厂，厂 c 懈，q ，q ，乙，乃 ，其中 i = i 一， s 刎表示加i i 件带有安装时间，并得出了目标函数的多项式时间算法。本章在 文献 2 7 】研究的模型的基础上增加了工件带有恶化效益安装时间的情形，讨论了 如下模型1 ip m a1 ，s j i ，】if ；f ，e c j ，q 厶“，e r , 。 设有n 个工件j l ，j 2 ，j n 需要在同一台机器上加工；每个工件均在在时刻0 已就绪；若工件j ，的排在位置，那么工件，的实际加工时间为 1 1 风+ 乙研阳 霸，1 = 乃( 专卜) q ，如( 歹= 1 2 ，挖) ， p o + 易 r - 1 安装时间为s 朋】= 0 ，s m 】= 7 p 矗】，其中口l 0 ，口2 0 ，0 ， 0 ， ， 几类工件加工时间可变的单机排序问题的讨论 第四章加工具有学习的单机排序问题 其中a 1 0 ，a 2 0 ，0 y 1 ，x o ，厂= 1 ，2 ，聆一1 。 证明：令厂( 功：y + l + q x ( 1 + 功q 生) 色一( 1 + 功q ) 啦 ，一， 则有： 州刮l + 掣户+ q 加埘之学严吲1 t 妒1 掣户 = q “一驭l + 妒2 因为c 6 0 。 ， 结论得证。 e j l 理4 2 饥y + 1 一( 1 + 妒( 盟) 色卜【厂+ 1 一( 1 + 名x ) 唧犁) 色】o ， 其中q 0 ，c 6 0 ，力1 ，石0 ，0 厂 1 ，= l ，2 ，n 一1 。 证明：令甙力：y + 1 一( 1 + 功q 盟) 吨】一陟+ 1 一( 1 + 纠q 二生) 色】 ， ， 则有： g ，( d ：7 + l 一( 1 + 功q 0 1 兰) 啦+ q x ( 1 + 允x ) q c ! 兰) 龟 ， ， g 一( 兄) ：口1 ( q 一1 ) x 2 ( 1 + 允x ) q 一2 ( 坐) 啦 ， 由q 0 ，a 2 0 因此g ( 五) 也是非减函数，则g ( 咒) g ( 1 ) = 0 引理得证。 - 2 l 4 2 问题1p 盒，】，s m 】ic m 联的求解 定理4 1 对于