2台并行机上的批在线调度.pdf

第2卷第2期 沈阳工程学院学报(自然科学版) V01．2No．2 2006年4月 Joumalof InStituteof Science) Apr．2006 Shenyang Engineering(Natural 2台并行机上的批在线调度 霍满臣1，一，陈忠菊3，唐立新1 (1．东北大学信息科学与工程学院信息与公共安全系，沈阳110004；2．沈阳工程学院基础教育部，沈阳110136； 3．辽宁公安司法干部管理学院，沈阳 110031) 摘要：针对在2台同构并行机上的批在线调度问题，将经典在线调度中工件顺次到达的列表调度，推广为批在线列表 的工件按LPlr规则调度．证明了该算法的竞争率为3／2，并给出了该算法的一个实例． 关键词：批在线调度；算法；竞争率；同构并行机；批工件列 中图分类号：TP278 文献标识码：A 批在线列表调度问题至少与声2／／c。。一样的难，故这 0 引 言 里所研究的问题是NP一难的．于是，对该问题建立了 随着信息和通讯技术的发展，如何充分利用过程 一个批在线调度启发式BLPrr一算法并给出它的竞争 计算机提供的实时信息进行生产调度在线优化已成为 率及证明．一个算法的质量是由其竞争率度量的．对批 近年调度领域的主要热点研究课题．与传统离线调度 工件列BL的算法A的竞争率定义如下． 不同，在线调度是在信息不完备情况下进行的决策，而 定义 离线调度是在被调度的工件信息完备的情况下所做的 sup{云獭l 决策．在生产实际中，由于与生产实际数据相连的调度 问题多数都属于在线调度，而离线调度方法不能用于 表示由在线算法对在m台机器上调度批列BL产生的 在线调度问题，因此，需要对在线调度问题进行专门的 研究．这里研究的是一个批在线调度问题．其描述如 优的makespan． 下．有埘台同构并行机M(i=1，2，…，优)和1个批在确定性调度中，均假设问题的实例的全部信息 是事先已知的．然而在实际中这种假设通常不实用，如 工件序列6i(j=1，2，…，孢)，这里批一个接一个地到 达．当1个批到达时，在不知道后面批任何信息的情况 放弃这一假设便导致了在线调度领域的出现…．现已 下，批中每一个工件必须立即被调度．1台机器1次只 提出了大量的在线调度算法．关于在线调度的综述由 能加工1个工件且每个工件1次只能在1台机器上加 SgallL2J给出，其中给出了大量的结论．在线算法是模拟 工，工件在加工过程中不允许中断．当该批中某个工件 现实情况，而这里的算法不充许了解输入实例的全部 被加工完且没有该批中其它工件等待加工时，下一个 信息．它是一步一步地获取信息并在仅有的部分输入 批中的工件要立即被调度．设批工件列表示为BL，且 信息的基础上，对新的要求给予反应．第一个关于在线 在一个批中工件的加工时间在该批到达时便已知．问 J在1966年 算法调度问题竞争率的证明是由Grahamb 题的目标函数是使由批在线算法所产生的调度的 给出的．他研究了一个简单的竞争率为2—1／Ⅲ的列 (Makespan)即最大完成时间最小． 表在线调度贪婪算法，其中m是同构并行机的数量， 众所周知，在2台同构并行机上的离线调度问题 但是提出的工件列仅是工件一个接一个地到达的工件 p2／／c。。。是N尸一难的，所以在m台同构并行机上的列．这里将这一单工件列改进为批工件列，提出一个