（管理科学与工程专业论文）具有指定到达时间的平行机在线排序问题研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：粢敛 日期：塑丑：笪： 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：坶导师签轹：琵望望日期： 复口- 大学硕十学位论文 摘要 本文以现代服务业中的预定系统为实际背景，将具有最迟完工时问的平行机 在线排序问题拓展，研究了一类具有指定到达时间和最迟完工时| 日j 的在线排序问 题( p m lp j , a r b i w a ，d jl 盯) ，并且证明了该问题是n p h a r d 问题。由于该问 题是n p h a r d 问题，所以在大规模的情况下，使用有限的资源在合理的时日j 内计 算出最优解是非常困难的事情。因此，本文将重点放在启发式在线算法的设计和 其性质的证明上面，最后，本文采用计算机模拟的方法，对启发式在线算法的效 率进行了模拟。本文的主要贡献如下： 1 针对p 2 i p ，= l ，a r b 咖a r y r j ，d jf 扩问题，证明了该问题的下界为2 。 2 在线算法i 的提出和性质的证明。本文在经典l s 算法的基础上提出第一 个启发式在线算法，并且对其性质做了分析。 3 。在线算法i i 的提出和性质的证明。为了能够有效地为末束到达系统的工 作预留空间，在在线算法i 的基础上，将两台机器分别赋予不同的优先 级，提出了在线算法i i ，并且分析了它的性质。 4 在线算法i i i 的提出和性质的证明。为了能够更为有效地为未来到达系统 的工作预留空间，在在线算法i i 的基础上，提出了在线算法i ，并且证 1 明其竞争比为2 。 4 5 提出具有0 - 1 约束的混合整数规划模型。 6 在线算法i i i 的平均境况分析。采用计算模拟的方法，使用v b a 工具，按 照工作个数将该问题分成四类，每一类用1 0 0 组数据进行测试，分别统 计它们的平均值和方差。 本文的研究成果在现代服务行业中具有具有广泛地应用i i 景，它可以应用在 服务业的预定系统中来提高设备的利用率，最大限度地满足客户的需求，例如， 可以在航空货运码头采用这种系统分配有限的站台，提高站台的利用率。 关键词：在线排序、平行机排序、指定到达时间、最迟完工时间，平均境况分析 中图分类号：0 9 3 复q 大学倾f j 学位论文 a b s t r a c t o n l i n es c h e d u l i n gi sw i d e l yu s e di nt h em o d e mm a n u f a c t u r i n gi n d u s t r ya n d s e r v i c ei n d u s t r y t h e r e f o r e ，s t u d y i n gs u c hs u b j e c ti so fg r e a tp r a c t i c a ls i g n i f i c a n c e t h i sp a p e rc o n s i d e r st h ep r o b l e mo fo l l l i n es c h e d u l i n gal i s to fi n d e p e n d e n tj o b si n w h i c he a c hj o bh a sa na r b i t r a r yr e l e a s et i m ea n dh a r d d e a d l i n eo nt w op a r a l l e l i d e n t i c a lm a c h i n e s w i t ht h r e ep a r a m e t e rm e t h o d ，t h i sp r o b l e mt h a ti sm o t i v a t e db ya r e a l b o o k i n gs y s t e m i n m o d e ms e r v i c e i n d u s t r y c a nb e n o t e d a s p 2p ，a r b i t r a r y r j ，d ，ie u i n t h i sp a p e rt h en p h 莉p r o p e i t y 。ft h i sp r o b l e mi s d e m o n s t r a t e d t h i sp a p e ra l s od e r i v e st h r e en o n t r i v i a lo n l i n ea l g o r i t h m sw i t h d e m o n s t r a t i o no ft h e i rr e s p e c t i v ep r o p e r t i e s t h er e s e a r c hh a ss e v e r a lf l o w i n g c o n t r i b u t i o n s ： 1 t h ep a p e rp r o v i d e st h ep r o o fo fd e t e r m i n i s t i cl o w e rb o u n d st w of o rt h et w o - m a c h i n ec a s e 2 t h ep a p e rd e r i v e st h eo n - l i n ea l g o r i t h mib a s e do nt h et r a d i t i o n a ll s a l g o r i t h ma n dp r o v e si t sc o m p e t i t i v er a t i o 3 t h eo i l - l i n ea l g o r i t h mi ia n dp r o o fo fi t sc o m p e t i t i v er a t i oa r ep r o v i d e di n o r d e rt ow e l lm a n a g eas c h e d u l es ot h a ta l la c c e p t e dj o b sw i l ln o tb el o s ta n dt h e r ei s s o m ei d l es p a c ef o rt h ef u t a r ej o b s 4 b a s e d0 nt h ea n a l y s i so fa l g o r i t h mi i t h ep a p e rp r o v i d e st h eb e t t e ra l g o r i t h m 1 1 1w i t hc o m p e t i t i v er a t i oo f 2 2 5t oa s s i g nt h ei d l es p a c ef o rt h ef u t u r e j o b s 5 。t h i sp a p e rp r o v i d e st h eh y b r i dp r o g r a m m i n gm o d e lf o rt h i sp r o b l e mw i t h0 - l c o n s t r a i n t 6 a v e r a g ec a s ea n a l y s i so f a l g o r i t h mi i ib yc o m p u t e rs i m u l a t i o n t h er e s e a r c ho ft h i sp a p e ri sv a l u a b l ef o rt h ep r a c t i c a ls i t u a t i o n t h ea l g o r i t h m c a l lb eu s e di nt h eb o o k i n gs y s t e mi nt h es e r v i c ei n d u s t r y f o re x a m p l e ；t h i sa l g o r i t h m c a nb eu s e di nt h ea i r p o r td o c ks y s t e mt oa s s i g nd o c k sm o r ee f f i c i e n t l y k e y w o r d s ：o n l i n es c h e d u l i n g ，p a r a l l e lm a c h i n e ，a r b i t r a r yr e l e a s et i m e ，h a r d d e a d l i n e ，a v e r a g ec a s ea n a l y s i s c l a s s i f i g a t i o nn 0 ：c 9 3 2 复且人学硕p 学位论文 1 导论 1 1 前言 排序理论又称为时间安排理论，它既是一门运筹学的分支，同时又是一门应 用科学。在排序理论中，工件是被加工的对象，是要完成的任务；机器是提供加 工的对象，是完成任务所需要的资源；安排时间表是在一定的约束条件下对工作 和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。因此，在 实际中，排序理论有着深刻的实际背景和广阔的应用前景。 生产排序理论顾名思义，与生产制造系统相关，它起源于对生产制造型企业 的生产方式的研究，其中有很多的术语如工作( j o b ) ，机器( m a c h i n e ) 等同样也与生 产制造系统相关，并且在生产制造型企业中有着广泛的应用，它是工业生产中的 一类带有普遍性的问题。比如，将原材料通过各种机器加工成某些满足条件的零 件需要排序；将生产出来的许多零件组装成某种产品需要排序；一个大型的工程 在兴建当中，必须要对各类人员进行安排、对各种器材的供应进行调度，都需要 排序。特别地，对于那些大型的、复杂的工作，排序的好坏对工程费用的大小影 响很大。然而，排序问题不仅仅存在和应用于生产过程中，而且在其他的领域中， 比如物流行业和服务行业如航空，餐饮等也同样存在着广泛的应用。在服务性行 业中，特别是餐饮和航空运输行业，排序问题也是一个非常重要的问题，排序问 题解决的好坏会对整个企业的盈利状况和客户的满意度产生直接影响。最终也会 对该企业在市场上的竞争力产生影响。在提高服务质量和客户的满意度的各种方 法当中，服务行业中的预订系统将发挥着至关重要的地位。一方面，企业良好的 预订系统会使现有的设备发挥着最大的效能；另一方面良好的预订系统也会最大 限度的满足顾客的个性化需求。因此对服务业中的预订系统的研究给在线排序的 研究带来了新的方向，同时它也受到了海内外学者的广泛关注。 目前，随着世界经济的发展，服务业在全球经济中所占的比重在不断地上升， 人们关注的重点也从原来的生产制造型企业逐渐地向服务型行业转变。然而，随 着全球竞争的不断加剧和市场全球化不断地加剧，服务企业的服务理念也从原来 的满足顾客需求朝着满足顾客的个性化需求转向。由于顾客总是期望能够买到价 格比较低廉、个性化水平高且能够按时交货的服务，因此，有效地控制成本、最 大限度地发挥现有服务资源的利用率和按时交货将成为服务型企业在竞争中脱 颖而出的重要一环。但是，当今服务业所面临的最大的挑战就是有限服务资源和 市场的个性化需求的矛盾，而良好的预订系统的设计将是解决这一矛盾的主要方 复日- 丈学硕i 。学位论文 法。因此，排序在服务业发展中的作用就不断地显现出来了。 服务行业与生产制造业有很多共同的特点，比如可以将服务系统中的服务资 源看作是生产系统中的机器，而将生产系统中的工作看作是服务系统中顾客的需 求，这样就可以将生产系统中的很多排序理论应用到服务行业中。然而，服务行 业与生产行业也有很大的不同，与传统的生产制造行业的主要不同是：在服务业 当中，所有的服务产品是都是一次性的，且不能够被存储的，即服务业当中没有 制造业意义上的库存。因此，在服务发生的时候，服务资源的利用率就成为了影 响服务业发展和盈利的一个主要的因素，而预定系统的设计就是要提高服务发生 时的资源利用率。在实际当中，顾客需求的多样性和不可预见性的特点经常会使 得现有的服务资源的配置不合理。一方面，为了提高顾客的满意度，越来越多的 服务型企业希望针对顾客提出的需求给出实时反馈和资源配置；另一方面，由于 服务资源的有限性和排他性，对某一顾客需求的满足一定是以损失其他顾客需求 为代价的。因此，如何来合理的配置现有的服务资源，使得企业能够为更多的顾 客提供服务将是运营管理和优化控制学科非常具有挑战性的领域之。困难之处 在于在服务资源的实时配置当中的参数太过复杂以及这些参数的变化太多，这使 得严格的理论结果和完美的优化模型在实际中无法得到有效地应用。比如：根据 e l l a w l e r ，j k l e n s t r a ，a ，h g r i n n o o yk a n 和d b ，s b x a o y s ( 1 9 9 3 ) 2 4 等的观点， 经典排序有资源的类型、确定性、可运算性、单目标和正则性等四个基本假设。 其中，资源的类型是指假设一台机器在任何时候只能加工一个工件，同时还假设 一个工件在任何的时候至多在台机器上加工；确定性是假设排序问题的所有参 数都是事先知道的和确定的；可运算性主要是假设在可以运算和可以计算的程度 上研究排序，而不是顾及如何确定工作的交货期等等可能发生的问题；单目标和 正则性主要是假设排序的目的是使衡量排法好坏的一个一维目标函数的函数值 为最小，而且这个目标函数是工件完工时间的非降函数。然而在现实生活中，排 序问题的出现不像经典排序假设的那样严格，成组分批排序、在线排序、随机排 序、人员排序和智能排序等等就是对以上四种假设的突破。 随着服务业的迅速发展、服务理念的变化和顾客的个性化的需求越来越多， 服务预定系统将会在服务业的发展当中起着重要的作用。方面，因为良好的服 务预定系统对企业的发展有利。良好的预定系统会使得企业提前对顾客的需求做 出准确的预测，也可以根据顾客的需求提前做好资源配置计划，以免顾客需求的 波动造成资源的浪费；另一个方面也可以提高顾客的满意度，提高顾客的回头率， 以免由于服务资源的局限性所造成顾客的离开。 与生产系统一样，服务预定系统中也存在着工作和机器的概念，这是因为服 务预定系统中的服务资源和生产系统中的机器有着相同的特点，它可以被看作是 4 复q 大学颀j 学位 仑史 机器；而服务预定系统中顾客的需求和生产系统中的工作有着相似的特征，因此 也可以将它看作是工作。然而，服务预定系统也有着独特的特点。第一，顾客的 需求是随机产生的，它没有时间上的先后性，即可以在六点钟产生对某一个服务 资源十点钟的需求，也可以在七点钟产生对其九点钟的需求；第二，每一个顾客 的需求都会有一个最大忍耐时间( d e a d l i n e ) ，即顾客不会无限制地等待下去。而本 文所讨论的问题就是限时平行机在线排序技术( o n l i n es c h e x i u l i n g0 1 3p a r a l l e l m a c h i n e ) 在服务业中的广泛应用。 限时平行机在线排序问题是指在企业考虑的待分配资源( 机器) 的顾客需求 ( 工作) 中，每一个工作( j o b ) 都有一个最迟完工截至时自j ( d e a d l i n e ) ，由于每一 个工作都必须在最迟完工截至时间之前完成，并且为了不浪费现有的服务资源 ( 机器) ，因此，在该工作到达系统之后，系统就必须对该工作做出资源配置计划， 当现有资源无法满足该工作的需求的情况下，舍去该工作，其目的是要将资源的 利用率达到最高。举生活中一个简单的例子，就是饭店的订餐和送餐系统。当顾 客打电话到饭店订餐并要求送餐的时候，就会告知具体送到的时间。饭店则可以 根据顾客需要的紧急程度和现有的人员的繁忙程度做出调整，推迟对那些需求不 是很紧急客户的服务，同时拒绝那些在有限时问内无法满足需求的顾客。根据限 时平行机在线排序问题广泛的应用背景，本文对其中的一种问题进行了研究，提 出了近似搜索算法并进行了论证。由于这类问题非常复杂，所以，对搜索算法的 研究是本文的重点。 1 2 本文研究的问题以及背景 本文所研究的问题是由航空货运进口问题演化而来 3 1 1 ，因为当前，航空货 运码头经常会碰到货运代理需要预定装卸货物站台的需求。航空货运代理商受货 主委托到航空货运码头提货，因此代理商需要通过传真、网络和电话等多种现代 化手段事先向航空货运码头提供需要提取货物的名称、类别等货物信息以及货物 代理商们预计到达码头提货的时间。但是，由于航空码头货物装卸站台的数量有 限，码头的调度人员必须将货物装卸站台合理地分配给货物代理商们，从而保证 在有限的货物装卸站台的条件下，航空货运码头能够最大程度上地满足各种代理 商的需求。 本文所研究的问题是具有指定到达时州和最迟完工时间的平行机在线排序 问题，这个问题就是以航空货运码头分配装卸货物站台给代理的过程中的一些关 键点为实际背景的，并且进行了抽象和简化。 首先，货物代理商们事先向航空货运码头提供货物信息和取货时间的时刻具 复日人学硕 学位论文 有随机性。也就是说，这个时间不具备非递减性。举个例子来说，下午二点钟需 要到码头取货的代理可能在上午十点钟就打电话预约货物装卸的站台；而下午一 点钟需要到码头提货的代理商可能在中午十二点才会打电话预约货物装卸平台。 因此在本文研究的这个抽象问题中间，工作达到时间的随机性就可以保证航空货 运进口问题的这个特性，突破时间非递减性的限制。 其次，每一个货物代理商根据货主的需求和自己的实际情况，都会有一个最 迟取货时间。如果货运码头不能够在最迟取货时间之前安排取货，那么该货运代 理不可能在当天提货，因此它会取消当天提货的需求。为了体现航空货物码头的 这个特性，在本文研究的问题中，当工作不能够在其最迟完工时间之前加工完毕， 那么它将会被系统舍弃。 再次，在货运代理通过传真、网络和电话等多种现代化手段事先向航空货运 码头提供货物信息和取货时间以后，码头的调度人员必须综合根据当| i 的货物装 卸平台的占用情况和取货时间等信息对当前的货运代理需求做出决策，如果能够 满足代理的需求，则通知代理取货时间；如果无法满足，则拒绝代理的需求。 最后，每一个货运代理提货所需要花费的时间是不同的。但是，为了简单起 见，本文假设每一个货运代理的提货时间均相同，在本文研究的模型中，假设工 作的加工时间均为l 。并且，本文所研究的问题以系统能够接受的工作个数为目 标函数，它可以很好的体现航空货运码头能够满足各种代理商需求的程度。 在本文的第三部分将就此问题的n p h a r d 性质进行证明。因为此问题是 n p h a r d 问题所以本文的研究重点将是此问题的启发式在线算法的设计和其相 关性质的证明。 6 复且大学硕十学位论文 2 在线排序问题文献综述 排序问题是组合优化领域的一类重要问题，在生产计划调度，计算机数据处 理与存储等方面有着广泛的实际背景。近年来，从各个角度、多个方面，排序问 题被很多学者再次研究。由于很多在线排序问题本身属于n p - h a r d 问题，所以对 近似算法的研究成为了研究的主题。面对在线问题，它的基本假设有以下两条： ( 1 ) 工件的信息是逐个释放的。即新的工件的信息只有在排序者对已经到达 的工件做出安排以后才会被排序者所知； ( 2 ) 工件的加工不可改变。即一旦排序者将工件安排给某台机器加工，在其 后的任何阶段不能以任何方式予以改变。 随着近年来对排序问题研究与发展的深入，排序问题已经成为国际上的热点 研究课题，同时排序问题中的在线排序算法研究则更是成为了国内外学者关注的 对象。一般地来说，在线排序模型可以分为以下三类： 第一：古典在线模型。工件是一个接一个地到达，仅当安排好当前的工件以 后，下一个工件的信息才知道，而一旦工件被安排，则不允许改动，这种模型的 结果目前已经比较丰富。 第二：实时到达模型。工件是实时到达的，即工件的到达时间是预先未知的， 而只有工件到达以后其加工时间才变成已知。容易看出，这一类模型会更加接近 实际，可以说是真正意义上的在线问题。 第三：加工时间未知实时到达模型：工件到达以后其加工时间仍然未知，只 有当其被加工完了以后其加工时间才会被知道。这类模型主要是源于计算机数据 处理，因为当计算机在执行任务的时候，用时的长短往往无法知道。 衡量一个在线排序算法最常用的指标就是竞争度( c o m p e t i t i v e n e s s ) ，即把在线 排序算法的结果与对相同工件运用离线排序算法所得到的结果进行比较。更确切 的说就是用竞争比( c o m p e t i t i v er a t i o ) p 来衡量一个在线排序算法的性能。对于使 目标函数最小的在线排序问题，竞争比p 定义为对问题的所有的实例的比值c c o 的上确界。其中c 和c o 分别代表由这个在线排序算法得到的目标函数值和相应 的离线排序的最优值。 2 1 经典在线排序问题 在线排序问题中经典的问题就是第一类问题，即古典在线排序问题。因为这 一类型的问题是其他在线排序问题的基础，同时对古典在线模型的研究会拓宽人 们对实时到达排序和加工时间未知的实时到达排序研究的思路和方法，对人们研 复且大学硕1 ：学位论文 究后两种在线排序问题有着启发的意义，因此在这里，本文作一个略微详细的介 绍。 问题基本描述；设有n 个工作以，以，。在m 台相同的机器上加工，加 工时问分别为e ，最，b ，只。对于每一个工作以( i = l ，2 ，3 n ) 而占，只需要在m 中的任意一台机器上加工，在工作以( i = 1 ，2 ，3 ，n ) 的开始加工到它完成加工的时 间段里面是不允许中断的，并且每台机器在同一个时刻最多只能加工一个工作。 工件是一个接一个地到达，仅当安排好当前的工件以以后，下一个工件以+ 的信 息才知道。而一旦工件被安排，煲l j 不允许改动。 目标：设计一种机器加工的近似算法，使得在这m 台机器的加工时间跨度 当中，最长的时间跨度最短，即m m c 。 对于这类问题，人们进行了大量的研究，o r a h a m ( 1 9 6 9 ) t 7 提出了同型机在 线问题的l s ( l i as c h e d u l i n g ) 算法以来，该算法渐渐地成为了经典算法，后来被 研究在线问题的人们广泛的引用，或者修改以便适应新的在线问题。 下面将给出l s 算法的基本思想和步骤： 初始状态：扣1 ；n 台机器的加工时间跨度c l ，c 2 ，c 。均为0 第一步：如果i n ，则将目前需要加工的工件j ，( i = 1 ，2 ，n ) 分别放到第l 台、第2 台、第r l 台机器上加工，并且分别计算此时这i 1 台机器的加工时l 日j 跨度c l ，c ：，巳，进入算法第二步；否则，算法结束。 第二步：寻找m i ne ( a - 1 ，2 ，3 ，m ) ，用k 表示能够使得e 达到最小时的 机器序号，则k ( 1 ，2 ，3 ，m ) 且gs e ( a - l ，2 ，3 ，i n r a k ) 。如果k 的取值 不唯一，进入算法第四步：否则进入算法第三步。 第三步；将工作，放到机器k 上进行加工，i = i + l ，进入算法第一步。 第四步：分别计算那些使得k 的取值相同的机器的当前加工工件个数 n u m l ，n u m 2 ，n u m 6 ，并且k = m i n ( n u m l ，n u m 2 ，n u m 6 ) ，进入算法第三步。 根据l s 算法的基本步骤，可以很容易的证明l s 算法的竞争比p s 2 1 m ( m 代表平行机的机器个数) 1 7 1 。这种经典的l s 算法自从它诞生以来成为了在线排 序的基石，很多学者在对后两类在线排序问题的研究的同时，都会引入对l s 算 法的研究。 8 复q 大学坝l 擘位论j 由于l s 算法已经成为在线问题研究的奠基经典算法，因此本文在研究限时 平行机在线排序问题时，也会对l s 算法有所探讨，并且会对l s 算法作出修改 以便使其更好的适应新的排序问题。 2 2 平行机在线排序问题 平行机在线排序主要是指整个系统当中有很多完全相同的加工机器，它们对 同一工作的加工结果是完全一样的，即一个需要加工的工作只需要在这些完全相 同机器中的任意一台上加工即可。平行机在线排序问题在实际中有着非常广泛的 应用背景，如在很多服务性行业中所设立的柜台就是一个很好的例子。每个柜台 对顾客的服务都是无差异的，即顾客只需要到系统中的任意一个柜台前面，即可 以使得自己的需求得到满足。而顾客的到达时间事先是未知的，且每一个柜台在 同一个时间段内也只能服务一个顾客。 平行机在线排序问题中的经典问题是第一类问题，即古典在线排序问题。在 l s 算法提出二十多年以后，f a i g l e ，k e r n 和t u r a n ( 1 9 8 9 ) 1 2 证明了当m = 2 ，3 的 时候，l s 算法是最佳的在线算法。在这之后，寻找r f l 4 时的最佳在线算法或者 改进已有的结果从未停止过。而针对m 4 的在线排序问题的研究主要是从以下 两个方面进行的：第一，改进竞争比下界。f a i g l e 等人对m 4 的确定武算法进 行了研究，并得出结论，对任意的m 4 的第一类问题，它的下界为1 7 0 7 。b a r t a l 等人( 1 9 9 2 ) 4 1 对以上的下界进行了进一步推进，将其改进为1 8 3 7 。后来， a l b e r s ( 1 9 9 7 ) 【l 】又将该下界改进为1 8 5 2 。再到后来，g o r m t e y ( 2 0 0 0 ) 等人应用了 计算机搜索的方法，将a l b e r s 提出的下界1 8 5 2 改进到了1 8 5 3 5 8 ：第二，改进 近似算法，从而改进竞争比。g a l a m b o s ，w o e g i n g e r 等人( 1 9 9 3 ) 1 6 在1 9 9 3 年对 l s 算法进行改进，使得竞争比由原来的2 - l m 改进到了2 - 1 m ，其中，当n l 斗c o 时，寸o 。后来又有很多人对这一结果进行了改进。第一个将竞争比改进到2 以下的是b a r t a l 等人( 1 9 9 2 ) 研究的针对m 7 0 的这类问题，将算法改进到l 。9 8 6 。 后来，k a r g e r ( 1 9 9 7 ) 1 1 等人提出了c h a s m 算法，将该问题的竞争比改进到区间 1 9 3 7 8 ，1 9 4 5 中的某处。a l b e r s 后来提出m 2 算法，将竞争比继续改进到了 1 9 2 3 。r u d o l ff l e i s c h e r 和m i e h a e l aw a h l ( 2 0 0 0 ) 1 3 在2 0 0 0 年提出了m r 算法， 并证明在m 6 4 的时候，他们的m r 算法竞争比小于1 9 2 3 ，而当m - - 4 o o ，其 竞争比可以达到1 9 2 0 1 尽管到目前为止，对第一类问题( 古典在线模型) 的研究结果已经非常丰富， 但是这种在线模型在实际环境中很难应用。因为它的基本假设是当且仅当当前工 件被安排，下一个工件才到达，所以工件总是被立即加工，所以序中不太可能出 现机器等待的情况。而第二类模型和第三类模型是实时的，工件到达后即使机器 9 复q 人学硕f 学位论文 空闲也可以不立即加工。纵观今年来的研究成果，对于这种类型问题的研究，从 总体上可以分为三种研究类型：针对最小化加工总长时间；针对最小化完工时间 总和；针对最小化工件等待时间总和。 第一：最小化加工总长时间。h a l l 和s h m o y s 研究表明，由g r a h a m 提出来 的l s 算法在应用到该问题时，所达到的竞争比为2 ，同时s h m o y s 等人还指出 这类在线问题的下界与相应的离线问题的估计值有关，同时给出了一个下界为 1 0 9 的证明。c h e n 和v e s t j e n s ( 1 9 9 7 ) 5 在1 9 9 7 年对结果进行分析后指出对任意 的1 1 1 而言，使用l p t 算法在该问题时的能够达到的竞争比为1 5 ，他还指出对任 意的1 1 1 条件下，一般地竞争比下界为1 3 4 7 2 9 ，特别当m - - 2 时，他给出了竞争地 下界比为1 3 8 1 9 7 。陈仕平和姚恩瑜等人( 1 9 9 9 ) 将m 任意条件下的下界改进到 1 3 8 2 。而对于m - - 2 的问题，j o h nn o g a ( 1 9 9 9 ) 1 6 和s t e v e ns s e l d e n 给出了一个 竞争比为1 3 8 1 9 8 的算法，使得m 3 成为研究的重点。 第二：最小化完工时间总和。c h e k u r i ，m o t w a n i ，n a t a r a j a n 和s t e i n ( 1 9 9 4 ) 【3 2 】 根据一台机器上的可中断松弛排序提出一个在线算法，并证明了该算法的竞争比 为r 3 一l m ) 。h a l l ，s c h u l z ，s h m o y s 和w e i n 通过贪婪算法区间思想，给出了一个 竞争比为4 + r 的在线算法。如果工件的加工不允许中断，v e s o e n s 已经证明了任 何确定型在线算法的竞争比的下界至少为1 3 0 9 。特别地针对两台机器的情况下， 这个下界可以改进到1 5 0 2 。鲁习文( 2 0 0 4 ) 研究同型平行机上的在线排序问题。 通过平移工件的到达时间，提出了一类在线确定型算法s s p t 。对目标为总完工 时问的情形，证明了该算法竞争比不小于2 且不超过4 - 1 m ，对目标为加工总长的 情景，该算法的竞争比的上界为3 - l m 。如果加工工件允许中断，v e s t j e n s 证明 了任何确定型在线算法的竞争比的下界至少为1 0 4 7 。而p h i l l i p s ，s t e i n 和w e i n 证明了算法s r p t ( s h o r t e s tr e m a i n i n g p r o c e s s i n g t i m e ) 是竞争比为2 的在线算法。 第三：最小化工件等待时间总和。传统的在线平行机问题都是使用m a k e s p a n 作为目标函数的，而这种目标函数是站在机器拥有者的那一方提出的，因为他们 总是希望自己机器的使用率最高。然而如果将目标函数的设置角度替换到工作那 一方，那么他们希望工作不会在加工前等待太长的时间，所以他们的目标函数将 变成最小化工件等待时间之和为1 ) 工件加工可中断。 d k a r g e r , c s t e i n , j w e i n ( 1 9 9 7 ) 11 】，针对单一机器的情况，提出了s h o n e s t r e m a i n i n gp r o c e s s i n gt i m e 搜索算法，然而在这个s r p t 算法中存在着某些工作 会无限拖延的情况。后来，c h r i s t o p ha m b u h l ，m o n a l d om a s t r o l i l l i ( 2 0 0 5 ) 2 针对 平行机是m 个的情况进行了研究，并提出了算法使其竞争比达到2 1 m ，同时证 明该问题的竞争比下界为2 - l m ，从而证明其得到了最优搜索算法。2 ) 工件加 工不可中断。c h r i s t o p h a m b u h l ，m o n a l d om a s t r o l i l l i 针对m - - 2 的平行机情况证明 1 0 复咀人学硕j 学位论文 了f i r s ti nf i r s to u t 算法可以获得最优的竞争比。m a s t r o l i l l im 针对任何多于2 个 平行机的情况下对f i f o 算法进行了研究，最后证明到f i f o 算法针对m 平行机 的竞争比为3 2 m 。 2 3 具有最迟完工时间的平行机在线排序问题 ( ? m l p ，0 ，d jl x d - ) 有最迟完工时间( d e a d l i n e ) 的平行机在线排序问题是从实际问题中演化而 来，它主要研究的问题是：假设在一个系统中有r n 台完全相同的机器，每一个 工作，都具有一个相应的到达时间( r e l e a s et u n e ) 和最迟完工时间( d e a d l i n e ) ，只 有当工作，到达系统之后，它的到达时间( r e l e a s e t i m e ) 和最迟完工时间( d e a d l i n e ) 才是已知的，即该工作的到达时间和最迟加工时间是不可以提前预知的。系统在 工作到达的时候就必须对该工作的排序方案做出安排。不过，只要该工作被安排 好了以后就不允许再做修改，且工作的加工过程是不允许中断的。对于那些无法 在最迟完工时问之前加工的工作，系统需要在该工作到达的时候做出舍去的决 定。目标函数是要最大化在最迟完工时间以前可以完工的工作数量，学者们同时 也将这种目标函数叫做产出最大化( t h r o u g h p u tm a x i m i z a t i o n ) 。 针对这一类型的排序问题，学者们通常采用的评价标准仍然是在线问题中标 准的评价标准一竞争l l ( c o m p e t i t i v er a t i o ) 。也就是说，一个在线问题算法所得到 的目标函数值与该问题在离线情况下、在同一组工作参数条件下，所得到的目标 函数最优值之问地比例，通常会用字母p 来表示。到目前为止，针对一台机器的 最迟完工时间在线排序问题已经被广泛地研究，g o l d m a n 等入( 2 0 0 0 ) 1 3 3 1 通过研 究给出了竞争比为4 3 的随机算法，同时，他们也给出了一个确定性的算法，并 且证明这个算法的竞争比为2 。他们同时还证明了一个贪婪算法的竞争比为3 ，2 ， 只要对于所有的工作，该工作的最迟完工时间比它的到达时问至少大于等于 2 ，用公式表示为：d e a d l i n e r e l e a s e t i m e 2 ，我们称这个差值为最长等待时 白j ( s l a c k ) 。这就意味着如果工作有足够的最长等待时间，那么该问题的下届2 将 会被突破，沿着这个方向，g o l d w a s s e r 等人( 1 9 9 9 ) 【2 s 在此基础上作了进一步的 延伸。如果对所有工作而言，都满足d e a d l i n e r e l e a s e t i m e 2 五，其中五为大于 零的实数，那么该问题的竞争比即为1 + 1 1 2 。 正如前面所述，有最迟完工时间的在线排序问题是要求工件一旦加工则不再 允许中断，然而，c h r o b a k 等人( 2 0 0 4 ) 2 7 在考虑随机在线模型时放宽了对这个条 复巨大学硕i + 学位论文 件的限制。在他的研究当中，他把重点放到了一种具有单位加工时间，且工件加 工可中断的在线排序模型上。并且通过研究，他提出了一个具有5 3 竞争比的随 机算法，同时针对可中断的在线模型提出了一个竞争比为3 2 的算法，并且证明 其是最优的。 然而，到目前为止，针对机器个数超过l 的最迟完工时间( d e a d l i n e ) 平行机 在线排序问题的研究还不是很多。l e e 等人( 2 0 0 3 ) 2 1 l 研究了一类将m 台机器上 的所有接受的工作的加工时间之和作为目标函数的问题，针对m 台平行机，提 出了一个竞争比为l o g o k ) 的随机算法，其中m = l ，2 ，3 ，l 0 9 0 k ) 。针对肼2 的情况，他们也同时得到了一个竞争比为【j ，l + l + m ( 1 k ) ”“】的确定性搜索算法。 而针对m = 2 、产出最大化为目标函数的最迟完工时间平行机在线排序问题，直到 最近，g o l d w a s s e r 和p e d i g o 等人( 2 0 0 6 ) 2 9 才提出了一个在线的搜索算法，并且 证明该算法的竞争比为3 2 。 从上面的讨论，我们可以看出，几乎所有的具有最迟完工时间的平行机在线 排序问题都假设当系统要对到达的工作做出资源配置计划( 即安排机器加工) 的 时候，该工件已经到达系统了。然而，在很多实际的情况下，一个服务预定系统 就可以在工件还没有到达系统之前，对系统中的机器和加工时| b j 做出预定，也就 是说，当顾客提出预定需求的时候，系统必须对顾客的需求做出立即反应。在很 多的情况下，系统会预先以订单的形式被告知将要到达工作的到达时间( r e l e a s e t i m e ) 和加工时| 日j ( p r o c e s s i n g t i m e ) ，然后系统需要对这个订单的内容做出立即的 回复，并且安排相应加工的机器和加工时间。 这一类问题与传统的最迟完工时间的平行机在线排序问题之f 日j 的主要区别 在于：不像传统的最迟完工时间的平行机在线排序问题，工件到达的时i n ( r e l e a s e t i m e ) 是呈现非递减的顺序的，而具有订单系统的最迟完工时间平行机在线排序 问题中工作的到达时间( r e l e a s et i m e ) 是具有随机性的。它不具有非递减性的特 点。举个例子来说，4 点钟到达系统的订单中所包含的工作可能是7 点钟到达系 统，而5 点钟到达系统的订单中所包含的工作可能是6 点钟到达，即后来的工作 可能需要先加工。 我们把这一类具有订单系统新的在线排序问题称之为具有指定到达时间 ( a r b i t r a r yr e l e a s et i m e ) 和最迟完工时间( d e a d l i n e ) 的平行机在线排序问题，容易 看出，这个新的在线排序问题是传统在线排序问题的一个扩展问题，因为只要将 所有的工作的到达时间都设为零，该问题就会变成传统地具有最迟完工时自j 的平 行机在线排序问题。不过，目前国内外对这类新的排序问题的研究还很少，因此， 本文将重点放在对这类新的在线排序问题的研究上。 1 2 复且人学硕十学位论文 3 具有指定到达时间( a r b i t r a r yr e i e a s et i m e ) 和最迟完工 时间( d e a d iin e ) 的平行机在线排序问题 ( p m ps a r b i t r a r y r j ，d iq x u ) 具有指定到达时间和最迟完工时间的平行机在线排序问题是传统在线排序 问题的一个拓展问题，因为只要将所有的工作的到达时间都设为零，该问题就会 变成传统地具有最迟完工时间的平行机在线排序问题。由于这类问题是属于 n p h a r d 类问题，因此本文的研究重点会放在算法的设计和性质的研究上。众所 周知，任何一个排序问题都具有其特殊之处，如果能够跟据它的特点设计出量身 定做的算法，那么它将有效地缩短算法的运算时间和缩短与最优解之间的距离， 这就会使得算法的效率显著提高。因此，本文一共提出了三个算法。其中第一个 算法是在传统在线排序的l s 算法基础上提出来的，同时对其应用到新的在线排 序问题上的结果进行了分析。第二和第三个算法则都是根据这类新问题的特点而 提出的，同时本文也对后两个算法在新的在线排序问题上的应用结果进行了分 析。 问题描述： ( 1 ) 假设系统中共有m 台完全相同的机器，有n 个工作，( 扛1 , 2 ，3 ，珂) ，每 一个工作以( i = 1 , 2 3 ，疗) 都有一个相应的到达时间t ( f = 1 , 2 ，3 ，胛) 和最迟完工时 问z ( f 1 , 2 ，3 ，疗) ，所有的工作都具有相同的加工时间，记为单位l 。 ( 2 ) 订单到达系统的时间可以与其包含的工作到达系统的时间不一致，也就 是说订单可以与其包含的工作同时到达系统，也可以在该工作到达系统之前到 达，但是不允许订单在其包含的工作到达系统之后到达。 ( 3 ) 当某一个订单到达系统时，系统必须决定是否接受订单中所包含的工作 ，。如果接受，根据工作，的信息和机器目前的使用状况，系统必须做出在哪 个时间段，工作，由哪一台机器进行加工的安排；如果不接受，即无法在最迟完 工时间之前完成工作，那么系统必须拒绝这份订单。 ( 4 ) 假如一个到达系统的订单所包含的信息是关于工作一( i = 1 , 2 ，3 ，行) 的到 达时间和最迟完工时间d 。的，那么系统在给工作以分配机器和相应的加工时问 复口| 人学坝i 学位论史 之前是无法知道其它新工作的信息的。 ( 5 ) 当某个订单所包含的工作，在系统中安排完毕以后，是不允许对现有的 安排计划进行修改的，并且一旦工作，在某个机器上加工开始，中间是不允许中 断的。 ( 6 ) 本文中使用记号z “力表示与工作相关的所有信息，其中，i 表示工作 的序号，r 表示该工作的实际到达时间，d 表示该工作的最迟完工时间。 目标函数：最大化系统能够在最迟完工时间之前完工的工作的数量，即最大 化系统的产出值( t h r o u g h p u tm a x i m i z a t i o n ) 评价标准：标准的在线排序竞争比评价标准。设斫口盯分剐表示算法a 和 最优