一类排序问题的近似算法

1、，类排序问题的近似算法排序是一类重要的组合最优化问题， 广泛应用于管理科学，计算机科学和工 程技术等很多领域。本文主要研究任务具有不同准备时间， 加工过程不能被中断的单机排序问题1h|4M工，这是一类最大延误问题，与任务的工期有关，本文通过利用分枝定界法对问题给出了算法。第一章我们简要介绍了排序问题的三参表示法和分类，以及我们所要重点研 究的单击排序问题中的最大延误问题。第二章对没有准备时间的最大延误问题 1,皿6给出EDD法则，然后研究有 不同准备时间，加工过程可以中断的 1|片印丁居司工沏小问题，根据EDD规则给出最优多项式算法。最后，我们在前两种问题的基础上提出出问题（2.3）的一种近似

2、算法一一分枝定界法，。第三章我们对问题（2.3）的分枝定界算法进行算法设计，并对其证明得到 最优排序，举例实现。排序问题产生的背景主要是机械制造，后来被广泛应用于计算机系统，运 输调度，生产管理等领域。从普通的生产部门计划安排，人员调度，学校课程表 的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法。本文 讨论的问题是没有准备时间的最大延误问题 1|Le= （2.1）,有不同准备时间，加 工过程可以中断的1rpprepLmx （2.2）问题，并且重点研究了任务具有不同准 备时间、加工不允许中丽的单机排序问题：1想（2.3）。问题（2.3）是强NP-难的，本文给出了证明，并且经常用

3、分枝定界法来求 解。而目前对于问题（2.3）给出的分枝定界法比较模糊，因此本文对分枝定界 算法进行重新设计并且在具体分枝时采取了一些重要的策略，即将深探法和每层选取下界最小的节点进行分枝相结合，这样作的好处在于可以迅速产生较好的可 行排序，从而更快地除去无用的分枝，以这样可以较快地得到最优排序，并且对本文给出的分枝定界法得到的序列为最优排序进行了证明。并给出例子进行运 算，得到最优序列。第一章绪论1.1 排序问题简介1.1.1 研究背景及意义排序论是组合优化中的一个分支，有着广阔的应用前景。深入来看，排 序论对提高效率、资源的合理配置、工程进展统筹安排以及经济运行等方面都起 到了辅助决策的作用

4、，所以管理层和决策层必须了解排序问题的的理论和应用。 我们可以把排序理解为两种涵义。 狭义的涵义是安排次序；广义的涵义是安排时 间表，所以排序论也称为时间表理论。在排序论中，被加工的对象是工件，或者 说是要完成的任务；机器是提供加工的对象，是完成的任务的作业资源；安排时间表是在一定的约束条件下对工件和机器进行分配和安排次序，使某一个或某几个目标达到最优，排序是安排时间表的简称。用一台或者一台以上的机器加工两 个或两个以上的任务时，确定加工顺序使效率最高即为排序问题， 而由于效率度 量方式不同，引进了不同的约束条件，得到了不少的排序模型，因此也有了更多的应用。随着应用范围的不断扩大，新问题的出现

5、，研究的人越来越多，内容越 来越丰富，应用也越来越广。例如，在机械加工，进程调度，机场调度等方面。 下面阐述了排序问题在科学管理方面，运筹学领域以及计算机科学领域的应用历首先，在管理科学方面。早在二十世纪初，第二次工业革命期间，Taylor、Gilbreths和Gant就发表了这方面许多研究成果，他们的目标是要进行有效的科 学管理，提高劳动生产率。基于此，Taylor被冠为“管理科学之父”。他们开创 的那些理论，当代被列为管理科学的范畴。当然这些理论无疑为我们学习排序论 奠定了坚实的基础，所以我们甚至可以认为排序论是管理科学的一个分支。其次，排序应用在运筹学领域。运筹学作为一门现代科学，是在第

6、二次世界 大战期间首先在英美两国发展起来的，有的学者把运筹学描述为就组织系统的各 种经营作出决策的科学手段。 P.M.Mors与G.E.Kimball在他们的奠基作中给运 筹学下的定义是：“运筹学是在实行管理的领域，运用数学方法， 对需要进行管 理的问题统筹规划，作出决策的一门应用科学。”运筹学的另一位创始人定义运 筹学是：“管理系统的人为了获得关于系统运行的最优解而必须使用的一种科学方法。”它使用许多数学工具（包括概率统计、数理分析、线性代数等）和逻辑 判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题，以期发挥最 大效益。在50年代，英美国家陆续创刊了许多运筹学方面的杂志。这也说明

