（基础数学专业论文）关于重新排序问题的研究.pdf

摘要 排序就是在一定的约束条件下对若干个要加工的工件或任务在指定的机器上按时 间进度进行分配和调度，使某一个或某一些指标达到最优 重新排序问题是一种新型的排序模型它有着重要的实际应用背景生产部门 根据自己的生产计划或是由客户提出的要求，在生产前一定时期内事先有一个作业方 案，将已有的任务或订单按照某一规则安排好，使某一目标值最优但是在即将开始 生产之前或在生产过程中又有新的客户订单或任务到达这时就要把新的任务和原有 的还未加工的任务一起加工为了不失信于对原客户的承诺或耽误原任务的完成，这 就要求在原有的工件或任务的次序不至于打乱的过多的前提下，使得总的目标函数值 达到最优h a l l 和p o t t s ( 2 0 0 4 ) 在前人研究的基础上，系统地研究了重新排序问题 他们引入了序列错位( s e q u e n c ed i s r u p t i o n ) 和时间错位( t i m ed i s r u p t i o n ) 的概念，研 究了在原来最优排序和任意排序的基础上重新排序，在原来排序的序列错位和时间错 位不至于太大的情况下，使目标函数最优的问题 多目标排序作为一种多目标决策，在解决经济、管理、工程、军事等领域出现的 复杂问题中起着越来越重要的作用例如，在一个工厂的生产过程中，生产决策者不 但想要使工件的总完工时间最小以减少生产费用，还要尽量使误工工件的个数最少， 以更好地满足顾客的要求多目标排序包括字典序最优问题、p e r a t o 最优解问题和组 合目标函数最优问题 在线排序是指每个工件的信息在该工件到达之前是未知的在工件的到达时间 得到该工件的所有信息并允许对该工件进行加工；而且一旦决定工件的安排就不允许 改变而离线排序在安排所有工件之前便知道所有工件的信息衡量一个在线排序算 法最常用的指标是它的竞争度( c o m p e t i t i v e n e s s ) ，即把在线排序算法的结果与对相同 工件运用离线排序算法得到的最优排序的结果进行比较更确切的说，我们用竞争 比( c o m p e t i t i v er a t i o ) p 来衡量一个在线排序算法的性能对于使目标函数为最小的在 线排序问题，竞争比p 定义为对问题的所有实例的比值g 岛的上确界，其中g 和岛 分别表示由这个在线排序算法得到的目标函数值和相应的离线排序的最优值 本文的内容分四部分：第一部分研究了几种特殊情形的重新排序模型( 第二章) 第二部分研究了一种新型重新排序模型( 第三章) 第三部分研究了多目标的重新排序 问题( 第四章) 第四部分研究了在线的重新排序问题( 第五章) 在第二章中，研究了几种特殊情形的重新排序模型，其主要结果如下：对一些未 解问题和强n p 困难问题，( 1 ) 给出了当工件的加工时间与工期相容或原始工件保 持其相对顺序时，使得最大延迟和加工时间和为最小的多项式或拟多项式时间算法； ( 2 ) 给出了当工件具有相同的加工时间或具有相同的工期时，使得误工和为最小的多 项式或拟多项式时间算法；( 3 ) 给出了当工件的加工时间与权重反相容时，使得加权 完工时间和为最小的多项式或拟多项式时间算法 在第三章中，对于具有到达时间的最小化最大完工时间的重新排序问题， ( 1 ) 给出了在最大序列错位约束下的最小化最大完工时间的重新排序闯题的多项式时间算 法：( 2 ) 给出了在总序列错位和约束下的最小化最大完工时间的重新排序问题的多项 式时间算法；( 3 ) 证明了在最大时间错位或总时间错位约束下的最小化最大完工时间 的重新排序问题是强p 一困难的 在第四章中，对于多目标的重新排序问题，本文将错位量作为第二目标来考 察，研究了四种错位量( d m 。( 矿) ，。( 矿) ，d ( 丌) ，锄( 矿) ) 与传统的目标函 数( 如g 。，l 。，嘶岛) 的相互组合问题，给出了多目标排序中字典序最优问 题、p e r a t o 最优解问题和线性组合目标函数最优问题的多项式时间算法或拟多项式时 间算法 在第五章中，主要研究了在线重新排序问题即在原始工件已经按照某一规则排 好，而新工件在原始工件的加工过程中是按时间顺序到达的在此情形下，本文分别 给出了在各种错位量约束下，目标函数为最小化最大延迟的竞争比为2 的在线排序算 法和最小化最大完工时间的竞争比为3 2 的在线排序算法 关键词：排序；重新捧序；多目标捧序；在线捧序；错位量；动态规划；计算 复杂性 i i a b s t r a c t s c h e d u l i n gi st oa l l o c a t es o m ej o b so rt a s k st os o m em a c h i n e su n d e ral i m i t e dc o i l - d i t i o na c c o r d i n gt ot i m eo r d e r ，a n di no r d e rt oo p t i m i z es o m eo b j e c t i v e s r e s c h e d u l i n gi so n eo fs i g n i f i c a n tm o d e ms c h e d u l i n gm o d e l 8a n di ti sm o t i v a t e db y i m p o r t a n ta p p l i c a t i o n s t h ep r o b l e mo fr e s c h e d u l i n gi nt h ef a c eo fd y n a m i c a l l ya r r i v m g o r d e r si 8f a c e dc o n s t a n t l yb ym a n u f a c t u r i n gc o m p a n i e s t h em a n u f a c t u r i n gc o m p a n i e s h a v eb e e nm a d et h e i rp r o d u c t i o ns c h e d u l e si ne a r l i e ra c c o r d i n gt ot h e i rp l a n e so rs o m e c u s t o m e r s c a l l ，a n ds c h e d u l et h ej o b sb ys o m er u l et oo p t i m i z es o m eo b j e c t i v e h o w e v e r i tf r e q u e n t l yh a p p e n st h a ta d d i t i o n a lo r d e r sa r r i v ea f t e ras c h e d u l eh a sb e e nd e v e l o p e d t h e s eo r d e r sm u s tt h e nb ei n t e g r a t e di n t ot h es c h e d u l es oa st oo p t i m i z es o m em e a s u r e o fs y s t e mp e r f o r m a n c ew i t h o u tc a u s i n gu n d u ed i s r u p t i o ni nt h e8 h o p b a s e do ns o m e r e s e a r c h e s ，h a l la n dp o t t s ( 2 0 0 4 ) s t u d i e dt h ep r o b l e mo fr e s c h e d u l i n ga n di n t r o d u c e dt h e c o n c e p t i o no fd i s m p t i o u s t h e yc o n s i d e r e dt h er e s c h e d u l i n gp r o b l e mt om i n i m i z et h e m a x i i n u l i ll a t e n e s sa n dt o t a lc o m p l e t i o nt i m eu n d e ral i m i to nt h ed i s r u p t i o nc o n s t r a i n t s m u l t i c r i t e r i as c h e d u l i n g ，a saw a yo fm u l t i - o b j e c t i v ed e c i s i o n - m a k i n g ，p l a y sa ni r a - p o r t a n tr o l ei ns o l v i n gc o m p l i c a t e dp r o b l e m sa r i s i n gf r o me c o n o m i c s ，a d m i n i s t r a t i o n ，e l i - g i n e e r i n g ，e t c f o re x a m p l e ，af a c t o r ya d m i n i s t r a t o ru e e d st oa r r a n g et h ej o b st ob e p r o c e s s e ds u c ht h a tt h et o t a lc o m p l e t i o nt i m ei 8m i n i m i z e df i r s t l yt or e d u c et h ep r o - c e a s i n gc o s ta n dt h et a r d yj o b sa r el i m i t e dt oal o w e s tl e v e ls e c o n d l y , a n dt os a t i s f y t h ec l i e n t s m u l t i c r i t e r i as c h e d u l i n gi n c l u d e sl e x i c o g r a p h i c a lo p t i m i z a t i o no rh i e r a r c h i c a l o p t i m i z a t i o n ，p a r e t oo p t i m i z a t i o na n dc o m p o s i t eo b j e c t i v ef u n c t i o no p t i m i z a t i o n o n - l i n es c h e d u l i n gi sam o d e r ns c h e d u n n gm o d e l i nw h i c ht h ej o bi n f o r m a t i o nm a y n o tb ek n o w ni na d v a n c e a j o bb e c o m e sa v a i l a b l ef o rp r o c e s s i n ga ti t sa r r i v a lt i m e ，a n di t s p r o c e s s i n gt i m eo n l yb e c o m e sk n o w nu p o n i t sa r r i v a l o n c et h ej o b sh a v eb e e ns c h e d u l e d ， t h es t a t e so ft h ej o b sc a n n o tb ec h a n g e d i nt h eo f f - l i n es c h e d u l i n g ，t h ei n f o r m a t i o no f a l lj o b sh a sb e e nc o m p l e t e l yk n o w ni na d v a n c e t h ep e r f o r m a n c eo fa no n - l i n ea l g o r i t h m i sd e s c r i b e db yi t sc o m p e t i t i v e n e s s ，i e t h er a t i oo ft h er e s u l to ft h eo n - l i n ea l g o r i t h m i i i a n dt h eo p t i m a lv a l u eo ft h eo f f - l i n es i t u a t i o nf o rt h es a m ej o b s e x a c t l y , f o rt h ep r o b l e m o fm i n i m i z i n go b j e c t i v e t h ec o m p e t i t i v er a t i opo fa no n - l i n ea l g o r i t h mi sd e f i n e da 8t h e s u p r e m u mo ft h er a t i oo fc a n dc o ，w h e r ega n dc oa r et h eo b j e c t i v eo fs c h e d u l i n g o b t a i n e db yt h eo n - l i n ea l g o r i t h ma n da no p t i m a lo f f - l i n ea l g o r i t h m ，r e s p e c t i v e l y t h i sp a p e ri n c l u d e sf o u rp a r t s i nt h ef i r s tp a r t ，s o m es p a c i a ls o l v a b l ee a s e so f r e s c h e d u l i n gm o d e l sa r ec o n s i d e r e d ( c h a p t e r2 ) i nt h es e c o n dp a r t ，t h en e wr e s e h e d u l i n g m o d e l sa r es t u d i e d ( c h a p t e r3 ) i nt h et h i r dp a r t ，m u l t i - c r i t e r i ar e s c h e d u l i n gm o d e l s a r ed i s c u s s e d ( c h a p t e r4 ) i nt h el a s tp a r t ，o n - l i n er e s e h e d u l i n gp r o b l e m sa r ep r e s e n t e d ( c h a p t e r5 ) i nc h a p t e r2 ，t h ef o l l o w i n gr e s u l t sa r ed e v e l o p e d ( 1 ) t h er e s c h e d u l i n gp r o b l e m t om i n i m i z et h em a x i m u ml a t e n e s so rt h et o t a lc o m p l e t i o nt i m eu n d e ral i m i to nt h e d i s r u p t i o nc o n s t r a i n t sw h e nd j ，力a r ec o m p a t i b l eo rt h eo r i g i n a lj o b sa r e 丑) ( e do r d e ra r e s o l v a b l ei np o l y n o m i a lt i m eo rp s e u d o - p o l y n o m i a lt i m e ( 2 ) t h er e s c h e d u l i n gp r o b l e mt o m i n i m i z et h et o t a lt a r d i n e s su n d e ral i m i to nt h ed i s r u p t i o nc o n s t r a i n t sw h e np 3 = po r 而= d a r es o l v a b l ei np o l y n o m i a lt i m eo rp s e u d o - p o l y n o m i a lt i m e ( 3 ) t h er e s c h e d u l i n g p r o b l e mf o rj o b so nas i n g l em a c l f i n et om i n i m i z et o t a lw e i g h t e dc o m p l e t i o nt i m eu n d e r al i m i to nt h em a x i m u md i s r u p t i o nw h e n 功a n dt 如o ft h ej o b sa r ea n t i c o m p a t i b l ea r e s o l v a b l ei np o l y n o m i a lt i m eo rp s e u d o - p o l y n o m i a lt i m e ， i nc h a p t e r3 ，t h ef o l l o w i n gr e s u l t sa r ed e v e l o p e d ( 1 ) t h er e s c h e d u l i n gp r o b l e m f o rj o b so nas i n g l em a c h i n ew i t hr e l e a s ed a t e st om i n i m i z em a k e s p a nu n d e ral i m i to n t h em a x i m u ms e q u e n c ed i s r u p t i o ni ss o l v a b l ei np o l y n o m i a lt i m e ( 2 ) mr e s c h e d u l i n g p r o b l e m f o r j o b s o n a s i n g l e m a c h i n e w i t hr e l e a s e d a t e s t o m i n i m i z e m a k e s p a n u n d e r a l i m i t o nt h et o t a ls e q u e n c ed i s r u p t i o nc a nb es o l v e di np o l y n o m i a lt i m e ( 3 ) t h er e s c h e d u l i n g p r o b l e m sf o rj o b so nas i n g l em a c h i n ew i t hr e l e a s ed a t e st om i n i m i z em a k e s p a nu n d e ra l i m i to nt h em a x i m u mt i m ed i s r u p t i o no rt h et o t a lt i m ed i s r u p t i o na r es t r o n g l yn p - h a r d c h a p t e r48 t u d i e st h em u l t i c r i t e r i ar a s c h e d u l i n gp r o b l e m s i nt h i sp a r t s t h ed i s - r u p t i o n so ft h eo r i g i n a lj o b sa r er e g a r d e da sa no b j e c t i v ei nt h es a m ea sc l a s s i c a lo b - j e c t i v e s t h er e s e h e d u l i n gp r o b l e m so fh i e r a r c h i c a lo p t i m i z a t i o n ，p a r e t oo p t i m i z a t i o n a n dl i n e a rc o m p o s i t eo b j e c t i v ef u n c t i o no p t i m i z a t i o nb e t w e e nt h ec l a s s i c a ls c h e d u l i n g c o s t ( s u c ha sg m ，工m “，嘶q ) 0 fa l lt h ej o b sa n dt h ed e g r e eo ft h ed i s r u p t i o n s ( d m “( ，r + ) ，。h ( 矿) ，功( 丌) ，今( 矿) ) a r ec o n s i d e r e d f o rs o m ep r o b l e m s ，w e p r o v i d eap o l y n o m i a lo rp 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 c h a p t e r5d i s c n s s e st h eo n - l i n er e s c h e d u l i n gp r o b l e m s i nt h sp a r t s ，t h eo r i g i n a l j o b sh a v eb e e na r r i v e da n ds e q u e n c e db ys o m er u l e ，t h en e wj o b sa r r i v eo v e rt i m e f o r t h eo n l i n er e s c h e d u l i n gp r o b l e mt om i n i m i z et h en l a x i n m ml a t e n e s su n d e ral i m i to i l t h ed i s r u p t i o nc o n s t r a i n t s ，82 - c o m p e t i t i v er a t i oa l g o r i t h mi sp r e s e n t e d f o rt h eo n l i n e r e s c h e d u l i n gp r o b l e mt oi l l l i l i m l z em a k e s p a nu n d e ral i m i to nt h ed i s r u p t i o nc o n s t r a i n t s w i t hr e l e a s ed a t e ，s o m e2 - c o m p e t i t i v er a t i oa l g o r i t h m sa r ep r e s e n t e d k e yw o r d s ：s c h e d u l i n g ；r e s c h e d u l i n g ；m u l t i c r i t e r i as c h e d u l i n g ；o n - l i n e s c h e d u l i n g ；d i s r u p t i o n ；d y n a m i cp r o g r a m m i n g ；c o m p u t a t i o n a lc o m p l e x i t y v 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有 剽窃、抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承 担由此产生的切法律责任和法律后果，特此郑重声明。 学位论文作者( 签名) ：名扔秒 二零零七年三月 1 1 排序问题 第1 章绪论 排序( s c h e d u l i n g ) 论又称为时间表理论，在自动化学科中称为调度论。排序论作 为运筹学的一个分支，作为一门应用学科，有着深刻的实际背景和广阔的应用前景 排序问题是一类重要的组合最优化问题，是工业生产中一类带有普遍性的问题对它 的研究是从二十世纪五十年代初期开始的，它产生的背景主要是机器制造业，后来被 广泛应用于农业、制造业、运输业、管理科学、计算机科学等领域如将原材料通过 各种机器加工成某些所需的零件需要排序；将生产出来的许多零件组装成某些产品需 要排序；一个大型的工程在兴建中，必须要对各类人员进行安排，对各种物资的供应 进行调度；等等一份题为美国国防部与数学科学研究的报告认为1 0 4 ：2 0 世 纪9 0 年代到2 1 世纪数学的发展重点将从连续的对象转为离散的对象，并且组合最优 化将有很大的发展“因为在这个领域内存在着大量急需解决而又极端困难的问题，其 中包括如何对各个部件进行分隔、布线和布局的问题”特别地，排序问题的模型繁 多，经典的排序模式已被突破，新的模式层出不穷；研究排序问题的方法涉及组合最 优化理论的各个分支，如线性规划与整数规划、动态规划、最大流问题、匹配问题、 计算复杂性理论等因此，排序论已是国际上发展迅速、研究活跃、成果丰硕、前景 诱人的学科领域之一 1 1 1 排序问题的描述 排序问题是利用一些处理机、机器或资源，最优地完成一批给定的任务或作业 排序问题产生的主要背景是机器制造业，因此在排序论中把要完成的任务或被加工的 对象称作工件，把完成任务所需要的资源或提供加工的对象称作机器或处理机。排序 又称安排时间表，就是在一定的约束条件下对若干个要加工的工件或任务和加工工件 所需要的机器按时间进度最优分配，最优排序和最优调度，使某一个或某一些指标达 到最优具体地，我们用下述方式来描述排序问题： 】 1 1 排序问题 设有n 个工件或任务，= ，五，厶 ，其中乃表示第j 个工件，j = 1 ，2 ，n ；有m 台机器m = m ，m 2 ，) ，其中坛表示第i 台机器，i = 1 ，2 ，m 排序问题就是在一定的条件下，为了完成各项任务，把m 的机器或资源 分配给了中的任务，使目标函数达到最优我们常常用的基本参数如下： 黝( 或功) ( p r o c e s s i n gt i m e ) 表示工件乃在机器尬上的加工时间( 简称工 时) ，当黝= 研时，说明工件j j 的加工时间与选择的机器无关或所研究的问题是单机 排序问题 q ( r e l e a s ed a t e ) 表示工件乃的准备( 到达) 时间，也就是工件易可以进行加 工的最早时刻 出( d u ed a t e ) 表示工件j j 的交工期( 应交工时间) 如果一个工件在它的交工期 之前完成，我们称之为按期完工工件( o n - t i m ej o b ) 否则，我们称之为误工工件( t a r d y j o b ) 对误工工件有时需要付出一定的罚值 哟( w e i g h t ) 表示工件乃的权重体现工件乃在整个系统中相对其他因素的重 要性 q ( c o m p l e t i o nt i m e ) 表示工件乃的完工时间 岛= 0 一而( 1 a t e n e s s ) 表示工件j j 的延迟 t j = m a x o ，岛一吗) ( t a r d i n e s s ) 表示工件乃的误时 马= m a x o ，吗一q ( e a r l i n e s s ) 表示工件乃提前完工的时问 = ：鬈而p 嘶) 表示工件乃的靴误时惩罚q 做误 工计数 、 关于作业时间安排，有几点约定： ( 1 ) 一个工件一旦开始加工，则直加工到完毕( 除非有允许中断的声明) ： ( 2 ) 每个工件必须在它的到达( 准备) 时间之后才能加工 1 1 2排序问题的分类 排序问题基本上是由机器的数量、种类和环境，以及工件或任务的性质和目标函 2 郑州大学博士学位论文第1 章绪论 数所组成机器的数量、类型和环境有多种变化，任务或工件的约束条件更是错综复 杂，再加上度量不同指标的目标函数，形成了种类繁多的排序模型目前国际上普遍 采用g r a h a m ( 1 9 7 9 ) f 4 4 等人首先使用的三参数表示法，即( 口i 卢i ，y ) 一表示法， 这样能大大简化排序问题的表示它们具有下面的含义： ( i ) 口域表示机器的数量、类型和环境，它可以为： 口= 1 ( s i n g l em a c h i n e ) 表示一台机器，是各种机器状况中特殊的情形( 单机情 形) 口= b ，( i d e n t i c a lm a c h i n e si np a r a l l e l ) 表示m 台速度相同的平行机器( 简称恒 同机1 口= q 。( m a c h i n e si np a r a l l e lw i t hd i f f e r e n ts p e e d s ) 表示y f l , 台一致的平行机 器( 简称一致机) 若机器尬的速度为饥，工件以的加工时间为乃，则工件乃在机 器 磊上加工时的实际加工时间为砌= p d v , 如果所有机器的速度都相同，此时即 为j ，m 的情形 a = 冠n ( u n r e l a t e dm a c h i n e si np a r a l l e l ) 表示m 台无关的平行机器( 简称无关 机) 此类机器随加工工件的不同而加工速度也不同若机器尬的速度为，则工 件乃只在机器尬上加工时的实际加工时间为黝= p ，v , j 此情形是q k 的推广 口= f m ( f l o ws h o p ) 表示m 台机器的流水作业每个工件以特定的相同机器次 序在这些机器上加工 口= 0 ( o p e ns h o p ) 表示m 台机器的自由作业。每个工件在机器上加工的次序 不事先假定 口= 厶o o bs h o p ) 表示m 台机器的异序作业每个工件以各自特定的机器次序 进行加工 ( i i ) 卢域表示工件的性质、加工要求和限制，资源的种类、数量和对加工的影响等 约束条件，它同时可以包含多项，主要有： p = 巧表示工件乃的准备时间不相同工件乃的加工不能在r j 之前开始 p = 丐表示工件有截止期限 3 1 2 计算复杂性 口= d j 表示工件有交工期 p = 锄= 矿表示工件的加工时间相同 卢= p r e c 表示工件的加工过程有一个先后次序的要求，后面的工件必须在它前 面的工件全部加工完成后才能开始加工 口= p m t n 表示工件允许中断抢先 p = 朋j 表示工件乃在平行机加工中允许加工的机器集合朋j 是机器集的子 集 p = ( 乃，嘞) 表示工件的加工时间与工期是相容的( c o m p a t i b l e ) ，即如果a 珊，则也而；意思就是工件的加工时间越长，工件的交工时间就越长 p = a n t i 一幻，嘶) 表示工件的加工时间与权重是反相容的( a n t i c o m p a t i b l e ) ，即 如果p is 巧，则劬哟；意思就是工件的加工时间越长，工件的权重就越小 ( i i i ) 7 域表示要优化的目标函数，它们是： ，y = c 0 。( m a k e 印a n ) 表示各工件的最大完工时间 。7 = l 。( 脚耐m ml a t e n e s s ) 表示各工件的最大延迟 。，y = 嘶q ( t o t a lw e i g h t e dc o m p l e t i o nt i m e ) 表示各工件加权完工时间之和 ，y = 嘶乃( t o t a lw e i g h t e dt a r d n e s s ) 表示各工件加权误时之和 。，y = ( n u m b e ro fl a t ej o b s ) 表示误工工件数 7 = l e x m ，恤) 表示多重指标排序的字典序最优，即目标是在第一个指标1 1 为 最优的条件下，使第二个指标他为最优 7 = e h li 能) 表示多重指标排序的p a r c t o 最优解 ，y = f ( 7 1 ，能) 表示多重指标排序的组合目标函数最优解 1 2 计算复杂性 在为组合最优化问题提供计算方案时，同时要对此算法进行计算复杂性分析，以 说明算法的效率及所研究问题的难易程度计算复杂性理论中一个很重要的部分是区 4 郑州大学博士学位论文第1 章绪论 别出“容易”问题( 即存在多项式时间算法的问题) 与“困难”问题( 即所谓n p - h a r d 问题) 问题与实例 在计算复杂性理论中，主要研究判定问题( d e c i s i o np r o b l e m ) 所谓判定问题，是 指含一组参数的问句，要求回答“是”或“否”当问题中的参数给定时，便称为一个 实例( i n s t a n c e ) 一个实例的大小( 输入长度) 称为规模( s i z e ) 算法的时间界 一个算法的运算次数是指其中使用的基本算术运算( 加、减、乘、除、比较) 的 次数 定义1 2 1 一个算法的时间界是指对输入长度为闭的实例z 而言，在最坏情况 的运算次数的上界，( i 纠) 定义1 2 2 若一个算法屯的时间界为，) = d ( n ) ，其中n 为实例的规模，詹 为确定的正整数，则a 称为多项式时间算法( p o l y n o m i a l - t i m ea l g o r i t h m ) 多项式时间算法也称为好算法或有效算法，它是相对于二元代码而言的 定义1 2 3 一元代码下的多项式时间算法称为拟多项式时间算法( p u d 0 _ p o l y n o m i a l ) p 问题与n p 问题 定义1 2 4 着一个问题存在多项式时间算法，则称之为p 问题 定义1 2 5 一个判定问题a 称为n p 问题，是指对此问题的任一个y e s - 实例五 都存在一个判据c ( z ) 及一个验证算法，使得检验g ( 刁可在多项式时间内完成 命题1 2 1p 问题类n p 问题类 多项式时间变换 问题a 可在多项式时间内变换为问题，是指存在一个多项式p ，对任给问题a 的一个实例厶可以在p ( i i ) 的时间内构造出问题的实例p i ，使得z 是a 的y e s 5 1 2 计算复杂性 实例铸是的y e s 实例，简记为a n p 完全问题 定义1 2 6 若判定问题a 满足如下两个条件，则称为p 一完全问题：( i ) a 是 p 问题；( i i ) 所有p 问题均可多项式地变换为a 要证明一个问题a 是n p 完全的就只需要做这样两件事： ( i ) a 属于p 类； ( i i ) 找一个已知的p 一完全问题b ，证明b 可多项式地变换为a 定义1 2 7 如果一个最优化问题的判定形式是n p 一完全问题，则称该问题为 p 一困难( n p - h a r d ) 问题 对一个问题a 及一个多项式p ，它的限制问题如是由a 中这样的实例z 组成： z 中出现的最大整数n u m b e r ( x ) p ( 川) 定义1 2 8 对于一个p 一完全问题，若存在一个多项式p ，使得其限制问题如 也是n p 一完全的，则称为强p 一完全的( s t r o n g l yn p - c o m p l e t e ) 要证明某排序问题是p 困难的，只需证明它的判定形式是尸完全的常用 的已知n p 一完全的问题是2 划分问题和3 划分问题 2 划分问题 给定正整数a l ，a n ，是否存在子集s c n = 1 ，2 ，凡) ，使 0 4 = 啦? i s i 、s 命题1 2 2 【4 0 】2 一划分问题是p 一完全的 3 一划分问题 给定正整数0 1 ，口3 ，l ，b ，其中6 i ) 是在矿中排在五之前 1 5 2 1 相容工件系统和具有固定顺序的最小化最大延迟问题 的乃的最后一个工件因为矿是一个e d d ( s p t ) 序列，并且由，m 是相容的 即面s 吨，p i p i 考虑一个由矿通过交换工件五和易而得到的新的排序一则 有q ( 一) = q ( 矿) 一功+ p i c j ( 矿) ，0 ( a ) = a ( 矿) ，并且工件以和五之间的所有 工件的完工时间在盯中比在矿中提前胁一p i 0 个单位因为工件以在一中的延 迟不比工件五在矿中的延迟大，因此最大延迟没有增加如果工件 在一中的位置 大于等于它在丌中的位置( 对工件五也一样) ，则有功( 丌，一) 功( 矿，矿) ； 否则马( 矿，口) 易( 矿，矿) 无论哪种情形，因为玩( 矿，一) = 现( 矿，矿) 一h 和岛( 矿，0 ) 功( 丌，矿) + h ，其中h 是工件五和如在矿中位置的差，我 们可以推出d 。何+ ，0 i ) d m 。( 矿，矿) 和功( 丌+ ，仃) s m j ( 矿，矿) 进而，如 果g ) 2q ( 矿) ，则有今印，一) a i ( t r ，矿) ；否则恕( 矿，o - i ) 今( 矿，一。) 无 论哪种情形，因为a i ( ，r ，盯) = a i ( 7 1 * ，矿) 一和气( 仃，一) ，( 丌，矿) + ，其 中h = a ( 矿) 一c ! f ( 一) ，我们可以推出。( 丌，一) 。( 矿，矿) 和，( 丌，一) ，( 矿，矿) 于是，盯是可行的和最优的这样有限次的交换可以证明，存在这 样一个最优排序，, 7 0 中的工件和矿中的一样按e d d ( s p t ) 序排列类似地可以 证明历v 中的工件也是按e d d ( s p t ) 序排列正是乃中工件与在丌中具有相同 的e d d ( b p t ) 序和排序的最优性，可以证明这样的最优排序中不存在空闲时间，否 则去掉这些空闲时间，排序仍然是可行的并且排序的最大延迟不会增加 口 这种原始工件集合乃和新工件集合另r 中工件都按e d d 序排列的性质，称 为( e d d ，e d d ) 性质由引理2 1 1 ，我们可以找到具有这种性质的最优排序 我们首先考虑问题1i 渤，d j ) ，b ( 丌+ ) kil 。由引理2 1 1 ，岛和西 中工件的( e d d ，e d d ) 性质表明，可以通过将, 7 0 和巩中工件的两个e d d ( s p t ) 序排列融合，用动态规划方法得到在总的序列错位约束下的最优排序 算法2 1 1 输入：输入p j ，d j ，j = l ，n ；k 和矿，其中k n o n n 标号：将知中的工件按e d d 序排列 预处理：计算：l p h ，i = 1 ，n o 和n ；o 。+ o j + l p h ，j = 1 ，n n 递归函数：f ( i ，五6 ) 表示工件 ，五，五和+ l ，矗o 的部分排序在总序列 错位为艿时最大延迟的最小值 1 b 郑州大学博士学位论文第2 章几种特殊情形的重新捧序问题 边界条件：( o ，o ，0 ) = 0 最优值：m i n o _ 5 j f ( n o ，n ，6 ) ) 递归关系：f ( i ，j ，6 ) = m i n m a x f ( i - - 1 ，五6 - j ) ，：1 鲰+ n h 。o + 。j + l 肌一d i ) ，m a x f ( i ，一 1 ，6 ) ，：；1 p h + 翟嚣+ 1 p h 一奶 在这个递归关系中，第一项对应部分排序以7 0 中工件五结束的情况，此时知 中的个工件在工件也之前已经排好，此时总的时间错位增加量为j ；第二项对应部 分排序以霸中工件厶。卅结尾的情况 定理2 1 1 算法2 1 1 在o ( 碣碍) 时间给出问题1i ( 巧，西) ，功( 7 r + ) 七l 工。 的最优排序 证明：由引理2 1 1 ，只要将丌中的工件序列和氖中工件的e d d 序列进行所 有可能的排列融合算法2 1 1 就是通过所有状态的费用函数的比较，从而找到最优排 序 因为i n o ，j 且6 k n o n n ，因此有d ( 砀碡) 个状态变量的值在标 号和预处理阶段，分别用0 ( n n l o g n n ) 和0 ( 礼