（运筹学与控制论专业论文）带到达时间的单位工件在线排序.pdf

浙江大学硕士学位论文 摘要 本文主要研究了单台机上带到达时间的单位工件在线排序问 题，并且给出了最优的在线算法。全文共分为两章。 第一章是绪论部分，简要介绍了组合优化、排序问题、算法和 算法的界及竞争比等基本概念。 在第二章中，我们详细介绍了单台机上的单位工件在线排序问 题，其目标函数为极小化最大机器完工时间c 一。在第一节中，简 要描述了单台机上带到达时间的单位工件在线排序问题：1i o n l i n ei c ；在第二节中，证明了问题1 io n l i n ei c 一的下界为 1 3 9 8 ；在第三节中，设计了一种算法，并证明了该算法的竞争比 rs 1 3 9 8 ，从而证明了该算法是最优在线算法。最后给出了两台机器 情形下的一个猜测：月( 2 ，i s ) = 昙。 关键词：排序，在线，竞争比，最优算法 浙江大学硕士学位论文 a b s t r a c t t h i sp a p e rm a i n l ys t u d i e st h ef o l l o w i n gp r o b l e m ：o n l i n es c h e d u l i n g f o ru n i tj o b sw i t hr e l e a s et i m e so ns i n g l em a c h i n e w ep r e s e n ta n o p t i m a la l g o r i t h m “t h ep a p e rc o n s i s t so ft w oc h a p t e r s i nc h a p t e r1 ，w ei n t r o d u c es o m eb a s i cn o t i o n s ：c o m b i n a t i o n a l o 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 s ，a l g o r i t h ma n dc o m p e t i t i v e r a t i o i nc h a p t e r2 ，w ei n v e s tig a t et h eo n li n es c h e d u li n gp r o b l e m f o ru n i tj o b sw i t hr e i e a s et i m e so ns i n g l em a c h i n e t h eg o a l i st om i n i m i z et h em a x i m u mm a c h i n ec o m p l e t i o nt i m e i nt h e f i r s ts e c t i o n ，w ei n t r o d u c et h ep r o b l e m ：1lo n l i n ei c 二1 1 1 t h es e c o n ds e c t i o n ，w ep r e s e n tt h a tl o w e rb o u n do f t h e p r o b l e mi s 1 3 9 8 i n t h et h i r ds e c t i o n w ed e s i g na no n l i n ea l g o r i t h ma n ds h o wt h a ti ti sa l l o p t i m a lo n l i n ea l g o r i t h mm a t c h i n gt h eb o u n d o f1 3 9 8 k e y w o r d s ：s c h e d u l i n g ，o n l i n e ，c o m p e t i t i v er a t i o ，o p t i m a la l g o r i t h m 浙江大学硕士学位论文 第一章绪论 1 1 组合优化 组合优化问题又称为离散优化问题，是一类重要的优化问题。从十七世纪开 始，许多数学家已经开始对组合优化问题进行研究。到了二十世纪后期，伴随着 工业科技革命和现代化管理科学的发展，特别是计算机技术的突飞猛进，组合优 化问题越来越受到应用数学、计算机科学及管理科学等诸多学科的高度重视，并 逐渐发展成为一门新兴的学科分支。 组合优化问题描述如下：令q = 和l ，s 2 ，s 。) 为所有状态构成的解空 间，c ( s f ) 为状态墨对应的目标函数值，要求解占，使得任意s f q ， c ( s ) = m i n ( s f ) 典型的组合优化问题有排序( s c h e d u l i n g ) 问题、指派( a s s i g n m e n t ) 问题、旅行商( t r a v e l l i n gs a l e s m a n ) 问题、背包( k n a p s a c k ) 问题、装 箱问题( b i np a c k i n 萄问题、图着色( g r a p hc o l o r i n g ) 问题、分划( s e t p a r t i t i o n i n g ) 问题、斯坦纳最小树( 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 ) 问题、最小费用流 ( m i n c o s tf l o w ) 问题等。组合优化问题的详细介绍可参见 6 和 7 。 上述问题描述均非常简单，并且有很强的工程代表性，但最优化求解很困 难。很多组合优化问题都可以给出整数规划( 或混合整数规划) 描述，从而可 利用整数线性规划的技巧( 如分支定界法) 来求解，但是由于整数规划的求解 具有相当大的难度，而组合优化又涵盖很广，因此人们转而研究问题的组合结 构，试图寻找又针对性的求解方法。 1 浙江大学硕士学位论文 1 2 捧序问题 排序( s c h e d u l i n g ) 问题是组合优化中一类有着重要理论意义和广泛实际 背景的问题。排序问题产生的背景主要是机器制造，后来被广泛应用于计算机 系统j 运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度， 学校课程表的制订，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论 和算法。近几十年来，排序问题得到了运筹学界、计算机科学界、工程学界和 管理学界极大的关注，鉴于经典问题的研究日益深入，而具有实际背景的新问 题又不断涌现，可以说，对排序问题的研究正在进入成熟期。 按照学术界多年来形成的惯例，一般用所谓的“三参数表示( t h r e e f i e l d r e p r e s e n t a t i o n ) ”口吲y l 来表示一个具体的排序问题。三个参数口，分 别刻画了特定的机器状况，工件特征和最优准则 2 ，下面我们分别对此作一简 要介绍。 机器状况描述了排序问题中机器的数量以及与机器有关的各种信息。常见的 机器状况有单台机( s i n g l em a c h i n e ) 、同型平行机( i d e n t i c a lp a r a l l e l m a c h i n e s ) 、同类平行机( u n i f o r mp a r a l l e lm a c h i n e s ) 、不同类型平行机 ( u n r e l a t e dp a r a l l e lm a c h i n e s ) 、流水作业( f l o ws h o p ) 、有序作业( j o b s h o p ) 、自由作业( o p e ns h o p ) 等等 8 。 其中同型平行机、同类平行机和不同类型平行机这三种机器状况的具体含义 如下： 同型平行机：系统中所有机器功能、效率完全一样，我们用符号p i i l 表示m 台同 型平行机； 同类平行机：系统中机器有各自不同的速度，但是任意工件在不同机器上的 一2 一 浙江大学硕士学位论文 加工时间有相同的比例关系，我们用q i l l 表示m 台同类平行机； 不同类型平行机：系统中机器各不相同，工件在不同机器上的加工时闻比不 全相同。 在三参数表示法中，它们分别用p ，q ，r 表示。习惯上也常常把这三种机器 状况归为一类，统称为平行机( p a r a l l e lm a c h i n e s ) 。本论文涉及到的排序问 题都是同型机这种机器状况。 工件特征一般是指工件信息是在线还是离线，工件在加工过程中是否可中 断，中断后是否在恢复加工时要受惩罚，工件是否需要准备时间，工件之间是否 存在优先加工的约束，以及工件的加工时间是否有特殊性等等。在经典排序文献 中，根据排序者在排序时掌握工件信息的多少又可把排序问题分为离线 ( o f f l i n e ) 、在线( o n l i n e ) 和半在线( s e m i o n l i n e ) 。 排序问题的实质是寻找对所需完成的任务( 工件) 以合理的安排以得到某种 意义下的最优结果，这就涉及到所谓的最优准则，通俗的讲也就是以什么为目标 函数。如果记q 为在某个满足排序问题要求的可行排序下工件的完工时间， 而在该排序下机器m ，的完工时间为丘，则称c 一= m c ，为该排序的最大完 工时间( m a k e s p a n ) ，c m i n = m i nl 。为该排序的最小机器负载。于是( 1 。和( k 就可看成是某种最优准则下的目标函数，对于前者，最优准则可叙述为找一个可 行排序，使得它的最大完工时间c 。在所有的可行排序中取得最小的值即这时 是极小化目标函数；对于后者，最优准则可叙述为找一个可行排序，使得它的最 小机器负载c 。在所有的可行排序中取得最大的值，即这时是极大化目标函数。 当然，除了上面的两个目标函数以外，排序问题中还有很多目标函数，较常见的 有总完工时间，最大延误时间，最大误工时间等。 一1 一 浙江大学硕士学位论文 1 3 算法和算法的界 算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰 描述。确定性算法从前一步到后一步的运行由当时状态唯一确定。如果存在一个 算法，它对排序问题的每个实例，经有限步后，都可以得到该实例的一个可行排 序，那么称该算法解此排序问题。 由于绝大多数排序问题是n p 难题，其最优解往往很难找到，但是根据实际 需要，又常常需要去求问题的启发式解或近似解。因此排序问题主要有两个方向。 一是对p 问题，即多项式时间可解问题，要寻找多项式时间算法( 又称有效算法) 来得到问题的最优解，或者对n p 难题的某些特殊情况下( 如工件加工允许中断， 工件的加工时间都是单位长度，工件之间有某种约束等等) 寻找有效算法，也就 是研究n p 难问题的多项式时间可解的特殊情况。二是设计性能优良的启发式算法 和近似算法j 当然，无论是启发式算法还是近似算法，其计算时间都应当是多项 式时间的。 衡量算法的“优良”程度有三种办法：数值实例计算分析，最坏情况分析和 概率分析这三种办法各有优点，也各有不足之处。目前理论上用的最多的是算 法的最坏情况分析。 定义对于使目标函数厂为最大的优化问题，记是这个优化问题的一个实 例，p 是所有实例的全体；并记 o p t ( 1 ) 是实例，的最优目标函数值( 即最优值) ， 厶( ，) 是算法爿的目标函数值 如果存在一个实数p ( p 1 ) ，对于任何的i p 有 p l ( ，) o p t ( 1 ) ， 一4 一 浙江大学硕士学位论文 那么称族算法爿的一个下界。 如果不能确定算法是否有界，或者能够确定算法的下界是无穷大时，这个算 法称为启发式算法。当p 是有限数时，这个算法称为是近似算法，即近似算法是 有界的启发式算法。用启发式算法和近似算法得到的解分别称为启发式解和近似 解。对于使上式成立的最小正数p 称为是算法的最坏性能比，也称为是算法的紧 界。 对于使目标函数为最小的优化问题，同样可以定义算法的一个下界和紧 界等下界p 仍是p 1 ，但是对于任何i p 有 六( ，) p o p t ( i ) ， 而紧界也是使上式成立的最小正数。 一5 一 浙江大学硕士学位论文 1 4 在线捧序和竞争比 经典排序假设排序问题一个实例的所有信息，包括工件的个数、就绪 时间、加工时间等在开始排序前都是事先知道的。这种情况我们称之为离 线( o i f - l i n e ) 然而在现实生活中许多情况并非如此，而是所有信息知道之 前就必须进行排序，这种情况称之为在线( o n l i i l e ) 的或者是半在线( s e m i o n 一1 m e ) 的。在在线排序问题中工件的信息是逐个释放的，决定当前工件 的加工时对其后面就绪的工件的信息是一无所知的，并且一旦决定工件的 安排后，其后就不允许再作任何改变。 解在线问题的算法被称为在线算法。衡量一个在线排序算法最常用的 指标是它的竞争度( c o m p e t i t i v e n e s s ) 。即把在线排序算法的结果与对相 同工件运用离线排序算法得到的结果进行比较1 5 1 。更确切地说，我们用竞 争比( c o m p e t i t i v er a t i o ) r a 来衡量一个在线排序算法a 的性能。对于 使目标函数为最小的在线排序问题，竞争比一定义为对问题的所有实例的 比值器的上黼舭。呷 器m 1 0 其中 ( 之( ，) 和c 急( ，) 分别表示由这个算法a 所得到的目标函数和相应的 离线排序的最优值，在不引起混淆时可分别简记作c ：。和( 墨。这时这 个在线排序算法称为r 竞争算法。进一步，如果不存在别的在线排序算法 的竞争比小于在线排序算法a 的竞争比，那么称这个在线排序算法a 是最 优( o p t i m a l ) 的。这时a 的竞争比又称为在线算法竞争比的下界( 1 0 w e r b o u n d ) 。对于使目标函数为最大的在线排序问题，可以类似定义竞争比 一6 一 浙江大学硕士学位论文 肛s u p 篇，v ，) 珈下界 一个在线排序算法的竞争度是与离线排序的最优算法进行比较而得的因 而，竞争度是表示由于问题实例没有获得完全信息所造成的损失。假设加工工 件的一个次序需要一个固定的费用这个费用是由相应的离线排序的最好算法 所确定的，因而也能把这个费用减少到最小同时，还假设在线算法对于给定的 一个工件次序的性能是可以用竞争比来衡量的，能够达到这个固有的费用的。 因而，能够把在线排序算法的排序过程看成是寻找工件次序的过程这个工件次 序是度量给定的在线排序算法的竞争度的基础。 l p t 算法1 3 】和l s 算法1 2 】分别是经典的离线算法和在线算法。l p t 算法是 把所有工件按加工时间的非增序排列，然后依次将它们安排在能使其最早完工 的机器上加工而l s 算法只是将工件按到达的顺序安排在能使其最早完工的机 器上加工。 1 浙江大学硕士学位论文 第二章单台机上单位工件在线排序问题 2 1 问题：1io n l i n eic 删的描述 自从g r a h a m 在1 9 6 9 年提出了m 台同型平行机上经典在线排序问题i i l 以 来，在线排序问题得到了深入地研究和发展。在经典在线排序问题中，当一个 工件到达时，必须立刻决定在某一台机器上进行加工，同时对当前工件后面就 绪的工件的信息是一无所知的。目标是极小化最大机器完工时间。同型机在线 排序的最简算法是g r a h a m 在1 9 6 9 年提出的l i s ts c h e d u l i n g ( 简记为l s ) 算法。 作为g r a h a m 的m 台同型平行机上经典在线排序问题的一个推广，l i & h 啪g 【3 l 提出了如下在线排序问题：给定一个工件序列口= _ ，l ，厶，歹。) ， 需要把它们不可中断地安排到m 台同型平行机上去加工，其中工件歹，的到达时 间是任意的( a r b i t r a r yr e l e a s et i m e ) ，而不是很多文献中所假定的工件到达 时间严格不减，其加工时间是p ，一旦决定工件的安排后，其后就不允许再作 任何改变。得到了如下结果：r ( 棚，l s ) ：3 一一1 随后l i & h u a n g l 4 1 3 l 在上述问题的基础上研究了加工时间受限的情况：给 定一个工件序列仃= - ，1 ，2 ，l ) ，需要把它们不可中断地安排到m 台同型 平行机上去加工，其中每个工件的到达时间是任意的，每个工件的加工时间 p 。均位于 p ，r p z 间，其中，1 ，p 0 ，工件的信息在其到达时刻才知道， 决定当前工件的加工时对其后面就绪的工件的信息是一无所知的，并且一旦决 定工件的安排后，其后就不允许再作任何改变。得到了如下结果： 一8 一 浙江大学硕士学位论文 ( 1 ) 对任意所 2 f 利蚍踯t 1 + 旦墨叠= 旦， i 3 一土一，旦 i1 + 2 r 坍( 1 + 2 r ) 7 历一1 ( 2 ) r ( 1 ，l s ) 小南， ( 3 ) 肥船) = 夏5 而r + 4 ，r 4 我们现在考虑单台机上单位工件在线排序问题：给定一个工件序列 盯= 1 在y - l + s ( 堤- - 个可任意小的正数) 时刻又来一个工件厶 对于任意算法a ，都有 c o ( 彳) y + 2 ， 0 p r ( 仃) = y 一1 + 6 + 1 + l = ) ，+ 1 + 则竞争比r a y y + + l + 2 占专7 y + 玎2 ，占专。； 情形2 ：x ，则蜀= r j + 1 ，啊= 佃，转入步骤2 ； 若o ，2s ，贝0 j 2 = m a x r 2 ，+ 1 ) ， g l = j 2 + l ，h i = 佃，转入步骤2 ； 一1 2 一 浙江大学硕士学位论文 ( 2 ) 当口 多，贝q 9 1 = 1 + l ，拐= 佃，转入步骤2 ； 若一1 夕时，贝u j l = ， 步骤2 ： g 。= 毛一b 。j 啊= s 。， 9 2 = 西+ 1 ，= 佃，转入步骤2 ； 若g l ，取= g l ( 1 ) 当 g ，h j 一1 ) 时，贝o j ，= g j + j 一g ， i 若s ，= g f ， 当h j 一_ 一1 = 0 时，n i j = l j + l ，g ，= g ，+ l ，h j = h j + l ： 当乃一s 一1 o 时，则，= i j ，g ，= g + 1 ，h j = h j ； 若j g j j ，= 勺一1 ，则，= i j ，g = g j , h j = h j l ； 若g j s t o , 贝l j g = g 川+ 1 ，乃“= 乃+ l 一1 4 浙江大学硕士学位论文 2 3 2 算法的最优性证明 引理l ：对于任何工件序列盯，都有c 。( 力 - o p t ( a ) + 1 证明：( 归纳法：对工件的个数n 进行归纳) 下记c 一( f ) 表示c 一( 力，o p t ( i ) 表示o p t ( c r ) ， 其中盯表示由i 个工件组成的工件序列。 l i 当n = l 时， 若口时，贝叽c 。( 1 ) = 1 + 1 = o p t ( 1 ) ； ：g a 夕，贝0 c 腑( 1 ) = p + l ， o p t ( 1 ) = + i ， 又因为夕1 5 1 1 ，口0 7 9 5 所以一口 1 ，因而一 1 故c 缸( 1 ) = 夕+ l ，贝0 c 衄( 1 ) = r l + 1 = o p t ( 1 ) 因而当n = l 时，c 一( 1 ) o p t ( 1 ) + i 成立 2 0 假设当n = k 时，结论成立，即g 。( 后) o p t ( 后) + i 则当n = k + l 时，欲证g 。( 七+ 1 ) o e r ( k + 1 ) + 1 下面分三种情形来讨论： 情形1 ：当第k + 1 个工件 + l 到达时，在算法序中 + 1 安排在 ( 1 m 。( 后) 之前加工( 如图i 所示) 一1 5 浙江大学硕士学位论文 _ ，i + 1 山 图1 则c ：。( 后+ 1 ) = c - m 。( 七) ，o p t ( k + 1 ) o p t ( k ) ， 又由假设：g 。( 七) o p t ( k ) + 1 ， 所以( i 。( 后+ 1 ) = ( n 。( | j ) o p t ( k ) + 1 o p t ( k + 1 1 + 1 即c ，m 。( 七+ 1 ) o p t ( k + 1 ) + 1 情形2 ：当第l ( + 1 个工件 + 1 到达时，在算法序中j 安排在 c o ( 后) 时刻加工 贝0 c ：。( 七+ 1 ) = c 。( 尼) + 1 ， 个 ( 七) 记【a ，b 是距离c 。 ) 最近的一个空闲间隔，即最后一个空闲间隔 ( 如图2 所示) 因为在算法序中 + l 被安排在e 。( 女) 时刻加工，说明 a r k + 1 蔓c 一( 露) ，此时记所有在空闲间隔【a ，b 】之后加工的工件集合为 以，则以中的所有工件的到达时间都大于a 且小于等于g 。( 七) 。 一1 6 浙江大学硕士学位论文 j k + l 上 t个 ab 个 ( 七) 图2 又因为 a ，b 】为最后一个空闲间隔，所以在计算o p r ( k + 1 ) 时，以中 的所有工件的加工顺序不发生任何变化， 由此可得：o p t ( k + 1 ) o e t ( k ) + 1 又由假设：c 乙。( i ) o p t ( 后) + 1 ， 所以c m 。( 七+ 1 ) = ( m 。( | i ) + 1 o p t ( k ) + 1 + 1 o p t ( 七+ 1 ) + 1 即c r m 。( 后+ 1 ) o p t ( k + 1 ) + 1 情形3 ：当第k + 1 个工件j 到达时，在算法序中五+ 1 安排在 ( ? 。( 后) + “由i a 算法可知t 为某个正整数) 时刻加工 ( 如图3 所示) 。 ，七+ l 上 图3 一1 7 一 个个 c o ( j ) c 二( | i ) + t 浙江大学硕士学位论文 则c m 。( 七+ 1 ) = c 衄( 七) + f + l ，o p t ( k + 1 ) o p t ( k ) + f + 1 又因为c 一( 七) s o p t ( k ) + 1 ， 所以c 二。( 后+ 1 ) = c 幺( 七) + f + 1 o p t ( k ) + 1 + t + 1 o p r ( k + 1 1 + 1 即c t m 。( 七+ 1 ) o p t ( k + 1 ) + 1 所以当n = k + l 时，g 。( i + 1 ) o p t ( k + 1 ) + 1 成立 综上所述，( ? 。( 仃) o p t ( a ) + 1 成立 定理2 ：队算法的竞争比尺埘1 + 詈，从而是最优的 证明：竞争比如= 掣篇) ，其中盯是任一工件蒯 又由引理1 可知，c 一( 盯) o p t ( a ) + 1 所巩= 警 踹) 面o p t ( 丽c 0 + 1 下面就o p t ( a ) 的取值分两种情形讨论： 情形1 ：当o p t ( 二时， 邬黑著 所以定理结论成立 s 1 + 兰1 3 9 8 2 一1 8 一 浙江大学硕士学位论文 情形2 ：当o p t ( 仃) 三时，因为o 7 口 o 8 ，所以一2 + 1 = 二 一 口 这与卯f 多这种情形不可能发生 口 觥争比如籍 等， 由2 2 节问题的下界讨论过程可知：孚= 等 一1 9 浙江大学硕士学位论文 所以竞争比月埘1 + 詈* 1 3 9 8 子情形2 ：仅加工两个工件，即n = 2 1 ) 当0 1 饼时， 因为o p t ( a ) 三，所以只考虑0 r 2 夕的情况， 口 否则将导致o e r ( o - ) 二 一 口 ( 1 ) 当0 ，2 时， c 。( 盯) = + 2 ，o p t o y ) = r 2 + 2 所以竞争岘爱 孚小争 9 8 ( 2 ) 当 ，2 ，l + 1 时， c i 。( 仃) = 1 + 2 ，o p t ( a ) = r j + 2 所以竞争峨鬟- l r j + 1 时， c 。( 盯) = r 2 + 1 ，o p t ( 盯) = 厂2 + 1 所以竞争比如兄r 2 + + 。l = l l + 詈乩3 9 8 因此，当o 1 口时，竞争比尺埘1 + 詈* 1 3 9 8 2 0 一 浙江大学硕士学位论文 2 ) 当口 ，1 时， 考虑多一1 吃 卿吃夕一i 两种情况 ( 1 ) 当一1 当吃一1 时， c i 。( 仃) = + 1 ，o p t ( o ) = 吒+ 2 所岘等竿， 因为夕+ 1 ：一2 ，故足埘上 1 + 三。1 。3 9 8 口 口 口 因此，当口 0 。这给出了相 似加工长度的在线排序问题对于l s 算法的竞争比的上界。 如果我们把相似加工长度这一条件改为单位时间加工长度，即i - = i ，并且 只考虑m - 2 的情形，那么直接把m = 2 并0f l 代入上述结果可得：r ( 2 ，岱) s 婴。 0 现在考虑到工件加工长度为单位时间这一因素，我们猜测r ( 2 ，三回= 三。 一2 2 浙江大学硕士学位论文 参考文献 【1 】r ，l g r a h a m ，b o u n d so nm u l t i p r o e e s s i n gf i n i s h i n ga n o m a l i e s 。s i a m j o u r n a lo f t a p p l i e d m a t h e m a t i c s ，1 9 6 9 ，1 7 ：4 1 6 - 4 2 9 【2 g r a h a m ，rl ，e l l a w l e r , j k l e n s t r