（运筹学与控制论专业论文）两类平行机分批排序问题.pdf

两类平行机分批排序问题 摘要 排序问题是一类重要的组合最优化问题本文首先介绍了排序问题的定义 和分类，然后对分批排序问题进行了讨论分批排序是现代排序模型之一，有着 很强的应用背景在这一排序模型中，若干个工件可以放在一批中同时加工，工 件在加工过程中不允许中断。也不允许移走正在加工的工件，同批工件的完工时 间均等于该批中最后工件的完工时间分批排序模型按照分批方式的不同可以 分成两类：并行分批排序模型和串行分批排序模型在并行分批排序模型中，机 器在每一时刻可以加工多个工件，在串行分批排序模型中，机器在每一时刻最多 只能加工一个工件，工件按一个接一个的串联方式形成一批 本文首先介绍了分批排序问题的分类及其研究成果，然后分别对两类平行 机的并行分批与串行分批排序问题进行了讨论第二章分别讨论了容量无限与 容量有限的平行机并行分批排序问题第一种同型批处理机，容量为无限，目标 函数是极小化完工时间和，本文给出了动态规划算法，并将结论进一步推广至同 类批处理机第二种同类批处理，容量为有限，目标函数是极小化加权总完工时 间，对其两种特殊情况：( 1 ) 所有工件加工时间相等，( 2 ) 所有工件权重相等，分别 给出了最优算法和启发式算法第三章讨论了容量相等的平行机串行分批排序 问题对目标函数是极小化加权总完工时间的两绅特殊情况：( 1 ) 所有工件权重 相等，( 2 ) 所有工件加工时间相等，分别给出了最优算法第四章总结了全文，并 提出未来的工作设想和努力的方向 关键词：排序，分批，平行机，加权总完工时间，动态规划 t w ok i n d so fb a t c hs c h e d u l i n go n p a r a l l e lm a c h i n e s a b s t r a c t s c h e d u l i n gp r o b l e mi s a l li m p o r t a n tc o m b i n a t i o no p t i m i z a t i o np r o b l e m t 1 l i s p a p e rf i r s ti n t r o d u c e dt h ed e f i n i t i o na n dt h ec l a s s i f i c a t i o no fs c h e d u l i n gp r o b l e m , t h e n d i s c u s s e db a t c hs c h e d u l i n g i tw a so n eo f t h em o d e ms c h e d u l i n gm o d e l s ，a n dh a sv e r y s t r o n ga p p l i c a t i o nb a c k g r o u n d i nt h i sn e ws c h e d u l i n gm o d e l ，an u m b e ro f j o b sa r e p r o c e s s e ds i m u l t a n e o u s l ya sab a t c h , n oj o bc a nb ea d d e dt oo rr e m o v e df r o mt h e m a c h i n eu n t i lt h ep r o c e s s i n go f t h eb a t c hi sc o m p l e t e d t h ep r o c e s s i n gt i m eo f ab a t c h i se q u a lt ot h el a t e s tp r o c e s s i n gt i m ea m o n ga l lj o b si nt h eb a t c h b a t c h - s c h e d u l i n g m o d e l sg oi n t ot w oc a t e g o r i e sb yt h ew a yo fb a t c h i n g ：p a r a l l e l b a t c hs c h e d u l i n ga n d s e r i a l - b a t c hs c h e d u l i n g 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 gm o d e l ，t h em a c h i n ec a n h a n d l em o r et h a no n ej o ba tat i m e ，w h i l ef o r t h es e r i a lb a t c hs c h e d u l i n gm o d e l ，i tg a l l h a n d l ea tm o s to n ej o ba tt h es a m em o m e n ts ot h a tt h ej o b si nab a t c hm u s tb e p r o c e s s e do n eb yo n ei nas e r i a lo r d e r f i r s tw ei n t r o d u c e dt h ec l a s s i f i c a t i a n dr e s e a r c hr e s u l t so fb a t c hs c h e d u l i n g p r o b l e m , t h e n d i s c u s s e ds e p a r a t e l yp a r a l l e lb a t c hs c h e d u l i n gp r o b l e ma n ds e r i a lb a t c h s c h e d u l i n gp r o b l e mo nt w ok i n d sp a r a l l e lm a c h i n e i nc h a p t e r2w cs e p a r a t e l y d i s c u s s e dp a r a l l e lb a t c hs c h e d u l i n gp r o b l e mo np a r a l l e lm a c h i n e sw i t hl i m i t e da n d i n f m i t ec a p a c i t y f i r s t ，f o ri d e n t i c a lp a r a l l e lm a c h i n ew i t hi n f i n i t ec a p a c i t ya n d o b j e c t i v e i st om i n i m i z et h et o t a l c o m p l e t i o nt i m e s ，w ep r e s e n tad y n a m i c p r o g r a m m i n ga l g o r i t h ma n dt h ec o n c l u s i o nw i l lb ef u r t h e re x t e n d e dt os i t u a t i o no f u n i f o r mm a c h i n e s s e c o n df o ru n i f o r mm a c h i n ew i t hl i m i t e dc a p a c i t ya n dt h e o b j e c t i v ei st om i n i m i z et h et o t a lw e i 曲t c dc o m p l e t i o nt i m e ，w es e p a r a t e l yp r o v i d e o p t i m a la n dh e u r i s t i ca l g o r i t h mf o rt h ef o l l o w i n gt w os p e c i a lc a s e s ：( 1 ) a l lt h ej o b s h a v et h es a m ep r o c e s s i n gt i m e ( 2 ) a l lt h ej o b sh a v et h es a m ew e i g h t i nc h a p t e r3 ， w ec o n s i d e rt h es e r i a lb a t c h i n gs c h e d u l i n gp r o b l e mo np a r a l l e lm a c h i n e st om i n i m i z e t o t a lw e i g h t e dc o m p l e t i o nt i m e 、i t l lt h er e s t r i c t i o nt h a te a c hb a t c hc o n t a i n se q u a lj o b s w eg i v ea l g o r i t h mf o rt h ef o l l o w i n gt w os p e c i a lc a s e s ：( 1 ) 舢lt h ej o b sh a v et h es a m e w e i g h t ( 2 ) a l lt h ej o b sh a v et h es a m ep r o c e s s i n gt i m e i nc h a p t e r4 ，t h ew h o l e d i s s e r t a t i o ni ss u m m a r i z e d r e s e a r c hw o r ki nt h ef u t u r ei sp o i n t e do u t k e y w o r d s ：s c h e d u l i n g b a t c h i n g ，p a r a l l e lm a c h i n e s ，t o t a l w e i g h t e dc o m p l e t e dt i m e ，d y n a m i cp r o g r a m m i n g 甄类平行机分批排序问题 第一章引言 排序论作为运筹学的一个分支，有着深刻的实际背景和广阔的应用前景， 排序论一直受到国际学术界的重视排序问题产生的背景主要是机器制造，后 来被广泛应用于农业、制造业、运输业、管理计算机科学等领域排序理论的研 究是从二十世纪五十年代初期开始的由于研究排序问题的方法涉及组合最优 化的各个分支，如线性规划，整数规划，动态规划，计算复杂性理论等，因此 自从它创立以来就得到运筹学、信息管理、计算机科学等学科领域的普遍重视 特别是新型排序的丰硕结果，使排序论已成为研究活跃、前景诱人的学科领域之 排序分为经典排序和新型排序新型排序是相对经典排序而言，也就是非 经典的排序新型排序的特征是突破了经典排序关于资源类型，确定性，可运 算性，单目标和正则性等基本假设，主要有可控排序，在线排序，分批排序， 准时排序，窗时排序，不同时开工排序，资源受限排序，随机排序，模糊排序， 多目标排序等本文主要研究分批排序问题 一、排序问题的定义 排序问题是一类重要的组合最优化问题，它是利用一些处理机( p r o c e s s o r ) 、 机器( m a c h i n e ) 或资源( r e s o u r c e ) ，最优的完成一批给定的任务( t a s k ) 或作业 ( j o b ) 在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完 工的限定时间、任务的加工顺序、资源对加工时间的影响等最优的完成指的是 使目标函数达到最小，而目标函数通常是对加工时间长短、处理机的利用率的描 述 在排序问题中，由于处理机的数量和种类，任务和作业的顺序、到达时间、 完工限制、资源的种类和性能等情况是错综复杂的，为此我们常常用到如下的基 本参数： 设有万个工件，记为以，以，以；有小台机器，记为m ，鸠，帆 “( 或p ，) ( p r o c e s s i n gt i m e ) 表示工件，在机器m 上的加工时间( 简称工时 当如= p ，时，说明工件的加工时间与选择的机器无关或所研究的问题是单机问 题 ，( r e l e a s ed a t e ) 表示工件j 的准备( 到达) 时间 d ，( d u ed a t e ) 表示工件，的交工期如果工件在它的交工期之前完成，我 们称之为按期完工的工件( o n - t i m e j o b ) ；否则，我们称之为误工的工件( t a r d y j o b ) 两类平行机分批排序问厦 对误工的工件有时需要一定的罚值 w ，( w e i g h t ) 表示工件j ，的权重 c ，( c o m p l e t i o nt i m e ) 表示工件j 的完工时间 l ，= c ，一d ，( 1 a t e n e s s ) 表示工件i ，的延迟 乃= m 戤 9 ，c ，一d ，j ( t a r d i n e s s ) 表示工件j ，的误时 e f = m a x o ，d ，一c j ( e a r l i n e s s ) 表示工件t ，f 的提前完工时间 通常我们规定： ( 1 ) 任务或作业和处理机是有限的； ( 2 ) 工件一旦开始加工，则一直加- r n 完毕( 除非有允许中断的声明) ( 3 ) 每个工件必须在它的到达时间之后加工 二、排序问题的分类 目前文献通常采用三参数分类法，即口l p l r ，它们具有下边的含义 口域表示处理机的数量、类型和环境，它可以是 口= l ( s i n g l em a c h i n e ) ：单处理机 口= 己( i d e n t i c a lm a c h i n e si np a r a l l e l ) ：r a 台同速机 口= 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 ) ：m 台恒速机 口= 疋( 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 台变速机 口= e ( f l o ws h o p ) ：m 台处理机，流水作业 口= d 用( o p e n j o b ) ：m 台处理机，自由作业 口= 厶( j o bs h o p ) ：m 台处理机，异序作业 域表示工件的性质、加工要求和限制，它可以是 = ，工件有不同的准备时间( 到达时间) = j ，工件有不同的安装时间 = b a t c h 表示工件是分批进行加工的分批排序模型按分批方式的不同分 两大类：串行分批和并行分批 在串行分批模型( s - b a t c h ) 中，机器在每一时刻只能加工一个工件，工件是 按照一个接一个串联的方式形成批，同批的工件完工时间为该批最后工件的 完工时间，批的加工时间定义为该批中所有工件加工时间之和：在并行分批模 型( p b a t c h ) 中，机器在每一时刻可同时加工多个工件，同批的工件完工时间相 同，批的加工时间定义为该批中所有工件加工时间最长者 ，域表示要优化的目标函数，它可以是 ，= c 二：时间表 2 两类平行机分批捧序问题 ，= c ，：总完m 时间 y = 一q ：加权总完工时间 ，= k ：最大延迟 ，= u ：延误工件总数 ，= w j ：加权延误工件总数 ，= 正：延误工时总和 三、分批排序问题 经典的排序是假设机器任何时候只能加工一个工件，但在实际生活中有的 “机器”可以同时加工多个。工件”这类机器可以同时加工多个工件的排序问 题称为分批排序问题或称为批加工机器排序( s c h e d u l i n ga b a t c h i n gm a c h i n e ) 分 批排序与经典排序问题的不同就在于若干个工件可以在一批中同时加工工件 加工过程中不允许中断也不允许移走正在加工的工件如何对工件进行分批是 问题的关键，确定了工件的一个分批后就可把一批看作一个工件来寻找其最优 算法或近似算法由此可见，分批排序是经典排序的推广，打破了经典排序的机 器在同一时间只能处理一个工件的约束，从而其难度不低于经典的排序问题 分批排序是兴起于9 0 年代初的一类应用背景极强的优化问题主要产生于 大规模的现代化生产流水作业线如：半导体生产，航空工业，钢铁铸造甚至制鞋 业，其中半导体生产流水作业线，确切来说，集成电路芯片生产流水作业线是被 研究和应用最广泛，最深刻的一个领域集成电路芯片的生产分为四个阶段：芯 片生产( w a f e rf a b r i c a t i o n ) ，芯片探测( w a f e rp r o b e ) ，装配( a s s e m b l y ) 及最后的测 试( f m a lt e s t i n g ) ，每一个阶段都有分批排序的应用 分批排序按照批处理机的类型主要可以分成两类：( 1 ) 每批的加工时间是这 批工件中所有加工时间的最大者，被称为并行分批排序( p a r a l l e l b a t c h ) ；( 2 ) 每批 的加工时间是这批工件中所有加工时间的和，被称为串行分批排序( s e r i a lb a t c h ) 并行分批排序 本文所介绍的并行分批排序模型p - b a t e h , 亦即所谓的b u r n i nm o d e l ，它来 源于集成电路芯片的生产测试过程在芯片测试时，其中一个过程是将芯片放入 烤箱烘烤每个芯片都有一个预定的烘烤时间，经受住这段时间烘烤的芯片被视 作合格产品烤箱有一个固定的容积b 烘烤过程是不允许被打断的每个芯片 预定的烘烤时间可能是不同的，为了保证产品质量，同一烤箱内芯片的实际烘烤 时间为其中预定时间最长的 模型p - b a t c h 研究的意义： 两类平行机分批排序问题 由于相对于其它过程来说，烘烤的用时是很长的( 大约1 2 0 ：5 ) ，成为芯片生产 的一个瓶颈随着半导体工业的飞速发展以及竞争的不断加剧，如何有效地利用 ( 厂家和顾客的) 时间这一宝贵资源显得越发重要，因而用组合优化的工具来研究 此问题是很有意义的 串行分批排序 串行分批排序仍是将工件分成若干批，每批放在一起一个一个的相继加工 机器在每一时刻只能加工一个工件，一旦某批工件形成以后。均有一个独立的安 装时间( 准备时n ) s ，在此时间段中不能加工任何工件，这里假定每批的安装时间 都相同 串行分批排序也具有广泛的应用背景例如在医院的x 诊室经常会看到这 样的情况：病人在外排队候诊，一组病人被医生一起领进诊室，在一台机器上依 次检查，结束后再一起出诊室，然后下一组病人再进去这就是典型的日常生 活中串行分批排序问题 四、分批排序问题的研究现状 分批排序问题是重要的现代排序模型之一，目前在文献中受到了普遍的关 注，文献【1 】被认为是较早研究分批排序问题的文章，b r u c k e r 2 和l e e 3 1 也对此 问题进行了研究自9 0 年代初以来，特别是最近几年，由于其深刻的应用背景， 分批问题受到了广泛的关注，新的研究成果不断涌现 并行分批排序可分为容量无限制的模型和容量有限制的模型两类，由三参 数法模型可记为l i p b a t c h ，b 甩l 厂，l i p b a t c h ，b n l f 对容量无限制的情形， b r u c k e r 2 综述了若干结果关于这方面的研究可以查阅书【4 】，另外，对单机目 标函数是极小化最大完工时间的情况，b r u c k e r 2 将其算法的时间复杂性改进为 m i n o ( n l o g n ) ，o ( h 2 肛) ，张玉忠 5 1 证n 了其最优性，对于有到达时间的情况 l i p b a t c h ，b n ，l c 二，l i u 6 对只有两个到达时间的情形用二划分问题证明了 其 r p 完备性l e e 7 等给出了拟多项式时间的动态规划算法，d e n g 8 对b 为常 数的情形给出了p t a s 算法，并最终解决了该问题张玉忠，邹娟 9 1 k 5 进一步研 究了带有优先约束的情况1 1 p - b a t c h ，p r e c ，b 厅1 1 b r u c k e r 2 】等对问题 l i p b a t c h ，b 聍i c ，给出了复杂性为d 控州“”) 的动态规划算法。d e n g 1 0 ；乖j l i p b a t c h ，b ”，r 罗，有到达时间的情况给出了算法，并且证明当和, i cp t a sb ，为常数时问题是多项式可解的对平行机的情形，l e e 1 l 】对 最i p b a t c h ，b n l c 二给出了b l s 和b l p t 算法，其性能比分别为b + i - l m 和 4 3 - 1 3 m 对问题己l p - b a t c h ，b n ，乃= p i 一q 苗翠霞【1 2 】给出了最优算法 两类平行机分批捧序问题 文献 1 3 1 对如i p - b a t c h ，b n i c m 给出了4 - 2 b 的近似算法，当b 是常数且加 工时间一致时文献【1 4 】对凡l p - b a t c h ，b 甩，_ i c 眦给出了p t a s 算法文献 【1 5 1 7 x , 1 有到达时间约束的并行分批排序问题的复杂性进行了研究 串行分批排序可分为容量无限制的模型和容量有限制的模型两类，由三参 数法模型可记为1 i s b a t c h f ，1 i s b a t c h ，b - ”l q 问题的总完工时间是所台批处理机各自的总完工时间的和， 设排序盯= 懈，口：，髟，曰：j 是第，台批处理机上的一个最优排序，其中 l p p j 我们把从批，b ：移动到批彰 得到另一个排序一= 斜，b ：u p ， 嘭、p ， ，b ，) ，因为p i p ，所以批 b ：的加工时间为p 啤u 阢) ) = p ( 8 ；) ，并且p 、p ， ) p ) 工件的完工 时间从c 喊) 减少为c 恤：j ，而其他工件的完工时间没有增加因此对于正则的 目标函数，排序a 7 也是最优的重复上述移动过程，可以得到每台批处理机上 吲，趔，b t , 是即r 序 下面根据引理2 构造动态规划算法设工件按卵r 序编号，在动态规划算法 中包含连续编号工件的批，按后退法在各处理机上排序设当前批处理机，上已 包含x 个工件，若把包含工件工，k 一1 的批放在该序列的开始，那么总完工时间 增加啊p ，其中一= x + k 一，是批处理机，上的工件数总完工时间的增加与批 处理机，上的工件数和新增批的加工时间有关用f o l ，一，刀。) 表示u ，刀) 被排 序时的总完工时间，其中z t _ - 。珥= n - j + l ，动态规划算法如下： 算法1 s t e pl ( 初始) 将各工件按s p t 重新编号，即p 。p 2 s p 。，令 e + ( o ，o ) = 0 ，当( ，玎l ，一，) 0 + l ，o ，0 ) 时，令0 1 ，) = 0 0 置 _ ，= 疗 s t e p2 ( 递归) 对每个满足啊 0 ，1 ，即一j + 1 ，= 1 ，m ，且 ：。啊= 万一_ ，+ 1 的数组“，； ，y l m )、 计算g 1 ，”，) = m i n e0 1 ，一，啊一 一办，) + 啊p 。，= 1 ，m 如果一0 1 ，) ：以( ：i ：冀：_ 一 一a ，) + 力，p 。，那么把包含i 件 o ，k 一1 ) 的批放到处理机j 序列的开始被加工，如果，= 1 ，转s t e p 3 ；否则令 _ ，= ，一1 ，重复s t e p 2 s t e p3 ，= i l l i i i e “，) l m 0 , 1 ，n ) ，= 1 ，所，：。啊= ，然后用 后退法找到相应的最侥解 在第二步迭代，不同多元组至多o o 一，+ 2 ) ”1 ，递归方程需计算 o ( m ( n - j + 1 ) ) ，所以算法的复杂性为o ( 二埘( n 一，+ 2 ) ”( n 一，+ 1 ) ) ，等价于 o ( m n ”1 ) 特别地，若m = 2 ，复杂性为o ( n 3 ) ；若m = 3 ，复杂性为d ( ，1 4 ) ( 四) 同类批处理机问题 设处理机的速度为丑，( f = 1 ，m ) ， 定理2 对于q i p 一6 口纪 ，b 行l q 问题存在一个最优排序，满足下列两 两类平行机分批排序问题 个性质 ( 1 ) 把工件按卵丁序编号，使p 1 p 2s 见，每批工件的编号是连续的 ( 2 ) 每台批处理机上协- 噬，西j 是即z 序，即j d ( 纠) s p ( 趔) s p ( 或) 证明与己l p - b a t c h ，8 - i z c _ ，类似 其动态规划算法与同型批处理机的动态规划算法类似首先将工件按s p t 序编号在动态规划算法中包含连续编号的工件的批，按后退法在各处理机上排 序假设当前批处理机，上已包含z 个工件，若把包含工件，七一1 的批放到该 批处理机的序列的开始那么总完工时间增加啊见一。偈，其中啊= x + k - 是批 处理机，上的工件数吼是批处理机z 上的速度总完工时间的增加与批处理机， 上的工件数，速度及新增批的加工时间有关用一h ，刀。) 表示o ，1 ) 被排 序时的总完工时间，其中e t 。n t = n - j + l ，动态规划算法如下： 算法2 s t e p1 ( 初始) 将各工件按驴丁重新编号，即p p 2 p 。令 只+ 。( o ，o ) = 0 ，当( ，n a ，n ，) o + 1 ，o ，0 ) 时，令e 0 1 ，一，) = o o 置 _ ，= 疗， s t e p2 ( 递归) 对每个数组h ，) 满足竹， o ”1 一，疗一，+ 1 ，= l , - - , m ， 且：。吩= n - j + l ， ，、 计算( 一，n ) = m i n e ( 惕，坼一( 七一，) ，) + 啊仇一 ，l = l ，研 如果( 啊，) = e ( 拶姑一( i 一，) ，) + 研既一一，那么批o ，七j 1 ) 被 排在处理机，上序列的开始加工，如果_ ，= 1 ，转s t e p 3 ；否则令_ ，= ，一1 ，重复 s t e p 2 ，、 s t e p3f = m i l l e ( 玛，) i 吩 0 , 1 ，疗 ，1 = l ，册，z t 。啊= h ，然后 用后退法找到相应的蛊优解 。 算法的复杂性为d b 疗“) 例求解问题q 2 i p - b a t c h ，曰竹i q ，其中一= 4 ，m = 2 ，即设有工件 ，以，以，以 ，各工件的加工时间为p ，= 3 ，p 2 = 4 ，p 3 = 5 ，p 4 = 9 两台批处 理机的速度分别为j 。= i ，j ：= 2 ，如何进行分批排序使总完工时间最小 解： 当j = 4 时，啊 0 ，l ，= l ，2 ，2 i 。啊= 1 e ( 0 , 1 ) = r a i n f ，( o ，o ) + p 4 1 s ： _ 4 5 ； e ( 1 ，0 ) = m i i l e ( o ，o ) + n = 9 ； 当，= 3 时，啊 o ，1 ，2 ) ，= 1 ，2 ，：，坼= 2 e ( o ，2 ) = m i i l 只( o ，1 ) + 2 岛屯；e ( o , o ) + 2 p 。屯) = r a i n 9 5 ；9 ； e ( 1 ，1 ) = m i i l 只( o ，1 ) + 岛 ；( 1 ，o ) + 见是 = m i n 9 5 ；1 1 5 = 9 5 9 两类平行机分批律序问履 e ( 2 ，o ) = m i n 五o o ) + 2 见 ；e ( o ，o ) + 2 p j s l ) = m i n 1 9 ；1 8 = 1 8 ； 当，= 2 时， ， o 123 ，= l ，2 ，二啊= 3 f 2 ( 0 , 3 ) = m i l l e ( o ，2 ) + 3 p 2 s 2 ；只( o ，1 ) + 3 办而；e ( o , o ) + 3 p 4 s 2 - - r a i n 1 5 ；1 2 ；1 3 5 = 1 2 f 2 ( 1 ，2 ) = m i n e ( o ，2 ) + p 2 s 1 ；f 3 ( i ，1 ) + 2 p 2 h ；f 4 ( 1 ，o ) + 2 p 3 s 2 = m i n 1 3 ；1 3 5 ；1 4 ) = 1 3 f 2 ( 2 ，1 ) = m i n f 3 ( 1 ，1 ) + 2 p 2 s i ；只( o , 1 ) + 2 p 3 s i ；f 3 ( 2 ，o ) + p 2 s 2 = m i n 1 7 5 ；1 4 5 ；2 0 ) = 1 4 5 f 2 ( 3 ，0 ) = r m g ( 2 ，o ) + 3 p 2 s , ；f 4 ( 1 ，o ) + 3 p 3 s , ；e ( o ，o ) + 3 p 4 s i = r a i n 3 0 ；2 4 ；2 7 ) = 2 4 当，= 1 时，? i t o ，1 ，2 , 3 ，4 ) ，= l ，2 ，乙啊= 4 e ( o ，4 ) = m i n f 2 ( 0 ，3 ) + 4 p i s 2 ；e ( o ，2 ) + 4 p 2 s 2 ；f 4 ( 0 ，1 ) + 4 p , h ；f ，( 0 ，o ) + 4 p 4 s 2 = m i n 1 8 ；1 7 ；1 4 5 ；1 8 = 1 4 5 e ( 1 ，3 ) = m m e ( o ，3 ) + a ；最( 1 ，2 ) + 3 p l s 2 ；f 3 ( 1 ，1 ) + 3 p 2 s 2 ；f 4 ( 1 ，o ) + 3 p 3 s 2 - - m i n 1 5 ；1 7 5 ；1 5 5 ；1 6 5 = 1 5 f 1 ( 2 ，2 ) = r a i n f 2 ( 1 ，2 ) + 2 p , s l ；e ( o ，2 ) + 2 p 2 s , ；f 2 ( 2 ，1 ) + 2 p , s 2 ；e ( 2 ，o ) + 2 p 2 s 2 = m i n 1 9 ；1 7 ；1 7 5 ；2 2 = 1 7 五( 3 ，1 ) = r a i n f 2 ( 2 , 1 ) + 3 p , s l ；f 3 ( 1 ，1 ) + 3 p 2 s , ；f 4 ( 0 ，1 ) + 3 p 3 s , ；f 2 ( 3 ，o ) + a 属 = r a i n 2 3 5 ；2 1 5 ；1 9 5 ；2 5 5 l = 1 9 5 e ( 4 , 0 ) = r a i n f 2 ( 3 ，o ) + 4 p , s 1 ；f 3 ( 2 ，o ) + 4 p 2 s , ；f 4 ( 1 ，o ) + 4 p 3 s 1 ；f 5 ( 0 ，o ) + 4 p j s , - - - m i n 3 6 ；3 4 ；2 9 ；3 6 = 2 9 最优值，= e ( o ，4 ) = 1 4 5 用后退法找到相应最优解：第二台批处理机砰= ，以，以 ，霹= 以) 其中各工件的完工时间分别为c 1 = g = c 3 = 2 5 ，c 4 = 7 1 0 两类平行机分批排序问题 二、同类批处理机的容量有限极小化加权总完工时间问题 ( 一) 引言 目前关于分批排序的研究多数集中于单批处理机，而关于同类批处理机的 研究并不多见【3 2 对同类机分批排序问题进行了研究，得到了有趣的“转换引 理”【1 2 】对单机和平行机极小化加权总完工时间问题的特殊情况进行了研究 本文对于目标函数为加权总完工时间且工件在同类批处理机上加工的特殊情况 进行了研究 前人已经证明了q 20 m q 的n p 完备性，而由【3 2 】易知q 2 l 口 h i 叶q 也是n p 完备，因此对任意台处理机的情况绒l b h i 叶q ，易推其胛完备 性本文对于目标函数为加权总完工时间的同类机并行分批排序问题的两种特 殊情况进行了研究：( 1 ) 所有工件加工时间都相等，( 2 ) 所有工件权重都相等，分 别给出了最优算法和启发式算法 ( 二) 问题描述 设一个工件的集合为“，j 2 ，以 ，每个工件，的加工时间p j ，权重w ， 埘台批处理机的集合 m l ，肘2 ，m 。) ，机器m 的速度是墨( i = l ，2 ，m ) ，若 各处理机的速度相同，即 = 屯一= ，则称为同型批处理机；否则称为同类 批处理机假设每台批处理机至多可同时加工b 个工件且b ，即处理机的容 量是有限的 本文所讨论的问题，若用三参数表示法。可以表示为 g i p b a t c h ，b 拧，马= p l e w j c j ( 1 ) 绋i p b a t c h ，b 拧1 e ( 2 ) ( 三) 工件加工时间相等的情况 ( 1 ) 对问题g i p - b a t c h , b n , p j = p l z w , c , 存在最优算法 在设计其算法之前。若假设批处理机每次至多只能加工1 个工件即b = 1 ，则 问题变成经典的同类机排序问题绋l 乃= p l _ q ，存在最优算法如下： 算法1 s t e p1 将工件按权重不增的顺序重新编号w 2 两类平行机分批捧序问卮 s t e p2 趴i a ，2 s , ，n 随，1 l s 2 ，2 | s z ，n | s 2 ，l | s 。2 | s ，n s m 中取出n 个较小的数，按不减排列 s t e p3 经过( 1 ) ( 2 ) 两步，o ) e e - r 件权重与( 2 ) 中的数形成1 一l 对应，若w ，对 应s 。，则工件，在处理机m 的第j | 个位置上加工 定理1 算法1 是求解绋l 乃= p l z w ；, 问题的最优算法 证明由于加权平均流时间问题与加权总完工时间问题可以相互转化，为了 方便，下边是对平均流问题加以讨论由于流时间与处理机速度有关，在处理机 m 。的第七个位置加工的任务耻1 的加权流时间定义为z = ：。p , s , ，由于 尼= p ，所以五q = 。】印一设处理机m ，上有个任务，则n = ：二l 啊，因此 加权平均流为r = ：。：，兰吐s t = 生ny l = = , i “i = ：q k e t - n = e ：= 。啊，上式是疗项之和，每一项都是加工时间与下列系数中某数 的乘积1 而，2 ，n i s l ，1 是，2 屯，性是，l ，2 ，n i s 上述乘积的极小值，可以通过以下规则得到，把疗个系数按不减排列，权重 按不增排列，对应相乘即可得到 证毕 因此，利用算法1 对绒i p - b a t c h ，b n ，p s = p l 一q 问题可以得到算法2 如下： 算法2 s t e pl 将工作按权重不增重新编号嵋w 2 2 s t e p2 取前b 个工件作为第一批且，次四个工件作为第二批岛，依次下去， 除最后一批以可能不满外，其它各批均是满的 s t 印3 把每一批看作是一个工件，利用求解q 肘l p ，= p l z w , q 的算法1 将各 批工件依次分配到各同类机上 定理2 算法2 能最优的解决q 肿l p 一6 口把厅，b w r ，存在两批b j ，b ，不妨设，eb j ，j j 最及 j f b s 下面分( 1 ) ( 2 ) ( 3 ) 三种情况讨论： ( 1 ) 若批b j 先于批b j 加工，则可将以与，r 作交换，即将- ，与以同放在批曰， 中，将，放在批b j 中，其它工件不动； 1 2 两类平行机分批排序阔厦 ( 2 ) 若批b t 先于批b j 加工，则可将以与，作交换，即将，与以同放在批 b ，中，将，放在马中，其它工件不动； ( 3 ) 若批曰，与批骂同时完工，则可将工件正与j f 交换或山与交换，其它 工件不动，则总目标函数值不变 设工件以o = f ，j ，厂) 在开始的排序与调整后的排序