7、了 作为运筹学子科学的排序论当时是在军事问题的刺激下产生和发展起来的。最后，排序论在计算机科学领域也有着非常重要的角色。在二十世纪的50年代，计算机在公共事业和经济领域扮演着重要的角色。人们不仅需要计算机解决实际中的排序问题，而且计算机网络本身又产生了新的排序问题，即如何管理计算机的问题。相比之下，出现在管理科学和运筹学中的排序问题我们一般称之 为“工程序列问题”，不过机器排序问题和工程排序问题之间并无明显的界线。 另外，排序论在近些年开始大量应用到了金融领域，如Gupta等人利用该理论解 决了多贷款偿还问题。该金融问题可以归纳为以下排序模型：目标为极小化完工时间，工件加工时间随开工时间延后指

8、数增长。我们把要偿还的贷款看做待加工的工件，机器的加工能力由我们目前的资金情况决定。1.1.2 排序问题的定义排序问题是一类重要的组合最优化问题， 它是利用一些处理机，机器或资源 最优的完成一批给定的任务(tesk)或作业(job),在执行这些任务或作业时需 要满足某些限制条件。如任务的到达时间，完工限定时问，任务的加工顺序，资 源对加工时间的影响等。最优的完成是指使目标函数达到最小， 而目标函数通常 是对加工时间的长短、处理机的利用率的表述。给定n个任务的任务集?2。. 53M个处理机的处理机集二=1/二S种资源的资源集F厂-皿/排序问题指的是在一定条件下，为了完成各项任务，把 p中的处理机

