（运筹学与控制论专业论文）一定条件下平行机排序问题的研究.pdf

摘要 摘要 论文主要研究了两类排序问题：类是已知最大工件加工时间的半在线平 行机排序问题；另一类是关于工件加工时间恶化单处理机排序问题。目标函数 主要考虑了最大完工时间( g 。) 、总完工时间( c j ) 、最大延误时间( l 。) 。全 文共分四章。 第一章是绪论部分，主要介绍排序问题相关的一些基本概念和预备知识，调 度理论中常用的各种专业术语和已有的一些结果。 第二章主要研究了已知最大工件加工时间半在线平行机排序问题针对三台 机的情况。我们设计了一个竞争比为；的算法，并且证明了此界是紧的。特别 地，对于m 台机的情况，我们给出了此问题的一个下界为丛；地。 第三章主要是关于工件加工时问恶化问题的若干研究，总结并证明了一，些 性质，相应的设计了一些新的模型，给出了一些算法。 第四章主要回顾了本文的一些结论，探讨了解决问题中存在的困难，并指 出了以后进一步的研究方向，提出了个人看法。 关键词：平行机排序，下界，虽坏情况界，e d d ，s p t a b s t r a c t a b s t r a c t i nt h i sp a p e r , w es t u d yt h es e m i - o n l i n ep a r a l l e lm a c h i n es c h e d u l i n gp r o b l e mw h e r e w ek n o wt h el a r g e s tp r o c e s s i n gt i m eo fa l lj o b si na d v a n c e a n dw ea l s oc o n s i d e r s t h es c h e d u l i n gp r o b l e mw i t hd e t e r i o r a t i o no fp r o c e s s i n gt i m e s o b j e c tf u n c t i o ni st o m i n i m i z es c h e d u l el e n g t h ，t o t a lc o m p l e t i o nt i m ea n dm a x i m u ml a t e n e s s 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 r1 ，w eg i v e ss o m ei n t r o d u c t i o na n db a s i ck n o w l e d g ef o rs c h e d u l i n gp r o b l e m s ，s o m et e r m sa n dr e s u l t si nt h i sf i e l d + i nc h a p t e r2 ，w es t u d i e ss e m i o n l i n ev e r s i o n so f p 3 ll c n zw i t ht h el a r g e s tp r o c e s s i n gt i m eo f a l lj o b si sk n o w ni na d v a n c e w ew i l lp r e s e n ta l g o r i t h mf o rp 3 l m a x l g n 。 a n dt h ec o m p e t i t i v er a t i oo ft h ea l g o r i t h mi sj 3 m o r e o v e r , t h el o w e rb o u n d e rw ew i l l i m p r o v ei sa tt h el e a s t 牮f o r 7 , m a c h i n ec a s e i nc h a p t e r3 ，w ec o n s i d e r sp r o b l e m so fd e t e r i o r a t i o no fp r o c e s s i n gt i m e s w e s u n m a a r i z ea n ds h o w s o m eq u a l i t i e s ，a n da l s od e s i g ns o m ea l g o r i t h m sf o rm o d e l sw h i c h w ed e s i g n i nc h a p t e r4 ，w em a i n l yr e v i e w e ds o m ec o n c l u s i o n si nt h i sa r t i c l e ，d i s c u s s e dh a s s o l v e dt h ed i f f i c u l t yw h i c hi nt h eq u e s t i o ne x i s t e d ，a sw e l la st h em a i np o i n t si nf u t u r e s t u d i e sa r eb r i e f l yi n t r o d u c e da n dp r o p o s ei n d i v i d u a lv i e w k e yw o r d s ：p a r a l l e lm a c h i n es c h e d u l i n g ，l o wb o u n d 、e d d ，s p t 第章绪论 1 1 排序问题概述 第一章绪论 排序( 又称为调度) 问题是组合最优化领域中的一类重要问题，它产生的背 景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领 域。从普通的生产部门的计划安排、人员调度、学校课程表的制订，到宇宙的 复杂庞大的飞行计划，都要用至l j h p 序的理论和算法。在理论上它又和算法设计 与分析、计算复杂性理论密切相关。近几十年来，排序问题得到了运筹学界、计 算机科学界、工程学界和管理学界极大的关注，鉴于经典问题的研究日益深入， 而具有实际背景的新问题又不断涌现，可以说，对排序问题的研究正在进入成熟 期。 处理机、任务或者作业和i f l 标函数三要素组成了排序问题。处理机的数 量、类型和环境有很多种情况，任务或作业和资源的约束更是错综复杂，再加 上度量不同指标的目标函数，形成了种类繁多的排序类型。我们用g r a h a m 等人 首先使用的三元组( t h r e e f i e l dr e p r e s e n t a t i o n ) 来描叙问题的类型，这样大大简化 了排序问题的表示。三元组记号由三个域组成：n l 卢h ，它表示一个具体的排序 问题，三个参数域卢和1 分别刻画了机器状况，工件特征和目标函数下面我们 分别对每个参数所代表的含义作具体介绍。 o 域表示处理机的数量、类型和环境，它可以为 1 ：单处理机 p m ：m 个同速机 0 m ：仇个恒速机 r m ：m 个变速机 f m ：m 个处理机，流水作业 o m ：m 个处理机，开放作业 j m ：m 个处理机，异顺序作业 第一幸绪论 f f s ：s 类处理机，柔性流水作业 其中同速机、恒速机和变速机这三种机器状况的具体含义如下：如果所有的 处理机都具有相同的速度，称之为同速移l ( i d e n t i c a lp r o c e s s o r s ) ；如果处理机的速 度不同，但是每个处理机的速度都是常数，不依赖被加工的任务，称它们为恒速 机( u n i f o r mp r o c e s s o r s ) ；如果处理机的速度依赖被加工的任务，它们被称为变速 机( u n r e l a t e dp r o c e s s o r s ) 流水作业、开放作业、异顺序作业和柔性流水作业的具 体含义分别为：如果每个作业需要在每个处理机上加工，而且每个作业的工序也 相同，即在处理机上加工的顺序相同，把这种多类型机的环境称为流水作业( f l o w s h o p ) ；如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把 它称为开放作业( o p e ns h o p ) ；如果个作业需要在每个处理机上加工，每个作业有 自己的加工顺序，称之为异顺序作业( j o bs h o p ) ；在多处理机中，还有一种更为复杂 的情况，这就是柔性流水作业( f l e x i b l ef l o ws h o p ) ，它是流水作业和平行机的推广 在柔性流水作业中，有- 5 类处理机，第j 类有5 f 个平行机，每个作业有s 道工序，每道 工序需要在每类平行机中的一个处理机上加工，且每个作业的加工顺序相同。 p 域表示任务或作业的性质、加工要求或限制，资源的种类、数量和对加工 的影响等约束条件。它同时可以包含多项。 排序问题的实质是寻找对所需完成的任务( 或作业) 以合理的安排以得到 某种意义下的最优结果，这就涉及到所谓的最优准则，通俗的讲也就是以什么 为目标函数。这正是1 域所代表的含义。如果记g 为在某个满足排序问题要 求的可行排序下工件 的完工时间，而在该排序下机器m i 的完工时间为“，则 称c 。= m a x g 为该排序的最大完工时f 自j ( m a k e s p a n ) ，c k 。= r a i n l 沩该排序 的最小机器负载。于是c 。和c 毫t 。就可看成是某种最优准则下的目标函数。当 然，除了上面的两个目标函数以外，排序问题中还有很多目标函数，较常见的有总 完工时间，最大延误时间，最大误工时间等，在此我们就不介绍了。有关排序 问题的近期综述可参见0 3 ， 1 4 】。 一般说来，排序问题分为确定性排序( d e t e r m i n i s t i cs c h e d u l i n 曲问题和随机排 序( s t o c h a s t i cs c h e d u l i n g ) 问题。前者所有的数据在进行决策之前都是已知的，而 后者在做决策时有些量是未确定的，例如加工时间、准备时间、工期等都是一 些随机变量，但他们的分布是已知的。 2 第一章绪论 1 2 算法设计与分析的简单介绍 鉴于7 0 年代建立起来的计算复杂性理论【1 2 】，以及几十年来人们在这方面 的各种工作，现今p p 的猜想已为绝大多数人所接受；而给出此猜想的证 明，也已成为对整个人类智慧的一大挑战，国际数学界将此问题列为二十一世纪 最根本的几个大问题中的一个。如果我们接受p p 的猜想，那么对于所谓 的n p 一难问题就不可能存在多项式时间内找到最优解的算法。也就是说，随着问 题实例的规模的增大，对这种n p 一难问题的每一个实例要用统一的算法找出最优 解，从计算时间上来看几乎是不可能的。因此一个自然的想法就是放弃对最优解 的寻找，而代之以寻找具有某种性能保证的可行解( 称为近似解) ，从而换取计算 时问，这也就是所谓的近似算法( a p p r o x i m a t i o na l g o r i t h m ) 的思想。事实上，排序 中所存在的问题往往是p 难的。 近似算法的好坏可以从两个方面来看，一是算法的计算时间，二是算法得到 的近似解的解值与最优解的解值的接近程度。这里，接近程度常常用所谓的最坏 情况界( w o r s t c a s er a t i o ) 来刻画：假设a 是求解极小化目标排序问题的某一近似算 法，称 r ( a ) = s u p 雨c a ：对排序问题任意一个实例) 为算法a 的最坏情况界，其中a a 和分别表示算法a 解实例，所得的目标函数值 和实例珀q 最优解值。如果近似算法a 还是所谓的在线算法，则这时将算法a 的最 坏情况界特别地称为竞争 = l ( c o m p e t i t i v er a t i o ) ，其中口是指相应离线问题的最优 解值。 下面介绍一下什么是离线算法，什么是在线算法，什么是半在线算法在 经典排序理论中，根据在确定排序时了解的工件信息的多少，常将排序问 题分为”在线”和”离线”两种。在在线问题中，工件一个个地到达，每个工件 只有在到达后才知道它的信息，某工件加工方案一旦决定就不允许改变； 对于平行机来说，当台数为m = 2 ，3 时，l s 是最好的算法【1 6 】，其竞争比分 别为i 和；。当m = 4 ，5 ，6 ，7 时，目前已经有的最好在线算法的竞争比分别 是1 7 3 3 3 ，1 7 7 0 8 ，1 8 0 0 0 ，1 8 2 2 9 。具体可参见【1 7 】，i 1 8 】。对于任意m 2 , a l b e r s 3 第一章绪论 s 在 1 9 中给出了竞争比为1 9 2 3 的再线算法，他的算法在m 1 3 时，是目前已 经有的最好在线算法。在离线问题中，所有工件的信息都事先已知。但是事实 i = = ，在实际应用中，大量存在的问题是所谓”半在线”的，即所知道的：e 件信息 介于在线和离线之间，或者说知道部分信息，且仍然要求工件加工方案一旦决 定就不允许改变。我们称求解在线( 半在线) 问题的算法为在线( 半在线) 算 法。如何利用这些部分信息，设计出比在线算法更好的半在线算法是这类研究 的核心问题。近几年来，半在线排序由于更加符合实际问题的应用背景，日益 受到越来越多的重视。具体可以参见【1 5 】。 最经典的离线算法和在线算法就是解平行机排序问题的l p t 算 法 3 ， 4 】和l s 算法【5 。l p t 算法先将工件从大到小排列后依次将它们安排在 能使其最早完工的机器上加工，而l s 算法只是按工件到达的顺序依次将它们 安排在能使其最早完工的机器上加工。就l p t 算法，已证明它解p m g m 。的最 坏情况界为；一丽1 4 】；就l s 算法，已证明它解p m c 。的竞争比为2 。具体参 见【5 。 对离线问题，如果不考虑时间要求，由于排序问题是组合优化问题，原则上用 枚举法总可以得到最优解。也就是说，如果给你足够多的时间，原则上存在最坏 情况界为1 的离线算法。但对在线问题，即便是给你足够多的时间，竞争比为1 的 在线算法在一般情况下也是不可能存在的。 一4 第璋绪论 1 3 排序理论中常用术语 一般说来，组合最优化问题或者是极小化问题，或者是极大化问题。我 们设实例集合为d n ，对于每一个实例i d ，有一个有穷的可行解集合岛( ，) 。 定义比凰= 西煞， n 的近似算法a 的绝对性能比嘞定义为，r a = i n f r 1 ： 对于所有实例，d n ，r ( i ) r 。 a 的渐近性能l p , r a 0 。= 伽，f r21 ：存在nez + ，对于所有满足o p t ( i ) 的，d h ，r a ( ，) r 。 绝对性能比和渐近性能比的数值越接近1 ，说明a 的性能越好，即近似程 度越高。但未必有r = r a 。例如装箱问题中的递降首次适合f f d ( f i r s tf i t d e c r e a s i n g ) 算法，冗p f d 。= 1 l 9 ，但容易给出o p 7 1 ( ，) = 2 而f p d ( ，) = 2 的实 例，从而r f f d 3 2 。 最佳可达渐近性能l l r m ， = i n f r 1 ：对于n 存在兄 。= r 的多项式时间的近似算法4 l 。r m ，v 能刻划一个最优化问题有多么好的近似 算法。 最优化问题的近似方案为一个算法a ，它以实例i d 和“精度要求”e o 作为输入，输出可行解c r 岛( ) 使得嘞，s14 - e 。这里使用术语“方案”是 因为实际a 上提供了的一系列近似算法，对于每一个固定值e 0 有一个近似算 法。如果对于每一个固定的e 0 生成的近似算法a 。都是多项式时间的，那末 我们称a 是多项式时间近似方案。如果本身的时间复杂性以l e n g t h 旧和1 e 的多 项式为界，则称a 是完全多项式时间近似方案。关于计算复杂性的内容可以参 见【2 0 】【2 1 。 绝对偏差定义为l 一( ，) 一o p t ( i ) i ，相对偏差定义为i 出篙丢；斋盟f 。 5 第二章已知最大工件加j ：时问的平行机排序问题 第二章已知最大工件加工时间的平行机排序问题 2 1 引言 在并行同型机排序问题中，如果我们对所给独立工件的信息全知道，这 样的排序问题为离线问题( o f f - l i n e ) 。若我们对所到来的工件的下一个工件信 息一无所知，同时，对工件的分配到各个机器以后，就不能再更改，我们称 这样的排序问题为在线问题( o n 1 i n e ) 。处于这两者之间，也就是说，只知道 所排工件的部分信息，同时，对工件的指派一旦作出就不可改变，我们称此 问题为半在线问题( s e m i o n 1 i n e ) 。在经典的平行机( i n d e n t i c a lm a c h i n e ) 排序中， 工件集了= p 1 ，p 2 ，) 表示n 个相互独立的工件，每一工件可以分配到事 先给定的m 台同型机中的任一台加工，目标函数为。( 所有机器中的最大负 载) ，即极小化最大机器完工时间。用三参数法表示为p m i | c k 。在p m i l g 。这 一问题中，工件和机器都是从零时刻开始被利用，并且不允许中断。 6 】中已 经证明此问题为排序理论中基本的n p 完全问题之一。自1 9 9 6 年以来，所谓 的半在线算法开始提出并受到越来越多的重视( 参见 1 5 】) ，已广泛的应用到 现实生活中。信息的不完备性也更贴近实际。y h e & g c z h a n g 在 1 忡给出了 事先已知工件的最大工件加工时间，当机器数m = 2 的平行机排序问题的最 优算法。算法竞争比为 。蔡圣义在【2 中，对m = 3 的情形进行了讨论，给 出了一个竞争比为( 1 + 7 3 ) z1 5 9 0 7 半在线算法。同时证明对该问题的这 一半在线情形，任意半在线算法的竞争比至少是 2 。并且 2 】根据在线问题 的l s ( 1 i s ts h e d u l i n g ) 算法，结合平行机排序问题和装箱问题互为对偶的思想， 设计了与中值有关的一系列算法。对于m 4 ，可利用类似思想设计出竞争比 为c ( m ) = 竺二兰监等芸芏皇堕的半在线算法a m ，当4 m 1 7 时，这些半在线 算法比目前已经有的最好在线算法在竞争比上都有所改进。 下一节主要探讨关于此问题的算法。给出了竞争比，并且证明了此界是紧 的，特别地，把下界推广到m 台机，比以往有了很大提高。其中三台机的竞争 比要好于蔡圣义在【2 中的竞争比。 6 第，二章已知最人丁件加t 时间的平行机排序问题 2 2 算法描述 本节所用符号说明：记最大工件加工时n m a x p d = p o ，o = 1 ，2 ，凡) ，记 三台机器分别为m l ，m 2 ，m 3 ，机器最终负载依次为尬，尬，m 3 ；2 1 2 件的加 工之间为p i ( i = 1 ，2 ，礼) ；c “为算法目标值，p 为问题最优目标值；工件 集，一协，j 2 ，矗) ；尬表示在工件岛到达时机器m i 上的当前负载( j = l ，2 ，n ；i = 1 ，2 ，3 ) 。 p n m a x l c k 。的算法如下： 1 m 1 、m 2 两台机器使用l s ( 1 i s ts c h e d u l i n g ) 算法，若发生f 面两种情形之 一，则把工件安排n m 。上加工： ( a ) 当前所来工件加工时间肼= p o ； ( b ) 盼+ 坛 2 p o ，i = 1 ，2 ；j = 1 ，2 ，n 。 2 其余工件执j y l s ( 1 i s ts c h e d u l i n g ) 算法。 定理2 2 1 ：上述算法关于p 3 i m o z l c 仉。问题的竞争比为；。 证明：我们分两类来证明此算法的竞争比为；。 1 若慨= 9 0 ；有两种情形 i ：m l ，m 2 均不大于p o ，则g 4 = c + = m 3 ， c a7 c = 1 i i ：m a ，m 2 中有一个或两者均大于m ，又易知i 矗一) l 如i p o ，从而有， g + ；( 尬+ 尬+ 尬) ；( + ( c a - p o ) + p o ) = ；e 所以 e 一c + ： 第一章l 二知最大i 一件加 一时问的平行机排序问题 2 若m 3 p o ，从而 t t t 3 上至少加工了两个工件。若r “3 上加工的第一个工件 为p 0 ，则由算法记l s 规则得知：m x p o ，m 2 p o ；若m 3 上加工的第一个 工件为p k 2 p o ，m 2 2 + p k 2 p o ，从而亦有m 1 m i 2 p o p k p o ，同理亦有 p o 。所以m 3 p o 时，m l ，尬均大于p o 。 砌如= r a i n 尬) 0 = 1 ，2 ，3 ) ，由算法知，i 弘一l p o ，( i ，j = l ，2 ，3 ) 。 从而c 4 m o + p o 墨2 。 由此可得， c + ；( c aq - m d + 蝙) = i 2 m o + 1 3 c | 4 c a c 4 s 否五；芋；冗石= 。( t 一否j ；冬冗磊) 3 ( ，；) = i 综上各种情况所知，p 3m 茁le k 。问题的上述算法竞争比为；。 下面我们来说明此界是紧的。我们依次来四个工件，加工时间分别 为譬，譬，孕，挚，然后再来两个加工时间为p o 的工件。我们可以根据上述算法可 以得到 c 4 = 2 p o 而最优解 ，1 4 p o 。一百 所以 c 4 2 p o 3 g +孥2 如图： 8 第二章已知最大t 件加j 一时问的平行机排序问题 ，姐 亨1 一 鳓 ，2 y , 了r 矽q 算法解tc = 2 p o 2 3p 3 1 m a x i g 。的下界 图2 1 蔡圣义在【2 】中，给出了当m = 3 时， 算法a 的竞争比至少是、，压。我们根据这一 鼻 丁 p o 鼻 了 p o 扫 2 ， 下下 最勰t = 每 已知最大工件加工时间的任意半在线 思路把平行机数目由3 台推广到m 台。 定理2 3 1 ：对平行机排序问题p r r t l 7 - ；7 , a x c m 任意半在线算法a 的竞争比至少 是以。 证明：令p l = p 2 = = p m 一3 = p o ，一2 = p o ，p m 一1 = ( 2 一1 ) p 0 ，p m = ( 2 一 2 ) p 0 。最初到达( m 一3 ) 个工件，加工时间相同且为p o ，若其中有两个或者 更多个工件放到同一台机器，则以后不来工件。这时显然c “( 1 ) c + ( ) = 票 、2 。此时，这( m 一3 ) 个工件只能分别放到( m 一3 ) 台平行机上：这时依次再到达 三个工件：p 。一2 ，p 。一1 ，p m 。如果p 。一2 与p 。一1 或者p 。被分配到剩余三台空闲平行 机的同一台机器上，此时不再有工件到达，竞争比c a ( i ) c + ( j ) 划：二监= v 互；否则分两种情况讨论： i ：若p m l 与p 。被指派给不同的机器加工，这时再来p m + 1 = p o ，以后不再来 工件，因此这时g 且( i ) c + ( ) 之堑号；2 垃= 以。 i i ：p m l 与被指派到同一台平行机加工，这时有m 一1 台平行机的负载 为p 0 ，这时可以依次再到达两个工件，p 。+ 1 = ( 、，厄一1 ) p o ，p 。+ 2 = ( 2 一v 压) p o 。 如果p 。+ l 与+ z 不是同时被分配到最后一台空闲机器加工，则以后不 有工件到达，此时；c a ( i ) c + ( ，) 、，厄；若是p 。十1 与p 。+ 2 都被分配到最后一 9 第二章已知最人r f l ：加1 ：时问的平行机排序问题 台空闲机器加工，则此时m 台机器的负载相同且都为p 0 ，此时再来一个工 件+ 3 ，加工时间为p o ，以后不再有工件到达，这时的竞争比e 4 ( z ) c 4 ( j ) 2 p o ( v 眨p o ) = , 7 。 根据上面的分析，针对已知最大工件加工时间的半在线平行机排序模型算 法a 的竞争比至少为、，厄 进一步讨论 我们利用半在线问题的部分信息：已知所给最大工件的加工时问。只要 我们选择适当的工件加工时间，仍然有可能提高此问题的下界。我 f r 的思路 是：设最大工件加工时间仍为p o ，还有两种类型的工件，其加工时间分别设 为x p o , ( 1 一x ) p o ，其中令z o ) 之后开工。 即工件i 的加工时间p 鼬) = ：霉j 姜；其中n ：为工件t 的增加比例系数。 其中，a i ( 0 ) 为每个：亡件事先给定的常数，t ( o ) 是工件i 的开工时间，并且证 明了此问题是多项式可解的。只要把所给工件按其增加比例系数 吼1 从大到小 排列是最大完工时间问题( 1f ic k 。) 的最优排序。 【7 】中对加工时间是一般线性增加的情况， 即工件i 的加工时间仇( t ) = 竺：辜耄 j 三；给出了一些最优排序的性质。 特别是 9 讨论了工件加工时间是简单线性恶化，即工件i 在时刻开始加 工的加工时间鼽( ) = t 的排序问题。作者证明了最大完工时间( 1 | ig m 。) 、 问题总完工时间问题( 11 1 g ) 、最大延误问题( 11 ft m 。) 、误工件个数问 题( 1i l 矾) 多项式时间可解的。 本章主要探讨【7 】给出的模型，根据实际情况，我们又设计了一些新的模 型，目标函数为g 和l 。给出了一些多项式算法，并且证明了一些最优性 质。 第三章关rl 。作加工时间恶化问题的若干研究 3 2 最大完工时间问题( 1if g m 。) 的一些性质 【7 】中已经给出了最大完工时间问题的多项式算法。本节给出此问题的一 些性质。定义本章常用符号：设工件i 的完工时问为g ，a j ：为工f 牛j 增加比例 系数；p j ：工件j 加工时间；c k 。：最大机器完工时问；r ：给定常数，该时刻 以后，所有工件加工时间是一个常数( q 刃：a 一( 口( 1 ) ，一( 2 ) ，a ( n ) ) 是工 件 1 ，2 ，礼) 的一个排序。t o ：( o ) 所有工件都在该时刻以后加工。 在证明性质之前，有必要再介绍一下临界工件的概念以及在此情况下完工 时间的计算公式。当然在【7 】中已做论述。各个工件完工时间如下： c 0 ( 1 ) = t o + a a ( 1 ) t o = t o ( 1 + a o ( 1 ) ) a ( 2 ) = t o o + n 。( 1 ) ) ( 1 + o 。( 2 ) ) g ( k ) = t o i i ：= 1 ( 1 + o 。( ：) )( t o 譬? ( 1 + a c t ( ) ) 丁) g ( + 1 ) = t o n ：= 1 ( 1 + n ，( ；) ) + a a ( k + o t( t 0 兀警1 ( 1 + n 。( 。) ) 兰丁) g ( n ) = t o n l l ( 1 + a a ( 。) ) + t e l 女+ 1 a 。( ，) 定义：设排序口中第个工件仃( ) 为临界工件，则满足g 岫1 1 = 仁k - 1 1 ( 1 + n ，c ；) ) 吼，则此排序相比较原序 列c k 。，减小。 证明：设工件原序列印= p ( 1 ) ，一( 2 ) ，o ( 女一i ) ，a ( 自) ，盯0 ) ，一u + 1 ) ，一( m ) ，盯( 礼) ) ，是工件 1 ，2 ，n ) 的个排序。交换以后的排序 为盯。= ( 矿( 1 ) ，一( 2 ) ，o ( k 一1 ) ，a ( m ) ，o ( j ) ，一( j + 1 ) ，一( 七) ，盯( n ) ) 。设 原序歹0 中，工件o ( ) 的前一个工件的完工时间为m ，原序列口l 中口( m ) 的完工时 1 4 第三章关于j 一件加r 时问恶化问题的若干研究 问为： m ( 1 + a k ) ，( 1 + a i ) + ( a i + 1 + + 。) 丁( 1 ) 根据新序列盯2 中，相同位置，盯( 七) 的完工时问为： m o + a m ) ( 1 + ) + ( + l + + a k ) t ( 2 ) ( 2 ) 一( 1 ) ：经过整理得， ( a 。一a k ) ( m ( 1 + a k + 1 ) ( 1 + a j ) 一丁) ( ) 出题设所给条件得( + ) 0 ) 时刻以后开始加工，工件的加工 时问是一个分段函数。由于t 于增加比例系数n ：之间有某种内在的联系，不给定 任何条件和假设，是很难确定其复杂性，给出一个简易的算法也是有难度的。 但最优排序应具有的性质还是可以通过分析给出。 总完工时间问题的性质 定义：我们把工件按照增加比率系数a 。数值，由小到犬把工件排序，此序列 我们为原始序列。 性质l ：最优排序中，临界工件前后的工件都是按照增加比例系数a 。由小到 大排列的。 证明：临界工件前面的工件的加工时问的解析式是：巩( ) = a i ( t ) ，显然工件根 据a ；的数值由小到大排列，临界工件前面工件总完工时问最小。临界工件后面 的工件的加工时问解析式是：p j ( t ) = “f t ，因为o f ，t 都是给定的常数，所以临界 工件后的工件的加工时间是一常数。在经典排序中，已知工件加工时问，目标 是极小化总完工时间的单机排序问题，存在多项式算法s p t ( s h o r t e s tp r o c e s s i n g t i m ef i r s t ) 。因此临界工件后面的加工一i 二件也是按照a 。值由小到排列，命题得证 件。 性质2 ：原始序列中，临界工件前面的工件不可能是最优排序中的临界工 证明：( 反证法) 设原始序列的临界工件为a ( ，) ，增加比例系数为o j ，其前面的 某个工件一( ) ，增加比例系数为a ，。若此工件o ( 0 为最优排序的临界工件，那 么a ( i ) 前面必然要有一个工件为原始序列中，临界工件后面的工件( 包括临界工 件) 。不妨设为a ( 七) ，其增加比例系数为n 女，显然a k 兰a ；。这样我们可以交换工 件o ( 0 与一( k ) ，而此新序列的临界工件变为口( ) ，根据增加比例系数的大小，以 及完工时间计算公式可得：显然更换临界工件以后所得排序的总完工时间要小 于未变换时的排序总完工时间。命题得证， 1 6 第二章关丁t 件加工h j 间恶化问题的若干研究 新模型的总完t 问题( 1l i g ) 的算法 模型一： 根据工件分批( b a t e h ) 的思想，我们改进【7 】中的模型，临界工件前的加工 时间的解析式仍为鼽( t ) = a i t ，l 临界工件后的每个工件( 包括i 临界工件) 的加 。 时间是选取临界工件后面工件的最大加工时间为其加工时间。b p p j ( t ) = m a x a t 1 。通过上面的介绍，我们可以写出工件加工时间的分段函数： 舯 洲甾 注：上式的 n k ) 不包括临界工件增加比例系数。 引理3 3 0 1 ：最优排序的临界工件必须是增加比例系数为m a x a t 的工件。 证明：( 反证法) 假设撮优排序的临界工件不是增加比例系数最大的那个工件，不 妨设其为o ( j ) ，增加比例系数为a j 。令a = m a x a 。) ，此工件记为o ( k ) 。盯( 足) 只 有两种排放方式，情况一：排在临界工件的前面，此时，我们只要交 换盯( ) 与盯( ) ，我们得到一个以a ( 七) 为临界工件的新排序，根据工件完工时间 公式可得，此排序要优于原排序。情况二：排在临界工件的后面，我们仍然交 换a ( ) 与一( j ) 两个工件，其它工件位置不变，显然，变换后的排序的总完工时 间要小于变换前的排序。综上所知，命题得证 定理3 3 1 ：模型一与原模型在目标为极小化总完工时间问题上有相同的难度。 证明：若原模型在多项式时间内可解，显然，模型一也可在多项式内可解，并 且原模型的算法可以应用到模型一；反之，模型一可以多项式时间内可解，根 据性质1 和性质2 ，原模型也可以在多项式时间内可解 模型二： 根据经典排序的想法，以及实际中的应用，临界工件后的加工时间是一常 数且相同。这样，我们可以把工件的加工时问的解析式表示如下： 刖= a i t 。t t t 注：解析式中p t ，且临界i 件的加工时间也为p 。 1 7 第二章关丁r 什加 i 时间恶化问题的若干研究 定理3 _ 3 2 ：工件按照各自的增加比例系数 毗) 【i = 1 ，2 ，礼) ，由小到大排列是 最大完工时i 暗j ( 1l ic 。) 的最优排序。 证明：不妨设工件增加比例系数有如下关系：a 1 a 2 a 。令( 7 0 = ( 盯( 1 ) ，盯( 2 ) ，仃( 礼) ) ，工件a ( i ) 的增加比例系数为a t 。若6 r 0 不是最优排序，设其 最优排序为o - t = ( 盯( 七，) ，盯( 也) ，盯( ) ，o ( k 。) ) ，( t o 中的临界工件为一( j ) ，一1 中 的临界工件为a ( k ) 。o ( k ) 前面的工件数为w l ，盯( j ) 前面的工件数j 一1 。叻中 临界t 件一( k ) 前面的工件按照增加比例系数a 。由小到大排列，显然j w ，并 且印中前w 个： 件的加工时间依次不大于o - l 中相对应工件。根据我们所给工件 加工时间的解析式可知，结论成立 定理3 - 3 3 ：按增加比例系数 n 1 ， 2 2 ，a 。) 由小到大排列是总完工时间问题( 1 g ) 的最优排序。 证明：由定理3 3 1 知，任何一个排序当中每一个工件的完工时问都不小于仃。中 相对应的工件完工时间，因此，命题得证 1 8 第j 章关j 二t 1 ，| ：加工时间恶化问题的若干研究 3 4 一个加强条件的最大延误问题( 1 | ll 。) 的最优排序 引言 在实际生产生活当中，每个任务不可能都是无限期的。恰恰相反，有 许多的任务是有工期的。工期出表示任务正限定的完工时间，如果不按期完 工，应受到一定的惩罚。众所周知，任务没有准备时间的最大延误的排序问 题1l i 工。有一个最优算法：b 1 e d d ( e a r l i e s td u ed a t ef i r s t ) 排序规则。本节将讨 论【7 给出模型的最大延误问题。 其子问题的1i i 上。最优捧序 定理3 4 1 ：文献 7 】所给出的模型，e d d 规则得不到其最大延误问题的最优排 序。 证明：令t o = 1 ，t = 5 ，取三个工件 五，正，珏) ，其增加比例系数分别为 n 1 = l ，a 2 = 2 ，a 3 = 3 ) ，工期分别为 d 1 = 8 ，d 2 = 1 8 ，d 3 = 2 0 。按照e d d 规则，排序 为 丑，t 2 ，死) ，l 。= l ；最优排序为 乃，乃，乃) ，l 。= 0 定理3 4 2 ：若工件的增加比例系数( n t ) = 1 ，2 ，n ) 与工期 d ，) 0 = l ，2 ，乱) 分别满足如下关系：a l2a 2 a n ；d 1 d 2 d n 。【7 】给 出的模型，对于问题1 | | l 。，e d d 规则可以得到最优排序。 证明：令o - 0 = ( 盯( 1 ) ，盯( 2 ) ，o ( 礼) ) ，其中盯( i ) 的增加比例系数为a i 。任意交 换印中的工件，若这两个工件都是临界工件前面的工件或者都是临界工件 后面的工件，结论成立；临界工件前后的工件进行互换，由定理可知，结论仍 然成立 1 9 第四章本文结果与展单 第四章本文结果与展望 本文给出了对于己知最大工件加工时间的平行机的半在线算法的下界 为地学，我们可以选定不同的工件，仍然可以提高此问题的下界。而对于3 台 机的竞争比为；，想降低此数值还是有一定的难度。它与下界的差值已经很小。 甚至可以猜想这是最优的半在线算法竞争比。 对于加工时间恶化问题的讨论，丰富了单台机的排序模型。其中最大完工 时间问题，已经彻底解决。而其他问题，仍处于未知状态，特别是它们的时间 复杂性。本文同时也设计了新的模型，其中有一个给出了最优算法。其他给出 了一些最优排序的内在性质，为给出更好的算法奠定了基础。模型中的难点在 于临界工件前后工件的加工时间会有一个“拐点”，使得问题总完工时间更加 依赖于增加比例系数 n ：1 与限定时间t 的关系。 当然，这只是考虑了单台机的情况，如果推广到多台机，显然这些经典 问题都是p 难的。对于最大完工时间两台平行机的情况，根据以往的组合算 法，其竞争比都是足够的坏。 由于研究还处于初级阶段，还存在不完善之处，需要在今后的工作中继续 学习、钻研。不妥之处，敬请指正。 2 0 参考文献 参考文献 1 】y h ea n d g z h a n g ：s e m i o n l i n es c h e d u l i n go n t w o i d e n t i c a l m c h i n e s ，c o m p u t i n g ，6 2 ，1 7 9 - 1 8 7 ( 1 9 9 9 ) 2 】蔡圣义：三台平行同型机的一个半在线排序算法，捣州师菹学魔学抛疗然剥 城j v 0 1 2 3n o 3j a n 2 0 0 2 3 】j c s i r i k ，h k e l l e r e r , g w o e g i n g e r t h ee x a c tl p t - b o u n df o rm a x i m i z i n gt h em i n i m u m m a c h i n ec o m p l e t i o nt i m e ，o p e r a t i o n sr e s e a r c hl e t t e r s ，1 9 9 2 ，1l ：2 8 1 - 2 8 7 【4 】r l g r a h a m ，b o u n d so nm u l t i p r o c e s s i n gf i n i s h i n ga n o m a l i e s ，s l a mj o u r n a lo na p p l i e d m a t h e m a t i c s ，1 9 6 9 ，1 7 ：4 1 6 - 4 2 9 【5 】r l g r a h a m ，b o u n d sf o rc e r t a i nm u t t i p r o e e s s i n ga n o m a l i e s ，b e l ls y s t e mt e c h j = ，1 9 6 6 ，4 5 1 5 6 3 ，1 5 8 1 【6 】g a r e y , m ，r ，j o i m s o n , d s ：c o m p u t i n g a n d i n t r a c t a b i l i t y ：ag u i d e t ot h et h e o r yo fn p - c o m p l e t e n e s s s a nf r a n c i s c o ：f r e e m a n1 9 7 9 7 】张峰，工件加工时间增加的排序问题( 1 【| c 。) ，高校应用数学学辊4 辑 2 0 0 0 ，1 6 ( 2 ) ：2 2 8 - 2 3 4 【8 】m o s h e i o v g ，v - s h a p e d p o l i c i e s t os c h e d u l e d e t e r i o r a t i o n j , o p e r r e s ，1 9 9 1 ，3 9 ：9 7 9 - 9 9 1 9 】m o s h e i o v , g ：s c h e d u l i n gj o b su n d e rs i m p l el i n e a rd e t e r i o r a t i o n ，m c o m p u t e r o p e ，= r e s 1 9 9 4 ，2 1 ( 6 ) ：6 5 3 - 6 5 9 【1 0 】b r o w n e ，s , y e c h i a l i vs c h e d u l i n gd e t e r i o m t i n gj o b so nas i n g l ep r o c e s s ，刀o p e r r e s ，1 9 9 0 3 8 ：4 9 5 - 4 9 8 i l 】b a k e r k ri n t r o d u c t i o n t os e q u e n e r i n ga n ds c h e d u l i n g ，聊j o h n 所l e y a n d s o n 1 9 7 4 1 2 】m r g a r e y , d s