（运筹学与控制论专业论文）带周期性维护时间的平行机排序问题研究.pdf

摘要 摘要 本文研究了带有维护时问( 单个或j 时期性) 的平行机排序问题。该问题可议描 述为：给顶一个相互独立的工件序列j = f j 。，j 。j j ，每个工件的加工时间( 长 度) 是p ；，i = l ，n ，且需要把它们分配到一台( 或多台) 平行机上进行不可中断 地加工。在加工过程中，需要对机器迸行维护，而工件在维护时段内不能加工。 工件和机器在零时刻都处于就绪状态。全文共分为三章。 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识。 第二章介绍了带单个维护时段的单机排序问题，分两种情况：维护时段固定 维护时段可选择。 第三章讨论了带周期性维护时间的平行机排序问题。本章证明了l s 算法是 p ，ip e r i o d i c i n a i n t e na n t e i c m a x 在线情况的最优算法，算法竞争比为2 。证明 了两台机p z lp e r i o d i c - i l i a i n t e n a n c e f c m a x 情况下，不存在常数界多项式时间算 法。此外，给出了一个离线算法的参数界。 关键词：排序，计算复杂性，工件不可中断，维护时问，近似算法 t h i sp a p e rm a i n l yc o n s i d e r sm a c h i n es c h e d u li n gp r o b l e mw i t h ( s i n g l e o rp e r i o d i c ) m a i n t e n a n c ea c t i v i t i e s g i v e nas e q u e n c ej = ( j l ，j 2 ，j 。) o f i n d e p e n d e n tj o b s ，e a c hw i t hap u s i t i r ep r o c e s s i n gt i m e ( s i z e ) p i ，i = l ，n ， a 1 1j o b sm u s tb en o n p r e e m p t i v e l ys c h e d u l i n go no n eo rs e v e r a li d e n t i c a l m a c h i n e s t h ep a p e rc o n s i s tso ft h r e ec h a p t e r s c h a p t e r1g i v e ss o m ei n t r o d u c t i o na n dp r e l i m i n a r i e sf o rs c h e d u l i n g p r o b l e m s c h a p t e r2i n t r o d u c 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 mw i t ho n e m a i n t e n a n c e t h e r ea r et w os o r ts ：f i x e dm a i n t e n a n c e 、o p t i o n a lm a i n t e n a n c e c h a p t e r 3d is c h ss e sm a c h i n e s c h e d u l i n gp r o b l e m w i t h p e r i o d i c m e i n t e n a n c e t h isc h a p t e rp r o v et h a tl sist h eo p t i m a lo n l i n ea l g o r i t h m o fp 】j p e r i o d i c - - m a i n t e na n c e f c m a x t h ec o m p e t i t i v er a t i oo fl sa l g o r i t n m i s2 t h ea l g o r i t h mw i t hc o n s t a n tb o u n do fp 2j p e r i o d i c - - m i n t e na n c e l c m a x d o e s n te x is t b e s i d e s ，w eg i v eao f f l i n ep o l y n o m i a la l g o r i t l mw i t h p a r a m e t e rb o u n d k e yw o r d s ：s c h e d u l i n g ，c o m p u t a t i o n a lc o m p l e x i t y ，n o n r e s u m a b l ej o b s ， m a i n t e n a n c e ，a p p r o x i m a t i o na l g o r i t h m 玎 第一章绪论 * 第一章绪论 1 1 平行机排序问题 排序( s c h e d u l i n g ) 是一类重要的组合优化问题，它广泛地应用于计算机科 学，管理科学和工程技术等很多领域，同时也是运筹学一个非常活跃的分支。排 序问题产生的背景是机器制造。后来普通的生产部门的人员调度，学校的课程安 排等等都需要用道排序的理论和算法。排序问题 1 】简单得说就是利用一些处理 机( p r o c e s s o r ) ，机器( m a c h i n e ) 或资源( r e s o t l f e e ) ，最优地完成一批给定的 任务( t a s k ) 或工作( j o b ) 。在执行这些任务或作业时需要满足某些限制条件， 如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工时问的影响 等。 一般的平行机排序问题可以描述成：给定一个工件序列j = j 1 ，j 。j j ， 每个工件的加工时间( 长度) 是p 。i = 1 ，n ( 在不混淆的情况下将工件序列表示 为j = p 。，p ：，p 。) ) ，需要把它们分配到m 台机器m 1 ，m 2 ，m m 上去加工。机器 m i 的速度为s i 1 。机器的负载是指所有在这台机器上加工的工件的总长度。在 算法s 下机器负载记为l i ( j ，s ) ( 在不会引起歧异的情况下，可筒记为1 1 ) ， i = 1 ，2 ，m 。 目前文献普遍采用一矛 三参数表示法ajply 来为排序闸题命名三个参数 o 【，口和v 分别刻画了机器的状况，工件的状况和目标函数。下面我们分别对每 个参数所代表的含义作具体说明。 o 【主要描述了机器的类型和加工规则。常见的有单台机，同型机( i d e n t i c a l m a c h i n e s ) ，同类机( u n i f o r mm a c h i n e s ) ，不同类机( u n r e l a t e dm a c h i n e s ) ， 流水作业( f l o w s h o w ) ，有序作业( j o bs h o p ) ，自由作业( o p e ns h o p ) 等等。 本文考虑同型机，即完全相同的平行机器，机器速度s ；均相同。 d 主要表示工件的性质，加工要求和限制( 如果不写，表示无限制) 。它可 以同时包含多项。如工件是在线还是半在线，加工是否可以中断，工件是否需要 准备时阀，工件之间是否存在加工顺序约束等等。在实际生活中，机器运行一段 时间之后需要停止并维护，在这样的背景下我们可以加入带维护时间这个条件来 考虑这一类问题。第二章列举了带单个维护时间的排序问题模型、计算复杂性和 第一章绪论 相应算法；第三章集中讨论了带周期性维护时间的排序问题，主要是单台机和两 台机的情况 v 主要描述了要优化的目标函数。类似于所有的组合优化问题，任何一个给 定的排序问题都有有限个可行解，目标函数给出了这个含有限个解的解空间的一 个度量，并在这个度量意义下定义了最优解。对于某个给定的排序问题，定义某 台机器的完工时问为安排好所有的工件后，这台机器上的最后一个完工工件的完 工时间。排序问题中最经典的目标函数是c m x ( m a k e s p a n ) ，即极小化最大的机 器完工时闻。事实上，最优化问题特别是排序问题的一个主要缺陷是对于目标函 数每个不同的度量都有不同的最优解。通常，不同算法用于不用度量，也都给出 自己的解。关于各种目标函数，如总完工时间，最大误工时间等等，请参考一些 排序方面的专著 1 】。 第一章绪论 1 2 离线，在线、半在线闷意和算法性能分析 根据我们在排序时掌握工件信息的多少把排序问题分为离线( o f f l i n e ) 和 在线( o n l i n e ) 两类。 在离线问题中，全部工件的所有信息在排序时都是已知的，我们可以充分利 用这些信息对工件进行安排。 而对在线问题，是指工件的信息逐个释放，即工件p i * l 的信息只有在对工件 p 1 ，p i 进行安排后才会被释放，并且工件一个个到达，一旦到达，就必须安 排它在某台机器上加工，且在以后不可改变。 半在线( s e m i o n l i n e ) 排序问题是介于离线问题和在线问题之间的排序问 题，也就是说我们除了知道当前到达的工件及之前的工件信息，同时还预先知道 工件的部分信息，但仍不允许对任何已安排的工件迸行重排 4 ；5 。常见的信息 有预先知道所有工件的总长度( s u m ) 6 ，最大工件的加工时间( m a x ) 7 】，工 件从大到小来( d e c r ) 【8 9 】，工件的加工时间在一个区问内( g r o u p ) 【7 】，工 件的相对大小( o r d i n a l ) 10 】，以及预先知道离线最优值( o p t ) 1 i 等等。 半在线排序问题的研究主要体现在如何有效地利用这些已知的部分信息来 设计出更好的算法，即要求该算法的性能要比已知的最好可能的在线算法的性能 要好。在半在线排序的研究出现之前，几乎没有人知道这些信息对于设计近似算 法的有用程度，也几乎没有人知道如何利用这些信息来设计更好性能的近似算 法。因此，与经典的平行机排序问题一样，半在线排序问题也是同样有趣和有意 义的。 对离线问题，我们将求解离线问题的算法称为离线算法。离线算法的性能用 最坏情况界( w o r s t - e a s er a t i o ) 来衡量。对一个工件序列j 和算法s ，记s ( j ) 代表算法s 的目标值，o p t ( j ) 代表最优值。对于极小化目标，算法s 的最坏情况 界定义为c ( s ) = s u p ， s ( j ) o p t ( j ) ) 。对于极大化目标，算法s 的最坏情况界定义 为c ( s ) = s u p ，f o p t ( j ) s ( j ) ) 。 对于一个( 半) 在线问题，求解该问题的算法就称为( 半) 在线算法。( 半) 在线算法的性能是可以通过它的竞争比( c o m p e t i t i v er a t i o ) 来衡量的。其定 义与离线算法的最坏情况界类似，其中o p t ( j ) 为相应离线问题的最优目标值。 第一章绪论 我们希望设计出竞争比尽可能小的算法。如果没有任何( 半) 在线算法的竞争小 于p ，则称这个( 半) 在线问题的上界为p 当这个问题的某个( 半) 在线算法 的竞争比小于p ，则称这个( 半) 在线问题的下界为p 。当这个问题的某个( 半) 在线算法的竞争比等于问题的下界时，我们就称这个算法是最优的。 第一章绪论 1 3 论文概述 本文主要讨论了带维护时闻的平行机排序问题。 第二章讨论了带单个维护时段的单机排序问题，分两种情况：维护时段固定、 维护时段可选择。对前一种情况，证明了1 ，啊“c j 的n p 困难性，介绍了s p t 算法和i d s p t 算法，以及两个算法的最坏情况界；对后一种情况，介绍了近期相 关文章的研究成果。 第三章讨论了带周期性维护时间的平行机排序问题。目前研究这类问题的文 章较少，本章的内容主要是接着m j i ，y h e ，t c e c h e n g 的文章 2 0 】做了些工 作。文章f 2 0 】证明了l p t 算法是p 。l p e r i o d i c - - m a i n t e n a n c e i c m a x 离线情况的最 优算法，算法最坏情况界为2 。本章证明了l s 算法是p ，ip e r i o d i c - - m a i n t e n a n t e l c m a x 在线情况的最优算法，算法竞争比也为2 。证明了两台机p ：ip e r i o d i c 一 眦i n t e n a n c e l c m a x 情况下，不存在常数界多项式时问算法。此外，给出了一个 离线算法及其参数界。 第二章带维护时问的平行机排序问题研究 第二章带单个维护时段的单机排序同邀研究 2 1 引言 现有的关于排序理论的文章大多数是基于机器连续可获得的假设。但在实际 生产过程中，由于确定的机器维护和不可预见的死机( 损坏) 现象，往往使得这 种假设不成立。在实践中，有工件等待加工而机器却停止运转进行维护的现象并 非罕见，我们要将机器维护计划和工件加工计划很好得协调起来。不确定的死机 ( 损坏) 现象将会打乱工件加工计划，并大大降低生产系统的效率。机器维护可 以通过较小的损失降低死机的概率，决策者越来越注意到制订机器维护计划的重 要性。 如果一台机器在加工过程中可以安排一次或者若干次的机器维护，这些维护 可能需要花费一些时间，但却可以使加工某些工件的速度变快，那么作为一个精 明的决策者，是否安排这些维护，何时安排它们以及对某个具体的工件是否有必 要等到维护之后再加工等等这些问题就应当排入考虑之列。这就是我们要介绍的 一一带有速率改变行为的单机排序问题，我们用并不准确的“速率改变行为”代 表的不只是上面提到的机器维护，还可能是机器中断，机器磨损以及加工过程的 学习效应等所有可利用的限制( 机器限制的可利用性见文献【i3 】) 。正是由于有 着广泛的应用背景，这个问题一直以来为很多人考虑和研究。 我们可以将问题简单地分为两类：速率改变行为固定和速率改变行为不定。 到目前为止，对于只有一个速率改变行为的情形，这样两类分别都有了一些比较 好的结果。比如，对于前者，已经给出了目标为最大完工时间或者完工时间总和 的近似算法，而对于后者，很多目标都已经有了获得最优解的多项式算法。 带有速率改变行为的单机排序问题的各个目标都已经有了较好的结果，对于 速率改变行为时间固定的情形，主要是复杂性的证明和近似算法的寻找，而对于 速率改变行为时间可选择的情形，主要是分辨其中哪些不是p 问题，而对其中的 p 问题如何给出多项式时间算法等。我们也可以将速率改变行为的次数加入考虑 因素中，一些问题仍然值得我们探讨。 第二章带维护时问的平行机排序问题研究 2 2 维护时段圈定的情况 为方便陈述，我们下面给出相关的记号：”个工件的集合j 2 “，以，以) ， 机器有一次速率改变行为，它的起始时间是r ，进行需要的时间是上。所有工件 都在零时刻释放，工件加工时不允许中断，l x 4 牛j , 的正常加工时间是只，而在 速率改变行为之后的加工时间为q 只，其中o 5 4 ) 的s p t 近似算法( s h o r t e s tp r o c e s s i n g t i m e ) ，其n p 困难性的证明相对复杂，而s p t 近似算法是指将工件按照从小到大 顺序加工，并尽可能地排在中断之前。 这个算法最坏情况界是在1 9 9 2 年被c y l e e 等在文献【3 中证明的，他们还 提供了一个最坏情况紧的例子，同时给了一个较为简单的困难性证明。 定理2 1 1 ， | i c 是n p 困难的 证明：将奇一偶划分问题多项式时间归约到l i j y c , 对于给定的奇一偶划分问题的实例，x 2 而，屯，x 2 一 ，其中对于所有的 皓1 ，2 ”，o t 2 l ( n - i + 1 ) ( x n l + x 2 ，) + 2 h + l 】m + 柏 + 2 ( n m + z ) + m 】 的l ，岛ij g 的实例。 由这个构造可以得到1 ，啊l i c 问题的n p 困难性( 具体见文献【3 】) 。 定理2 2s p t 算法的最坏情况界不超过9 7 。 证明：对于s p t 最坏情况界的估计，还用c y l e e 等文中的记号，记s p t 算法得 到的排在机器中断前的工件集为b ，之后加工的_ t - 件集为a ，s p t 排序s 中s - 件z 的完工时问为c ，相应的最优解中前面j b l 个工件的集合是x ，而其余工件 的集合是y ，最优排序s 中工件z 的完工时间为c 。考虑到没有机器中断时的 完工时间总和以s p t 排序最优，他们得出s 在中断前的空闲时间j 不会超过s 的 空闲时间j ，并由此给出最优解和s p t 解的完s - 时间总和的一个比较， q c + ( r l l x 占一j + ) 以及最优解的一个估计c 2 ( 掣+ l 舻一万“，这 样相对误差界就有 e = 连乒s 斋器 2 即s p t 算法的最坏情况界不超过9 7 。 另一3 - 面，c y l e e 等人的工作还包括给出一个紧实例：n = 4 ，a 。l ， 岛2 马5 只2 m 21 ，r = m ，上= l ，这个实例按照s p t 排序的完工时间总和 是9 m + 4 ，而最优解是7 m + 6 ，这样当m 呻。o 时，该实例的最坏情况界斗9 7 ， 所以s p t 算法最坏情况界就是9 7 。 可以看到，c y l e e 等对最优解和算法所得解都是用占一这个数来估计的， 这个方法在2 0 0 3 年c s a d f i 等人的文章( 文献【2 ) 中也得到体现，c s a d f i 等人在这篇文章中对于s p t 算法进行改进得到m s p t 算法，即首先将工件按照s p t 排好，然后通过交换一次机器中断前的一个工件和中断后的一个工件选择对目标 8 第= 章带维护时问的平行机排序问题研究 值最好的情况。 定理2 3m s p t 算法的最坏情况界是2o 17 。 证明：如果记这个算法得到的排序是s ，工件，的完工时间为c ，那么得到的 两个主要估计就是 q ( l 兰掣+ 2 ) ( 巧一d ) ，c - z c , + ( j r l 2 ) ( 占一占) 。 由此得到相对误差界为 s = 避乒岽篙专 另一方面，有实例：”= 7 ，对于i 1 ，2 ) ，口= 1 ；而对于i 3 4 ，5 ，6 ，7 ，a = m ； 并且r = m ，l = 1 。此实例最坏情况界恰是2 0 1 7 ，这样m s p t 算法的最坏情况 界就是2o 1 7 。 也就是说m s p t 算法改进了s p t 的结果。20 0 5 年y h e ，w y z h o n g ，h k g u 在 文章 2 1 中给出了l ，趣h y , c , 的p t a s ( 这个p t a s 是文章12 3 中算法的拓展) 。 s + 和s 分别表示由最优算法和s p t 算法得到的序列。b 表示序列s 中在维护 时段之前的工件集合；a 表示s 中所有在维护时段之后的工件集合。x 表示序列 s + 中前f b f 个工件集合，y 表示后f a f 个工件集合。6 和6 分别表示序列s + 和s 中维护时段前的空闲时段。 定义2 2 1 令a a “k ，k - 交换”程序是指：对序列s ，将a 中的a 个工件与b 中的b 个工件交换，且 b 中的b 个工件总长与6 之和不小于h 中的a 个工件长度之和。经过这样的交换， 维护时段前后的工件按非递减的顺序重新排列。 算法s p t e ： 1 将所有工件按s p t 规则排序 2 对任一给定正整数k ，用“k ，k - 交换”生成新序列 3 在1 和2 步中的两个序列中选取最好的作为结果输出 第二章带维护时问的平行机排序问题研究 当令k = l 时，上述算法就是m s p t 算法【23 】因此s i t e 是m s p t 算法的一般 形式。s a d i fe ta 1 f 2 3 】已经证明m s p t 算法的最坏情况界为2 0 1 7 。y h e w y z h o n g ，h k g u 【23 给出结果： 定理2 4 对任意给定的整数k 2 ，算法s p t e 的最坏情况界至多为1 +! ， 5 + 2 、2 k + 8 时间复杂性为o ( d ”) 。 由此可知s p t e 是问题1 ，啊h y c , 的一个p t a s 。 第- i 带维护时问的平行机排序问题研究 2 2 2 维护时段前后机器加工速率改交 再来看带有机器磨损或者学习效应的情形，此时月也是一个固定的时刻。与 上面不同的是，以上在进行“速率改变行为”时工件都不允许加工，而这类情形 下，上：o ，并且工件在速率改变时可以加工，也可以空闲直到速率改变进行之 后。 在带有机器磨损的情形，有口，2 1 。在2 0 0 1 年t c e c h e n g 等的文章( 文 献【1 5 1 ) 证明了有机器磨损的最大完工时间问题是n p 困难的，同时指出了一些 特殊多项式可解的情形。 在有学习效应耐，o r + a k p k ，那么机器空f , - j 至, j 时刻r 才开始加工以以及后来 到达的工件；否则，在以一，之后直接加工以和其余工件。 离线算法 i ： ( 1 ) 将工件重新标号，使得啦哆2 c t 。，t = m i n ( j i ：，只 胄) 。 ( 2x 将工件以，以一。加工，执行算法a o 的第2 步。 y h e 等在文章中证明了算法a o 的竞争比是2 ，两算法a i 的最坏情况界是5 4 。 第= 章带维护时问的平行机排序问题研究 2 3 维护时段可选择的情况 速率改交时问可选择，印指r 不再是一个固定的时刻。 此时，分两种情况：必须有维护时段，但开始时刻r 可选择；是否有维护时 段，可选择。 c 一y l e e 和v j l e o n 首先在2 0 0 1 年的论文 12 】中分别给了1 l l , m ic ， 1 f l , m i c j ，1 i r m i w j c j 的多项式时间算法，主要利用的是动态规划方法；此外 对于1 lr m i l m a x 还证明是n p 困难的，并且给了一个伪多项式时间算法。 c 一y l e e 和c s l i n 在2 0 0 1 年的文章【1 6 】中假定工件加工时间在维护发生 前后保持不变，研究了工件可中断情况中的1 i i m ，r a i e 【c m a x 】，1 i i m ，r a f e c i 】，1 1 1 7 1 1 1 ，r a i m a x e l i 】，1 l l , m ，r - a i e 【m a x l i 四种情况；对于工件不可中断的 情况研究了1 ir i b ，i l l 一a i e 【c m a x ，1 lr m ，n 1 一a i e 【c - 】，1 ir m ，n r - a i m a x e 【l i ， 1 l l - m ，i l l - 一a l e 【m a x l i 。文章研究上述各种情况所具有的特殊性质，并得到了一些 有益的结论： ( i ) 目标为最小化期望最大完工时问的情况，若r 的分布函数f ( x ) 是凹函 数，按s p t 规则得到的工件序列是最优的；若r 的分布函数f ( x ) 相对于工件加 工时间总和是凸函数时，按l p t 规则得到的工件序列是最优的。 ( i i ) 目标为最小化总期望完工时间的情况，若r 的分布函数f ( x ) 是凹函数， 按s p t 规则得到的工件序列是最优的。 ( i i i ) 目标为最小化最大期望误工时间的情况，当工件序列满足“l , e v e l , s e - a g r e e a b l e ”假设时，若r 的分布函数f ( x ) 是凹函数( 或凸函数) ，按e d d 规则得 到的工件序列是最优的。 y h e ，m j i 和t c e c h e n g 在2 0 0 5 年的文章【17 中，分析了目标为最小化 最大完工时间和总完工时间的情况下的问题复杂性： 第二章带维护时间的平行机排序问题研究 t s b l e1 s u m m a r yo f n p - h a r d n e s sr e s u l t s i 荫l s l = 0s 1 o 够f 2a 加s i - 0 t a b l e l 中的妒； s 1 ，s 2 ，s m ) 表示r 可以选择的时刻集合。 文章对目标为最小化最大完工时问的情况，给出了伪多项式时间算法和完全 多项式近似方案；对目标为完工时间总和的情况，给出了一个特殊情况的伪多项 式时闻算法。 t a b l e2 s u m m a r yo f t h ea l g o r i t h m s 第三章带周期性维护时间的平行机排序问题研究 第三章带周期性维护时同的平行机排序问题研究 3 1 引言 周期性维护计划包括定期检查、定期修理和预防性维护。合理的周期性维护 计划可以提高生产效率和安全性，从而促进产量的提高和对安全的重视。 随着加工系统越来越多地安排周期性维护，我们有必要研究在带有周期性维 护的系统中如何来安排工件加工顺序。l i a o 和c h e n 】1 就曾研究过目标为最小 化最大延误时间的此类问题，他们给出了一个分支定界算法和针对大规模实例的 启发式算法，并通过测试验证该启发式算法有较好的性能。 在m i n 儿，y o n gh e ，t c e c h e n g 的文章 2 0 中，讨论了目标为最小化 m a k e s p a n 的周期性单机排序问题。文章证明了经典l p t 算法的最坏情况界为2 ， 且该问题不存在最坏情况界小于2 的多项式时问近似算法，即l p t 算法是最优离 线算法。 本章中所用的符号于文章 2 0 】统一，t 表示连续加工时问，t 表示单次维护 时间，b 表示最优解中所用加工时段数，b 表示l s 算法中所用加工时段数。 第三章带周期性维护时问的平行机排序问题研究 3 2 单台机的曩佳在线算法 在文章m i nj i ，y o n gh e ，t c e c h e n g ，s i n g l e m a c h i n es c h e d u l i n gw i t h p e r i o d i cm a i n t e n a n c et om i n i m i z em a k e s p a n 【2 0 】中证明了单台机带周期性维 护时问离线情况下，”t 算法是最优的。接下来，我们将证叹在线情况下，l s 算法是最优的。 3 2 1 复杂性证明 c y l e e 在他的一篇文章中提过该问题的复杂性，但未做证明，在此重新证 明作为补充。 定理3 2 1 ：p 1 i p e r i o d i c m a i n t e n a n c e i c m a x 是强n p 难的。 证明：我们将该问题多项式时间归约到“三元划分问题”。 对任一“三元划分问题”的实例i ： 有3 m 个元素的有穷集合a ， _ a l ，a 2 ，a 0 ：，a i = m t ，且对任意i = l ，2 ，3 m 有t 2 a i t 4 问：a 是否能分成m 个不相交的集合s ，s ：，s 一 使得1 j m ，e a ies ja i = t ? 构造上述问题的一个实例i ： 机器连续加工时间为t ，每次维护时间为t 有工件p - ，p 2 ，p h ( 满足p i = a i ，对任意1 i t 4 ，所以每个加工时段内恰好有三个工件( 工件长度之和 为t ) 。于是，得知实例i 中a 必存分成m 个不相交的集合s l ，s 坼s 一，使 得使得1 j m ，a i es ja i f t 。 充分性：如果 是能分成m 个不相交的集合s t ，s ：，s ，使得1 j ：c j + ：，a j = ：，( c j + a j ) t b + 矛盾，说明引理3 2 2 成立 一 定理3 2 2 ：对于p l l p e r i o d i c m a a i n t e n a n c e l c m a x 问题，r l s = c l s c o p t 2 。 证明：1 ，b t 1 时，必有b = l ，此时c l s c o p t = i 2 时，由引理3 2 2 可得，b _ b b 一1 ( 1 ) 若b - b * b * - i c l s ( b - 1 ) ( t + t ) + y c o p t( b 一1 ) ( t + t ) + x 其中y 表示l s 算法中最后一个加工时段内所有工件总长；x 表示最优解 中最后一个加工时段内所有工件总长。 由b - b * b * 一1 得b - 1 2 ( b 一1 ) ，又因为b 、b 是整数，所以b 2 ( b 一1 ) 。 c l s ( b - 1 ) t 2 f f i ( b 一1 ) t 。最优解中酋b * - i 个 加工时段内的工件总长”。再联合假设y x ，得最优解中工件总长小于 l s 算法中工件总长，这与实际矛盾，说明假设y x 不成立，印y 2 ) 内加工，则之后没有新工件， 有c d c o r r = ( n - i ) ( t + t ) + 5 】一o o ( 一0 ) ，其中n 2 。 2 ，算法a 将工件p l = 6 放在第一个加工时段内，当工件p 2 = t 到达时只能 放在第二个及以后的加工时段内，设其放在第n 个时间段( n 2 ) 内加 工，此时 有c c o p r 一 t + ( n 一1 ) ( t + t ) ( t + t + ) 一n ( t 一* ) ，其中n 2 。 3 、综合1 ，2 得在线情况问题下界为2 。 一 小结：由定理3 2 。2 和定理3 2 3 的结论可知l s 算法是 p 1i p e r i o d i c - m a i n t e f l a n c ei c m a x 问题在线情况下的最优算法。 第三章带周期性维护时闻的平行机排序问题研究 3 3 两台机问题讨论 3 3 1 复杂性证明 两台机器复杂性证明与单台机器的情况是类似的。 定理3 3 1 ：p 2 i p e r i o d i c 一眦i n t e n a n c e i c m a x 是强n p 难的。 证明：我们将该问题多项式时间9 3 约到“三元划分问题”。 对任一“三元划分问题”的实例i ： 有3 m 个元素的有穷集合a ，a f f i a ，a 2 ，a 0 ：，a l - - - m t ，且对任意i l l ，2 ，3 m 有t 2 a i t 4 问：a 是否能分成m 个不相交的集合sz ，s ：，s 。 使得1 j m ，ea jes ja i f f i t ? 构造上述问题的一个实例i ： 机器连续加工时间为t ，每次维护时间为t 有工件p 1 p 2 p 4 ( 满足p i f f i a i ，对任意1 i t 4 ，1 i 3 m ，所以每个加工时段内恰好有三个 工件( 工件长度之和为t ) 。进而得：实例i 中a 能分成m 个不相交的集合 s l ，s 2 ，s ，使得1 j m ，a es ja i f t 。 充分性：若实例i 中a 能分成m 个不相交的集合s ，s z ，s ，使得1 j m ，a ies ja i = t 。可得实例i 中工件p - ，p 2 p n 能恰好放入m 个加工时 段，而工件p z ，p * ：p i 也恰好使用了m 个加工时段，于是c m a x f f i a l t + ( m _ 1 ) t ，即实例i 中问题的回答是肯定的。 又因为“三元划分问题”是强n p 难的，所以到p 2 i p e r i o d i c - m a i n t e n a n c e l c m a x 问题也是强n p 难的。 第三章带周期性维护时间的平行机排序问题研究 3 3 2 一般情况下不存在常数界多项式时问算法 上节已经证明该类问题单台机情况下有竞争比为2 的最优近似算法，而两台机器 时情况却大不一样，不存在常数界近似算法。 定理3 3 2 ：p 2 fp e r i o d i c - m a i n t e n a n c e l c m a x 问题不存在常数界算法。 证明- 反证法，假设存在该问题一般情况下的常数界( c ) 多项式时问算法 ， 即“( i ) c o r r ( i ) c ，对任意实例i 。 对任一。划分问题”的实例i ： 有2 m 个元素的有穷集合b ，b = ( a ，a ：，a 。) a i z + ，1 i c a c ( t + t + 1 ) c t ，即“二 元划分问题”无解。 于是算法a 可在多项式时间内求解“二元划分问题”，这与“二元划分 问题”为n p 难，矛盾，说明不存在这样的算法 。 即p 2 ip e r i o d i c - m a i n t e n a n c ej c m a x 问题不存在常数界多项式时间算法。 第三章带周期性维护时问的平行机排序问题研究 3 3 3 离线算法及其参数界 由于一般情况下p , 1 p e r i o d i c - m a i n t e n a n c e c m a x 问题不存在常数界算法 自然想到考虑该问题的参数界。这里我们令c 【= t t 算法 ：( 1 ) 将维护时段按图示编号，工件加工对按编号顺序放入维护时段 - - i：i： 二：i( 二： 二： 1 2 l1 4 12 k ) m i一 ( 2 ) 用f f d 算法将工件排序 定理3 3 3 算法a 的参数界为r - - m a x ( 2 ，8 5 + 6o 【5 ) 证明：令符号( i ) 表示b = 2 k ，k + 1 ；( i i ) 表示b = 2 k 。- 1 ，k 1 ； ( i ) 表示b f f i 2 k ，k 1 ；( i i ) 表示b = 2 k - i ，k 1 将排好顺序的加工时段看做箱子，则b 表示用f f d 算法排序时使用的箱子数，b 表示最优算法排序时使用的箱子数。 接下来分四种情况讨论算法a 的参数界： ( i ) ( i ) ：此时c = ( k - 1 ) ( t + t ) + x ，c z ( k - i ) ( t + t ) + y ，其中x t 2 ，y t + t + x 3 t 2 + t ，于是c t 2 ，y c t 因为b 3 b 2 ，于是k 3 k 2 + 1 2 = 2 + 3 ( c 一x ) ( 2 t + 2 t ) c t + t + 3 c 2 - 3 x 2 + y 2 t t 3 = 5 t 3 ，得 c c ( 4 t 3 + t ) ( 5 t 1 6 ) = 8 5 + 6a 5 2 2 第三章带周期性维护时间的平行机排序问题研究 k = 2 ，k = 3 时，c = t + t + x ，c = 2 ( t + t ) + y ，因为x t 2 ，y t ，于是c 2 c k 3 时，c 2 t + 2 t + x s t 2 + 2 t ，于是c o ，y t 因为b 3 b 。2 ，于是k t + t + x 3 t 2 一t 2 ，于是c 2 c ( i i ) ( i i ) ：此时c = ( k - 1 ) ( t + t ) + x ，c ；( k - 1 ) ( t + t ) + y ，其中x o ，y t 因为b 3 b 2 ，于是k 3 k 2 - 1 4 = 3 【1 + ( c 一x ) ( t + t ) 】2 1 4 c 3 c 2 + 5 ( t + t ) 4 - 3 x 2 + y 3 c 2 + 9 t 4 + 5 t 4 k 5 t + 5 t + x 9 t 2 + 5 t 2 ，于是c 2 c 2 3 参考文献 参考文献 【1 】m p i n e d o s c h e d u l in g ：t h e o r y a ig o r i t h m sa n ds y s t e m s p r e n i c eh a l l , 19 9 5 【2 】c s a d f i ，e p e n z ，c r a p i n e ，j b l a z e w i c z ，p f o r m n o w i c z ，a ni m p r o v e da p p r o x i m a t i o n a l g o r i t h mf o r t h es i n g l em a c h i n et o t a lc o m p le t i o nt i m es c h e d u l i n gp r o b l e mq i t h a v a i l a b l i t yc o n s tr a i n ts ，e u r o p e a n j o u n a lo f o p e r a t l o n a l r e s e a r c h , 20 0 5 ，1 6 1 ：3 - 1 0 【3 c y l e e ，s d l i m n s i n g l em a c h i n ef l o w - ti m es c h e d u li n gw it hs c h e d u l e dm a i n t e n a n c e ，a c t si n ，o r m a t j