（运筹学与控制论专业论文）一类单机具有主次指标的排序问题.pdf

详细中文摘要 由于以误时工传数作为一个指标豹擎橇主次指标摊序润遂中有三个问题的笈杂髓至 今仍是来解的。本文就着力研究以误时工件数z 。，和最大误时霸。鼹个指标分别作为主次 指标的排序问题的两个多项式可解的予问题：1 、单机、工件系统舆有加工时间和工期一 致往、以最大误爵为主指标、戮谡辩工件数为次指标懿簿疼闯踅；2 、单毫毪、工件系绕翊 j e 期并带有准备丑寸阅且准备时间和工期一致、以最大误时为主指标、以误时工件数为次指 标的排序问题。 1 问题1 | | 巧i 的具有一致憔的予问题 本文第二章研究y m 件系统的加工时问和工期一致( a g r e e a b l e ) 的子问题，并给出 了该闷逶的多项式孵润算法，从而证鹾了该闻麓为p 问题。 算法1 ： ll a g r e e a b l e ，p r m p | 缉l 咒。 ( i ) 将工 串z ，五，z 重象撩裂，使褥 n 仇岛且d 如成 ( i i )若p ，西，则将工件石无间断( 从而机器无空闲) 地从0 时刻开始加工；否则 协 讲，则将工件石安辩在时间段 西十五。，+ 一荔，4 + 名月进行船工。 ( i i i )设工僻五，石，石( j 锄在稚l 器上瓣船工澄经确定。蓿工俘五+ ，奁最早静哥开 工时刻可中断加工能接肄究工，则在最单可开工时刻对工件鼻+ ，进行可中断加二r ：，使得在 e + ，之前机器无空阕时阔；否则，将工件z 。安排在妒。之前的长度为旃+ ，的空闲时阊段 内进行可中断加工。 定灌1 黼蘑i i ( 1 a g r e e a b ! e ，p 御| 彩| 黝是p 瀚蘧。 定理2 问透i ( 1 | a g r e e a b l ei 配l 酗是p 问题。 2 霹麓llf 珐| 妻孽具有准备对阊豹子阔题 本文第三章研究7 荣鸯准备辩阉豹王 孛系统懿一令多瑷式可麟瓣子阚题。 算法2 ：1 l ( 如谚) a g r e e a b l e ，妒np r m pi 配 咒。 ( i ) 将工件 ，以，上麓新排列，使得 苗蟊西盏n 乃厶。 ( i i ) 设n 一是由e r d 廖褥到的一个排序。诞x 。所占用黪时趣瑗为 x = x ( # ) 。 雹：= l 。 ( i i i ) 若工件五在最早开工时刻 辅= m a x r s , r a i n f ff x ) ) 开工能够按时完工，令y j 是x 中从时刻滞开始的长度为p 的时间段。令工件山在时间段 y j 上加工。置x ：= x y j 。转( v ) 。 ( i v )若工件正在蕞翠霹舞工时刻 母= m a x r j , m i n t ! te x 开王不能按时完工。令王终系统 五，勘，。朋在x 上以可中断e d d 序避芎亍撼序所占 有的加工时间段为x 差x 。记时间段 y j = r x x i 毋t 西+ 。) 。 设时间段y i 的长度为，叉记时间段x 中恰处于时刻才+ 咒，前的长度为p 一，的时间 段舞y i ”。令 = y j 7 u y j ”。 霉x ：= ) ( y j 。转( v ) 。 ( ￥) 若 n ，剡薰歹户l 转( i i i ) ：蓑歹= 胁则停。 定理3 闻题：ll ( 如毋a g r e e a b l e ，万碾p r m pi 毋 是p 问题a 关键词：排序 主次指标多项式时间算法 误时工件数最大误时 a b s t r a c t f o rs i n g l em a c h i n ep r i m a r y - s e c o n d a r yc r i t e r i as c h e d u l i n g p r o b l e m s ，t h e r ea r et h r e eo p e n p r o b l e m sw h i c h a l lh a v e e a s o n eo ft h ec r i t e r i a t h ep r o b l e m ss t u d i e di nt h i sp a p e ra r et w o p o l y n o m i a l l ys o l v a b l es u b c a s e sa b o u to n e o f t h et h r e ep r o b l e m s ，w h i c hc a nb es t a t e da sf o l l o w s ： 1 s i n g l em a c h i n es c h e d u l i n gt o m i n i m i z et h en u m b e ro ft a r d yj o b sw i t ht h em a x i m u m t a r d i n e s sb e i n gm i n i m i z e df i r s t ，s u b j e c tt ot h ej o bs y s t e mw i t ht h ej o b s p r o c e s s i n gt i m e sb e i n g a g r e e a b l ew i t ht h e i rd u e d a t e s 2 s i n g l em a c h i n es c h e d u l i n gt o m i n i m i z et h en u m b e ro ft a r d yj o b sw i t ht h em a x i m u m t a r d i n e s sb e i n gm i n i m i z e df i r s t ，s u b j e c tt ot h ej o bs y s t e mw i t hi d e n t i c a lp r o c e s s i n gt i m e sa n dt h e j o b s r e l e a s ed a t e sb e i n ga g r e e a b l e w i t ht h e i rd u ed a t e s 1 a s u b p r o b l e m o f p r o b l e mi l i z u ji 矗w i t h t h e j o b s p r o c e s s i n g t i m e s b e i n g a g r e e a b l e w i t ht h e i rd u ed a t e s i nc h a p t e r2 ，ap o l y n o m i a l - t i m ea l g o r i t h mf o rt h i ss u b p r o b l e m i sf o u n d s ot h es u b p r o b l e mi s p p r o b l e m a l g o r i t h m 11i a g r e e a b l e ，p r m pi i “ ( i ) s e q u e n c e t h ej o b si ne d do r d e rs u c ht h a t p ，肋胁a n d d l 函巩 ( i i ) i f p ，曼d ，l e tj r s t a r tw o r k u n p r e m p t i v e l y a tt i m e0 ，o t h e r w i s e ，s c h e d u l ei tf r o mt i m ed + k 。 一p 1 t o t i m e d l 七t 0 ( i i i ) s u p p o s et h a tj _ ，以，西( f ，1 ) h a v ea l r e a d y b e e ns c h e d u l e d i fj j + ，c a nb eo n i m 。l y s c h e d u l e db ys t a r t i n gi t sp r o c e s s i n gp r e e m p t i v e l y a tt h ee a r l i e s ta v a i l a b l et i m e ，t h e nw e s c h e d u l 。 + ，b ys t a r t i n gi t sp r o c e s s i n gp r e e m p t i v e l y a tt h ee a r l i e s ta v a i l a b l et i m e ；o t h e r w i s e ，s c h 8 d u l 。 t a tt h el a s t p ，f r e et i m eb e f o r et i m e 扩 t h e o 代m 1p r o b l e mi i ( 1i a g r e e a b l e ，p r m pl mi ) i s a p - p r o b l e m t h e o r e m2 p r o b l e m i ( 1 i a g r e e a b l ei uie 。) i sap p r o n e m 2 as u b p r o b l e mo f p r o b l e ml l l x i 矗“w h e r et h ej o b sh a v er e l e a s ed a t e s t h i ss u b p r o b l e mi ss t u d i e di nc h a p t e r3 ap o l y n o m i a l t i m e a l g o r i t h mi sa l s of o u n df o rt h i s s u b p r o b l e m a l g o r i t h m 21 i ( ，d j ) a g r e e a b l e ，易亏陆p r m p 巧i 是。 ( i ) s e q u e n c e ，正，工i n e d do r d e rs u c ht h a t 西如磊且，乜h 。 f i i ) l e t “e r dr e p r e s e n tt h es e q u e n c eu n d e rt h ee r d o r d e ra n dx r e p r e s e n tt h eo c c u p i e dt i m e p e r i o d ( i n t e r v a l s ，s l o t s ) o f t h ej o b s p r o c e s s i n gt i m e u n d e rt h es c h e d u l e “e r dt h a ti s x ：= x ( 班r d ) s e t j ：= 1 ( i i i ) i f j o b 岳c a n b e p r e e m p t i v e l y s c h e d u l e ds u c ht h a t 巧s t a r t si t sp r o c e s s i n ga tt i m e t + 2 m p l x 0 ，m i n t j t x ) a n dc o m p l e t e si t sp r o c e s s i n gb e f o r et i m e 西t h e nw ep r e e m p t i v e l ys c h e d u l ej o b 巧b ys t a r t si t s p r o c e s s i n ga tt i m e d e n o t e t h et i m ep e r i o do c c u p i e db yt h ep r o c e s s i n go f j jb yy s e tx ：。 y 。g o t o ( v ) ， ( i v ) s u p p o s et h a tj o b 乓c a l ln o t b ep r e e m p t i v e l ys c h e d u l e ds u c ht h a t 占s t a r t si t sp r o c e s s i n ga t t i m e ，十= m a x 强m n r f f x a n dc o m p l e t e si t sp r o c e s s i n gb e f o r et i m e 喀l e t x b et h et i m ep e r i o do f t h ep r o c e s s i n go ft h e j o b s 专+ ，审2 ，五 u n d e r e d do r d e rs t a r t i n ga tt i m et 4 d e n o t e y j = ，x x 咯墨f 曼磅十7 k 甜+ l e t b e m e l e n g t l lo f t h e p e 抽dy j a n d y j ”b ea p e r i o d o f t i m e j u s tb e f o r e t h e t i m e 西+ “+ i nx w h i c hh a st h el e n g t h p 一，d e n o t e y j 2 y i u x ” t h e nw e p r e e m p t i v e l y s c h e d u l e j o b 巧i n t h et i m ep e r i o dy j s e tx ：2x y i g o t o ( v ) ( v ) i f j o 躐嚣( 筇) = o 并用以袭明工彳牛z 误工与磷，l 矗。 常见酾最小记鞴称肖：憩流程另( 芹) ，总误时乃( 嚣) ，最大误时( 尊) = t t t 持x 为嚣) 1 ，商，诿王传数秘( 丑骧及它们的舾投形式：热王慧流程e 霹髯( 嚣) ， 擞权惑谈时形( 描) ，热投诿工工传数e 鬈留 o 躐嚣( 井) = o 并用以袭明工彳牛z 误工与露，l 月。 常见静最小记鞴称肖：憩流程另( 芹) ，总误时乃( 嚣) ，最大误时( 尊) = 嬲芹 为嚣) l ，璃，诿王传数辑( 噩竣及它铘的姗投形式：觏王总流程黟只嚣 ， 擞权惑泼对彤乃( 嚣) ，热投误工工侔数彰留 露) 。这些醒标毽数在本文中将被分爨遮 为芦( = 瑚、e t ( 然兄) 、咒，、e 劫、孵( 竺删、彰( 嚣孵彩、 爨( 一影彩。 6 文 2 对上面7 个溪标掰霸组合构成鳇犟枫主次指标的排序润题迸行了研究，褥裹了 它们熬复杂瞧如下袭1 。 表l ：1 1 ；f ，ly ，静复杂性( p ：p 阍蘧；勰_ h ：n p 一困难闻题 o ：未解问题) 主指标次指标n 霸。 f野z u款丁 x w t 霸。 pn p hon p - hn p - h n p h fppppp 骆ppn p - hn p _ 魏n p 也 uen 擎氇n p - hon p 氇 箨乞n 瓢ln n ln p 南n p mn p - h fn p 去 p 氇n p 也n p 壤n p - h 芑驺n p 点n n hn p - hn p 氇n p 也 上表中我铝看到了7 令据标组合成的妻次指标接序的3 6 令阕越。其中只有3 个谶踅 仍然是来熬闯题，i 旺黾都璺误对工件数u 住为其菜一指椽豹l ；霹_ 题。另外有2 s 个融疆是 n p 潮难鹊海题，有8 个润题怒多项式可解瓣蠲题。在多项式霹解豹翔题中，都含有f 或 陈捧为其荣指标。冀窀阏疆豫f 或瓢为第一指标外均为n p o 瓣难惩蘧。 文【3 】讨论了具有主次指标的单枫嗣王麓排序l 司题，其每一个王等均在0 对瓤蓟遮。7 个指糖组合成的圭次指标摊序的3 6 个阔题中，1 5 个闯题是n p 戮难的，其余2 1 个润题则 是p 麓题。它们的复杂缝觅下裘2 。 文强】磺究了敬误辩王箨数为主捂拣，熬羧大漩嚣于为次担搽戆主竣攮标随浆翡一个势 棱定界冀法，该算法髓蠢效熬解决工件数在1 0 0 0 戳内的闷题。 表2 ：iid = d | y t | r ，的复杂性( p ：p 润题：n p h ：# p 一困难藏题) 主指振y ，次撂标y 2 瓦。职 既u敝f胁 k 。p ppn p hpn p - h fpp ppp 盼 ppn p hpp u p pn p - h p n p h x w n p hn p hn p _ hn p hn p - h rppppp lz 骄n p - hn p _ h n p hn p - hn p - h 1 , 4 本文的圭簧结莱 出予和误时工件数有燕韵主次指标阔题中有三个问题的复杂健至今仍是未解的。本文 就着力磅究以最大误对霸。终圭指标、以误孵工终数z u 作次撂撂懿接痔闯题的鼹令多顼 式可解的子问题：l 、单机、工件系统具有加正时间和工期一致、以最大误时为主指标、 以误霸寸工件数为次指标的排序问题；2 、单机、工件系统同工期并带有凇备时间、且准备 鞋瓣粒王鬻一致、以最大误鞋必燕指标、激谈蹲工黪数为次撂糠豹撵枣瓣题。 主要结果如下； 定理2 4 问鼹i i ( 1l a g r e e a b l e ，p r m pl lk ) 怒p 阕瓤。 定理2 5 问戢i ( 1la g r e e a b l ei ，lk ) 与问题i i ( 1i a g r e e a b l e ，p r m pl i 五。) 的最优解相同，最优值招等。 定理2 6 问题i ( 1fa g r e e a b l ei i ) 魁p 问题。 定理3 5 问题1i ( “砌a g r e e a b l e ，舟p r m pl 扩ik 烧p 问题。 8 第二章闻题1 ij 扩| 磊；的具有一致性的子问题 2 1 蟊题1 | l 扩| 磊，最优解的性质 本问题1 ，| 的主指标是最大误时，次指标是误时工件数。也就是要在畿小的 最大误时的限制下，找具骞最小的误时工 牛数的序列。该闯题豹个可行解是指最大误时 是最小的所有工件的加工次序的序列。它是表1 中3 个未解问题之一。下面我们先来看一 下分掰戳最大误时和误时工件数为指标的单指标问题的情况。 在文 s 中关予以最大误辩为指标的排痔闻题有下面静结论： 禽题2 。1e d d ( e a r l i e s td u ed a t ef i r s t ) 序是问题1i 名，的一个最优解。 这里豹e d d 序是指按各工件工期不降静次序对工件进行排列。对给定的工件，可用算 法2 。l 在o ( n o g o ) 时闻内找到问题1 ii ? 纛的最优解。 算法2 。l ；11 l 疋瓣e d d 算法 ( i ) 擦工件正，厶，正重新排列，使褥 西盛a l ( i i )对新的工件编号，令工件石的完工时间为 e = 岛( 其中g = 0 ) ( i i i )令= 嬲盖 0 以0 ，输出k 的数值即为最优值丘 在文 6 中关予以误时工件数为指标的排序问题有下面的结论： 命题2 2 问题1 1 的最优解由m o o r e 算法产生。 m o o r e 算法 6 的思想如下：将要排序的工件按e d d 序排列，并依e d d 序逐个检查它的 下述穗征：该工 牛乏前静工件分成按期宪工静王俘集。( o n - t i m ej o b s ) 和误时的工件集 。( t a r d yj o b s ) a 熄该工传放在它前面的能按期完工的工件集盎；之中，并以它结素。麴 果它不能按期完工，则将它之前的按期完i i 件中加工时间最长的工件放入a ：，作为误时 9 工馋。否裂，该工件在矗；中是戆按期完工懿王徉。我们将工 牛集矗，袭。分别按e d d 露捧 列，就得到了命题2 2 所说的最优解。 m o o r e 算法的时间界为o ( n l o g n ) 。 受到上述两个单指标排序问题的算法思想的启发，结合下面所讨论的具有主次指标的 捧痔阏透l | i u lk 最伉解翡健质，我将要讨论一些多项式可瓣豹一垫子问题。 定理2 。l溺题l u 7 0 存在按赣宪工工件帮误时工锌都以e d d ( e a r l i e s td u e d a t ef i r s t ) 序排列的最忧缌。 诞骧设阀题有一个最优鳞耵，在序列耵孛工锌z 捧在工传互之前，且它们的正鬟 a i 。那么，将序列丌中的工件正移动到紧跟工件山后的位置，其它工件在次序不变的 前提下，徽籀痤移动，记诧净剜为m 。下面考虑m 串工伴和工件另躺误对情况： r a m ) = 0 ( 玎一菇= 【0 ( 秽_ 蝴- d , = 囝一鳓- p j = 乃( m - p j 乃( 彩l ( f 略。g 7 d 一喀= 0 ( 醇一d , - 萌，则将工释z 安捧在时潞段咖露? 一曲，咖气一迸彳亍加工。 ( i i i )设工件z ，石，z ( ? 饼在撬嚣主豹热_ i 已经确定。若工箨z “在最辜熬霹开 工时刻可中断加工能按时究工，则在最早可开工时刻对工件+ ，进行可中断加工，使得在 + ，之前机器无空闲时间；否则，将工件+ ，安排在d + ，+ 幺? 之前的长度为p w 的空闲时间段 内进行可中断加工。 定理2 2 鼙法2 2 绘出了闳熬i i ( i | a g r e e a b l e ，p r m p | 秽| 的最优解。 证明设算法2 2 褥到静蓊 序为玎。簧| j 对 王一工件五或者 锄西 躐者 苟 毋( 嬲西+ 置7 从而总有乃( 哪7 0 。这就说明了算法2 2 使得第一指标z 。达到了最优。为证明定理 的正确性，只需证明在可中断及具有约束条件乃丘? 的情形下算法2 2 得到的排序使 得秽迭翻簸小。 装琴然，设。燕在零孛叛教具有约束条棒五0 懿壤形使褥秽这到最，l 、豹一个蓑 序( 下文称为最优排序) ，但是0 与丌本质不同，即存在工件另锼得g ( 0 ) 奠( 丌) 。令 膏= 并( 丌jo ) = 埘如 10 ( 0 ) 0 ( m 。 进一步，不妨设0 的选取使得j = 并( m0 ) 达到了最大。这样，对于1 x 1 ，均有0 ( 0 ) = e ( 踊。壶予工件豹可中断性，对于误工的工粹，在满足误辩不越过五0 豹限制下，可潋尽 可能地往后排。这样徽并不影响。的最优性。上述过程可以按照王件的序号从小到大的顺 序从0 出发逐步进行。显然，得到的新序列0 仍是一个最优排序，且对l 一 d l 量 鼗嚣壹，童算法2 。2 ，露笈在最旱懿哥开工露刻瓣工传z 遴行鸯弱工，五锯是误工豹e 壹 于a ，帮科在。u 。上的一致性，工件上在o 下一定是误时工件。但由予z 在排序球 下是按照“在误时不超过? 的限制下，可以尽可能地往后