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

! ：，+ ! ! j 一 ! j ! i i ll l i l l lii i ii il li ll y 1 7 31510 ，苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 ： 涉密论文口 本学位论文属在 年一月解密后适用本规定。 非涉密论文囱 论文作者签名： 导师签名： r 甑。功f 口l “，l 日期：竺! 刍：一：， 几种加工时间为变数的单机 本学位论文主要研究两类排序问题：一类是工件的加工时间增加的单机排序 问题；另一类是工件加工时间带有学习效应与恶化效应相结合的单机排序问题。 全文共分四章。 一 第一章绪论，主要介绍排序问题的一些基本概念、预备知识及其一些背景。 第二章讨论工件加工时间增加的两个排序问题。对于第一个问题11 p , ( o ( t o , p , 乃i 三一，讨论了它的一些性质。在一般情况下，给出一个启发式算法，并得到算法在 最坏情况的上界；在特殊情况下给出了一个多项式算法。对于第二个问题ll 以力( t o ， 乃，乃) lg 懈，给出了多项式算法。 第三章，对于工件加工同时带有学习效应和恶化效应的排序问题，单机最大 完工时间和完工时间和是多项式可解的，而目标函数为加权完工时间和最大延迟 在特殊情况下分别按w s p t 序和e d d 序保证最优。 第四章总结论文的主要结果以及提出一些展望。 关键词：组合优化，排序，多项式算法，学习效应，恶化效应。 作者：莫泽 指导教师：闻振卫 a b s t r a c t 几种加工时间为变数的单机排序问题 s o m e s 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 m so f v a r i a b l e p r o c e s s i n gt i m e a b s t r a c t i nt h i sp a p e r , w es t u d yt w ok i n d so fs c h e d u l i n gp r o b l e m s ：o n ei st h es c h e d u l i n g p r o b l e m o nas i n g l em a c h i n ew i t h i n c r e a s i n gp r o c e s s i n gt i m e ；t h eo t h e ri s t h e s 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 mw i t he f f e c t so fl e a r n i n ga n dd e t e r i o r a t i o n t h et h e s i s c o n s i s t so ff o u rc h a p t e r s i nc h a p t e r 1 ，i n t r o d u c t i o n w eg i v es o m eb a s i cc o n c e p t s ，k n o w l e d g ea n d b a c k g r o u n di n f o r m a t i o no fs c h e d u l i n gp r o b l e m s i nc h a p t e r2 ，w ed i s c u s st w os c h e d u l i n gp r o b l e m sw i t hi n c r e a s i n gp r o c e s s i n gt i m e f o rp r o b l e m1p ，( f ) 只乃i 。w ei n v e s t i g a t ei t sp r o p e r t y , a n dg i v eah e u r i s t i ca l g o r i t h m a n daw o r s t - c a s ee r r o rs u p p e r b o u n d t h i sp r o b l e mi sp o l y n o m i a l l ys o l v a b l eu n d e ra ： s p e c i a lc a s e f o rp r o b l e m1i 删( t o ，乃，乃) ig 啪ap o l y n o m i a la l g o r i t h mi sp r o p o s e d i nc h a p t e r3 ，w ed i s c u s st h e s c h e d u l i n gp r o b l e m sw i t he f f e c t so fl e a r n i n ga n d d e t e r i o r a t i o n ，s i n g l em a c h i n em a k e s p a na n d s u mo fc o m p l e t i o nt i m e sm i n i m i z a t i o n p r o b l e m sr e m a i np o l y n o m i a l l ys o l v a b l e ，r e s p e c t i v e l y b u tf o rt h ef o l l o w i n go b j e c t i v e f u n c t i o n s ：t h ew e i g h t e ds u mo fc o m p l a i o nt i m e sa n dt h em a x i m u ml a t e n e s s ，t h i sp a p e r p r o v e st h a tt h ew s p t r u l ea n dt h ee d dr u l ec a nc o n s t r u c tt h eo p t i m a ls e q u e n c eu n d e ra s p e c i a lc a s e ，r e s p e c t i v e l y i nc h a p t e r4 ，w es u m m a r i z et h et h e s i sa n dp r o p o s es o m ep r o b l e m sf o rf u t u r e r e s e a r c h 、 k e y w o r d s ：c o m b i n a t o r i a lo p t i m i z a t i o n ，s c h e d u l i n g ，p o l y n o m i a la l g o r i t h m ，l e a r n i n g e f f e c t ，d e t e r i o r a t i o ne f f e c t w r i t t e n b y m o z e 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 第二章工件加工时间增加的排序问题”4 2 1 问题1ip ( t ) ( t o ，p dl 工眦。4 2 1 1 引言4 2 1 2 问题的描述5 2 1 3 问题1ip ( t ) ( t o ，只di 工m 觚的一些性质5 2 1 4 问题1ip ( t ) ( t o ，只di 工m 。的实验结果9 2 2 问题1lp ( t ) ( t o ，1 1 ，列ic _ 瞰9 2 2 1 引言9 2 2 2 问题的描述1 0 2 2 3 问题1lp ( t ) ( t o ，乃，列lc _ 蛾一些性质1 1 2 2 4 求解问题的算法一1 5 2 2 5 算例k l6 第三章同时带有学习效应和恶化效应的排序问题 3 1 引言”：18 32 问题的分析及其特点2 0 3 3g 戤问题和q 问题2 2 驴4 坳q 问题2 4 3 5 上胍x 问题2 7 第四章总结与展望 参考文献 攻读学位期间发表的论文：”： 附勇匙“ 致谢 3 2 科，它有着深刻的实际背景和广泛的应用前景，其最初的背景主要是机器制造， 后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产计划、 运作调度、人员安排、学校课程表制订，到复杂而庞大的宇宙飞行计划等，都要 用到排序的理论和方法。在理论上，排序又和算法设计与分析、计算复杂性理论 密切相关。近几十年来，排序问题得到了运筹学界、计算机科学界、工程学界和 管理学界极大的关注。随着经典排序问题研究的日益深入，具有实际背景的新型 排序问题不断涌现。可以说，排序问题的研究正在进入成熟期。 排序模型的三参数表示：1 9 7 9 年g r a h a m ，l a w l e r ，l e n s t r a 和r i n n o o yk a r l 1 】 等人在前人研究的基础上提出了排序问题的三参数表示法：口l l 弘这里我们参考 教材1 2 1 【3 】，给出了如下说明。 ( 1 ) 参数口= 厶，其中所表示机器的数目，当m 缺损时表示机器的数目不指定， 可以是任意正整数。 参数名 l ，尸，q ，尺，d ，n 以描述“机器的环境( m a c h i n ee n v i r o n m e n t ) ”： 名= 1 表示单台机器， 五= p 表示同型( 号) 机， 五= q 表示同类( 别) 机， 名= r 表示非同类型机， 五= 0 表示自由作业机器， 旯= f 表示流水作业机器， 。 旯= ，表示异序作业机器， ( 2 ) 参数尉苗述“工件的特征( j o bc h a r a c t e r i s t i c s ) ”。 当威中含有如下术语时，意义分别是： 厶煅，乃掰，0 ，芝m 0 ，乃，乏m 乃，巧，坳q ) 。 当础中含有如下术语时，意义分别是： c i 嬲：时间表长( 最大完工时间) ，即c n 麟= m a x q ) 它等于最后一个被加工 完工件的完工时间，小的时间表长意味着高效率。 0 ，m ，0 ：( 加权) 总完工时间，小的总完工时间意味着小的平均完工时间， 即效率高。 ： 厶雠：最大延迟，即厶雠= m a x l a ，其中白= q 弓是工件_ ，的延迟时间。 乃，乃：( 加权) 总误工时间，其中乃= m a x q - 弓，o ) 。 fl ，t j 0 巧，巧：( 加权) 总误工数，其中驴、0 ，t ，0 。 排序问题的求解：排序问题的所有可行解全体所成集合称为其可行集。由于 机器数和工件( 或作业) 数都是有限的，因此绝大部分排序问题都是从有限个可行解 中找出一个使得目标函数达到最优的可行解，即最优排序。 排序问题是一类特殊的组合最优化问题，求解排序问题的基本思路是：充分 利用排序问题本身的特殊性质以及借鉴求解其它组合最优化问题的方法，以确定 满足约束条件的最优排序。求解排序问题的基本步骤是：首先，对问题进行分析， 运用复杂性理论以判定所求问题的难度。其次，对于具有多项式算法的排序问题： 要尽可能地找出空间复杂性和时间复杂性较好的算法。空间复杂性是指算法所占 据的存储量，而时间复杂性是指计算所花费的时间长度，它们均是问题的输入规 2 几种加工时间为变数的单机排序问题第一章绪论 模的函数。对于n p 困难的问题，通常有两种处理方法：一种办法是用分枝定界法 或动态规划法等巧妙的穷举或隐枚举来求出确切的最优排序。这类算法的计算量 很大，往往只能对规模较小的问题才是可行的；另一种办法是求问题的近似最优 排序。有许多种很有效的求近似最优解的算法，如局部搜索算法、遗传算法、模 拟退火算法、神经网络算法、蚁群算法等各类启发式算法，但界定( 衡量) 这些 算法的近似程度往往是一项困难的工作。 由于绝大多数排序问题是n p 困难的，其最优解很难找到或即使找到了也无法 判定。在实际应用中也往往没有必要去找出理论意义上的最优解，而只需找到满 足一定要求的满意( 近似) 解。因此对于n p 困难的问题，一方面在特殊情况下( 如 加工允许中断，工件的加工时间都是单位长度，工件具有某些一致性等) 寻找有效 算法，也就是研究该n p 困难问题的某些多项式可解的情况。另一方面是设计性能 优良的启发式算法和近似算法。当然，无论是启发式算法还是近似算法都应该是 多项式时间算法。实际上，n p 难题可解情况的多项式时间算法往往可以作为该 n p 难题本身的启发式算法和近似算法。： 衡量算法的“优良”程度有三种办法：数值算例计算，最坏情况分析和概率分析 【4 1 。这三种办法各有优缺点。目前理论上用得较多的是算法的最坏情况分析。最坏 情况分析是分析算法在最坏情况下的性态；概率分析是分析算法的“平均”性态。在 理论分析( 最坏情况分析和概率分析) 之前进行大量算例计算也是非常有用的办法。 一则可以对理论分析给出估计和提供思路，再则可以与已有的算法进行实际比较。 记j 是所论问题的一个实例，尸是该问题的所有实例的全体；记们是实例， 的目标函数最优值( 望小型) ，屈是由算法日所得到的实例，的目标函数值。如 果存在一个实数，o 1 ) ，对于任何足尸有局哟，那么称算法日为，- 近似算 法，称，是算法日的一个性能比上界。称使该不等式成立的最小正数，是算法日 l 的( 最坏情况) 性能比紧界。如果不能确定算法日的任何性能比上界，或者能确 定性能比上界是无穷大时，那么算法只能叫做启发式算法而不叫近似算法。同 样可以定义目标函数为最大化的问题算法的性能比下界和紧界。 第二章工件加工时间增加的排序问题几种j j n - r 时间为变数的单机排序问题 第二章工件加工时间增加的排序问题 2 1 问题l lp ( o ( t o ，只刀i 三m 。x 2 1 1 引言 在经典排序问题中，一个工件的加工时间是一个固定不变的常数；而现在的 某些实际排序问题中，一个工件的加工时间可以是随该工件的开工时间不同而变 化的函数。例如在钢铁企业中，某些工件的加工时间与工件的温度有关。当工件 的温度落在一定的范围内时，它的加工时间为固定的常数；如果工件在加工之前 等待的时间较长，引起工件温度的下降，那么该工件的加工时间会随之增加。人 们称这种现象为( 加工时间) 恶化效应。 m o s h e i o v 【5 】讨论了工件加工时间是简单线性恶化，即工件五在时刻t 开始加工 的加工时间是p l = a d 的情形，单机排序问题，并证明了相应的最大完工时间g 斌 问题、总完工时间0 问题、最大延迟( 延误) l 一) 问题以及误工工件个数 鳓问题都是多项式时间可解的。 对于工件圻在时刻t 开始加工的加工时间为 a i t t 三臃( d ，= 6 3 3 1 6 4 8 ，故对于不具有工件一致性的问题 li p f ( f ) m ，乃l 三眦，e d d 序并不一定是最优序。 对于把e d d 序作为一个启发式算法解，下面我们将给出该算法的一个最坏情 况的界。为了避免三，黼出现负数的情况，类似于文献【9 】，我们讨论 l m a , “ e d d 。) + d m a x ( 2 5 ) 上积儿) + 西瞰 的上界，其中厶矿m o x d f ，f i 。表示最优序。 定理4 对于任意一个问题1p 乃 t o 均是给定的常数，t 表示对应工件的开工时刻；排序的目 的是极小化时间表长( 最大完工时间) c ，搬。 显然，如果乃= t 2 ，所述问题就是文【6 】中已讨论的问题；以下总假定乃 n f o o 我们记这里所讨论的问题为：li 以f ) ( t o ，乃，t 2 ) ig 掰，并且以下假定，在无专 门指出时，所论及的问题就是问题：li 以f ) ( t o ，孔，7 2 ) ig 懈。 、 定义对于一个给定问题1ip t ) ( t o ，乃，t 2 ) lg 磁以及它的一个给定排序a 如 果工件妇向满足 融 乃c 文的 则称工件出的为乃临界工件；如果工件妇满足 跚) 7 2 1 ，出妁仍，且缸1 ) 硒，我们交换工件与工件妇矗1 ) 的顺序，其 余工件的相对位置保持不变，并记新排序为仍即以七一1 ) = 氓助，吠助= 文七一1 ) ， 对于其余的工件下标j ，彻= 劬。那么c o ( 行) ( 回c & 。) ( 回。 证明：记r = 。1 ) ( 回= 酝1 ) ( a ) 1 ) ( 国= 及1 + a a k q ) ) 2 的 1 1 ， c a ( ) ( 回= 孔1 + 口a ( 知1 ) ) + a o ( k ) t i = 疋1 + 口最助) + 口文缸1 ) 1 1 第二章工件加工时间增加的排序问题几种加工时间为变数的单机排序问题 c 反k ) - c d ( 耐= 口d 缸1 ) 【及l + 口文动一死】 0 得：c k ) q 帕。 引理2 说明，对于任意的最优排序a 对于开工时间 乃的所有工件，码中的 工件一定可以排在踢中的工件之后而不破坏排序的最优性。也就是具体地设出七) 为乃临界工件，则在排序8 _ k 的前k 个工件中，一定可以将属于伤的工件排在属 于囝的工件的前面而仍保持排序的最优性；除非前k 个工件中没有硒中的工件， 否则乃临界工件出舫一定属于硒。 引理3 对于一个给定的排序历若k - d 乃，妇缸1 ) 囝，且如妁愿，我 们交换工件1 ) 与工件妇妁的顺序，其余工件的相对位置保持不变，并记新排序 为仍即有最p o ( k - 1 ) = 氓幼，氓助= 6 ( k - o ，对于其余的工件下标，砌= 劬。那么 帕( 力s 眙万) ( 回。 证明：记丁= 陆1 ) ( 国= & 缸1 ) ( 功乃， 白b 1 ) ( 国2r + a , 定k ) t l ， 如果t 2sl 那么 白b 1 ) ( 国= 丁+ a z t k - ；) t 1 ， c 矾1 ) ( 回= 丁+ a a k 4 ) t 2 ， 白七) ( 西2 丁+ a 氓k - d t l + a , 爱k ) t 2 ， c k 七) ( o = 丁+ 口一知1 ) 死+ 口d d 死= c 仅助( 回。 于是，c o ( 一) ( o ) = 劬力( 回。 如果r 0 ； 如果c 舻】) ( 国 乃，那么 c 最 ) ( 回= ( 丁+ 口d 如1 ) 死) ( 1 + 口揖d ， c a ( 七) ( d ) = 孔l + 口a ( 七1 ) ) + 口相乃2 双1 + 口文七) ) + 口文肛1 ) 死， 1 2 几 的 妇| | ) 为乃临界工件，则在排序趾的后础个工件中，一定可以将属于理的工件排 在属于玛的工件的前面而仍保持排序的最优性。 引理4 对于一个给定的排序历若1 ) 1 1 ，t i m e , k - i ) ，则存 在最优排序a 使硒1 中的所有工件一定排在岛中的所有工件之后。 、 证明：由前面的几个引理易推得。 推论1 说明，只有国2 中的工件，即系数口，比较大的工件才有可能排在某些赐 的工件的前面。 推论2 若囝1 = 硒，即硒2 = 西则最优排序为万= ( 1 ，2 ，力) 。 定理1 存在某最优排序a 满足： 第二章工件加工时间增加的排序问题几种加工时间为变数的单机排序问题 ( 1 ) 若乃临界工件属于伤，则万= ( 1 ，2 ，刀) ，设乃临界工件是以仍( 1 s 耽) ，那么， s = r a i n mt o y i ( 1 + b i ) 乃) 产l 并且， 若疋临界工件是以奶，且” 1 2 ，则 一 g ( 0 5 = t o h ( 1 + b i ) + 乃( 6 叶l + 6 计l + + 6 砣) + 乃( 口n 2 + l + a 忱+ 2 + + a d 否则( 或死临界工件是如，或存在乃临界工件硒，或不存在死临界工件) ， n 2 c 二( 回= t o l - i ( 1 + b i ) + 乃( 鳓+ l + 毗+ 2 + + 口d ( 2 ) 若乃临界工件l ，厄硒，则 万= ( 1 , 2 ，工n 2 , + l ，n 2 + 2 ，n 2 + k , j + l ，产2 ，n 2 ，耽+ 七+ l ，抛+ j h - 2 ，n 2 + n 1 ) 其中0 七t ! ，0 _ ，1 2 。并且， ，k 若疋临界工件飙国，则g ( 国2 咄( 1 + b i ) 户y i l ( 1 + 锄曲+ t 2 ( a p l + 口以+ + c ) + 乃( ? + j h l + 口，1 2 + 量卜2 + + 口一) 。 ，k搿 若乃l | 缶界工讹砭，且， “ b 1 ( - 1 0 ) ，但排序西比排序五更差。 j 1以山 0 以以 j 。 以以 1 51 53 1 56 4 8 1 18 81 5 07 53 0 3 01 52 0 2 57 52 2 55 4 乃118 8 列2 3 7 6 3 8 7 6 4 6 2 6 4 9 2 65 2 2 6 5 3 7 6 5 5 7 6 于是，最优排序是历= ( 1 ，2 ，3 ，4 ，7 ，8 ，5 ，6 ，9 ，1 0 ，1 1 ) 或五= 伊= ( 1 ，2 ，3 ，7 ，8 ，4 ，5 ，6 ， 9 ，1 0 ，1 1 ) 。最优值为g 懈= 4 8 7 。 1 7 第三章同时带有学习效应和恶化效应的排序问题几种加工时间为变数的单机排序问题 第三章同时带有学习效应和恶化效应的排序问题 3 1 引言 k u n n a t h u r 、g u p t a ( 1 9 9 0 ) 1 0 】与b r o w n e 、y e c h i a l i ( 1 9 9 0 ) 1 1 1 讨论了同一个工件在 不同的时间加工所需要的实际加工时长不同的排序问题例子，并且工件开始加工 时间越晚工件的加工时间越长，即具有恶化效应。自此以后，关于具有恶化效应 的排序问题得到广泛研究，a l i d a 、w o m e r ( 1 9 9 9 ) 1 2 】和c h e n g 、d i n g 、l i n ( 2 0 0 4 ) t 1 3 】 分别对有关恶化效应的排序问题进行了综述。另一方面，w r i g h t ( 1 9 3 6 ) t 1 4 】在飞机制 造厂里首先发现能提高生产率的生产模型工人具有学习能力。b i s k u p ( 19 9 9 ) 1 1 5 】 和ic h e n g 、w a n g ( 2 0 0 0 ) 1 6 】是将学习效应的概念引进排序问题的先驱。b i s k u p ( 2 0 0 7 ) t 1 7 】 对具有学习效应的排序问题进行了综述。 尽管对具有学习效应或恶化效应的排序问题的研究已有很多，但将两种效应相 结合的研究还相对不多。在现实生活中，同时具有学习效应和恶化效应的情况随 处可见，w a n g 、c h e n g ( 2 0 0 7 a ) t 1 8 】和w a n g 、c h e n g ( 2 0 0 7 b ) t 1 9 】给出了实例。 l e e ( 2 0 0 4 ) t 2 0 l i , , - j 论t 单机g 懈和0 排序问题：工件的加工时间分别为： 办= ( 风+ a j t ) r 4 ( 岛 o ) 和办= a r 4 ( 1 l p 风= o ) ，其中( 0 ) 是该工件的恶化率，脚) 是该工件的开工时间，口( 0 ) 是学习因子，并分别给出了多项式时间算法。w a n g 、 c h e n g ( 2 0 0 7 b ) t 1 明研究的排序问题中，工件的加工时间为：i , = ( 风+ 口，) 尸，其中 p o 0 ，口，是工件恶化率，是在排序中的位置，a ( s 0 ) 是学习因子。他们得出按 口，) 递减排列，最大完工时间误差界是无穷大。对于工件的加工时间为： p ，= 位，+ 肛) ，4 ，其中t l , j ；0 ，( o ) 是恶化率， w a n g ( 2 0 0 6 ) 2 q 指出单机排序问题 是多项式可解的。w a n g 、c h e n g ( 2 0 0 7 a ) t 1 8 1 研究韵排序问题中，工件的加工时间为： 办= ( 乃+ 哆f ) ，4 ，乃 o ，哆( o ) 是工件恶化率。对于工件的加工时间为 p ，= p j ( a f t ) + f i r 。) 其中乃( o ) 是工件的基本加工时间，口o ) 是关于t 的增凸函数， 且口( 0 ) 0 ，w a n g ( 2 0 0 7 ) 1 2 2 】证明了单机上g 蛾排序问题和完工时间平方和排序问 几种加工时间为变数的单机排序问题 第三章同时带有学习效应和恶化效应的排序问题 题均是多项式可解的，对于目标函数是e w , c j 和厶懈的排序问题在一致性条件下给 出了多项式算法。x u eh u a n g 等( 2 0 0 9 ) 【2 3 1 研究的排序问题中，工件的加工时间为： r - i p j 【，】= 乃( 1 + p t 4 口“，其中所【，】表示工件每排在第，个位置的加工时间，p j 0 i - i 是工件巧的基本加工时间，研门为排在第f 仑位置所对应的工件的基本加工时间， a l 是恶化因子，0 a o ，c 0 ，a 0 ，t c e c h e n g ( 2 0 0 8 ) 2 9 】讨论了 t _ p o + 乙研，】 办= 仍( ) d 1 ，啦，其中a l o ，a 2 o ，b 0 ，口 0 ，所以只要证分子0 ，为此，令： f ( x ) = 五一l + ( 1 + 缸) 。- 2 ( 1 + 曲。( 是上式的分子) 贝u a f ( x ) a x = 知( 1 + 五工) 一一五口( 1 + 功4 - 1 o ，x ( 0 ，+ o o ) ，y , f ( o ) - - - 0 于是f ( x ) 0 。 由于鸦椤中的后刀- ( 一1 ) 个工件对应相同，且，由式( 3 1 ) 知，这以( h 1 ) 个工件的加 工时间也对应相等，所以g l 甜( 椤) g 一回劭，故定理得证。 定理2 对于排序问题11 m o d e ln 旧i g 慨，关于基本加工时间的s p t 为最优序。 证明：由式( 3 4 ) 有： r - ir - i t_1n + 乙研，】+ 乃岛+ 乙研，】+ b q ( 万) 一c j ( a ) = ( p j b ) ( 口- 1 一口7 ) + 6 【二一上生_ - 一r 一6 【上= l - _ 一】4 p o + y p , p o + 所 i f f i l i - i 当日b 时，显然q ( 万) 一勺( 回o ，由于万与骺加( 一1 ) 个工件相同，且，由式( 3 2 ) 知，这拧- ( 一1 ) 个工件对应的加工时间相等，所以g 讲( 刃- ( 占) 加，故定理得证。 定理3 对于排序问题1 i m 。d e l o n e 嚆g ，关于基本加工时间的s p t 为最优序。 证明：令w = 牛， 风+ 易 l f f i l 五：p - - - l ( 1 ) ， p i p o + 研，】 t = ， p o + 易 q ( ) 一q ( 万) = 一，+ 1 ) 鼢，】( 万) + o 一，) 仍”。】( 万。) j f f i l j f f i l o w 一， = x ， 第三章同时带有学习效应和恶化效应的排序问题几种加工时间为变数的单机排序问题 一( 刀一，+ 1 ) 易【，】( 回一( 刀一r ) p j 【，+ l l ( d = ( 刀一r + 1 ) p 4 + b a 一1 】+ ( 珂一，) 【b o + 五叻4 + b a 7 】 一( 刀一r + 1 ) p 4 + b a 1 卜( n - r ) p j ( t + w ) 4 + b a 7 】 = ( p j 一只弘。+ ( 玎一r ) p j t 4 一p , t 4 + b ( f + z w ) 4 一p j ( t + w ) 4 】 = ( 乃一层矿坳叫只等 名一l + ( 1 + 触) 4 叫l 删。】 - 显然( p j 一只) 尸o ，又由定理1 知：仰一，) b 等【旯一l + ( 1 + 纠。一五( 1 + 功4 】o 。 得：e c , ( 8 ) 一q ( 回o 。故结论得证。 j - ii l 定理4 对于排序问题1 i m o d e l t w 。晤q ，关于基本加工时间的s p t 为最优序。 证明：腓令w ：，l ，名：丝( 叫，之竺社， 风+ 易 另 岛+ 艺研 c j ( g ) - c j ( 8 ) = ( n - r + 1 ) p j 【，1 ( 万) + o 一，) b l ，+ l 】( 万) j = lj - i 一( 刀一，+ 1 ) a 【，】( 回一( 刀一r ) p j 【，+ l 】( 回 = ( 乃一p f ) 口，- 1 + ( n - r ) p j a 7 - 1 - p , a 7 - 1 + 只口7 - p j a 7 + 6 0 + 兄w ) 4 6 ( f + 呐4 】 = ( 所一只) 口7 1 + ( 万一，) 【( 所一只) ( 口7 一一口7 ) + 6 ( f + 五w ) 4 6 ( ，+ 忉4 】0 得：q ( ) 一q ( 回o 。故结论得证。 j - i j i 3 4 叼q 问题 现在我们来讨论目标函数是坳q 的两类模型。首先定义工件的关于权与基 本加工时间的一致性概念。 2 4 o w 一， = x 几种加工时间为变数的单机排序问题 第三章同时带有学 - j 效应和恶化效应的排序问题 _-_-_-。_。_。_i-_-_-_-_-_。-1_。1。一一一定义1 如果对于任意两个工件西和西，有 w is w j 历 p i 那么我们称此问题具有工件关于权与基本加工时间一致性。 定理5 对于排序问题11 m o d e lo n e l 喁，如果具有工件关于权与基本加工 j = 时闻一致性，则w s p t 序为最优序。 证明：用反证法，即存在某最优序扩= 似，印，且有力 p i 。交换工件历和 p i ，得一新排序万= ，f ，_ ，功。 由定理1 知，q ( ) q ( 回，k b ，则有： 而： 窆m g ( ) 一窆q ( 回2 叶q ( 6 ) + 嵋e ( ) 一w f g ( 回一w j c g o 3 k = l k = 1 w j c j ( 5 ) + w c f ( 万) 一w , c , ( 0 9 一w j c ，( 0 9 p o + r - i 研】t , o + z p , ，】p o + e v