9、和乳中 的资源分配给？坤的任务，使目标函数达到最优。其中：处理机：只有一个处理机的排序问题成为单机排序，否则成为多机排序问题。任务和作业：排序问题中的约束条件主要指的是任务或者作业的性质，以及他们在加工过程中的要求和限制，下面描述了一些任务的性质。(1)加工时间向量'' =( 1 ' )其中“是任务£在处理机R的加工时间(2)到达时而到达时间叮是任务Tj已经准备好可以被加工的时间(3)工所和截止血艮工期表示任务工的限定完工时间，如果不按期完工要受到一定的惩罚，绝对不允许延误的工期称为截止期限1.1.3 排序问题的分类以及三元组表示在排序问题中，如果所有的数据在

10、进行决策前都是已知的， 排序问题称为确 定性排序问题，如果有的数据例如加工时间， 准备时间和工期，在决策前是未知 的，他们是一些随机变量，但他们的分布式已知的，这样的排序问题称为随机排 序问题，无论是确定性排序还是随机排序我们都假定：(1)任务或作业和处理机都是有限的(2)在任一时刻，任何处理机只能加工一个任务或一道工序(3)极小化单一目标函数处理机，作业或任务，目标函数三要素组成了排序问题，处理机的类型，数 量和环境有数十多种情况，任务和资源的约束条件更是错综复杂， 再加上度量不 同指标的目标函数，形成了种类繁多的排序类型，我们用Graham等人首先提出来的三元组来描述排序问题的类型，这样大

11、大简化了排序问题的表示三元组记号由三个域组成：口 101r(下面只提到本文中用到的不同的域中的值)其中艮域表示处理机的数量类型环境，他们可以使：1:单处理机j：m个同速机B域表示任务的性质加工要求和限制，资源的种类和数量以及对加工的影响5:任务有不同的到达时间，如果0中不出现与，表示万=0, j=1 , 2,n prmp:加工时可中断，如果R域中没有出现，表示加工时不可中断y域表示被优化的目标函数?大延误1.2 单机排序问题中的最大延误问题单机排序问题是最简单的一类排序问题，同时也是最重要的排序问题之一， 首先单机排序问题容易解出排序方案，这些方法对于研究比较复杂的排序问题具 有指导作用，可以

12、为处理复杂排序问题提供近似算法，其次单机排序问题大量存在于现实生活中，有广泛的实际背景，许多实际问题都可以理解为单机排序问题。 因此单机排序问题对于有效利用资源，提高生产效率具有十分重要的指导意义。 本文对单机排序问题中的最大延误问题进行讨论，下面给出最大延误问题的定 义。最大延误问题定义：=max=vnax 其中l二g一4，是任务匕的延误时间。1.3 去文主要结论第二章主要就单机排序问题中的三类问题：1|八3问题，l|rpr叩|401fl工问 题，1工问题分别给出了算法。(1) M于没有准备时间的最大延误问题 1出E=，按最早工期优先(EDD)给出 最优排序。(2)对于任务具有不同准备时间，

13、任务加工允许中断的1|9詈7"£9,2*问题，利 用最优多项式算法可以得到最优排序。(3)对于任务具有不同准备时间，任务加工不允许中断的1叮Vms问题，利用分支定界法可以得到最优序列。第三章对1匕|%皿问题的分支定界法进行算法设计，并对 2.3.2的例子进行 运算，得到最优序列。第二章最大延误问题2.1 1| 问题EDD规则：将任务按最早工期优先的规则排序任务没有准备时间的最大延误问题1U(2.1)按EDD规则就可以得到最优排序，按照这一规则，任务按 由不减的顺序进行排 列。定理1:对于问题(2.1), EDD规则可以得到最优排序。卜面证明任何不满足EDD规则的排序，都可以

14、转化为满足EDD规则的排序, 且目标函数不变。假设某最优排序n违反了 EDD规则，则在此排序中，至少有两个相邻任务石和几， 弓.排在我之前，且d广九。设与在时间t时开始加工，则句"t+外dj , L1c =t+巧+B&-U。将7T做变动如 下：对调弓和取的位置，其他位置不变，从而得到另外一个排序 炉 在胃中，町的 加工时间是t,笃紧随其后。因此，八'工+川石* , 工中安电d，因为a>4, 所以L/匕J,因此、皿之九皿/,这说明任何不满足 EDD规则的排序都可以转化为满足EDD的排序，而目标函数不变，定理得证。例2.1:考虑排序问题1| L”,其中n=6,p二(

15、3,1,4,1,3,2)d=(2,10,6,4,11,12)由EDD规则可以求得最优序列为巧,7,乙，4 R、TJ,最大延误Lffliur = 22.2 1后,"印问题对于任务具有不同准备时间，任务加工允许中断的排序问题1匕亚叩工(2.2)最优多项式算法可以得到最优排序0最优多项式算法：(1)在当前到达的任务中，选择工期最小者加工(若有多个，任选其一)(2)每当加工完某任务或者有新任务到达，则转(1),重新确定当前加工任务， 直到加工完全部任务。例2.2:考虑问题1匕：prMju 其中n=4p=(4, 2, 6, 5)r=(0, 1, 3, 5)d=(8, 12, 11, 10)求其

16、最优排序和最大延误。t=0 时，3到达，从t=0时开始加工1t=1 时，鸟到达，因为%所以继续加工7t=3 时，与到达，因为刈 = min1%, d如盛所以继续加工心t=4 时，A加工完毕，心，心到达，因为豆之=所以从t=4时开始 加工.t=5 时，到达，因为&所以从t=5时开始加工门t=10 时，口加工完毕，心，踽到达，因为% = min心，3所以从t=10时继 续加工一t=15 时，4加工完毕，从t=15时开始加工7t=17 时，心加工完毕。最优排序如图所示，最大延误一 二TttT H。4 51015 17 f图2.1 :例2.2的最优排序2.3 1归/初招问题2.3.1 问题是强

17、NP-hard的任务有不同的准备时间，任务加工不允许中断的排序问题1 r J _ 一.(2.3)定理2:问题（2.3）是NP-hard的为了证明定理的结论，只能将三划分问题归结为问题（ 2.3）即可。给定整 数%,叫，, b,使b/4 <dj< b/2,且号可以如下建立问题（2.3） 的一个例子，任务数n=4t-1,又马=油+。-1） , p； = 1,弓= jb +人 /=1，2S 马=0,巳二勺一“1, % =出 十 一 1） , j = G 4t 1令守=0,使0的排序当且仅当每个任务 7；.可以在万和& =0+马之间加工，也就是剩余任务可以安排在长度为 b的七个区间

