| 中文部分 | 第1-88页 |
| 中文摘要 | 第6-10页 |
| 英文摘要 | 第10-16页 |
| 符号说明 | 第16-17页 |
| 第一章 绪论 | 第17-23页 |
| §1.1 研究的缘起与背景 | 第17-19页 |
| §1.2 算法的若干基础概念 | 第19-20页 |
| §1.3 论文概要 | 第20-23页 |
| 第二章 极小化加权完工时间和的批机器并行调度 | 第23-34页 |
| §2.1 引言 | 第23-24页 |
| §2.2 预备知识 | 第24-25页 |
| §2.3 小工件 | 第25-27页 |
| §2.4 一般问题 | 第27-33页 |
| §2.4.1 动态规划框架 | 第27-28页 |
| §2.4.2 工件子集的压缩表示 | 第28-31页 |
| §2.4.3 在一个块中调度工件 | 第31-33页 |
| §2.5 结语 | 第33-34页 |
| 第三章 极小化加权完工时间和的无界批机器并行调度 | 第34-40页 |
| §3.1 引言 | 第34-35页 |
| §3.2 预备知识 | 第35-36页 |
| §3.3 动态规划 | 第36-37页 |
| §3.4 工件子集的压缩表示 | 第37-38页 |
| §3.5 在一个块中调度工件 | 第38-39页 |
| §3.6 结语 | 第39-40页 |
| 第四章 极小化最大延迟的批机器并行调度 | 第40-50页 |
| §4.1 引言 | 第40-41页 |
| §4.2 预备知识 | 第41-43页 |
| §4.3 小工件分批 | 第43-46页 |
| §4.4 调度工件 | 第46-49页 |
| §4.5 结语 | 第49-50页 |
| 第五章 工件具有尺寸的极小化最大完工时间的单机批调度 | 第50-60页 |
| §5.1 引言 | 第50-51页 |
| §5.2 预备知识 | 第51页 |
| §5.3 SBPP问题的多项式时间近似方案 | 第51-58页 |
| §5.3.1 简化输入 | 第52-53页 |
| §5.3.2 短工件 | 第53-55页 |
| §5.3.3 一般情形 | 第55-58页 |
| §5.4 问题BPP的一个(2+ε)-近似算法 | 第58-60页 |
| 第六章 环网络中的呼叫接纳控制 | 第60-67页 |
| §6.1 引言 | 第60页 |
| §6.2 预备知识 | 第60-62页 |
| §6.3 无向环网络 | 第62-65页 |
| §6.4 有向环网络 | 第65页 |
| §6.5 结语 | 第65-67页 |
| 第七章 多纤波分复用链网与环网中的利润极大化问题 | 第67-74页 |
| §7.1 引言 | 第67-68页 |
| §7.2 多纤链网 | 第68-71页 |
| §7.3 多纤环网 | 第71页 |
| §7.4 均匀多纤环网 | 第71-73页 |
| §7.5 结语 | 第73-74页 |
| 第八章 圈中t-区间的k-染色问题 | 第74-78页 |
| §8.1 引言 | 第74-75页 |
| §8.2 预备知识 | 第75页 |
| §8.3 KCTIC的一个3.042-近似算法 | 第75-78页 |
| 参考文献 | 第78-84页 |
| 致谢 | 第84-85页 |
| 作者简介 | 第85-87页 |
| 学位论文评阅及答辩情况表 | 第87-88页 |
| 英文部分 | 第88-195页 |
| Chinese Abstract | 第96-100页 |
| English Abstract | 第100-106页 |
| Notation Index | 第106-107页 |
| Chapter 1. Introduction | 第107-115页 |
| ·Motivation and background | 第107-110页 |
| ·Some key concepts of algorithms | 第110-112页 |
| ·Thesis outline | 第112-115页 |
| Chapter 2. Minimizing Total Weighted Completion Time on Identical Parallel Batch Machines | 第115-129页 |
| ·Introduction | 第115-117页 |
| ·Preliminaries | 第117-118页 |
| ·Small jobs | 第118-121页 |
| ·The general problem | 第121-128页 |
| ·A dynamic programming framework | 第121-122页 |
| ·Compact representation of job subsets | 第122-125页 |
| ·Scheduling jobs within a block | 第125-128页 |
| ·Conclusion | 第128-129页 |
| Chapter 3. Minimizing Total Weighted Completion Time on Parallel Unbounded Batch Machines | 第129-137页 |
| ·Introduction | 第129-130页 |
| ·Preliminaries | 第130-132页 |
| ·Dynamic programming | 第132-133页 |
| ·Compact representation of job subsets | 第133-134页 |
| ·Scheduling jobs within a block | 第134-136页 |
| ·Conclusion | 第136-137页 |
| Chapter 4. Minimizing Maximum Lateness on Identical Parallel Batch Machines | 第137-149页 |
| ·Introduction | 第137-139页 |
| ·Preliminaries | 第139-141页 |
| ·Batching the Small Jobs | 第141-145页 |
| ·Scheduling the Jobs | 第145-148页 |
| ·Concluding remarks | 第148-149页 |
| Chapter 5. Minimizing Makespan on a Single Batch Machine with Job Sizes | 第149-162页 |
| ·Introduction | 第149-151页 |
| ·Preliminaries | 第151页 |
| ·A PTAS for problem SBPP | 第151-159页 |
| ·Simplifying the input | 第152-153页 |
| ·Short jobs | 第153-155页 |
| ·General case | 第155-159页 |
| ·A (2 + ε)-approximation algorithm for BPP | 第159-162页 |
| Chapter 6. Call Admission Control in Ring Networks | 第162-171页 |
| ·Introduction | 第162-163页 |
| ·Preliminaries | 第163-164页 |
| ·Undirected ring networks | 第164-168页 |
| ·Directed ring networks | 第168-169页 |
| ·Concluding remarks | 第169-171页 |
| Chapter 7. Maximizing Profits in Multifiber WDM Chain and Ring Networks | 第171-180页 |
| ·Introduction | 第171-173页 |
| ·Multifiber chains | 第173-176页 |
| ·Multifiber rings | 第176-177页 |
| ·Uniform multifiber rings | 第177-179页 |
| ·Concluding remarks | 第179-180页 |
| Chapter 8. On the k-Coloring of t-Intervals in a Cycle | 第180-185页 |
| ·Introduction | 第180-181页 |
| ·Preliminaries | 第181-182页 |
| ·A 3.042-approximation algorithm for KCTIC | 第182-185页 |
| Bibliography | 第185-191页 |
| Acknowledgements | 第191-193页 |
| Curriculum Vitae | 第193-195页 |
| 学位论文评阅及答辩情况表 | 第195页 |
