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).***
