（基础数学专业论文）多目标分批排序及其相关课题.pdf

摘要 在过去的5 0 年中，机器排序问题已成为组合最优化中最活跃的研究课题之一然 而，在大多数经典的排序文献中，只考虑机器一次至多加工一个工件，且目标函数只有一 个随着时间的推移，分批排序和多目标排序已蓬勃发展起来可是将两者( 分批排序和 多目标排序) 结合起来的研究尚不多见由于电子加工业及其它产业的高速发展，以及决 策者的不同利益需求，将分批排序与多目标排序结合起来考虑，应该提到议事日程上 设他个无关的工件以，如， ，它们将在一台分批处理机上加工工件以 的加工时间、工期、期限和权分别为纺、略、心和哟u = 1 ，钆) 以岛和g 分别表示工件五的开始加工时间和完工时间给定一个序口，l io ) = c ，o ) 一d ， 与三m 舣o ) = m a x , = 1 岛( 盯) 分别表示工件易的延迟与序盯的最大延迟t j = m a x 0 ，l j ) 为工件以的延误，以为它的单位惩罚因子本论文主要考虑分批处理机上同时最小化 双目标排序问题所谓的分批处理机是指机器可同时加工多个工件，放在一起加工的工 件集称为一批，同一批中的工件具有相同的开工时间和完工时间根据批的加工时间的 不同定义，分批处理机又分为平行分批处理机和序列分批处理机对前者，一批的加工 时间等于这一批中最长工件的加工时间这一模型是由半导体加工的烘烤、计算机系 统及其它领域的操作抽象而来的对后者，一批的加工时间等于这一批中所有工件的加 工时间之和，且在每一批加工开始前，都有一个常数8 的安装时间这一模型起源于现 实生活中这样的要求：当一批工件加工完成后，需要一段时间来调换工具、维修机器等 另一方面，两个目标函数可以代表两个决策者的不同利益这一方向发展的基本动机源 于这样的事实：质量评估通常是一个多维概念并且决策者常常追求多个目标同时最优 化一对所有目标函数找出全部的p a r e t o 最优序称一个可行序仃是关于目标函数， 和9 的p a r e t o 最优序，是指不存在可行序7 r ，使得，( 7 r ) ，( 盯) ，9 ( 7 r ) 夕( 盯) ，且其中这 两个不等式至少有一个严格成立 本学位论文的主要研究成果如下： 1 单机平行分批的双目标排序 前人分别对双目标及平行分批两方面已得到一些结果例如，证明了同时最小化最 大延迟和最大费用函数的单机排序问题可在o ( 佗3l o g n ) 时间内解决在平行分批处理 机上，当机器容量无界时，最小化最大延迟问题已有o ( n 2 ) 时间的动态规划算法而我 i 们考虑两方面的结合，即同时最小化最大延迟和最大完工时间的平行分批排序问题，并 给出一个o ( n a ) 时间的多项式时间算法，可以求出全部p a r e t o 最优解对多目标优化问 题而言，求出全部p a r e t o 最优解是最完整的解答另外，当机器容量有界，且工件的加工 时间为常数时，以总延误为主指标，次指标分别是误工工件数、加权误工工件数和加权 总完工时间的分层最小化问题已有d ( n 3 ) 时间算法我们统一地给出o ( n l o g 他) 时间算 法，改进了上述时间界 2 单机序列分批的双目标捧序 对于序列分批的单目标排序问题，当机器容量无界时，最小化最大延迟问题已 有o ( n 2 ) 时间的算法；最小化加权总完工时间也已有了d m ) 时间的算法对于双目标 问题，没有已知结果我们在o ( n 2 ) 时间内解决了同时最小化最大延迟和最大完工时间 问题此外，对同时最小化最大完工时间和总完工时间问题，在机器容量无界或有界的情 形下，我们分别给出o ( n 2 ) 时间算法以上算法均可求出全部p a r e t o 最优解，获得完全 的解答 3 单机双目标排序 己知最小化具有截止时间的误工工件数问题是p 一困难的对如下特殊情形的 误工工件数问题，文献中已有d ( n 2 ) 时间的后向算法( i ) 如果d d j ，那么玉西 与p i 彩；( i i ) 如果鼽岛，那么d 一d j p i 一乃为建立统一的理论，我们提出了一种 对偶算法一前向的贪婪算法，对情形( i ) ，它有更好的时间界0 ( n l o g n ) 对情形( i i ) ，得 到相同的时间界，但方法有不同特点并且我们还研究了工件) j l i 时间相等的情形，也找 到了0 ( n l o g n ) 时间算法 因为不同的决策者对同一个工件的工期要求可能不同( 它们分别代表各自的期望利 益) ，所以可设每一个工件j j 具有两个工期d ；1 和d ：2 ( 1 歹n ) 这样，对一个给定 的序盯，就诱导了两个目标函数最大延迟。l m o 缸) 与l 然我们证明同时最小化关于两个 工期集合的最大延迟问题可在o ( n 3l o g n ) 时间内解决，求出全部p a r e t o 最优解，且时间 界是紧的 关键词：排序；平行分批处理机；序列分批处理机；多目标；p a r e t o 最优序 a b s t r a c t m a c h i n es c h e d u l i n gh a sb e e no n eo ft h em o s ta c t i v er e s e a r c ht o p i c si nc o m b i n a t o r i a l o p t i m i z a t i o no v e rt h el a s th a l fc e n t u r y h o w e v e r ，m o s to ft h ec l a s s i c a ls c h e d u l i n gl i t e r - a t u r e sc o n s i d e rt h a tt h em a c h i n ec a np r o c e s sa tm o s to n ej o ba tat i m e ，a n dc o n s i d e r o n l yo n eo b j e c t i v e s c h e d u l i n go nb a t c h i n gm a c h i n e sa n dm u l t i c r i t e r i as c h e d u l i n gp r o b - l e m sh a v eb e e ns t u d i e de x t e n s i v e l yi nr e c e n ty e a r s y e ti ts e e m st h a to n l yl i t t l ew o r k h a v eb e e nd o n ei nt h e i ri n t e r s e c t i o np a r t ，t h a ti s ，m u l t i c r i t e r i as c h e d u l i n go nb a t c h i n g m a c h i n e s t h i ss i t u a t i o nc a n n o ts a t i s f yt h er e a l - l i f en e e dd u et ot h er a p i dd e v e l o p m e n t o fs e m i c o n d u c t o rm a n u f a c t u r i n ga n do t h e ra r e a s i ti sn e c e s s a r yt oc o n s i d e rm u l t i c r i t e r i a s c h e d u l i n go nb a t c h i n gm a c h i n e si no r d e r t og i v eb e t t e rs e r v i c et or e a l i t y s u p p o s et h a tw ea r eg i v e n 礼i n d e p e n d e n tj o b s 以，j 2 ，厶t h e ya r et ob es c h e d u l e d o na s i n g l eb a t c h i n gm a c h i n e t h ep r o c e s s i n gt i m e ，d u ed a t e ，d e a d l i n ea n dw e i g h to f j o b 乃a r ep 3 ，d j ，d ja n d ( j = 1 ，他) ，r e s p e c t i v e l y a n dw eu s e 岛a n dc jt o d e n o t et h es t a r t i n gt i m ea n dt h ec o m p l e t i o nt i m eo fj o b 乃f o rag i v e ns c h e d u l e 盯， 岛o ) = c o ) 一d ja n dl m 蹦o ) = m ( 备l 岛( 盯) a r ed e f i n e da st h el a t e n e s so f j o bj ja n d t h em a x i m u ml a t e n e s so f 口，r e s p e c t i v e l y 乃= m a x 0 ，l j ) i st h et a r d i n e s so fj o bj j ，a n d u ji si t su n i tp e n a l t y i nt h i st h e s i s ，w ef o c u so nm i n i m i z i n gb i c r i t e r i as c h e d u l i n gp r o b l e m o na b a t c h i n gm a c h i n e ab a t c h i n gm a c h i n ei sa m a c h i n et h a tc a nh a n d l eu pt obj o b si n ab a t c h t h ej o b si nab a t c hs t a r ta n dc o m p l e t er e s p e c t i v e l ya tt h es a m et i m e a c c o r d i n g t ot h ed i f f e r e n c eo ft h ep r o c e s s i n gt i m eo fab a t c h ，b a t c h i n gm a c h i n ei sd i v i d e di n t o p a r a l l e l - b a t c h i n gm a c h i n ea n ds e r i e s - b a t c h i n gm a c h i n e i np a r a l l e l b a t c h i n gm a c h i n e ， t h ep r o c e s s i n gt i m eo fab a t c hi se q u a lt ot h el a r g e s tp r o c e s s i n gt i m eo fj o b si nt h eb a t c h t h i sm o d e li sm o t i v a t e db yt h eb u r n - i no p e r a t i o n sf o rs e m i c o n d u c t o rm a n u f a c t u r i n g ， c o m p u t e rs y s t e ma n do t h e ra r e a s i ns e r i e s - b a t c h i n gm a c h i n e ，t h ep r o c e s s i n gt i m eo fa b a t c hi se q u a lt ot h es u mo ft h ep r o c e s s i n gt i m e so fj o b si nt h eb a t c h i na d d i t i o n ，t h e r ei s ac o n s t a n ts e t u pt i m e8f o re a c hb a t c h t h i sm o d e l 印p l i e st oal o to ff i e l d s f o re x a m p l e ， a f t e rab a t c hi sp r o c e s s e d ，p e o p l eo f t e nt a k eas p a nt oc h a n g et o o l s ，r e p a i rm a c h i n ea n d s oo n o nt h eo t h e rh a n d ，t w oo b j e c t i v ef u n c t i o n sm a yr e p r e s e n td i f f e r e n ti n t e r e s t so f t w od e c i s i o n m a k e r s t h eb a s i cm o t i v a t i o no ft h i sd i r e c t i o ni st h a tq u a l i t ye v a l u a t i o ni sa m u l t i d i m e n s i o n a ln o t i o na n dd e c i s i o n - m a k e r su s u a l l yp u r s u es e v e r a lp e r f o r m a n c ec r i t e r i a s i m u l t a n e o u s l y - - t of i n da l lp a r e t oo p t i m a ls c h e d u l e s af e a s i b l es c h e d u l e 盯i sp a r e t o i i i o p t i m a l ，w i t hr e s p e c tt ot h ep e r f o r m a n c ec r i t e r i afa n dgi ft h e r ei sn of e a s i b l es c h e d u l e 7 rs u c h t h a tb o t h ，( 7 r ) ( o ) a n d 夕( 7 r ) 9 ( 盯) ，w h e r ea tl e a s to n eo ft h ei n e q u a l i t i e si s s t r i c t i h em a u lr e s u l t so ft h i st h e s i sa r ea sf d l o w s ： 1 b i c r i t e r i as c h e d u l i n go nap a r a l l e l - b a t c h i n gm a c h i n e p r e v i o u sr e s e a r c h e r sh a v es h o w e dt h a tt h ep r o b l e mo fm i n i m i z i n gm a x i m u ml a t e n e s s a n dm a x i m u mc o s tc r i t e r i o no nam a c h i n ei ss o l v a b l ei no ( n 3l o gn ) t i m e f o rt h ep a r a l l e l - b a t c hs c h e d u l i n gp r o b l e m ，w h e nt h eb a t c hc a p a c i t yo ft h em a c h i n ei su n b o u n d e d ，w eh a v e k n o w nad y n a m i cp r o g r a m m i n ga l g o r i t h mt h a tr e q u i r e so ( n 2 ) t i m ef o rm i n i m i z i n gt h e m a x i m u ml a t e n e s s w es t u d yt h eb i c r i t e r i ap r o b l e mo fs c h e d u l i n go nab a t c h i n gm a c h i n e t om i n i m i z em a x i m u ml a t e n e s sa n dm a k e s p a ns i m u l t a n e o u s l y , a n dp r e s e n t e da l lo ( n 3 ) a l g o r i t h m ，a n di ti sac o m p l e t es o l u t i o n i na d d i t i o n ，w h e nt h eb a t c hc a p a c i t yo ft h e m a c h i n ei s b o u n d e d ，a n dt h ep r o c e s s i n gt i m e so fa l lj o b sa r ee q u a l ，s o m eh i e r a r c h i c a l m i n i m i z a t i o np r o b l e m sw i t ht o t a lt a r d i n e s sa st h ep r i m a r yc r i t e r i o n ，t h en u m b e ro ft a r d y j o b so rt h ew e i g h t e dn u m b e ro ft a r d yj o b so rt h et o t a lw e i g h t e dc o m p l e t i o nt i m ea st h e s e c o n d a r yc r i t e r i a ，h a v eo ( n 3 ) a l g o r i t h m s w ep r e s e n to ( nl o gn ) a l g o r i t h m ss o 嬲t o i m p r o v et h et i m eb o u n d s 2 b i c r i t e r i as c h e d u l i n go nas e r i e s - b a t c h i n gm a c h i n e f o rt h es e r i e s b a t c hs c h e d u l i n gp r o b l e m ，w h e nt h eb a t c hc a p a c i t yo ft h em a c h i n ei s u n b o u n d e d ，t h ep r o b l e mo fm m i m i z i n gt h em a x i m u ml a t e n e s sh a sa l lo ( n 2 ) a l g o r i t h m ； t h ep r o b l e mo fm i n i m i z i n gt h et o t a lw e i g h t e dc o m p l e t i o nt i m eh a sa no ( n ) a l g o r i t h m w ep r e s e n ta no ( n 2 ) a l g o r i t h mf o rt h ep r o b l e mo fm i n i m i z i n gm a x i m u ml a t e n e s sa n d m a k e s p a ns i m u l t a n e o u s l y m o r e o v e r ，f o rt h ep r o b l e mo fm i n i m i z i n gm a k e s p a na n dt h e t o t a lc o m p l e t i o nt i m e ，w ef i n da l lp a r e t oo p t i m a ls c h e d u l e si no ( n 2 ) t i m ef o ru n b o u n d e d a n db o u n d e dm o d e l s ，r e s p e c t i v e l y 3 b i c r i t e r i as c h e d u l i n go nam a c h i n e w eh a v ek n o w nt h a tt h e s i n g l em a c h i n es c h e d u h n gp r o b l e mo fm i n i m i z i n gt h en u m b e r o ft a r d yj o b s ，w i t hd e a d h n ec o n s t r a i n t ，i sn p h a r d s o m eo ( n 2 ) b a c k w a r d ss c h e d u l e a l g o r i t h m sh a v eb e e np r e s e n t e df o rt h ef o l l o w i n gs p e c i a le a s e s ： ( i ) 也呜i m p l i e s 五弓a n dp i 乃； i v ( i i ) p i 胁i m p l i e sd 一d j p 一殇 t oe s t a b l i s hau n i f o r mt h e o r y , w ep r o p o s ead u a la p p r o a c h - - t h ef o r w a r d sg r e e d ya l g o - r i t h m s f o rc a s e ( i ) ，i th a sab e t t e rt i m eb o u n do ( n l o gn ) f o rc a s e ( i i ) ，i th a st h e s a l l l et i m eb o u n d ，b u th a sd i f f e r e n tf e a t u r e s m o r e o v e r ，a n dw es t u d yt h ec a s ew i t ht h e i d e n t i c a lp r o c e s s i n gt i m e ，a n dp r e s e n ta na l g o r i t h mw i t ht i m eb o u n do ( n l o gn ) a sw e l l s i n c ed i f f e r e n td e c i s i o n - m a k e r sm a yh a v ed i f f e r e n td u ed a t e sf o ra j o b ( t h e yr e p r e s e n t t h e i ri n d i v i d u a le x p e c t e di n t e r e s t s ) ，w em a y s u p p o s et h a te a c hl o bj ih a st w od u ed a t e s 砖1 a n d 孝( 1 j 佗) t h u sf o rag i v e ns c h e d u l e 矿，t r oo b j e c t i v ef u n c t i o n so fm 戚m 眦 l a t e n e s s 。l m ( o 娃a n dl g 基a r ei n d u c e d w ep r 删t h a tm i n i m i z i n gt w om 越m 啪l a t e m 潞 s i m u l t a n e o u s l y , w i t hr e s p e c tt ot w os e t so fd u ed a t e s ，i ss o l v a b l ei no ( n 3l o gn ) t i m e ，a n d t h et i m eb o u n di st i g h t k e yw o r d s ：s c h e d u l i n g ；p a r a l l e l - b a t c h i n gm a c h i n e ；s e r i e s - b a t c h i n gm a c h i n e ；m u l - t i c r i t e r i a ；p a r e t o - o p t i m a ls c h e d u l e v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明 确方式标明。本声明的法律责任由本人承担。 学位论文作者：i 可代 日期：加。7 年；月3 i 曰 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。根据 郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送 交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学可以将本学位 论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印或者其他复制手段 保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相 关的学术论文或成果时，第一署名单位仍然为郑州大学。保密论文在解密后应遵守此 规定。 学位论文作者：听可扯 日期：知。弘- m t e t 第1 章绪论 1 1排序论的学科特点 1 1 1 发展概貌 排序论是组合最优化的一个重要分支组合学是关于安排配置的数学学科排序论 是时间进程中的组合学由于其中种类繁多而富有特色的组合结构和广阔的应用前景， 学科的发展动力经久不衰具体地说，它起源于制造业中对机器资源和加工任务的合理 利用和安排的优化问题假设有n 个工件五，以，厶要在m 台机器上加工生产者需 要将工件按照时间资源的消耗需求安排在机器上，使得某个预定指标达到最优这就是 所谓的排序问题排序的英文为“s c h e d u l i n g ，它既有安排次序的意思，又有安排时间表 的含义也就是说，我们不仅要安排工件加工的次序，还要安排工件加工的时问 时至今日排序论已从组合最优化理论中逐步发展成为- - f 相对独立的学科在2 0 世纪初期，h e n r yg a n t t 引入了所谓的g a n t t 图表，开始关注和研究产品制造中出现的 排序问题然而，排序理论的深入研究兴起于2 0 世纪5 0 年代，从此确定它作为运筹学 的一个部分1 9 5 4 年，j o h n s o n 【6 3 1 在他的论文“o p t i m a lt w o - a n d - t h r e e - s t a g ep r o d u c t i o n s c h e d u l e sw i t hs e t u pt i m e si n c l u d e d ”中，考虑了最小化最大完工时间的两台机器的流水 作业排序问题，并给出了一个简单而又巧妙的多项式时间最优算法，即著名的j o h n s o n 规则1 9 5 5 年，s m i t hf 9 2 1 考虑了最小化加权完工时间和的单机排序问题他证明了在一 个最优排序中，工件是按照工件的权重与加工时间的比值的非增顺序安排加工的( 也称 作s m i t h 规则) 在6 0 年代，动态规划、整数规划和分枝定界算法被用来解决大量的排 序问题1 9 7 2 年，k a r p 6 5 1 发表了有关复杂性理论的重大结果这引起了人们对排序问 题复杂性理论的研究进一步，为解决p - 困难的排序问题，拟多项式时间算法和近似 算法被广泛研究 在经典的排序问题中，人们一般地假设：( 1 ) 所有的工件都必须在机器上加工，并且 机器一次只能加工一个工件；( 2 ) 所有工件的信息，包括它的到达时间、加工时间等等都 1 第1 章绪论 是事先已知的，确定不变的；( 3 ) 目标函数只有一个，且是正则的这里正则是指目标函 数关于工件完工时间是非减的近年来，排序所研究的范围变得越来越广泛，而且越来越 多的问题源于实际生产而成为排序的新模型新的排序模型打破了经典排序中对机器类 型、工件性质和目标函数等的限制，开拓了排序的适用范围相对于经典的排序模型，人 们将这些新的排序问题称为现代排序问题它们对上述基本假设的突破如下： 作为基本假设( 1 ) 的突破，有分批排序和允许拒绝工件的排序等分批排序可 以分为序列分批排序和平行分批排序对于序列分批排序问题的部分结果见参考文 献1 1 6 ，8 8 ，2 6 ，8 1 ，8 6 ，1 0 7 1 9 9 2 年，l e e 等人1 7 3 1 提出了平行分批排序问题根据批容量 的不同，平行分批排序又可以分为有界的情形和无界的情形有关平行分批排序的结果 见参考文献f 1 5 ，7 2 ，8 8 ，9 5 】2 0 0 0 年，b a x t a l 等人1 1 2 1 首先考虑了允许拒绝工件的平行机 排序问题 作为基本假设( 2 ) 的突破，有在线排序、随机排序和加工时间可控排序等在在线 排序中，工件的信息事先不被知道，而是随着工件的加工逐步释放的特别地，如果当一 个工件被安排加工后，下一个工件的信息才被告知，我们称这种排序问题为按序在线的 如果当工件的信息只有在它到达时间之后才能知道，我们称这种排序问题为按时在线 的进一步，如果一部分信息是事先知道而另一部分信息是逐步释放的，则我们称这种排 序问题是半在线的有关在线排序的结果参见【5 9 ，1 1 0 1 9 8 0 年，v i c k s o n 【1 0 2 】首先提 出加工时间可控的概念关于加工时间可控排序的更多结果参见文献f 3 0 1 作为基本假设( 3 ) 的突破，有多目标排序和多代理排序等1 9 5 6 年，第一篇有 关p a r e t o 最优解计算的文章出自s m i t h 9 2 尽管他没有明确地阐述双目标问题，他提 出的算法事实上解决了在单机上同时最小化完工时间和与最大延迟问题详细介绍参见 文献【l ，5 0 】 除了上述介绍的一些新型排序之外，近年来研究较多的新型排序还有准时排序、窗 时排序、资源受限排序、限选机器排序和平行工件多台机器排序等 1 1 2 模型分类 由于早期的排序问题是作为组合优化问题提出并进行研究的，通常描述一个简单的 问题需要很多的文字加以说明这种状况对排序这门学科的长远发展很不利直到1 9 7 9 年，g r a h a m 等人【4 2 】提出用三参数法( q 例7 ) 来表述排序问题由于这种表述方式简 单明了，本论文也采用这种方式下面，我们介绍排序中的一些常用记号，详细内容参 2 1 1 排序论的学科特点 看【1 4 】，1 4 2 】，f 8 7 】，【9 6 】本学位论文用到的其它术语将在后面陆续列出 在三参数表示法口例7 中， ( 1 ) 参数q 表示排序问题的机器环境，即可供使用的机器的数量、类型和性能如： q = 1 ：单机，表示只有一台机器可用 q = p m ：m 台同速机，表示有m 台机器可用它们具有相同的功能，且具有相同的 速度 q = q m ：m 台恒速机，表示有m 台机器可用 的速度，但每台机器的速度都是常数 o r = r m ：m 台变速机，表示有m 台机器可用 依赖于被加工的任务 它们具有相同的功能，且具有不相同 它们具有相同的功能，且机器的速度 o t = f r o ：m 台机器的流水作业，表示每个工件都要在m 台机器上加工，且在机器 上的加工顺序也相同 ( 2 ) 参数p 表示工件特征，即工件的信息以及安排加工时所受的限制如： 五，如，厶：n 个待加工的工件 功：工件以的加工时间 ：工件以的到达时间 ：工件以的权重，它表示工件的重要程度 d j ：工件五的工期，它是工件的计划完工时间 画：工件五的期限，它是工件的最后截止时间 s - b a t c h ：序列分批也就是说工件被分批2 nt ，每批的加工时间等于该批中工件的 加工时间之和，且处在同一批中的工件有相同的开始加工时间和相同的完工时间另外， 开始加工每批前有一个常数的安装时间 p - b a t c h ：平行分批也就是说工件被分批加工，每批的加工时间等于该批中最长工 件的加工时间，并且处在同一批中的工件有相同的开始加工时间和相同的完工时间 6 ：机器的容量为b 它指至多b 个工件可以作为一批同时在机器上加工；如果容量 无界，则表示为b 礼 ( 3 ) 参数，y 表示目标函数，即优化的指标如： g ：工件以的完工时间， 3 第1 章绪论 c m 麟：工件的最大完工时间或全程( m a k e s p a n ) ，即瓯蜮= m a x 0 ：1 j n ) c j ：工件的总完工时间 嘶q ：工件的加权总完工时间 岛：工件如的延迟，即易= 伤一也 l m 麟：工件的最大延迟，即l 。a x = m a x 岛：1 j n ) t j ：工件乃的延误，即乃= m a x 易，o ) 缸：工件的最大延误，即t m 馘= m a x ( t j ：1 j 咒) t j ：工件的总延误 q t j ：工件的加权总延误 ：工件乃的惩罚因子定义为：如果0 呜，即工件如按时完工，那么= 0 如果0 嘞，即工件易误工，那么= 1 u j ：误工工件数 屿u j ：加权误工工件数 1 1 3 基本概念与术语 可行序：如果一个序满足问题所指定的工件特征及约束条件，那么这个序被称为 个可行序 最优序：最小化一个给定目标函数的可行序称之为最优序 e d d ( e a r l i e s td u ed a t ef i r s t ) 规则：按照这一规则，工件按工期略不减的顺序进行 加工 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 ) 规则：按照这一规则，工件按加工时间p j 不减 的顺序进行加工 下面，我们介绍一些有关算法复杂性的概念 判定问题：回答是“是”或“否”的问题 通过对相应的目标函数，定义一个门槛值k ，每一个排序问题都对应于一个判定 问题：是否存在一个可行序仃使得，( 盯) 后? 对一个离线的排序问题来说，如果能找到一个有效的算法，得到一个最优解是最为 4 1 1 排序论的学科特点 理想的尽管当工件的个数几比较小的时候，我们可以枚举所有礼! 种可能的排序方式 但是，当n 比较大时，枚举几乎是不可能的甚至对一个最简单的最小化总完工时间的 单机排序问题，当n = 2 0 时，就是2 0 1 竺2 4 1 0 1 8 种排序方式即使使用目前最快的计 算机，也需要几年的时间才能枚举完因此，枚举不是一个好的算法 什么是一个好的算法呢? c o b h a m 【2 8 】和e d m o n d s 【3 4 】建议，一个好的、有效的算 法应该是一个多项式时间算法也就是说，存在一个整数k ，使得算法能够在o ( n 七) 时 间内完成例如，对上述的最小化总完工时间的单机排序问题，s m i t h 算法( 见f 9 2 】) 可 在o ( n l o g n ) 时间内得到该问题的一个最优排序，计算机只需要几秒钟就能完成 多项式时问算法：在t u r n i n g 机模型下，该算法在多项式时间( 在二元输入的意义 下，经过多项式次数的运算) 给出“是”或“否”的回答 p 类：具有多项式时间算法的判定问题构成的类 p 类：判定问题a n p 类当且仅当对a 的一个“是”一实例3 2 ，存在个关于 它是“是”一实例的“判据”( 证明文件) c ( 3 2 ) ，其长度是z 的多项式，且c ( 3 2 ) 可在多项式 时问内验证其有效性 尽管大多数人都猜测p p ，但长期以来一直没有得到解决，这已经成为目前组 合最优化理论中最为重要的未解问题之一 给定一个判定问题p p 类如果所有其它的在n p 类中的问题都可以在多 项式时间内转化为p ，我们就称p 是n p - 完全的如果一个问题p 尸类在二元 输入时是p l 完全的，则我们称p 是一般意义下n p - 完全的；相应地，如果一个问 题p p 类在一元输入时是n p - 完全的，则我们称p 是强p - 完全的 对一个最优化问题p ( 包括排序问题) 来说，如果它的判定问题是p l 完全的， 那么我们称p 是p _ 困难的类似地，我们也有一般意义下n p - 困难的与强p 一 困难的定义如果b 可在多项式时间内转化为尼，且已知b 是( 强) n p - 困难的，那 么b 也一定是( 强) p 困难的 对任何一个p 困难的问题，除非p = p ，否则不存在多项式时间的最优算 法也就是说，对这类问题，找到一个多项式时间的最优算法几乎是不可能的 拟多项式时问算法：在一元输入的意义下，该算法在多项式时问给出“是”或“否” 的回答 对任何一个强p _ 困难的问题，除非p = p ，否则不存在拟多项式时间的最优 算法 5 第1 章绪论 自从j o h n s o n 【6 3 1 对两台机器流水作业排序问题给出了一个简单而巧妙的算法之 后，很多人试图将他的结果推广到三台或者更多的机器上，然而皆未成功直到1 9 7 6 年， g a r e y 等人f 3 9 1 才证明三台机器流水作业问题是n p - 困难的因此，给定一个排序问 题，我们首先要弄清楚该问题是否为尸一困难的从2 0 世纪7 0 年代以来，已经有大 量的排序问题被证明是p 一困难的 因为绝大多数的排序问题都是p 一困难的，所以对这类问题我们找不到( 至少到 目前为止找不到) 一个多项式时间的最优算法因此，人们提出了近似算法的概念在 多项式时间内找到一个满足要求、接近最优解的近似解当前，对p 一困难问题，设计 有效的近似算法已成为排序问题研究的一个很有前景的方向 设p 是一个最小化单一目标函数的离线排序问题，且a 是p 的一个多项式时间 算法如果对p 的每一个实例，都有a ( ，) ko p t ( i ) ，这里k l ，a ( i ) 及o p t ( i ) 分别表示由算法a 作用于实例j 所得到的目标函数值与实例i 的最优值，那么称算法a 是排序问题p 的一个肛近似算法，也说算法a 有性能比k 使得a ( j ) ko p t ( i ) 成 立的最小的k 称为a 的最差情形性能比( 或者近似比) 设p 是一个最小化单一目标函数的在线排序问题，且a 是尸的一个多项式 时间在线算法如果对p 的每一个实例j ，都有a ( i ) ko p t ( i ) ，这里k 1 ，a ( i ) 及o p t u ) 的定义同上，那么称在线算法a 是排序问题p 的一个肛竞争在线算法，也 说算法a 有竞争比k 使得a ( i ) ko p t ( i ) 成立的最小的k 称为在线算法a 的竞争 比 1 2排序论的两个发展方向：分批排序与多目标排序 1 2 1 应用动机 排序论的内容丰富多彩、变化多端其中分批排序和多目标排序是它的两个具有生 机和活力的研究领域这主要是由于以下原因：首先，它们所研究的问题都源于生活，具 有很强的应用背景和实用价值；其次，它们包含一系列内容丰富而深刻的理论问题；再 者，从技术角度看，分批排序和多目标排序都处于一个难度适中的水平一它们中的一些 问题是可解的，但是解决它们又需要非平凡的技术方法 一般而言，一个排序问题就是在一定的约束条件下，如何对工件和机器按时间资源 的限制进行分配和安排加工，使得一个或多个指标达到最优正如前面所述，经典的排序 6 1 2 排序论的两个发展方向：分批排序与多日标捧序 问题只涉及一般的排序问题：机器一次至多加工一个工件，且目标函数只有一个随着科 学技术的进步和生产力的不断发展，排序理论现在已经广泛应用到许多其他领域，且所 研究问题也更加复杂比如，分批排序与多目标排序等很多实际问题通过构造合适的 模型可直接归结为分批排序问题或多目标排序问题下面我们举几个分批排序与多目标 排序问题的例子 例1 ：某服装厂有礼个订单，这些订单和季节有很大关系因此，每个单子都有一个 工期如果延期交工，则服装厂就要承担客户的损失，且损失与延期的时问成正比另外， 所有单子的总延误越小，服装厂的信誉就越高，下一次得到单子的几率就越大决策者希 望在保证服装厂利益最大化的情况下，信誉度最高这是一个字典序最优或分层最优排 序问题 例2 ：某公司和客户要就一批货物签定交货日期，如果延期交工，公司要负违约金， 且延期越长，违约金越多如果公司提前完成货物生产，那么它就要花钱储存货物，储存 时间越长，储存费用越高那么如何选定交货日期才能使公司的利益最大化呢? 如果将 公司看成一台机器，货物看成工件，目标是同时最小化储存费用和违约金，这就转化成一 个双目标排序问题 例3 ：某单位组织员工进行透视体检，人员要分批进入室内，同一批进入