（运筹学与控制论专业论文）带学习因子的单机排序问题.pdf

带学习因子的单机排序问题 摘要 本文主要研究带学习因子的一类单机排序问题：n 个工件需在同台机器 上依次加工，工件j ，j = 1 ，2 ，n ，所需的正常加工时间为n ，如在某序中工 件j 第r 个加工，则机器对其实际加工时间为n ，。，其中d 0 为一学习因子。 要求适当排列这n 个工件的加工顺序，使某目标函数达最小，特别对加权完 工时问之和、最大迟后、延误工件数这三个目标函数，给出了在相应的一致 性条件下，对应的w s p t 规则，e d d 规则，修正m o o r e l o d g s o n 算法获最优序， 并估计了在一般情况下由这三规则所获序的误差。全文共分三章。 关键词排序学习因子一致性条件 误差 a b s t r a c t i nt h i st h e s i s ，w em a i n l ys t u d yf o l l o w i n gs 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 sw i t hl e a r n i n ge f f e c t ：nj o b sa r et ob ep r o c e s s e di ns a m e m a c h i n e ，t h eb a s i cp r o c e s s i n gt i m ef o rj o bji s p j j 2 1 , 2 ，n i nag i v e n s e q u e n c e ，i f j o bj i si np o s i t i o nr , t h e nt h ea c t u a lp r o c e s s i n gt i m ef o rj o bji s p 。r ，i nw h i c hd 0i sag i v e nc o n s t a n tl e a r n i n ge f f e c t w ea r ea s k e dt o s e q u e n c e t h enj o b si ns u c haw a yt h a ts o m eo b j e c t i v ef u n c t i o n sa r e m i n i m i z e d f o rt h ef o l l o w i n gt h r e eo b j e c t i v ef u n c t i o n s ：t h et o t a lw e i g h t e d c o m p l e t i o nt i m e s ，t h em a x i m u ml a t e n e s sa n dt h en u m b e ro ft a r t yj o b s ，t h i s p a p e rp r o v e s t h a tt h ew s p tr u l e ，t h ee d dr u l ea n dt h em o d i f i e d m o o r e h o d g s o na l g o r i t h mc a nc o n s t r u c tt h eo p t i m a ls e q u e n c eu n d e r c o r r e s p o n d i n gc o n s i s t e n tc o n d i t i o n s ，r e s p e c t i v e l y t h i sp a p e rg i v e sa l s ot h e e r r o re s t i m a t i o nf o rt h e s et h r e er u l e si ng e n e r a lc a s e s k e yw o r d ：s c h e d u l i n g ；l e a r n i n ge f f e c t ；c o n s i s t e n t c o n d i t i o n ；e r r o r e s t l m a l o n 第一章绪论 1 1 排序问题 排序问题是运筹组合优化中的一个重要分支，虽然它只是2 0 世纪5 0 年代初期 才开始，但在近5 0 年来得到了广泛而深入的研究，现在已经成为运筹学中相当具 有生命力的一部分。生产实际中存在大量的、不同类型的排序问题。为了叙述简 便，人们使用了一些简便的描述排序问题的记号。下面所使用的记法来自g r a h a m 给定n 个工件组成的工件集j = p 。，：，j 。 ；m 个处理机的处理机集 m = m 。，m ：，m 。 和s 种资源的资源集吼= r j , r ：，r 。) ，排序问题指的是在一 定条件下，为了完成各项加工，把m 中的处理机和r ( 如果有) 中的资源分配给 j 中的工件，使目标函数达到最优。 排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和 目标函数所组成。一般来说，我们将所要完成加工的对象称为工件，执行加工称 为加工工件。只有一个处理机的排序问题称为单( 处理) 机排序问题，否则称为 多( 处理) 机排序问题。 排序问题巾的约束条件，0 ：要指的足工件或作业的性质以及它们在加生样 中的要求和限制。r 面的数据描述了 ：件的。些性质。 j e 中p 。是 j ，在处理机m ，i 一所需要的f 【1 ：刚i r 问。 ( 2 ) 工件，到达时间( a r r i v a lt i m e ) 或准各时间( r e a d yt i m e ) ， 0 表示工件，已经准备好可以被加工的时间。如果所有的工件的准备时间相同， 取r ，= o ，= 1 , 2 ，n ( 3 ) 工件j ，的应交工时间( d u ed a t e ) t 表示对工件限定的完工时间。如果刁 按期完工，应受到一定的惩罚。绝对不准许延误的应交时间称为截止期限( d e a d l i n e ) 当乃= d 时，即d 是工件的共同应交工时间( c o m m o nd u ed a t a 简记为c o n ) ( 4 ) 0权因子，表示工件j ，相较于其它工件的重要程度。 令： c j ：表示一序中工件j 的完工时间。 l j ：表示在一序中工件j 的延误时间，三，= c ，一d ， ：表示在一序中工件j 的超前，e j = m a x o ，d ，一巳 巧：表示在一序中工件j 的延误，巧= m a x 0 ，c ，一吒j c ：表示在一序中工件的加工全程( m a k e s p a n ) ，它等于序中最后一个工件的 完工时间。 l ：表示在一序中工件的最大延误( m a x i m u ml a t e n e s s l 对任给排序问题，我们通常采用g r a h a me ta 1 ( 1 9 7 9 ) ( ij 提“j 的所渭三参数法来 给山它的+ 个简单刻划：_ = = 三参数可简弓成口y ，其中： 1 口：机器环境 机器i ，j 以是单台，也可以址多台。对多台机来说按照功能可分为两大类： ! | j 平fj ：机( p a r a l l e l ) 和g - h ( d e d i c a t e d ) 机。前者又1 - _ 分为：i 类：( 1 ) 不同机器的 加工速度完全致，f i 不依赖r | 称为| _ j 弘( i d e n 【i c a i ) 机，记为p ；( 2 ) 1 、 同的机器儿订不同的加工述度，j l 速度弗小依赖r 川7 h 氍、为旧类( l m j f 、o r n l ) 桫l ，i 已为q ：( 3 ) 耵c * * 的m 1 1 j 趣j 楚俄赖d 【| f ：1 。f ”i ，1 i f u f | 0f ：r 。吲j 使r f ：同台村l 糍 上也可能有不同的加工速度，称为不同类机( u n r e l a t e d ) 机，记为r 。对于专 用机来说也可以分为三类：( 1 ) 流水作业( f l o w e r s h o p ) ，记为f ；( 2 ) 自由作业 ( o p e n s h o p ) 记为o ；( 3 ) 有序作业( j o b s h o p ) ，记为j 2 口：特定的加工限制和约束 常出现的加工限制和约束有：工件j 的准备时间，工件j 的应交工时间，工件 间的偏序关系( 优先加工约束，p r e c ) ，允许中断继续加工( p r m p ) 等。 3 y ：目标函数 目标函数一般根据实际需要来确定，在排序问题中常用的极小化目标函数一 般有：c 。，上，c ，弓( 总延误时间) ，“，( 总延误工件数) ， 产i产ij = l 圹妒甏可懈一叫n 扣 ( 加权完工时间之和) ，( 1 一p 一- ) 0 r 0 ，问题r 总存在多项式时间的( 1 + e ) 一近似算渤。，则称r 具多项式 时间近似方案( p o l y n o m i a lt i m ea p p r o x i m a t i o n s c h e d u m e ) a c 。进而，如果4 的 复杂性是关于输入长度和三的多项式函数，称r 为具有完全( f u l l y ) 多项式近似方 案，除非p = n p , 否则，强n p c 问题没有完全多项式近似方案。 第二章带学习因子的排序问题 2 1 引言 单机排序问题是最简单也是最重要的一类排序问题。单机排序问题已被相当 多地研究。在传统的排序中多数单机问题工件的加工时间给定且在序中是独立的。 在实际环境背景下，生产设备( 机器，一个工人) 由于相同或相似的行为加工能 力随着时间的推移而不断加强，其结果，一给定工件所需的加工时间在序中排于 后比排于前为少。这一称作为“学习因子”( l e a r n i n ge f f e c t ，简记为l e ) 的概念是 由w r i g h t ( 1 9 3 6 ) 提出的，虽然它在管理科学中已被相当多地研究。然而在排序问题 中还很少涉及，b i s k u p ( 1 9 9 9 ) 2 第一次把学习因子与排序问题联系在一起。本文即 是讨论带学习因子的排序问题。，并采用b i s k u p ( 1 9 9 9 ) 【2 】给出的下述基本假设： 有n 个给定的工件( 零件) l ，。，：，j 。在0 时刻可用。每一工件有一正常的 d n l 日寸r b ，i 件足标按最小加工时间排列即p 。! p ：s p 。，如果序中工件被排 在第一个，那么这个工件的加工时间是正常的，而后面的工件由于学习因子的作 用，它们的加工时间小于正常的加工时间。学习因子采用n a d l e r ，s m i t h ( 1 9 6 5 ) 3 】 和y e l l e ( 1 9 7 9 ) 4 提出的形式。给出。即若尸，代表工件i 在位置r 的加工时间则 b = p r “，a 茎0 ( a 称为学习因子) 。根据工件的序的位置很易计算不同工件的 加t 时间r 看表1 ) 12 n ，1只e 2 。 p 疗。 ，2最 只2 。县 4 j 。只 e 2 4只n 4 ( 表1 ) 文中出现一些变量和参数有： a ，：工件j 的超前惩罚因子，口，= 口表示所有工件的超前惩罚因子相同。 岛：工件j 的延误惩罚因子，岛= 卢表示所有工件的罚因子相同。 巳：工件j 的完工正常费用因子，g = 口表示所有工件的完工正常费用因 子相同。 巧：工件j 的到期日的正常费用因子，一= y 表示所有工件到期日的的正 常费用因子相同。 2 2 带学习因子的相关排序问题综述： 1 i 旧c ， ( 2 1 ) b i s k u p ( 1 9 9 9 ) 2 】应用两工件的相邻对交换原则证明，对问题( 2 一1 ) 依s p t ( s h o r t e d p r o c e s s i n gt i m en r s t ) 规则排列的序为一最优序，因此该问题o ( n l o g n ) 可解。 2 1 | d ，= d ，l e i ( c t e ，+ 卢l + 犯，) ( 2 - 2 ) b i s k u p ( i 9 9 9 ) 2 ( 2 2 ) 化为指派问题从而仍是0 f 月3 ) 可解。 i 哆= z i b 吗+ 弼+ 砌( 2 - 2 一1 ) 对问题( 2 - 2 - i ) m o s h e i v o “2 0 0 1 ) 5 】中将其化为加权指派问题，) h i i i i o ( n3 ) 可 。 3 i l e i c ( 2 3 ) 同样用相邻对交换原则m o s h e i v o r ( 2 0 0 1 ) 【5 】证明了问题( 2 - 3 ) ，s p t 序为最优的。 4 1 l d ，：d , l e s 宝c j + o - 占) ic 一c j l o j 1 ( 2 4 ) j = l i = 1j = l m o s h e i v o r ( 2 0 0 1 ) 在3 c 5 也将( 2 - 4 ) 化为加权指派问题从而d ( h 3 ) 可。 对于m 台平行机 ( 2 5 ) m o s h e i v o r ( 2 0 0 1 ) 6 指出存在这样的最优序，在每台机器上工件依s p t 规则排列 但用例子表明基于s p t 的l i s t 算法不一定最优。在文【6 】中，m o s h e i v o r 将( 2 5 ) 化 为一指派问题从而在m 给定时可多项式求 。 2 3 经典的排序理论和带有学习因子的排序理论 经典的排序理论和带有学习因子的排序理论中，我们看到( 2 - 1 ) 与钏z c j 都 是依s p t 序为最优的，( 2 - 3 ) l j1 1 1 7 _ c 也是相同的最优策略。在文【5 】中m o s h e i v o r 分别举例说明以下三种带有l e a r n i n g 的排序问题与经典的排序理论的最优序不 致，并指出这三个问题仍是o p e n 。 1 ) i i l e i z i o c ， ( 3 1 ) 经典的排序理论中，目标函数, 1 1 2 w ，c ，是依w s p t ( w e i g h t e ds h o r t e dp r o c e s s i n g t i m ef i r s t ) 最优的，即随着兰上的非降序来安排：r = 件的顺序，而这个规则对( 3 1 ) 刁i 是 最优的。 2 ) i i l e i l 。 ( 3 2 ) 经典的排序理论中，目标函数1 忙。即最大迟后问题是依e d d ( e a r l i e s td u ed a t e g t i m ef i r s t ) 规则最优的，即工件按d ，不减的顺序来安排工件，而这个规则对( 3 2 ) 不 是最优的。 3 ) i l e i u ，( 3 - 3 ) 经典的排序理论中，目标函数1 l u ，即最小误工数问题已被m o o r - h 。d g s o n 算法 解的，特别是j a c k s o n ( 1 9 5 5 ) 提出如果序中没有延误的工件存在，那么就按e d d 规 则可获最优序，但这些规则不适于( 3 3 ) 本文在第三章对带有l e a r n i n g 的加权完工时间之和、最大迟后、延误工件数 这三个目标函数给出了在相应一致性条件下，对应的w s p t 规则、e d d 规则、修 正m o o r e - h o d g s o n 算法仍可获最优序；并估计了在一般情况下由该三规则所获序 的误差。 第三章 一致条件下带学习因子的单机排序问题 3 1 加权完工时间之和问题 定理1 在一致性条件：p 。p ，w l ，v i ，下，w s p tj 亭5 ) b 1 陋i c ， = 1 的最优序。 证：在定理所给一致性下，以下三组不等式同时成立 p l p 2 一p 。，w l w 2 w ，p ll w i p 2 1 w 2 p h ，。 因此，序( 1 , 2 n ) 即为w s p t 序，其相应目标函数值 z = w l p l l 。十w 2 ( p 1 1 。+ p 2 2 4 ) + + k ( p1 。+ p 2 2 。十+ p 。门。) = ( w 1 + w 2 + + w ) p 1 1 。+ ( w 2 + + w ) p 2 2 。+ + u p 。 = o p ， 其中0 = ( w ，+ + l + + 1 ) ，4 ，= 1 , 2 ，”。显然，r j r j + i 且各0 达可能的 最小值，p p 川，= 1 2 ， 一1 ，因此由向量内积性质知z 达可能的最小值。定理 证毕。 若n 个工件间不存在定理所给的一致性条件，当用w s p t 序作为问题的时 如令z ( w s p t ) ，z ( o p t ) 分别表示相应w s p t 序和最优序对应的目标函数值 则有： 定理2z ( w s p t ) z ( o p t ) _ 0 。 由p 2 w 2 = ( 1 + e ) ( 1 0 + l l e ) 1 1 0 = p l w i ，得( 2 ，1 ) 为w s p t 序。 相应地z ( w s p t ) = 2 0 + 3 1s + l l c2 + 1 0 ( 2 。1 而相应序( 1 ，2 ) 的目标函数值z = 2 0 + 1 1s + ( 1 0 + 2 1 s + l l s 2 ) 2 “。 容易验证，当2 。 p i ) ，j 在i 前，现交 换工件j ，i 的位置得序疗，下证厅不差于丌。 设在行中工件j 第r 个加工，其开始加工的时间为c 。首先要证工件j 在万中 完工的时间不迟于工件i 在厅中的完工时间，即： c + 所，4 + p ，( r + 1 ) “c + p ，4 + 只( r + 1 ) 。，即 ( p j p i ) p + 1 ) 。( p ，一p i p 。 ，由p ， p i 口0 ，为正数知该不等式显然成 立。 现记工件i ，j 在序疗、- 中的迟后分别为) ，( z ) ，厶( 石) ，上，口) ，则有： m a x 厶衍) ，上，仿。) = m a x c + p i r a - 一，c + p i r a + p ，p + 1 ) 一哆 m a x 三( 玎) ，工如) j 2 m a x c + p j r a + 只( r + 1 ) 。d ，c + 乃r n d j 因此，由工件j 在刀中完工的时间不迟与工件i 在石中的完工时间，要证刀不差 于万 只要证 m a x l e ( x 1 ) ，( 丌) ；m a x 工，( 厅) ，( 丌) = c + p ，。+ p ，( r + 1 ) a d 。； 而由c + p ，r 。d ， d ( 因此p ，只) ，口o , r 为正数知该不等式显然成立。定理得证。 若n 个工件间= f f ；存在定理所给的一致性条件，当用e d d 序作为问题的时，如 令z ( e d d ) ，z ( o p t ) 分别表示相应e d d 序和最优序对应的目标函数值，则 有： 定理4 z ( e d d ) z ( o p t ) b 。、( 1 4 + 2 4 + + 胛。) 一d 。 b 。( 1 。+ 2 4 + i e ：不妨设d 。d 2 d 。，则有： z ( e d d ) = m a x 扫1 。+ p 22 4 + + p ，。一d ，：1 ，n _ o ，a o 且充分小。 对于此例，( 2 ，1 ) 为e d d 序，相应地： z ( e d d ) = m a x 1 0 + c 一( 1 一s ) ，1 0 + 6 + ( 1 0 6 ) 2 “一( 1 + s ) = 9 + 2 e 而相应序( 1 ，2 ) 的目标函数值 z = m a x l o 一一( 1 + ) ，1 0 一s 一( 1 0 + f ) 2 “一( 1 一) = 9 + ( 1 0 + 5 ) 2 。= z ( o p t ) z ( e d d ) z ( o p t ) = 9 + 2 【9 + ( 1 0 + s ) 2 “ 而 f 3 2 1 ) p ( 1 。+ 2 。+ + 月。) 一d 。m 】【p 。( 1 4 + 2 。+ + h a ) 一d 】 ：【( 1 0 + 占) ( 1 + 2 。) 一( 1 一e ) ( 1 0 一) ( 1 + 2 。) 一( 1 + e ) = 【9 + 2 + ( 1 0 + s ) 2 。】 9 2 6 + ( 1 0 一e ) 2 。】 ( 3 2 2 ) 显然，当a 0 且均充分小时，( 3 , 2 1 ) ，( 3 2 2 ) 均趋于l ，故定理4 中所给的上 界是精确的。 3 3 延误工件数问题 引理1 吲s p t 序为问题1i i l e i c 的最优序 引理2 p i , a 2 一玩p 0 ，则序( f 。，己，i 。) 的加工全程不超过任一形式 为( i if 2 ，+ i ，+ 1 ) ，k 1 , 2 ，m ) ，的序的加工全程。 证：设序( f 。，f 2 ，i 。) 加工全程为z 。，序( ，f ：，i 。，。f 。) ，t 1 , 2 ，嘲的加i 工全程为z ，则 z l z 2 = ( p 1 1 “+ p b2 “+ + p k ，玎。) 一 p ，i 。+ p ，：2 。+ + p “一( 七一1 ) 。+ p “+ k “+ 十p h + m 。1 = ( p 一p k ) 七。+ + ( p k p k ) 。0 引理获证。 修正m h ( m o o r e h o d g s o n ) 算法 初始过程：令已排工件序，= ( 妒) ，“= 妒 ，将工件集 i ，2 ，n 中的工件序依 e d d 序排列，得序j 。= ( _ ，；，。， ) ，令k = l 循环过程：取出，。中排于最前的工件。放于j 的最后，得新的己排工件序j = ( j ，j 。) 。如在j 中如期完工则令j 。= j ：如在j 中j 。为延误工件，则 从j 中去掉一工件使j 中剩余工件的加工全程最短( 如有多个这样的工件，取足标 最大者) ，并将去掉的工件放于j 。中，记最后所得的j 为j 4 。若k = n ，则以序 ( j 。，4 ) 。其中j 。中的工件依任序排列，作为原问题的解，否则令j = 以，k ：= k + 1 转回循环过程。 注：在原( m h ) 算法中，当 放于序j 尾成为延误工件时，从已排工件序 去掉加工时间最长者，在修正( m h ) 算法中将其改为从已排工件序去掉一工件 使j 中剩余工件的加工全程最短，两者效果是一样的，因此有： 定理5 在一致性条件：d i d jjp ，p j ， v i 下，修t m 聪法可获问题h 善的最优序。 证：不妨设矾d 2 玉兰d，则在定理条件下也同时有p 。p 2 s p 。 令t ，。为由工件集t = 1 , 2 ，k ) 中工件所组成，且满足下列条件( a ) ，( b ) 的这样 个序： ( a ) 以中工件全部如期完工，且数量达最大可能数，比如说月+ ( b ) 如由c 。中工件可组成多个这样的序使满足( a ) ，则，。是其中所有工 件中加工全程最短者。 现归纳证明，由修_ i _ i 三( m h ) 算法构造的j ；，! ，j 。满足( a ) ，( b ) 。 相应k = l ，由于，= ( ) 或i ，l = ( 1 ) ，依p 是所有：【：件中加工时间为最短者 知，j 。满足( a ) ，( b ) 。 i 殳棚应k = m ，c 。= 1 ；2 ， 由修正m 1 1 算法构造的j 。满足( a ) ，( b ) ，现证 对k = m + l ，由修正m h 算法构造的以也满足( a ) ，( b ) 。 情况1 若序，+ 1 ) 中，工件m + l 为如期完工工件。对于此时的 ，。= ( ，m + 1 ) ，由于在c 。中不可能构造一个比，。 如期完工工件数 还多，同时其最后一个工件m + l 又必须包含在其中的序，因此算法所得的，。为 c 。+ 中具总加工时间最少的这样一个序，即 情况2 若序( j 。，m + 1 ) 中，工件m + l 为延误工件。此时由于，是从c 。 中取出的具最大完工工件数且满足( a ) ，( b ) 的序知，t 。= ”。，且依引理2 知修 i e ( m h ) 算法在将m + l 附于j 。后再去掉的工件也为工件m + l ，即此时的，。= j 。 是在如期完工工件数为的条件下从c 卅。中取出的具总加工时间最少的这样一个 集合，即，。满足c a ) ，( b ) 。 最后证排于，。后，。中的工件依任意序排列均为延误工件。依引理2 及一 致性条件知，在任阶段可能去掉的工件是该阶段新进入的工件。设工件m j 。是 在阶段m 去掉的工件。那么由m 在( ，。，) 中为延误工件，及巴只+ 只 知它无论处于 。后什么位置均为延误工件。 证理完毕j 若n 个工件间不存在定理所给的一致性条件，当用修正( m h ) 算法时， 如令z ( 修正m h ) ，z ( o p t ) 分别表示相应修i em h 算法和最优序对应的目 标函数值，则有： 定理6z ( o p t ) z ( 修正m h ) n 证：只要谣测应z ( o p t ) = n 时的z ( 修正m h ) 1 即可。 不妨设d isd 2 ，sd 。，最优序为( i i ，f 2 一f 。) ，且在最优序：i 卅二1 第n 1 ，m 21 个加1 ：，那么由z ( o p t ) 一n 知p “1 “+ p k2 “+ + p 聊“d ，其中，。= i ，由此 p t 。1 ds d j 曼d l , 这样，当用修正m - h 算法时，如果依此从j 。= ( 1 , 2 ，n ) 中取出工件放 入j 时已有工件如期完工，则定理获证；如果依此从j 呸( 1 , 2 ，n ) 中取出的排 于工件i 。前的工件均为延误工件，则修正m h 算法下一步取的工件为i 。，由于 p ，。l 。d 。，因此工件f l 如期完工，而z ( 修正m h ) 1a 证理完毕。 定理6 中所给的上界是精确的，例： 令n = 2 ，p i = 6 ，d l = 1 2 ；p 2 = 1 0 ，d 2 = 1 1 ，口= 一1 对于此例，( 1 ，2 ) 为最优序，( 2 ，1 ) 由修正m h 算法得，相应地 z ( o p t ) - - 2 ，z ( 修正m h ) = 1 。 参考文献： 1 】g r a h a m ，r l ，e l l a w l e r , j k l e n s t r aa n da h g r i n n o o y , k a n o p t i m i z a t i o na n d a p p r o x i m a t i o ni nd e t e r m i n i s t i cs e q u e n c i n ga n ds c h e d u l i n g a n n d i s c r e t em a t h ， 5 ( 19 7 9 ) ，2 8 7 3 2 6 【2 】b i s k u p ，d s i n g l e m a c h i n es c h e d u l i n gw i t hl e a r n i n gc o n s i d e r a t i o n s e u r o j o p e r r e s ，11 5 ( 1 9 9 9 ) ，3 0 2 3 2 8 【3 n a d l e r , ga n d s m i t h ，w d ，m a n u f a c t u r i n