带等级平行机调度和MapReduce调度问题的算法研究

发布时间：2018-06-03 17:11

  本文选题：在线排序 + 竞争比　； 参考：《浙江理工大学》2016年硕士论文

【摘要】：排序是一类重要的组合优化问题,它广泛应用于管理科学、计算机科学和工程技术等众多领域。本文主要研究两类排序问题：第一类是带服务等级约束的两台同类机在线排序问题,目标是极小化总完工时间(∑j=1n Cj)。第二类是MapReduce流水作业调度问题的算法研究,目标是极小化最大完工时间(Cmax)。全文共分四章。第一章简要的介绍排序的基本理论以及MapReduce的相关知识。第二章主要研究带两个服务等级的两台同类机在线排序,目标是极小化总完工时间。加工的工件均是单位长度且具有服务等级。等级低的工件只能在第一台机器上加工,等级高的工件可在两台机器中任意一台加工。本章分两种情形讨论。情形一：第一台机器速度为1,第二台速度为s(s≥1),我们给出问题的常数下界至少为20(?)41+9≈1.299,并给出最优常数界算法；情形二：第一台机器速度为s(s≥1),第二台速度为1,我们也同样的给出问题的常数下界至少为(?)≈1.372和最优常数界算法。最后,我们对问题的后续研究做出一些讨论。第三章主要研究两阶段流水作业(flow shop)环境下的MapReduce调度问题,目标是极小化最大完工时间。MapReduce加工主要包括Map和Reduce两阶段。相应的,每个工件有Map和Reduce两道加工工序,每道工序有一个任务集,记为Map任务集和Reduce任务集。且只有该工件的Map任务集中任务加工完成后才能进行Reduce任务的加工。第一阶段为m1台平行机,第二阶段为m2台平行机。在Reduce任务均不可中断的情况下,我们根据Map任务是否可任意分割分为两种情况来研究。若Map任务不可中断,我们给出最坏情况界为2-1/m的近似算法H1,其中m=max{m1,m2};若Map任务可以任意分割,我们主要讨论p(Rj)=βp(Mj)(0β+∞)的特殊情况,给出近似算法H2并证明其最坏情况界不大于2-1/m2-(1-m2)1/1+βm1;最后,我们对问题的后续研究做出一些讨论。第四章总结全文并提出相关问题进一步的研究方向。
[Abstract]:Sequencing is an important combinatorial optimization problem, which is widely used in many fields such as management science, computer science and engineering technology. In this paper, we mainly study two kinds of scheduling problems: the first is the on-line scheduling problem of two similar machines with service level constraints, the goal of which is to minimize the total completion time (鈭，

本文编号：1973553