（概率论与数理统计专业论文）同时带有学习和恶化效应的单机成组排序问题.pdf

同时带有学习和恶化效应的单机成组排序问题中文摘要 中文摘要 本文包括五个部分，第一章引言介绍了排序问题的一些背景知识第二章对加工 时间具有与位置有关的学习效应的情形，分别研究了目标函数是最大完工时间与总完 工时间的成组排序问题，给出了问题l i = 黝协+ ( 1 一a ) r 1 ，c t , s d g 删。，1 咖毛= p 巧陋+ ( 1 一入) ，- o i 】，c t , s = a i 一屈t l ，1 i 砖= 砌队4 - ( 1 一a ) r o 1 ，g 正霹= ( 1 + s 1 1 1 + 鄂l + + 乱一l j ) 6 鼠i q 一和l i p s ，= 肋队+ ( 1 一a ) ，叫】，c t , i c 舀的最优解 第三章讨论了一类工件的加工时间与开工时间成线性关系的单机排序问题，加工时间 具有学习效应且安装时间带有恶化的成组排序问题1 = a q b q t ，s = 况，g t i g ，m 和1 i = 一b t ，s = 6 t ，g t i 第四章讨论了具有恶化加工时间，工件间存在 树型优先约束的单机排序问题l 胁= a i t j ，o u t t r e ei 哟q 第五章综述了论文的结 果，并给出了一些展望 关键词t 成组技术；学习效应；单机；树约束；恶化 作者杨士梅 指导老师：闻振卫( 副教授) 同时带有学习和恶化效应的单机成组排序问题 英文摘要 s i n g l e - - m a c h i n eg r o u ps c h e d u l i n gp r o b l e m sw i t h l e a r n i n ga n dd e t e r i o r a t i o ne f f e c t a b s t r a c t 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 c h a p t e rt w oi n v e s t i g a t e ss e v e r a ls i n g l e - m a c h i n e 矛o u ps c h e d u l i n gp r o b - l e m sm 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 hp o s i t i o n - d e p e n d e n tl e a r n - i n ge f f e c t o p t i m a ls o l u t i o n so fp r o b l e m sl = 砌 a + ( 1 一a ) r q l ，g t , s il ， 1 i = p o a + ( 1 一a ) r 4 】，g t , s i = 啦一屈i ，1 l 砖= 肋协+ ( 1 一入) r 。】，c t , s ：，= ( 1 + 岛l l + 叠2 l + + 唧一1 1 ) 6 最i a n d1 = 协+ ( 1 一a ) r 4 】，y g t , l a r e g i v e n c h a p t e rt h r e ed i s c u s s e ss i n g l e - m a c h i n ep r o b l e m sw i t hl 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 os t a r tt i m e g r o u ps c h e d u l i n gp 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 n ：1 p o = 叼一b t ，s = 五t ，y g t f g 眦a n d1 p i j = 叼一b t ，s = 6 t ，g t i a r ed i s c u s s e d c h a p t e rf o u rd i s c u s s e ss c h e d u l i n gp r o b l e mw i t ho u t t r e e - s t r u c t u r e da n d d e t e r i o r a t i o ne f f e c t ：ll p i ( a + ) ，o u t t r e ei 嘶岛i nc h a p t e rf i v e ，yw es u m m a r i z e t h er e s u l t so ft h et h e s i sa n dp r o p o s es o m en e w p r o b l e m s k e y w o r d s ：g r o u pt e c h n o l o g y ；l e a r n i n g - e f f e c t ；s i n g l e - m a c h i n e ；t r e e - r e s t r i c t e d ； w r i t t e nb yy a n gs h i m e i s u p e r v i s e db yp r o f w e nz h e n w e i i i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：扬趁e t 期：丝丝：垒占 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文本人电子文档的内容和纸质论文的内容相一致除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：拉梅e 1 期：乏凄垒： 导师签名雄日期：业 同时带有学习和恶化效应的单机成组排序问题第一章 第一章引言 5 1 1排序问题简介 排序( s c h e d u l i n g ) 问题产生的背景是机械制造，后来被生产管理、计算机系统和 运输调度等领域广泛应用从普通生产部门的计划安排、人员调度、学校课程表的制 订，到宇宙飞船复杂庞大的飞行计划，都要用到排序的理论和方法 1 1 1 排序问题的定义 排序问题是一类重要的组合优化问题，它是利用一些处理机( p r o c e s s o r ) ，机器( m & - c h i n e ) 、或资源( r e s o u r c e ) ，最优的完成给定任务( t a s k ) 或工件( j o b ) 的加工执行任 务时需要满足某些限制条件，如工件的就绪时间，完工的限定时间，任务的加工限定 顺序( 如出树等) 、资源对加工时间影响等最优的完成是指使得目标函数达到最小， 目标函数通常是对加工时间的长短、处理机的利用率等的描述 1 1 2 排序问题的分类 排序问题按处理机数量的不同。可以分为； 单处理机问题 多处理机问题；多处理机问题又进一步可分为以下几类问题； 同类机( 平行机) 问题( 包括同速机和异速机) 多类机( 车间作业) 问题 柔性流水作业问题 多类机指的是m 个处理器具有不同的功能在多类机环境中，各个工件需要在不同 的处理机上加工在这种情况下，把工件称为作业( j o b ) 设有工件集j = 以，无，厶) 每个作业乃有吩道工序( o p e r a t i o n ) 砰) ，才，硝) ，工序指的是作业在某处理机 上被加工的这部分工作 1 同时带有学习和恶化效应的单机成组排序问题 第一章 如果每个作业都需要在每个处理机上加工( 即码= m ，歹= 1 ，2 ，n ) 而且每 个作业的工序的顺序也相同，即每台处理机上工件的加工顺序相同，把这种多类机的 环境称为同顺序作业或流水作业( f l o ws h o p ) 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序在机器上a n - r ， 把它称为自由自由或开放作业( o p e ns h o p ) 1 1 3 排序问题中本文所使用的符号 下面对排序问题的常用符号作一简单的说明： 也一一第歹个工件 功一一工件乃的基本j j - r 时间 岛一一工件乃的安装时间 p q 一一第i 组中的第j f 个工件的基本加工时间 嘶- - - - - i = _ 件乃的优先因子( 权) 岛一一工件乃的完工时间 g 棚。一一最大完工时间或时间表长 c h a i n s 一一链 o u t t r e e 一一出树 1 1 4 排序问题的最优准则 设工件 ，j 2 ，厶对应的权分别为w l ，耽，完工时间分别为q ，岛， ，c k ，常用的准则有： 使最大完工时间达到最小，即：求 r a i nm a x x j n ( q ) 使每个工件的完工时间的加权和达到最小，即；求 r a i n l 屿q 1 1 5 排序问题的三参数表示 1 9 6 7 年c o n w a y 等首先提出用四参数来表示排序问题1 9 7 9 年g r a h a m ，l a w l e r ， 2 同时带有学习和恶化效应的单机成组排序问胚 第一章 l e n s t r a 和r i o n n o o yk a n 等提出改用三参数三参数记号由三个域组成： 口吲，y 它 们具有下面的含义 a 域表示处理机的数量、类型、环境，它可以为 h 单处理机 p m ：m 个同速机 q m ：m 个恒速机 忌；：m 个变速机 日。：m 个处理机，流水作业 0 m ：m 个处理机，自由作业 厶：m 个处理机异顺序作业 p 域表示任务的性质、加工要求和限制可能的项主要有 巧：任务的到达时间 p r m p ：加工可中断 p r e c ，c h a i n ，i n t r e e ，o u t t r e e ：分别表示一般有序约束，链约束，入树和出树 b r k d w n ：机器故障( b r e a k d o w n s ) 表示机器不能连续被使用 任何约束条件的项都可以出现在p 域中，同时可以出现多项若出现两项或两项 以上，两项之间要用逗号隔开另有一些项比较复杂，在有关章节使用它们时再作解 释 ，y 域表示要优化的目标函数，它可以是 q ：时间表长 岛，嘶岛：总完工时间，加权总完工时间 l ：最大延误 功，屿岛：总误工，加权总误工 ，屿：误工任务数，加权误工任务数 1 1 6 排序问题的求解 排序问题是一类重要的组合优化问题由于排序问题中的处理机、任务或工件都 3 同时带有学习和恶化效应的单机成组排序问题第一章 是有限的，绝大部分排序问题的求解就是从有限个可行解中找出一个最优解，使目标 函数达到极小在排序问题中，把可行解称为可行排序( f e a s i b l es c h e d u l i n g ) ，最优解称 为最优排序( o p t i m a l ) 求解排序问题的基本思路是t 应用或借鉴求解其他组合优化问 题的方法，充分利用排序问题本身的特色性质，确定满足约束条件的最优排序有些 问题可以直接转化为其他的组合优化问题求解对具有多项式时间算法的排序问题， 要尽可能的找出空间复杂性和时间复杂性好的算法所谓空间复杂性是指算法所占存 储的多少，时间复杂性是指计算时间的长短，它们都是输入规模的函数 对于个排序问题首先要用复杂性理论对它进行分析，判断它是属于p 问题还 是属于n p - 难问题，以便知道求解此问题的难度若它是p 问题，则求解此类问题就 是寻找计算量尽可能小的多项式时间算法；若它是n p - 难问题，则大致有两种基本方 法：是用分枝定界法，动态规划法等巧妙的枚举来求出它的最优排序这类算法计 算量大只对规模较小的问题才是可行的i 另一种方法是求出它的近似最优排序，包括 各种局部搜索法和启发式算法，分析误差是使用这类算法不可缺少的工作，也是最困 难的工作这类算法计算量小，并能满足一定的实际需要对于尚不知是否存在多项 式时间算法的排序问题，也可用启发式算法得到近似最优排序或针对它的一些特殊情 形设计最优算法 1 2 论文各部分的主要内容 第二章对加工时间具有与位置有关的学习效应的情形，分别研究了目标函数是 最大完工时间与总完工时间的成组排序问题，安装时间 s ) 为确定的一组数的情形 给出了问题l i p s j = p , j x + ( 1 一入) r 。】，g s l ，l l p ：j = 队+ ( 1 一a ) r 4 1 ，g t , s i = o r i 一展i ，1 i 砖= p 巧协+ ( 1 一a ) r q 】，c t , 碍= ( 1 + 鱼l l + 两2 】+ + 两。一1 1 ) 6 & i 和1 l 芘= p , j a + ( 1 一a ) r 吖lg zi 的最优解 第三章讨论了类工件具有线性加工时间的单机排序问题，加工时间具有学习效 应且安装时间带有恶化的成组排序问题1 = 叼一b t ，s = 6 t ，g 7 j g 哪和l l 硒= 4 同时带有学习和恶化效应的单机成组排序问题第一章 叼一暑，s = 鄙，g t i ，具有恶化加工时间 第四章讨论了具有恶化加工时间，工件间存在树型优先约束的单机排序问题l 协= 岛，o u t t r e ei 嘶q 第五章综述了论文的结果，并给出了一些展望 5 同时带有学习和恶化效应的单机成组排序问题第二章 第二章一类带有与位置有关的学习效应的 单机成组排序问题 2 1引言及问题的描述 近年来，非定常加工时间的排序问题备受关注在经典的排序中，一般假设工件 的加工时间是固定不变的常数然而，在某些现实生产系统中，由于公司( 或雇员) 反复从事相同( 或相似) 的工作，加工效率会逐渐提高一个工件排在靠后的位置比 排在相对靠前的位置加工时间短，即工件的加工时间依赖加工位置，这种现象就称为 与位置有关的学习效应而在某些实际问题中，例如在钢铁企业中，某些工件的加工 有温度要求，在满足温度要求的情况下，工件的加工时间是固定的常数但是如果工 件在加工前有等待时间，将引起工件温度的下降这样一来，无论是重新加温使其满 足温度要求，还是在不满足温度要求的低温下加工，都将导致加工时间的增加这一 现象称为工件具有恶化现象这类排序问题比经典的排序问题更为复杂在通常情况 下，只有这类问题相应的经典问题才有可能存在多项式算法 b i s k p d l l 】第一个提出并解决了带有与位置有关的学习效应的单机排序问题 他假设工件五的加工时问是位置的减函数孙= 鼽r o ，其中r 是工件五所排在的位 置，o 0 是给定的常数对于加工时间具有更为一般的与位置有关的学习效应的 情况，跚= a 一，q 0 ，m o s h e i o v ，g 2 , 3 1 研究了几个单机排序问题和平行机上最小 化总完工时间问题d b i s k u p ，d s i m o n s 4 l 研究了更为复杂的加工时间与位置有关 的学习效应问题。 l 盼= 戤r i d g ：( 1 i 霉皿r l ( 置+ ) + 七( z ) ，其中l r ( 1 e a x n i n gr a t e ) 为 学习效率，0 0 加工时间具有和位置有关的学习效应用 p 毛表示工件如排在组内第r 个位置上加工的加工时间，其中r = 1 ，2 ，m 假定 砖= 盼+ ( 1 一a ) 产】，i = 1 ，2 ，其中锄，a 为常数，且q 0 ，0 as1 黝 理解为基本加工时间目标函数分别是极小化最大完工时间以及极小化总完工时间， 因此，我们的问题可以记为： l l 踮= p i j 协+ ( 1 一入) ，i 戤l ，g t , 最l ( 1 ) 1 i 面= 脚协+ ( 1 一a ) 产】 最i ( 2 ) 2 2问题( 1 ) 的求解 我们根据安装时间的不同情况来分别考虑如下三种情形t 2 2 1 安装时闻 & ) 为一组固定的常数的情形t 设7 r = ( 1 ，以2 ， n 。，以l ，无n 。，以l ，) 是工件的一个加工顺 序，并且我们已经对工件进行了重新编号。用表示工件南的完工时问则 7 同时带有学习和恶化效应的单机成组排序问题 第二章 第1 组中各工件的完工时问分别为： c n = s 1 + p l l 盼+ ( 1 一a ) 1 0 1 j c 1 2 = c n + p 1 2 【a + ( 1 一入) 2 q 1 = 岛+ p 1 2 盼+ ( 1 一a ) 2 口- 1 + p l l a + ( 1 一a ) 1 0 1 1 ， q n = c l n l - - i + p l n 。协+ ( 1 一a ) n ：1j = 岛+ p l n 。陋+ ( 1 一a ) 砰】+ + p 1 2 n + ( 1 一入) 2 。1 】+ p l l a + ( 1 一入) 1 m 】 = 毋+ 七n ：l1p l k 队+ ( 1 一a ) 七口1 】 第2 组中各工件的完工时间分别为t c 2 1 = c t n l + s ；+ 耽l 队+ ( 1 一a ) i 】 = 马+ 岛+ 芒1 p l k a + ( 1 一a ) 七口1j + 耽l 队+ ( 1 一a ) l 幻】 ， c 2 n 。= v 2 n 2 - - 1 + 仇n 。协+ ( 1 一a ) 谬】 = 毋+ 岛+ 是l p l 知协+ ( 1 一入) 七。1 1 + 廷l p 2 k 队+ ( 1 一入) 七d 2 1 第，组中各工件的完工时间分别为。 o l = g l ，v 一。+ 毋+ p ，l 协+ ( 1 一入) 1 d ，1 q 铝，= g 红，一，+ p 歹靠，队+ ( 1 一入) 孔；，1 = 名1 瓯+ 罂l p l 七盼+ ( 1 一a ) 胪- 】+ + 翟1 p 批队+ ( 1 一入) 七4 ，】 在上式中，第一项，。最是常数，与组内和组问的顺序均无关第二项以后的各 项只与组内顺序有关。于是组间顺序可以任意排列对于组内工件来说，在毽l 鼽奄队+ ( 1 一a ) 舻】中，由于啦 1 ) ，第i 组中的第歹个工 件记为如这些工件需要在一台机器上加工所有工件均在0 时刻到达每个工件的 加工不可中断，组内工件间无等待时间，且每组工件不允许被他组工件断开加工每 组存在与其开工时间有关安装时间& = 也t ，其中况是个大于零的常数啦表示第 1 4 同时带有学习和恶化效应的单机成组排序问题 第三章 i 组的工件的数量，n l + 他l + + n ，= 住p o = 叼一b o t ，其中，t 是工件南的 开工时间， i = 1 ，2 ，l ；j = 1 ，2 ，啦a i j 0 ，吣称为恶化率：满足0 b i j 1 ， 且b ( 翟lm 知一幻) 嚷i 假设在工件组g 七中无，以后的工件为以u ，以u + l ，以n 。， 则在排序7 r 中，k 后面的工件的完工时间为 瓯= + a k 缸一6 h = a k u + ( 1 一b k u ) c k j c k ，u + 1 = i ：k u + 口七，u + 1 一b k ，t 件l i ：x u = a k , u + l + ( 1 一b k 。u + 1 ) 伉 = a k 计l + ( 1 6 k ，u + 1 ) ( + ( 1 一k u ) ) = a k ，+ l + ( 1 一b k ，u + 1 ) a k u + ( 1 一b k 1 ) ( 1 一k 札) c b g n 。= 警un 罂u + l ( 1 一b k i ) a h + 1 - i 廷u ( 1 一b k 。) 因此在排序一中工件j h 的完工时间是 。= 罂u 兀罂u + - ( 1 6 航) 口h + 兀罂u ( 1 一b k 。) 瓯t n 翟u ( 1 一b k ”) 0 ，因为 c ，所以有仇似 g 。成立，即交换后工件组g 七 中最大完工时间变小了这与排序丌的最优性矛盾因此，组内工件按照笋递减排 口莳 列 下面再来证明组间按照笔氢妾宅罢警揣递减排列为最优 假设在最优排序丌中，组g i 排在组g j 的紧前面，而 ( 尻一b i l ) n 翟：( 1 一b i k ) 一1 ，( 吗一b j l ) 兀琶2 ( 1 一七) 一1 墨l n 饕七+ l ( 1 6 i r ) 、n k ；11 口j 七n 警七+ l ( 1 嗡) 1 6 同时带有学习和恶化效应的单机成组排序问题第三章 组g t 的开工时问为t 交换组g i 和组q ，并保持其他工件组的顺序不变，得到另 外一个排序7 r ，一中组g j 的开工时间也为t 在排序7 f 中，组g i 中每个工件的完工时间为； g 1 = & + a 1 = 盈t + 啦l b i x t g 2 = q l + a 2 = 啦2 + ( 1 一b i 2 ) o i l = 啦2 - i - ( 1 一b a ) o i b 1 ) t - t - 啦l ( 1 6 i 2 ) ， g 啦= ( 盈一6 - ) 兀芒：( 1 一b i k ) t + 罂l 兀翌k + l ( 1 6 i r ) q l = 岛+ 功l = s g l i4 - q l 一1 g 咄 = 吩l - t - ( 岛一b j l ) c ，l q 2 = o i l + 乃2 = l + ( 如一b j l ) c n + q 2 一b ，2 ( a j l + ( 如一b 1 ) g m ) = 2 + ( 1 一b j 2 ) o j b 1 ) c + a j l ( 1 一b j l ) q ，l ，= ( 吗一b 1 ) 兀翟2 ( 1 一吼) g 啦+ 翟。勺k n 墨七+ 。( 1 一b j ，) 在排序矿中，组q 中每个工件的完工时间为： c ：；l = 马+ 功l = 岛t + l 一如l t c p j 2 = c ! ；l + 乃2 = 町2 + ( 1 一b j 2 ) q l = 叼2 + ( 1 一2 ) ( 而一b j l ) t + a j l ( 1 一b 2 ) ， c ；唧= ( 毛一b - ) 兀n 七；j2 ( 1 6 j 七) t + 琶。唧七兀，n ：j 七+ - ( 1 一岛r ) 同时带有学习和恶化效应的单机成组排序问题第三章 q 1 = 最+ p i l = 民c ；唧+ 啦! 一兢l q 叼 = a i l + ( & 一b i l ) q 唧 c ! ：2 = q l + p i 2 = a i 2 + ( 1 一以2 ) c 。t l = a i 2 + n i l ( 1 一氏2 ) + ( 1 一饥2 ) ( 氏一b i l ) c ；唧 = ( 魂一b i l ) n 芒2 ( 1 一k ) q 哪+ 翟l 啦k 兀凳七+ l ( 1 一k ) g n ，一= ( 如一如) n 翟2 ( 1 一b 七) g m + 琶。七n 翟七+ 。( 1 6 j r ) - 【( 况一玩- ) 兀廷2 ( 1 一址) c ! ；呵+ 芒- 啦 兀翟( 1 一k ) 】 = ( 毛一毛) 兀琶：( 1 一b 七) 【( 民一6 ) 兀芒：( 1 一b i k ) t + 翟。口t 七兀翌七+ l ( 1 一k ) 】+ 芒l 叼k n 錾k + l ( 1 一嗡) 一【( 盈一k 1 ) n 釜2 ( 1 6 让) 【( 毛一b - ) n 翟2 ( 1 一b j k ) t + 芒。七兀墨蠹+ 。( 1 6 j r ) 】+ 廷。n 竺七+ 。( 1 一b ) ) = 【( 西一b - ) n 乏：( 1 一) 一1 】翟。n 翟七+ 。( 1 6 i r ) 一【( 五一饥) n 芒2 ( 1 一阮i ) 一1 】芒。叼 i - l , _ - 七+ 。( 1 一如，) 0 因此有q 唧 c 成立，即交换后工件的完工时间变短了这与排序7 1 为最优排序矛 盾于是组问工件按照鬟裂睦湍递减飙得到最优解定理证毕 3 3 问题( 7 ) 的求解 问题1 l 黝= 一b ，s = 础，g t i 比较复杂，我们只就岵= b ，文= 6 ， 且每组工件的个数相等，即m = m ，l = l ，2 ，的情况给出最优顺序即问题 1 = 叼一觇，s = 6 t ，g t i 其中瑰= 仇，待l ，2 ， 1 8 同时带有学习和恶化效应的单机成组排序问题 第三章 定理6 ：对于问题1 p i j = a q b t ，s = 6 t ，g t i ，n = m ，i = 1 ，2 ，组内 工件按照递增排列，组问按照口t i + 罂l ( 1 一b ) m - k 姒递增排列可以得到最优顺 序 证明过程与定理1 类似，故略 1 9 同时带有学习和恶化效应的单机成组排序问题第四章 第四章带树型约束加工时间恶化的 单机排序问题 4 1引言及问题的描述 k u n n a t h u r 1 5 l 等人研究了目标函数为加权总完工时间的具有恶化现象的单机排 序问题，并对一些特殊情形给出了多项式时间算法m o s h e i o v 对工件的加工时间是 开工时问的简单线性函数的单机排序问题进行了讨论l l s l m o s h e i o v 又对工件的加工 时间是开工时间的简单线性函数的f l o w s h o p 问题进行了讨论 1 7 1 ，得到了类似于经典 f l o w s h o p 问题的结论赵传立讨论了工件加工时间是开工时间的线性函数的单机加 权总完工时间问题 x s l1 慨( o + b t ) l 屿岛，并对工件间为链式约束结构的情况给出了 多项式时间算法m o s h e i o v 1 9 l 研究了工件具有相同的基本加工时间但恶化率不同的 总完工时间问题。证明了此问题具有v 型性质，并给出了一些启发式算法许川容， 谢政 2 0 1 研究了线性加工时间的树约束单机排序问题1 协= a # t ，o u t t r e e i w j q 他 们定义了最大家庭树，并利用找最大家庭树的方法来解决这一问题本章也是讨论问 题l i p # = 哟t ，o u t t r e e l 嘶岛本章算法与他们 2 0 1 所使用的方法不同，只要进行收 缩、打开等操作就可以很容易的解决该问题因而本章方法比文【2 0 1 的方法更简单易 懂 本章研究工件加工时间具有恶化效应，工件间存在出树型优先约束的加权总完工 时间问题 设有n 个工件 ，无，j n 需要在一台机器上加工；工件的加工之间存在出树 型优先约束记工件乃的权因子为屿若工件乃的开工时间为t j ，则其加工时间为 功= 哟巧( 其中勾为大于零的常数，通常称为工件的乃恶化率) 由于工件间存在优 先约束，因而并非工件的任一顺序都是可行的顺序记工件的所有可行顺序的集合为 ，排序的目的是求一个最优顺序，r ，使加权总完工时间最小用三参数表示法， 2 0 同时带有学习和恶化效应的单机成组排序问题第四章 该问题记为 1 b = 哟幻，o u t t r e e i 嘶q ( 8 ) 4 2 问题1 o u t t r e e i w j q 的求解 在讨论问题( 8 ) 之前，我们先给出问题1 o u t t r e e le 屿q 的收缩树算法在该问 题中，工件的加工时间为常数，带有出树型约束先给出算法所涉及的几个定义 定义1 假定工件之间存在优先( 偏序) 关系 。若有两个工件满足关系五 乃， 则必须加工完五才能加工乃若j ：i 乃，并且不存在工件以，使五 以 0 所以有些掣 半丝l 掣成立 p i l 十十a k p j l 十十扔 引理4 2 ：在出树中，如果工件 的权时比最大，设乃是以的先驱，那么存在 最优排序，使工件以排在工件乃的紧后加工，从而工件乃的所有后继都排在以之 后加工 证明。假设在某个最优排序7 r 中，工件以没有排在工件乃的紧后j n - r _ ，l i p - r _ 件五和 以之间有工件 l ，以2 ，以i ) 7 r = s j ，以1 ， l ，如，以) 交换工件如和工件 以，保持其他工件位置不变得到另外个排序一，由引理4 1 可知排序一优于排序丌 反复这种交换可以得到个排序，在这个排序中工件 排在工件 以- ，凡) 的前 面加工，即工件五定排在工件乃的紧后面 下面给出问题l l o u t t r e e ie 嘶q 的算法 算法1 步骤0 置j _ 以，兄，厶 ；对每个工件七，计算“权时比。彩5 詈 步骤l ：对于每个( 以) 妒的工件乃，找一个工件 ，使得权时比 鲰= m a x g j l j j 正n ( j j ) 咖) ； 步骤2 ：把节点以和它的先驱工件( 设为) 易这两个节点收缩成个节点，将该点仍 记为乃；置j ：= j ( 包括偏序关系一同改变) ；吩：= 毗+ w j ，p j = 殃+ 乃； 计算新的仍 步骤3 ：若了已变成为个链，则转步骤4 ，否则转步骤1 步骤4 ：把所有收缩的点逐次打开t 后收缩的先打开从而得到个依次加工的工件顺 序，算法结束。 2 2 同时带有学习和恶化效应的单机成组排序问题 第四章 引理4 3 ：设乃是以的个先驱，( 乃) ，且在当前时刻w m a = m a x 詈i , z j , n ( j z ) 矽) 把工件节点乃和以收缩而成的二个工件节点名，则竺警竺， j p j 且( j ：；) 证明；由嚣2m a