（应用数学专业论文）带尺寸、可拒绝的分批排序.pdf

曲阜师范大学博士学位论文 带尺寸、可拒绝的分批排序 摘要 排序问题一直是组合优化领域的一个热门方向，有着坚实的应用背景和深刻 的理论意义带尺寸的分批排序、可拒绝排序都是比较新的排序模型，本文就这 两个模型做了以下一些工作t 1 本文主要对带尺寸的分批排序极小化完工时间和的问题进行了研究对于 问题l i b ，s ，功= 1 1 q ，运用拆分的技巧首次给出了近似比是常数的三个近似 算法，近似比分别是4 ，2 ，和3 2 此外我们还给出例子表明后两个算法所给的界 是紧的接下来针对问题1 1 b ，s ，i e ，对已有的几个算法进行了分析，说明这 几个算法的最差性能比是无穷大 2 首次对可拒绝的分批排序问题1 1 b n ，r e j i w 1 t j + t p 和l i b n ，r e j i + t p 进行了研究。在已知它们是n p 一困难的基础上，我们给出 f 伪多项式时间精确算法以及f p t a s 算法这是最好的精确算法和近似算法； 因为对于n p - 困难问题，最好的精确算法就是伪多项式时间算法，而最好的近似 算法也只能是f p t a s 算法 关键词 排序，分批，可拒绝，n p 一困难，最差性能比，伪多项式时间，f p t a s ，动态规 划 曲阜师范大学博士学位论文 b a t c hs c h e d u l i n gw i t hn o n i d e n t i c a lj o bs i z ea n d w i t hr e j e c t i o n a b s t r a c t d u et oi t sp r o f o u n ds i g n i f i c a n c ei nb o t hr e a lw o r l da n dt h e o r y , s c h e d u l i n gh a s a l w a y sb e e na h o tt o p i ci nt h er e s e a r c ho fc o m b i n a t o r i a lo p t i m i z a t i o ns i n c et h e 1 9 9 0 s b a t c hs c h e d u l i n gw i t hn o n i d e n t i c a lj o bs i z ea n ds c h e d u l i n gw i t hr e j e c t i o n a r ea l lr e l a t i v e l yn e ws c h e d u l i n gm o d e l s ，w h i c ha r ea t t r a c t i n gm o r ea n dm o r e a t t e n t i o nr e c e n t l y i nt h i sd i s s e r t a t i o n ，m a n yn e wr e s u l t so ft h ea b o v et w om o d e l s o nc o m p l e x i t i e sa n da l g o r i t h m sa r ep r e s e n t e d ： 1 w em a i n l yd e a lw i t ht h eb a t c hs c h e d u l i n gp r o b l e mw i t hn o n i d e n t i c a lj o b s i z et om i n i m i z et h et o t a lc o m p l e t i o nt i m e s f o rp r o b l e m1b ，s j ，n21 1 q ， w el i s pt h et e ( 。h n i q u eo fs p l i t t i n ga n dp u tf o r w a r df o rt h ef i r s tt i m et h r e ea p p r o x i m a t i o na l g o r i t h m sw i t hc o n s t a n tr a t i o s ，t h er a t i o sb e i n g4 ，2a n d3 2r e s p e c - t i v e l y f u r t h e r m o r e ，w ep r o v i d ei n s t a n c e st os h o wt h a tt h et w ob o u n d s2a n d a 2a r et i g h t l a t e rw em a k ea n a l y s i so fs e v e r a le x i s t i n ga l g o r i t h m sf o rp r o b - l e n t1b ，s jl qa n ds h o wt h a tt h ew o r s tc a s er a t i o so ft h e s ea l g o r i t h m sc a nb e a r b i t r a r i l yl a r g e 2 w em a k et h ef i r s ts t u d yo ft h et w ob a t c hs c h e d u l i n gp r o b l e m sw i t hr e j e c - t i o nl i b 凡，r e j i 屿t j + t pa n dl i b n ，r e j i v j + t p h a v i n gk n o w n t h a tt h e ya r en p h a r d w eg i v ep s e u d o - p o l y n o m i a lt i m ea l g o r i t h m sa n df p t a s f o rt h e m t h e ya r et h eb e s te x a c ta n da p p r o x i m a t i o na l g o r i t h m sb yf a r a s f o rt h en p h a r dp r o b l e m s ，t h eb e s te x a c ta l g o r i t h mw ec a no b t a i ni sp s e u d o p o l y n o m i a lt i m ea l g o r i t h m ，a t t dt h eb e s ta p p r o x i n m t i o na l g o r i t h mc a no n l yb e f p t a s n 曲阜师范大学博士学位论文 k e y w o r d s s c h e d u l i n g ，b a t c hs c h e d u l i n g ，s c h e d u l i n gw i t hr e j e c t i o n ，n p h a r d ，w o r s te a s e r a t i o ，p s e u d o - p o l y n o m i a lt i m e ，f p t a s ，d y n a m i cp r o g r a m m i n g 第一章绪论 本章首先介绍7 排序问题的由来及应用背景，简单阐述了现代排序与经典排 序的主要区别，然后给出了必要的预备知识，最后概述了本文研究的主要问题及 研究结果 1 1 应用背景及问题描述 1 1 1 应用背景 半个世纪以来，排序问题一直是运筹学领域里一个很活跃的分支，在工农业 生产、经济管理、交通运输及服务业中都有着广泛的应用背景，发挥着巨大的作 用1 9 8 3 年。美国科学、工程与公共事务委员会数学组国防部分组在题名为美 国国防部与数学科学研究i 的报告中称，“在这个领域内存在着大量急需解决 而又极端困难的问题，其中包括如何对各个部件进行分隔布线和布局的问题” 这所谓的“分隔，布线和布局问题”，许多就与排序有关 排序问题( s c h e d u l i n g ) ，在自动化领域又称调度，是指给定若干机器和一组工 件以及某个目标函数，按照一定的要求合理地将这些工件分配到机器上，给每台机 器上的工件安排一个加工顺序以及相应的开工时间，使得给定的目标函数达到最 优这里的机器和工件都是抽象的概念，按照b a k e r 2 1 的解释，“排序领域中许多 早期的工作是在制造业的推动下发展起来的，所以描述排序问题时很自然会使用 制造业的术语，虽然排序问题在许多非制造业领域内取得了相当有意义的成果， 但是制造业的术语经常在使用因而，往往把资源( r e s o u r c e ) 称为机器( m a c h i n e ) ， 把任务( t a s k ) 称为工件( j o b ) ”首先请看下面几个例子； 例1 1 机械加工一个机械加工车间要加工一批机器零件，每一个零件都 具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个 机床上的加工时间可能不同如何安排加工顺序才能以最短的时间加工完所有的 零件? 这是一个流水作业排序问题 1 第一章绪论 例1 2 进程排序在计算机多道程序操作系统中，并行执行多个进程：在宏 观上同时执行多个进程，在微观上在任何时刻c p u 只能执行一个进程进程的 到达时间是不同的，怎样排序这些进程才能使c p u 的利用率最高或进程的平均 周转时间最短? 这也是一个排序问题 例1 3 机场排序【j l 在一个飞机场有几十个登机门，每天有几百架飞机降落和 起飞登饥门的种类和大小是不同的，班机的机型和大小也是不同的一些登机 门安放在能容纳大型飞机的地方，小登机门只能容纳小型飞机飞机按时刻表降 落和起飞，由于天气和机场的其它原因，时刻表也有很大的随机性当飞机占有 登机门时。到达的旅客下飞机，出发的旅客上飞机，飞机要接受诸如加油、维护和 装卸行李等服务如果飞机在下一个机场不能按时降落，此时为了节省燃料，飞 机不能起飞，登机时间推迟，飞机需要占有一个登机门而其它的飞机不能使用 机场的排序人员需要制订一个可行的方案，把登机门分配给降落的飞机，使机场 的利用率最高或晚点起飞的飞机最少。这也是一排序问题 在第二个例子中，c p u 被看作是机器，需要处理的进程则被看作是工件； 在第三个例子中，飞机放看成是工件，登机门被视作机器我们还可以举一些日 常生活中的例子，比如在银行和医院里，提供服务的银行员工和医生可以看作机 器，排队等候服务的顾客和就诊的病人则是工件由这几个例子可以看出，排序 问题有着极其丰富的内涵和广阔的应用背景 1 1 2 历史起源及研究概况 普遍认为j o h n s o n1 9 5 4 年的论文【4 】是经典排序研究的第一篇论文在随后 的半个世纪里，全世界共发表了排序方面的论文2 0 0 0 余篇，出版专著和教材4 0 余部，形成了运筹学领域很活跃的一个方向国内从事此方向的研究是很早而且 卓有成效的我国运筹学界的泰斗越民义先生早在上世纪6 0 年代就注意到了排 序问题的意义和理论上的难度，他和中科院的韩继业先生1 9 7 5 年的论文【5 】，开 创了中国研究排序问题的先河在两位先生的大力倡导下，国内的排序研究得到 了长足的发展一大批有才华的学者致力于排序问题的研究，最早的有唐国春教 2 曲阜师范大学博士学位论文 授、林诒勋教授，秦裕瑗教授，陈荣秋教授、唐恒永教授、孙世杰教授等。他们 发表了很多高质量的论文，出版了多部学术专著和教材，同时在应用方面也有许 多成果 作为排序问题的入门教材和参考书，我们向读者推荐陈礴教授等的ar e v i e wo fm a c h i n es c h e d u l i n g ：c o m p l e x i t y ，a l g o r i t h m sa n da p p r o x i m a b i l i t y 【6 】， 唐国春教授等的现代排序论【7 1 ，越民义先生的组合优化导论【8 】以及唐 恒永教授和赵传立教授的排序引论【9 】 1 1 3 经典排序与现代排序 排序问题有经典排序( e l r u s s i c a ls c h e d u l i n g ) 和现代排序( m o d e r ns c h e d u l i n g ) 之分根据e l a w l e r 等f 1 0 1 1 9 9 3 年的观点，经典排序问题有如下四个基本假设： ( 1 ) 资源的类型一台机器在任何时刻最多只能加工一个工件，一个工件在 任何时刻最多只能被一台机器加工； ( 2 ) 确定性排序问题一个实例所需的任何输入参数都是事先知道的、完全 确定的； ( 3 ) 可运算性经典排序是在可以运算的程度上研究排序问题，而不去顾及 诸如如何确定工件的交货期，如何购置机器和设备等技术上可能发生的问题； ( 4 ) 单目标和正则性经典排序假设排序的目的是使衡量排法好坏的一个一 维目标函数的函数值最优，此目标函数是任何工件完工时间的非减函数 唐国春教授等7 1 在其著作现代排序论里，详细介绍了发展较为完备的1 0 种现代排序模型，其中成组分批排序( s c h e d u l i n gw i t hb a t c h i n ga n dl o t s i z i n g ) 、 同时加工排序( b a t c hs c h e d u l i n g ) ，不同时开工排序( s h e d u l i n gw i t hn o n s i m u l t a - n e o u sm a c h i n ea v a i l a b l et i m e ) 和资源受限排序( r e s o u r c e - c o n s t r a i n ts c h e d u l i n g ) 打破了假设( 1 ) 的限制；可控排序( c o n t r o l l a b l es c h e d u l i n g ) 、随机排序( s t o c h a s - t i ( s r h t ，d u l i n g ) 、模糊排序( f u z z ys c h e d u l i n g ) 和在线排序( o n 1 i n es c h e d u l i n g ) 打破了假设( 2 ) 的限制；多目标排序( m u l t i c r i t e r i as c h e d u l i n g ) ，准时排序( j i t s c h e d u l i n g ) 和窗时排序( d u ew i n d o w ss c h e d u l i n g ) 打破了假设( 4 ) 的限制 3 第一章绪论 1 1 4 排序问题的表示 一个排序问题由机器环境、工件状况及目标函数三者来刻画由于在现实中这 三者可能出现的情况以及其组合关系是错综复杂的，随着研究的不断深入，新的排 序模型层出不穷，纳入我们视野的已有数千种我们一般用m = m 1 ，m 2 ， 表示机器的集合，用歹= ，如，厶 表示工件的集合，用p ，表示工件如 在机器上的加工时间，1 i m ，1sj n 机器环境只有一台机器即m = 1 的问题称作单机排序问题，否则称为多机 排序问题在多机排序问题中，研究较多的是平行机( p a r a l l e lm a c h i n e s ) 的排序问 题，此时也分为三种情况z 同型机( i d e n t i c a lp a r a l l e lm a c h i n e s ) 、同类机( u n i f o r m p a r a l l e lm a c h i n e s ) 和不相关机( u n r e l a t e dp a r a l l e lm a c h i n e s ) 同型机是指每个 工件在所有的机器上加工时间都相同，即p i ，= p j ，1 i 兰m ，1 jsn ；同 类机是指每台机器坛都有一个速度因子巩，工件以在机器上的加工时间 p 。，= p j s 。，1 i m ，1 j 弼不相关机是指工件在不同机器上的加工时间没 有任何关系 工件状况工件状况主要指工件加工时受到的约束或具有的性质，除了加工 时间( p r o c e s s i n gt i m e 简称工时) 以外，基本的约束或性质有以下几类t ( 1 ) 到达时间( a r r i v a lt i m e ) 或释放时间( r e l e a s et i m e ) 或准备时间( r e a d y t i m e ) ，唐国春教授统一称之为就绪时间，一般用q 表示，指的是工件以到达且 可以开始加工的时间n 没有明显表示出时表示所有工件零时刻同时到达有 时我们也用r j 0 ，r 来表示只有两个到达时间； ( 2 ) 工期或交货期( d u ed a t e ) ，一般用d ，表示，指的是工件以应该完工的时 刻，若工件此时没完工。则会对目标函数产生一定的影响； ( 3 ) 权或权重( w e i g h t ) ，一般用码表示，度量的足工件以的重要程度，在目 标函数中能体现出来； ( 4 ) 中断加工( p r e e m p t i o n ) ，指的是工件加工过程中可以任意打断，在随后 的某个时刻在同一台机器或其它的机器上继续加工而总的加工时间不变允许中 4 曲阜师范大学博士学位论文 断使得加工更加灵活，我们一般能得到比不允许中断更好的结果( 当然这并不绝 对，因而研究一个模型中断是否有效是有意义的允许中断也不意味着问题变简 单) 本文研究的问题均不允许中断加工； ( 5 ) 先后约束( p r e ( 1 e d e n c e ) ，指的是工件加工时必须满足一定的先后约束关 系，这种先后关系一般可用一个不包含有向圈的有向图来表示，特殊地，我们有 时研究此有向图是几条链( c h a i n s ) 或树( t r e e ) ，入树( i n - t r e e ) ，出树( o u t t r e e ) 的情况 ( 6 ) 在线( o n l i n e ) ，指的是工件的信息逐个释放，又有o v e rl i s t 和o v e rt i m e 之分； 不同的排序模型主要区别在工件环境上，形形色色的排序模型主要体现在这 上面，上述提到的工件环境仅仅是一些最基本最常见的 目标函数 排序的目标是极小化某个( 或多个) 目标函数，我们考虑的目标函数一般有 两种形式，极小化最大化形式( m i n m a xc r i t e r i a ) 以及极小化和的形式( m i n s u m c r i t e r i a ) ，即，m 。和办，其中，m 。= m a x 乃：1 jsn ，矗为工件以的完 工时间g ，的非减函数，1 j n 这种随着每个工件的完工时间的增加而增加 的目标函数称作正则的目标函数当然，现代排序研究的一些问题已经突破了目 标函数的正则性下面是一些最基本最常见的目标函数z ( 1 ) 最大完工时间( m a k e s p a n ) 氏“= m a x c ；：1sj n ( 2 ) ( 加权) 总完工时间( t o t a l ( w e i g h t e d ) c o m p l e t i o nt i m e ) n ( 叼) g = ( 屿) g ； 5 = 1 ( 3 ) 最大延迟( m a x i m u ml a t e n e s s ) l 。= m a x l j ：1 jsr l 5 第一章绪论 其寺l i = c j d j ； ( 4 ) ( 加权) 总延误( t o t a l ( w e i g h t e d ) t a r d i n e s s ) ( 嘶) 乃= ( 嘶) 乃 j = l 其中乃= m a x q d j ，o ： ( 5 ) ( 加权) 误工总数( ( w e i g h t e d ) n u m b e ro ft a r d yj o b s ) ( 哟) 屿= ( 嘶) ， j = 1 其中q d j 时= 1 ，gs 由时v j = 0 为了表示不同的排序模型，国际上通用g r a h a m 等提出的三参数法【1 1 】，即 用q 例，y 来表示一个排序问题，其中n 代表机器环境，芦和，y 分别代表工件环 境和目标函数o 的取值范围一般是 1 ，p iq ，r ，分别表示单机，同型机，同类 机，不相关机我们还用p m ，q 。，尼。分别表示机器台数m 为常数而非输入的相 应廿j 题，这与m 作为输入的一部分的情况仅仅在分析算法的时间复杂性时有区 分比如一个算法的时间复杂性为0 ( n “) ，则在f i m 机器环境下此算法是多项式 时间的，而在p 机器环境下则不是多项式时间的卢和7 基本的取值前面我们 已经介绍过了用三参数法，本文所研究的排序问题可表示为： ( 1 ) 1 i b ，叼，乃= 1 l g ； ( 2 ) 1 1 日n ，r e j 【屿乃4 - t p ； ( 3 ) l i b mr e j i 屿v j4 - t p ； 其中，b 表示分批排序， 知表示工件带尺寸，r e j 表示可拒绝排序，t p 表示被拒绝工件的总惩罚费用 6 曲阜师范大学博士学位论文 1 2 预备知识 1 2 1 排序问题的求解 排序问题本质上是一类组合优化问题，针对问题的每一个实例，其可行解即 可行排序的个数一般是有限个，因而我们可以用枚举的方法来求得其最优解，然 而一般情况下这种幼稚的想法是没有任何意义的，因为可行解的数目可能是异常 巨大的，即便是借助于目前最先进的巨型电子计算机，所花费的时间也是绝对不 能为我们所接受的 1 9 8 0 年代以后，排序问题的研究引入了计算复杂性理论计算复杂性理论认 为，时间复杂性为多项式的算法足我们理论上可以接受的算法随着研究的不断 深入，我们发现大多数的排序问题是n p 一困难的，目前一般认为不可能存在多 项式时间的精确算法，从而我们的工作主要足设计性能良好的近似算法衡量精 确算法好坏的标准只有一个，那就是运行时间，相应地我们需要分析其时间复杂 性；而衡量一个近似算法，我们一方面要看运行时间，更重要的一方面是看其近 似程度，因为我们通常所说的近似算法都是指多项式时间的，这样的算法其运行 时间会随着计算机运行速度的飞速提高以及对算法细节的不断改进而显著降低 分析近似算法近似程度的途径一般有三种，最差性能分析( w o r s tc a s ea n a l y s i s ) 、概率分析( s t o c h a s t i ca n a l y s i s ) 和数值模拟分析( s i m u l a t i o na n a l y s i s ) 最 差性能分析，顾名思义，即以此算法最坏情况的表现来衡量此算法，是我们最常 用的分析标准这种标准具有一个明显的缺陷，即最差情况一般都是分析过程中 人为构造出来的极端特殊的例子，这种极端情况在实际中可能根本不会发生或者 发生的概率极小，从而对于那些对最坏情况不是很敏感的实际问题来说，要求一 个算法的最差近似比很小无疑足太苛刻了，因而很多时候甲均情况分析是很有必 要的，常用的手段有概率分析和数值模拟分析数值模拟分析主要依靠直觉和经 验，没有理论基础，因而很多时候只能作为辅助手段来说明算法的性能由于概 率分析需要首先确定输入数据的概率分布，这通常并不容易，再加上理论上的困 难，采用概率分析的学者比较少尽管如此，概率分析还是一个前景很光明的方 7 第一章绪论 向下面给出最差性能分析中一些基本的概念我们提到的组合优化问题指的都 是输入数据和目标函数值为非负整数且极小化目标函数的问题 定义2 1 我们称一个算法一4 是组合优化问题p 的一个p 一近似算法( a p - p r o x i m a t ea l g o r i t h m ) ，如果a ( z ) o p tc z ) p 对p 的任何实例i 均成立，其中 o p t ( 1 1 指的是，的最优值 定义2 2 如果上述定义中的p 是最小可能的，即p = i n f 5 ：4 ( z ) o p t f f ) s 6 v i 尸l 则我们称p 为算法一4 的最差性能比( w o r s tc a s ep e r f o r m a n c er a t i o ) 如果一个近似算法的最差性能比为无穷大或者我们没有分析得到一个有界的 近似比，则我们称此算法为一个启发式算法( h e u r i s t i c ) 也有的学者将近似算法 统称为启发式算法 定义2 3 如果一族算法 钆 。，对于任意小的正数e ，a 是问题p 的一个 ( 1 + e ) 一近似算法，而且如果我们把e 看成常数其时间复杂性为多项式的，我们 则称这族算法为问题p 的p t a s ( 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 ) 算 法 如果上述定义中我们进一步要求4 。的时间复杂性还是1 e 的多项式，则称 4 。k 为问题p 的f p t a s ( f u l l yp 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 ) 算 法 引理2 1 强n p 困难问题不存在伪多项式时间的精确算法，也不存在f p t a s 算法，除非p = np 在英文里强n p 一困难写作s t r o n g l yn p h a r d 或u n a r yn p h a r d ，而一般的 n p 困难称作w e a k l yn p h a r d 或b i n a r yn p h a r d 此引理的详细证明以及组合 优化的其它基本知识可以参考p a p a d i m i t r i o u 等的 1 2 i 1 2 2 基本方法和技巧 排序问题本质上都是离散的，不像连续问题一样有一整套的工具但人们在 长期的研究过程中还是总结出了一些基本的方法和技巧 设计精确算法常用的方法是动态规划( d y n a m i cp r o g r a m m i n g ) ，另外还有分 8 曲阜师范大学博士学位论文 支定界( b r a n c ha n db o u n d ) 、局部搜索( 1 0 c a ls e a r c h ) ，模拟退火( s i m u l a t e d a n n e a l i n g ) 和遗传算法( g e n e t i ca l g o r i t h m ) 等；设计近似算法常用的方法是启发 式算法或在精确算法( 一般是动态规划算法) 的基础上进行数据处理，另外还有 连续化的方法目前绝大多数启发式算法在本质上都是贪婪的( g r e e d y ) ，这在问 题结构较简单时是有效而易分析的，针对结构较复杂的问题，最近另有学者利用 基因算法或神经网络来设计改良近似算法( m e t ah e u r i s t i c ) 还有人用整数规划来 研究排序问题目前的算法大多数都是确定性的，随机算法也有人研究 在算法设计中一个很重要的概念是优势集( d o m i n a n ts e t ) 所谓优势集是指 解空间的一个子集，对于解空间中任意一个排序都可在此子集中找到一个不劣于 此排序的解也即优势集是包含问题最优解的一个集合很多时候我们研究的方 法是找4 组好的优势规则( d o m i n a n c er u l e ) 以确定一个尽可能小的优势集，然后 用动态规划、搜索算法甚至简单枚举法从此优势集中找一个最优解或近似解 类似的思想还有6 一优势集 1 ) 的概念以及数据处理时的一些技巧j 一 优势集是优势集概念和思想的推广，是指包含一个j 一近似解的解空间的一个子 集6 = 1 时便是一般的优势集的概念设计6 一近似算法的一个基本思路可 以是确定一个尽可能小的6 一优势集然后从中选一个最优的在数据处理时，我 们可以损失一定的算法精度而使其具有一些良好的性质常用的方法有数据舍入 ( r o u n d i n gt h ei n p u td a t a ) 以及状态空间修剪( t r i m m i n gt h es t a t e s p a c e ) 等 1 2 3 离线与在线 经典排序问题研究的都是离线( o f f - l i n e ) 模型，即排序所需要的所有信息我 们都预先已知随着研究的不断广泛和深入，人们发现有许多实际问题是在线的 ( 0 1 1 一l i n e ) ，即信息不是零时刻全部释放，而是在工件加工过程中逐步释放 1 2 4 几个常见的n p 一困难问题 下面几个组合优化问题的n p 一困难性后面将要用到，故单独做一些介绍我 们叙述其判定形式( r e c o g n i t i o nv e r s i o n ) 9 第一章绪论 装箱问题( b i np a c k i n gp r o b l e m ) 有一集物品 1 ，2 ，竹 ，每个物品j 有一个称作体积的参数“，给定一个称为容积的参数b 和一个界( t h r e s h o l d ) u ， 是否存在此集物品的一个划分，使得每个子集物品的总体积不超过b 而划分的 总子集数小于或等于c ，? 背包问题( k n a p s a c kp r o b l e m ) 任给n 组正整数 ( ，勺) ：1 j n 和 正整数b ，其中码称作价值，8 ，称作尺寸，而b 是容积任给一个界u ，是否 存在一个指标集彤 1 ，2 ，n 使得难耳u 而且，k b ? 二划分问题( p a r t i t i o np r o b l e m ) 任给2 m 个非负整数x = n 1 ，a 2 ，n 2 。 是否可以将x 分成两部分x 1 和以使得。托a ；= 断x 。= ( n l 十a 2 + + a 2 。) 2 7 特别地，如果我们还要求i x - j = l x 2 l = m ，其中i x - i 和i 五毛1 分别 代表它们的基数，则问题称作等基二划分( e q u a lp a r t i t i o np r o b l e m ) 1 2 5 几个经典算法 在研究经典排序过程中，人们发现了许多简单而有效的算法，这是我们研究 现代排序问题的基础本小节我们将介绍几个常用的经典算法 s p t 算法对于问题l l | q ，简单地按工时非减的顺序j b o i e p 可得到最优 排序，这就是s p t ( s h o r t e s tp r o c e s s i n gt i m ef i r s t ) 算法对于问题1l w 3 0 ， 我们可以按p ，w $ 非减的顺序加工，称为w s p t ( w e i g h t e ds p t ) 算法，它是由 s m i t h 首次提出的，又称为s m i t h sr u l e 1 3 e d d 算法对于问题1 i i l 。a x ，工件按工期非减的顺序进行加工即可得到最优 排序，这就是所谓的e d d ( e a r l i e s td u ed a t ef i r s t ) 算法【1 4 1 l s 算法对于问题p i | c k 。，l s ( l i s ts c h e d u l i n g ) 算法描述为，将所有工件按 任意的顺序排成一个列表，工件按此列表顺序进行加工，每一时刻将未加工的工 件放到最早完工的机器上进行加工l s 算法的最差性能比为2 一i m ，其中m 为机器的台数 l s 算法是由g r a h a m 于1 9 6 6 年提出的【1 5 1 ，后来他发现如果将 工件预先按工时非增的顺序排列，则我们可以得到更好的结果，其最差性能比为 4 3 1 ( 3 m ) ，这就是所谓的l p t 算法1 16 】 1 0 曲阜师范大学博士学位论文 1 3 本文主要结果及创新点 分批排序问题是一类应用背景极强的新型排序问题，近年来引起了国际上越 来越多的学者的关注，新的成果不断涌现本文主要在带尺寸的分批排序、可拒 绝排序这两方面给出了一些新结果 一在第二章中我们主要对问题1 1 b ，s j ，聊= 1 i g 进行了研究，对于该 问题首次提出了近似比是常数的近似算法之前u z s o y 曾经证明了该问题的n p - 困难性，我们从另一个角度证明了这一问题是n p - 困难的之后利用工件可拆分 时该问题是多项式可解的，以及乖j 用工件可拆分时的最优解和原问题最优解的关 系，我们给出了近似比分别为4 和2 的近似算法；进一步，如果我们将批的容量 限制为1 ，将工件区分为大小工件的话，利用小工件可拆分时的最优解和原问题 的最优解的关系，又可以得到最差性能比是3 2 的近似算法此外，我们还给出 实例表明算法所给的界2 和3 2 是紧的 二可拒绝排序也是一类很有意义的新型排序问题，与经典排序问题中工件 必须加工相比，这类排序问题显示出了更大的灵活性z 某个工件可以不加工，但 是要付出相应的惩罚在第三章中我们首次对两个可拒绝的无界批量分批排序问 题进行了研究具体地，我们得出了如下结果， ( 1 ) 对于问题l f b 凡，r e j i 吣弓+ t p ，提出了伪多项式时间精确算法 ( 2 ) 对于问题l i b n ，r 可i 屿v j + t p ，提出了伪多项式时间算法和f p - t a s ( f u l l yp 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 ) ( 3 ) 我们给出的伪多项式时间算法和f p t a s ，分别是针对上述两个可拒绝问 题的最好的精确算法和近似算法因为我们知道，对于一个n p 困难问题来说， 最好的精确算法是伪多项式时间算法，而最优的近似算法即为f p t a s 三在第四章中，针对带尺寸的分批排序问题l b ，8 ，i c ，我们对已有的 几个启发式算法进行了分析，指出这几个算法的最差性能比是无穷大 第二章工件带尺寸的分批排序的几个近似算法 本幸主要对工件带尺寸的分批排序进行了研究。借助于拆分的技巧，对问题 1 l b ，s j ，功= i i q 给出了最差性能比分别为4 , 2 ，和3 2 的近似算法；此外，我 们还给出例子表明后两个算法所给出的界2 和3 2 是紧的 2 1 引言 在本章中，我们主要研究如下排序模型：工件集合记为j = ，如，厶 机器为单台批处理机，批的容量为b ，工件同时到达并且有着单位加工时间工 件山的尺寸记为8 j ( j = 1 ，2 ，n ) 同一批工件的尺寸之和不能超过批的容量 b ，并且加工不允许中断目标函数是极小化工件的完工时间之和；用传统的三元 素表示方法，此问题可表示为1 i b ，聊= 1 f q ， 工件带尺寸的分批排序问题，已经取得的比较重要的结果有tr u z s o y 1 7 1 对 于问题1 b ，s ，| g 提出了一个分支定界算法和几个启发式算法 g c z h a n g 等【18 1 对r u z s o y 提出的启发式算法进行了严格的理论分析，在此基础上他们 对问题1 i b ，s f g 。提出了一个最差性能比为7 4 的近似算法这是目前为止对 于该问题最好的近似算法对于在线模型，张玉忠和柏庆国f 1 9 】就两个到达时间 的一致情形给出了竞争比不超过s 2 的在线算法；对问题1 j b ，s j l g ，y q s h i 和g c z h a n g 2 0 1 对工时为常数的在线情形进行了研究，给出了竞争比为 3 的 在线算法此问题还有待于进一步的深入研究 2 2 对于问题l i b ，s j ，p j = l l 岛的两个近似算法 对问题1 i b ，勺，功= 1 q ，r u z s o y 1 7 】证明了它是n p - 困难的他们采 用的办法是通过背包问题和该问题的多项式化归在本节中，我们先给出n p 困 难证明的另一种表述然后给出一个4 近似算法和一个2 - 近似算法 定理2 2 1 问题l l b ，s j ，乃= 1 i e q 是n p 一困难的 曲阜师范大学博士学位论文 证明：我们通过等基二划分和该问题之间的多项式化归来证明该定理 等基二划分问题可以描述为tg 是2 n 个正整数的集合g = a l ，a 2 ，啦。 是否存在一个xc 1 ，2 ，2 n 使得a j = a = 1 2 啦且满足i x i = n ? i e x ；= l 任给等基二划分问题的一个实例，构造问题1 l b ，s 1 ，功= 1 i q 的实例如 下t 工件集合为j = 以，以，如a 工件 的尺寸8 。满足下列关系：8 ；= a l + d ( d 2 a ) ( i = l ，2 ，2 n ) 批的容量满足b = a + n d 显然此例的构造在多项式时间内可以完成 下面我们证明；等基二划分问题有解 = 号对于所构造的排序问题的实例， 存在一个可行排序，其目标函数值3 n 争：等基二划分问题有解不妨假设x = 1 ，2 ，仃 考查排序丌= ( b 1 ，b 2 ) 其中b 1 = ，也， ，b 2 = 厶+ l ，厶十2 ，如 显然满足q ( h ) 3 n 故必要性得证 ， 一：对于所构造的排序问题的实例，如果存在个可行排序7 r 满足q ( 7 r ) j 3 n ，则必然有g 。( 7 r ) = 2 否则，如果c k 。( 7 r ) 2 ，我们必然有1 8 1 1 扎( b l 就是7 r 的第一批) 不 然则有下列不等式成立：q ( ”) n + 2 一1 ) + 3 = 3 n + 1 这和假 ， 设g ( 7 r ) 3 n 矛盾故如果c k 。( 丌) 2 ，则必然有i b zj 佗然而根据 ， 工件尺寸以及批容量的设定，任何付+ 1 个工件都不能装在一批中因此我们有 c 。( ”) = 2 注意到s = 2 b ，因此我们有口= ( b l ，b 2 ) 1 8 1 i = i b 2 i = n 此 外，这两批都是满的因此等基二划分问题有解充分性得证 在本章中我们用( p ) 表示问题1 l b ，s j ，p = 1 l q 用( s p ) 表示问题 l i b ，s j ，乃= 1 l g 当工件可拆分时的情况在( s p ) 中，工件j a j = 1 ，2 ，n ) 可以被分成若干部分。这几部分分别被记为以：，乃。，氐每一部分如( f = 1 ，2 ，k ) 有一个权重，在数量上等于8 3 1 ；加工时间仍为1 我们将每一部分 1 3 第二章工件带尺寸的分批排序的几个近似算法 的完工时间乘上它的权重再求和，就得到可拆分时的目标函数值 接下来我们证明问题( s p ) 是多项式可解的首先给出几个引理 引理2 2 1 将问题( s p ) 的最优排序记为矿；则在矿中至多只有最后一批工 件是不满的 证明；此引理的结论是显然的，因为工件可以拆分 引理2 2 2 将问题( s p ) 的最优排序记为矿；则在仃中工件按照尺寸非减的 顺序被先后安排 证明：假设7 r 是问题( s p ) 的一个可行排序 如果在，r 中存在两个工件 和以满足t8 i 8 f ，y b l ( 排序”的第z 批) ， 。b k 且f ( 这里y 是 的最后一部分，而z 是以的第一部分) ，我们对排 序丌做如下调整： ( 情形1 ：) 如果有s ( z ) = s ( ) ，则简单地交换。和y 的位置； ( 情形2 ：) 如果有8 ( x ) s ( ) ，则将y 与$ 的一部分( 记为霉i ，其中满足 s ( x 1 ) = s ( ) ) 交换； ( 情形3 ：) 如果有s ( x ) ( k a ) b 在推导上面不等式时我们舍弃了剩下的1 1 , 一j 工件j j + h 厶因为根据算 法a 1 ，如果工件集合是 以，如，以，工件以还是被放在批或中从上面不 等式，我们得到k 1 十【2 8 | i b 更进一步地，我们有k 2 1 ，这就意味着 q ( 7 r ) s2 c j ( 7 r ：) z 一1 我们知道k 2 1 = 2 ( t 1 ) + 2 4 “一1 ) 这就意味着 g ( 7 r ) 4 ( 。q ，( ；) + 屿，c j ：( ”：) ) 对所有的工件求和，我们有g ( 7 r ) s4 ，( ：) 4 g ( 矿) jj 故定理2 2 3 得证 接下来，我们对于问题( p ) ：i i b ，8 1 ，乃= 1 i 白，给出另外一个近似算法 算法a 2 ： s t e p1 ：根据算法a 得到问题( s p ) 的最优排序7 r ：； s t e p2 ：对排序7 r ：做如下调整，如果工件与在7 r ：中被拆分并且有如 既- u 研，则将工件以自成一