（基础数学专业论文）大规模排序问题的列生成算法研究.pdf

摘要 摘要 排序论又称为时间表理论，它是为满足一个或者多个优化目标，安排稀缺资 源，执行任务的决策过程一般认为，1 9 5 4 年，j o h n s o n 的论文f 5 2 1 是经典排序的第一 篇义章，从此排序论迅速发展起来随着社会的发展，新的问题及模型层出小穷，同 时伴随着问题的规模越来越大，因此从解决实际需要出发，从归结得到的排序模 型具有实际应用意义的角度来看，对于大量n p 一难的排序问题，设计精确算法是目 前排序论研究中一个值得深入研究的课题 对于大规模的n p - 难的组合优化问题，已有的精确算法有分支定界算 法，动态规划算法，以及列生成算法6 2 ，7 6 ，8 5 ，9 5 ，9 9 】等最初，列生成方法 是f o r d 与f u l k e r s o n 3 4 在1 9 5 8 年求解最短路问题时提出，后来它在求解整数规 划方面得到很好的应用但是很少的文献应用列生成方法来求解n p 难的排序问 题，v a nd e na k k e re ta 1 f 8 7 】结合d w 分解和分支定界方法，对于所有b 的正则目 标函数，给出了经典单机排序问题的列生成算法1 9 9 9 年，陈志龙和p o w e u 2 5 讨论 了经典排序问题q i i 厶( c f ) 的列生成算法，这里q p ，q ，r ) ，他们在【2 6 】中给出 了j i t o u s t i n - t i m e ) 平行机排序问题的列生成算法 本文辛要研究结果包括以下几个方面：一是研究n p 一难的成组加工排序问题 的列生成算法；二是建立一种新型排序一柔性同时加工排序模型，讨论它的复杂 性并设计精确算法三是对现代排序问题，资源受限的确定性排序问题进行了研 究 在第一章，首先介绍了排序问题的基本知识和分类方法，然后介绍了列生成方 法在整数规划方面的应用，以及关于求解大规模排序问题的列生成算法 经典的排序中更换工件所需要的安装时间是假设与机器无关的，并且与工 件的排法也无关然而在实际问题中，工件在机器上加工前所需要的安装时间往 往是与排法有关的，在第二章，我们考虑了成组加工排序问题分别讨论一台机器 和m 台机器环境下，大规模的n p 难问题的列生成算法，并通过试验，验证了我们 的算法的有效性。 在第三章考虑了一种新型的排序模型柔性同时加工排序问题，系统地讨 论了它在不同的工件约束条件，以及不同的目标函数下，柔性同时加工排序问题的 计算复杂性给出机器容量和时间满足一致性，目标是工件完工时间和的柔性同 时加工平行机排序问题的列生成算法 最后考虑到企业的市场竞争，生产成本和资源的限制，例如机器加工能力的限 制，较少的生产线，库存限制等等，在第四章，主要研究机器加工和仓储的综合准时 排序问题，讨论了仓库容量有限，一台机器，目标函数分别是最小误工工件和，最 小工件投送时间和，最小最大工件误工和最小最大工件延误的排序问题的复杂性 关键词：排序，多台机器，成组分批，柔性同时加工，复杂性，精确算法，伪多项 式算法，列生成算法 同济大学博士学位论文 a b s t r a c t t h es c h e d u l ei sas e r i e so fd e c i s i o n - m a k i n g w h i c hi n c l u d i n ga l l o c a t i o no f s c a r c er e s o u r c ea n dt op e r f o r mt a s k s ，f o ro n eo b j e c t i v eo rs e v e r a l f r o mt h e j o h n s o n sp a p e r 5 2 ( 1 9 5 4 ) ，p r o b a b l yt h ef i r s tp a p e rt oa d d r e s st h ep r o b l e mo f s c h e d u l i n g ，t h et h e o r yo fs c h e d u l i n gi s s t u d i e db ym o r ea n dm o r er e s e a r c h e r s m a n yn e ws c h e d u l i n gm o d e l sc o m ef o r t hw i t ht h ed e v e l o p m e n to fs o c i e t ya n d t h es i z eo ft h ep r o b l e m sb e c o m eb i g g e ra sn e v e rb e f o r e b e c a u s eo fr e q u i s i t e si n t h el a r g e s c a l ei n d u s t r i a lo p e r a t i o n ，t h a td e s i g nt h ee x a c ta l g o r i t h mb e c o m e so n e i m p o r t a n ta s p e c ti nt h es t u d yo fs c h e d u l i n ga 土p r e s e n t f o rt h el a r g e - s c a l en p h a r dc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m s ，t h e r eh a v e e x i s ts o m ee x a c ta l g o r i t h m s ，f o re x a m p l e ，b r a n c ha n db o u n d ，d y n a m i cp r o - g r a m m i n ga n dc o l u m ng e n e r a t i o ne t c t h ec o l u m ng e n e r a t i o nt e c h n i q u ei sf i r s t d i s c u s s e db yf o r da n df u l k e r s o n 3 4 ( 1 9 5 8 ) w h e nt h e ys o l v e dt h es h o r t e s tp a t h p r o b l e m s u b s e q u e n t l y , m o r ea n dm o r ep a p e r sa b o u tt h ec o l u m ng e n e r a t i o n a p p e a r e d 6 2 ，7 6 ，8 5 ，9 5 ，9 9 t h e r ea r es t i l lf e wp a p e r st or e s o l v et h en p h a r d s c h e d u l i n gp r o b l e m sb ya p p l y i n gt h ec o l u m ng e n e r a t i o nt e c h n i q u e i nt h i sd i s s e r t a t i o n ，w ed e a lw i t han u m b e ro fm o d e r ns c h e d u l i n gp r o b l e m s ， w h i c ha r i s ei ni n d u s t r ym a n u f a c t u r ea n db u s i n e s sm a n a g e m e n t ，a n dg i v et h ec o l - u m ng e n e r a t i o na l g o r i t h m sf o rt h r e en p h a r ds c h e d u l i n gp r o b l e m sr e s p e c t i v e l y t h em a i nr e s u l to ft h i st h e s i sc o n s i s t so ft h r e ep a r t s i nt h ef i r s tp a r t ，w ef o c u s o nt h ej o bs c h e d u l i n gp r o b l e mw i t hl o ts i z i n g ，w h e r et h es e t u pt i m e so fj o b sa r e d e p e n d e n to nm a c h i n ea n ds e q u e n c eo fj o b s an e ws c h e d u l i n gm o d e l ，f l e x i b l e b a t c h i n gs c h e d u l i n g ，i sf o r m u l a t e di nt h es e c o n dp a r t i nt h ef i n a l l yp a r t ，w e c o n s i d e rt h er e s o u r c ec o n s t r a i n e ds c h e d u l i n gp r o b l e m ar e v i e wo fc o l u m ng e n e r a t i o na p p r o a c h e s ，u s e di nh u g es c a l ei n t e g e rp r o - g r a m m i n ga n dn p h a r ds c h e d u l i n gp r o b l e m s ，i sp r e s e n t e d i nc h a p t e r1 ，a l o n gw i t h am o r ed e t a i l e dd e s c r i p t i o no fp r e l i m i n a r i e s ( e g n o t a t i o na n dc l a s s i f i c a t i o n ) o n m o d e r ns c h e d u l i n g i nt h em o s tc l a s s i c a ls c h e d u l i n gm o d e l ，i ti sa s s u m e dt h a tt h es e t u pt i m e s o fj o b sa r ei n d e p e n d e n to fm a c h i n ea n ds e q u e n c e i nm a n yp r a c t i c a ls i t u a t i o n s ， h o w e v e r ，t h es e t u pt i m e sa r ed e p e n d e n to nt h ep r o c e s s i n gs e q u e n c eo fj o b s ，f o r e x a m p l e ，c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n gs y s t e m i nc h a p t e r2 ，w ed i s c u s s t h es c h e d u l i n gj o b so ns i n g l em a c h i n ea n dp a r a h e lm a c h i n e sw i t hl o ts i z i n ga n d g i v et h ec o l u m ng e n e r a t i o na l g o r i t h m sf o rt h e mr e s p e c t i v e l y t h ec o m p u t a t i o n a l r e s u l t ss h o wt h a to u ra l g o r i t h m sa r ec a p a b l eo fs o l v i n gm e d i u ms c a l en p h a r d p r o b l e m s i ft h ec a p a c i t yo fam a c h i n ei sn o tc o n s t a n t ，w ec a l li taf l e x i b l eb a t c h i n g i v a b s t r a c t m a c h i n e i nc h a p t e r3 ，w ef i r s ta d d r e s st h ep r o b l e mo fs c h e d u l i n gj o b so na f l e x i b l eb a t c h i n gm a c h i n e i ti sd e n o t e da 8x l d b a t c h l 7 w 色s y s t e m a t i c a l l yd i s c u s s t h ef l e x i b l eb a t c h i n gs c h e d u l i n gu n d e rm u l t i - k i n d so fm a c h i n ee n v i r o n m e n t ，j o b c h a r a c t e r i s t i c sa n do p t i m a l i t yc r i t e r i a w ba n a l y z et h e c o m p l e x i t yo fe a c hp r o b l e m a n dg i v ep s e u d o p o l y n o m i a la l g o r i t h m sf o rt w oe s p e c i a lc a s e so ft h ep r o b l e mt o m i n i m i z et h em a k e s p a n f o rp r o b l e ml i d b a t c h f q ，w ep r o p o s eac o l u m n g e n e r a t i o na l g o r i t h mb a s e do nt h eb r a n c ha n db o u n d as t a n d a r da s s u m p t i o nu s e di nm o s tc l a s s i c a ls c h e d u l i n gi st h a ta o bi s d i s p a t c h e dt oac u s t o m e ri m m e d i a t e l ya f t e ri t sp r o c e s s i n gc o m p l e t e d b u ti n m a n yp r a c t i c a ls i t u a t i o n s ，as e to fd e l i v e r yd a t e sm a yb ef i x e db e f o r ea n yj o b sa r e p r o c e s s e d t h e nt h ej o b ss h o u l db ed e p o s i t e di nt h ew a r e h o u s eb e f o r et h e ya r e d e l i v e r e d t h i si sp a r t i c u l a r l yr e l e v a n tw h e r e d e p o s i ta n dd e l i v e r ya x ee x p e n s i v eo r c o m p l i c a t e do p e r a t i o n s ，f o re x a m p l e ，s u p p l yc h a i nm a n a g e m e n t ，h e a v ym a c h i n e a n d8 0o n o nt h eo t h e rh a n d ，t h er e s o u r c ei sc o m m o n l yl i m i t e d ( e g 1 i m i t e d p o w e ro rm a n p o w e ra n dr e s t r i c t e dc a p a c i t yo fw a r e h o u s ee ta l 。) 。i nt h ec h a p t e r 4 ，w es t u d yt h ep r o b l e mo fp r o c e s s i n gj o b so ns i n g l em a c h i n ew i t hw a r e h o u s e c o n s t r a i n e d1 ，w l d l 7 ，w h e r e 7 ，l m ，凹) a n dl ，w 1 8 l 岛 k e y w o r d s ：s c h e d u l i n g ，m u l t i p r o c e s s o r ，l o ts i z i n g ，f l e x i b l eb a t c h i n g ，c o m - p l e x i t y , e x a c ta l g o r i t h m ，p s e u d o - p o l y n o m i a la l g o r i t h m ，c o l u m ng e n e r a t i o n v 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 硬棚、 沙年占月舌e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月 e t年 月 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：锲保亏文 z 年 月否日 第一章绪论 第一章绪论 在近代科技发展中，运筹学在国民经济和科学研究的各个领域的作用和地位 显得h 益重要，世界上许多发达国家对它非常重视，投入了大量的资金和研究力 量我国在这方面的研究也取得了一定的规模和成果题为美国国防部与数学 科学研究的报告认为，2 0 世纪9 0 年代以及整个2 1 世纪数学发展的重点，将从连 续的对象转向离散的对象，并且组合优化将会有很大的发展，因为“在这个领域内 存在着大量急需解决而又极端困难的问题，其中包括如何对各个部件进行分割、 布线和布局的问题”，这里的“分割、布线和布局”就与排序论密切相关 排序论又称为时间表理论，它是为满足个或多个优化目标，来安排稀有资 源来执行任务的决策过程作为组合最优化中广泛研究的，理论研究十分活跃的 学科之一，它有着深刻的实际背景和广阔的应用前景排序论是来源于实践的新 兴的肫用科学，它不仅应用于运输业，分派销售和其他的服务行业，尤其是在制造 业、生产系统中起着十分重要的作用例如一个生产纸袋的工厂，原材料主要是 成卷的纸张，生产包括三个阶段：印刷商标，粘合纸袋和缝合纸袋机器在每个阶 段的生产速度，能够印刷的颜色或者加工纸袋大小的能力都有所不同每个订单 就足一个要在支付日之前生产一定数量的特殊纸袋的任务一旦任务不能在支付 之日完成就要受到惩罚，l 司时也降低了信誉因此如何使惩罚尽可能的小，或者最 小总的生产时间来提高工厂效益，那么怎样安排生产是关键的又如机场中登机 通道的分配一个任务繁忙的机场每天都会使用许多登机通道接待几百架次飞机 起飞和降落，飞机通道和飞机型号不都是一样的飞机按照一定的时间表起飞和降 落，然而，这个时间表受制于许多不确定的因素，比如天气和其他的机场当某个通 道被一个飞机使用时，这架飞机起飞的时间可以看作是它的交货期限，如果知道 了在下一个机场他不能够在预先决定的时间降落，那么它就不能准时起飞，由惯用 的规则，旅客继续在候机厅等待，这个飞机通道继续被使用，于是耽误了其它飞机 使用这个通道因此不得不给出一个可行的分配，使飞机的总延误时间和通道的 服务时间最小等同样在信息产业领域，也存在着大量未得到很好解决的排序问 题例如计算机中央处理器执行任务的时间分配问题，然而不知道精确的执行时 间，但是可以计算出他们的随机执行时间，另外每一个程序都有自己的优先水平， 因此设计一个好的对各程序的时间分配表，能够大大的降低中央处理器总的执行 时间，从而节约了能源和提高了工作效率 尽管排序论实际使片j 的经验还不够丰富，但是他的迅速发展和应用的经验，说 明了在我们的实际生产活动中，除了直接运用排序的各种近似算法和精确算法之 同济大学博士学位论文 外，更可以用排序理论来指导和改进我们的工作，提高生产效率，给社会带来巨大 的经济效益 1 1 基本概念及分类 普遍认为，1 9 5 4 年j o h n s o n 的论文【5 2 为经典排序的第一篇文章从此，排序论 迅速发展起来，b a k e r 于1 9 7 4 年在书【6 】中对当时确定性排序的发展作了完整的 论述，但是他没有涉及到计算复杂性问题，1 9 7 6 年，c o f f m a n 在【2 4 】中详细讨论了 这一点2 0 0 2 年，h e n r y 4 7 分别对确定和随机排序研究进行综述随着排序论的 发展，不断涌现出越来越多的新型排序，例如可控排序f 5 9 ，9 1 】，资源受约束排 序【1 1 】，o n - l i n e 排序 1 9 ，7 7 和i 件可分拆同时加工排序等现代排序，2 0 0 3 年唐国春 等在f 8 1 1 中对现代排序作了详尽的论述。 排序问题按静态( s t a t i c ) 年i 动态( d y n a m i c ) ，确定性( d e t e r m i n i s t i c ) 并f i 非确定 性( n o n d e t e r m i n i s t i c ) b f f 丁以分为四大类在本文中，我们主要研究静态的确定性排 序问题 1 1 1 符号和分类 令j = 以，厶 表示将在m 台机器m = 尬，) 上加工的工件集 合在不至于混淆的情况下，我们有时候用工件如的下标歹来表示这个工件令矶j 1 表示工件j 在机器必上所需要的加工时间，这里i = 1 ，m ，j = 1 ，礼在单 机和同型机排序问题中，第一个下标将被省略在没有引起混淆的情况下，我们将 用p 1 j ，p 2 j ，与功分别替代l p l j ，；1 p 2 j ，与1 功在某些问题中，关 于工件歹的其他参数还有交货期( d u e - d a t et i m e s ) d j ，权或者价值( w e i g h t ) 职等在 本文中，我们始终假设所有的参数p md j ，职等均是非负整数 用7 r 表示工件 的个加工排序，那么定义下面的变量 q ( 7 r ) = 工件乃在排序7 r 中的完工时间； 岛( 7 r ) = 工件如在丌中投送到客户的时间 l j ( 7 r ) = q ( 7 r ) 一略，i 件乃在丌中的延迟； 弓( 丌) = m a x 易( 丌) ，o ) ，i 件如在丌中的延误； 瓣翥 篇雾l 即以咖略 第一章绪论 为描述方便起见，以后将用a ，l j ，乃和u j 分别替换上述变量。 在排序问题的分类方法中，标准三参数表示方法f 4 5 1q 俐7 ，被广泛使用( 见 文献l a w l e re ta l s s ) ，其中q 描述了机器的环境( m a c h i n ee n v i r o n m e n t ) ，例如口= p m 表示m 2 台同型机，如果m 没有出现，则同型机的个数是任意多个，如果m = l ，则我们考虑的问题是单机环境，表示为1 俐，y 。 参数p 描述了工件的特征( j o bc h a r a c t e r i s t i c s ) ，例如在本文中出现的主要有 勺表示工件的就绪时间不相同； 锄表示工件之间有顺序安装时间，即工件乃紧跟着五加工所需要的准备时间； d b a t c h 表示机器最多同时2 n t _ 的工件个数可以是不相同的，批的加工时间 等于这批工件中所有r t 件加工时间的最大者： i n c ( d e c ) 一d b a t c h 表示机器的容量是时间的增( 减) 函数； 而表示工件有截止e t 期( d u e - d a t e ) ； 壕不工件分别在其截止日期嘭投递； s 表示工件在固定的几个发送时间的其中一个发送 参数1 描述了优化的目标函数( o p t i m a l i t yc r i t e r i a ) 在本文中，我们所考虑的目 标函数主要有 c = m a x q 1 1 j n 表示m t c r 3 v 完工时间( m a k s p a n ) ； 良凹= m a x c 3 1 1 j 佗) 表示最后一个工件的投递时间； ( ) g 表示工件总( 带权) 完工时间； ( w j ) 岛表示工件总( 带权) 投递时间； l = m a x l j 1 j n ) 表示工件最大延迟； = m a x t # 1 j 佗) 表示工件最大延误； ( ) 弓表示工件的( 带权) 总延误； ( 嵋) 表示( 带权) 误工工件数 3 同济大学博士学位论文 例如用l i p b a t c h ，b 1 表示是多个供应 商；相似的，参数g 描述制造商的状况参数w 描述机器加工的能力，w 省略表示机 器加工能力没有限制参数q 描述机器的环境，同样的，参数p ，y 如前面所述，分别表 示工件的特征和优化目标 例如，如果在制造商问题中有g 个制造商，每个制造商有一台机器，目标是最 d , 力n m 费用和运输费用总和，那么这个问题表示为 g ，1 | i 垆+ 叫m ， 踟m ， ， 其中掣表示表示工件j 在制造商问题中的流程时间在供应商问题中，由于工 件在加工之前已经全部就绪，所以工件的流程时间等于它的完工时间，即f 尹= c 尹可苏表示从制造商七向顾客9 发送工件的次数；如果一个供应链排序问题是 单供应商的( 或者单个制造商) ，这个供应商( 或者制造商) 有一台机器，并且他的仓 库容量有限，因此当前加工完毕且没有发送的工件总长度不超过仓库的容量，目标 函数是最小误工工件和，这个问题表示为 l ，w 蚓 如果在这个问题中，我们的目标是使总的流程费用和运输费用之和最小，那么上述 问题表示为 1 ，w 巧+ 磋 办( 矽+ 彤m ， 如m ，h ) 4 第一章绪论 1 1 2 计算复杂性 柔性同时加工排序问题l i p b a t c h ，b 佗i 有多项式时间的最优算 法f b l p t ( f u l lb a t c hl a r g e s tp r o c e s s i n gt i m e ) j 6 3 然而当机器最多可同时加工的 工件个数是时间的分段增函数时，我们在第三章证明了l d e s d b a t c h i 僦。不 存在多项式时间的最优算法，因此求解问题l i d e s d b a t c h i 凹比1 防一b a t c h ，b 礼l 困难 一个最优化问题有三种形式：最优化形式，计值形式与判定形式当讨论求 解最优化问题的难易程度时，我们一般按其判定形式的复杂性把最优化问题分类 用p 表示多项式时间算法所能解决的判定问题类，即p 类是相对容易解决的最优化 问题，它们有有效算法用n p 表示更广泛的类问题，对于n p 类中的问题，并不要 求它的每个实例都能用某个算法在多项式时间内得到回答，我们只要求，如果z 是 问题答案为是的实例，则存在对x 的一个简短证明( 其大小以z 的长度的多项式为 界) ，使得能在多项式时间内检验这个证明的真实性有上述可见，p g n p 如果p 1 和p 2 都是判定问题，我们说p 1 在多项式时间内归结为p 2 ，当且仅 当p 1 有多项式时间的算法珥，并且奶是多次以单位时间把p 2 的算法奶用作子程 序的算法，我们把奶叫做p l t u p 2 的多项式时间的归结 判断问题p 0 ( p o e n p ) 称为是n p 完备的，如果所有其他的n p 问题都能多项 式地归结到p 0 n p 一完备问题是n p 类中“最难的”问题，一般认为它不存在多 项式算法当证明了所有其他的n p 问题都可以多项式地归结至j j p o ，而没有验 i t p o e n p 类时，我们称p o 是n p 一难的，例如，整数背包问题，排序问题l l i n c ( d e s ) 一 d b a t c h 等，但是它们有伪多项式时间算法 假设p 是个判定问题，是到的函数，我们用p ，表示限制于使n u m b e r ( i ) ，( 1 川那样一些实例上的p ，其中n u m b e r ( i ) 表示，中出现的最大整数，i a i 是实例j 的 规模如果对于某个多项式p ( 亿) ，p p 是n p 一完备的，则称p 是强n p 一完备的强n p - 完备问题没有伪多项式算法例如，3 一p a r t i t i o n i ；- j 题，哈密顿圈问题，以及排序问 题l i d b a t c h l ，1 ，w i s ieq 等 如果把排序问题按三参数法进行分类，通常认为有近万个不同的排序问 题中，只有近：的问题为p 类问题，而超过i 的问题为n p 一完备或者n p 一难的，剩 余问题中的大多数可能被证明为n p 一完备或者n p 一难的并且复杂性理论还让 人们意识到排序问题不太可能存在大范围的统一算法如果我们证明了一 个排序问题l 俐口z 是n p 一难的，那么我们说i i p i l m 也是n p 一难的，因为如果 令奶= ，则l 俐凹能多项式地归结到1 蚓l m 凹，其中表示1 蚓的 最优值图1 1 给出了排序问题的目标函数基本的归约关系 5 同济大学博士学位论文 图1 1 ：目标函数的归约关系图。 12 列生成方法 随着经济和科学技术的发展，一方面新的问题及模型层出不尽，同时伴随 着问题的规模越来越大，实际生产中需要解决的问题的难度也越来越大例 如，对于单台机器排序，带权总完工时间问题1 1 l w j c j 存在多项式时间算 法，耳 j w s p t ( w e i g h t e ds h o r t e s tp r o c e s s i n gt i m e s ) 序是其最优序，然而当问题模 型扩展，或者工件具有4 i 同的就绪时间，或者工件之问具有优先关系，或考虑多 台机器，则带权总完工时间问题职g 就相当复杂，是n p 一难的另一方面，从解决 实际问题出发，从归结得到的排序模型具有实际应用意义的角度来看，对大规模 的n p 一难排序问题，只是给出一些近似算法和近似解，已不能满足于实际的需要 因此，发展一些新的理论、方法和技术，设计性能优良的精确算法是目前排序论研 究中的一个值得深入研究的课题 对于大量n p 一难组合优化问题，已有的精确算法有分支定界算法，动态规划算 法以及列生成算法7 6 1 等以往的研究证明，列生成技术是分析和设计较大规模 的n p 一难的组合优化问题的精确算法和近似算法最为成功方法之- - 6 2 ，8 5 ，9 4 ， 9 5 ，9 7 ，9 9 】 1 2 1 列生成算法在整数规划方面的应用 最早提出列生成方法的文献有f o r d 和f 、u l k e r s o n 【3 4 】求解最短路问题， d a n t z i g 和w b l f 宅在文献【3 1 】中描述了线性规划的分解而较早应用列生成方法 是求解如下形式的线性规j z i j l p 4 1 ，4 2 】： m i n c z s t a x = b z 0 ， 6 第一章绪论 其中c 是佗维价值向量，非负变量x = ( x 1 ，z n ) ，a 是m 他矩阵，b 表示m 维约束向 量，并且佗m ，即它包含特别多的列 对于求解一般的整数规划p ： r a i n ，( z ) s t a x b ， z s z 是整向量 其中，( z ) 不一定是线性的函数，参量a ，6 如l p 中的定义，s 是一个多面体我们需 要p 的线性松弛问题l p 列生成的基本思想是，令集合 s + = z s i z 是整向量】 被包含有限个列( 点) 的集合替换如果s 有界，那么本身就是一个包含有 限个点的集合，不妨令p = 可1 ，) ，其中玑是几维向量，那么是一个由 点y l ，铷构成的凸胞，我们用c o n v ( s + ) 来表示因为d w 分解( d a n t z i gw b l f e d e c o m p o s i t i o n ) 【3 1 的基本思想就是用极点表示多面体，因此使用d w 分解，把 原问题分解成几个子问题如果s 无界，一个经典的结果是s 可以用有限个点的凸 组合与有限个仿射的线性组合来表示【6 9 】，更多的结果见文献【8 2 ，8 3 ，9 4 1 根据模 型的实际应用背景，在本文中我们只考虑s 有界的情形 当给定s + = y l ，珈) ，对于y y 舻可以表示为 y = f 纨a 奄， l k p 其中 fa 萨1 ， l 岛p k o ，1 ，k = l ，p 。 令c k = f ( y k ) ，a k = a y k 我们获得p 的等价的整数规划i p ： r a i nf c 入七 l k ：w y i i e l s t ：如犰l m ， ( 1 2 6 ) t j y i 0 ，且为整数，i i 其中l m 表示原材料的标准长度如果如0 ( m m ) ，当前解是最优解，否则，如 果k 0 ，那么p o p 的解确定了一个进基列，然后更新r m p 的列数j 卜j + 1 ，目标 函数的系数勺= 与每行z 的系数= 酊( i j ) d e s r o c h e r se ta 1 f 3 0 1 应用列生成方法求解带时间窗口的车辆择路问题( t h e v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s ) 时，他把p p 转化成求解一个约束最短 路问题( c o n s t r a i n e ds h o r t e s t p a t hp r o b l e m ) 关于v r p t w 一个经典模型是 m i n 勺巧 z 一o o j e j s t a i j x j 1 ，i ， j e j c j x j 一乱= 0 ， j e j fz 一钞：0 ， z 一 j j ， 巧0 ，歹z ( 1 2 7 ) ( 1 2 8 ) ( 1 2 9 ) u ，u o 且为整数( 1 2 1 0 ) 令睨，q p 依次表示的对偶变量，其子问题p p 是 m i n c j 一a i j w i 一勺q 一盼 i e i 如果一条路( 列) 经过点 如，i l ，旗，i k + 1 ，t k ，t k + 1 ) ，那么车辆选择它的费用 是 9 p 一 蚪 舻 q 脚 a 一 眦 脚 一 “ 岛 k 脚 同济大学博士学位论文 其中 g a r e y 和j o h n s o n 4 3 证明了c s p p 是n p 一难的，d e s r o c h e r se ta 1 f 3 0 1 给出p p 的一伪 多项式动态规划算法在v r p t w 的成功应用，极大的促进了列生成算法的 发展w i l h e l m 9 6 在1 9 9 9 年巧妙构造了有多种工具的装配问题( a s s e m b l ys y s - t e md e s i g nw i t ht o o lc h a n g e s ) 数学模型，用列生成方法求解其方法的基础 是f a z i o 和w h i t n e y 提出的状态转移图，用状态转移图计算不同工具被使用的顺 序 前面提到d w 分解 1 4 ，3 l 】可以把大规模的问题分解成几个相对较小的 问题第三类列生成方法就是在分支定界算法中，每一个节点处，使用d w 分 解f 1 3 1 用r m p 的对偶变量的值改进每一个s p 的目标函数系数，如果需要，则由 一个或者几个s p 产生进基列，而每一列对应着某个s p 多面体的一个极点最早 使用d w 分解技术求解i p 是在1 9 6 9 年，a p p e l g r e n 4 求解运输问题( s h i ps c h e d u l i n g p r o b l e m ) ，在1 9 7 1 年，a p p e l g r e n 【5 】又改进了分支的策略，并且每一次迭代都保留原 来的列，使列生成算法可以有效解决6 7 个周内的1 0 0 艘船的任务安排j o h n s o n 建 立了c s 的另外一个模型， r a i n f 鼠 j 二- t f ， s t z 沛+ s 严玩，i j ， m m l 溉m k ，m m ， i e l z 衲0 ，且为整数，i i ，仇m ， 8 i 0 ，i i 令”表示对应极点七( 七k ) 的变量，e c s 应用d - w 分解，得到r m p ： ( 1 2 i i ) ( 1 2 1 2 ) ( 1 2 1 3 ) ( 1 2 1 4 ) m i n fs i e i s t ( n ) 妒+ s 严6 t ，i i ， ( 1 2 1 5 ) k e km m f 妒= 1 ， ( 1 2 1 6 ) k e k a 血0 ，且为整数，k k( 1 2 1 7 ) 其中口孙等于在解七k 中，在卷仇上切割长度为如的块数，这里k 表示由子问 题s p 可行域的所有极点组成的集合若令y i 等于在卷m 上切割长度为如的块 1 0 廖+ q 脚 a +哌 随 l l 刁 白 脚 = 勺 第一章绪论 数，i j ，那么s p 如下所示， r a i n 町一q + m e mi e l 乩t 如l m , 仇m ， i ( 1 2 1 8 ) 轨m 0 ，且为整数，i i ，m m ( 1 2 1 9 ) 通过上面的计算，j o h n s o n 指出在建立模型时，为了使用d w 分解，要尽量避免对称 结构，因为使用三角形的块结构，得到的s p s 较容易求解1 9 9 7 生g ，s a v e l s b e r g h 7 5 在 求解一般的任务分配问题( g e n e r a l i z e da s s i g n m e n tp r o b l e m ) 时就充分说明了这一 性质，他建立g a p 模型如下所示， m i n i e lj - ， 础x i j = 1 ，歹z i e i a i j x i j 6 t ，i j ， z u o ，1 ) ，i ，歹z ( 1 2 2 0 ) ( 1 2 2 1 ) ( 1 2 2 2 ) 在计算过程中，每个节点处分解出多个子问题s p i ，i i m i n ：( 一晖) 一q ： j e j s t ：a i j x i j 6 f ， ( 1 2 2 3 ) j e j o ，1 ) ，j z( 1 2 2 4 ) 前面我们提到的整数规划线性松弛，都是求解其线性松弛，但是线性松弛得到 的解一般是非整数解有时人们也考虑拉格朗日松弛，对于g a r ，把每个工件只安 排给一个代理商的约束( 1 3 2 0 ) 放到目标函数中，贝i j g a p 的拉格朗日松弛是 唧nz 警 + 7 r ( 1 一) m t ( 1 3 2 3 1 ) ，( 1 ，3 ，2 2 ) ) ( 1 2 2 5 ) 。 i e ij e j j e jj e j 尽管