（运筹学与控制论专业论文）具有等长工件平行批排序模型的一些结果.pdf

摘要 排序( s c h e d u l i n g ) 就是在一定的约束条件下对工件和机器按时间进行分配 和安排加工次序，使一个或多个目标达到最优排序论作为运筹学的一个重要 分支，目前受到国内外学者的广泛关注本文主要对于等长工件平行批排序模 型进行了研究，作了以下两方面的工作：( 1 ) 具有优先约束，到达时间、等长 工件的单机平行批排序问题；( 2 ) 具有到达时间、加工时间相同，极小化加权 总误工的单机平行批排序问题 一个批机器或批加工机器是指可同时将几个工件作为一批进行加工的机 器，每一批的加工时间等于这批工件中最长的加工时间一旦一批工件开始加 工就不能被中断，其他工件也不能加入该批 本文中研究的问题可描述如下：假设有n 个工件 ，如，厶，一台在给定的 时间内只能加工一批工件的机器工件之间具有优先约束关系，每个工件如有 加工时间功和到达时间吩( 其中巧，勺都为整数) 工件是成批被加工处理的， 这里的一批是指工件的一个子集，这些批( 子集) 构成了工件集的一个划分一 个批的加工时间等于这批工件中最大的加工时间，即融= m a x p ，：以毋，如 果工件 ，乃有优先约束正 乃，则要求以一定要在五完工后加工这意味着 j ：f 和七不能在同一批中被加工一批的完工时间定义为该批所有工件的完工 时间，即g = 8 。+ m a x p ，：易玩) 参照文献【1 】i 【2 】：我们称这个排序模型为平行批排序问题，记为 l l p r e c ；p - b a t c h ；q i ， 这里，是要优化的目标函数 主要结果如下： ( 1 ) 具有优先约束、到达时间、等长工件的单机平行批排序问题 我们对于具有优先约束，k 个不同到达时间，等长工件的最大延迟极小化 单机平行批排序问题进行了研究首先，对于有固定k 个不同到达时间r ( o ( 1 i k ) 的平行批排序模型，给出块的概念进而证明在最优排序中所有块的构 形是这样的时间序列( r ( ”，r ( ”，r ( ”a ) ( 1st bs 后) ，其中r ( 7 ( 1 ) ，7 ，7 ( ) ) 其次，对于所有可能的构形进行枚举，并给出一个0 ( 2 n l o g k n 2 ) 时间的算法求 解l 。最优值最后对于问题1 i p r e c ；p - b a t c h ；p j = p ；7 ( ) ，ie 1 ，2 ，：k l f ，当， 为和函数厶形式，即， w 3 g ，g ，u j ，q ，乃，屿乃) 时，给出了 一个0 ( 2 n ) 时间算法当k 为一固定值时，这两个问题是多项式可解的 ( 2 ) 具有到达时间，加工时间相同极小化加权总误工的单机平行批排序问 题 b a p t i s t e 在【5 l 中给出了问题l i p - b a t c h ；b n ；乃= p ；r j i ， w j ，哟g ，t j 的一个o ( n s ) 时间的动态规划算法，并指出对于目标函数嘶t j ，平行批等长工 件问题的计算复杂性仍是未解的本文中，我们将讨论问题l i p - b a t c h ；b n ；p i = p ；r l i 嘶乃首先，我们假设w l w 2 2w n 且d lsd 2 sd n ，即工件的 权数与工期是反一致的此时，通过适当的修正，t 吩乃就为一个有序的目标 函数，这使得我们的排序问题具有特定的优势性质其次，建立动态规划参数 及方程，给出一个o ( b 2 n 7 ) ( b n ) 的时间动态规划算法求解最优值 关键词：单机；排序；平行批；工期；最大延迟；优先约束；加权误工和 a b s t r a c t s c h e d u l i n gi st oa s s i g nj o b sp r o c e s s e do i lm a c h i n e su n d e rs o m ec o n s t r a i n s ，s u c ht h a t o n e - o rm u l t i - c r i t e r i aa t t a i nt ot h eo p t i m u m t h et h e o r yo fs c h e d u l i n gi sa l li m p o r t a n t b r a n c ho ft h eo p e r a t i o n sr e s e a r c h ，w h i c hh a sr e c e i v e dm u c ha t t e n t i o nb ym a n ys c h o l a r s i n t h i sp a p e r ，w ec o n s i d e rt h es i n g l em a c h i n ep a r a l l e l - b a t c h i n gs c h e d u l i n gp r o b l e mw i t he q u a l p r o c e s s i n gt i m e o u rs t u d yi n c l u d e ：( 1 ) s c h e d u l i n gap a r a l l e l - b a t c h i n gm a c h i n es u b j e c t t op r e c e d e n c ec o n s t r a i n t s ，kd i s t i n c tr e l e a s ed a t e sa n de q u a lp r o c e s s i n gt i m e ；( 2 ) s i n g l e m a c h i n ep a r a l l e l - h a t c h i n gs c h e d u l i n gp r o b l e mt om i n i m i z et o t a lw e i g h t e dt a r d i n e s sw i t h 七 d i s t i n c tr e l e a s ed a t e sa n de q u a lp r o c e s s i n gt i m e ， ab a t c hm a c h i n eo rb a t c hp r o c e s s i n gm a c h i n ei sam a c h i n et h a te a r lp r o c e s ss e v e r a l j o b ss i m u l t a n e o u s l ya sab a t c h a n dt 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 o n g e s t p r o c e s s i n gt i m eo fa l lt h ej o b si nt h eb a t c h o n c et h ep r o c e s s i n go fb a t c hi si n i t i a t e d ，i t c a n n o tb ei n t e r r u p t e d ，n o rc a no t h e rj o b sb ei n t r o d u c e di n t ot h eb a t c h -f t h ep r o b l e m st h a tw es t u d yi nt h i sp a p e rc a nb ef o r m u l a t e d8 st h ef o l l o w i n gm o d e l ： l e tn j o b sj l ，j 2 ，厶a n das i n g l em a c h i n et h a tc a nh a n d l eb a t c hj o b sa tt h es a m et i m e b eg i v e n t h e r ea r ep r e c e d e n c er e l a t i o n b e t w e e nt h e j o b s e a c hj o b 也h a sap r o c e s s i n g t i m e 聊a n dar e l e a s ed a t er jt w h e r ep ja n dr ia r ei n t e g e r ) t h ej o b sa r ep r o c e s s e di n b a t c h e s ，w h e r eab a t c hi sas u b s e to f j o b sa n dw er e q u i r et h a tt h eb a t c h e sf o r map a r t i t i o n o ft h es e to fa l lj o b s 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 o n g e s tp r o c e s s i n gt i m e o f a l l t h e j o b s i n t h e b a t c h ，i e ，= m a x p ，：弓b ， l ，2 ， i f 五a n d 弓b r e t w oj o b ss u c ht h a tj j ，w ea l s or e q u i r et h a tj 3b ep r o c e s s e da f t e rt h ec o m p l e t i o nt i m eo f j i ；s oj a n dj c a n n o t b e p r o c e s s e d i n t h e 8 a l n e b a t c h t h e c o m p l e t i o n t i m e o f a j l t h e j o b s i nab a t c hi sd e f i n e d 嬲t h ec o m p l e t i o nt i m eo f t h eb a t c h ，i e ，g = s = + m a x 【p j ：乃见) f o l l o w i n g 【i i ，【2 l w ec a l lt h i sm o d l et h ep a r a l l e l - b a t c h i n gs c h e d u l i n gp r o b l e ma n dd e - n o t e i t b y l l p r e c ；p - b a t c h ；r j i ， w h e r e ，i st h eo b j e c t i v ef u n c t i o nt ob em i n i m i z e d t h em a i nc o n c l u s i o na sf o l l o w ： ( 1 ) s c h e d u l i n gap a r a l l e l b a t c h i n gm a c h i n es u b j e c tt op r e c e d e n c ec o n s t r a i n t s ，kd i s - t i n c tr e l e a s ed a t e sa n de q u a lp r o c e s s i n gt i m e w ec o n s i d e rt h ep r o b l e ml l p r e c ；p - b a t c h ；p i = p ；r ( o ，i 1 ，2 ，七 l l m a x f i r s t ， w eg i v et h ed e f i n i t i o no fb l o c kf o rt h ep a r a l l e lb a t c hs c h e d u l i n gw i t hkd i s t i n c tr e l e a s e d a t e s ”( 1 ) ( 1si 后) ：a n ds h o wt h a ta no p t i m a ls c h e d u l e i sg i v e nb yt h er e l e a s e d a t es e q u e n c e ( r ( ，r ( ，r ( m ) ( 1 n bsk ) f o re a c hc o n s t r u c t i o no fb l o c k s e c o n d ，w e e n u m e r a t ea l lc o n s t r u c t i o n o f b l o c k ，a n d g i v e a n o ( 2 n l o g k n 2 ) p o l y n o m i a l t i m e a l g o r i t h m f i n a l l y , w ea l s os h o wt h a tt h ep r o b l e ml l p r e e ；p - b a t c h ；p i = p i r ( o ，i 1 ，2 ，砖l ， f z w j q ，g ，屿u j ，t j ，嘶t j ) c a n b es o l v e di n0 ( 2 7 1 ) t i m e ( 2 ) s i n g l em a c h i n ep a r a l l e l - b a t c h i n gs c h e d u l i n gp r o b l e mt om i n i m i z et o t a lw e i g h t e d t a r d i n e s sw i t h 尼d i s t i n c tr e l e a s ed a t e sa n de q u a lp r o c e s s i n gt i m e b a p t i s t eh a sg i v e n 蛐o ( n 8 ) t i m ed y n a m i cp o r g r a m m i n ga l g o r i t h mi n1 5 1 f o rt h e p r o b l e m l i p - b a t c h b n ，r i ，鼽= 训，f 毗阢，w i g ，正) ，a n d p o i n t e d o u t t h a t f o rt h ec r i t e r i a w i 正b a t c h i n gi d e n t i c a lj o b si ss t i l la no p e np r o b l e m i nt h i sp a p e r ，w es t u d yt h ep a r a l l e l - b a t c h i n gs c h e d u l i n gp r o b l e ml l p r e c ；i 沪b a t c h ，b 0 ，将输出一个常数c 并且如果以任意输入p 的一 个实例，和个f 0 ，它将输出，的个可行解且满足a ( i ，e ) ( i + e ) o p t ( 1 ) + c , 对每个固定的f a 的运行时f 司有界于s i z e ( 1 ) 的个多项式我们也把多项式时 间的近似方案缩写为p e a s 1 2平行批排序问题 这一节我们介绍平行批排序模型它是一种实际应用背景很广泛的排序模 型，在许多文献上都受到了关注和研究平行批排序问题的基本模型最初是由 l e ef 3 1 首次提出的，每批的工件数限制不超过6 记作1 i p - b a t c h ；6 n i l 这种有 界的模型是受到半导体制造业的燃烧实验工序的启发如将一批集成电路放在 大小有限的一个烤箱内加热以便测试它们的耐热能力，这些电路放在烤箱内直 到所有电路烧断，电路的加工时间( 燃烧) 可以不同，当一个电路被烧断后，它 必须在烤箱中等到所有电路都被烧断因此这批电路的加工时间是这批工件中 最大的加工时间 5 平行批排序的无界形式在【4 】中给出了广泛的研究这种无界形式在实践 中也有大量的应用例如一批物质需要在一个充分大的窑里加热变硬，这时每 批的容量就没有限制 而对于单机等长工件的平行批排序问题，在服务行业也有着广泛的应用， 因为通常服务是标准化的，即所有工件加工时间是相同的此外工件( 顾客或 订单) 可以不同时间到达，具有不同的工期等等例如，飞机场上的飞机需要 标准化检查，对于不同的飞机检查时间相同，而这些飞机的着陆时间( 到达时 间) 和起飞时间( 工期) 是不同的这样的排序问题与我们的排序模型是一样 的 一般而言，平行批排序问题可描述如下：假设有n 个工件 ，以，厶，一 台在给定的时间内只能加工一批工件的机器工件之间可以具有优先约束关 系，也可以不具有优先约束关系每个工件乃有加工时间乃和到达时间巧( 其 中丹，巧都为整数) 工件是成批被加工处理的，这里的一批是指工件的一个子 集，这些批( 子集) 构成了工件集的一个划分一旦一批工件开始加工就不能 被中断，其他工件也不能加入该批一个批的加工时间等于这批工件中最大的 加工时间，即儿= m a x 锄：乃岛，另外，我们给定一个批序后，就将按这 个批序加工这些工件，要求每批的开始时间至少应为这批工件中最大的到达时 间，即8 ；= m a x 扔：如玩) ，而且亦称为b 的到达时间如果工件 ，易有优先约束五 乃，则要求与一定要在五完工后加工这意味着五和如 不能在同一批中被加工一批的完工时间定义为该批所有工件的完工时间，即 g = + m a x 切：易岛) 参照文献【1 】， 2 1 ，我们称这个排序模型为平行批排序问题，无界形式记为 l l p r e c ；p - b a t c h ；p j ；r j f ，或l p - b a t h ；p j ；r a f 有界形式记为 l p r e c ；p - b a t c h ；6 n ；p j ；q l ，或1 p - b a t c h ；b d j ，则：1 现在，我们开始介绍一些规则的优化指标 g 一最大完工时间，在这里g 。= m a x c j l a j s ，1 ) k “最大延迟，在这里工一= m a x l i 1 j n ) 0 完工时间和 嘶q 加权完工时间和 乃误工时间和 乃加权误工时间和 误工工件数 屿加权误工工件数 7 1 4已知结果及本文主要结果 关于单机平行批排序问题的最优化研究在书【1 】i 文献【2 1 【3 l | 4 】【5 1 5 6 11 7 1 及网 址【8 】上有大量的研究我们在此列举一些已有的结果： ( 1 ) 2 0 0 1 年，p b r u c k e r1 1 1 证明了问题l p r e c ；p ，= p ；p - b a t c hi ，对于每个正则 的目标函数都有一个的o ( n ：) 算法 ( 2 ) 2 0 0 4 年，c h e n g ，n g ，y u a n 和l i u 【6 】给出了即使是链式约束问题 1 c h a i n s ；p - b a t c h c , 一和l l c h a i n s ；p - b a t c hi 岛，也是强n p - 困难的而当工件与 加工时间是一致的或是反一致的情形，即当五 乃，表明p s 乃或当五 以， 表明肼乃时，问题1 p r e c ；p - b a t c hi g 一可以在o ( n 2 ) 时间界内可解 ( 3 ) 2 0 0 5 年，c h e n g ，y u a n 和y a n g 在文献啊中给出了一些关于带有约束条 件到达时间、加工时间相同的单机平行批排序问题的结论 给出了问题l l p r e c ：, p ，= 1 ；p - b a t c hi ，的一个o ( n 2 ) 时间算法 当工件有不同的到达时间时，对于问题l c o m p e t e - p r e c ；p - b a t c h ；约= p ；巧l ， 指出可在o ( n 7 ) 时间界内解决 对问题l l p r e c ；, p c = p ；p - b a t c h ；r j le w j g 给出了一个近似算法( r e l e a s ed a t e r o u n d i n ga l g o r i t h m ) 对问题1 p r e c ；p j = p ；p - b a t c h ；r jj g 。给出了个o ( n 2 ) 时间算法 ( 4 ) 2 0 0 5 年，y u a n ，s h a n g 在【lo l 中对1 1 p r e c , , p c = p ；p - b a t c h ；吩i g 又进一 步给出了一个d 协料2 ) 时间的( 1 + 击i ) 一因子近似算法，即一个p t a s ( 5 ) 2 0 0 0 年，p b a p t i s t e 5 】对于问题l i p - b a t c h ；b n ；r 渤= p i ， ， q ，嘶q ，e t a 给出了卟o ( n 8 ) 时间的动态规划算法 在本文我们作了以下几方面的工作t ( 1 ) 对于具有优先约束，七个不同到达时间，等长工件的最大延迟极小化单 机平行批排序问题首先，对于有固定k 个不同到达时间r ( o ( 1s is 七) 的平 行批排序模型，给出块的概念进而证明在最优排序中所有块的构形是这样的 时间序列( r ( ”，r ( 2 ) ，r ( ) ( 1 f 1 6s 七) ，其中r ( 7 ( 1 ) ，7 ( 2 ) ，”( ) ) 其次，对于 所有可能的构形进行枚举，并给出一个0 ( 2 n l o g k n 2 ) 时间的算法求解一最 r 优值 ( 2 ) 对于问题l l p f e c ；p - b a t c h ；p l = p ；r i o ，i 1 ，2 ，七) f ， 当，为和函数，j 形式，即， 嘶q ，g ，q ，乃，q 乃时，给出了一个o ( 2 n ) 时 问算法当k 为一固定值时是多项式可解的 ( 3 ) 对于具有到达时间，加工时间相同极小化加权总误工的单机平行批排 序问题l i p - b a t c h ；b n ；p s = p ；勺l w j 乃首先，我们假设 1 1 1 1 2 w n 且 d l d 2s 蟊，即工件的权数与工期是反一致的此时，通过适当的修正， q 乃就为一个有序的目标函数，这使得我们的排序问题具有特定的优势性 质其次，建立动态规划参数及方程，给出一个o ( b 2 n 7 ) ( b m 的时间动态规 划算法求解最优值 9 第二章具有优先约束、到达时间、等长工件单机平行批的最优化 排序问题 2 1相关介绍 一个批机器或批加工机器是指可同时将几个工件作为一批进行加工的机 器，每一批的加工时间等于这批工件中最长的加工时间一旦一批工件开始加 工就不能被中断，其他工件也不能加入该批 在这里我们研究的问题可描述如下：假设有n 个工件j l ，五，厶，一台在 给定的时间内只能加工一批工件的机器工件之间具有优先约束关系，每个工 件易有加工时间乃和到达时间q ( 其中p j ，r j 都为整数) 工件是成批被加工 处理的，这里的一批是指工件的一个子集，这些批( 子集) 构成了工件集的一 个划分一个批的加工时间等于这批工件中最大的加工时间，即m = m a x p j ： 乃鼠 ，z 1 ，2 ， 另外，我们给定一个批序后，就将按这个批序加 工这些工件，要求每批的开始时间至少应为这批工件中最大的到达时间，即 之h = m a x r j ：易毋 ，而且亦称为现的到达时间如果工件正，乃 有优先约束五 乃，则要求如一定要在 完工后加工这意味着 和弓不 能在同一批中被加工一批的完工时间定义为该批所有工件的完工时间，即 c z = s z + m a x p j ：j j b t 、 参照文献【1 1 ， 2 1 ，我们称这个排序模型为平行批排序问题，记为 l p r e e ；p - b a t c h ；r j f 这里，是要优化的目标函数在给定的排序下，为g 的函数我们假设，是 正则的，即，( q ) 关于g 是非减的函数 对于问题l p r e c ；p - b a t c h ；r j l ，个可行排序是由个批序b s = ( b 1 ，b 2 ，b n ) 给出的这个批序满足 ( 1 ) 对五 如的两个工件，如果五毋，五日，则一定有z r ( 2 ) ， 则可将磷2 向左平移得到一个新的最优排序，使得尉2 在时刻r i 2 开工并置 r ( 2 ) ：= r i 2 依次类推我们可以得出每一块( b l o c k ) 的开工时间r a r o ) ，( 2 ) ，r ( 女) ( 1 i 竹b ) 口 定理2 对于问题l l p r e c ；p - b a t c h ；办= 觑r ( o ，i ( 1 2 ，圳l 一存在一个最 优排序，使得在最优排序中块的开工时间序列为( r ( ”，r ( 2 ) ，r ( m ) ，且有块的数 目n b 七个。所有块的构形不超过o ( 2 ) 种 1 3 证明设最优排序中的分块数为l q , 一，若n - k ，则每块都有开工时间r ( “，即 r ( ”，r ( ”，r ( n a ) ，由定理1 我们知道r ( 7 ( 1 ) ，7 ( 2 ) ，7 女) ) ，这与有固定数k 个 7 f t ) 矛盾，故l s 珊sk 因此在最优排序中块的所有构形最多有； 圭l 2 l ：2 t 一1 2 t 种，即 - 1i n 6j 至多有o ( 2 ) 种构形 口 定义集合 p = r ( ) + x p ；i 1 ，2 ，七) ，z o ，1 ，2 ，：乱 ) = r ( ) + x p d j ；i l ，2 ，奄) ，z o ，1 ：2 ，n ) ，j 1 ，2 ，n ) ) 注意i p | = o ( k n ) ，i i = o ( k n 2 ) 在第一章引言中我们指出，如果目标函数关于g 是正则的，则其最优排序 必存在于优势集中，而【5 】5 讨论了平行批排序问题的优势性质，一个有用的结 论如下面引理所述 引理1 对于问题1 l p r e c ；p - b a t c h ；彤= 爿7 t 小i 1 2 七 | k 。一定存在一个 最优排序使得每批的开始时间及完工时间都属于集合p 为了叙述方便，我们把所讨论的问题记为p ( 歹) ，这里了= ，j 2 ，厶) 对于问题p ( j ) 而言，求解最优排序可转化为求解判定问题 a ( x ) ：工m s x ( v x c ) 是否有解我们用二分法澍分法) 来取定x 的值对每种块的构形进行求解 对某一固定块的构形f ，求解判定问题a ( x ) 可记为a ( x ，f ) 如果对所有块的构 形判定问题a ( x ，f ) 均无解，我们则去掉小于x 的那一半值对余下的x c 再 用二分法取值来判剔a ( x ，固有解情况如果对某些块的构形判定问题a ( x ，聊 有解，我们则去掉大于x 的那一半值，对余下的x c 再用二分法取值来判 别a ( x ，f ) 有解情况最终找出使l sx 有解的最小值x ，从而找出对应的 构形及最优排序由于| c j = o ( k n 2 ) ，将中的值用二分法取定需要o ( 1 0 9 ( k n 2 ) ) 下面考虑判定问题a ( x ，f ) ：三一x 的求解 我们的排序问题为p ( 了) ，在安排工件加工时，要考虑工件问的优先约束关 】4 系，且限定最后一批的完工时间不大于某个( 限制的) 实数丁为此，我们给出 下面的引理 引理2 设a ( x ，f ) 存在可行排序，且f 当前的最后一个块的开工时间为 r ( ( n b ) ，令：矿= m a x x ：存在无后继工件如，使得：r 1 r ( + 印，r ( + 印+ p z 且r “+ x p + p 一出s 硼则存在a ( x ，f ) 的一个可行排序，使得当前最后一 批为 b = j j ：占无后继工件，r 1 r ( + x * p ，r ( + x * p + p 一由s x ) 并且最后一批的开工时间为s = r ( ) + x * p 证明设在某个可行排序中，当前最后一块的开工时间为r ( 订，最后一批的 开工时间设为r ( + 印，由矿的定义可知z s 矿 情形1 如果z = 矿，则在无后继的工件中，能在s = r ( o + x * p 开工的工件满 足r l r ( + 矿p 且延误易不超过x ，即r ( + x * p + p d jsx 的工件恰好构成 排序中的最后一批 情形2 如果z 矿，我们可将b 中的工件，即将无后继工件，且到达时间 不超过r ( + x * p ，r ( o + x * p + p d j x ，r i o + 矿p + p t 的那部分工件从在 r ( 0 + x p 处开工的当前最后一批中取出，单独作为一批，并在s = r ( + 矿p 处开 工这并不影响判定问题a ( x ，f ) 的可行性 i - 1 由引理2 ，我们就可以给出求解判定问题a ( x ，f ) 的算法 算法a ( x ，n 。 输入：工件集了= ，无，厶；工件间的约束关系 r ( 寸”，则将它们安排到在r ( 计1 ) 处开工的那一块 中的第一批加工，即成为下一块的第一批工件 1 3 这样，我们就可以对所有块的构形按引理3 的方法进行分批排序加工工 件，显然一定有一种构形存在，使得工件即能全部安排加工，且，j 最小这 就是我们要找的最优排序我们给出下面的算法 算法日： 。 输入：工件集了= ，j 2 ，厶) ；工件间的约束关系 r ( ) ，置i ：= i + 1 ；转第三步； 1 7 第六步：对于使爹( 了) 有解的f ，比较厶的大小； 输出：使哥( 了) 有最优值的排序及最优值办 定理4 对于排序问题尹( 了) ，算法日给出了一个最优排序，且其计算复杂 性为0 ( 2 住) 证明由前面的分析及引理3 ，我们知道利用算法h 对于问题声( 了) 一定有 可行排序存在，而定理2 表明由于具有固定k ( k n ) 个到达时间r ( d ( 1si 七) ， 因此所有块的构形至多为0 ( 2 t ) 种我们依据算法日就能在那些可行排序中， 找出一种构形及排序，使得办达到最优，这恰为我们要找的最优排序 在算法何中，第一步需要0 ( 2 ) 时间，第三步要花费o ( n ) 时间，因此总的 计算时间为o ( 2 k n ) 当七为固定数时，其为多项式时间的 1 8 第三章具有到达时间、加工时间相同最小化加权总误时的单机平 行批排序问题 3 1基本概念 平行批的排序问题在许多文献上都有研究，其问题的应用背景我们在上一 章已经进行过说明而对于单机等长工件的平行批排序问题，在服务行业也有 着广泛的应用，因为通常服务是标准化的，即所有工件加工时间是相同的此 外工件( 顾客或订单) 可以不同时间到达，具有不同的工期等等例如，飞机 场上的飞机需要标准化检查，对于不同的飞机检查时间相同，而这些飞机的着 陆时间( 到达时间) 和起飞时间( 工期) 是不同的这样的排序问题与我们的 排序模型是一样的 对于平行批机器，r 有两种不同的情况，一种是有界情形，即每批至多有b 个工件，每批的加工时间为该批最大的加工时间对于等长工件，每批的加工 时间为p = 办另一种为无界情形，即每批可以有任意多个工件两种情形都 假设没有安装时阅。不过，如果需要考虑安装时问的话，可以通过将每个工件 的加工时间增加一个常数s 来处理 2 0 0 0 年，p b a p t i s t e 5 l 给出了问题l i p - b a t c h ；b n ；r j ；p j = p l y ， ， t 吩巧，q g ，e t a 的个o ( n s ) 时间的动态规划算法本文中，我们将讨 论问题l i p - b a t c h ，b ，l ，q ，易= p i t 乃的计算复杂性，其中t j = m a x 0 ，g d i ) 为工件乃的误时，嘶为工件乃的权数 一基本定义 - 下面引入文献【5 】中的有序目标函数的定义 定义1f 是一个有序的目标函数当且仅当： ( 1 ) ，是个和函数，即，= 厶( o ) ， ( 2 ) f 是正则的，即坳，f j 是非降函数， ( 3 ) 后在时刻毛后为一常数，即v t2 毋，有乃( t ) = l ( a a ， 1 9 ( 4 ) v i j ，最曼岛且t 一( ，一办) ( ) 在t o ，氐l 上是非降的 我们容易看到，目标函数嘶乃并不满足定义1 中的条件，即不是一个有 序的目标函数但我们可以通过修正使其满足定义1 中的条件而不改变其最优 值其具体方法如下：首先考虑一个充分大的时刻，其次改变后，j 的值， 使得v t n ，a t ) = m ，这里m 也是一个很大的数值而且我们注意这样的事 实，如果和m 足够大时，由于原问题在后不可能到达，因此，修正后问 题的最优值就是原问题的最优值 定义2 对于工件如而言，如果在而后完工，我们就说乃是误工的否则， 就说也是按时完工的 二加权总误工和目标函数的修正 对于问题l i p - b a t c h ；b d j ， ( 撕一嘶) 噩+ d j w , a i ，t = 也 显然在1 0 ，副上是非减的，满足定义1 中的条件( 4 ) 因此只需满足引理1 中 的条件，通过适当的修正，t 吩乃就为一个有序的目标函数，这为后面的研究 提供了保证 3 2动态规划算法 一，有序目标函数的性质 对满足引理1 的目标函数e ”j t j 经过修正已为一个有序的目标函数下面 将论证这样的目标函数所具有的性质 1 优势性质 首先引入下面的定义 定义3 对于个排序”，如果没有任何排序以使得g ( 盯) q ( ”) ，即对任何 排序1 7 有：g ( 一) q ( ”) ，则称丌为一个主动排序 正象我们上一章讨论的那样，对于平行批排序问题，主动排序是具有优势 性的参照【5 】 1 9 】我们可以假设平行批工件在下面的时间集合p 中的任一时 间上开工或完工： p = r j + 印，j 1 ，n ，z o ，n ， 注意： i p i = o ( n 2 ) 2 有序目标函数的性质 定理1 对于问题l i p - b a t c h ；6 弼吩；乃= p l e ”j t j ，当奶乃修正为有序的目 标函数时，对于任何一对分别在k ，气开始成批力n - r _ 的按时完工工件厶，五( t ，) ， 一定有t n s t v 或t 。 h 证明：设( 鸲”) 是按字典序且不满足定理结论的最小下标向量，即缸 如并且如此时将这两个工件进行交换，其余工件不动由于 乃为有序的目标函数，交换后 帆z + 魄瓦+ 咒， 即 t 氏m a x 0 ，t 。+ p d t l + t 如m a x 0 ，t 。+ p 一磊 m a x o ，t 。+ p 一也 + 7 3 t t m a x 0 ，“- i - p d l ， 2 1 j 屿z s 嘶乃， 即目标函数值没有增加表明在假设条件下，可行排序可以转变成更好的一个 可行排序，且满足t 。s t 。，或t 。 ( ”) 可重复上述过程，直到将所有不满足结论的工件都进行调整，使其都满 足t 。t 。，或者“ 凡此时产生的新排序目标函数值一定不会超过原来排序 的目标函数值注意，我们每调整一步，向量( ”，”) 的下标是增加的，因此这 种调整交换的过程是有限次的故也是可行的 综合上面的讨论，我们可以看到排序问题l i p - b a t c h ，b mq ，乃= p l 屿乃 有二个优势性质： ( 1 ) 开工或完工时间属于集合尹 ( 2 ) 对于任何一对分别在屯，“处开始成批加工的按时完工工件凡，五 ”) ， 一定具有t u t 。或“ 这表明当五，山都到达可以加工时，一定是下标小 的先于下标大的工件先加工或是同时加工，否则下标小的工件就还没有到达 在下面的讨论中我们称这样的排序为平行优势( p a r a l l e l - d o m i n a n t ) 排序 二问题l l p - b a t c h ，6 勺，办= p l 乃的动态规划 1 基本概念与记号 设每批的容量为6 ，即每批至多有b 个工件可成批加工我们的动态规划递 推公式依赖于部分批的概念在一个部分批中，允许有一些洞，这些洞是可以 事先安排一些工律来进行加工的。我们将每个部分批实际进行加工的工件数记 为p ，每批最多可加工b n 个工件工件集u k ( t + ，t r ) 表示那些下标不超过七且 到达时间在区间( t z ，t ，l 的工件集合即 巩( l ，0 ) = 乃防七，r j ( t t ，0 】) 2 动态规划变量 动态搜索由四个参数kt 。，“及胁来确定，这些参数的任意组合就定义了 关于巩( 如，t ，) 中工件的子排序问题其目标函数值是在一定的约束条件下，使 山。( 饥f r ) 嘶乃达到最小化 2 2 定义4 一个排序口对于子问题( k ，t t ，t ，p ，) 是平行优势( p a r a l l e l - d o m i n a n t ) 排序当且仅当 ( 1 ) ”本身是一个平行优势排序 ( 2 ) v k ( t l ，t ，) 中的工件在山+ p 前不会开工，即在t l 处对于仉( t l t ，) 只是个 虚拟的批次 ( 3 ) 砜( f “0 ) 中的工件可能是误工的，也可能是在4 - p 之前或“+ p 处完 工 ( 4 ) 在一个部分批中，含有脚个v k ( t j ，o ) 中的工件，在。处开始且在f r + p 处完工 现在我们定义动态规划变量 定义5p k ( t t ：0 ，胁) 是由目标函数0 。“。j q 乃关于子排序问题( 奄，靠，0 ，芦，) 在所有的p a r a l l e l - d o m i n a n t 排序上取得的最小值如果没有这样的排序，则 最( 屯0 ，脚) = + 初始值： 碱k 小嘉“ 下面分析动态规划的递归过程设 娠0 ) = j j l js 七，吩，纠，有下 列几种情形： 情形1 如果以酞( 赴，o ) 是误工工件，此时我们只需考虑子问题( k 一 1 ，如，r ， - ) 的最优值及以的误工成本即可因为误工工件我们可以任意的向后 排 情形2 如果靠魄( 幻，t ，)