| 摘要 | 第1-5页 |
| Abstract | 第5-11页 |
| 第一章 绪论 | 第11-21页 |
| §1.1 背景知识 | 第11-13页 |
| §1.2 基本概念与符号 | 第13-18页 |
| §1.3 本文的主要结果 | 第18-21页 |
| 第二章 等级约束下的负载平衡问题 | 第21-45页 |
| §2.1 引言 | 第21-24页 |
| §2.2 目标函数为min-max | 第24-31页 |
| §2.2.1 问题P|GoS_2|C_(max) | 第24-27页 |
| §2.2.2 问题P_m|GoS|C_(max) | 第27-31页 |
| §2.3 目标函数为max-min | 第31-40页 |
| §2.3.1 问题P|GoS|C_(min) | 第31-37页 |
| §2.3.2 问题P_m|GoS|C_(min) | 第37-38页 |
| §2.3.3 问题P|GoS_k|C_(min) | 第38-40页 |
| §2.4 目标函数为min-l_p | 第40-45页 |
| §2.4.1 问题P|GoS|l_p | 第40-41页 |
| §2.4.2 问题P_m|GoS|l_p | 第41-45页 |
| 第三章 带数目约束的负载平衡问题 | 第45-55页 |
| §3.1 引言 | 第45-46页 |
| §3.2 目标函数为min-max | 第46-49页 |
| §3.3 目标函数为max-min | 第49-50页 |
| §3.4 目标函数为min-l_p | 第50-55页 |
| 第四章 划分拟阵约束下的负载平衡问题 | 第55-66页 |
| §4.1 引言 | 第55页 |
| §4.2 目标函数为min-max | 第55-59页 |
| §4.2.1 k为固定常数的情形 | 第55-57页 |
| §4.2.2 m为固定常数的情形 | 第57-59页 |
| §4.3 目标函数为max-min | 第59-63页 |
| §4.3.1 一般情形 | 第59-60页 |
| §4.3.2 k为固定常数的情形 | 第60-62页 |
| §4.3.3 m为固定常数的情形 | 第62-63页 |
| §4.4 目标函数为min-l_p | 第63-66页 |
| §4.4.1 一般情形 | 第63-65页 |
| §4.4.2 m为固定常数的情形 | 第65-66页 |
| 第五章 拒绝费用受限的负载平衡问题 | 第66-78页 |
| §5.1 引言 | 第66页 |
| §5.2 目标函数为min-max | 第66-76页 |
| §5.2.1 问题P|rej≤B|C_(max) | 第67-71页 |
| §5.2.2 问题P_m|rej≤B|C_(max) | 第71-76页 |
| §5.3 目标函数为min-l_p | 第76-78页 |
| 第六章 带机器准备时间的负载平衡问题 | 第78-88页 |
| §6.1 引言 | 第78-79页 |
| §6.2 目标函数为min-max | 第79-84页 |
| §6.2.1 问题只P,r_i‖C_(max) | 第79-82页 |
| §6.2.2 问题P_m,r_i‖C_(max) | 第82-84页 |
| §6.3 目标函数为通用函数 | 第84-88页 |
| 第七章 环上的负载平衡问题 | 第88-106页 |
| §7.1 带拒绝费用的环上的负载问题 | 第88-92页 |
| §7.1.1 流量不可分的情形 | 第89-90页 |
| §7.1.2 流量可分的情形 | 第90-92页 |
| §7.2 混合环上赋权有向超图的嵌入问题 | 第92-96页 |
| §7.2.1 基于线性规划的2-近似算法 | 第93-95页 |
| §7.2.2 强多项式时间近似算法 | 第95-96页 |
| §7.3 赋权环上有向超图的嵌入问题 | 第96-106页 |
| §7.3.1 m≤c_1 ln n的情形 | 第97-99页 |
| §7.3.2 m≥c_1 ln n且c_(OPT)≥c_2m的情形 | 第99-101页 |
| §7.3.3 一般情形 | 第101-106页 |
| 第八章 推广的装箱问题 | 第106-119页 |
| §8.1 拒绝费用受限的装箱问题 | 第106-108页 |
| §8.2 凹费用装箱问题 | 第108-119页 |
| 第九章 网络中的最小费用插点问题 | 第119-127页 |
| §9.1 引言 | 第119-120页 |
| §9.2 (s,U)-插点问题 | 第120-121页 |
| §9.3 路上的插点问题 | 第121-124页 |
| §9.4 树上的插点问题 | 第124-127页 |
| 第十章 结论 | 第127-129页 |
| 参考文献 | 第129-138页 |
| 攻读博士学位期间完成的主要研究工作 | 第138-139页 |
| 致谢 | 第139-140页 |