随机需求约束下的批处理资源调度模型与算法

发布时间：2019-07-11 17:59

【摘要】：从20世纪初期开始，由于在制造业的大量应用，调度问题日益受到人们的重视。调度问题研究的是将有限的资源在一定时间内进行合理的分配，以期做到尽可能高效率的完成不同的任务。它是一个决策过程，目标是优化一个或者多个目标函数。随机批处理调度也称为在线批处理调度，是现代调度模型领域中发展较为快速的一类调度模型。调度的随机性是指工件在到达系统之前，工件的信息例如工件的到达时间、到达数目、工期、权重和后续是否还有新的工件到达等情况，事先是未知的。批处理调度是相对于传统的单个工件加工的调度问题而言，它是指把要加工的工件结成一批共同进行加工处理。由于批处理调度有利于提高企业的生产效率和节约资源，因此它受到来自运筹学，管理学和工程学等领域学者的日益重视。因为随机批处理调度模型对于大多数机器环境和目标函数来说是NP-难问题，所以基于近似思想产生的竞争比，用在线算法与离线算法的接近程度来衡量算法性能，成为研究随机批处理调度算法的有力工具，并且得到大多数学者的认可。它通常指随机调度算法目标函数值在最坏情况下，和离线算法接近程度，是二者比值的下确界。本论文利用基于启发式算法的相关规则，去处理工件在到达系统之前所有信息未知的随机批处理调度模型，最后通过竞争比和数据的仿真过程来说明算法是具有竞争性的。论文考虑的机器环境为并行机，工件随机到达的随机批处理调度模型。论文的具体工作如下所示： (1)介绍了不同的调度模型和竞争比的相关知识,批处理调度模型的主要研究方法和相关模型的研究现状。 (2)针对并行机，目标函数为最小化总的权重完工时间和最小化总的权重延迟的随机批处理调度模型，提出了竞争比小于1+α的算法。其中α=β_m通过(1+β_m)~(m+1）=β_m+2求得，m为机器的数量。 (3)最后通过概率相关知识，研究了m=2的并行机且有两个不同的作业族的模型，目标函数为最小化最大完工时间，得到了竞争比小于1+α的算法。 (4)利用泊松过程模拟工件的随机到达，对具体的算法利用仿真数据进行了验证。
文内图片：随机批处理调度模型示意图

图片说明：这类模型研究的比较少。本文采用传统的随机调度的角度去建立模型进行相关研究和讨论。2.3.1 模型背景在物流系统中批处理调度经常出现在，当用户的订单为同一个地方的时候企业不可能对于收到的每个订单立即进行投递，而是要等到相同目的地的用户订单达到一定条件的时候才考虑投递。每次批处理的货物太少企业的成本太高但是若投递的时间过长（即批处理的形成时间过长），用户体验就会不佳，同时利于企业的长久发展。本文在批处理调度的时候从企业利润和用户体验两个角去考虑。文中的随机性主要是指用户的订单的中货物的数量，订单到达时间，望的货物到达时间（工期或者交货期），订单的权重等信息，，在用户订单到达之这些信息都未知。模型示意图如下所示：
文内图片：批处理能力无限算法流程医

图片说明： 29图 3-2 批处理能力无限算法流程图3.3.3 算法仿真3.3.3.1 仿真数据对于随机到达的工件我们使用泊松过程对它的每个工件序列的到达时间和到达工件个数进行仿真，每个工件序列的权重使用一个随机函数进行仿真。仿真过程如下：假设工件的到达服从 =2 的泊松过程，并行机的批处理能力无限，即B ，机器的数量为 3 台，每批工件的加工时间为 3.0 秒。由于仿真过程中涉及的参数较多，我们将它们的标记在表 3-1 中进行统一说明，仿真数据结果在表 3-2 中。
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186

【参考文献】