（运筹学与控制论专业论文）两种排序问题的近似算法.pdf

錾江走喾硕士学位论炙 摘要 本文磷究了礴耪蓑 廖润题：秀套祝上戏缝搬工豹滚拳 睾韭撼彦润题帮单台飒 有维护时段的排序问题 全文共分三章。第一灌篱要分绍了缀合毯豫隰逶、捺滓蠲瑟瓣基本穰念与冀 法和最坏情况分析的简要介绍程第二章中，我们详细介绍了两台机上成组加工 的流承作避j j f 序闷题，觚组工件蓟另一缝工件之闯需辩调整时闻首兔辩 驴 难的五is ，g ，i 。岛离线排膨，给出了一个遮似算法，证盟了它的墩坏情况 界为2 然后讨论了e i s ，g t i q 。在线排序，并给出了个竞争比为2 的近似 算法，并诞明不霹能存在党争院夺于2 翡在线近儆算法第三章磺究了攀台橇器 裔维护时段的排序问题，目标为极小化总完工时间对该问题，文献中最好的近 似算法m s p t 的绶坏情况界为2 0 1 7 我们将文献中基予邻域搜索思想的2 - o p t 操 乍推广为k ，k 一交换操 乍，利用此操作，给出了一个多项式时闯近似方案，从 而大大改进了文献中的结果 关键词：流东终娥攘彦；藏缀技术；擎螽穗器嚣 黟；维护辩段；避钕算法；最嚣 情况分析 濒汉大学硕士学位论文 i ii ii i , , i i i i i i i i i i i i i i i i i i i i i i ；i i i i i a b s t r a c t t h i sp a p e rs t u d i e st w oo f f - l i n es c h e d u l i n gp r o b l e m s ，w h i c ha r et w o - m a c h i n e f l o w s h o ps c h e d u l i n gp r o b l e m s 、i 1s e t u pt i m ea n dg r o u pt e c h n o l o g ya n das i n g l e m a c h i n es c h e d u l i n gp r o b l e mw i 镪m a i n t e n a n c e t h i sp a p e ri n c l u d e sf l 球e ec h a p t e r s 。i nc h a p t e r1 ，w ei n t r o d u c eb a s i cd e f i n i t i o n s a n dn o t a t i o n so fc o m b i n a t o r i a lo p t i m _ i z a t i o n ，s c h e d u l i n gp r o b l e m sa n da l g o r i t h m ， w o r s t - c a s er a t i o i nc h a p t e r2 ，w ec o n s i d e rt w o - m a c h i n ef l o w s h o ps c h e d u l i n g p r o b l e m s 、衍氇g r o u pt e c h n o l o g y ，w h e r es e t - u pt i m ei sn e e d e df r o mo n eg r o u pt oo t h e r g r o u p 。f o rt h ep r o b l e meis ，g f | “g ，a l la p p r o x i m a t ea l g o r i t h mw i t h w o r s t - e a s er a t i o2i s p r e s e n t e d f o r t h eo n - l i n e p r o b l e m 互ts ，g f | c 纛，a l l a p p r o x i m a t ea l g o r i t h m 谢t l lc o m p e t i t i v er a t i o 2i sa l s op r o p o s e dw h i l ei tc a l lb e p r o v e dt h a tt h e r ei sn o to n l i n ea p p r o x i m a t i o 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 ol e s s t h a n2 i nc h a p t e r3 ，w - es t u d yas i n g l em a c h i n es c h e d u l i n gp r o b l e mw i t hm a i n t e n a n c e u n d e rt h eo b j e c t i v ef u n c t i o no fm i n i m i z i n gt o t a l c o m p l e t i o n t i m e 。t h eb e s t a p p r o x i m a t i o na l g o r i t h mi nl i t e r a t u r ei sm s p t w i 血w o r s t - c a s er a t i o2 0 1 7 b a s e do i l t h ei d e ao fl o c a ls e a r c h ，w eg e n e r a l i z e2 - o p to p e r a t i o np r o p o s e di nl i t e r a t u r et o ，1 | e x c h a n g eo p e r a t i o n 。w i t hn e wo p e r a t i o n ，w ep r e s e n t ap o l y n o m i a lt i m e a p p r o x i m a t i o ns c h e m ef o rt h ec o n s i d e r e dp r o b l e m ，w h i c hg r e a t l yi m p r o v e st h ek n o w n r e s u l t k e y w o r d s ：f l o w s h o ps c h e d u l i n g ；g r o u pt e c h n o l o g y ；s i n g l em a c h i n es c h e d u l i n g ； m a c h i n e m m n t e n a n e e ；a p p r o x i m a t i o na l g o r i t h m ；w o r s t - c a s ea n a l y s i s l 溪汪走喾磋士擎位论文 i i i i i i i i i 黼蔷i i i i i 鞘鞠i i i i i 耐蔷宣；i i i 黛赫i i i i i 羞；i i i i 黛嗣i i i i i 嵩誓i i i i i 葺i i i i 嵩麓离暑i i i 第一章绪论 1 1 组合优化简介 组合优化翊题又称离教挠化阉题，是运筹学中一个非鬻活跃的分支，其实质 是寻求对需完成任务的合理安排以得到某种意义下的最优结果熟广泛应用于管 瑾辩学、诗算撬秘学、工程鼓术鞠现炙纯蹩产等缀多壤域，这类勰蘧与甄摸璞， 越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高殿重视， 蠢趣来越多静入程这方露送行磅究。 定义1 1 。1 组合优化问题石鼹个极小化问题，或是一个极大化问题，它由 下述三部分组成； ( 1 ) 这个问题的实例集合； ( 2 ) 辩每一个突倒，有一个有限的可行解集合s ( o ； ( 3 ) 嗣标函数为，它对每一个实例，和每一个可行解盯s ( i ) ，都可以得 到一个有理数f u ，盯) 如果该润题楚极小化蛔题( 或援大化翊题) ，则实铡j 豹最谯嬲麓这样个可 行解盯s f f ) ，它使得对所有的盯s ( x ) ，都有f ( 1 ，仃+ ) f ( i ，玎) ( 或 厂( 1 ，g ) f ( i ，g ) ) 。 常见的组合优化问题有背包问题( k n a p s a c kp r o b l e m ) 、排序问题( s c h e d u l i n g p r o b l e m ) 、装麓溺逐国i n - p a c k i n g p r o b l e m ) 、薹 翻阉n ( s e t p a r t i t i o n i n g p r o b l e m ) 、 指派问题( a s s i g n m e n tp r o b l e m ) 、旅行售货商问题( t r a v e l i n gs a l e s m a np r o b l e m ) 、 辩毽续最，l 、瓣溺题( 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 w p r o b l e m ) 、最，j 、费鬻流闯越陋n - c o s tf l o wp r o b l e m ) 等。缀合凌纯韵奔缁冒参冕 y h c 0 1 】，在这里我们只对本文研究的排序问蹶作一介绍 浙江大学硕士学位论更 l 。2 攥序阕题 排序问题是组合优化这门学科的一个重要组成部分，有潜堂要理论意义和广 泛实际背景它在生产计划调度、信息处理、公用事业管骥等许多方面具有大髓 黪应用，阍酎它与瑾论计算辊科学和离数缀合数学存在饕密翅的联系 工 串螽o b ，t a s k ) 楚渡鸯鼙工懿对象，怒癸完成熬荏务；橇- - 瓣( m a c h i n e ，p r o c e s s o r ) 是提供加工的对象，是完成任务所需鼷的资源；排序( s c h e d u l i n g ，又称为调度) 也称为安排时间表，炫在一定的约束条件下对工件和机器按时间进行分配和安排 次序，使某一个或浆一些目标达到最优为了简单明确地描述某一种具体的排序 弱遂，1 9 6 7 每c o n w a y 等蓄先提遗矮溪个参数寒表示龚 穿瓣越。1 9 7 9 年g r a h a m ， l a w l e r ，l e n s t r a 和r i n n o o yk a n 等【g l l r - 7 9 】提出三参数表示法( t h r e e f i e l d r e p r e s e n t a t i o n ) 目前国际上使用的三参数口g r 来表示个排序问题，其中 搿，y 分别代表特定的机器环境，工件特征和优化的目桥下面分别对这三个 参数馋一麓要分绍。 税器环境焉来攘述梳器酶数量、不间机器之闯静关系等与税器有关瓣瞧 质首先明确什么叫中断加工：一个工件在加工过程中，如果可以中止加工而让 别的工件优先加工，并且稍后在原来机器或在其他机器上继续加工，这种性质称 为中断热工。规器掰以分成2 大类：邋用乎行( p a r a l l e l ) 枫朔专媛串联( d e d i c a t e d ) 镌。对予不兔诲审鞭麴工静篱嚣寒漤，一令工 孛在m 念平褥瓿豹燕工，只嚣 要在这m 台机器中的任何一台机器上加工一次；一个工件在m 台串联机上的加 工是需要在这m 台机器中的每一台机器上都加工一次串联机又可分为3 类：工 件依次以特定的相脚的机器次序在这燃机器上加工的流水作她( 丑o w s h o p ) 、i 件 绞次在提器上熬王戆次序可戮任意静莛耄终韭0 弦珏s h o p ) 秘每一令工舞戳套巍 的机器加工次序丽进行加工的异序俸娥( j o bs h o p ) 平行祝嘏可分成3 类：其蠢鞠 闹加工速度的同型( i d e n t i c a l ) 机、具有不同的加工速度但此遮度不依赖于工件的同 类( u n i f o r m ) 机和髓加工的工件不同加工速度也不同的非嗣擞型( u n r e l a t e d ) 机肖 戆掇器有调整对闻灏维护靖闯( p e r i o ao f m a i n t e n a n c e ) 面使王l 孛加工中断或延期 2 浙江大学硕士学位论文 王锋特餐楚撵工俸熬耱莹惑( 被撩工瓣工彳孚中篱i 拿王律遽鬻记舞，) ，包 括工件的加工时间( p r o c e s s i n g t i m e ) ，指工件，在机器m 上加工所需的( 非负的) 时潮，哥鞋翅擞来表示 工赞豹到这对阉( a r r i v a lt i m e ) 又准蘩瓣藏( r e a d yt i m e ) 或释放时间( r e l e a s e t i m e ) ，是指工件t ，可以开始加工的时刻，可以用，来寝示； 交货麓( d u e d a t e ) d j 表示工件了；豹酝骞工痔懿攘工应该缝寒豹对刻：投( w e i g h t ) w ，表示工件，的重要性；各工件问在加工过程中相互之间的依赖关系，比如先 后( p r e c e d e n c e ) 约束；工件在热工霹缝否中数等等擞撼具体撵廖闫题中瓣工 孛 信恳的了解程度，又可将排序问题分为离线( o n - l i n e ) 、程线( o n ，l i n e ) 幕l 半在线( s e m i o n ，l i n e ) 等如果在排序开始前已知工件的全部信息，例如工件数h 、每个工件j ， 酶黼工时闻和释放嚣寸闻r ，等信惑，则称该闻题是离线阎题稀如果工件静信 息怒随着排序过程逐个跤知的，即只有在位于某个工件j 前的众部工件均被安 簿完毕后，簿序者方麓知道工件，的有关翁怠，赢菇工传一里被安莽 藏不麓改 变这样的排序问题称为在线( o n l i n e ) l b q 题但在实际问题中，大量的问题是介 予弼卷之藏魏，霹我餐簸者籍遘该溺题匏一臻整露痿惑，或者秘道君续工辞嚣部 分信息例如，已知所有工件的最大加工时间，不知道每个工件的具体加工时 间但与在线阔题摆比，这些信息可以用来憾计螽续工传搬工黔闻的范围，这是 有利于算法设计的于怒，我们锻这样的问题称为逶半在线( s e m i - o n l i n e ) n - 题 所谓优化的目标，也就是以什么为目橼函数如果记c ，为某个排序问题的 可行j 菲序中麓工 牛，静完工时闻，剐称。= m a x c ，为该l 序静最大完工时闯 ( m a k e s p a n ) 送就是某种最优准则下的目标瀚数，其煅优准则为：找一个可行排 序，镬得它斡皴大完工眩蘑q 。在 | 舞有楚霹行瓣痔中鼗褥爱小德，繇较夸纯嚣标 函数排序问题中的优化目标还有很多其他的目标函数，常见的有求最小总完工 时阈、鼓，l 、熬权总完工对闯。毪g 、最大延谈越阗毛= q 一嘭、簸少误 z _ g 2 件数u ，( 如果c ，兰d ，那么u ，= 0 ；如果c ，d ，那么u ，= 1 ) 等在排序问题 中，如暴所骞黪数握在送行决繁之 ；誊都是已翔兹，瓣序闽题称为确定糕接穿 ( d e t e r m i n i s t i cs c h e d u l i n g ) ( n 题如果有的数据，例如加工时间、准备时间和工期 等，在做决策时是未知的，它们是一些随机变量，但它们的分布是已知的，这样的排 序阍题称为陵梳排序( s t o c h a s t i cs c h e d u l i n g ) n 题我稍程这里只讨论确定憔簧 序 t 浙江夫擎磺士学位论文 1 3 算法和最坏情况分析 定义l 。3 。1 葵法怒攒一步一步求麟阕题戆逶霜步骤，它蹩熬决阉蘧豹多骤豹 一个清晰描述，这擞我们仅讨论确定型算法，即算法从前一疹到后一步的具体操 作是惟一确定的如果存在一个算法，它对问题z 的每一个裳例，在有限步詹， 一定可得到该实例必予酉的提问的答枭，那么我们就称该爨法解问题茁 磐褰线闻莲豹舞法豁为襄线雾法，裰疲逡，鳃在线蘑遴瓣霹法称蠢在线算法。 定义1 3 2 最优算法是对于一个优化阀题z ，如采绘定任意一个实铡j ，算法 爿总能找到一个可行解盯6 - s ( ，) ，如果j 拽一步这个可行解的目标值总是等于锻优 解值盯+ ，则称一为最优算法 对于一个其俸阏蘧可能会有不围黪黪法求解，我稍希糍罨技鳃目题懿簸餐效 算法透鬻曩计算辩闻箨为餐量标准，魄就是说把能最快褥剿最终结莱的算法称 为最有效算法为了排除计算机速度_ 葶口操作系统等因素，我们总是用算法中所含 撼本运算次数来表示算法所用的时间，这里基本运算是指加、减、乘、除、比较 等运算。由于算法掰月的时闻跟实例的规模有关，为此我们用输入长度来刻画爽 壤豹痰摸。繇诿输入长凄是豢蘧述实镄骚瘸懿诗算橇蠹菇繁元数。 定义1 3 3 算法时间复杂性是关于实例输入长度挥躺黼数厂( 聆) ，用来表示簿 法的时间需求对于每一个可能的输入长度，它是该算法解此输入长度的最坏可 能的实例所需的时间( 基本运算步数) 即对于输入长度相同的所有实例，把算法 对这些实铡豹最嚣 骞凝终隽怼霾复杂憋瓣度量。 若存在一个常数c ，使得对所有璁o ，都有| 苁筇) | 兰c | g ( n ) | ，则称函数厂( 一) 是0 ( g ( ”) ) 时间复杂性是0 ( p ( 珂) ) 的算法称为多项式时间算法，这里p 0 ) 是个 多项式，n 为输入长度，不能这样限制时间复杂性函数的算法称为指数时间算法， 我髑把多项式时间黧法舔为努戆有效豹爨法，把能用多颈斌鞋尊阕算法求解懿阕壤 髂为“易解”闻题，露剃就称为难解阀邋 定义1 3 4p 类问题对一个组合优化问题，如果已找到了多项式时间算法， 4 浙江大学硕士学位论文 那么魏稼它隽多矮式藏淄哥舞润瑟把搿毒这样馥阋鬃集合记为p 嚣魏多顼式 时间可解问题就称为p 类问题 绘定一个判定闯题，魏渠存在个算法，鼹任鹰一拿答案麓“是”豹实铡厶 该算法首先给出一个猜想，该猜想规模不超过，的输入长度的某个多项式函数， 且验泌猿想的正确牲仅霭多项式时瓣，则称该润题j 嚣予n p 类 设有两个判定问题万，石，如果对而的任一实例，。可以多项式时间构造出 靛一个万，实例，使，的答案为“是”当且仅当j ，的答案为“是”，则称石，w 以多 项式时间归约到疗：如慕玎。可阻多项式时间归约到硝：，而石：肖多项式时间算 法，则茁，也有多项式时阉算法。 恣义1 3 5 n ，p 一难如果p 类中所有问鼷都可以多项式时间蛸约到p 类中 菜个闯题z ，则称荭是n p 完全阉题如栗筇；是n p 一完全闯嫩，石，n p ，且 丌。可以多项式时闯归约到疗：，则玛是p 一完全问题如果某优化问题霈的判 定问题是尸一宠全的，则称石问越是n p 一难p h 删) 的。 简单而言，n p 一难问题也就是不可能在多项式时间内找到最优解的算 法这样，一个自然的想法就是放舞对最优解的寻找，而把研究的重点转向寻找 能在较短辩闻( 多项式爵游讷褥到接近于最後解静算法。 我们衡量黧法的优劣可从两个方面来看，一是算法的时间复杂性，二照算法 褥裂辫簿擅与矮往解毽熬接近程度，秀度爨接近程痰，我们定义最蓼撼猿爨 ( w o r s t - c a s er a t i o ) 定义l 。3 6 最坏情况界对于使髫标函数厂为最小的离线优化闯题万，记刊黾 这个优化问鼷的一个实例，并记，( ，) 是实例，的最优瓣标函数德( 即最优馑) ， 厶( ，) 是算法尉的目标凰数值如果存在一个实数r ( r 1 ) ，对于任何实例柏亍 厶( d r f ( 1 ) 。 那么称，是算法的一个上界相应的可以定义目标函数为最大的上界的定义如 果不魏确定算法是否畜器，或者麓够骥定算法戆上器怒无穷大黪，这个冀法般 称为是启发式辣法当，是有限数( 不是无穷大) 时，这个算法一般称为近似算 法 遴一步，设胃是极小化目标问题厅的一个近似算法，蘑胃解其实例j 得到 浙江大学硕士学位论文 的解值为兀( ，) ，称 p 。= i n f p 1 i 厶( d 兰p ，( ) ，v 1 ) p 为算法h 的最坏情况界如果矾是极大化目标问题，则称 p t t = s u p p 1 i 厶( ) p ，( nv d ， 为算法h 的最坏情况界 对于使目标函数厂为最小的在线优化问题石。，对在线算法4 ，用竞争比 ( c o m p e t i t i v er a t i o ) 来衡量它的最坏情况，常用q 表示设，( ) 是实例1 在离线情 况下的最优目标函数值( 即最优值) ，则称 q = i1 i 厶( j ) 厂( d ， onfp p v i 为在线算法4 求该问题的竞争比对于极大化在线问题同样可以给出相应的概 念，称 c a = s u p p 1 l l ( ) p 厂( nv i 口 为在线算法一求该问题的竞争比 有关计算复杂性的理论可参见【y h c o l 】 f g 7 9 浙江大学硕士学位论文 1 4 本论文主要结果 在本文中，我们研究的排序问题的两种具体问题 在第二章中，我们首先讨论了离线状态下流水作业机排序问题，即两台流水 作业机器所有工件的信息在排序开始前都已知道，工件由于加工方法或工件长 度等原因要分组进行加工，每组工件在加工之前都有准备时间，工件需依次经过 两台机器分别加工一次，优化目标是求极小化加权总完工时间，即 m i n y 彬，c 。本文提出了一个近似算法，并证明了其最坏情况界为2 接下 j 。o o 来研究了在线状态下流水作业机排序问题，工件是分组到达的，即排完了前一组 后一组工件的信息才知道，优化目标是极小化最大工件完工时间1 t i a x e ，同样 提出了一个近似算法，并证明其竞争比为2 ，并证明不可能存在竞争比小于2 的 在线近似算法 第三章我们讨论了单台机器在有维护时段约束的排序问题，机器在维护时期 是不能加工工件的，目标是求总完工时间y g 最小，将文献中基于邻域搜索思 想的2 - o p t 操作推广为七，k 一交换操作，利用此操作，给出了一个多项式时间近 似方案 浙江大学硕士学位论文 第二章流水作业两台机器的成组排序的一个新问题 2 1 引言 流水作业问题是由j o h n s o n 【j s m 5 4 最早研究的，他研究了两台机器目标是 求极小化最大完工时间，提出了个最优的算法，人们都称之为j o h n s o n 算法该 算法可描述为：把需要加工的n 个工件分成两个互不相交的子集s 和最，这里 s = 正：n p ，：) 和足= 以：p t 。 只：) ；在s 中的工件按p f t 非减的顺序排序，在 马中的工件按p ，：非增的顺序排序，的工件全部排在是前；其中只，p i ：分别 表示第i 个工件在机器1 和机器2 上的加工时间后来的流水作业排序问题的模 型都是在这个基础上发展而来的 i g n a l l 和s c h r a g e i s 6 5 1 在1 9 6 5 年最早研究了e | | c ，并提出t - - + # 枝定界法g a r e y ，j o h n s o n 和s e t h i 【g j s 7 6 】在1 9 7 6 年证明了当目标为极小 化最大完工时间时，对m 台流水作业机排序问题，当m 3 时是n p - 难的；当目 标为极小化总完工时间罗c ，或平均完工时n ( m e a n f l o wt i m e ) 时，m 2 时这个排 序问题是强p 难的由于问题的难解性，很多人都在寻找n 个工件m 台机器目 标为求总完工时间的启发式算法，人们提出了各种各样的启发式算法，h o 在1 9 9 5 年【h j c 9 5 】、w a n g ，c h u 和p r o t h 在1 9 9 7 年【w c p 9 7 】、a l l a h v e r d i 和a l d o w a i s a n 在2 0 0 2 年【a a 0 2 】中都给出了各自的算法g o z a l e z 和s a h n i 在1 9 7 8 年【g s 7 8 】 中，研究了m 台流水作业机器目标为极小化总完工时间f c ，的排序问题，提出 一个最坏情况界为m 近似算法在这里我们主要讨论两台机器流水作业排序， 多台机器的排序不再多介绍h o o g e v e e n 和k a w a g u c h i 在1 9 9 9 年 h k 9 9 1 也研 究了| | c ，提出了一个近似算法，它以( b 。+ b ：) 非减的顺序为排序依据进 浙江大学硕士学位愉文 牙撵序，其最坏 毒况雾为2 声，够+ 鼎) ，劳曼是紧懿，冀中箩窝娃分爨表示工俘麓 工时间中的最长和最短的加工时间 滚水终业瓣序阕题逐寿其恁愆演变。铡舞，无等德( n o - w a i t ) 限裁，楚攘每个 工件的各相邻机器之间怒连续加工的a l d o w a i s a n 【a t o l 】等很多人已研究了 这类阀题蹲例如，枫器在加工过程中有维护时段，农其健模型巾早已考入磅究 过，l e e 在1 9 9 7 年 l c y 9 7 1 把遮种维护时段引入到两台机器流水作业摊序中， 提出了一个的流水作业排序的一个新问题本章将成缎技术弓l 入两台机器流水作 业撵序中 成组技术( g r o u pt e c h n o l o g y ，g t ) 是利用任务的某种性质将任务分成精干组 秀避行秀霭工，娃提高生产效率鹃一静涿理帮方法。毽虢是说，蔽据工件困定方法、 安凝时间的不同分成不同的组，同组中的工件接连加工时，不需蒙或需要较少的 安装跨震：哭建在不弱缌豹工 串接连热工辩，羽蒿要一定夔安装( 诿整) 瓣阕。 本章考虑工件构成比较复杂的排序问题，根据工件所用的夹具和刀旗的不 同，王磐罴分戏不同缝遴嚣翅工，以减奎在秘工过程中爨换夹吴灏刃具夔次数。具 体地说，我们讨论如下定义的两台流水作业机器成组加工的排序问题： 设有n 个工件，工传都在零时刻到达，郎在开始摊序以前融知全部工传排序 所用的所有信息由子装具和工装要求，它们将分为m 组加工，假设工件已经 分好缀，只有机器在加工完一组所有的工件后才能加工另一组工件，第i 缀记为 q ，其中共奢n t 个工件( - - 1 ，2 ，掰) 设有两台机器m 和掰：。每个工件需要首 先在机器蝎上加工完毕，然后再在机器m ：上加工第f 组的第，个工l 牛记为 厶泸l 2 ，m ) ，箕在m 1 和甜：上的加工时间分剐为呜和舀( 已包含工伴的装卸 时间) ，其权黧为形，在两台机器上每组中工件的加置次序是一样的，在两台机 器上各个组的加工次序墩是一样的每台机器在莱一对刻只能加工一个工件，一 个工传在某一时刻只能在一台机器上被加工，每台机器在加工每一组工件之前都 有一个调整辩润，第i 缀在甄、材：上的谲藏时涸分稍记为爵鞠s ：0 = i ，2 ，。，撬) ， 是用来安装针对加工这缌工件所需的夹具和刀具的时间。用c 1 口、c 2 ，和e ，分别 表示工件，。在枫器码、机器掰：上的完工时闯和该工件的最终完工珏寸闯，则有 浙江火学硕士学位论文 巴2 c 3 ”目标是求极小化加权总完工时间，即m i n 。彬，g 用三参数法， 该问题可表示为五i s ，g t t 。q ，其中，s 表示调整时闽，g r 表示成缀加 工 如果所有调整时间为0 ，每组只有一个工件，本问题变为经麒排序问题 五形，它是卿一垂戆戆，因魏奉文露讨论弱阕嚣毽是船一困难，掰鼓 近似算法的设计与分析是十分必要的s u n g 霹班y o o n 在1 9 9 8 年 s y 9 8 研究了 ei | 形c ，给出了两个近似算法，最坏情况界都为2 a l l a n v e r d i 在2 0 0 0 年 【a a 0 0 】戮究了每个工穆都疆立繁调蘩对润豹嚣台瓿器滚东箨监鞠题 i s , i c ，给出了一个分枝定界法，并用数据验证了该方法的复杂性y a n g 和 c h e m y c 0 0 在2 0 0 0 年研究了工件分组并且每组工件在加工前裔准备时间和 加工厥有运输时间的骶台机器流水l 乍灶封 序阏题曩l s ，r , g t l c 蠡，绘出了一个多 项式时间算法，并证明其算法能够得到最优解本章所讨论的问题尚未见研究， 我稍褥绘塞一令透纭算法，并涯鞠它雏最坏憾翼舞爻2 ，量该赛楚紧豹。 在本章的第三节中，将讨论e 旧g r i 问题的在线排序，并给出了一个最 坏情况界为2 的近似算法，并证明不可能存在最坏情况界小于2 的在线近似算 法。淀意对墨l lc m 。问题的在线撼序，也存在最坏情况界为2 的近似算法，思是 最好可能【c p w 9 8 】 浙江大学硕士学位论文 2 2 1 算法 2 2 e 旧c r l y 。c ，问题 在单台机排序中，当目标为极小化加权总完工时1 1 司的方法，加权最短加工时 间优先( w e i g h t e ds h o r t e s tp r o c e s s i n gt i m ef i r s t ，简记为w s p t ) 算法可产生最优解 工件按w ，p ，非增的顺序进行排序下面利用此规则给出求解 es ，g ti 。c 。问题的一个近似算法，记为a 1 算法爿1 ： 1 对同组中的工件，按w s p t ) 删h i ( 二铲非减顺序排序) ； 2 对每一组g ，计算q = s ；+ s ：+ ( 4 + 岛) ，形= ； 3 将各组按参非减顺序加工 显然上述算法的时间复杂性为o ( n l o g n ) 以下假设每个工件的编号已满足 算法要求的顺序，即对任意i = 1 2 ，m ，有 等羔警茎警及鲁嚣s 甓 2 2 2 最优值的下界估计 定理2 2 1 设盯是问题的一个最优排序，则有 mn1 厂mj _ im m，、 艺q ( a ) 告l 艺q ，+ 艺 ，+ s ：+ 岛) + ( 以+ 最) i - i = 1j = l i = l ，司 i = 1 i = 1 尸i 滓l ，2 i t 寸 证明对于任一排序，为简单计，将此排序下第i 个加工组中第，个位置的 工件记为第i 组中的第，个工件即j i 。( i = 1 2 ，m ，j 1 2 ，n r ) 浙江大学硕士学位论文 显然第f 组的第1 个工件在第1 台机器m 上的完工时间q 。为：前l 组( 第i - l 组) 工件在第1 台机器m 上的完工时间加上第f 。组在第l 台机器上的调整时间s i 和第i 组的第1 个工件在第1 台机器m 的加工时间a j 。；第i 组的第1 个工件在 第二台机器m ：上的完工时间为：前1g f l ( 第i 一1 组) 的工件在第二台机器j l 如上 的完工时间加上第i 。组在第二台机器上的调整时间s ：与第i 组的第1 个工件在 第1 台机器m i 的完工时间c - 的最大值加上第i 组的第1 个工件在第2 台机器m ： 的加工时间b i ：可写为 q l = q - 1 1 + s + a ， 岛= m a x g ! 。，c ； _ 1 。+ 墨： + e 。 同理，对第i 组的第j 个工件有 ， i - ln ，一 q ，= 口川+ 4 y = 掣吐忆+ 墨。+ 如= 如+ 品+ 4 k = l= ip = li = 1k - 1 c 力= m a ) ( q p c 2 j 。) + 置y ( 2 1 ) 由式( 2 1 ) 得 由式( 2 3 ) 得 ( 2 2 ) 岛之c ，z ，q + e y = m a x q 产l ，c o q p 尽7 1 + e y ( 2 _ 3 ) c ；i 2 c ；h + b i i 将式( 2 2 ) 式( 2 4 ) 相加得 ( 2 4 ) is l + s ，2 + ( 如+ 玩) i + s 。+ s n + ( 爿m + b m ) + b “ ( 2 5 ) ，；l 、女= 1，k = l n t 由于q ，= s 。+ s f ：+ ( 如+ 巩) ，式( 2 5 ) 可改写为 2 ，e + 4 ， +s i闰 + 臆 4 唧糊 h h = ， b + ， q 一 ：吖 c j醇 ，m + 昌 i h + 。n 一 ， 耳 + ， 醇 + 、j耳 + 4 ( ， + 昌 墨 t i m + )稚 + 如 ( n 一 四。 2 浙江大学硕士学位论文 ，一lj 2 岛兰翁+ 墨，+ s ，：+ ( 囊* 牛毽* ) + 毒_ ， - i扣t 对式( 2 。6 ) 两边同乘以彬y ，褥 ( 2 6 ) i = 1m 。慨+ 善( 4 。屿小叫 ( 2 7 ) y ，。一f + s 。+ s 。+ ( 4 。+ e ，。) + 1 ( 2 7 = 1 将式 2 7 ) 关于f l - l 2 ，捌，k l 2 ，靠，鞠期褥 mh z m 岛ff 一1j、 z z 2 b 黑! 鎏竺攀型一翌 1 q ( 仃) 一昙f 杰壹( 4 。+ 玩) + 窆岱。+ s ，：) + 曰。1 。 。 为o 第1 组的惟一工件为j ：4 。= n ，b 。，= 1 分两种情况讨论 情况1 在n + l 时刻前某个时刻开始加工。这时来第2 组的惟一工件以，： 爿：i = 1 ，b ：= ，且不再来其他工件由于在线排序不允许重排，且预留的时段不 够安排 。显然得c 2 l ( 口) 2 n + 1 而最优排序为盯+ 2 ( j 2 ，j l 。) ， c 2 l p + ) = n + 2 在h o 。有c 2 1 ( 盯) c 2 1 ( + ) 2 2 情况2 直到n + l 时刻后才开始加工以。则不再来任何3 - 件可得 c ：p ) = 2 n + 2 ，而最优排序在零时刻开始加t ，c ：。p + ) = 珂+ 1 从而 c n ( o ) c ：( 盯) = 2 所以任何在线排序的竞争比至少为2 i 浙江大学硕士学位论文 第三章有维护时段的单台机器排序问题 3 1 引言 本章研究下述单台机排序问题：给定n 个工件，= 以i f _ 1 , k ，f ) ，工件以的 加工时间为p ，每个工件都需要在一台机器上不中断的加工机器有一个维护时 段，维护开始的时间为r ，且维护持续的时间为l 在维护期内，机器是不能加 工工件的目标为寻找一个排序使得总完工时间尽可能小该问题用三参数法可 表示为l ，啊l i c j a d i r i 等a a b f r 8 9 及l e e 和l i m a ni l l 9 2 z 研n t n + 问题，用不同规约方法证明了这个问题是n p - - 目i 的，都研究了s p t 算法( s h o r t e s t p r o c e s s i n gt i m e ) a d i r i 等人 a b f r 8 9 】提出s p t 算法的最坏情况界为5 4 ，l e e 和l i m a n l l 9 2 】证明了s p t 算法的最坏情况界为9 7 同时也证明t