（运筹学与控制论专业论文）供应链管理中的若干排序问题研究.pdf

供应链管理中的若干排序问题研究 摘要 本文主要研究供应链管理中的若干排序问题，即工件可以进行外包加工的一 种新的排序模型和带批处理的流水作业问题。全文共分为三章。 第一章是绪论部分，介绍了组合优化和排序问题，算法的时间复杂性与近似 算法等基本概念。 第二章主要研究基于机器排序的工件外包问题，证明了这个问题等价于一个 子集和问题，从而证明该问题也可以在o ( n p ) 时间复杂性内加以解决，还提出了 针对该问题的算法4 和近似算法4 ，并且证明了算法4 是f p l a s 。 第三章主要研究带批处理的流水作业问题e 专d i b ，v = l ，k = 1 l l ，给出了 e 专d l b ，1 ，= 1 ，k = l i c m 缸问题的混合整数规划模型，通过3 一划分问题( 3 一卯) ， 证明了e d l b ，1 ，= 1 ，k = , i c o 。是强n p 难的。在工件加工顺序给定的情况下， 我们给出了该问题的启发式算法，证明了该算法最坏情况界是2 ，而且是紧界。 关键词：排序，近似算法，动态规划 供应链管理中的若干排序问题研究 a b s t r a c t t h i st h e s i sm a i n l yc o n c e r n san e w s c h e d u l i n gm o d e lf o raf i r m 、7 i ，i t ha no p t i o no f o u t s o u r c i n ga n daf l o ws h o pp r o b l e m 、析t l lab a t c h i n gm a c h i n e w ef i r s ti n t r o d u c e b a s i cn o t i o n so fs c h e d u l i n gp r o b l e m ，a p p r o x i m a t i o na l g o r i t h m sa n dc o m p e t i t i v e a n a l y s i s i n c h a p t e r2 ，w ei n v e s t i g a t et h eo u t s o u r c i n gs i t u a t i o n sw h i c hb a s e do n a s c h e d u l i n gp r o b l e m w ep r o v ei te q u a l st oas u b s e ts u mp r o b l e m ，t h u st h ep r o b l e m c a nb es o l v e db yad y n a m i cp r o g r a mi no ( n p ) t i m e w et h e nd e v e l o pa na l g o r i t h m 4 a n da p p r o x i m a t i o na l g o r i t h m4f o rt h ep r o b l e ma n dw ea l s op r o v e4t ob e f p t a s i nc h a p t e r3 ，w ei n v e s t i g a t eaf l o ws h o pp r o b l e mw i t l lab a t c h i n gm a c h i n e e - - - d l b ，v = l ，后= li c m 。w e f o r m u l a t et h e p r o b l e m f i t sam i x e d i n t e g e r p r o g r a m m i n gm o d e l w ea l s os h o wt h a tt h ep r o b l e mi ss t r o n g l yn p - h a r db ya r e d u c t i o nf r o t h3 - p a r t i t i o n ，w h i c hi sk n o w nt ob en p h a r di nt h es t r o n gs e n s e w h i l e t h ep r o c e s s i n go r d e ri ss e t ，w ed e v e l o pah e u r i s t i ca l g o r i t h ma n dp r o v e2t ob et h e w o r s tc a s er a t i o w ea l s os h o wt h et i g h t n e s so ft h eu p p e rb o u n do ft h eh e u r i s t i c a l g o r i t h m k e yw o r d s ：s c h e d u l i n g ，a p p r o x i m a t i o na l g o r i t h m ，d y n a m i cp r o g r a m m i n g 供应链管理中的若干排序问题研究 第一章绪论弟一早珀下匕 1 1 组合优化和排序问题 组合优化问题又称离散问题，是一类重要的优化问题。随着计算机科学、管 理科学和现代化生产技术等的日益发展，这类问题与日俱增，越来越受到运筹学、 应用数学、计算机科学及管理科学等诸多学科的高度重视。组合优化一个通俗的 定义是指在离散的有限的数学结构上，寻找一个( 或一组) 满足给定约束条件并 使其目标函数值达到最小或最大的解，其正式定义如下： 组合优化问题是一个极小( 大) 化问题，它由下述三部分组成： ( 1 ) 实例集合； ( 2 )对每一个实例j ，有一个有穷的可行解s ( ，) ； ( 3 ) 目标函数厂，它对每一个实例，和每一个可行解盯s ( ，) ，赋以一个有理 数f ( i ，仃) 。 如果该问题是极小( 大) 化问题，则实例，的最优解为这样一个可行解盯s ( ，) ， 它使得对所有的盯s ( ，) ，都有f ( 1 ，仃+ ) f ( 1 ，仃) ( 厂( ，仃) f ( i ，盯) ) 。 组合优化问题涵盖甚广，常见的组合优化问题有分划问题( p a r t i t i o n ) 、排 序问题( s c h e d u l i n g ) 、装箱问题( b i np a c k i n g ) 、背包问题( k n a p s a c k ) 、指派问 题( a s s i g n m e n t ) 、旅行售货商问题( t r a v e li n gs a l e s m a np r o b l e m ) 、斯坦纳最小 树问题( s t e i n e rm i n i m a lt r e e ) 等，网络中的组合优化问题还包括最短路问题 ( s h o r t e s tp a t h ) 、最小生成树问题( m i n i m a ls p a n n i n gt r e e ) 、最大流问题 ( m a x - f l o wp r o b l e m ) 、最小费用问题( m i n - c o s tf l o wp r o b l e m ) 等等。在此，我 们只对本文研究的排序问题作一介绍。 排序( s c h e d u l i n g ) 理论是研究如何在满足一定要求下，对需要完成的任务进 行统筹安排使得到的结果在某种意义下达到最优，它有着重要的理论意义和广泛 的应用背景。排序理论与理论计算机科学和离散数学结合紧密，并广泛应用到生 产计划调度、信息处理、物流管理、服务行业等领域，这些新兴领域的蓬勃发展 不仅使经典问题的研究不断深入，而且还涌现了许多有实际背景的新问题。排序 研究己成为目前组合优化领域最活跃的分支之一。 供应链管理中的若干排序问题研究 根据排序研究的最初背景，我们通常把需要完成的任务称为工件( j o b ) ，把 完成任务需要的资源称为机器( m a c h i n e ) ，我们希望找到一个可行的排序 ( s c h e d u l e ) ，使得某个给定的目标函数达到最小( 大) 。这里的可行一般是指在同 一时刻，一台机器至多加工一个工件，一个工件也只能在一台机器上加工，并且 该排序满足问题特定的约束要求。描述一个排序问题可用所谓的“三参数表示法 ( t h r e e f i e l dr e p r e s e n t a t i o n ) 口厂 1 5 ，其中口，7 分别代表特定的 机器环境、工件特征和最优准则，它们是排序问题的三个组成部分。 机器环境用来描述机器的数量、不同机器之间的关系等与机器有关的性质。 常见的机器系统包括单台机( s i n g l em a c h i n e ) 、平行机( p a r a l l e lm a c h i n e s ) 、 流水作业( f l o ws h o p ) 、异序作业( j o bs h o p ) 和自由作业( o p e ns h o p ) 等。在本 文中，我们着重讨论流水作业排序问题，即机器数至少为2 。 工件特征一般可用工件的加工时间( 也称为工件长度) ，工件的释放时间，工 件相互之间的依赖关系等来描述。根据排序者对工件信息的了解程度，又可将排 序问题分为离线( o f fl i n e ) 、在线( o nl i n e ) 和半在线( s e m i o n l i n e ) 等。如果排 序者在排序开始前就己知工件的全部信息，例如工件数，每个工件的加工时间等， 则称该问题是离线( o f fl i n e ) 的。反之，如果工件的信息是随着排序过程一个 个地依次释放的。具体地说，只有在位于某个工件前的全部工件均被安排完毕后， 排序者才能知道该工件的有关信息，而且工件一旦被安排就不能改变。这样的排 序问题称为在线( o nl i n e ) 的。而半在线( s e m i o n li n e ) 是指排序者掌握的信息位 于在线和离线之间。 最优准则，就是以什么为目标函数。一个最优化问题的优化目标通常是一个 一维实数，我们用e 表示某一排序工件以的完工时间，f = 1 ，2 ，刀，用三，表示在 某一排序机器鸩的完工时间，_ ，= 1 ，2 ，m ，记巴= m 。“a x 。c ，巴= m 。搿a 拥x ：，, 别称为最大机器完工时间和最大工件完工时间( 极小化目标) 。常见的其它目标 函数还有总完工时间、最大延误时间、最大误工时间等，在此我们就不一一介绍 了。 2 供应链管理中的若干排序问题研究 1 2 算法时间复杂性和近似算法 排序问题的算法( a l g o r i t h m ) 是指一个预先制定的执行程序，对这个排序问 题的任何一个具体的例子( 简称为实例，i n s t a n c e ) ，按照这个程序操作后都可以 得到一个可行的排序。解离线问题的算法称为离线算法，相应地，解在线问题的 算法称为在线算法。 将实例通过某种规则编码后输入计算机所占用的字节数称为该实例的输入 长度。每一个可能的输入长度，算法解此输入长度的最坏可能实例所需的基本运 算次数( 如加法、乘法、比较等) 称为该算法的时间复杂性( 函数) 。如果存在一个 多项式函数p ( n ) ，使得算法的时间复杂性为d ( p ( 刀) ) ，那么称该算法为多项式时 间算法，否则称为指数时间算法。伪多项式时间算法是一类特殊的指数时间算法， 它的时间复杂性是关于实例输入长度n 和实例中最大数的二元多项式函数。由此 出发，可以导出计算复杂性理论的一系列重要概念和结论 1 2 。 一个组合优化问题，如果已经找到了多项式时间算法，那么就称它为多项式 时间可解问题。把所有这样的问题集合记为尸，因此多项式时间可解问题就称为 p 类问题。我们称答案为“是”或“否”的问题为判定问题。给定一个判定问题， 如果存在一个算法，对任何一个答案为“是”的实例，该算法首先给出一个猜 想，该猜想规模不超过，的输入长度的某个多项式函数，且验证猜想的正确性仅 需要多项式时间，则称该问题为n p 类问题。 对于两个判定问题蜀，如果对乃的任一的实例厶，可以多项式时间构造 出乃的一个实例厶，使得厶的答案为“是”当且仅当厶的答案为“是 ，则称蜀 可以多项式归约到乃。如果蜀可以多项式时间归约到乃，而码有多项式时间算 法，则乃也有多项式时间算法。 鉴于7 0 年代建立起来的计算复杂性理论，以及几十年来人们在这方面的努 力，现今p n p 的猜想已经为多数人所接受：如果我们接受p n p 的猜想，那 么对于所谓的胛一难问题就不可能存在多项式时间内找到最优解的算法。因此 一个很自然的想法就是放弃对最优解的寻找，而寻找某种有性能保证的可行解， 我们称之为近似解，从而换取可接受的计算时间，这就是所谓的近似算法 3 供应链管理中的若干排序问题研究 ( a p p r o x i m a t i o na l g o r i t h m ) 的思想。经典的求解平行机排序问题的离线和在线 问题的近似算法分别是l p t 算法 1 3 和l s 算法 1 4 。衡量近似算法的优劣可从 两个方面来看，一是算法的时间复杂性，二是它得到的解值与最优解值的接近程 度。 设彳是求解一个极小化问题的一个近似算法。称 兄= i i l f ，1 i c _ ( d 圮钟( ，) ，v i p ) 为算法彳的最坏情况界( w o r s t - c a s er a t i o ) ( 对于离线情形) 或竞争比 ( c o m p e t i t i v er a t i o ) 1 8 ：1 9 ( 对于在线和半在线情形) ，这里c ( ，) 和c d p 7 ( ，) 分 别表示算法a 解实例i 所得的目标函数值和相应问题离线情形的最优目标值，同 样地，对极大化排序问题，称 毛= i i l f 厂 l l c 粥( ，) s 心爿( ，) ，v i p ) 为算法a 的最坏情况界( w o r s t - c a s er a t i o ) ( 对于离线情形) 或竞争比 ( c o m p e t i t i v er a t i o ) ( 对于在线和半在线情形) 。 如果某问题有一系列近似算法 4 ) ，对任意给定的6 - 0 ，4 是一个多项式 时间算法，而且心1 + g ，则称它为多项式时间近似方案( f r a s ) ；进一步，如 果4 的复杂性是以输入长度及二的某个二元多项式为界，则称为完全多项式时 占 间近似方案( f p t a s ) 。 4 供应链管理中的若干排序问题研究 1 3 论文综述 本文主要研究了供应链管理中的若干排序问题，即考虑工件可以进行外包加 工的一种新的排序模型和带批处理的流水作业问题。第一章介绍了组合优化和排 序问题，算法的时间复杂性与近似算法等基本概念。第二章研究基于机器排序的 工件外包问题，证明了这个问题等价于一个子集和问题，从而证明该问题也可以 在o ( n p ) 时间复杂性内加以解决。本章还提出了针对该问题的算法4 和近似算法 4 ，并且证明了该算法4 是f p ，i a s 。第三章研究带批处理的流水作业问题 五专db ，v = l ，后= l l c m 缸，给出了e d l b ，v = l ，七= l l c 础问题的混合整数规划 模型，通过3 一划分问题( 3 - p p ) ，证明了e 专d l b ，v = l ，k = 1 l c 懈是强n p 难 的。在工件加工顺序给定的情况下，我们给出了该问题的启发式算法，并且证明 了该算法的最坏情况界是2 ，而且是紧界。 5 供应链管理中的若干排序问题研究 第二章考虑工件外包加工的1 + 10 问题 2 1 引言 本章研究工件可以进行外包加工的一种新的排序模型。外包加工 ( o u t s o u r c i n g ) 2 2 这种方式已经越来越多地被实际生产所采用。一方面，它 可以降低运营成本，另一方面，当订单数目过大时，还可以克服驻地加工 ( i n h o u s ep r o d u c t i o n ) 生产能力有限的缺点，但是，生产商要支付子承包商 一定的加工费用，而且外包的工件一旦加工完成，从子承包商回到生产商还要考 虑必要的运输延时和运输费用。 基于机器排序的外包问题，吸引了越来越多的人进行研究。很多人研究了驻 地生产和外包生产的库存管理问题，如a t a m t u r k 和h o c h b a u m 2 ，b r a d l e y 4 ， v a nm i e g h e m 2 8 ，y a n ge ta l 3 0 。c h u n ge ta 1 1 0 研究了可以进行外包加 工的j o bs h o p 的一个模型，这个模型考虑了外包加工的费用，但忽略了运输费 用；c h e n 和l i 7 在考虑带外包加工的排序问题时，假设外包加工的机器的处 理容量无限，因此对于外包加工的工件，就无需考虑这些工件的处理序列问题； c a i ，l e e 和v a i r a k t a r a k i s 6 研究了第三方加工机器的模型，但模型中只考虑 工件全部由第三方加工机器加工，工件加工完后再从第三方加工机器运回到原 地。 本文考虑了驻地加工的机器和外包加工的机器都只有一台的情况。假设一台 机器要处理刀个工件，为了使这些工件尽早加工完毕，我们考虑将其中一部分工 件交给一个子承包商进行外包加工，但外包加工也带来了新的问题，即外包加工 的费用，运输费用和运输延时。记见为工件五的驻地加工时间，则当五被外包 加工时，它的加工时间为a p k ，口表示外包机器的处理速度；它的外包费用为 仇，表示工件的外包加工费用与其加工时间有关。我们用1 + l0 c t 眦表示该问 题，第一个1 表示驻地加工的机器的数目，第二个1 表示外包加工的机器的数目， 目标是设计一种有效的加工方案，从而使得完工时间c m 戤和总费用尽可能小。 以下是本章用到的记号： j = j 。1 , 五， ) 表示所需加工的工件集； 6 供应链管理中的若干排序问题研究 以= 五i 五在原加工地加工) ； 以= 五i 五在外包加工地加工) ，以= g 表示不采用外包加工； 仇：工件五在原加工地的加工时间； a p k ：工件五在外包加工地的加工时间，其中口表示外包机器加工速度； 见：工件五在外包加工地的加工费用； f ：驻地到外包地来回一次所需的时间； k ：驻地到外包地来回一次所需的费用； p ：总加工时间，尸= 乃； j = l 尸( x ) ：x c _ j 中的工件总加工时间，即p ( x ) = p j ； p | t x p ( 以) ：驻地加工工件的总加工时间，p ( 以) = 乃； p ( 以) ：外包加工的工件的总加工时间，p ( 以) = 乃。 p j + 4 q i 2 6 指出l + l0 问题等价子一个子集和问题，我们在此给出了具体证 明。本章首先给出了基于子集和问题动态规划的伪多项式时间最优算法，然 后对任意的占 0 ，给出算法4 ，其最坏情况界不超过1 + 占，因而得到了该问题 的f p t a s ，最后还给出一个最坏情况界不超过1 + 貉的多项式时间近似算 法4 。 7 供应链管理中的若干排序问题研究 2 2 子集和问题 子集和问题：给定正整数集彳= 口l ，呸， 和正整数b ，找彳a ，使得 吩b 且吩尽可能大。即： 巳e a a e a m a x ) - x j = l 豇吩专b 一j j j = l 0 , 1 我们用s s p ( a ，b ) 表示上述问题，称b 为子集和问题的容量。子集和问题属于脚 完全问题 1 2 。 反子集和问题：给定正整数集肛 q ，a 2 ，) 和正整数曰，找彳a ，使得 吩b 且哆尽可能小。即： a j e a a e a m i n 乃弓 = l 豇乃一b 一j j j = l o ，1 ) 我们用m s s p ( a ，b ) 表示上述问题。 r e b e l l m a n 在 3 中提出了解决s s e ( a ，b ) 问题的b e l l m a n w i t h l i s t s 算 法；h k e l l e r e r ，u p f e r s c h y ，d p i s i n g e r 2 0 指出s s p ( a ，召) 问题可以通过动 态规划算法在伪多项式时间内达到最优。j o h n s o n 1 9 第一次提出了子集和问题的 多项式时间近似方案，接着被m a r t e l l o 和t o t h 2 4 改进。i b a r r a 和k i m 2 7 1 第一 次提出了子集和问题的完全多项式时间近似方案。对于反子集和问题，b a b a t s 给出了时间复杂性为d ( ) 的f p t a s ，g e n s 和l e v n e r 1 6 给出了时间复杂性为 s 8 供应链管理中的若干排序问题研究 d ( 鸟的胁s 。 引理1 ：记以b 为容量的子集和问题的最优解为a ，以a j - b 为容量的反子集 和问题的最优解为么”，则有a - 么么”。 证明：令咒= l - x ，则薯= l 一只。将其代入脚( 彳，a j b ) 可得： 即： 所以，a = 彳a ”。 m i n ( 1 - y j )j _ j 旺巳( 1 一乃) 哆- b y j o ，1 ) m a x a j y j s 1 n j y j b 一j o j 乃 0 , 1 9 供应链管理中的若干排序问题研究 2 3l + l0 c 懈问题和其相关算法 我们首先给出问题的复杂性证明。 定理1 ：l + 1 0 0 问题是n p 难的。 证明：不难发现在k = o ，f = 0 ，口= l ，p = o 时，1 + l0 0 问题退化为两台平行 机排序问题p 20 c 慨，而尸20 0 是n p 难问题，所以1 + 10 c 雠也是n p 难的。- 上述定理告诉我们该问题不存在多项式时间最优算法，而由下面定理2 可知 算法么是该问题的一个伪多项式时间最优算法，因此1 + l0 c m 戡是普通意义下的 n p 完全问题。在给出算法么之前，我们先指出最优解的一些性质。 引理2 ：最优解只运输一次工件，即在所有外包工件完工后将其运回。 证明( 反证法) ：否则，若最优解在所有外包工件完工前有部分外包工件先被运 回，则最优解中将有至少两次运输费用。而如果将最优解的外包工件作为一批运 输，那么一方面由于所得的排序仍与原排序相同，所以完工时间不会发生改变， 另一方面运输的费用只有一次，即我们得到了目标值比原来更小的方案，这与原 来方案的最优性矛盾。 由此，算法的外包工件只需要运输一次，所以问题简化为只要选出外包的工 件即可。 引理3 ：如果算法将以分给外包加工，且以o ，即尸( 以) = x 0 ，则算法的目 标值为厂( x ) = m a x p - ( 1 - t i ) x ，( a + t i ) x + r ) + k 。 证明：显然尸( 以) = p x ，于是该算法完工时间为m a x p ( 4 ) ，a p ( d 2 ) + r ，由引 理2 运输费用为k ，外包费用为t i p c j 2 ) ，所以算法的目标值为： f ( x ) = m a x p ( d 1 ) ，a p ( a ) + r + t i p ( a ) + k = m a x p - x + t i x ，( a + t i ) x + r ) + k = m a x 尸一( 1 一) x ，( o t + t i ) x + r + k ( 1 ) 一 1 0 供应链管理中的若干排序问题研究 引理4 ：函数f ( x ) = - - ( 1 - f 1 ) x + k ，, x 复p - z 且在等减， ( 口+ ) 卅+ 疋石而 1 + 口 在x 导兰单调递增。 _ l 十口 引理5 ：当f ( x ) p 时，所有工件都驻地加工是最优方案。特别地，当1 或f p 时，所有的工件应驻地加工。 证明：显然不采用外包加工的目标值为p ，所以根据引理3 ，若采用外包加工的 目标值f ( x ) p ，则没必要使用外包加工地，即所有工件都驻地加工是最优方案。 当运输时间r p 时，采用外包的目标值显然大于尸，所以工件应驻地加工。又 当l ，p - ( i p ) p ( 4 ) = 尸一( 1 - f 1 ) x p ，由( 1 ) 可得采用外包的目标值 f ( x ) p ，因而此时驻地加工还是最佳方案。 _ 以下不妨设 1 ，f 0 ，我们给出该问题的f p t a s 。 算法4 ： 1 调用s s p ( ，拿兰) 的f p t a s ，界为百l+占(1-f1)， 得到以。 i + 口 l 十s 2 i 周用m s s p ( ，导兰) 的f p t a s ，界为1 + 占，得到以。 l + 口 3 计算f ( p ( j 2 ) ) ，f ( p ( 4 ) ) ： 3 1 如果i i l i n ( 尸( 以) ) ，f ( p ( d 2 ) ) ) p ，输出f 2 j ，停止； 3 2 如果f ( p ( j 2 ) ) 厂( p ( 以t - ) ) ，输出以。，停止； 3 3 否则，输出以。，停止。 在讨论算法4 的最坏情况界之前，我们先给出几个有用的引理。 引理6 ：若含，+ 哩含s t + 凸则剃+ 占 证明：不妨设a l a 2 ，则： m i n a i ，a 2 ) = a l ， 1 2 供应链管理中的若干排序问题研究 而 所以， 垒垒件占， b 2b 2 垒l + g ， b 1 m i a l ，a 2 m i n b l ，b 2 ) 1 + 占。 一 引理7 ：尸( 以) j p ( 以。) _ 去乏旦，p ( 以。) 尸( 以”) l + g 。 证明：根据引理l ，算法彳第2 步中得到的以= ，以就是m s s p ( ，毛芸) 问 p r 题的最优解，再由算法4 的第2 步，所以有尸( 以) p ( 以”) 1 + 占。 另外，算法彳第1 步得到的以；是s s p ( ，三三) 问题的最优解，显然 姒) 聃) 警。 _ 定理3 ：算法4 的最坏情况界不超过1 + 占，因此是求解该问题的一个f p t a s 。 证明：f l 了p ( 2 ) 鲁若以及p ( 以) 詈苦，所以根据引理4 ， f ( p ( 4 。) ) = 尸一( 1 一) p ( 以) + k ，f ( p ( j x ) ) = 尸一( 1 一) p ( 以) + k 。 下面证明勰 1 + 占，显然勰丽p - ( i - p ) p ( j 2 ) 。 由引理7 ， 1 上- _ 生 姒) p ( j 2 ) 等， 所纠 。 且p ( 以) p ，所以， ! ! 盟丛生：2 二竺竖2 三 p ( 以。) 1 一 供应链管理中的若干排序问题研究 ! ! 三塑墨：! 二! 丝! ，由( 2 ) ，( 3 ) 以及引理6 ，所以 筹m s 。- 算法4 ： 令= 五l 仇詈苦) ，令八以中最小的工件为z ，其加工时间为b 。 1 如果以= a ，则 i i 若厂( 研) p ，输出五，停止； 1 2 若厂( b ) p ，输出o ，停止。 2 如果互乃而p - - t ，则 。 3 1 若m i n f ( p ( d 4 ) ) ，厂( 仍) ) p ，输出a ，停止； 3 2 若f ( p ( j 4 ) ) 厂( 只) ，输出以，f f a ； 1 4 垡窒壁笪里生塑董王壁壁塑望婴窒 一_ _ _ - 一一 3 3 输出j l ，停止。 3 如果荟矿等，将中工件按照其力n 工时间的不增j 唳序排列，按此j 哽序， 将以中的工件尽可能多地分给外包加工，使得当前外包加工工件的总长度不 超过_ e - r ，设得到的工件集合为互，则 l + 口 3 1 如果( p ( 以) ) p ，输出o ，停止； 3 2 输出以，停止。 引理8 如果算法进入第步，则有1 2 三1 + 二三a 互1 而p - r ，另一方面中的工件加工时间都不小于b ， 所以p ( 以) a 互ii p - 石v ，矛盾! _ 定理4 ：算法4 的最坏情况界不超过m a x 1 + 荔2 再0 - i p j ) ，1 ) 。 证明：情形1 如果= f 2 j ，即每个工件的加工时间都大于毛：，则算法目标值 为c ：n f i n f ( p , ) ，一。而对最优解，如果不采用外包，则c = p c ；否则， 最优解外包的工件加工时间总和必大于菩二三，由引理4 ，c 厂( 易) c 。 l 十口 情形2 如果以彩且互马百e - i r ，则由算法，c = 1 1 1 i n 厂( p ( 以) ) ，( 只) 一。 设最优解外包加工的工件集合为万，不妨万a ，即最优解采用了外包，此时由 引理3 ，c = 厂( p ( z ) ) 。若p ( 乃鲁署，则万山，根据引理4 ，则有 c = 厂( p ( 乃) 厂( p ( 以) ) c ，。否则，尸( _ ) 等，所以尸( _ ) 另，同样由引 理4 可知c 厂fp 、l c 。 供应链管理中的若干排序问题研究 情形3 如果a 且善岛 而p - r ，算法进入第3 步，于是算法所得的目标值 c ：m i n 厂( p ( _ ) ) ，p ) m i n 厂( 导兰) ，p 。根据引理8 ，中工件加工时间总和 l + 口 满足三而p - t 互乃p 1 - _ _ z r 所以再由弓l 理3 ， 厂( p ( 以”= 尸一( 1 一) p ( 以) + k 尸一( 1 一) 丢而p - t - + k 。 厂( 尸( 以”，尸一( 1 一) i l 而p - r 厂( 筹) 一h w ) 等 1 二巫1 - 互f l 二二型二：! 巫r 一( 1 一掣) p 一( 1 一) 二 1 + 口1 + 口 ，丽1 - pr + - t i 历击 。1 + 嚣茹鬟 2 ( 芝一1 ) p f 、1 一 7 ：1 + 三! ! 二丛 2 卢+ 口一1 最后由引理6 ，等1 + 乏2 丽( 1 - f 1 ) 。 1 6 一驴 l 矽舂兰 1 2 一卜 + +11l 一 = 供应链管理中的若干排序问题研究 第三章带批处理的流水作业问题 3 1 引言 在工业生产和配送系统中，加工完的工件都要被运到仓库或客户手中，因此 做好机器排序和工件运输之间的协调就显得尤为重要。本章主要研究带批处理机 器的生产和运输问题，相关的文献主要可以分成两大类，一类研究带运输的机器 排序问题，l e e 和c h e n 2 1 把运输分成两种情形，第一种情形是考虑把半成品 运到另一台机器进行下一步加工，另一种情形是把已经加工完毕的工件运到仓库 或客户手中。两种情形都考虑了运输容量和运输次数；l e e 和o u 2 2 考虑了两台 加工机器位于不同的地方，每一个工件由两部分组成，并且这两部分工件分别在 这两台机器上加工，加工完后运到配送中心将这两部分组装成套。l i 和 v a i r a k t a r a k i s 2 3 考虑了两台加工机器在同一个地方，每一个工件由两部分组 成，并且这每个部分在指定的机器上加工，待两部分都加工完毕后，将这两部分 组装成套进行运输。c h e n g 和k a h l b a c h e r 8 ，c h e n g 和g o r d o n 9 ，w a n g 和 c h e n g 2 9 考虑了成批运输工件；h a l l 和p o t t s 1 7 考虑了在供应链系统 中将排序费用和运输费用相结合的各种问题，但没有考虑运输容量的限制。 第二类研究带批处理机器的相关问题。a h m a d ie ta 1 1 考虑了两台机或三台 机的f l o ws h o p 中至少有一台是批处理机器的一系列问题，但这些问题都仅考虑 了生产层面的排序，而没有结合实际生产中与费用密不可分的运输。 本章研究的目标是带批处理的流水作业问题e 专d l b ，= 1 ，后= l i c 蚴，加工 一个工件要经过两道工序，分别在m 和鸠上完成，m 为单件加工机器，一次 只处理一个工件，工件，在其上的加工时间为f 门，鸩为批处理机器，在它上 面加工的工件，可以单独加工，也可以进行批处理，且批处理的时间均相同，记 为丁。m 有一个批处理容量，记为c ，即m 上每批最多加工c 个工件。工件只 有在其所在批的所有工件都加工完毕以后才能被运输。运输车辆只有一辆，且一 次最多运一个工件，工件，运往目的地的时间为t 车辆的返回时间都相同，记 为， 带批处理的流水作业问题在实际生产生活中具有广泛的应用，例如钢铁厂炼 供应链管理中的若干排序问题研究 优质钢时，首先将原材料进行分拣加工，然后分批将其高温熔化成钢水，统一浇 铸到已有的模具中。浇铸完的钢铁根据其用途被运到不同的地方，为了考虑问题 的方便，本文设运输工具返回钢铁厂的时间均相同。本章给出了 ej d l 曰，v = l ，k = 1 l 问题的混合整数规划模型，通过3 一划分问题( 3 一即) ， 证明了e 专d i 曰，1 ，= l ，k = 1 i l 是强n p 难的。在工件加工顺序给定的情况下， 我们给出了该问题的启发式算法，并且证明了其最坏情况界是2 ，而且是紧界。 1 8 供应链管理中的若干排序问题研究 3 2e d b ，v = l ，七= l l l 问题的描述和分析 本节通过一个整数规划模型对问题进行深入分析，相关记号表示如下： n ：工件集，n = l ，2 ，刀) ； y ：小车的数目； 七：小车的运输容量，即运输一次能装的工件的数目： 0 ：工件j 在m 。上的加工时间； c ：m 2 的批处理容量； 丁：m ：进行一次批处理的时间； 0 ：工件加工完后由小车从肘：运往其目的地的时间； f ：小车返回m ：所需的时间； ，：鸠上批处理的数目，其中刀c ，刀； 骂：鸠上第f 批处理的工件集，i = 1 ，2 ，； 只：鸠上第e 批工件开始加工的时间； q ：鸠上第骂批工件的完工时间( 到达客户的时间) ； f 1 鼢工件被安排在第舭处理 如2 1 【0 第，个工件没被安排在第舭处理 ， 豇如= l ，= 1 2 硼 吩 - c ，i = l 2 一i j = l 1 9 ( 2 ) 巧0 。纠 = p = - 供应链管理中的若干排序问题研究 q 1 = p 1 + 丁+ 0 2 蜘+ ( y j l - 1 ) t j = l= 1 鼻口l + 丁 f一 只0 。，i = 2 ，j ，3 ， m = lj - l q q l + ( 0 2 + f ) ，i = 2 3 ， = l q 只+ 丁+ ( t j 2 + f ) 如一f ，i = 2 州3 ， j = i ( 4 ) ( 5 ) ( 6 ) ( 1 ) 式表示工件j 在鸠上只属于某一批进行加工，( 2 ) 式表示鸠上各批的容量 不超过其处理容量c ，( 3 ) 式和( 4 ) 式表示鸠上第一批工件进行批处理的开始 时间和完成时间( 达到客户的时间) ，( 5 ) 式表示某一批工件只有在其前上一批工 件处理完毕之后才能开始加工，( 6 ) 式表示某一批工件必须在m 。上完成加工以 后才能在鸠上进行加工，( 7 ) 式和( 8 ) 式分别说明了它们的完工时间和上一批的 完工时间的关系。 供应链管理中的若干排序问题研究 3 3 最- d b ，v = 1 ，j i = 1 l c 咄的复杂性 对于两个判定问题乃，乃，如果对乃的任一的实例，可以多项式时间构造 出的一个实例厶，使得厶的答案为“是当且仅当厶的答案为“是，则称乃 可以多项式归约到死。 定理1 ：如果巧可以以伪多项式变换归约到死，而乃是强p 难的，则乃也是强 p 难的。 3 一划分问题( 3 一即) ：给定3 办个元素，日= 1 ，2 ，3 h ，对于每一个，日， 有一个正整数的大小乃，且对于某个正整数6 ，满足等 ( j i l + 2 ) 6 = y 矛盾。所以，鸩上恰好有( j i i + 1 ) 批，且每批含3 个工件。 因为c 腿y ，而运输这3 办+ 3 个工件的总时间为b - 3 + 3 + b h - 1 = b h + b - 1 ， 所以最早可能开运的时刻为1 + 6 = y 一( b h + b 一1 ) 。由此可知： ( i ) 工件以m 是排在最前面的工件。 ( i i ) 鸠的第一批工件为3 h + l ，3 h + 2 ，3 h + 3 。 ( i i i ) 小车从l + 6 时刻开始运工件，只要有待运工件小车就没有空闲时间。 记昼，垦，色+ 。为鸠进行批处理的各批工件，s ，最，瓯+ 。为各批工件开始加 工的时间，q ，c 2 ，c h “为各批工件在鸠上完成加工的时间，q ，c 2 ，g + 。为各批 工件到达目的地的时间。 由上面的讨论可知： s = 1 ， q = 1 + 6 ， c ；= l + 6 + 6 3 + 2 = 2 b ， 小车返回到鸠运岛的时刻为c l + l = 2 b + l ，因为小车没有空闲时间，所以岛必 须在2 b + l 之前加工完，即c 2 l + 2 b 。