（运筹学与控制论专业论文）带有固定工件和工件运输时间的单机排序问题.pdf

摘要 排序问题有着深刻的实际背景和广阔的应用前景，一直受到国际学术界的 重视本文主要研究了带有固定工件和工件运输时间的单机排序问题固定工 件是一类特殊的工件，它们的开工时间和完工时间都是预先确定的，在时间轴 上占据着一些互不相交的区间在整个加工过程中，工件不允许中断每个工 件有一个运输时间，我们假定在工件力n - r 完后有足够多的卡车运输。 论文共分两章 第一章( 概述) 主要介绍了排序的背景、发展、基本概念及排序模型的记 法 第二章主要讨论了四个排序模型的复杂性、拟多项式时间算法和近似算 法。用三参数法表示我们的模型即是： i f b ( f ) ，缈i l ， i f b ，毋i l ”m ， l f b ( f ) m a x w j c j ， l l f b ( f ) i 嘶g 本文主要结果如下z ( 1 ) 问题i l f b ( f ) ，l l 。、1 i f b ( f ) f m 觚岛和1 i f b ( f ) l 哟g 是n p 一困难 的，问题i l f b ，刊l 。是强n p 困难的 ( 2 ) 问题i i f b ( f ) ，劬i l 、l i f b ( f ) i m a x w i q 和1 f b ( f ) i 屿g 是拟多项式 时间可解的 ( 3 ) 对于问题i i f b ，劬i 三。给出了最坏性能比为2 的近似算法，并证明这是 最好可能的多项式时间近似算法； 对于问题e f b ( 1 ) ，l l 。给出了最坏性能比为2 的多项式时间近似算法； 对于问题l f b ( 1 ) m a x w j 0 给出了最坏性能比为2 的多项式时间近似算法， 在二；篙为常数的情况下我们得到了p t a s 算法并证明除非p = n p ，对于问 题i i f b ( 2 ) i m a x w j q ，不存在常数界的多项式时间近似算法 关键词：固定工件；运输时间；拟多项式时间算法；多项式时间近似算法； 最坏性能比 i a b s t r a c t s c h e d u l i n gp r o b l e mi sa t t r a c t i n gal o to fa t t e n t i o nb e c a u s ei t sd e e p l yb a c k g r o u n di nt h e r e a lw o r l da n db r i g h tf u t u r ei nv a r i o u sa p p l i c a t i o ne n v i r o n m e n t s i nt h i sp a p e rw e c o n s i d e r s i n g l em a c l l i n es c h e d u l i n gw i t hf i x e dj o b s t h ef i x e dj o b sa l es p e c i a la n dt h e i rs t a r t i n g t i m e sa n dc o m p l e t i o nt i m e sa r ep r e v i o u s l yg i v e n t h e yo c c u p ys o m ed i s j o i n ti n t e r v a l si n t h eh o r i z o n d u r i n gp r o c e s s i n g ，p r e e m p t i o ni sn o ta l l o w e d w h e n c et h ep r o c e s s i n go fa j o b i sf i n i s h e d ，i ti sd e l i v e r e dt oi t sc u s t o m e ri m m e d i a t e l yw h i c ht a k e sa d e f i v e r yt i m e w e a s s u m et h a tt h e r e 龇s u f f i c i e n t l ym a n yv e h i c l e st od e l i v e rt h ej o b s t w oc h a p t e r sa r ei n c l u d e di nt h i st h e s i s i nt h ef i r s tc h a p t e r ，s o m en o t a t i o n ，d e f i n i t i o n sa n db a s i cb a c k g r o u n di n f o r m a t i o na b o u t t h es u b j e c ta r ei n t r o d u c e d i nt h es e c o n dc h a p t e r ，w ed i s c u s sf o u rs c h e d u l i n gm o d e l sm a i n l y t h e ya r e r e p r e s e n t e d a s i f b ( f ) ，劬l l t 一，l f b ( f ) l m a x w j g ， i f b ，劬i 三，一， i i f b ( f ) i ”g t h ec o m p l e x i t y , 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 m sa n dp o l y n o m i a l t i m ea p p r o x i m a t i o n a l g o r i t h m sa r ei n c l u d e d m 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 ) i l f b ( f ) ，劬i l 。，l l f b ( f ) i m a x w j c ja n di i f b ( f ) 1w j ga r en p h a r d ，i i f b ，i l 。 i ss t r o n g l yn p h a r d ( 2 ) i l f b ( f ) ，q j f l 。，i i f b ( f ) m a x w j qa n di l f b ( f ) l 屿c jc a n b es o l v e di np s e u d o - p o l y n o m i a lt i m e ( 3 ) f o ri l f b ，q j i l 删，w eg i v ea2 - a p p r o x i m a t i o na l g o r i t h ma n ds h o wt h a tt h i si s b e s tp o s s i b l ep o l y n o m i a l - t i m ea p p r o x i m a t i o na l g o r i t h m ； f o ri l f b ( 1 ) ，劬i l 。，a ；- a p p r o x t m a t i o na l g o r i t h mi sp r o v i d e d ； f o rl l f b ( 1 ) i m a x w j q ，w ep r o v i d eap l o y n o m i a l - t i m ea p p r o x i m a t i o na l g o r i t h mw i t h w o r s tc a s er a t i o2 w h e n 篆i sa c o n s t a n t ，w eg e tap t a s w ea l s op r o v et h a tf o ra n y g i v e nc o n s t a n tm ，t h ep r o b l e ml l f b ( 2 ) m a x w j gh a sn op o l y n o m i a l - t i m ea p p r o x i m a t i o n a l g o r i t h mw i t hw o r s tc a s er a t i oa c h i e v i n gmu n l e s sp=n p i i k e yw o r d s ：f i x e dj o b s ；d e l i v e r yt i m e s ；p s e u d o - p o l y n o m i a la l g o r i t h m s ；p o l y n o m i a l - t i m ea p p r o x i m a t i o na l g o r i t h m s ；w o r s tc a s er a t i o i i i 第一章概述 1 1排序论介绍 排序论是组合最优化的一个重要组成部分在工业生产中存在着大量的排 序问题。将原材料通过各种机器加工成零件需要排序；将生产出来的许多零件 组装成某种产品需要排序；一个大型工程在兴建中，必须要对各类人员进行安 排，对各种器材的供应进行调度排序的好坏对于作业费用的大小影响很大 排序论作为一门应用科学，有着深刻的实际背景和广阔的应用前景。早在 二十世纪初，第二次工业革命期间，t a y l o r ，g i l b r e t h 和g a n t t 就发表了许多相 关的研究文章他们的目的是进行有意义的科学管理，提高劳动生产率题为 ( 美国国防部与数学科学研究的报告认为，2 0 世纪9 0 年代以至整个2 1 世 纪数学发展的重点，将从连续的对象转向离散的对象，并且组合最优化将会 有很大的发展因为。在这个领域内存在着大量急需解决的而又极端困难的问 题，其中包括如何对各个部件进行分割、布线和布局的问题”。从深层次和长 远看，排序论对提高效率、资源的开发和配置、工程进展的安排以及经济运行 等方面都起到辅助科学决策的作用 在排序中，工件是被加工的对象，是要完成的任务；机器是提供加工的对 象，是完成任务所需要的资源；排序是在一定的约束条件下对工件和机器进行 分配和安排次序，使某一个或某一些目标达到最优。 排序分为经典排序和现代排序。根据1 9 9 3 年e l l a w l e r 【7 等人的观点，经 典排序关于资源类型，确定性、可运算性、单目标和正则性有4 个基本假设。 突破经典排序的基本假设，现代排序主要有可控排序，成组分批排序，在线排 序、准时排序、同时加工排序、不同时开工排序、资源受限排序、随机排序、 模糊排序和多目标排序等1 0 多种 1 2基本概念 一个最优化问题的难易程度，是针对一些有代表性的问题而言的。所谓的 问题是指需要回答的一般性提问，通常含有若干个参数或自由变量，这些参数 的值还没有给定若给定所有参数具体的值后，便得到问题的一个实例即一 个最优化问题，就是这个问题的一些实例的集合 把实例用计算机表达出来所占用的存储单元总数，就定义为实例的大小( 或 规模) 用初等运算( 包括算术运算、比较和转移指令等) 的步数，表示一个算 法在计算机上执行所需要的时间即每做一次初等运算，需要一个单位时间 对于所有规模为扎的输入，算法的行为( 即计算次数) 可能不同我们把其中 最坏的行为定义为算法关于输入规模为n 的复杂性。因此算法复杂性是输入规 模的函数 当算法的复杂性被输入规模的多项式界定时，该算法为多项式时间算法 这样的算法是可接受的，也是实际有效的一般认为这样的算法为好算法 g a r a y 【8 】等把“多项式时间算法”定义为时间复杂性为o ( p ( n ) ) 的算法，其中p 是某个多项式函数，礼为输入的规模。 一个最优化问题的提法有三种：最优化形式、计值形式、判定形式我们按 判定问题的复杂性把最优化问题分类一个最优化问题的判定形式可描述为： 给定任意一个组合最优化问题 m i 里f ( x ) 问是否存在可行解跏，使得f ( x o ) l ? 这里x 是有限集，l 为整数 即判定问题是需要用“是”或“否”来回答的问题类 我们用p 表示用多项式时间算法所能解决的判定问题类。也就是说，p 类 是相对容易解决的判定问题类，它们有有效的算法。而n p 类问题是一类比较 丰富的判定问题类。对于一个n p 问题，我们并不要求它的每个实例都能用某 2 个算法在多项式时间内得到回答我们只要求：如果z 是问题的答案为“是” 的实例，则存在对于z 的一个简短( 其长度以z 的长度的多项式为界) 证明， 使得能在多项式时间内检验这个证明的真实性我们知道p n p 而一个重 要的问题至今悬而未解：尸是p 的真子集呢，还是p = n p ? 利用归结的概 念，人们还是在一定程度上揭开了这个奥秘 如果a 。和a 。都是判定问题，4 。和a 是求解a 。和a 。的算法如果 4 。是多项式算法，并且是多次的以单位费用把a 作为子程序的算法，我们说 a 1 在多项式时间内归结为a 2 ，称一4 1 为a 1 到a 2 的多项式归结( p o l y n o m i a l - t i m e r e d u c t i o n ) ，记作a lo ( a 2 如果所有其它的n p 问题都能多项式归结到a ，判定问题a n p 称为是 n p - 完备( n p - c o m p l e t e ) 设a 是个计算问题，是把映射到的函数我们用a ，表示限制于 使n u m b e r ( i ) f ( 1 l i ) 那样一些实例上的a ，其中n u m b e r ( i ) 是，中出现的最大整 数，l ，i 是实例i 的输入规模如果对于某个多项式p ( n ) ，4 是n p 一完备的，则 说a 是强n p 完备的 如果一个判定问题是( 强) n p - 完备的，其对应的最优化问题称为( 强) n p 一困难的。 如果求解问题a 的算法4 能在以i j i 和n u m b e r ( 1 ) 的多项式为界的时间内 求解任何实例，称4 为拟多项式时间算法 n p 一困难问题可能有拟多项式时间算法，但一般认为它不存在多项式时间 的精确算法。而任何强n p - 困难的问题都没有拟多项式时间算法，除非p = p 如果把排序问题按三参数法进行分类，有一种说法认为有9 0 0 0 多个不同的 排序问题( 【5 】) ，其中7 6 为n p - 困难问题，1 2 为p 问题，在剩下的1 2 中， 有种种迹象表明其中绝大多数将被证明是n p 困难问题复杂性理论还让人们 意识到排序问题不可能存在大范围内的统一算法。对任一排序问题，必须充分 利用其结构作不同的处理。 根据以上分析，对n p 困难问题的解决出现了两种趋势：一是对给定的n p 一 困难的排序问题给出各种形式的动态规划算法和分枝定界法以获得精确解；二 3 是降低原来的目标，不去寻找求解此问题的多项式时间的精确算法，而考虑问 题的各种特定情形下的多项式时间算法，进而寻找在大多数情况下能快速求解 的近似算法衡量算法的。优良”程度有三种办法：数值算例计算、最坏情况 分析和概率分析目前理论上常用的是算法的最坏情况分析 设a 为一目标函数为最小的优化问题，是求解它的算法如果存在一个 实数r ( r 1 ) ，对于问题以的所有实例，都有 一4 ( ) sr o v t ( i ) 其中4 ( ，) 是有算法4 得到的，的目标值函数值，o p t ( i ) 是，的最优目标函数 值( 即最优值) ，那么称r 为算法的4 的一个上界如果不能确定算法是否有 界，或者能够确定算法的上界是无穷大时，这个算法称为启发式算法。当r 是 有限数( 不是无穷大) 时，这个算法称为近似算法也就是说，近似算法是有 界的启发式算法用启发式算法和近似算法得到的解分别称为启发式解和近 似解对于使上式成立的最小正数r 称为是算法的最坏情况性能比( w o r s tc a s e r a t i o ) ，简称为最坏比或最劣比，也称为算法的紧界 对于一个近似算法，一个重要的工作是分析最坏情况下的误差界，利用最 坏性能比来衡量算法的好坏当然，最坏性能比越小，近似算法的精度越高。 4 1 3排序的记号 1 9 7 9 年，g r a h a m ，l a w l e r 【6 】等人提出用三参数法a 俐，y 来表示一个排序问 题。这也是目前国际上通用的排序模型的表示方法其中a 域刻画的是机器的 环境，p 域刻画的是工件的特征，y 域刻画的是将要极小化的目标函数。在o t 域必须有一个参数输入，在卢域可以没有，也可以有一个或多个参数输入，在 ，y 域一般有一个或多个参数输入采用这种记法，我们研究的排序模型可以表 示为t i l f b ( f ) ，l 工t ，l l f b ( f ) l m a x w ，q ， i i f b ，劬l l ，i l f b ( f ) l 0 下面我们对常用的和在上述模型中出现的符号作出说明。 ( 1 ) o l 域： o t = 1 单台机器 a = p 相同的平行机 a = q 一致的平行机 o z = r 无关的平行机 ( 2 ) 域： 卢= 巧工件有到达时间 p = q j 工件有运输时间 p = p r e c 工件间有序约束 卢= o n l i n e - l i s t 工件是按序在线 p = o n l i n e ，吩工件是按时在线 p = f b 工件中有固定工件 卢= f b ( f ) 固定工件有f 个 ( 3 ) ，域： 我们先来介绍一些常见符号的含义： 5 性 嘶工件工件如的权重，体现了工件在整个系统中相对其它因素的重要 g 工件以的完工时间 l j = c j + 劬工件易被送到顾客手中的时间 一些本文中出现的正则目标函数列举如下t ，y = g 工件的最大完工时间，此处g 。= m a x c j l l j n 7 = l 。所有工件都被送到顾客手中所花费的时间，此处 = m a x 岛1 1 j n ，y = m a x w i o 工件的最大加权完工时间 ，y = 嘶c j 工件的加权完工时间和 6 第二章带固定工件和工件运输时间的单机排序问题 2 1引言 大多数排序模型要求在整个时间轴上，机器都是可以利用的。然而，在现 实世界中可能并非如此我们在安排生产时就经常遇到一类特殊工件，我们把 它称为固定工件例如，生产前已经确定好的在固定时间段的清洗工件和维修 工件另外，由于现实生活中资源安排问题常常是动态的，输入的数据要经常 更新在处理这种动态环境时，一种比较自然的方法是根据最新得到的数据对 资源重新安排；另一种则是保留已有的安排，利用剩余资源加工新的工件这 样，先期安排的工件就就在处理新的工件前固定下来。在排序中，我们所说的 固定工件是指这些工件的开工时间和完工时间以及安排在哪台机器上加工都 在排序前已经确定在新工件就绪前这些工件已经在时间轴上占据了一些互不 相交区间，新工件则只能在剩余的时间段内加工也就是说固定工件占据的区 间对新工件而言是禁用的相对于固定工件，我们把新的需要安排加工次序的 工件称为自由工件固定工件的例子还出现在工业生产的排序软件中，这种软 件提供交互式的排序功能，系统允许人工固定一些工件而把余下的工件按照一 定的规则自行安排设计者的思想是使决策者可以在安排中加入自己的主观意 愿 在我们的模型中，提供加工的对象是单机这样，所有的工件必须在同一 台机器上加工，而同一时刻机器只能加工一个工件在加工完后，每个工件要 被送到各自的顾客手中这样，每个工件有一个运输时间我们假定有足够多 的卡车，在工件加工完后能立刻被运输。在整个加工过程中，工件不允许被中 断我们研究的问题是如何安排新工件的加工次序才能使设定的目标函数达到 最优 我们将本文中经常用到的几个排序规则列举如下： 设 ，也，厶是n 个待加工的工件工件以的加工时间为聊，权重为嘶， 运输时间为鳓，1 j n 7 l d t - 规则：将工件 ，如，厶按劬非减的顺序排列的排序规则称为最大 运输时间优先规则，简称为l d t - 规则 在l d t - 规则之下，工件 ，五，厶被重新编号使得q 1 q 2 锄 由文献【1 】，我们有： 引理2 1 1 对于问题l i l l 。，按l d t - 规则得到的排序是一个最优的排序 g w - 规则；将工件 ，也，厶按叻非增的顺序排列的排序规则称为最大 权优先规则，简称为g w - 规则 在g w - 规则之下，工件以，也， 被重新编号使得w 。w 。 t o n 由文献【1 】，我们有。 引理2 1 2 对于问题l m a x w j c j ，按g w - 规则得到的排序是一个最优的排 序 引理2 1 3 对于问题1j | g 。，将工件连续排列得到的排序是一个最优的排 序 s p t - 规则：将工件以，如，巩按胁非减的顺序排列的排序规则称为最短 加工时间优先规则，简称为s p t - 规则。 在s p t - 规则之下，工件 ，也，厶被重新编号使得p 1 p 2 p n 由文献【1 】，我们有： 引理2 1 4 对于问题1 | | eq ，按s p t - 规则得到的排序是一个最优的排序 w s p t - 规则；将工件以，以，厶按警非增的顺序排列的排序规则称为加 权最短加工时间优先规则，简称为w s p t 一规则 在w s p t - 规则之下，工件, 1 1 ，j 2 ，厶被重新编号使得等之w 。2 等 由文献 1 】，我们有： 引理2 1 5 对于问题1 i i 嘶g ，按w s p t - 规则得到的排序是一个最优的 排序 8 2 2复杂性 我们在本节讨论了四个基本模型的复杂性它们用三参数法表示为 i l f b ( f ) ，劬1 l 。 i i f b ，i 厶盂， 1 f b ( f ) m a x w j c j i l f b ( f ) l 奶g 定理2 2 1 问题i l f b ( f ) ，劬i l 。是n p - 困难的 证明：我们用划分问题作归结划分问题是经典的n p 一困难问题。 划分问题：给定礼个正整数a l ，a 2 ，记饕1 a j = 2 a 问是否能把这些 正整数的下标集，= l ，2 ，扎) 划分成不相交的子集s - 和使得幽a k = k a k ? 给定划分问题的一个实例，我们按照如下方式构造i i f b ( f ) ，国l l 。的一个 实例： n 个自由工件以，也，厶，其中功= a j0 = 1 ，n ) 一个固定工件厶+ 1 厶+ 在a 时刻开工，2 a 时刻完工，这里a = j 1 譬。a j 运输时间劬= q ，1 j 竹+ 1 门槛值6 = 3 a + q 问是否存在一种排序8 使得l 。( s ) d ? 显然，上述构造可以在多项式时间内完成 如果划分问题的实例有解，则存在两个互不相交的子集s ，和使得e 矾a k = 。如a - = a 将研中的工件排在厶+ - 之前，中的工件排在厶+ ，之后显然 l 。( s ) = 3 a + g = 6 反之，如果存在排序8 使得l 一( s ) 6 ，我们用岛表示在a 之前完工的工件 的下标集，表示在2 a 之后开工的工件的下标集。显然舀s la j = 马s 1 功 a 由l 。( 8 ) = 2 a + 易岛功+ q 6 可知邑岛q = 邑岛功sa 注意到 托s l p j + j s 2 乃= 2 a ，我们有s 。a j = d 岛= 舀幽功= ，s 2 聊= a 从而 9 划分问题有解 口 如果所有工件的运输时间都相等，问题i l f b ( f ) ，毋l l 。等价于l l f b ( f ) i g 。， 从而我们有 定理2 2 2 问题l l f b ( f ) i m a x w j 0 是n p - 困难的 由引理2 1 2 我们知道将工件连续排列得到的排序是1 i | g 。的一个最优序。 由定理2 3 1 的证明我们看到即使只有一个固定工件，所有工件运输时间都相 等，问题i i f b i 厶。也是n p - 困难的从而不存在多项式时间算法。可以说，固 定工件的引入使问题变得困难当然，对于这种特殊的情况，只要在在固定工 件开工之前安排尽可能多的负载就达到最优，从而可以在0 ( 2 n ) 时间内解决 在固定工件的个数没有限制的情况下，m s c h a r b r o d t 【1 1 】等用3 _ 划分问题 作归结，证明问题i l f b i g 。是强n p - 困难的从而我们有 定理2 2 3 问题i f b ，劬l l 。是强n p 困难的 c y l e e 和s d l i m a n 【9 用奇偶二划分作归结，证明带有一个维修区间， 目标函数为极小化完工时间和的的单机排序问题是n p - 困难的。类似的可以证 明问题i f b i q 是n p - 困难的从而我们有 定理2 2 4 问题i i f b ( f ) i w j g 是n p 困难的。 i 0 2 3动态规划算法 对于有限个固定工件的情形，我们已经证明问题i f b ( f ) ，q j i l 。 l l f b ( f ) l m a x w j c j 和1 f b ( f ) i q q 都是n p - 困难的在本节我们给出这些问题 的拟多项式时间算法 假定f 是一个确定的常数，固定工件占据着f 个互不相交的区间【a i ，玩) ，其 中1 isf ，0 a l 5 1 如 b 2 a f b r 记 = 【0 ，a 1 ) ，1 2 = 【b l ，a 2 ) ，i f = 【b f 一1 ，a f ) ，i r + i = 【b e ，+ ) 以表示区间五的长度如果a 。= 0 ，则，1 是一个空集，i i ij = 0 假定固定工 件五的运输时间为，权重为以 引理2 3 1 存在排序问题i f b ，q j i l 。的一个最优解，使得在每一个区间 五内加工的工件按l d t - 规则排列 证明：设7 r 是问题i i f b ，口j i l 。的一个最优序设在排序丌中存在区间厶 中的两个相邻工件以和以不满足上述规则，即劬 q k ，而工件如排在了以的 前面。现在我们对丌做如下变动，交换以和以的位置。记新的排序为丌7 ，并设 7 r 中以的完工时间为t 对工件以，g ( 丌) g ( ，r ) ，从而l k ( u ) l 。( 丌) 对工件 乃，易( 丌7 ) = t + 口j t + q k l 。( 7 r ) 对其它工件 ，工件的位置以及完工时间没 有发生变动从而“( 丌) = 如( 7 r ) sl 。( 7 r ) 继续上述交换直到每个区间五内的工件均按照l d t - 规则排列。引理得证口 定义2 3 1 我们说一个排序口为l d t - 序，如果它满足在每一区间五内加 工的工件按照l d t - 规则排列 由引理2 3 1 ，我们只需找出一个最优的l d t - 序 将几个自由工件按照l d t 序排列，不妨设q l 之啦2 q n 将排序问题限 制在前j 个工件上考虑，将这一问题记为r ( j ) 定义2 3 2 我们说一个排序满足限制冗( 乩，z 。) ，如果它满足在每个区 间五加工的工件总加工时间为础，l isf 记p j = p + p 2 + + p j 定义q 1 为乃0 ) 在l d t - 序中取得的最小运输完 工时间定义q 1 0 ；z l ，z 2 ，z f ) 为r ( j ) 在满足限制冗( z 1 ，z 2 ，) 的l d t - 序 中取得的最小运输完工时间定义茁f + 1 = b 一( z ，+ z 。+ + 。f ) 定义边值条件如下； q 1 0 ；x l ，勋，z p ) = l m 。a x ，( b i + q ；) ，如莉= 0 ，z 1 2 $ 2 = 一z f 2 o 0 0 ，如果存在1 i f + 1 ，使得戤 0 易见q 1 0 ) = m i n q ( j ；z l ，x 2 ，x f ) ：x i20 ，戥p 0 ) ) 此外，问题的最优值由q 。( n ) 给出。 假定丌是前j 个工件的一个l d t - 序使得l 一( 丌) = q 1 ( j ；x l , ，x f ) 假定 易被安排在区间五内加工则在，r 中乃一定是厶内最后一个加工的工件从 而岛( 7 r ) = 玩一1 + 础+ 劬，这里a o = 0 我们有 q 1 ( j ；z 1 ，z 2 ，x f ) = m a x q ( j 一1 ；x l ，x 2 ，z t 一1 ，观一如，x i + l ，z f ) ，玩一1 + 冠+ 这样就得到该问题的动态规划方程 q 0 ；。l ，z 2 ，x f ) 21 萎& 1 m a x q ( j 一1 ；z 1 ，z 2 ，z l 一1 ，现一功，z i + ，一，z f ) ，玩一，+ 鼢+ q a 1 2 记p = p ( n ) 我们有至多o ( n p f ) 次迭代每次迭代可以在o ( f ) 时间内计 算因此，算法的时间复杂度为o ( n f p f ) 定理2 3 1 当f 为确定的常数时，排序问题i i f b ( f ) ，劬i l 。可以在拟多项 式时间内解决 引理2 3 2 存在排序问题l l f b ( f ) l m a x w j q 的一个最优序，使得在每一个区 间五中加工的工件按照g w - 规则排列 证明：类似于引理2 3 1 用二交换法 定义2 3 3 我们说一个排序仃为g w - 序，如果它满足在每一区间厶内加 工的工件按照g w - 规则排列 、由引理2 3 2 ，我们只需找出一个最优的g w - 序 将n 个自由工件按照g w - 规则排列，不妨设w 。w 。w 。将排 序问题限制在前j 个工件上考虑，并将这一问题记为岛( j ) 记易= p 。+ p 2 + + 彩定义q 2 ( j ) 为伤( j ) 在g w - 序中取得的最小最大加权完工时间定义 q 2 0 ；，z f ) 为危( j ) 在满足限制冗( ，z 。) 的g w - 序中取得的最小 最大加权完工时间定义z f + l = p j 一( 。1 + z 2 + + x f ) 定义边值条件如下： q 2 ( j ；x l ，x 2 ，茁f ) = i m i a x f 叫：玩， 如果j = 0 ，z t = z 2 - = z f = 0 o o ，如果存在1 i f + 1 ，使得甄 0 类似于前一问题的讨论我们得到该问题的动态规划方程 q 2 0 ；z l ，z 2 ，x f ) 21 0 磐i + l m a x q ( j 一1 ；z l ，z 2 ，z i 一1 ，戤一聊，z 件1 ，z f ) ，w j ( b i 一1 + 勋) ) q 2 ( j ) = m i n q ( j ；z l ，x 2 ，x f ) ：甄0 ，兢p 0 ) ) 最优的目标值由q 。( n ) 给出该算法的时间复杂度为o ( n f p f ) 定理2 3 2 当f 为确定的常数时，排序问题l l f b ( f ) m a x w j g 可以在拟多 项式时间内解决 1 3 引理23 3 存在排序问题i i f b l 嘶g 的一个最优解，使得在每一个区间五 中加工的工件按w s p t - 规则排列 证明：类似于引理2 3 1 用二交换法 定义2 3 4 我们说一个排序盯为w s p t - 序，如果它满足在每一区间厶内 加工的工件按照w s p t - 规则排列 由引理2 3 3 ，我们只需找出一个最优的w s p t - 序 将n 个自由工件按照w s p t 序排列，不妨设w _ ，l 。嚣2 尝将排 序问题限制在前j 个工件上考虑将这一问题记为乃0 ) 记p j = p 1 + p 2 + + 勋定义q 3 为岛( j ) 在w s p t - 序中的取得最小加权完工时间和定义 q 3 0 ；，z f ) 为伤0 ) 在满足限制n ( x l ，) 的w s p t - 序中取得的最 小加权完工时间和定义z f + 。= b 一( z 1 + z 2 + + x p ) 定义边值条件如下： q 3 0 ；x l ，x 2 ，x f ) = 以魄，如果j = 0 ，x l x 2 一x f = 0 i i f 0 0 ，如果存在1si f + 1 ，使得以 0 类似于上文的讨论可得该问题的动态规划方程 q 3 ( j ；z 1 ，。2 ，z f ) 。l 当型冉1 m a i x q 3 0 1 ；z 1 ，z 2 ，锄一1 ，戤一聊，z 件1 ，z f ) + w j ( b i 一1 + 兢) q 3 0 ) = m i n q a ( j ；x 1 ，2 ：2 ，z f ) ：o ，1 羡if 鼢p 0 ) f 最优的目标值由q s ( 礼) 给出该算法的时间复杂度仍为o ( n f p f ) 定理2 3 3 当f 为确定的常数时，排序问题i i f b ( f ) l q c j 可以在拟多项 式时间内解决 1 4 2 4近似算法 首先我们考虑问题问题i i f b ( 1 ) ，q j i l 。 假定唯一的固定工件在a 时刻开工，b 时刻完工，运输时间为0 以了= 以，厶) 表示自由工件的集合，记p = p 1 + p 2 + + 以表示自由 工件的最大加工时间记历= 也：p j 舛将历中的工件称为大工件记 刃= g j ：功 p ) 将历中的工件称为小工件如果o = 0 或者口p ，那么 将所有工件按l d t 序排在【6 + ) 或者【o ，a ) 就是问题的一个最优解。不妨设 0 a p 算法2 4 1 步骤1 如果p 。s p ，将所有工件按l d t 序排列不妨设q 1 q 2 q n 记k = m a x j n ：a o 将 ，如，以 按l d t 序排在【0 ，口) ，其它工件 按l d t 序排在【b ，+ o o ) 记相应的目标函数值为l 。转步骤5 ； 步骤2 如果a p 。，将岛中的工件按l d t 序排列。不妨设函= ，也，山) 其中q l2q 2 和记k = m a x ：ep i n ) 将 以，以， ) 按l d t 序排在【0 ，口) ，其它工件按l d t 序排在f b ，+ o 。) 记相应的目标函数值为l 。转 步骤5 ； 步骤3 将历中的工件按l d t 序排列不妨设历= ，如，山 ，其中 q l q 2 知记k = m a x j ：p i a p ，一) 将, 7 1 u 以，也，以) 按 l d t 序排在【0 ，o ) ，其它工件按l d t 序排在【b ，+ 。o ) 记相应的目标函数值为l ， 转步骤4 ； 步骤4 将历中的工件按l d t 序排在【b ，+ o o ) ，其它工件按l d t 序排在【o ，n ) 记相应的目标函数值为l z 令三。= m i n l z ，l 。 转步骤5 ； 步骤5 输出取得l 。的排序盯 1 5 定理2 4 1 对于问题i i f b ( 1 ) ，劬f 上。而言，工。( 仃) i 上。( 7 r ) ，其中厶一( 和l ( 丌) 分别表示由算法2 4 1 得到的目标函数值和问题的最优值，并且这个 界是紧的 证明：设丌是一个最优的l d t 序使得【0 ，o ) 中机器的空闲时间最少 以五表示在n 之前完工，运输时间小于虬的小工件；以而表示在b 之后 开工，运输时间大于等于q k 的4 、- 3 2 件即 兀= 乃历：劬 q k ，0 ( 7 r ) 6 ) 如果盯= 丌，那么己。( 盯) = l m 。( 丌) 不妨设盯丌显然矗o ，五o 从 而角 设 是乃中最后完工的工件我们对丌做如下变动：取出五中 的工件；对【o ，o ) 中的其它工件保持丌中的序，并将乃中的工件以任意序排在 其后；取出五中的工件；对【b ，+ o 。) 中排在厶前的其它工件保持丌中的序， 并将五中的工件以任意序排在其后；排在矗后的工件保持丌中的序置于最 后记新的排序为矿注意到盯和矿中安排在 o ，n ) 中加工的工件相同，我们 有l 。( 盯) l 。( 7 r ) 设矿下五中工件的最早开工时间为s ，最后完工时间为t 以下我们讨论 矿中工件的完工时间 对 0 ，n ) 和【b ，s ) 中的工件，我们有g ( 矿) 曼0 ( 丌) ，从而岛( 丌) 易( 丌) 对五中的工件， 劬( 矿) t g ( 7 r ) + 尸( 矗) 一p ( 危) q k ，q h 弧，我们有毋q a 从而 岛( 矿) = g ( 矿) + 劬 a 假定在g r 中如取得最大加权完工时间。我们有 d m “( 盯) = 嘶c j d 懈( 7 r ) 凹1 ( 6 + p 1 ) w l a 注意到所有工件按g w - 规则排在 b ，+ o o ) ，我们有 d 。( 丌) 叫j ( c j o ) 由此可得 d 仇( 仃) = t 0 c ；一w j a + w j a d m ( _ 7 r ) +