US-France Cooperative Research: Offline and Online Algorithms for Job Scheduling Problems

University Of California-Riverside, Riverside CA

Investigators

Abstract

0340752 Chrobak This three-year U.S.-France cooperative research project in computer science involves Marek Chrobak at the University of California, Riverside and French researchers, Philippe Baptiste at the Ecole Polytechnique and Christoph Durr at the Universite Paris Sud. Their objective is to design efficient algorithms for scheduling problems arising in real-time systems and multi-user computer systems with service quality constraints. To model such constraints, they focus on techniques for speeding-up dynamic programming algorithms for scheduling problems and on very fast algorithms that compute near-optimal schedules. The project takes advantage of complementary expertise of the U.S. and French researchers in algorithm design and analysis and computer theory. A U.S. graduate student will participate in the design, analysis, and implementation of the developed algorithms and is expected to base his doctoral dissertation on this research. Computational problems in other areas of scheduling may apply the developed algorithms. These ideas include approximation methods for solving scheduling problems, and new performance measures for online problems.