（运筹学与控制论专业论文）有服务等级约束的平行机排序问题的可中断算法.pdf

摘要 摘要 本文主要研究有服务等级约束的平行机排序问题的可中断算法全文共分三 童 第章是绪论部分，主要介绍了排序问题的相关概念和准备知识，以及对本 文的一个简要概述 第二章介绍了有服务等级约束的平行机排序问题的可中断离线算法我们 首先研究m 台同型机的可中断离线排序问题，并给出了一个时间复杂性为o ( n ) 的 最优算法接着考虑了2 台同类机可中断离线排序问题，给出了一个时间复杂性 为o ( n 2 1 的最优算法 第三章介绍了有服务等级约束的平行机排序问题的可中断在线算法主要考 虑了2 台同型机和2 台同类机可中断在线排序问题，要求服从先来先加工的服务原 则对于2 台同型机在线情形，我们给出了一个最优算法，竞争比为；对2 台同类机 在缉隋形，我们分了两种情况：其中一种情况是2 台同类机中等级较高的机器速度 也较大，此时我们给出了一个最优算法，竞争比为1 + s 万1 i - , 另一种情况是等级较高 的机器速度较小，此时我们给出了一个算法，其竞争比与下界至多相差0 2 2 2 8 关键词：平行机排序，服务等级约束，离线算法，在线算法 a b s t r a c t 焱b s t r a c t t h i st h e s i sm a i n l ys l a l d yp r e e m p t i v ea l g o r i t h m sf o rs c h e d u l i n gu n d e ra g r a d eo f s e r v i c e i tc o n s i s t so f t h r e ec h a p t e r s i nc h a p t e r1 ，w ei n t r o d u c e ss o m en o t a t i o na n dp r e l i m i n a r yf o rp a r a l l e lm a c h i n e s s c h e d u l i n gp r o b l e m i n c h a p t e r 2 ，w c i n v e s t i g a t e t h e p r e e m p t i v e o f f l i n e a l g o r i t h m s f o r s c h e d u l i n g u n d e r ag r a d eo fs e r v i c e f i r s tw es t u d yt h ep r e e m p t i v eo f f - l i n ea l g o r i t h mf o rs c h e d u l i n go n mi d e n t i c a lm a c h i n e s w eg i v ea no p t i m a la l g o r i t h mw i t h i n0 ( 鼹) t h e nw es t u d yt h e p r e e m p t i v eo f f l i n es c h e d u l i n go nt w ou n i f o r mm a c h i n e s a n da no p t i m a la l g o r i t h m w i t ht h et i m ec o m p l e x i t y ( ) ( n 2 ) i sg i v e n f o rp r e e m p t i v eo f f t i n es c h e d u l i n go nt w o i d e n t i c a lm a c h i n e s ，a sas p e c i a lc a n eo f t h ep r o b l e m ，w ea l s og i v ea no p t i m a la l g o r i t h m f o rp r e e m p t i v eo f f l i n es c h e d u l i n go nt w oi d e n t i c a lm a c h i n e s i nc h a p t e r3 ，w ec o n s i d e rt h ep r e e m p t i v eo n l i n e 蜊t h m sf o rs c h e d u l i n gu n d e r ag r a d eo fs e r v i c e ：w em a i n l ys t d yt h ep r o b l e m sf o rt w oi d e n t i c a lm a c h i n e sa n dt w o u n i f o r mm a c h i n e s i nt h e s ep r o b l e m s ，w ec o u l dn o tv i o l a t eab a s i cs e r v i c er u l eo f ”f i r s t - c o m e - f i r s ts e r v e ”，f o rt w oi d e n t i c a lm a c h i n e s ，w eg i v ea no p t i m a lo n l i n ea l g o r i t h m w h o s ec o m p e t i t i v er a t i oi s ；f o rt w ou n i f o r mm a c h i n e s ，t w oc a s e sa l ec o n s i d e r e d o n ei st h em a c h i n ew i t hh i g h e rg r a d eh a sb i g g e rs p e e d ，t h eo t h e ri st h em a c h i n ew i t h h i g h e rg r a d eh a ss m a l l e rs p e e d 。f o rt h ef i r s tc a s e ，w eg i v ea no p t i m a la l g o r i t h m 。f o r t h eo t h e r , w eg i v ea na p p r o x i m a t i o na l g o r i t h m ，t h eg a pb e t w e e ni t sc o m p e t i t i v er a t i o a n dt h el o w e rb o u n do f t h ep r o b l e mi so 2 2 2 8a tm o s t 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 ，g r a d eo fs e r v i c e ，o f f - l i n ea l g o r i t h m ， o n l i n ea l g o r i t h m i i 第一章绪论 1 1 组合优化问题 第一章绪论 定义1 1 1 ：组合优化问题7 r 是一个极小化问题，或是一个极大化问题，它由下述三 部分组成： ( 1 ) 实例集合； ( 2 ) 对每一个实例t 有一个有穷的可行解集合嗣= 【) ； ( 3 ) 目标函数- ，= 它对每一个实例j 和每一个可行解口s 刃，赋以一个有理数 ，( i o ) 如果丌是极小化问题( 极大化问题) ，则实例，的最优解为这样一个可行 解口+ 研刁，它使得对于所有一s f = 【j ，都有，( ，矿) sf ( i ，口) ( f ( 1 ，矿) f ( i ，口) ) 组合优化问题又称离散优化问题，是一类重要的优化问题它的研究对象是 是具有离散结构的最优化问题，在经济管理、生产调度、工程技术和军事方面 有着广泛的应用背景随着计算机科学、管理科学和现代化生产技术等的日益 发展，这类问题与日俱增，越来越受到运筹学、应用数学、计算机科学及管理 科学等诸多学科的高度重视虽然某些组合优化问题有悠久的历史渊源，被费 马( f e r m a t ) ，欧拉( e u l e r ) 等众多著名数学家研究过，但作为运筹学的一个独立分支 而发展壮大起来还是近几十年的事 常见的组合优化问题有分划问题( s e tp a r t i t i o n i n g ) 、排序问题( s c h e d u l i n g ) 、 装箱问题( b i n - p a c k i n g ) 、背包问题( k n a p s a c k ) 、指派问题( a s s i g n m e n t ) 、旅行售 货商问题( t r a v e l l i n gs a l e s m a np r o b l e m ) 、斯坦纳最小树问题( s t e i n e rm i n i m a l t r e e ) 等网络中的组合优化问题还包括最短路问题( s h o r t e s tp a t h ) 、最小生成 树问题( m i n i m a ls p - a n n i n gt r e e ) 、最大流问题( m a x f l o wp r o b l e m ) 、最小费用流问 题( m i n c o s tf l o wp r o b l e m ) 等很多组合优化问题可以转化为整数线性规划( 或混 合整数规划) 问题，但是整数线性规划的求解同样也是困难的，而且组合优化涵盖 甚广，因此人们致力于研究各个问题的组合结构，试图找到一些好的性质和有针 对性的求解方法各种组合优化问题的详细阐述可参考 1 3 】接下来我们将对组 合优化问题之一的排序问题进行介绍 第一章绪论 1 2 排序问题 排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问题排序 问题产生的背景主要是机械制造，后来被广泛应用于计算机系统、运输调度、生 产管理等领域从普通的生产部门的计划安排、人员调度，学校课程表的制定，到 宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法由于它在现实计 算机系统中有多方面的应用，排序问题早已成为理论计算机学界的研究领域之 ，并己拥有大量有趣的积极的和消极的结果近几十年来，排序问题得到了运筹 学界、计算机科学界、工程学界和管理学界极大的关注鉴于经典问题的研究日 益深入，而具有实际背景的新问题又不断出现，可以说，对排序问题的研究正在进 入成熟期 一般的平行机排序问题可以描述为：给定机器集合m = 呐， ) 和工件集合j = ，如，厶) ，需要把礼个工件 ，如，厶分配到m 台机 器 以， 如，尬。上加工其中坞的加工速度为勺( 1 j 茎m ) ， 的加工时间 为鼽( 1 茎i n ) 由于排序问题中的机器和工件都是有限的，绝大部分排序问题 是从有限个可行解中找出一个最优解，使目标函数达到极值在排序问题中，把可 行解称为可行排序，最优解称为最优排序排序者的任务是寻找一个可行排序，使 给定的目标函数达到最小( 极小化目标) 或最大( 极大化目标) 按照学术界多年形成的惯例，一般用所谓的”三参数表示法”( t h r e e f i e l d r e p r e s e n t a t i o n ) a 伊7 来表示一个具体的排序问题 其中血域表示机器的数量、类型和环境，它可以为： 1 ：单机 尸m ：m 台同型机 0 。：m 台同类机 ：m 台变速机 f m ：m 台机器，流水作业 d 。：m 台机器，开放作业 厶：m 台机器，异顺序作业 f f s ：s 类机器，柔性流水作业 我们对上述的同型机和同类机的概念给出进一步的说明在排序问题中，如 果每台机器加工工件的速度相同( 通常设为1 ) ，称为同型机( i d e n t i c a lm a c h i n e ) j j f 一一 第一。章绪论 序如果每台机器的加工速度不尽相同( 经常将最慢的机器的加工速度设为1 ) 。但 是强一露定掇嚣在燕工不同工释的辩候速度麓固定不交的，称秀瓣类辊( u n i f o r m m a e h i n e ) 排序对于上面掇到的其它定义请参考【4 】 口域表示工 孛的特鬣、加工要求和限铡等约束条终，包括王 譬的加王射 闯( p r o c e s s i n gt i m e ) ；工体的到达时间( a r r i v a lt i m e ) 又叫准铸时间( r e a d yt i m e ) 或释放 时i 目 ( r e l e a s et i m e ) ，是指工件可以开始加工的时刻；交货期( d u ed a t e ) 袭示工件的所 寿王痔毂热工波该彗衷懿瓣型；投( w e i g h o 表示工箨懿重簧瞧；鑫王雩| ：在搬工_ ；窭程 中相互之间的依赖关系，比如先后( p r e c e d e n c e ) 约束；工件在加工时能否中断等等 在平行机摊序问题中，如果工件加工可阻中断，即允许将未完成加工的工件 孛藜船工，梳瓣转丽翔工其它熬工侮，两未完成静工俘哥在不阕静税器上继绥麴 工，但必须保诞不重叠，即在同一时刻不能在不同的机器上加工同工件，称这类 捐 序为可中断( p r e e m p t i v e ) 排序如柒不允许中断，一旦王件在菜套机器上开始加 工，斌必须不丽断的一次加工完，称这类捧序为不可中断( n o n p r e e m p t i v e ) 莽 净在 很多实际系统中，例如许多操作系统的调度器，就是利用可中断来平衡每个任务 的等德时阉，从嚣提高系绞瓣响应对闻困扰，可中叛的调发策略爨寿重要的实稼 意义另一方谣，若在可中断的前掇下，还允许并行，即阏个工件臼勺不同部分可 以并行的分配给不同的机器处理，则会导致平凡解( 每谂机器的负载一样大) ，所 以凌喾j 在上繇爵孛瑟接黪豹定义中强镶了不霹并行静条转，帮露一王律懿不嗣部 分必须是不可塑叠的分配到机器上加工的 根据具体排序闽题中对工件信息的了解程度。又可将排序问题分为离 线( o f f i i n e ) 、京线o n n 蛰霸半在线( s e n t io n l i n e ) 簿痔。所谓离线捧廖楚据全部工律 的所有信息在排序时均融知，排序瀚可以充分利用这些信息对工件进行安排在 线撼序是指排痔者只知道当前到达的工件及之藏的工件的信患，焉对接下来靛工 件的信息一无所知，其摹本假设有磷条： ( 1 ) 工件的信息是逐个释放的即工件j 4 1 的信息只有在排序者对工件五， 作 毽安蓑 基才会羧簿痔者疆知 ( 2 ) 工件加工不可改变即一旦排序者将工件安排给某台机器加工，在其后的任何 阶段不能以任何方式改变 还衣大量静实际翊遂是介子离线帮在线两者之阔的，静我们或者知道该瓣蘧黪一 些熬体信息，或者知道后续工件的部分信息例如，已知所有工件的最大加工时 间，不知道每个工 牛的具体船工时间，但与在线阉题相比，这些信息可以弱来镳诗 后鼷工件加工时间的范围，这是有利于算法设计的，我们把这样的摊序称为半在 一3 第一章绪论 线排序 ，y 域表示要优化的目标函数如果记g 为某个排序问题的可行排序中的工 件 的完工时间，则称c r m a x = i l l a x g 为该排序的最大完工时间( m a k e s p a n ) 这就 是某种最优准则下的目标函数，其最优准则为：找一个可行排序，使得它的最大完 工时间c k a x 在所有的可行排序中取得最小值，即极小化目标函数排序问题中的 优化目标还有很多其它的目标函数，常见的有求最小总完工时间g ，最大延误 时间l 最少误工工件数仉等 关于排序问题的更详细阐述请参考【4 _ 6 】等专业论著 4 第一章绪论 1 3 算法、最坏情况界、竞争比 定义1 3 1 ：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一 个清晰描述这里我们仅讨论确定型算法，即算法从前一步到后一步的运行是由 当时的状态唯一确定的如果存在一个算法，它对问题”的每一个实例，在有限 步后，一定可以得到该实例的关于”的提问的答案，那么我们就称该算法解问题7 r 对于一个具体的问题可能会有不同的算法求解，我们希望寻找解问题的最有 效算法通常用计算时间作为衡量标准，也就是说把能最快得到最终结果的算法 称为最有效算法为了排除计算机速度和操作系统等因素，我们总是用算法中所 含的基本运算次数来表示算法所用的时间，这里基本是指加、减、乘、除、比较 等运算由于算法所用的时间跟实例的规模有关，为此我们用输入长度来刻画实 例的规模所谓输入长度是指描述实例所用的计算机内存单元数 定义1 3 2 ：算法时间复杂性是关于实例输入长度n 的函数，( 札) ，用来表示算法的 时间需求对于每一个可能的输入长度，它是该算法解此输入长度的最坏可能的 实例所需的时间( 基本运算步数) 如果存在一个多项式函数p ( n ) ，使得算法的时间复杂性为0 ( p ( 礼) ) ，那么称该 算法为多项式时间算法，否则称为指数时间算法由此可以导出计算复杂性的一 系列重要概念和结论 7 】我们把多项式时间算法称为好的有效的算法，把能用多 项式时问算法求解的问题称为”易解”问题，否则称为难解问题 我们衡量算法的好坏可从两个方面来看，一是算法的时间复杂性，二是算法 得到的解值与最优解值的接近程度为衡量这个接近程度，我们定义最坏情况 界( w o r s t - c a s er a t i o ) 和竞争l t ( c o m p e t i t i v er a t i o ) 求解离线问题和在线问题的算法分别称为离线算法和在线算法分别用最坏 情况界和竞争比来衡量离线算法和在线算法的好坏 定义】_ 3 3 ：对于使目标函数，为最小的离线优化问题7 r ，记是这个优化问题的一 个实例，并记，( ，) 是实例，的最优目标函数值( 即最优值) ，向( ，) 是算法h 的目标 函数值如果存在一个实数r ( r 1 ) ，对于任何实例有 ，h ( ) r ，( n 第一章绪沦 那么称r 是算法的一个上界相应的可以定义目标函数为最大的下界的定义如果 不能确定算法是否有界，或者能够确定算法的上界是无穷大时，这个算法一般称 为是启发式算法当r 是有限数( 不是无穷大) 时，这个算法一般称为近似算法 进一步，设日是极小化目标问题7 r 的一个近似算法，用日解实例j 得到的解值 为扫( n 称 r h = i n f r 1j 由( j ) r ，( n v ) 为算法h 的最坏情况界如果丌是极大化目标问题，则称 t h = s u p r 1i 局( ，) r ，( ) ，w ) 为算法h 的最坏情况界 对于使目标函数，为最小的在线优化问题丌，对在线算法日，用竞争比来衡量 它的最坏情况设f ( 1 ) 是实例，在离线情况下的最优目标函数值( 即最优值) ，则称 7 h = m ， r 1f 向( ，) r ，( ，) ，v y ) 为在线算法日求该问题的竞争比对于极大化在线问题同样可以给出相应的概 念，称 r h = s u p r 1i 届( ，) r ，( n v ，) 为在线算法日求该问题的竞争比 对于一个优化问题”，如果给定任意一个实例，算法h 总能找到一个可行解， 并且这个可行解的目标值总是等于最优解值，则称h 为最优算法 计算复杂性理论的一些重要概念和结论可以参考【7 】 6 第一啦绪论 1 4 论文概要 本文主要研究机器和和工件带有服努等级约束的可中断平行机排序问题在 许多服务行业，像银行业、通信业以及务种网络服务行业，我们经常需要细分服 务市场人群，接行等级差异报务。例如最j 慝海南电信为使客户对海南电信的贡献 与掰享受兹簸务鞠遗盛，提高毫痿客户瓣惫谖瘦稻渍意密，梵客户提供等级蓑 弹化服务对所有商业客户和公众客户裰据其通信消费承平情况，分为l 孓5 s 五 个不同服务等级，释户的服务等级级别根据客户在某一时间段的通信消费情况自 动确认服务级别越高的客户所享受到的各业务服务时限越斑，投诉回复时限越 快，用户回访等特绦服务的频次及周期也姻应比服务级别低的客户高，从而体现 差异纯爨务。 在捧穿运题中，为了体理这穰不同缀剐的服务，一种有效的办法就是给祝嚣 和需要加工的工件划分服务等级( g r a d eo f s e r v i c e ) 我们将每个工件和每台机器都 标注了一个服务等级，只有工件的服务簿级不小于机器的服转等级时才能放在该 机器上加工，目标娥极小化最大完工时间 第二章磅究鸯般务等级约京的平行枫撑拳运题豹可中凝窝线算法对m 台弼 鍪l 枫窝两台露粪裁瓣精形，我翻都给爨了多疆式时闻最饶冀法+ 第三章转两磅究 在线情形，即有服务等级约束的平行机排序问题的可中断在线算法注意到对于 在线情形，可以通道在机器上两个相邻的工件之间引入空闲时间，留待后来的工 件加工使用，而使排序结果更好，读者可渗见文献【8 ；9 】但是遮违背了在每台机 器上先来先加工遮榉一个基本的服务原嬲，所以本文在讨论在线算法时不允许在 麴工过程孛； 天空阑l l 雩润。这一章我嚣l 主绥考虑了2 台嚣型极秘2 台羁类瓿可中颧 往线排序闻题 一7 一 第一二章有服务等级约束的平行机排序问题的可中断离线算法 第二章有服务等级约束的平行机排序问题的可中断离线算法 2 1 引言 在许多服务行业，像银行业、通信业以及各种网络服务行业，我们经常需要 细分服务市场人群，推行等级差异服务在排序问题中，为了体现这种不同级别 的服务，一种有效的办法就是给机器和需要加工的工件划分服务等级( g r a d eo f s e r v i c e ) 将性能越好的机器标记越高的服务等级，需要越高级服务的工件标记越 高的服务等级并且限定服务等级高的机器只能加工服务等级高的工件，而服务 等级低的机器既能加工服务等级低的丁件，又能加工服务等级高的工件这样在 均衡目标下，就可以将性能好的机器留下来加工需要更加高级服务的工件 给定机器集合m = a 矗，m 2 ，) 和工件集合j = ，如，厶) 其 中尬的加工速度为s ，服务等级为9 ( m j ， 的加工时间为p l ，服务等级为9 ( 以) 只 有当g ( ) g ( m j 时，工件 才能放在机器尬上加工由于只有m 台机器，不失一 般性，设有至多m 个不同的服务等级，用整数1 ，m 标记，目标函数为最小化最 大工件完工时间g k a x 称此问题为带服务等级约束的平行机排序问题 不难看出，对于带服务等级约束的平行机排序问题，如果该问题中工件的最 低服务等级不小于机器的最高服务等级，即所有工件都能在任一机器上加工，该 问题可转化为经典的平行机排序问题p | | c k 。和q | | c l 。问题p 竹川c a x 是n p 难 问题，求解此问题的常用方法是近似算法最简单的近似算法是l s ( 1 i s ts c h e d u l i n g ) 算法 1 0 ，由g r a h a m 于1 9 6 6 年首先提出l s 算法是按工件给定的顺序，将每 一个工件分给最早空闲的机器加工它在安排当前工件的加工时不要求知道 下一个工件的信息，因此特别适合用于解在线排序问题另一个常用的近似算 法是最长加工时间优先( 1 0 n g e s tp r o c e s s i n gt i m ef i r s t ，简记l p t ) 规则【1 1 】，它也是 由g r a h a m 提出来的该算法首先将工件按其加工时间从大到小的顺序排列，然后 按此顺序用l s 算法排序它要求工件的信息全部己知后才开始加工，但它比l s 有 较小的最坏情况界对于i l g 。，1 9 7 8 年c o f f m a n 等人还给出了由装箱问题的 一个算法f f d 算法作为子程序的m u l t i f i t 近似算法 1 2 1 9 9 0 年越民义教授证明 了m u l t i f i t 算法的最坏情况界不大于普+ ( p ，且常一、，。，1 3 可改进的【1 3 】 对于工件加工可中断的情形，问题比较容易求解对p p m p t l c m 。， m c n a u g h t o n 1 4 给出了一个时间复杂性为o ( n ) 的多项式时间最优算法 第二章柯服务等级约束的平行机排序问题的可中断离线算法 对q l p m p t g k 。，h o “a t h 等【1 5 】给出了一个时间复杂性为o ( n 2 ) 的多项式时间最优 算法l e v e l 算法 h w a n g 等 1 6 首先引入了有服务等级约束( u n d e rag r a d eo fs e r v i c ep r o v i s i o n ) 的m 台同型机不可中断的离线平行机排序问题由于p m l i 。是p 难的， 显然这个问题也是p 难的他们将g r a h a m 的l 丌算法改进，给出了一个近似算 法l g l p t ( 1 0 w e s tg r a d e - l o n g e s tp r o c e s s i n gt i m e sf i r s t ) 算法算法的最坏情况界： f ； t l g - l 刀2 i ； 并且界是紧的 事实上，1 9 9 5 年a z a r 等在 1 7 】中所讨论的一类排序( s c h e d u l i n gw i t he l i g i b i l i t y ) 跟有服务等级约束的平行机排序有很多相似之处，并且a z a r 等给出了一个解 决这类排序问题的算法a w 算法该算法的最坏情况界不超过l o g 。2 m ，这个界是 一个随着m 递增的函数l e n s t r a 等在 1 8 】中对于工件集不相关的一般排序问题给 出了一个基于线性规划的算法( b i n a r ys e a r c ha l g o r i t h m ) ，其中a z a r 等在 1 7 】中提 到的排序是该问题的一个特例该算法的最坏情况界是常数2 ，但是算法中引入了 一个线性规划模型，其计算复杂性未被证明是多项式时间可解的， 本章我们讨论的是有服务等级约束的平行机排序问题的离线可中断算法其 中第二节研究m 台问型机可中断的离线情形，给出了一个多项式时间最优算法， 时间复杂性为0 m ) 第三节研究2 台同型机可中断的离线情形在此情况下，不 失一般性，可以假设g ( 尬) = i ，i = 1 ，2 因为如果两台机器的服务等级相同，问题 就转化为经典的平行机排序问题q 2 p m p t l c 。2 台同型机可中断的离线情形我 们分两种情况： 情况a ：尬的速度为1 ，m 2 的速度为s ( s 1 ) ； 情况b ：m a 的速度为s ，m 2 的速度为1 对于两种情况，我们给出了个统一的多项式时间算法，时间复杂性为0 ( 4 2 ) ，并 且分别证明了算法在情况a 和情况口卜均是最优的 9 2 3 = 一 m m 击 第二帝有服务等级约束的平行机排序问题的可中断离线算法 2 2m 台同型机离线最优算法 给定机器集合m = m 1 ，捣，) 和工件集合j = ，也，厶) 在本节中，我们令所有机器的速度都是1 ，设机器和工件都有个服务等级， 1 m 假设前m 1 台机器服务等级为1 ，第m 1 + 1 到第m 1 + 2 台机器服务等 级为2 ，最后”女台机器服务等级为，m l + m 2 + + ”= m 设前“1 个工件 服务等级为1 ，第n 1 + 1 到第n 1 + n 2 个工件服务等级为2 ，最后n k 个工件服务等 级为女，n 1 + n 2 + + ”女= n 为表达方便，记服务等级为i 的工件的加工时间总和 为正令g = m a 碧，。t 】i + + t 2 ，鲁玉，m a x l 9 鱼仇) 2 2 1 最优值的下界估计 对于有服务等级约束的m 台同型机离线可中断排序问题，我们证明以下引理 引理2 2 1 ：对于有服务等级约束的m 台同型机可中断的离线平行机排序问题，最 优算法的目标函数值c o p r c 证明：对任意的f ，1 f 自，因为我们记服务等级为i 的工件的加工时间总 和为噩，所以等级小于等于z 的工件的总长度可以表示为：一，正为了保证 任一工件都在服务等级不大于它的服务等级的机器上加工，服务等级不超 过z 的机器要把服务等级4 i 超过f 的工件全部加工完毕，所以加工的工件的 总长度应至少是2 。正由于共有m l + + m l 台等级不超过2 的机器，所 以c o p t 而音毒幸；与丽，1 曼f 另一方面，为了保证任一工件不会在同一时刻 被两台机器同时加工，必须有g b p r m a x l i 。仇综上得c o 尸r c 2 2 2 算法 下面我们给出一个算法日1 ，是对求解p l p m p t l c k a x 问题的最优算法 1 4 】进行 改进所得 算法h 1 ： 1 计算e = m “ 鲁，鲁擐，帮，m a x - 。9 a ) 2 将n 个工件按照 ，以，厶的顺序排成一列，其总长度等于n 个工件的加 工时间之和且不超过m c 一1 n 一 第二章自服务等级约束的平行机排序问题的可中断离线算法 3 把上述序列分成m 部分，第一部分为【0 ，q ，第二部分为 g ，2 c ，第m 部分 为【( m 一1 ) c ，m c 4 把第一部分 o ，q 的排序作为尬的排序，把第二部分【e ，2 q 的排序作 为尬的排序，把第m 部分【( m 一1 ) c ，m a 的排序作为的排序 2 2 3 算法分析 首先我们分析一下算法研的时间复杂性对于算法玩，第一步中g 共包 含k + 1 = 0 ( m ) 项，计算每一项需要的时间为0 ( n ) ，所以计算c 所需的时间 为o ( m n ) = 0 ( n ) 而其它几步求解p i p 仃班l 瓯a x 的算法，时问复杂性都不超 过0 ( n ) 所以日l 的时问复杂性为o ( n ) 下面我们分析算法凰的可行性，可行性包含两个内容：一是根据可中断排序 的不重叠性，在任意时刻任一工件至多只能在一台机器上加工，二是根据等级约 束，任一工件不会在等级比它的等级大的机器上加工 定理2 2 1 ：算法且是可行的，从而是最优算法 证明：根据算法，每台机器上至多只有最后一个工件可能中断加工，且该工件的 剩余部分在下一台机器的零时刻加工由于c m a x l c t c 。p l ，所以任一中断的工 件不会在同一时刻被两台机器同时加工 下证所有工件的确在满足服务等级约束的前提下，可以在c 时刻以前加工完 毕我们首先考虑等级为l 的工件，其加工时间总和为噩根据等级约束，它们只 能在等级为1 的机器上加工，即只能在前m 】台机器上加工而前m 。台机器在g 时 刻前可完成的工件的总加工时间为m l c2m 1 黑= 五，所以算法使等级为1 的工 件都在等级为1 的机器上加工考虑等级为2 的工件，它们既可以在等级为1 的机 器上加工，又可以在等级为2 的机器上加工同时，前m 1 + m 2 台等级为l 或2 的 机器在c 时刻前剩余的总时间为( m l + m 2 ) g 一五( w t ，+ m 2 ) 三圭黑一五= t 2 ， 所以算法使等级为2 的工件都在等级不超过2 的机器上加工一般地，e 而砉嚣兰与面，1 茎f 茎可保证等级不超过f 的工件都在g 时刻前在等级不超过f 的 机器上加工完毕综上可知算法h l 是可行的根据引理2 ，2 1 ，最优目标函数 值c o p t c ，又算法h 。产生的目标函数值c h = c 从而研是最优算法 第_ _ 二章霄服务等级约束的半舒机撵序阀逛的可中断离线萁法 2 32 台同类鞔离线最优算法 不失一般性，假设在工件集合j 中，前札1 个工件等级为1 ，第佗1 + 1 到第n 个工 件等级为2 ，在2 1 节中，我们提到把2 台阿炎机离线情形分两种情况：情况a ：m 的 速度为1 ，m 2 酌滚淡y 口s ( s 1 ) ；情况嚣：强的速度为s ，a 是豹速度为t 下箍曾先 绘窭令算法强，然舞砖嚣静薅嚣分蘩麓开讨论 2 3 算法 算法2 ： 先将等级为1 豹工件按任意次序放穗魑上如工下面利用l e v e l 算法【1 5 】分配 等级舞2 豹工磐 1 梅造分享排序 1 1 若所有工件都已加工完毕，转2 否则将每个未加工究的工件在某一时刻 剩余部分记为该工件此刻的l e v e l ，设具有鼹高l e v e l 的工件有“个 若o f = 1 ，将这个具有最高l e v e l 的工件分给速度快的机器加工。另一台机器用 寒麴i l e v e l 次之戆下譬 ( 毽是在m x 未熬王宠等级为l 熬工黪之藏，诀为更奏磊磊愚 空阕的， 若口2 ，将遮n 个工件分给两台机器联合n i ( 在炳未加工完等级为1 的工 件之前，只在 如上联合加工) 这里联合加工是指在某个区间，我们指定几个工件 在这个区间内共同加工，并且要求它们在这个区间内加工榈同的长度，或者可以 谈交它们在这个送闫蠹其有籀嗣的翔王速度，但是并没商髓确舆体的撵净方式。 我稻称毙时蕊撵垮为分享撵痔。 1 2 当有下列情况出现时，转1 1 等级为1 的工件全部加工完毕或菜个等级为2 的工件加工完毕 两个原来l e v e l 不相等的工件由于加工速度不同达到了棚等 2 由分享撵廖构造具体薅_ 亭。 修改1 中嚣鸯联台青鞋工静区阗，设蘩个联合鸯鼙工懿区闻淹嬲工懿工律懿个数 为卢，则将这个区间分成p 个相等的予区间若只有一台机器参与联合加工，将口个 子区间分给这胆个= i = 件，每个工件一个。菪两台机器参与联合加工，两台机器上的 对应区间都被分成了口个子区间，各给每个工件分配一个，并适当安排，使得两白 机器上分给同一个工传酌时间段不重爨， 一1 2 一 第二章有服务等级约束的平行机排序问题的可中断离线算法 易见算法岛的时间复杂性由等级为2 的工件决定，而等级为2 a - 件是按 , n , , l e v e l 算法排序，所以飓的时间复杂性就等- j ：l e v e l 算法的时间复杂性o ( n 2 ) 2 3 2 情况a 分析 对于情况a 我们能够得到以下一些结论 引理2 3 ，1 ：对于情况a ，最优算法的目标函数值c 6 m a x t 1 ，t 。i + + t 1 2 ， m a x n l + 峰 n 譬) 证明：因为服务等级为1 的工件必须放在炳上加工，所以c b 日蜀若两台 机器同时完工，所需加工时间为哿孕，而最大完工时间是最后完工的机器所 用的时间，所以c b 刀马导成立r h 于任一等级为2 的工件j i ( n l + 1 茎i n ) 在同一时刻至多只能在一台机器上加工，加工完毕所需的时间至少为譬， 所以c o p t 譬，住l + 1 i n ，从而c b p t m a h l + l 兰i 鱼譬综上c b p t m a x t 1 ，嗉学，m a 1 + 1 蜓。譬) 定理2 , 3 2 ：对于情况a ，算法岛产生的目标函数值c 也= m a x t 1 ，t 。i + + t 1 2 m a 而。十1 1 。如譬) ，从而是最优算法 证明：注意到在算法日2 中分享排序和具体排序有相同的完工时间，为了简化证 明，我们下面只考虑分享排序算法上如解任一符合情况a 的实例，有下面三种可 能， 1 脑在 如之后停机下证尬上只有等级为1 的工件反证，假设m 上有等 级为2 的工件则由算法规则，它们在 以上都排在所有等级为1 的工件后面加工 那么在尬停机后尬加工的工件中必定包含等级为2 的工件，将这些工件全体记 为j ，但是由于 如的速度比尬大，按照算法，会首先考虑分给速度大的，而 不会只分给而不分给 毛加工假设与算法矛盾，所以m 1 上只有等级为1 的工 件此时c m 等于m 的完工时间，即c 镜= 丑 2 尬，m ：n 时停机此时显然有c 鼻。= 丑s 皿+ 1 3 如在 矗之后停机记尬的停机时刻为t o 首先我们证明 如在t o 时刻后加 工的工件只有一个如果有两个以上工件，则按照算法规则，不论它们的l e v e l 是否 相等，两台机器均会在t o 时刻后仍在加工工件，矛盾所以 如在t o 时刻后加工的工 件只有一个，将它记为以 第二章有服务等级约束的平行机排序问题的可中断离线算法 根据算法，当两个等级为2 的工件有相同的加工时间或相同的剩余加工时间 时，它们有相同的l e v e l ，那么接下去它们将会被联合加工，直到同时完工这说 明任一工件不会在比它的加工时间短的工件之前先完工既然以最后完工，所 以以的加工时间最长，即m = m a x n 。+ l 。 。p 1 由于以的加工时间最长，即在0 时刻具有最高的l e v e l ，所以从0 时刻开始以就 被分给 岛加工如果在以加工过程中有别的工件在某个时刻( 剩余) a n 工时间 超过以的剩余加工时间，那么接下去它们将被联合加工，直到同时完工但是 这与九是唯一一个最后完工的工件矛盾，所以直到最终工件加工结束，没有 工件的( 剩余) a n 工时间超过 的剩余加工时间，也即 始终是l e v e l 最高的唯一 一个工件由算法，速度大的机器只加工了一个工件以所以魄= 譬= m & x , a 1 + l ! 。如譬 综上我们得到结论c k = r a a x t 1 ，写子，m a j c n ，+ ! t 。譬) ，从而凰是最优算 法 2 3 3 情况_ 口分析 分析情况b ，我们能够得到以下一些结论 引理2 , 3 3 ：对于情况b ，最优算法的目标函数值一m a x 争，哿 ，( ；一 击) 正+ m “。+ l 孕，构造工件集j = ，如，厶，以) 注意情形b 下机器尬的速度 为s ，大于机器尬的速度且 ，也， ，只能在尬上加工所以，的最优排 序为：将 ，如，厶。放在m 上加工，将以先分给 毛加工，然后当等级为1 的 工件在舰上加工完毕后，再将以的剩余部分分给尬继续加工从而最优值 为孚+ 丝= ( j 一嘉) 乃+ m s m n 。+ 1 9 9 譬因为l ，j ，所以工件集j 的最优值 不小于工件集l ，7 的最优值，从而 砣孚+ 学= ( 三一言) 孙时m a x 81 蜓。堕8s ss “1 + 三4 三“ 1 4 第二誊奇服务等级约束的平行机摊序阚题龅可中断璃缝算法 定理2 3 4 ：对予精凝雷，算法岛产生麓健= m 巍x 蛩，2 ；警，( ；一主) 噩+ m a x n l + 1 1 。9 警 ，从而是最优算法 证明：我们仍旧考虑分享排序，由于a 矗的速度比a 1 2 的速度大，按照算法，m 2 不可 能在蝇之后停机，所以算法岛解任一符合情况b 的实例，有下灏两种可能 1 。麓彝立磊霹辩势援，霓薅显然毒e 致= 每譬。 2 尬在之后停枕如果蝎土只移等级为1 的工件，贼c 巍一孚如果甄上 有等级为2 的工件，皿0 类似于定理2 3 ，2 中3 的证明，我们能得到以下结论：惦上最 后完工的工件是等级为2 的最长工件，记为以由于以零时刻的l e v e l 最大，所以矗从 零时刻开始先分给此时唯一空闲的机嚣加工，一旦强上簿级为l 的工件加工 囊毕，裁转移到a 磊主继续翔工妻囊箨极。没有其它等级势2 麓王终分跨甄与磊联 台热工，因为这会与兹是最后完工的难一个工件矛蘑掰淤我们可知c m 裁等 于以的加工时间，即g 镜= 警+ i 掣一( 一言) 丑+ m a r c n h l l 如譬 综上即知c 一m 觚 孚，2 ；轷，( 一嘉) 五+ m a x 。1 + - ! i 如警) ，h 2 是最优算法 1 5 第= 章有服务等级约束的平行机排序问题的町中断在线算法 第三章有服务等级约束的平行机排序问题的可中断在线算法 3 1 引言 在第2 章中我们讨论了几种离线情形，这一章主要研究在线算 法，在没有服务等级的约束下，关于可中断在线平行机排序已有不 少很好的结果对p m i p m p t ，o n l i n e c m 。，c h c n - 等 1 9 给出了一个最优算法， 竞争比 。m m ，。= 而i ，当m 趋向于无穷大时，该表达式趋向于音“1 5 8 对q 。i p m p t ，o n l i n e i a x ，目前并未得到完全解决，现在只对2 台机器已给出最 优算法w e n