（计算机软件与理论专业论文）若干批调度问题的算法研究.pdf

， 0 - k 7 j j 扫 原创性声明和关于论文使用授权的说明 原创性声明 i l l lliii i ii ii i ii iiiiil y 1 7 913 5 5 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：弛孝乓皂二 日 j 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 令弋 一 一 k 7 f f 喁 山东大学硕士学位论文 目录 摘要i a b s t r a c t 1 1 1 第l 章绪论1 1 1 应用背景及问题描述l 1 2 研究现状2 1 3 1 4 1 5 第2 章 2 1 2 2 2 3 2 4 2 5 第3 章 3 1 3 2 1 2 1 最小化最大完成时间2 1 2 2 最小化( 加权) 完成时间之和3 1 2 3 工件可拒绝4 1 2 4 工件有尺寸4 1 2 5 智能算法5 研究方法5 研究成果6 论文的组织结构6 近似算法研究7 预备工作7 具有相同到达时间g p 问题的2 近似算法8 2 2 1 具有相同到达时间s p 问题的多项式时间算法8 2 2 22 。近似算法1 0 g p 问题的4 近似算法1 0 g p 问题的2 + f 近似算法l l 2 4 1具有k 个到达时间s p 问题的拟多项式时间算法1 l 2 4 2 s p 问题的多项式时间近似方案一1 5 2 4 32 + e - 近似算法1 5 本章小结1 6 遗传算法研究1 7 简介1 7 b m f 问题的遗传算法1 8 3 2 1 初始种群1 8 3 2 2 编码与解码1 8 3 2 3 选择2 0 山东大学硕士学位论文 3 2 4 交叉2 l 3 2 5 变异2 3 3 2 6 整体算法2 4 3 2 7 程序设计2 5 3 2 8 实验结果2 5 3 3s b s 问题的遗传算法2 8 3 3 1解码2 8 3 3 2 交叉3 1 3 3 3 整体算法3 3 3 3 4 实验结果3 3 3 3 5 结果分析3 5 3 4 本章小结。3 6 第4 章总结与展望3 7 参考文献3 8 致谢4 4 攻读硕士期间发表的学术论文目录4 5 攻读硕士学位期间参与的项目4 6 q t v j 一 f - l 簟 - l 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h 一 c h a p t e r1 p r e f a c e 1 1 1 b a c k g r o t m d sa n dd e s c r i p t i o no f t h ep r o b l e m s 1 1 2 b a c k g r o u n d so f t h er e s e a r c h 2 1 2 1m i n i m i z et h em a k e s p a n 2 1 2 2m i n i m i z et h es u mo f ( w e i g h t e d ) c o m p l e t et i m e 3 1 2 3 r e j e c t i o n 。，。4 1 2 4j o bs i z e z i 1 2 5 i n t e l l i g e n ta l g o r i t h m s 5 1 3t h em e t h o d so f t h er e s e a r c h ， 5 1 4o d ra c h i e v e m e n t s 6 1 5t h eo r g a n i z a t i o n so f t h et h e s i s 6 c h a p t e r2a p p r o x i m a t i o na l g o r i t h m s 7 2 1p r e l i m i n a r i e s 7 2 2a 2 - a p p r o x i m a t i o na l g o r i t h mf o rg p w i t hi d e n t i c a lr e l e a s ed a t e s 8 2 2 1a p o l y n o m i a lt i m ea l g o r i t h mf o rs p 、析t l l i d e n t i c a lr e l e a s ed a t e s 8 2 2 2a 2 - a p p r o x i m a t i o na l g o r i t h m 1 0 2 3a 4 - a p p r o x i m a t i o na l g o r i t h mf o rg p 1 0 2 4a 2 + e - a p p r o x i m a t i o na l g o r i t h mf o rg p 1 1 2 4 1a p 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 mf o rs pw i t hkd i s t i n c tr e l e a s ed a t e s 1 1 2 4 2a p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e f o rs p 1 5 2 4 3a2 + e - a p p r o x i m a t i o na l g o r i t h m 1 5 2 5c o n c l u s i o n 1 6 c h a p t e r3 g e n e t i ca l g o r i t h m s 1 7 3 1i n t r o d u c t i o n 1 7 3 2g e n e t i ca l g o r i t h m sf o rb m fp r o b l e m 1 8 3 2 1i n i t i a lp o p u l a t i o n 18 u l 山东大学硕士学位论文 3 2 2 e n c o d i n ga n dd e c o d i n go f i n d i v i d u a l s 1 8 3 2 3s e l e c t i o n 2 0 3 2 4 c r o s s o v e r 2 1 3 2 5 m u t a t i o n 2 3 3 2 6f r a m e w o r ko fg e n e t i ca l g o r i t h m s 2 4 3 2 7 d e s i g no f t h ep r o g r a m 2 5 3 2 8 c o m p u t a t i o n a le x p e r i m e n t s 2 5 3 3g e n e t i ca l g o r i t h m sf o rs b sp r o b l e m 2 8 3 3 1 d e c o d i n go f i n d i v i d u a l s 2 8 3 3 2c r o s s o v e r 31 3 3 3f r a m e w o r ko fg e n e t i ca l g o r i t h m s 3 3 3 3 4 c o m p u t a t i o n a le x p e r i m e n t s 3 3 3 3 5 a n a l y s i so f t h er e s u l t s 3 5 3 4c o n c l u s i o n 3 6 c h a p t e r4 c o n c l u s i o n 3 7 r e f e r e n c e s 3 8 a c k n o w l e d g e m e n t 4 4 r e s u m e 4 5 p r o j e c t 4 6 k 、t 山东大学硕士学位论文 摘要 单机批调度问题是最近十几年广泛研究的一个领域。在本文之中，我们首先 针对给定n 个工件和一个容量为曰的单机并行批处理机器问题展开研究。每个工 件- ，f ( _ ( 1 ，2 ，1 ) ) 具有一些给定属性( r j ，p f ，s i z e f ，w i ) ，r j 是工件，厶基够被调 度的最早时间，即到达时间；p j 是工件，在不被打断情况下，需要在机器上处 理的时间，即处理时间；s i z e j 是工件，的尺寸；w j 是工件，在被拒绝情况下需 要在目标中付出的惩罚值。机器能够把一定数量的工件作为一批同时进行处理， 只要这批工件的尺寸总和不超过曰。一批的处理时间等于这批中工件的最大处理 时间。同一批处理的工件具有相同的起始时间和相同的完成时间。我们的目标是 调度这些工件，使得接受工件的最大完成时间与拒绝工件的惩罚总值之和最小。 我们首先给出了此类问题无论到达时间是否相同均是n p - 困难的，且不存在 近似比小于3 2 的近似算法；之后，我们给出了工件具有相同到达时间的情况的 2 近似算法；最后我们给出了工件可能具有不同到达时间的问题的2 + e - 近似算 法，其中 0 可以为任意小的常数。 另外，受实时机器视觉系统启发，我们对并行批混合流水车间最小化最大完 成时间的调度问题进行遗传算法的研究。此问题描述如下：工件集，中的n 个工 件需要被忌阶段的流水车间处理，其中每个阶段i ( f 1 ，2 ，忌 ) 有m f 个平行 批处理器。设鼠p 表示阶段f ( f 1 ，2 ，七) ) 的处理器p ( p 1 ，2 ，m i ) ) 的 容量。也就是说，在阶段f 的处理器p 至多同时处理磅。个工件。一批的处理时间 等于这批工件中的最大处理时间。我们可以把一个工件看成一个具有k 个任务的 序列，每个任务针对一个阶段，且任何任务必须在其前序任务处理完成之后才能 够被处理。设p f f 为工件，f ( ，j ) 在阶段f ( f 1 ，2 ，硒) 需要的处理时间。 我们对此问题有以下的假定：1 每个阶段的处理器只能处理此阶段的任务；2 同 一处理器在一个时刻只能处理一批。设c u ( s ) 为调度s 中工件- ，f ( ，j ) 的第 f ( f 1 ，2 ，材) 个任务的完成时间。我们问题的目标可以简化为找出最小化 m a x 肛， c f ( s ) 的调度s 。我们分别对交叉操作和变异操作给出两种不同的方法， 然后对这些方法的四种不同的组合方式进行实验。在此基础之上，我们还针对工 件具有尺寸和可以拒绝的最小化最大完成时间加惩罚总值之和的单机并行批调度 问题，给出一种新的解码方法和四个版本的遗传算法，最后得到一个版本的遗传 算法好于其他三个等实验结果。 山东大学硕士学位论文 关键词：批调度；遗传算法；到达时间；工件尺寸；拒绝 i i 山东大学硕士学位论文 a b s t r a c t h 1m el a s td e c a d e ，t h e r eh a sb e e ns i g n i f i c a n ti n t e r e s ti ns i n g l em a c h i n es c h e d u l i n g p r o b l e m st h a ti n v o l v eb a t c h i n g w ec o n s i d e r t h ep r o b l e mo fs c h e d u l i n go i las i n g l ep a r a l _ l e lb a t c h i n gm a c h i n e w ea r eg i v e nas e to fnj o b sa n das i n g l ep a r a l l e lb a t c h i n gm a c h i n e w i t hc a p a c i t yb e a c h j o bj j ( j 1 ，2 ，1 ) ) i sc h a r a c t e r i z e db ya m p l eo f i n t e g e rn u m - b e r s ( r j 。pj 。s i z e j ，w j ) 。w h e r er ji st h er e l e a s ed a t eb e f o r ew h i c hj o bj j c a n n o tb es c h e d - u l e d ；p ji st h ep r o c e s s i n gt i m ew h i c hs p e c i f i e st h em i n i m u m t i m en e e d e dt op r o c e s sj o b rw i t h o u ti n t e r r u p t i o n ；s i z eii st h es i z eo f j o bk a n dw ji st h ep e n a l t yp a i dt oj o b ) li f i ti sr e j e c t e d t h em a c h i n ec a np r o c e s san u m b e ro fj o b ss i m u l t a n e o u s l ya sa b a t c ha s l o n ga st h et o t a ls i z eo f t h ej o b si nt h eb a t c hd o e sn o te x c e e db t h ep r o c e s s i n gt a m eo f ab a t c hi st h el o n g e s tp r o c e s s i n gt i m eo fa n yj o bi nt h eb a t c h j o b sp r o c e s s e d i nt h es a m e b a t c hh a v et h es 锄es t a r tt i m ea n dt h es a m ec o m p l e t i o nt i m e o u rg o a li st os c h e d u l et h e i o b ss ot h a tt h em a k e s p a no ft h ea c c e p t e dj o b sp l u st h e t o t a lp e n a l t yo ft h er e j e c t e dj o b s i sm i n i m i z e d f i r s t ，w es h o w t h a tt h ep r o b l e m sa r en p h a r da n dt h ew o r s t - c a s er a t i o so f t h e m a r ea t l e a s t3 2 ；t h e n ，w ep r o p o s ea2 a p p r o x i m a t i o na l g o r i t h mf o rm es p e c i a lc a s ew i t hi d e n t i c a l r e l e a s ed a t e s ；f i n a l l y , w ep r e s e n ta na p p r o x i m a t i o na l g o r i t h m f o rt h eg e n e r a lp r o b l e mw i t h w o r s t c a s er a t i o2 + e ，w h e r e 0i sa na r b i t r a r i l ys m a l lc o n s t a n t m o i l v a t e db yt h er e a l t i m em a c h i n e v i s i o ns y s t e m s ，w ea l s oc o n s i d e rp a r a l l e lb 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 em a k e s p a n i nh y b r i df l o w - s h o pe n v i r o n m e n t su s i n g g e n e t i ca l g o r i t h m s t h ep r o b l e m c a l lb es t a t e da sf o l l o w s ：c o n s i d e ra s e tjo f nj o b st ob e p r o c e s s e di nak - s t a g ef l o w - s h o p ，w h e r ee a c hs t a g e ih a sm ip a r a l l e lb a t c h i n gp r o c e s s o r s ， i 1 ，2 ，”l e t 磅pd e n o t et h ec a p a c i t yo f p r o c e s s o rp o fs t a g ei ，i 1 ，2 ，材， p ( 1 ，2 ，耽) t h a ti s ，p r o c e s s o rp o fs t a g eic a np r o c e s sa tm o s tb i pj o b ss i m u l t a n e 。 o u s l y 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 el a r g e s tp r o c e s s m gt i m ea m o n gi t s m e m b e r s i ti sc o n v e n i e n tt ov i e wajo ba sas e q u e n c eo f kt a s k s - o n et a s kf o re a c hs t a g e ， w h e r et h ep r o c e s s i n go f a n yt a s kc a nc o m m e n c eo n l ya f t e rt h ec o m p l e t i o no f t h ep r e c e d i n g t a s k l e t 玩fb em e t i m e n e e d e d t 0p r o c e s s j o b 乃a ts t a g ei ，i 1 ，2 ，忌) a n d 乃j w e h a v et h ef o l l o w i n ga s s u m p t i o n sf o rt h ep r o b l e m ：1 p r o c e s s o r su s e da te a c hs t a g ec a n n o t p r o c e s st a s k sc o r r e s p o n d i n gt oa n y o t h e rs t a g e s ；2 d u r i n gt h ep r o c e s s i n go fab a t c h ，n o n e wb a t c hc 锄s t a r to nt h es a m ep r o c e s s o r l e tc q ( s ) b et h ec o m p l e t i o nt i m eo f t h e t h 一。一 i i i t a s ko f j o b - ，fi ns c h e d u l es ，i 1 ，2 ，忌) a n d 乃j w ec o n s i d e r t h em a k e s p a n m i n i m i z a t i o np r o b l e m ，i e ，t of i n da s c h e d u l est h a tm i n i m i z e sm a x 乖， c b ( s ) j w e9 1 v e 铆om 甜1 0 d sf o rc r o s s o v e fa n dm u t a t i o ns e p a r a t e l ya n di m p l e m e n tf o u r v e r s i o n so ft h e g e n e t i ca l g o r i t h m ，o n ef o re a c hc o m b i n a t i o no f t h ec r o s s o v e ra n dm u t a t m no p e r a t o 。st o i n v e s t i g a t et h ep e r f o r m a n c e t h e n ，w e f o c u so nt h es i n g l eb a t c h i n gm a c h i n es c h e d u l l n g p r o b l e m 谳i o bs i z e sa n dr e j e c t i o nt om i n i m i z e t h em a k e s p a no ft h ea c c e p t e dj o b sp l 懈 t h et o t a lp e n a l t yo ft h er e je c t e djo b s ，a n dg i v ea n e wd e c o d e dm e t h o da n df o u rv e r 5 1 0 n s o fg e n e t i ca l g o r i t h m s e x p e r i m e n t ss h o wt h a to n e o ft h ea l g o r i t h m sp e f e r m sb e 竹e rt i l 锄 o t h e r s k e y w o r d s ：b a t c hs c h e d u l i n g ；g e n e t i ca l g o r i t h m ；r e l e a s ed a t e ；j o bs i z e ；胁 j e c t i o n 氏 山东大学硕士学位论文 第1 章绪论 最近一二十年，人们对包含批的调度问题进行了深入的研究。批的引入是为 了获得效率：把工件组成批进行处理可能比单独处理更节约资源、更快捷。 1 1 应用背景及问题描述 分批调度兴起于9 0 年代初，主要应用于大规模的现代化生产流水线，如航空 工业 1 ，2 】，钢铁铸造【3 】，制鞋业【4 】以及半导体生产制造等，其中半导体生产流 水作业线，是被研究最广泛的一个领域。 。 在半导体生产流水作业线的芯片测试环节，要将芯片放入烤箱之中烘烤。每 个芯片都有一个预定的烘烤时间，经受住这段时间烘烤的芯片才被认为是合格的 产品。烤箱有一个固定的容量8 。总尺寸不超过这个容量的一些芯片可以作为一 批放入烤箱内同时烘烤，烘烤过程不允许被打断。每个芯片需要的烘烤时间可能 不同。为了保证产品质量，同一批芯片实际需要的烘烤时间为其中预定时间最长 的那个。由于烘烤时间用时很长，从而成为芯片生产流程的一个瓶颈。迫切需要 使用各种技术，提出算法以缩短产品的生产流程，提高生产效率。 从以上描述之中，可以抽取出我们的问题模型，我们使用国际上通用的r l g r a h a m 等【5 】提出的三元组来进行表示。常见问题的参数描述如下：给定，1 个工 件，每个工件( j o b ) ，( j 1 ，2 ，1 ) ) 有一些给定的参数，譬如：处理时间 ( p r o c e s s i n gt i m e ) p j ，到达时间( r e l e a s ed a t e ) r j ( 在此时间之前工件歹不得被处 理) ，权重( w e i g h t ) w j ，惩罚值( p e n a l t y ) e j ( 若拒绝处理此工件，则需支付此 惩罚值) 和工期( d u ed a t e ) d ，等。我们给定一个单机批处理系统( 即系统中的 机器可以同时处理多个工件，同时处理的工件称作一批，一批的处理时间等于 这一批中所有工件最大的处理时间) 。此类问题要求设计一个调度方案，即：选 择工件、给工件分批、以及给批排序使得某目标函数达到最小值。我们研究的 一般是正则目标函数，即目标函数为每个工件完成时间的非减函数，通常包括： 最大完成时间( m a k e s p a n ) c m a 算= m a x l ，l i c 幺x 是d ( 甩) 时间可解的，只需把所有工件放入一 批进行处理即可。对于l i b n l c m a 工是o ( n 2 ) 可解的 9 】9 。c yl e e 1 4 】也对此问题进行了研究。利用堆排序和动态规划，c k p o o n 和pz h a n g 【1 5 】设计了目前最好的时间复杂性为o ( n l o g n ) 的算法，并且， 他们猜测这可能是理论上最好的算法。由li b n l l m 瓤问题是强n p 困难的，可知 l l r j ，b ，l i c 一也是强n p 困难的【9 】。z l i u 和wy u 1 6 】证明了，即便只有两 个到达时间，此问题也是n p 一困难的；他们还对此情形给出了紧界为2 的贪婪算 法。c yl e e 1 4 】还对两个到达时间的情形提出了伪多项式时间的动态规划算法， 其时间复杂性为o ( n b 2 工只。m 1 ；对于一般情形，他们给出了紧界为2 的贪婪算 法。在此基础上，张玉忠对到达时间为任意常数个的一般情形设计出了伪多项式 2 山东大学硕士学位论文 时间的动态规划算法【1 7 】，之后，x d e n g 等 1 8 】得到了一般情形的多项式时间 近似方案。c k p o o n 和pz h a n g 【1 5 】也对1 1 0 ，b n ) 、到达时间相同、权重可能 不同的情况，eb r u c k e r 等【9 】给出了多项式时间动态规划算法。批容量b 是常 量、到达时间相同、权重相同的情况存在一个o ( ，l 口( 肛l 1 时间的算法【9 】。当b 充 分大时，c k p o o n 和wy u 【2 1 】得到了复杂性为o ( ，1 6 b ) 和，l d ( 侗的算法。d s h o c h b a u m 和d l a n d y 2 2 】还给出了2 近似算法，m - c c a i 等 2 3 】在此基础上给 出了多项式时间近似方案。当b 是变量时，这个算法的时间复杂性实际上是指数 次的，在这种情况下问题的复杂性目前尚未可知。z l i u 和t e c h e n g 【2 4 】对于 b 为变量时、到达时间相同、权重相同的情况下，设计出了多项式时间近似方案。 对于1 l b ，1 ) 的一般情况， 即：批容量无界、到达时间可能不同、权重可能不同的情况，x d e n g 等【2 7 】证 明其是n p - 困难的；这篇文章的作者之一在其后的一次报告中称权重相同的情况 也是n p 一困难的。1 9 9 9 年f a e w i p i d i s 等【2 8 】采用规整舍入技术取得了突破性的 进展之后，对于批容量有界( b ，1 ) 和无界的各种情况，人们运用此项技术设计 出了多项式时间近似方案【2 7 ，2 9 ，3 0 】。z l i u 和t e c h e n g 【2 4 】对于【2 7 】中的多项 式时间近似方案进行改进，得到一个全多项式时间近似方案。pb a s t i s e 【3 1 】还利 用动态规划对l l r j ，p = p ，b 圳w j c j 问题给出了多项式时间的最优算法。对于 l l r j ，b 川c j 问题，p c c h a n g 等【3 2 】还利用约束规划给出了分支定界算法。 山东大学硕士学位论文 1 2 3 工件可拒绝 在现实世界中，由于资源的限制，调度者有时候可以选择是否拒绝一些工件。 yb a r t a l 等 3 3 】首先引入了工件以一定代价被拒绝，并研究了在相同并行机器上 的离线以及在线调度。对于可以拒绝的最小化最大完成时间目标函数，当允许所 有工件抢先模式下，s s s e i d e n 【3 4 】给出了一个改进的在线算法。hh o o g e v e e n 等【3 5 】研究了允许抢先模式下的离线版本算法。z c a o 等【3 6 】把工件可以拒绝的 最小化最大完成时问问题通过以惩罚总值w 作为限制条件，当作双目标优化问 题来处理。王珍等 3 7 】针对l i p b a t c h ，b 0 可以为任意小的数。 对于1 l b n ，s i z e 肥m x ，l d u p o n t 和c d h a e n e n s - f l i p o 4 6 】给出了分支定界的算 法。对于另一个问题1 i b n ，p f _ a s i z e j i c , , 。x ，尽管它不能够以装箱问题作为特 例，yz h a n g 和z c a of 4 7 】仍证明了此问题不存在近似比小于3 2 的近似算法。 对于加权完成时间的1 i b n ，s i z e j ie ( t o j ) c j 问题，r u z s o y 【4 4 】，f j g h a z v i n i 和 l d u p o m 4 8 】，m a z i z g l u 和s w e b s t e r 【4 9 】分别进行了研究，给出了一些启发式 算法或分支定界算法，但理论分析方面没有大的突破。 4 b 山东大学硕士学位论文 1 2 5 智能算法 由于大多数批调度问题的n p 困难性，不少人也进行了智能算法的研究。冯 大光和唐立新 5 0 】对最小化加权完成时间之和的单机批调度问题部分工件的分批 性质进行了研究，提出了启发式算法，并通过数学实验与常规算法进行了对比。 马慧民和叶春明【5 1 】针对半导体炉管区批调度问题，设计了双层粒子群算法，其 中外层应用基于文化进化的并行粒子群算法进行批量计划问题的求解，内层采用 传统的粒子群算法求解调度问题，通过对其他文献中的仿真实例进行计算和结果 比较表明，算法优于文献中的启发式算法和蚂蚁算法。对于1 i 曰 0 ，a ( ) 是关于问题丌实例输 入长度和1 e 的多项式时间算法，则称a ( ) 为解答7 r 的全多项式时间近似方案。 a p x ( “a p p r o x i m a b l e ”的缩写) 是允许近似算法近似到一个特定下界近似比的近 似算法集合，也就是说是具有常数近似比的近似算法集合。一个问题是a p x 困 难的是指存在一个从a p x 集合的每一个问题到它的p t a s 归约。显然，如果一个 问题是a p x 困难的那么此问题就不存在多项式时间近似方案。 我们采用g p 来表示l i p b a t c h ，s i z e j ，f l c 榭善+ w 这个问题，采用铲来表示和 g p 类似的问题，除了所有的工件能够被切分，即：l i p b a t c h ，s p l i t ，s i z e j ，r ，l c 一+ w 。在调度问题之中，一个工件能够被切分是指它的尺寸被切分。也就是说，每 一个原始工件乃= ( r j ，p j ，s i z e j ，哟) 能够被切分为部分工件j j ( 1 ) ，乃伽) ，对每个 部分工件) ( k ( 1 ，m ) ) ，有属性( 0 ，p j ，s i z e i s i z e j 且m n ，则工件乃能在调度i l ( s - s i z e j ) 的最后一批中容纳，那么已( j ) = p j l ( s s & e j ) 。如果s s i z e j 且m = 0 ，则工 件乃能在调度乃一k s s i