18、，即三划 分问题有解，定理证毕。2.3.2分支定界法对于有n个任务的排序问题，一个完全的搜索树共有n层节点，第0层节点 为根节点，从根节点分支产生第一层共有n个节点，每个节点对应一个第一个位 置已经排好的部分序列，从第一层的一个节点可以分支产生第二层的n-1个节点，每个节点对应一个前两个位置已经排好的部分排序，从r-1层的一个节点分支可以产生第r层n-r+1个节点，每个节点对应一个前r层已经排好的部分排序，确 定各节点二等下界，由第n-1层的一个节点可以确定一个可行排序，其目标函数 值作为最优排序目标函数值的一个上界,如果节点下界不小于当前上界,则杀死该节点，如果节点的下界小于当前上界，则对该

19、节点进行分支，不断改变当前最优目标函数值的上界，最后得到最优排序。在分支过程中，并不是每个节点都可以分支，如果 k-1层上某个节点，对应任务4,.7Tt已经排在前面k-1个位置，这时只有满足下式的任务 小才 可以产生第k层节点入 < 然t，rj + pj其中是尚未排序的任务集，t是几T的完工时间。定界方法也有好多种，根据可中断问题（2.2）的EDD规则确定各节点的下 界。图2.2分支定界法搜索树第三章 对问题（2.3 ）的分支定界法算法设计3.1分枝定界法算法设计（1）令耳工=+8,将问题（2.3）分成n个子问题跳就，/ 将其中适合 条件守叁写加匕的分枝号杀死，然后用可中断EDD规则计算

20、没 有被杀死的节点的下界。（2）若第k层已有节点，而第k+1层还无节点，在第k层取一下界最小者若有多个左侧优先）进行分枝生成k+1层n-k个节点柱）烈”,将适合条 件%”之向口小七拉.力血工缶%十41）的子问题杀死，其中t加值的完成 时间，然后用可中断EDD规则计算未被杀死的节点的下界。（3） 一但生成n-1层节点，则得二可行排序 距p叫计算它们的目标函数值 4取，令七为其中最小者，对目标函数值大于七的排序对应的节点杀 死，若目标函数值相等则杀死其中一个排序对应的节点。（4）在层数41的活点中选一层数最高且下界最小的节点启F若有多个左侧 优先），设它位于 s层将其分成n-s个子问题内洋；,冏r

21、 ,将适合条件 皂min3用X”.%1Km风£.啕+%的节点杀死，用可中断EDD规则网 计算未被杀死的节点的下界，杀死其中下界 之一的节点，在余下的节点中选 rriLu rh取一下界最小者作为 标重复过程4,直到下列条件之一成立结束：i）若下的直接后继都被杀死，重复4。ii）产生n-1层节点，得二可行排序/t山叫工工，分别计算两个可行排序的 目标函数值，若都兰七将二排序对应的节点都杀死，否则若二排序目标函数值 不等，令二;；=二排序的最小的目标函数值，而将它俩中目标函数值大的排序对 应的节点及前面的n-1层节点都杀死，若它俩目标函数值相等则将其中之一对应 的节点及前面的n-1层节点都

22、杀死，重复4。（5）若除了第n-1层外其余各层均无活点，则第n-1层节点对应的排序即为 最优排序。定理3:对问题1,j|£z利用上述算法可得最优排序.证明：设算法得到的最优排序为。/。由分枝方法知搜索树的所有树叶的 可行排序集构成问题（2.3）的可行排序集的一个划分，因此若设冗为问题（2.3）的任 一可行排序，则必有且仅有一个叶子设为子问题1以它为可行排序，而汴近对应第n层那个唯一的叶子，所以它的目标函数值设为 乙=上述算法中最后一个上 界，又由上述算法知对子问题1它只可能有两个原因成为树叶，一个是它的下界 当时的最好上界，另一原因是有一子问题优于它，若是前者，由上述算法知随 着分枝过程的深入L'的上界越来越小，所以此时冗的目标函数值L"子问题1 的最优目标函数值之七?"若是后者则在问题1下面某层有一叶子设为子问 题2的最优目标函数值因