| 中文摘要 | 第1-6页 |
| 英文摘要 | 第6-10页 |
| 第一章 绪言 | 第10-23页 |
| §1.1 排序研究背景 | 第10-12页 |
| §1.2 网络路由选择研究背景 | 第12-14页 |
| §1.3 概念与符号 | 第14-19页 |
| ·排序的概念与符号 | 第14-17页 |
| ·环路由负载问题的概念与符号 | 第17-19页 |
| §1.4 衡量算法性能的主要参数 | 第19-20页 |
| §1.5 论文的篇章结构安排 | 第20-23页 |
| 第二章 相关历史结果及文献综述 | 第23-35页 |
| §2.1 在线排序 | 第23-29页 |
| §2.2 平行批排序 | 第29-32页 |
| §2.3 环状网络路由负载问题 | 第32-35页 |
| 第三章 平行批、分组工件在线算法 | 第35-44页 |
| §3.1 引言 | 第35-37页 |
| §3.2 算法竞争比的下界估计 | 第37-39页 |
| ·批容量无界的情形 | 第37-38页 |
| ·批容量有界的情形 | 第38-39页 |
| §3.3 算法 | 第39-44页 |
| 第四章 平行批、批容量无界的一个弱渐近最优在线算法 | 第44-48页 |
| §4.1 引言 | 第44-45页 |
| §4.2 主要结果和证明 | 第45-48页 |
| 第五章 平行批、具有链序约束和单位加工时间工件的在线算法 | 第48-70页 |
| §5.1 引言 | 第48-49页 |
| §5.2 算法竞争比的下界估计 | 第49-50页 |
| §5.3 算法及其性质 | 第50-52页 |
| §5.4 B_0存在的情形 | 第52-66页 |
| §5.5 B_0不存在的情形 | 第66-69页 |
| §5.6 结论 | 第69-70页 |
| 第六章 平行批、具有任意序约束和单位加工时间工件的在线算法 | 第70-76页 |
| §6.1 引言 | 第70-71页 |
| §6.2 批容量无界、优化max(ω_j)C_j或∑(ω_j)C_j | 第71-74页 |
| §6.3 批容量有界、优化G_(max) | 第74-76页 |
| 第七章 边赋权环网络路由负载问题算法 | 第76-90页 |
| §7.1 引言 | 第76-77页 |
| §7.2 问题的阐述和概念 | 第77-78页 |
| §7.3 信息请求可任意分割的赋权环负载问题 | 第78-83页 |
| §7.4 信息请求可整分割的赋权环负载问题 | 第83-86页 |
| §7.5 信息请求不可分割的赋权环负载问题的PTAS | 第86-90页 |
| 参考文献 | 第90-98页 |
| 附录:攻读博士期间完成的论文 | 第98-99页 |
| 致谢 | 第99页 |
