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

0340752 ChrobakThis三年美国-法国计算机科学合作研究项目涉及加州大学滨江分校的Marek Chrobak和法国研究人员，Ecole Polytechnique的Philippe Baptiste和巴黎南部大学的Christoph Durr。他们的目标是设计有效的算法调度问题中出现的实时系统和多用户计算机系统的服务质量约束。为了模拟这种约束，他们集中研究加速动态规划算法的技术，以解决调度问题，并在非常快的算法，计算接近最佳的时间表。该项目利用互补的专业知识，美国和法国的研究人员在算法设计和分析和计算机理论。 一名美国研究生将参与所开发算法的设计、分析和实现，并将以这项研究为基础撰写博士论文。调度的其他领域的计算问题可以应用开发的算法。这些想法包括解决调度问题的近似方法，以及在线问题的新性能度量。

0340752ChrobakThis 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.