近似算法在调度中的应用

摘要

本文研究的中心内容为近似算法，其具体应用是围绕网络中的调度问题展开的，这里的网络环境主要指的是网格。近年来，由于网格技术的高速发展，其上的任务调度问题也成为研究的热点。 本文所讨论的近似算法分为两种：其中大部分章节是以研究基于线性规划的近似算法为主；另介绍了LPT、MinMin、模拟退火等启发式算法。本文首先对基于线性规划近似算法的构造作了理论介绍和讲解，并在随后的内容中针对网格环境中有带宽的资源调度问题进行了专门的算法构造和讨论。然后，根据网格环境中约束条件的不同给出了如多背包问题、基于Time-indexed规划方程等不同的数学模型，并且还针对前面提到的带资源约束的任务调度问题，提出了启发式算法。最后，采用Simgrid软件包对算法进行了模拟和结果对比，并给出了核心算法代码。通过与传统算法MinMin的比较表明，模拟退火算法在调度问题中的应用效果要更好。

目录

文摘

英文文摘

声明

第1章绪论

1.1背景概述

1.2研究内容及选题意义

1.3论文组织结构

第2章基础知识介绍

2.1近似算法

2.1.1线性规划求近似解

2.1.2随机方法

2.1.3去随机(Derandomization)

2.1.4随机Rounding

2.1.5原始对偶(primal-dual)

2.2调度(Scheduling)问题

2.2.1基本概念

2.2.2调度问题的分类

2.2.3调度问题的求解

2.2.4典型调度算法

2.3本章小结

第3章网格中有带宽的资源调度问题

3.1简介

3.2预备知识

3.2.1星型拓扑结构的分配模型

3.2.2树型拓扑结构的分配模型

3.3随机算法解线性规划方程

3.4算法求解代替解线性方程

3.5本章小结

第4章网络中调度模型的应用

4.1引言

4.2调度模型在网络中的应用

4.2.1预备知识

4.2.2数学模型

4.3启发式算法的引入

4.3.1最长加工时间优先(LPT)

4.3.2 Min-min和Max-min算法

4.3.3模拟退火算法(SA)

4.4算法模拟

4.5本章小结

第5章总结与展望

参考文献

致谢

附录