Off-Line and On-Line Techniques for Scheduling and Resource Allocation

该项目的重点是为调度和资源分配的理论和实践中的各种问题开发算法。 该项目的重点是：（i）为组合调度理论中的问题开发改进的近似算法;（ii）为资源分配开发在线算法;以及（iii）实现和测试这些算法。 特别是，该项目的第一个目标是开发一般技术的NP-难调度问题的近似算法的设计。 这些技术是基于几类整数规划公式，他们已经被应用到产量近似算法的平均加权完成时间的一些约束调度问题。 这方面的第二个目标是从最坏情况分析的角度更好地理解这些通用技术的优势。 第三个目标是研究多目标调度问题的近似算法。 第四个目标是研究在线调度和资源分配问题，最初集中在算法，提供良好的平均服务的工作流，不同类型和优先级，随着时间的推移到达。 这项研究的成果预计将是：（a）对一些模型和最优性标准有更好的理论理解，（B）工作站网络和现代并行计算机（如IBM SP2）的算法。

This project focuses on developing algorithms for a variety of problems in the theory and practice of scheduling and resource allocation. The project concentrates on: (i) developing improved approximation algorithms for problems in combinatorial scheduling theory; (ii) developing on-line algorithms for resource allocation; and (iii) implementing and testing these algorithms. In particular, the first goal of the project is to develop general techniques for the design of approximation algorithms for NP-hard scheduling problems. These techniques are based on several classes of integer programming formulations, and they have already been applied to yield approximation algorithms for average weighted completion time for a number of constrained scheduling problems. The second goal in this area is to better understand, from the prospective of worst-case analysis, the strengths of these general techniques. The third goal is to investigate approximation algorithms for multi-criteria scheduling problems. The fourth goal is to study on-line scheduling and resource allocation questions, focusing initially on algorithms that provide good average service to a stream of jobs, of different types and priorities, that arrive over time. The outcome of this study is expected to be: (a) a better theoretical understanding of a number of models and optimality criteria and (b) algorithms for a network of workstations and modern parallel computers (such as the IBM SP2).***