（运筹学与控制论专业论文）机器有两种不同速度的平行工件在线排序.pdf

摘要 本文主要研究关于平行工件( p a r a l l e lj o b s ) 的排序( s c h e d u l i n g ) 问题有2 m 台一致平行机，其中m 台速度为1 ，另外m 台速度为s ( s 1 ) 每个平行工件以 要求必须在m ，( m m j 之1 ) 台机器上同时加工这个工件，但每个工件只能选取 同一种速度的机器工件在零时刻都已到达，但他们的加工时间是未知的，只 有当工件加工完成时才可知道。这种在线模型称为无预见的( n o n c l 缸r v o y a n t ， 简记为n c v ) ，目标是极小化最大完工时间( g 。) 用三参数表示法，我们的 问题可以表示为q 2 m l d = 0 ，r n j ，o n l i n e 一竹c t ，l g 。我们对该排序问题提出了 相应的在线算法，并采用国际上通用的算法评价标准竞争比( c o m p e t i t i v er a t i o ) 来衡量、分析给出的算法。通过构造坏的实例，我们给出了问题的下界( 1 0 w e r b o u n d ) 同时研究了该模型在一定限制下的特殊情形，得到了更好的竞争比 本文的主要结果如下： ( 1 ) 对于排序模型q 2 m l r j = 0 ，r n j ，o n l i n e n 例i g 。，给出了其下界 p = z 一而与 ( 2 ) 对于排序模型q 2 m l 巧= 0 ，o n l i n e n 例l g 。给出一个竞争比为 口= s 【2 + 而m 许s 可- - 丽s - 2 】 1 s s s 。 2 + 而2 m 雨- - 2 t t 矿s m 2 一篙 s 仇 的在线算法，其中 s + ：c 丽m + 赢蕊。+ 晶+ 南丽5 ( 3 ) 对于排序模型q 2 m l r j = 0 ，叻，m l i n e 一礼删i g 。，在p m ( 8 + 1 ) 奶一限 制下，给出了一个竞争比为 口= 2 + 而m 丽s - s - 2 2 + 粼 2 一篙 1 8 8 7 8 1 1a n dmm a c h i n e so fs p e e d1 e v e r y p a r a l l e lj o bj jm a yr e q u i r e ”b ( m 0 1 ) m a c h i n e ss i m u l t a n e o u s l y , a n de v e r yj o bi s o n l ya b l et oc h o o s em a c h i n e sw i t ht h es a m es p e e d w ea s s u l l ed = 0f o ra l lj o b s ，b u tt h e i r p r o c e s s i n gt i m ei su n k n o w nu n t i lt h ej o bh a sf i n i s h e d t h i st i p yo fo n - l i n em o d e l si sc a l l e d n o n c l a i r v o y a n t ，d e n o t e db yn c vi ns h o r t t h eo b j e c t i v ei sm a k e s p a nm i n i m i z a t i o n ( c k ) u s i n gt h e3 - f i e l dn o t a t i o n ，o u rp r o b l e mi sd e n o t e da sq 2 m l r i = 0 ，o n l i n e n 倒i c w e p r e s e n ta l g o r i t h m sf o rt h es c h e d u l i n gp r o b l e ma n da d o p tt h es t a n d a r dp e r f o r m a n c e m e a s u r ec o m p i t i t i v er a t i ot oa n a l y z ei t w ea l s ep r o v i d el o w e rb o u n d sb yt h es p e c i f i c i n s t a n c e s a tt h es a m et i m e ，w ec o n s i d e rs p e c i a lc a s e so ft h ep r o b l e m ，a n dg i v eb e t t e r c o m p i t i t i v ea l g o r i t h m s t h em a i nr e s u l t so ft h i sp a p e ra r ea sf o l l o w s ( 1 ) f o rt h es c h e d u l i n gm o d e lq 2 m i d = 0 ，o n l i n e n 删l g m ，w eg i v et h el o w e r b o u n d 胪2 一南 ( 2 ) f o rt h es c h e d u l i n gm o d e lq 2 m r j = o ，m j ，o n l i n e 一扎i ，w eg i v ea n a l g o r i t h mw i t hc o m p e t i t i v er a t i o p = s 【2 霉1 二蚤 3 + 丽m + 蒜 3 f 碌磊；i j 赢翥 e i 矿 ( 3 ) f o rt h es c h e d u l i n gm o d e lq 2 m r i = 0 ，o n l i n e 一删i ，w h e np m 0 + 1 ) 肼m ，w eg i v ea na l g o r i t h mw i t hc o m p e t i t i v er a t i o l2 + 丽m 耳s 可- s 丽- 2 1 s s 7 p 2 2 + 器等暴 s ，s m 【2 一等 s m ( s = 呼，p 2 善他功，a n d = 警功) ( 4 ) e d r h es c l l e d u l i n gm o d e lq 2 m r j2o ，m j ，o n l i n e n c v c m a zw i t h p m ( s + 1 ) 1 警巧 a n du s i n gv i r t u a l i z a t i o n ，w eg i v ea na l g o r i t h mw i t hc o m p e t i t i v er a t i o ( p = 叻黪) t r p = 。一而 k e yw o r d s ：p a r a l l e lm a c h i n e ；p a r a l l e lj o b ；o n - l i n es c h e d u l i n g ；c o m p e t i t i v er a t i o f a s tm a c h i n e ；s l o wm a c h i n e 4 第一章绪论 1 1排序的介绍 排序，是在一定条件下分配时间资源去完成一些任务，使得某一个或某一 些目标达到最优。它是一类重要的组合最优化问题，是运筹学研究的一个非常 活跃的分支。排序问题产生的背景是机器制造。二战之后，随着大型制造业的兴 起，人们逐渐意识到排序问题研究的重要性。人们普遍认为1 9 5 4 年j o h n s o n 1 1 发 表的一篇关于两台机器同序排序问题的论文是第一篇关于排序研究的文章。从 这篇论文问世以来的半个多世纪中，排序问题的研究有了迅速的发展，全世界 已经发表的文献3 千多篇，其中包括排序专著和教材5 0 余种。今天，排序论 不仅仅应用于机器制造业，它更广泛的应用于管理科学、计算机科学和工程技 术等领域。而在这些领域取得的丰硕成果使排序论成为发展最迅速的学科领域 之一 排序论一般分为理论部分和应用部分在唐国春，张峰等人2 0 0 3 年的现 代排序论【2 】一书中提到，排序理论研究可分为经典排序( c l a s s i c a ls c h e d u l i n g ) 和现代排序( m o r d e r ns c h e d u l i n g ) b r u c k e r 和k n u s t 在“c o m p l e x i t yr e s u l t so f s c h e d u l i n gp r o b l e m s ”( 参见胁t p ：w w m a t h e m a t i k u n i o s n a b r u e e k d e r e s e a r c h o 剐c l a s s ) 使用c l a s s i c a l 和e x t e n d e d 两个词来区别经典和非经典的( 推广的) 两 类排序问题。他们也用n e wc l a s s e so fs c h e d u l i n gp r o b l e m s ( 新型排序) 来表示非 经典的排序问题因此，现代排序就是非经典的，新型的排序相对经典排序 而言，其最大特点就是突破了经典排序的基本假设从上个世纪8 0 年代以来， 新型排序模型不断涌现常见的1 0 余种排序模型有：平行工件排序、可控排 序、成组分批排序、在线排序、同时加工排序、准时排序、不同时加工排序、 资源受限排序、随机排序、模糊排序、多目标排序等( 参见文献【2 】) 对于一个组合优化问题，如果能找到一个多项式时间的算法，我们就将其 归为p 问题但不幸的是，对于大多数问题而言，我们并不知道是否存在一个 多项式时间的算法然而，我们知道有这样一类问题，一旦其中的一个问题能 够在多项式时间内解决，那么所有其它的问题皆可以在多项式时间内解决，我 6 们将其归为n p 一困难问题。丽这些问题目前我们还无法给出它们的多项式时 间算法对于它们我们可以寻求一个算法去逼近最优解，这就是近似算法的思 想 由于大多数排序问题都是n p 一困难问题，其最优解往往很难找到，而且 在实际应用中我们也没有必要去寻求最优解，而仅仅找出满足一定条件的近似 解就行了。因此，研究排序问题可以从以下两个方面入手； ( 1 ) 对于p 问题，寻求多项式时间算法； ( 2 ) 对于n p 一困难问题，一是在特殊情形下寻找有效算法，即研究它的可 解情形；二是设计性能优良的近似算法。 对于近似算法我们该如何去衡量它的“优良”程度呢? 常见的有三种办法： 数值算例计算、最坏情况分析和概率分析目前，在排序研究中，用得最多的 是算法的最坏情况分析下面我们介绍一些有关近似算法的概念在这里，我 们以m i n 型优化问题为例作介绍( 见文献【3 】) 给定一个带有非负权重的优化问题p ，常数k 1 ，若存在一个多项式时 间算法a ，对尹的任何实例，皆有a ( i ) k o p t f f ) ，则我们称a 是优化问题 p 的一个k 一因子近似算法，也称算法a 具有性能比后；使得a ( i ) sk o p t ( i ) 成 立的最小的k ，就称为a 的最差性能比。 给定一个带有非负权重的优化问题p ，若存在一个多项式时间算法a 和 一个常数c ，对p 的任何实例j 皆有a ( i ) sk o p t ( t ) + c ，则我们称a 是优化 问题p 的一个渐近的k 一因子近似算法，也称算法a 具有渐近性能比k 。 给定一个带有非负权重的优化问题p ，若存在一个多项式时间算法a ， 使得任意p 的一个实例，和每一个固定的e 0 ，a 都是优化问题p 的一个 ( 1 + ) 一因子的近似算法，那么算法a 称为p 的一个近似方案。 1 2在线排序和平行工件的排序 本文主要涉及到现代排序中的在线排序和平行工件的排序下面我们将对 这两个模型作简单介绍： 7 在经典排序中，一般假设一个实例的所有信息，包括工件的个数、到达时 间，加工时间等在开始排序前都是事先知道的。这种情形我们称为是离线的 然而在现实生活中许多情况并非如此，决策者需要在工件信息到来之时就必须 进行决策这种情形我们称为是在线( o n 一妇e ) 或者是半在线( s e m io n - l i n e ) 的 在在线排序中，工件信息是逐个释放的，决策者在决定当前工件的加工时对其 后的到达工件是一无所知的，并且一旦决定工件安排后就不允许改变。 根据工件的到达方式，在线排序分为两种： ( 1 ) 按序( o v e rl i s t ) 在线排序：工件是排列成一个顺序逐个出现的一个工 件只有当表中排在其前面的工件都安排后才知道这个工件的相关信息。 ( 2 ) 按时( o v e rt i m e ) 在线排序：工件随着时间进行安排，在任何时刻只知道 当前已到达工件的信息。 事实上，在按时在线排序中，又有两种分类：第一种是工件的信息，如加 工时间，在工件到达时就可知道；第二种就是工件的信息在其加工完时才能被 “告知”这种在线模型称为无预见的( n o n c l m r v o y a n t ，简记为n c v ) ，而在本文 中我们主要考虑第二种按时在线排序 由于在线排序问题( 除个别目标函数外) 通常不存在最优算法，因此，我们 往往考虑它们的近似算法通常我们用在线排序算法的竞争比来衡量它的优 劣，即把在线算法的结果与对相同工件运用离线最优算法得到结果进行比较 我们定义在线算法a 的竞争比r a 是排序问题所有实例的比值暑竺的上确界， 其中c 矗和c 分别由算法4 得到的目标函数值和相应的离线排序的最优值。 然而，由于对未来工件信息的未知，我们很难找到一个在线算法达到最优因 此，r a 的值往往大于1 另一方面，对于一个在线问题，我们可以设计不同 的在线算法来区分它们的“好坏”我们的目标是设计竞争比尽可能小的在线 算法 在经典排序中，我们还假设任何机器任何时刻最多只能加工一个工件，而实 际生活中有的“机器”可以同时加工多个“工件”例如，一个烤箱可同时烘烤多个 面包。最典型的是发生在大规模集成电路的生产中，为了保证成品合格，检验阶 段要把集成电路放在烘箱中试验它们的耐温性能。一个烘箱可以同时检测多个 8 集成电路，而且在检测过程中不可以移走任何集成电路这种机器可以同时加工 多个工件的排序问题称为分批加工机器排序( s c h e d u l i n gi nab a t c h i n gm a c h i n e ) 这是一台机器同时加工多个工件作为一批然而，随着计算机及现代生产技术 的不断发展，多台机器也可同时加工一个工件，因而关于平行工件的排序问题 近年来受到了国内外的广泛关注假定有m 台平行机和n 个平行工件，每个 工件如有加工时间珊，并将加工时间珊叫做工件如的长度。与一般工件不 同的是每个平行工件需要m j 台机器加工，并将m ，叫做工件乃的宽度。工件 乃加工期间一直占用台机器，每台机器一次至多加工一个工件，在工件易 的加工期间，所用的台机器需要花费相同的加工时间乃每个工件的到达 时间可以是未知的，到达方式可以是按序( o v e rl i s t ) 或按时( o v e rt i m e ) 到达，也 可以是零时刻都已到达，并且工件之间也可以存在某种序关系工件的加工时 间可以是工件到达就知晓，也可以在工件加工完成时才可知晓 1 3排序的记号 1 9 7 9 年，g r a h a m ，l a w e r 等人【4 】提出用三参数来表示一个排序问题在这 里，我们采用o lp l ，y 来表示，其中。域表示机器状况，卢域表示工件状况， ，y 域表示目标函数下面我们分别作一些说明； ( 1 ) q 域： o l = 1 单台机器 o l = p 相同的平行机 a = q 一致的平行机 口= r 无关的平行机 ( 2 ) p 域： p = 巧工件的到达时间 p = 工件乃需要叻台机器加工 p = 勺= 0 工件零时刻都到达 卢= p r e c 工件间有序约束 9 p = 0 1 1 一l i n e - l i s t 工件是按序在线 卢= 0 1 1 一l i n e - n c v , q工件是无预见的按时在线 ( 3 ) 7 域： 首先，我们介绍一些符号： g j 工件如的完工时间 由= 工件乃需要由台机器加工，也称为工件易的度 7 k最优的完工时间 勺工件乃的开工时间，这里，= q 一功 p j工件在速度为1 的机器上的加工时间 巧工件以的到达时间 岛工件在速度为s 的机器上加工所需时间，即白= 警 现在，我们介绍一些目标函数： 7 = g 。= t 最大完工时间，此处，g 。；m a x g f l j 几 7 = l 。最大延迟，此处，l 。= m a x 岛1 1 歹n ) ，y = 巩。工件被运到目的地的最大时间，此处，历一= m a x d j l l j 竹 ，y = e q 完工时间和 ，y = e w j g 加权完工时间和 ，y = 乃误工时间和 7 = e 嘶乃加权误工时间和 7 = 误工工件数 ，y = 嘶加权误工工件数 1 4 相关结果及本文主要结果 本节我们主要介绍本文研究的排序模型以及现有文献中有关此类模型的 相关结果，最后列出本文的主要结果 本文所讨论的问题是有2 m 台机器，其中m 台机器的速度为1 ，另外m 台 机器的速度为s 工件集丁= 以，厶) 中有1 1 个工件在零时刻都已到达，其中 1 0 工件弓需要台机器加工，并且这台机器只能选取同一种速度的机器， 加工期间不可中断，其加工时间在加工完成时才可知道，目标是找到一个可行 排序使得最大完工时间最小我们的排序模型用上一节提到的三参数法可表示 为：q 2 m l r j = o ，o n l i n e n 删f g m 对于目标函数为最大完工时间的平行工件排序问题，现已有文献研究，但 最初的研究主要集中在将加工时间都限制为1 的情形 对于离线的情形，在1 9 8 1 年，e l l l o y d 1 6 证明了模型p i m j 仍= 1 i c k 。和 p 3 i 叻，p r e c ，岛；1 i g 。( m j 2 ) 是n p - 困难的，而p 2 i m j ，p r e c ，巧= 1 i g 。是多 项式可解的在1 9 8 6 年，j b l a z e w i c z 等人【5 】证明了模型p i 叻嘞= 1 i g 是强 n p 一困难的在1 9 8 9 年，j d u j l e u n g 7 证明了模型p 2 l m j i c 。和p 3 1 m j l g 。 是n p 一困难的，并且是拟多项式可解的另外，他们也证明了p 4 1 l g 。是 强n p 一困难的 对于在线的情形，在1 9 9 4 年，f e l d m a n n 等人1 利用l s 算法证明了模型 p m l r j = 0 ，m j ，o n l i n e n 铡i g 有竞争比2 一击2 0 0 2 年，n a r o s k a 等人【2 1 证明了模型p m l r j ，m j ，o n l i n e 一钆删l g 。有竞争比2 一鬲1 2 0 0 6 年，b e r i t 1 5 】 证明了对于模型p m l r i ，m j ，o n l i n e n 刮a 一，不可中断的l s 算法产生排序 的最大完工时间至多是最优的可中断的最大完工时间的两倍，这将导致问题 p m l r j ，r a j ，o n l i n e 一帕，l g m 和p m l r j ，p m t n ，o n l i n e n 铡j g 的竞争比是 2 。 对可中断的离线情形，1 9 9 4 年，m d r o z d o w s k i 6 】证明了模型p i ，p m t n l g 对于任意机器数是n p 一困难的在1 9 8 6 年，j b l a z e w i c z 等人【5 】证明了模型 p m i ，p m t n g 是多项式可解的j a n s e n 等人进一步研究了这一问题并给出 线性时间算法。 以上是同型平行机( 恒同机) 情形的研究情况本文将研究同类平行机( 一 致机) 的一种特殊情形：有m 台机器速度为1 ，另外m 台机器速度为s ( s 1 ) ， 工件以要求必须在( 仇1 ) 台机器上同时加工，并考虑无预见的在线排 序，这也就是将模型p m l r j = o ，o n l i n e 一删j g 一中，p m 换成q 2 m 进行 了研究 下面我们就给出本文的主要结果 ( 1 ) 对于排序模型q 2 m l r j = 0 ，m j ，o n l i n e n 驯g 。，给出了其下界 p 卅一两! 矗 ( 2 ) 对于排序模型q 2 m l r j = 0 ，m j ，o n l i n e n c v l 。给出一个竞争比 p l s 矿 矿 s m 的在线算法，其中 s = c 鼎+ 鼎蕊5 一【- 南+ 高蕊5 ( 3 ) 对于排序模型q 2 m l r j = 0 ，m j ，o n l i n e 一礼倒i g 。，在p m ( s + 1 ) p m 。限 制下，给出了一个竞争比为 d = 2 + 面m 再s 可- 丽s - 2 2 + 粼 2 一篙 l s 8 7 8 7 三! 竺! 坐1 2 8 2 m ( s + 1 ) + ( m + 1 ) 8 情形2 1 2 当乃袈燃t 时， ! 竺! ! ! 竺1 2 2 m ( s + 1 ) + 2 ( m 一1 ) 一( m 一1 ) 2 面丽1 t 砀刀端之堕业鬻掣 坠等等1 出，一坠m 铲( s 巧一mfs+) + 1 ) 、2 ( m m j + 1 ) + ( m + 1 ) s 巾 m 一2 m j + 12 m + ( m + 1 ) 3 t 一 2 m ( s + 1 ) m ( s + 1 ) 4 m + 2 m s 一2 1 其中的系数为 二! 。! ! 丝竺1 2 2 m ( s + 1 ) 2 m ( s + 1 ) ( 2 m + m s 一1 )= 2 m ( s + l 坐) ( 2 m ! + ! m s - - 1 ) 。 2 u 所以当m j = 1 时，前式右端有最小值( 因为它是关于的增函数) 故 乃刀之丽2 m + ( m + 1 ) s t 一蒹糟嬲t ( 2 m + 7 1 2 8 + s ) ( m + 7 1 2 8 ) ，丌 2 丽万订砸磊而；i 可1 2 m + f m + 1 ) 8 = - - - - - - - - - 一 4 m + 2 m s 一2 、1 ( m + 1 ) 8 + ( m + 1 ) 巾、1( m + 1 ) ( s + 1 )t s2 m ( s + 1 ) + ( m 一1 ) 一s 2 m ( s + 1 ) + ( m + 1 ) s 2 硒翻1 z 情形2 2 当快讥器存在窄阶段时，设工件j 在最后的窄阶段上加工，其实际 花费的时间为芬，那么工件j 安排之前快机器一直至少运行m 一+ 1 台机器， 并且慢机器在排序s 中一直运行至少学1 台机器 情形2 2 1 当旦2 ( 2 m 型s + 塑m l - - s ) 时， 胛警= 岛卷嵩篙t 1 7 =ms+面re+再s+百1+而(m-丽1)s3ms 2 m s83r 竺3 等m s 筹2 m r + + ( m 一) s 一 十 + 3 竺里! 1 7 1 l m s + m + 8 + l t 一 3 m s + 2 m + 8 一83 m s + 2 m + 8 l s 2 m ( s + 1 ) + ( m + 1 ) s 情形2 2 2 当幻莉2 m 丽s m1 t 时， 丁。硒丽1 z 刀2 端坠生氅善铲业挫 坠铲t 一坠等等型 ( m - m 丽j 西+ 了1 了) s 广+ t 一鱼尘二景铲及2 2 m m s 。+ 一m 。+ + m 1 ) t ， 其中的系数为 - - 8 2 s ( 2 m s + m + 1 ) m ( s + 1 ) 。2 m ( s + 1 ) ( 2 m s + m 一8 ) 所以，当m j = l 时，上式有最小值，故 ：型! ! ! 0 2 2 m ( s + 1 ) ( 2 m s - 8 - b m ) ，个 2 m s + m + l t f 竺竺二兰! ( ! 竺兰竺! ! t = ( 2 m s - b m + 1 ) ( m s + m ) t o p r 孬磊石可1 一2 m ( 8 + 1 ) ( 2 m s - s + m ) 1 2 m ( s + 1 ) ( 2 m 而1 ：! 竺! 竺! t ：竺! 竺! ! f 竺二! ! ! t 2 ( 2 m s 一8 + m ) 一3 m s + 2 m 十8 + ( m 一3 ) s m s + m + 8 + l + 2 8 t m s + m + s + l t 三竺竺! ! t 一 3 m s + 2 m + 83 m s + 2 m + 8 83 m s + 2 m + 8 1 ( m + 1 ) ( s + 1 ) 8 2 m ( s + 1 ) + ( m + 1 ) sr 2 丽丢丽? 2 对整体2 m 台机器而言，存在窄阶段 情形1 快慢机器都不存在窄阶段时，此时两类型机器一定不是同时完工( 否 则整体就不存在窄阶段了) ，且每种类型的机器在完工之前都至少有f 学1 台 机器在运行，设先完工类型的机器的完工时间为噩，工件j 决定总完工时间 t ，即c s = z 转为工件j 在速度为1 的机器上加工所花费的时间，为工件在 速度为s 的机器上加工所用时间，即t j = 孚 1 8 情形1 1 当快机器先完工时，工件j 在慢机器上加工，并决定总完工时间 t ，且五t p j ( - f 件j 安排之前快机器肯定没有完工) 情形1 1 1 当乃而署篝臻t 时， t o p t 警= 丽司( m a 甭- 1 ) ( s 丽+ 1 碉) t = 蕊丽1 t 情形1 1 2 当p js 而尚舞黯b t 时， 端端+ 端t ， 端卜卅端m + lt = 黜t 一端巧 望 垒1 2 t 一- 赴( 竺! ! 鱼! ! t m ( 8 + 1 ) m ( 8 + 1 ) ( 7 7 1 - i - 1 ) 8 + 2 m ( s + 1 ) 1 糌2 m ( s1 丁一 一 + ) ( 竺1 2 1 1 竺1 21 1 ! 1 2 m ( s + 1 ) ( m + 1 ) s + 2 m ( s + 1 ) 】 = 高等1 ) 8 2 m ( s 1t 兰8( m + ) 一一 2 硒蔼1 m s - - s - 2 z s 【2 + 两硒干i 】“ 塑! 1 2 2 m ( s + 1 ) - 4 - ( m + 1 ) 8 情形1 2 当慢机器先完工时，工件j 在快机器上加工并决定总完工时间t ， 且五 t 一白( 工件j 安排之前快机器肯定没完工，否则工件j 就可以提前安排) 情形1 2 1 当芬2 嘉m i ；干+ l 辫s + 貉l 于时， 册2 譬= 岛柰黼t 三! 竺! 地1 2 8 2 m ( s + 1 ) 十( m + 1 ) 8，。面翻z 1 情形1 2 2 当t j 杀蔷龄糟t 时， 孙5 r n c 殇之鼎聃m ( s r j 咀+ 1 ) - 1 t 端卜卅端t = 甓等- t - 1t 一端岛 m ( s) m f s + 1 ) 叼二- 母笋 0 + 1 ) 印f 学( m + 1 ) ( s + 1 ) m ( 8 + 1 ) 一m ( 8 + 1 ) 2 m ( s + 1 ) - i - m + 1 错t 一硒等等厕 22 m 2 m ( s + l i + m 4 - 1 l 1 。2 m ( s + 1 ) + r a + 1 1 ；端t=孺12m(s 1m m s - - s - - 2 z 二_ s + ) + (十1 ) s s 【2 + 雨再可而】 情形2 当快慢机器都存在窄阶段时，同样设先完工类型的机器的完工时间 为t 1 ，工件j 决定总完工时间t ，即勺= 正胁为工件j 在速度为1 的机器上加 工所需时间，巧为工件在速度为s 的机器上加工所用时间，即t j = e 。t 情形2 1 当快机器先完工时，快机器的最大完工时间为t 1 ，慢机器的最大完 工时间为t ，工件j 在慢机器上加工，勺= t ，实际花费时间为聊，乃t 一聊， 并在【0 ，t v j l 快慢机器都至少运行m - m j + l 台机器，在i t - v j ，t t 至少运行m j 台 慢机器 情形2 1 1 当翰而尚蔷赘朵而t 时， 刀譬2 ；丽杀臀篇而t 兰! 竺1 2 ( ! 1 2下 。s2 m ( s + 1 ) + ( m + 1 ) s 1 t s 2 + 丽m s - s - 2 - 情形2 1 2 当功而尚嵩攀桊而t 时， 勋2 端坠群( t 刊+ 南弓 = 坠裂若1 业t 一坠型m 辨( s # 1 卫乃m ( 8 + 1 一 十) “ 坠铲t 一止等拦坐两等啬蒜而t 其中m ，的系数为 丽i 2 ( 1 赢- m i s 云) 干孬 坚! 狴1 2 t 【m + 2 ) 【s + 1 j + 2 m s + m 一2 m ( s + 1 ) + ( m + 1 ) 8 ；亲黼t=孺12m(s - 4 - m s - - s - - 2 z s + 1 ) + ( m + i ) 5 s ( 2 7 ；再而f i i 丽】 情形2 2 当慢机器先完工时，快机器的最大完工时间为t ，而慢机器的最 大完工时间噩，工件j 在快机器上加工，c j = t ，弓= 譬，t 1 t - t j ，并在【0 ， t - ) 快慢机器都至少运行m r n j + l 台机器，在【t - t j ，t ) 至少运行台快机 器，则 情形2 2 1 当t j 两尚嵩攀纂而t 时， 砀刀2 譬= 白丽再高等宰菪t 2 2 m ( s 等1 糕t ；2 m ( s