论文部分内容阅读
排序是一类重要的组合优化问题，它广泛应用于管理科学、计算机科学和工程技术等众多领域。本文主要研究两类排序问题：第一类是带服务等级约束的两台同类机在线排序问题，目标是极小化总完工时间(∑nj=1Cj)。第二类是MapReduce流水作业调度问题的算法研究，目标是极小化最大完工时间(Cmax)。 全文共分四章。 第一章简要的介绍排序的基本理论以及MapReduce的相关知识。 第二章主要研究带两个服务等级的两台同类机在线排序，目标是极小化总完工时间。加工的工件均是单位长度且具有服务等级。等级低的工件只能在第一台机器上加工，等级高的工件可在两台机器中任意一台加工。本章分两种情形讨论。情形一：第一台机器速度为1，第二台速度为s(s≥1)，我们给出问题的常数下界至少为20/√41+9≈1.299，并给出最优常数界算法；情形二：第一台机器速度为s(s≥1)，第二台速度为1，我们也同样的给出问题的常数下界至少为√33.3/2≈1.372和最优常数界算法。最后，我们对问题的后续研究做出一些讨论。 第三章主要研究两阶段流水作业(flow shop)环境下的MapReduce调度问题，目标是极小化最大完工时间。MapReduce加工主要包括Map和Reduce两阶段。相应的，每个工件有Map和Reduce两道加工工序，每道工序有一个任务集，记为Map任务集和Reduce任务集。且只有该工件的Map任务集中任务加工完成后才能进行Reduce任务的加工。第一阶段为m1台平行机，第二阶段为m2台平行机。在Reduce任务均不可中断的情况下，我们根据Map任务是否可任意分割分为两种情况来研究。若Map任务不可中断，我们给出最坏情况界的近似算法H1，其中m=max{m1,m2}；若Map任务可以任意分割，我们主要讨论p(Rj)=βp(Mj)(0<β<+∞)的特殊情况，给出近似算法H2并证明其最坏情况界不大于；最后，我们对问题的后续研究做出一些讨论。 第四章总结全文并提出相关问题进一步的研究方向。