（运筹学与控制论专业论文）组合优化中的逆目标问题.pdf

摘要 摘要 随着社会的发展，经典的组合优化问题在受到众多学者的关注的同时， 又不断的产生了一些新的模型。本文就从逆目标函数的角度考虑了若干重要 的组合优化问题，包括排序和装箱，我们将这类问题称为逆目标优化问题。 事实上这类逆目标优化的问题文献中已有相关讨论，比如t s p 一- - m a x i m u m t s p 【9 ；2 5 ；4 0 ；4 8 ；极小割一一极大割( m a x i m u mc u t ) 【蚓；最短路一一最长 路( 1 0 n g e s tp a t h ) 【4 7 等等。本文中将要详细讨论的逆目标优化问题包括懒惰 官僚排序问题( l a z yb u r e a u c r a ts c h e d u l i n g ) 3 b 拖沓工人排序问题( p r o c r a s t i n a t o r s c h e d u l i n g ) 1 0 】；极大化资源装箱问题( m a x i m u mr e s o u r c eb i np a c k i n g ) 1 2 ；1 3 】以 及逆目标箱覆盖问题( l a z yb i nc o v e r i n g ) 等。本文将就这几个问题进行算法及复 杂性方面的研究。全文共分六章，第一章主要介绍一些组合优化及算法方面相 关的概念和预备知识；第二章简要综述近年来与本文相关的逆目标优化问题的 若干成果，并列举了本文得到的一些主要结果。 在第三章中，我们研究了懒惰官僚的排序问题( l a z yb u r e a u c r a ts c h e d u l - i n gp r o b l e m ) 。我们主要考虑在单台机下，工件截止时间相同的懒惰排序问 题( c o m m o nd e a d l i n el a z yb u r e a u c r a ts c h e d u l i n g ) ，并且假设工件在加工过程中 是不可中断的。在离线情况下，我们证明了算法s j f ( s h o r t e s tj o bf i r s t ) 对于目 标函数【m i n t i m e s p e n d 其最坏情况界仍然是2 ，解决了文献 2 3 1 中提出的公开问 题。进一步的，对于目标函数 m n t i m e s p e n d 和 r a i n m a k e s p a n ，我们分别设计 了两个多项式时间近似方案( p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ，a k 和玩。 对于任给的正整数七，该近似方案的最坏情况界至多是1 + 1 k 。最后我们证明 了即使工件的到达时间和截止时间均相同，懒惰官僚排序问题对于若干目标函 数仍然是n p 困难的。对于在线情况下的懒惰官僚排序问题，同样假设所有工件 具有同一个截止时刻。我们给出了一个算法a ，其竞争比为( 怕+ 1 ) 2 ，并且证 明了它就是最优的在线算法。 第四章中研究了几个有关装箱问题的逆目标优化模型。我们首先证明了极 大化资源装箱问题( m a x i m u mr e s o u r c eb i np a c k i n gp r o b l e m ) 是n p 困难的，解决 了文献【1 2 ；1 3 中提出的公开问题：并且证明了f f l ( f i r s tf i ti n c r e a s i n g ) 算法是绝 对比意义下最好的算法，其最坏情况界为。接下来我们考虑了逆目标的箱覆 盖问题和带限制的o p e n e n d 装箱问题，分别指出了它们是n p 难的，并设计出 了相应的最好的近似算法。尤其对于逆目标箱覆盖问题，我们纠正了l i n 等人 摘要 在1 5 1 】中关于问题计算复杂性的证明。 第五章研究了拖沓者的排序问题( p r o c r a s t i n a t o rs c h e d u l i n gp r o b l e m ) 。对于 离线情况下，即使- 件的初始速度不为零，我们证明仍存在一个多项式时间算 法l t l t b + 可以极小化目标函数【拥一t i m e - s p e n t 。我们还考虑了在线情况下工件 的最大延迟比问题，指出只要采用q d e l a y 算法，4 就是可以达到的最好的最 大延迟比。 第六章为后记。简要的总结了一下本文的工作，讨论了未来的研究方向以 及一些公开问题。 关键词：排序，装箱，计算复杂性，算法 一一 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 ys e v e r a lv a r i a n t so ft h er e v e r s eo b j e c t i v ec o m b i n a t o r i a lo p - t i m i z a t i o np r o b l e m s ，i n c l u d i n gt h el a z yb u r e a u c r a ts c h e d u l i n gp r o b l e m , t h em a x i m u m i c s o u r c cb i np a c k i n gp r o b l e m , a n dt h el a z yb i nc o v e r i n gp r o b l e me t c t h e s ep r o b l e m s s t u d yt h et r a d i t i o n a ls c h e d u l i n g ，b i np a c k i n gp r o b l e mi na n o t h e rp o i n t s u c hi n q u i r i e s o f t e nl e a dt oab e t t e ru n d e r s t a n d i n go ft h es t r u c t u r ea n d a l g o r i t h m i cc o m p l e x i t yo f t h e 嘶g i n a lo p t i m i z a t i o np r o b l e m ，a n dg i v er i s et oar i c hs e to fn e wq u e s t i o n st h a te x p l o r et h ed i s t i n c t i o nb e t w e e nm a x i m i z a t i o na n dm i n i m i z a t i o ni nc o m p u t i n go p t i m a l s o l u t i o n s t h et h e s i si ss p l i ti ns i xc h a p t e r s i nc h a p t e rlw ef i r s ti n t r o d u c es o m ep r e - l i m i n a r yc o n c e p t sr e l a t e dt oa l g o r i t h m sa n dc o m p l e x i t yt h e o r y , a n dt h eb a c k g r o u n do f m o d e l sc o n s i d e r e di nt h i st h e s i s i nc h a p t e r2 ，w es u r v e yt h er e l e v a n tr e s u l t so nt h el a z yb u r e a u c r a ts c h e d u l i n g p r o b l e ma n dt h em a x i n l l n nr e s o u r c eb i np a c k i n gp r o b l e m t h e nw ep r e s e n tt h em a i n r e s u l t so ff l d st h e s i s i nc h a p t e r3 ，w ec o n s i d e rt h el a z yb u r e a u c r a ts c h e d u l i n gp r o b l e m w ef o c u so n t h ec a s cw h e r e 棚t h ej o b ss h a r eac o f n n l o nd e a d l i n e , s u c hap r o b l e mi sd e n o t e da s c d l b s p a sf o rt h eo f f - l i n ec a s e w ef i r s ts h o wt h a tt h ew o r s t - c a s er a t i oo ft h ea l g o - r i t h ms 】f ( s h o r t e s tj o bf i r s t ) i st w ou n d e rt h eo b j e c t i v ef u n c t i o n m n t i m e s p e n t 。a n d t h u sa n s w e ra no p e nq u e s t i o np o s e db ye s f a h b o de ta 1 【2 3 w ef u r t h e rp r e s e n tt w o p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m a sa ka n db kb o t hh a v i n gw o r s t - c a s er a t i oo f 1 + 1 k ，f o ra n yg i v e ni n t e g e r 竞 0 ，u n d e rt h eo b j e c t i v ef u n c t i o no f 【m i n m a k e s p a n 】 a n d 【r a i n t i m e s p e n t r e s p e c t i v e l y f i n a l l y , w ep r o v et h a tt h ep r o b l e mc d - l b s p 廿 i n a i n s n p - h a r d u n d e rs e v e r a l o b j e c t i v e f u n c t i o n s ，e v e n i f a l l j o b ss h a r e t h e s a m e r e l e a s e t i m e w ea l s oc o n s i d e rt h eo n l i n ec a s eo fc d - l b s p w eg i v ea no p t i m a lo n l i n ea l g o r i t l m aaw i t ht h ec o m p e t i t i v er a t i oo f 华f o rt h eo b j e c t i v ef i i n c i 册 m i n - m a k e s p a n a n d 【r a i n t i m e s p e n t i n c h a p t e r 4 ，w e p r e s e m t h e c o m p u t a t i o n a l c o m p l e x i t y p r o o f s f o r t h e l a z y b i n e n v 一 耐n gp r o b l e m , t h er e s t r i c t e dop l 一e n db i np a c k i n gp r o b l e m , a n de s p e c i a l l yt h em a x i m u u lr c s o l l l - c eb i n p a c k i n gp r o b l e m ，w h i c hw a s a no p e np r o b l e m p o s e di n 【1 2 ；1 3 w e a l s og i v et h ec o r r e s p o n d i n g l yb e s tp o s s i b l ea l g o r i t h m sf o rt h e s ep r o b l e m s 一一 a b s t r a c t i nc h a p t e r5 ，w es t u d yt h ep r o c r a s t i n a t o rs c h e d u l i n gp r o b l e m w ep r e s e n ta l l o p t i m a lo f f - l i n ep o l y n o m i a lt i m ea l g o r i t h ml r t b + u n d e rt h eo b j e c t i v eo f 【m n t i m e s p e n t ，f o rt h em o d e lw i t ham o r eg e n e r a jj o bs p e e df u n c t i o n ， ( ) = m t 0 一n ) + 仇， w h e r e 饥i st h er e l e a s es p e e do f j o bi w ea l s oe x p l o r eo nt h em a x i m u ms t r e t e hr a t i oi n o n l i n ec a s e ，w ep r o v et h a t4i sb e s tp o s s i b l ef o ro t d e l a ya l g o r i t h m s f i n a l l y , i nc h a p t e r5w ep r e s e mas u m m a r yo fo u rr e s u l t s ，a n dp o i mo t t ts o n l e f u m mw o r k si nt h e s ea b 髂 k e yw o r d s ：l a z yb u r e a u c r a ts c h e d u l i n g ，m a x i m u mr e s o u r c eb i np a c k i n g ，c o r n - p u t a t i o n a lc o m p l e x i t y l 、，一 第一章绪论 1 1 组合优化简介 第一章绪论 最优化问题似乎自然地分为两类：一类是连续变量的问题，另一类是离散 变量的问题。在连续变量的问题里，一般地是求一组实数，或者一个函数；而 对于具有离散变量的问题，则是从一个无限集或者可数无限集里寻找一个对 象：典型地是一个整数，一个集合，一个排列，或者一个图。这两类问题各有 相当不同的特色，并且求解它们的方法也是各有千秋。在对离散优化问题的研 究中，从某种意义上说，我们是从它与连续优化问的分界线入手。 离散优化问题又称为组合优化问题，是一类重要的优化问题。二十世纪应 用数学的重大发展之一，就是将现实生活中寻优的过程用数学模型进行描述并 求解。随着计算机科学，管理科学和现代化技术等的日益发展，针对离散变量 的优化问题逐渐得到人们的关注。而且这一类的问题也与日俱增。越来越受到 运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视。它在近几 十年来逐步发展壮大，取得了丰硕的研究成果，成为运筹学的一门新兴的学科 分支。 定义1 1 1 ：组合优化问题是一个极小( 大) 化问题，它由下述三部分组成： ( 1 ) 实例集合； ( 2 ) 对每一个实例j ，有一个有穷的可行解集合s ( 1 ) ； ( 3 ) 目标函数，它对每一个实例j 和每一个可行解口s ( ，) ，赋以一个有理 数f ( 1 ，口1 如果该问题是极小( 大) 化问题，则实例珀q 最优解为这样一个可行 解矿s ( j ) ，它使得对所有的口s ( j ) ，都有f ( 1 ，矿) ( j r ，口) ( ，( j ，矿) f ( 1 ，口) ) 1 2 算法和计算复杂性 定义1 2 1 ：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的 一个清晰描述。如果存在一个算法，它对组合优化问题”的每个实例j ，在有限 步后一定可以得到该实例的关于7 1 的提问的答案，那么称该算法解此组合优化问 题7 r 。 第一章绪论 判断算法的优劣主要有两个因素：运行速度和性能表现。为了衡量算法的 运行速度，学术界引入了复杂性的概念。具体的，可以从算法的空间复杂性或 时间复杂性上进行考虑。前者是指算法在计算机运行过程所用到的最大空间 ( 字节数) ；后者则是指算法运行所需的时问。我们在本文中所使用的标准主 要是算法的时间复杂性。 定义1 2 2 ：算法的时间复杂性是指关于实例输入长度礼的函数f ( n 1 ，用来表示算 法的时间需求。具体讲就是，将一个实例通过某种规则编码输入计算机后所占 用的字节数称为该实例的输入长度；对每一个可能的输入长度，算法解具有此 输入长度的最坏可能实例所需的基本计算次数( 如加法、乘法、比较等) 称为 该算法的时间复杂性( 函数) 。如果存在一个多项式函数p ( 礼) ，使得算法的时 问复杂性为0 ( p ( n ) ) ，( 这里咒为输入长度) ，那么称算法为多项式时间算法。 否则称为指数时间算法。 还有一类算法，它的时间复杂性不光与实例的输入长度有关，还与实例中 的最大数有关。如果存在一个关于实例输入长度和实例中最大数的二元多项 式，使得算法的时间复杂性不超过，则称这类算法为伪多项式时间算法。 由于当输入规模增加时，指数时间算法的算法效率降低特别快，以至于任 何一个多项式时间算法都变得比任一个指数算法更有效，所以我们把多项式时 间算法称为好的有效的算法。并且对于组合优化问题的研究的重点，也都致力 于寻找好的多项式时间算法。 但是，并不是所有的问题都能够找到多项式时间的最优算法，由此便引出 了计算复杂性理论中与此相关的的一系列重要概念和结论【3 0 】。 定义1 2 3 ：一个组合优化问题如果已找到了多项式时间算法，那么就称它为多 项式时间可解问题。把所有这样的问题集合记为p ，所有多项式时间可解的问题 就成为p 类问题。 定义1 2 4 ：给定一个判定问题，如果存在一个算法，对任何一个答案为“是” 的实例j ，该算法首先给出一个猜想，该猜想规模不超过珀q 输入长度的某个多 项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于n p 类。 性。 很显然p p 。但是多项式时间可验证性并不能保证多项式时间可解 一2 一 第章绪论 在p 与n p 问题上的个重大进展是在7 噼代初由斯蒂芬库克和列奥尼德 列文完成。他们发现n p 中的某些问题的复杂性与整个类的复杂性相关联。这些 问题中任何一个如果存在多项式时间算法，那么所有n p 问题都是多项式时间可 解的。这些问题称为n p 完全的。n p 完全性现象对于理论与实践都具有重要意 义。 定义1 2 5 ：如果n p 类中所有问题都可以多项式时间归约到n p 类中某个问题7 r ， 则称丌是n p - 完全问题。 定义1 2 6 ：语言a 称为多项式时间映射可归约到语言b ，或简称为多项式时间可 归约到b ，记为as pb ，若存在多项式时间可计算函数，：+ 一+ ，对于每 一个u ，有 u a 兮，0 ) b 函数，称为a 到b 的多项式时间归约。 定理1 2 7 ：如果，r l 是n p - 完全问题，丌2 n p ，且7 r 1 可以多项式时间归约到丌2 ， 则丌2 是n p - 完全问题。 由以上定理及定义知，如果某n p - 完全问题有多项式时间算法，则n p 类中 所有其他问题也有多项式时间算法，因此n p 完全问题是n p 类中最难的问题。 另一方面，如果一个n p - 完全问题没有多项式时间算法，则所有n _ p 完全问题也 没有，因此所有- n p - 完全问题是同等难度的。到目前为止，这些问题既没有找到 多项式时问算法，也无法证明多项式时间算法的不存在性。 定理1 2 8 ：p = n p 当且仅当存在一个n p 完全问题有多项式时问算法。 定义1 2 9 ：如果某优化问题7 r 的判定问题是n p - 完全的，则称问题7 r 是n p - 难的。 定理1 2 1 0 ：如果存在一个n p - 难问题7 r 1 可以多项式时间归约到丌2 ，则丌2 也 是n p - 难的。 定理1 2 1 1 ：除非p = p ，n p - 难问题没有多项式时间算法。 但n p - 难问题可能存在伪多项式时间算法。在p n p 的假设下，对于 不存在伪多项式时间算法的n p - 难问题，就称为强n p - 难问题( s t r o n g l yn p - h a r d p r o b l e m ) 。 一3 一 第一章绪论 对于这些不存在多项式时间最优算法的问题，我们往往放弃对最优解的寻 找，转而寻找一个可以快速得到的可行解，把它作为最优解的近似值。那么我 们自然会希望得到的近似解与最优解最大可能的接近，以增加算法的有效性。 为了衡量算法得到的近似解值与最优解值的接近程度，一般的我们采用最 坏情况界进行分析。 对于离线的情况，所有的任务信息事前都知道。那么我们就把我们所设计 的多项式时间算法的解值与最优算法的解值进行比较。由于最优解值确切是多 少无法知道，所以转而取其下界，以反映在最坏情况下多项式时间近似算法与 最优算法的差距。具体的，对于离线问题7 r 来说， 定义1 2 1 2 ：如果是一个极小( 大) 化问题，是任意实例。设a 是 r 的一个近 似算法。用a ( j ) 和o f t ( i ) 分别表示算法a 解实例j 所得的目标函数值和实例，的 最优目标函数值。则近似算法a 的最坏情况界( w o r s t - c a s er a t i o ) 定义为对于 所有的实例j ， r a ( 丌) 2 乎 r 1 i 端，) 阶) = 妒刈署鲫) 而对于在线问题，任务的信息是随其到来的同时释放的，事先并不知晓。 所以一般情况下对于在线算法性能的衡量，是将它的解值与离线情况下的最优 解值相比较。同样的取其下界，称之为竞争比。即对于在线问题丌， 定义1 2 1 3 ：如果7 r 是一个极小( 大) 化问题，j 是任意实例。分别 记a ( j ) 和o p t ( i ) 为在线算法a 对于实例，所得的目标函数值和离线情况下的 最优目标函数值。则在线算法a 的竞争比( c o m p e t i t i v er a t i o ) 定义为 “( 丌) = t 矿p ，l 石；募| _ s r ，w ) ( 嘶) = 乎 r 1 i 帮蚓 上述定义指出了对于任意实例，算法解至多与最优解相差多少，这是一个 正面的( p o s i t i v e ) 的结果。如果再可以证明确实存在一个实例，使得算法解与最 优解的比值与上界相同，则意味着算法的界已经无法再改进了，这样一个负面 的( n e g a t i v e ) 结果也是同样重要的，此时称所得到的算法的界是紧的。 4 第一章绪论 进一步的，对于一个组合优化问题而言，它也存在一个下界，表明对于任 意的近似算法，它在最坏情况下与最优解至少要差距多少。 定义1 2 1 4 ：问题7 r 的下界( 1 0 w e r b o u n d ) 定义为 ( ”) = 代i “v a ) 如果还有细( 丌) = f ( 7 r ) ，则称算法b 对于问题7 r 来讲是最好的( t h eb e s tp o s s i b l e ) 。 定义1 2 1 5 ：如果某问题有一系列近似算法 a ，使得对于任意给定的s 0 ， 如) 是一个多项式时间算法，而且7 也1 + s ，则称它为多项式时间近似 方案( p o l y n o m i a lt h n ea p p r o x i m a t i o ns c h e m e ) ，简记为p t a s 。进一步的，如 果 a 的时间复杂性是关于输入长度以及；的某个二元多项式，则称它为完 全多项式时间近似方案( f u l l yp o l y n o m i a lt u n ea p p r o x i m a t i o ns c h e m e ) ，简记 为f p t a s 。 1 3 本文有关的问题模型 尽管大部分组合优化问题可以转化为整数规划( 或混合整数规划) 问 题，但由于整数规划的求解同样也是困难的，而组合优化又涵盖甚广，因 此人们致力于研究各个问题的组合结构，试图找到一些好的性质和有针 对性的求解方法。常见的组合优化问题有分划问题( p a r t i t i o n ) 、排序问题 ( s c h e d u l i n g ) 、装箱问题( b i np 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 r m i m m a lt 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 ) 等。组合优 化全貌可参见【4 3 ；6 2 ，在此，我们只对本文研究主要涉及到的问题作简单介 绍。 本文中涉及到的经典的组合优化问题主要是排序和装箱问题。 1 3 1 排序问题 排序问题又称为时间表问题( s c h e d u l i n g ) ，是一类有着重要理论意义和广泛 一5 一 第一章绪论 应用背景的组合优化问题。其实质是寻求对需完成的任务的合理安排以得到某 种意义下的最优结果，除了在计算机科学领域外，排序问题还在生产计划调 度，信息处理，公共事业管理等诸多方面具有大量应用。同时，它还和离散组 合数学存在着密切的联系。自五十年代首批文献问世以来，排序问题得到了运 筹学、工程学、管理学和计算机科学界的极大关注。 按照学术界多年来形成的惯例，我们把需要完成的任务称为工件( j o b ) ， 把完成任务需要的资源称为机器( m a c h i n e ) ，我们希望找到一个可行的捧序 ( s c h e d u l e ) ，使得某个给定的目标函数达到最小( 大) 。这里的可行一般指在 同一时刻，一台机器至多加工一个工件，一个工件也只在一台机器上加工，并 且该排序满足问题特定的约束要求。给定一具体的排序问题，需要明确以下三 个方面的信息：机器环境、工件特征和最优准则。 机器环境用来描述机器的数量、不同机器之间的关系等与机器有关的性 质。常见的机器系统包括单台机( s i n g l em a c h i n e ) 、平行机( p a r a l l e lm a c h i n e s ) 、流 水作业( f l o ws h o p ) 、有序作业( j o bs h o p ) 和自由作业( o p e ns h o p ) 等。 工件特征一般是指工件的各种加工信息，包括工件的加工时间，工件的开 工时间，工件之间加工顺序以及工件和其开工时间的依赖关系，工件加工时是 否允许中断以及中断恢复后再加工时是否要受惩罚等等。根据排序者对工件信 息的了解程度，又可将排序问题分为离线( o f f l i n e ) 和在线( o n l i n e ) 等。如果 排序者在排序开始前就已经知道工件的全部信息，例如工件数、每个工件的加 工时间等，则称该问题是离线的；而如果工件的信息是随着排序过程逐个释放 的，即只有在位于某个工件前的全部工件均被安排完毕后，排序者才能知道该 工件的有关信息，而且工件一旦被安排就不能改变。这样的排序问题就称为在 线的。 所谓最优准则，通俗地讲，也就是以什么为目标函数。排序问题比较常见 的目标函数有极小化最大完工时间、极大化最小机器负载、极小化( 赋权) 总 完工时间、极小化最大延误时间、极小化误工工件个数等。例如，如果记g 为 某个排序问题的可行排序中工件以的完工时间，则称g 一= m a x j o 为该排序 的工件最大完工时间( m a k e s p a u ) ，它即为某种最优准则下的目标函数。这个 最优准则为：找一个可行排序，使得工件的最大完工时间。在所有的可行排 序中取得最小值，即最小化目标函数。有关排序问题的综述，可参看【1 8 ；5 4 1 。 懒惰官僚排序问题 懒惰官僚排序问题( 1 a z yb u r e a u c r a ts c h e d u l i n gp r o b l e m ) 与经典排序的不同之 一6 一 第一章绪论 处在于，它是从执行任务的机器( 宫僚) 的角度考虑排序问题的。一个生性懒 惰的官僚，在只要保持忙碌状态就可以得到同定报酬的假设下，很自然的会选 择尽量减少自己执行的任务量，或者可以提前下班，或者加工工件的权和最 小。这里工件也有到达时间，截止时间，并且每个工件需要一个固定的加工时 长。我们可以从单台机、多台机，可中断、不可中断，在线、离线等情形下对 这个问题进行分析。 拖沓工人的排序问题 拖沓工人的排序问题( p r o c r a s t i n a t o rs c h e d u f i n gp r o b l e m ) 呼应了经济学中著名 的p a r k i n s o n 原理，即白领工作中的一个常见现象：无论给定多少时间，增派多 少人手，最后的工作时间一定是覆盖整个给定区间的。我们考虑的排序模型刻 画了机器的加工速度与当前时刻距离截止时间长短满足线性关系时的情形，某 种意义上这个模型可以表现为：拖得越晚，速度越快。在这里，目标函数可以 考虑极小化总加工时问、最大化完工工件个数，以及在线情况下的工件最大延 迟比等等。 1 3 2 装箱及箱覆盖问题 装箱问题 装箱问题是一个经典的组合优化问题。对于给定的足够多的箱子和一些 物品，记箱子的容量为1 ，物品的尺寸都大于零小于1 。我们需要将物品全部装 入箱子中去，使得每个箱子中物品的尺寸和不超过箱子的容量。所谓的装箱 问题( b i np a c k i n gp r o b l e m ) ，是指寻找一种方法，使得对于任意给定的一个物品 集，按照这种方法去装箱，使用的箱子数目最少。 装箱问题在生产生活实践中有广泛的应用价值，比如轧钢厂生产出来的 钢条一般为同一长度，而用户所需的钢条则可能具有各种不同的尺寸。如 何根据用户提出的要求，用最少的钢条截出他们所需的订货，这显然是上 述的装箱问题。再比如说集装箱装货问题等等。同时它也可以看作是排序 问题的一个特例。上面所说的装箱问题是最一般的装箱问题，又称为一维装 箱，它已被证明为n p - 困难问题。关于一维装箱问题的近似算法，最著名的当 属f f d 算法。d s j o h n s o n 于1 9 7 3 年证明了f f d 告0 p r + 4 ，并且这里的系 数尝是不可改进的。这个结果后来由越民义【6 3 】改进为f f d 导d p r + 1 。 目前最好的结果是g d o s a 2 1 于2 0 0 7 年在e s c a p e 会议上给出的证明：f f d ( 1 l 9 ) o p t + 6 9 除了这一经典的装箱问题之外，还有一些其它类型的装箱 一，一 第一章绪论 问题。比如从箱子参数的角度考虑，还有二维装箱、多维装箱，变尺寸装箱问 题1 6 8 ；1 5 ；6 7 1 等等：另外也可以从物品参数的角度进行分类，比如带拒绝的装 箱问题，物品可旋转的装箱问题等等。另外还可以从对物品信息的了解将装箱 问题分为在线和离线两种情形。装箱问题的结果丰富而有趣，关于装箱问题的 综述可参见c o f f m a n 等人所写的a p p r o x i m a t i o na l g o r i t h mf o rb i np a c k i n g 【1 9 。 极大化资源装箱问题 b o y a r 等人【1 2 】首先提出了从令一个角度考虑装箱问题目标的模型，即极大 化资源的装箱问题。在这里，问题的目标函数恰好相反：对于给定的物品集， 将所有的物品分别装入箱中后，我们希望使用的箱子个数越多越好。极大化装 箱问题在日常生活中是十分常见的，比如对于搬家公司，他们的收费在里程一 定的情况下，是直接与所使用卡车的数量有关的。即所使用的卡车数量越多， 收费也越多。那么作为希望盈利的搬家公司来说，他们一定会选择一种装车策 略，使得在某些合理的限制条件下尽可能多的使用卡车 o p e n 一曲d 装箱问题 o p e n e n d 装箱问题f 4 9 】源于香港的地铁站收费问题。每一张地铁票都有一定 的面额，每段旅程的费用都可以从中扣除。但是对于最后一段旅程，只要地铁 票里的余额不为零，就可以当全额使用，不需再追缴差价。这时乘客就在余额 不足的情况下占了便宜。对于一个要做若干段旅行的乘客来说，最少购买几张 地铁票就可以完成旅行，这就是o p e n e n d 装箱问题。其中，箱子数对应票面总 值，物品则对应着每一段路程所需的费用。 另外本文中还考虑了另外一种带限制的o p e n - e n d 装箱问题，其目标函数 也是极小化所使用的箱子的个数，但是在物品超出箱子容量的限制上与经 典的o p e n - e n d 装箱问题又略有不同。o p e n - e n d 装箱问题中只要最后一个物品装 入前物品尺寸和小于箱子容量即可，超出多少没有限制；但是在这个带限制 的o p e n e n d 装箱问题中，要求物品超出箱子容量的部分小于箱中任何物品的尺 寸。 箱覆盖问题 箱覆盖问题也是一个经典的组合优化问题，对于给定的物品集，我们希望 尽可能多的使用箱子，使得除了最后一个箱子之外，其余箱子都被物品覆盖。 我们称一个箱子被覆盖，如果其中的物品的尺寸和大于箱子的容量，并且满足 把箱子中最小的物品拿出后物品的尺寸和就小于箱子容量。 一8 一 第一章绪论 箱覆盖问题最初的产生是源于超市分装土豆时，每个袋子里的土豆的重量 都不能低于广告宣传中的体积，否则就可能会被扣上商业欺诈的帽子，伊超市 的目标肯定是希望最后分装出来的土豆袋数越多越好。所以对于给定的一堆土 豆，他们会寻求一种较优的分装策略，使得每袋土豆的重量刚刚好超过宣传 值，而得到最多的袋数从而增加受益。 装箱问题与箱覆盖问题限制条件对称，目标函数又刚好相反，是两类非常 重要的组合优化问题。 逆目标箱覆盖问题 与经典的箱覆盖问题的目标函数恰好相反，这里我们希望被覆盖的箱子个 数越少越好。同样的，除了最后一个箱子之外，其余箱子都要被物品覆盖。并 且每个箱子中最后一个装入的物品一定有一部分包含在箱予内部，而超出来的 部分小于箱子中任何一个物品的尺寸。4 1 中将介绍一个逆目标箱覆盖问题的实 际背景，这里不再赘述。 一9 一 第二章组合优化中的逆f 1 标问题综述 2 1 引言 第二章组合优化中的逆目标问题综述 组合优化问题磅礴而枝叶繁茂，在实际的生产生活中又不断的产生一些新 问题。本篇综述主要介绍组合优化中若干逆目标问题的研究成果。所谓的逆目 标问题，就是从另一个角度对一些经典的组合优化问题进行考虑，一般目标函 数与原问题的目标函数恰好相反，所以又称之为逆目标优化。 下面将主要综述与本论文有关的两个逆目标优化问题，一是a r k i n 等 人【3 】于1 9 9 9 年提出的懒惰工人排序闯题，二是b o y a r 等人于2 0 0 5 年提出的极 大化资源的装箱问题( m a x i m u mi e s o l l r c cb i np a c k i n g ) 【1 2 ；1 3 事实上，调整目标函数对经典组合优化进行重新考虑文献中已经出现很多 了，这些探讨和尝试反过来也可以帮助更好的理解原问题的结构和算法的复杂 性。比如最长路问题：与著名的s h o r t e s t - p a t h f n 题相似，在任意的一个有限连通 图上，对于给定的两个顶点，设计一个有效的算法找出两点之间最长的路( 即 一个没有l o o p s 的r o u t e ) 。还有最大割问题( m a x i m u mc u t ) 【3 4 1 、极大化旅行 商问题( m a x i m u m t s p ) 【9 ；2 5 ；4 0 ；4 8 等等，这里就不再赘述。 2 2 懒惰官僚排序问题 下面我们将详细介绍懒惰官僚排序中的一些结果。主要是离线和在线情况 下的确定性算法，包括单台机、多台机情形。既有难解性结果，也有相应的多 项式时间算法分析。我们将分别对可中断情形和不可中断情形进行介绍。首先 介绍一下问题的模型及相关参数。 2 2 1 问题模型 工件及机器特征 给定一批工件 ，如，厶，工件的加工时间( 长度) 分别 为m ，沈，到达时间为7 l ，您，截止时间为d 1 ，d 2 ，如。现 有一台( 多台) 机器对这些工件进行加工，但不要求工件全部加工完。对 每个工件 。i = 1 ，n ， r i ，矧为其可行区间，即工件只有在到达之后、 截止时间之前才可以加工。令c f = 函一鼽表示工件五的关键时刻点，即该 一1 0 一 第二章组合优化中的逆f 1 标刚题综述 工件最晚要在岛时刻开始加工，否则不可能完工。我们需要寻找一个町行 序列将丁= 件有序的分配到机器上，使得该序列如果存在，则其中的工件都 在可行区间内加工，并且可以最优的保证某种目标函数。 另外对于多台机情形，通常假设工件不可以“跳跃”，即每个工件只能由 一台机器加工。而且机器独立加工，相互之间不存在影响。当然，任何机 器在任何时刻只能加工一个工件。 目标函数 传统的排序问题中，如果对于给定的工件无法在截止时间之前全部完工， 一般会考虑针对某些特定的目标进行优化。比如极大化按时完工工件的权 和，极小化最迟完工的时间，或者极小化延误工件个数等等。在懒惰官僚 排序问题中，我们考虑的目标函数都是由懒惰的官僚自然的需求产生的， 如下所示： 1 极小化总加工时间( m i n t i m e s p e n t ) 2 极小化完工工件的权和( m i n - w e i g h t e d - s u m - o f - c o m p l e t e d - j o b s ) 3 极小化最大完工时间( m i n m a k e s p a n ) 4 极小化完工工件数( m i n n u m b e r - o f - j o b - c o m p l e t e d ) “忙碌”假设 在懒惰官僚排序问题中，由于机器( 官僚) 是要选择给定工件集的一个予 集进行加工，而他的目标是尽量减少工作量，所以很自然的，要增加一个 “忙碌”的假设，即任何时刻，只要存在可以加工的工件，就一定要开始 加工。否则，工人的最优策略一定是一直闲置，什么工作也不做了。在不 可中断情形下，定义一个工件当前是可行的，即该工件如果立即开工，可 以在截止时间之前完工；对于可中断情形，工件是否可行定义的要复杂 些，具体参见下面可中断定义。 可中断定义 一个序列称为可中断的，如果其中的工件可以在加工过程中中断，并且不 需要付出任何代价即可继续加工。具体的，文献中主要考虑了三种可中断 情形。在时刻t ， 1 工件可以中断，如果它已经到达并且还尚未到截止时间，即nst 第二审组合优化中的逆目标日j 题综述 吨： 2 工件可以中断，如果它已经到达也未到截止时间，并且仍然有机会可 以完工。即t ，其中= 疵二- a + 玑为调整后的关键时刻，肌为已 加工完成部分： 3 工件可以中断，如果它已经到达也未到截止时间。但这里需要满足的 是工件只要开始加工就必须完工。 事实上，对于第三种中断假设，当工件的到达时间都相同时，它是等同于 一般情况下的懒惰工人排序问题的，因为此时中断不再有任何好处。其复 杂性结果也与不可中断情形类似。而对于第一种中断假设，一般情况下对 于以上几个目标函数都是多项式时间可解的。因此文献的结果主要集中于 对第二种中断假设情形下的研究。 离线与在线 离线情况下，在零时刻即知道全部工件信息，包括工件的到达时间，截止 时间和加工长度等。而在在线情况下，只有当工件到达时，其相关信息才 被释放。并且必须在工件到达的同时做出决定是否加工，并安排加工，然 后新的工件才会到达 其他参数 a r k i n 等人【3 】还考虑了工件加工时间与其可行区间之间的比，记为冗，即 对于所有的工件，令r s u p s 生产) 。他们证明了当r 2 时，懒惰官僚 排序问题对于上面提到的四个目标函数都存在伪多项式时间算法。类似 的，表示最长可行区间与最短可行区间比的上界；用表示最长工件与 最短工件比的上界。 2 2 2 离线不可中断情况下文献成果 下面介绍一下懒惰官僚排序问题中离线不可中断情形下的研究结果。关于 问题的计算复杂性，下面的结论都是在p p 的假设前提下的。 对于一般情况下的懒惰官僚排序问题l b p ，a r k i n 等人【3 】证明其对于上述四 个目标函数都是强n