（运筹学与控制论专业论文）带服务等级的在线排序问题及相关问题研究.pdf

摘要 摘要 现代工业的快速发展产生了越来越多新的组合优化模型，带服务等级的排序 问题是其中一个重要分支，近年来受到了许多学者的关注本文主要研究带服务 等级的在线平行机排序问题全文共分为五章 第一章首先介绍了排序问题的基本概念，基本理论以及近年来取得的研究 成果，接着描述了带服务等级的平行机排序问题并给出了相关符号和定义 第二章研究m 台同型平行机带一般服务等级的排序问题对工件可分模型， 设计了基于数学规划的在线算法和问题下界，数值计算表明，对于任意给定 的仇，这类算法的竞争比均能达到问题的下界接着，考虑了工件不可分模型， 给出了任意m 台机器的一般在线算法和在m = 3 ，4 ，5 时具有更好竞争比的改进算 法，证明了一般在线算法的竞争比与对应可分模型的算法竞争比相差至多为1 第三章研究m 台同型平行机带两个服务等级的排序问题对工件可分与单位 工件模型，分别给出了竞争比为静熹与；的在线算法，并证明了对任意机 器数m 和任意的等级分配七，算法都是最优的进一步，考虑了不可分模型，设 计了一个竞争比为l + 杂 的在线算法，从而降低了该问题的已有上 界，又对某些m 和k 的组合提出了另一个改进算法此外，还证明了在k 3 以 及m ；( 惫+ 1 ) 时任何在线算法的竞争比都至少是2 ，以及其他一些m 和k 组合下 问题的下界 第四章研究两台同类平行机带服务等级的排序问题，给出了与两台机器 的速度之比s 相关的最优在线算法当0 8 1 时，算法的竞争比为r a i n 1 + s ，2 4 - 2 s q - 一s 2 ；当s 1 时，算法的竞争比为m i n 丁l + s ，可l + 酉3 s + 万s 2 ) 第五章研究两类在线购物券优惠消费问题，该问题具有实际背景，且与排 序问题、装箱问题有着密切联系首先考虑了折扣券消费模型，针对允许购买的 折扣券数目的不同，分别给出了不同的在线消费策略( 算法) 和问题下界，并证 明了这些策略对所有折扣率在允许购买任意张、至多一张或者两张折扣券的情 况下都是最优的接着，研究了单张抵价券消费模型，证明了该模型的在线情形 是无穷下界的，对于已知总支出额度预算情形，设计了依赖于预算大小的消费 策略，并证明了这些策略与最优策略的竞争比相差不超过0 1 2 9 关键词：排序问题，在线，算法设计与分析，等级 a b s t r a c t a b s t r a c t r a p i dd e v e l o p i n gm o d e mi n d u s t r yi sg i v i n gb i r t ht om o r ea n dm o r en e wc o m b i - n a t o r i a lo p t i m i z a t i o nm o d e l s o n ei m p o r t a n tb r a n c hi st h es c h e d u l i n gp r o b l e mw i t h h i e r a r c h ys e t t i n g s ，w h i c hh a sr e c e i v e dm a n yr e s e a r c h e r s a t t e n t i o nr e c e n t l y t h i st h e - s i sm a i n l ys t u d i e so n l i n ep a r a l l e lm a c h i n e ss c h e d u l i n gw i t hh i e r a r c h ys e t t i n g s f i v e c h a p t e r sa r em a d e i nc h a p t e r1 ，w ef i r s ti n t r o d u c es c h e d u l i n gp r o b l e m ，w i t ht h eb a s i cc o n c e p t i o n ， t h e o r ya n d r e s u l t si n c l u d e d ，t h e nw eg i v ea d e s c r i p t i o nf o rh i e r a r c h i c a ls c h e d u l i n gp r o b l e m ，a sw e l la sr e l a t e dn o t a t i o n sa n dd e f i n i t i o n s c h a p t e r2s t u d i e sg e n e r a lh i e r a r c h i c a ls c h e d u l i n go nmp a r a l l e li d e n t i c a lm a - c h i n e s f o rt h ef r a c t i o n a lm o d e l ，w eg i v eb o t ho n l i n ea l g o r i t h ma n dl o w e rb o u n db a s e d o ns o l u t i o n so fm a t h e m a t i c a lp r o g r a m m i n g f o ra n yg i v e nm t h ec o m p e t i t i v er a t i oo f o u ra l g o r i t h ma c h i e v e st h el o w e rb o u n db yn u m e r i c a lc a l c u l a t i o n n e x tw ec o n s i d e rt h e i n t e g r a lm o d e l w h e r eb o t hag e n e r a la l g o r i t h mf o ra n ym a n da l li m p r o v e da l g o r i t h m w i t hb e t t e rc o m p e t i t i v er a t i o sf o rm = 3 ，4 ，5a r ep r e s e n t e d w es h o wt h a tt h ec o m p e t i - t i v er a t i oo ft h eg e n e r a la l g o r i t h mi sa tm o s to n em o r et h a nt h a to ft h ea l g o r i t h mf o rt h e c o r r e s p o n d i n gf r a c t i o n a lm o d e l i nc h a p t e r3 w ei n v e s t i g a t eo n l i n eh i e r a r c h i c a ls c h e d u l i n go nm p a r a l l e li d e n t i c a l m a c h i n e sw i t ht w oh i e r a r c h i e s f o rb o t ht h ef r a c t i o n a lm o d e la n dt h em o d e lw i t hu n i t j o bs i z e ，o p t i m a la l g o r i t h m sa r eg i v e n ，w h i c hh a v ec o m p e t i t i v er a t i oo f 万a n d lr e s p e c t i v e l y m lt l l ea l g o r i t h m sa r ep r o v e dt ob eo p t i m a li nt h es e n s e o fa n yn u m b e r o fm a c h i n e sma n da n yh i e r a r c h ys e t t i n g s 后i n t e g r a lm o d e li sa l s os t u d i e d w ed e s i g n a no n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i o1 + 鬲e m 历z - - 丽t t l , i ，w h i c hi m p r o v e st h e p r e v i o u su p p e rb o u n df o r t h ep r o b l e m t h ep e r f o r m a n c ef o rs o m ep a i r so f 后a n dm i s f u r t h e ri m p r o v e db ya n o t h e ra l g o r i t h m b e s i d e s ，i ti ss h o w nt h a ta n yo n l i n ea l g o r i t h m i sa tl e a s t2 - c o m p e t i t i v ew h e n 七3a n dm 3 ( k + 1 ) a n dl o w e rb o u n d sf o rs o m e o t h e rp a i r so fma n dka r ea l s oo b t a i n e d c h a p t e r4d i s c u s s e so n l i n eh i e r a r c h i c a ls 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 w e p r e s e n to p t i m a lo n l i n ea l g o r i t h mw i t hr e s p e c tt ot h es p e e dr a t i o8o ft h em a c h i n e s f o r 0 夕f 的那些机器定义p f 的加工长度为无穷大 即可由此可见，不同类机器排序问题比带服务等级排序问题更为一般另一方 面，当所有工件的服务等级都相同时，不难看出，带服务等级的排序问题就退 化为经典的同型机或同类机排序问题了 此外，文献中还有一类带机器权限( m a c h i n ee l i g i b i l i t yr e s t r i c t i o n s ) 的平行机 排序问题，该问题中每个工件p j 都有一个独立的允许加工的机器集合m f ，称 为加工集( p r o c e s s i n gs e t ) 这里加工集一般可以是机器集的任一子集，而文献 中还常研究它的两类重要的特殊情形：嵌套( n e s t e d ) j j h 工集和包含( i n c l u s i v e ) j j i 工集对于任意两个加工集m f 和m 忌，如果是嵌套加工集情形，则必有条 件m ，nm 七= d ，m f m k 和m m j 之一成立：而如果是包含加工集情 形，则要么m ，m j c ，要么m k m ，事实上，容易发现包含加工集也属于嵌 套加工集，而带服务等级的排序问题则与包含加工集的情形等价关于带机器权 限的排序问题研究可参看文献【3 ；2 8 ；2 6 ；4 7 等或综述文献 4 2 1 1 5 论文概述 本文主要研究带服务等级的在线平行机排序问题在第二章中，我们研 究m 台同型机带一般服务等级的在线排序问题，对工件可否分割两种模型分别 给出了基于数学规划的算法和下界第三章主要考虑m 台同型机带两个服务等级 的情况，对可分模型、单位工件模型以及不可分模型，分别得到了改进算法或 者最优算法第四章研究两台同类机带服务等级的排序问题，我们给出了任意机 器速度的最优算法在第五章，我们考虑购物券优惠消费问题，研究了折扣券和 抵价券两种不同模型，并分别给出了针对各模型的消费策略和下界全文主要结 果可参看表1 2 一6 一 第章绪论 为方便叙述，我们将在本文中用m 和歹分别表示机器和工件集合文中主要 考虑同型机和同类机两种类型，工物在机器坛上加工所需的加工时间为警， 其中8 i 表示机器尬的速度由于我们主要研究在线算法( 不妨通用a 代替) ，所以 在后面的章节中，如无特殊说明，将一直沿用下面的记号 前j 个工件的加工长度总和即乃= ：1p k 枥个工件中加工长度最大的工件，歹= l ，2 ，佗，即p 尹积= m a x ，p k 莉个工件中服务等级为i 的工件集合，j = 1 ，2 ，佗，于是i 就表示所 有服务等级为i 的工件全体 前j 个工件中所有服务等级为i 的工件的总加工长度，歹= 1 ，2 ，佗，即 乃t = ip k ，于是死i 就表示所有服务等级为i 的工件的总加工长度 机器 么在算法a 晗好分配完第歹个工件时的完工时间( 或称机器负载) ， j = 1 ，2 ，佗，i = 1 ，2 ，m 另假设= 0 ，i = 1 ，2 ，m 算法a 在恰好加工完第j 个工件时的目标值，j = i ，2 ，佗，于是c a = l 0 由前歹个工件组成的实例的离线最优值，即最优排序( 最优解) 的目标函数 值，歹= 1 ，2 ，佗于是c + = e 一7 乃矿 丐 日 譬譬 第一章绪论 问题结果所在章节 给出竞争比为线性规划最优值1 ( ”) 的算法 2 2 1 给出非线性规划最优值p ( “) 的下界 2 2 2 p m ，9 = m i ，r n c i c m 。 数值计算表明，y ( m ) = p ( m ) 且趋向于e ( ，y ( m ) 的具体取值见第二章表2 1 ) 2 2 3 竞争比为1 ( ) + 1 的诱导算法 2 3 1 p m ，g = m | | c m 。 m = 3 ，4 ，5 的改进算法，竞争比分别为2 ，2 3 3 ，2 6 1 2 3 2 p m ，g = 2 f r a c c m 。竞争比为磊岛的最优算法 3 2 p m ，g = 2 p j = l c m 。 竞争比为鲁的最优算法 3 3 给出竞争比不超过1 + 韶的算法 3 4 1 p m ，g = 2 i | c m 。 给出七3 ，m ( 尼- 4 - 1 ) 时的问题下界2 以及其他 3 4 2 一些m 和k 组合的问题下界( 详见第三章表3 1 ，3 2 ) 0 s m a x k m a x ，。- 磐砑凹) 引理2 2 2 ：记q 元列向量1 = ( 1 ，1 ，1 ) t ，并记c = ( c 1 ，c 2 ，c 口) 为一q 元行向 量如果存在一个q 阶可逆矩阵a = ( ) q g 满足c a _ 1 0 ，则对于任意g 元列向 量x ，都有 c x ( c a 以1 ) m a x o r l x ，眈x ，o l q x ) ， 其中q i 为矩阵a 的第i 行向量 一1 0 一 第二章带般服务等级的在线同型机排序问题 证明：因为a 可逆，所以显然c x 可以写成为c x = ( c a 1 ) ( a x ) 又根据条 件c a _ 1 0 ，于是有 c x = ( c a 一1 ) ( a l x ，a 2 x ，o q x ) ? ( c a 一1 1 ) m a x a l x ，o l 2 x ，q q x ) 一 2 2 1 基于线性规划的算法l p 我们对可分模型的在线算法是基于一个线性规划的最优解，对于确定 的m ，算法的竞争比显然要好于b 册n o y 等人的结果【5 】同时，算法对工件的安 排十分简洁：服务等级相同的工件将按照同样的比例在机器集上分割加工 具体地，对任意给定的m ，我们首先考虑下面的线性规划问题： ( l p ( m ) ) m l i l 7 m j = 1 ，m ，( 2 1 ) i x 税+ x i j 7 ，i = 1 ，仇， ( 2 2 ) j = i + l 注意到上述线性规划共有芷产+ 1 个非负决策变量以及芷产个约束条件，且 不难看出 x i i = 1 ，i = 1 ，2 ，m ，x o = 0 ，i 一 一u 叼 z o 第二章带一般服务等级的在线同型机排序问题 算法l p ： 设当前到达的工件为以，加工长度和服务等级分别为p 七以及g k = j ，则在机 器尬，m 2 ，坞上加工该工件，且在坛上的加工长度为z 铲p k ，i = 1 ，j 定理2 2 3 ：对带服务等级的排序问题p m ，夕= m l f r a c i c m 。茁，算法l p 总能在多 项式时间里得到可行排序，且算法l p 的竞争比为7 ( 川 证明：注意到算法总是将服务等级为j 的工件分配到前j 台机器上，并且等级 为歹的工件p k 在莉台机器上加工的长度总和为名1 爿j m p k = p k 量1z 垆，又根 据( 2 1 ) 式，就有：1x 。( m ，p k = p k 所以l p 必能给出可行排序l p 的时间复杂性 主要在于求解线性规划，而我们知道线性规划是多项式时间可解的，因此我们 的算法也是多项式时间的 我们用第一章约定的记号磁表示算法结束时尬的负载，i = 1 ，m ， 于是c l p = m a x 磁因为只有服务等级不小于i 的工件才会被l p 安排到机 器尬上，又考虑到l p 的特殊性，即等级相同的工件在机器上分割加工的比例 也完全相同，所以就有， l ：= z ，i = 1 ，m j i 不失一般性，设c l p = 玩 记x ( 1 ) = ( 死i ，死，件1 ，死m ) t 以及c ( ) = ( z 妒，z 饼1 7 一，z i m m ) ，贝u c r c l p = c ( t ) x ( t ) 令 一1 2 一 、l 0 0 l m 0 0 磊 一1 1 o。一；。一m 三；。一 。一m ，-。 = a 第二章带一般服务等级的在线同裂机排序问题 为( m i + 1 ) 阶矩阵，则a ( ) 可逆，且其逆矩阵为 注意到 a 裔= i00 - ii + 1 0 0 - ( i + 1 1i + 2 00 o0 0 0 o 0 仇一1 0 0 一( m 一1 ) m c a i = ( 妒一z 5 僻。) ，( z + 1 ) ( z ：磐，一z ：磐。) ，( m 1 ) ( z ：2 。一z 暨) ，m z 器) ， 再根据( 2 3 ) ，就有c ( ) a 葛0 另一方面，由引理2 2 1 可得， g = ，嚣；静倒m ，3 2 ( ，m 凄- = 纠，m 一a x 。懈， 其中a 玎表示矩阵a ( i ) 的第歹行向量于是根据引理2 2 2 的结论可知， c l p = c x ( c ( 1 ) a i 1 ) 触m 一一a x ；十o g i j x ( c a 嚣1 ) q 最后我们再利用规划l p ( m ) 中的约束( 2 2 ) ，对于任何i ， c ( t ) a i 1 = z z ：? + z ：磐1 + + z 器7 m 因此就得到了e l p 7 ( m g ，即算法三p 的竞争比为7 ( 仃 - 2 - 2 - 2 基于非线性规划的问题下界 下面考虑p m ，g = m l r a c l 船问题的下界，我们也将利用一个非线性规 划n l p ( m ) 来给出问题的下界 定理2 2 4 ：对于带服务等级的排序i b - 题p m ，g = m l r a c l c , m 茁，任何在线算法的 一1 3 0 0 0 第二章带一般服务等级的在线同犁机排序问题 竞争比都至少是p ( m ) ，这里p ( 仇) 是下述非线性规划l p ( m ) 的最优值： m a xp 1 j ( 舭p ( m ) ) s t 鼽怕+ 1 飞却倒m ，a x ，l - p 。“，册，( 2 4 ) p21 ，胁0 ，i = 1 ，m ， q l = q m + l = 0 ，吼0 ，i = 2 ，m 证明：由于 鼽= 1 ，i = 1 ，m ，q i = 0 ，i = 1 ，m + 1 ，p = 1 】 显然是l p ( m ) 的可行解，所以l p ( m ) 的可行域不会是空集于是可令 蠢川，i = 1 ，m ，q 川，i = 1 ，m + l ，j 9 ( m 】- 为l 尸( m ) 的一个最优解为证明p m ，g = m l f r a c l c 。z 问题的下界，我们考 虑m 个工件组成的序列，其中第z 个工件加工长度为p 辨i + 1 ，服务等级为m i + 1 ，i = 1 ，m f h 弓i t n 2 2 1 可知，前i 个工件的最优值为 q 。七当黑# 晶。：三。p 肚m 扎a x ，m 了1 。：三。p _ 1 ，m ( 2 5 ) 以下我们将用数学归纳法证明：对任意i ，1 i m 一1 ，任何竞争比小 于p ( m ) 的近似算法a ，必在前i 个工件中选择总加工长度至少为掣i + 1 的工件或工 件部分安排在前m z 台机器尬，一 上加工 对i = 1 ，如果算法a 在前面m 一1 台( 即除以外) 机器上加工第一个工 件的总长度少于拶，则不再来其他工件于是a 产生的排序目标值将至少 为p 船) 一招，结合( 2 5 ) 式以及( 2 4 ) 式可得 罢盟p r o 型( m ) 刈m ， c ：一 。厂 即算法4 的竞争比至少是p ( m ) ，矛盾! 所以结论在i = 1 时必然成立 1 4 第二章带一般服务等级的在线同型机排序问题 假设结论对i 成立，我们考虑第i + 1 个工件到达的情形注意到第i + 1 个工 件的加工长度和服务等级分别为p 裂i 和仇一i ，并根据归纳假设，可知此时在 前m i 台机器已经加工和将要加工的工件和工件部分的总长度至少为铡。+ ，+ p 裂 如果a 将其中少于掣l 的部分安排到前m i 一1 台机器尬，一i 一1 上 加工，则工件序列终止而此时机器一 的负载将至少有p 裂t + 掣件1 一q 裂i ， 根据( 2 5 ) 式以及( 2 4 ) 式，我们可以得到， 伊掣i + 掣州一龆圳细m a x 椰g 。妻。) = 四 因此算法a 的竞争比将不小于p ( m ) ，与假设矛盾! 矛盾表明，a 在前m i l 台 机器上的加工总长度至少为口婴；，即结论对i + 1 时也成立于是根据归纳法原 理，结论对任意1 i 仇一1 成立 最后考虑第m 个工件p ：叫到达，因为其服务等级为l ，所以只能选择机 器尬加工再根据上面的结论可知，此时的负载将不少于p + 9 5 m ，从而 由( 2 5 ) 式以及( 2 4 ) 式，就有 c a + - - 抄，i - - - - m l , a x - , m ( 三妻= ) 刮确g 于是4 的竞争比仍然不少于p ( m ) ，定理得证 2 2 3l p 的最优性讨论 我们已经给出了p m ，g = m l l r a c l a z 问题的算法和下界，当m 2 为确 定值时，算法和下界所依赖的两个规划l p ( m ) 和三p ( m ) 显然都能求解，例如 当m = 4 时，l p ( 4 ) 和l p ( 4 ) 的最优解分别为 z 兽= 1 ，z 兽= 西1 4 ，z 掺= 百1 ，z 搀= 。，z 身= z 舞= 西1 3 ，z 搿= 去， z 绺= z 终= z 辨= 互1 1 ，v ( 4 ) = 两4 4 ) 一1 5 第二章带一般服务等级的在线同犁机排序问题 以及 蹦一骘= 珞。一 k = i + lk = lk = i + l 即此时( i i ) 也成立故结论对j + 1 时也成立得证 咯。= 珞，= 嘭 七= 1 定理2 3 2 ：对于不可分模型p m ，g = m | i a ，算法d f a 的竞争比不超过7 ( m ) + 1 i e n ：注意到引理2 3 1 中的( i ) 确保了算法中岛的存在性，所以d f a 是合理的不 妨假设最后一个工惭n 决定算法的目标值，于是g d f a = l 缝1 + 加又根据定 1 8 一 苟弓 一 h礞 帅腻 l i 衣 ；脚 第二章带般服务等级的在线同型机排序问题 义，l k nl - - 厶n k n ，再由引理2 2 1 以及定理2 2 3 ，可知 c d f a z 挈+ p n c 己p + m 一y ( m q + p 孑。z ( 7 m ) + 1 ) g 2 3 2 改进算法日t 尽管l p 算法本身对可分模型具有很好的性能，但其对不可分模型的 诱导算法d f a 的性能就不那么令人满意了，特别是m 较小时的情形例如 在m = 2 时，l p 的竞争比为，y ( 2 ) = 百4 ，所以d f a 的竞争比就是；+ 1 = ；， 而m = 2 时最优算法的竞争比却是5 3 7 ；4 8 1 因此在本小节我们针对这种情 形设计了一个改进的算法一等级阈值算法( h i e r a r c h i c a lt h r e s h o l da l g o r i t h m ，简 记h t ) ，使得在m 较小( m 5 ) 时它的竞争比严格好于d f a 值得指出的是，我 们的改进算法对m 较大时虽然也可行，但是竞争比的分析却极其复杂，并且未 必严格好于d f a ，所以对m 较大时，我们仍然采用d f a 算法 首先给出引理2 2 1 的一般化结果，用第一章定义的符号t j , = 七。p k 表示 前j 个工件中等级为i 的工件的总加工长度，我们记 上b j = m a x m a x t 口x ，q 2 x ，c a - 1 - - c - ，- ，( 言 ) = ( 差，三) 。， 故根据引理2 2 2 的结论，得到c m c a 1 i g = 2 g 由此我们可知，算 法h t ( 3 ；1 ) 的竞争比不超过2 - 定理2 3 6