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

0340752Chrobak这个为期三年的美法计算机科学合作研究项目涉及加州大学河滨分校的Marek Chrobak和法国的研究人员，巴黎理工大学的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.