| 摘要 | 第1-9页 |
| Abstract | 第9-12页 |
| Acknowledgements | 第12-20页 |
| 1 Introduction | 第20-37页 |
| 1. 1 Preliminaries and notations | 第21-29页 |
| 1. 1. 1 Network topologies | 第21-23页 |
| 1. 1. 2 General scheduling models | 第23-24页 |
| 1. 1. 3 Classification of on-line fashions | 第24页 |
| 1. 1. 4 Objective functions | 第24-25页 |
| 1. 1. 5 Three-field notations | 第25-28页 |
| 1. 1. 6 Performance measure | 第28-29页 |
| 1. 2 Problems considered in this thesis | 第29-33页 |
| 1. 2. 1 Scheduling of parallel jobs | 第30-31页 |
| 1. 2. 2 Extended classical scheduling problems | 第31-33页 |
| 1. 3 Practical motivations | 第33-36页 |
| 1. 4 Outline | 第36-37页 |
| Part Ⅰ. Scheduling of parallel jobs | 第37-99页 |
| 2 History overview | 第38-49页 |
| 2. 1 Introduction | 第38-39页 |
| 2. 2 Non-preemptive scheduling on makespan objective | 第39-45页 |
| 2. 2. 1 Off-line | 第39-40页 |
| 2. 2. 2 Jobs arrive over list | 第40-41页 |
| 2. 2. 3 Jobs arrive over time | 第41-43页 |
| 2. 2. 4 Jobs arrive on dependencies | 第43-45页 |
| 2. 3 Preemptive scheduling with makespan objective | 第45-47页 |
| 2. 4 Maximizing the throughput | 第47-49页 |
| 3 On-line scheduling of parallel jobs with dependencies on 2-dimensional meshes | 第49-63页 |
| 3. 1 Introduction | 第49-51页 |
| 3. 2 Preliminaries | 第51-52页 |
| 3. 3 Lower bounds | 第52-56页 |
| 3. 4 On-line algorithms | 第56-63页 |
| 4 On-line scheduling of parallel jobs in a list on PRAMs | 第63-81页 |
| 4. 1 Introduction and preliminaries | 第63-66页 |
| 4. 2 An improved on-line algorithm | 第66-71页 |
| 4. 3 Semi on-line problems | 第71-78页 |
| 4. 3. 1 Non-increasing processing times | 第71-73页 |
| 4. 3. 2 Non-increasing job sizes | 第73-75页 |
| 4. 3. 3 Known longest processing time | 第75-78页 |
| 4. 4 Preemptive algorithm on PRAMs and lines | 第78-81页 |
| 5 Scheduling malleable parallel jobs on 2-dimensional meshes | 第81-88页 |
| 5. 1 Introduction | 第81-83页 |
| 5. 2 Preemptive schedules | 第83-84页 |
| 5. 3 Converting the preemptive schedule | 第84-86页 |
| 5. 4 Analysis of the algorithm | 第86-88页 |
| 6 Maximizing the throughput | 第88-99页 |
| 6. 1 Scheduling parallel jobs on hypercubes | 第88-94页 |
| 6. 2 Scheduling parallel jobs on two identical machines | 第94-99页 |
| 6. 2. 1 Description of the algorithm | 第95-96页 |
| 6. 2. 2 Analysis of the algorithm | 第96-99页 |
| Part Ⅱ. Scheduling of non-parallel jobs | 第99-147页 |
| 7 On-line scheduling with extendable working time | 第100-125页 |
| 7. 1 Introduction | 第100-103页 |
| 7. 2 On a small number of identical machines | 第103-112页 |
| 7. 2. 1 Lower bounds | 第103-105页 |
| 7. 2. 2 Competitive analysis of algorithm H_x | 第105-110页 |
| 7. 2. 3 A new algorithm A_α for three machines | 第110-112页 |
| 7. 3 On machines of unequal regular working times | 第112-123页 |
| 7. 3. 1 Tight bound for a list scheduling algorithm | 第113-116页 |
| 7. 3. 2 The two-and three-machine cases | 第116-121页 |
| 7. 3. 3 Without the assumption on processing times | 第121-123页 |
| 7. 4 Note on parallel jobs | 第123-125页 |
| 8 On-line scheduling with partial information | 第125-142页 |
| 8. 1 Introduction | 第125-127页 |
| 8. 2 On two-and three-identical machines cases | 第127-130页 |
| 8. 2. 1 The two-machine case | 第127-129页 |
| 8. 2. 2 The three-machine case | 第129-130页 |
| 8. 3 On two uniform machines | 第130-135页 |
| 8. 3. 1 Lower bounds | 第131-132页 |
| 8. 3. 2 Upper bounds | 第132-135页 |
| 8. 4 Maximizing the minimum completion time on two uniform machines | 第135-142页 |
| 8. 4. 1 Upper bound | 第135-137页 |
| 8. 4. 2 Lower bound | 第137-142页 |
| 9 Conclusions | 第142-147页 |
| 9. 1 Summary of our results | 第142-146页 |
| 9. 2 Open problems and future research | 第146-147页 |
| Bibliography | 第147-160页 |
| Appendix | 第160-161页 |
| A List of publications during the period of Ph. D. study | 第160-161页 |
