Algorithms for Scheduling and Load Balancing

近年来，并行和分布式系统的爆炸性增长给调度理论领域带来了新的重要性。为了使这项技术发挥其提供巨大计算能力的潜力，了解如何在并行或分布式系统的资源上最佳地调度计算组件，从而实现对这些资源的最有效利用是至关重要的。在这项研究中，将为一组机器调度的基本问题设计算法。虽然这项工作的动机是将这些问题应用于并行和分布式计算，但其中许多问题在运筹学中也具有重要意义。重点讨论了调度多台机器的两个基本模型：车间模型和平行机模型，在车间模型中，每个作业有多个作业，每个作业都必须由特定的机器处理；在并行机器模型中，每个作业有一个可以由任何机器处理的作业。这些问题中的大多数都是NP难的，关于它们在多项式时间内能被很好地逼近，还有很多需要理解的地方。此外，将在更全面地捕捉现实的并行和分布式调度问题的调度模型上进行工作。传统模型在很大程度上忽略了任何底层的并行和分布式网络；它们还经常假设问题的完整说明是在开始构建时间表之前给出的。将研究特定网络和体系结构上的调度和负载平衡问题，以及传统和更现实的调度模型的在线算法。

The recent explosive growth in parallel and distributed systems has brought new importance to the field of scheduling theory. In order for this technology to fulfill its potential of providing tremendous computing power, it is crucial to understand how to best schedule the components of a computation on the resources of the parallel or distributed system, so that the most efficient use possible of these resources is achieved. In this research algorithms will be designed for the basic problems of scheduling a set of machines. Although this work is motivated by the application of these problems to parallel and distributed computing, many of the problems are of great importance in operations research as well. The focus is on two fundamental models of scheduling more than one machine: the shop model, in which each job has a number of operations, each of which must be processed by a particular machine, and the parallel machine model, in which each job has one operation which can be processed by any of the machines. Most of these problems are NP-hard, and much remains to be understood about how well they can be approximated in polynomial time. Further, work will be done on scheduling models that more completely capture realistic parallel and distributed scheduling questions. Traditional models have largely ignored any underlying parallel and distributed network; they have also most often assumed that the entire specification of a problem is given in advance of the beginning of the construction of a schedule. Problems of scheduling and load balancing on specific networks and architectures and on-line algorithms for both the traditional and more realistic scheduling models will be studied.