Approximation-Based Techniques for Resource-Constrained Scheduling Problems

该项目旨在开发一种算法工具，用于解决多标准资源约束调度问题。目标是：(1)推广和实现基于为更简单但相关的模型提供最佳（分析性）最坏情况性能保证的技术的算法；(2)开发在复杂和现实的资源约束项目调度设置中算法的最坏情况分析工具；(3)评估研究合作伙伴提供的实际应用的性能，包括桑迪亚国家实验室提供的大型复杂维护调度问题；(4)开发利用其特殊结构更快地求解底层线性规划的技术。如果成功的话，这项研究将产生在各种应用领域（包括化学工程、复杂系统维护、项目规划）中产生候选高质量时间表集合的技术。除了为特定的最优性标准生成高质量的计划之外，计划的集合将允许在最优性标准的集合中选择最佳平衡的计划。此外，时间表的收集将允许灵活地选择与物流规划和优化系统的其他要素最好地集成的时间表。这项工作也将有助于计算工具和方法，可用于解决在调度和资源分配问题中出现的线性方案。

This project is to develop an algorithmic tool for solving multicriteria resource-constrained scheduling problems. The goals are: (1) to generalize and implement algorithms based on techniques that yield the best (analytical) worst-case performance guarantees for simpler but relevant models; (2) develop tools for the worst-case analysis of algorithms in complex and realistic resource-constrained project scheduling settings; (3) evaluate the performance on real applications provided by research partners, including a large and complex maintenance scheduling problem provided by Sandia National Laboratories; and (4) develop techniques for solving the underlying linear programs faster by taking advantage of their special structure. If successful, this research will yield techniques to generate, in a variety of application domains (including chemical engineering, complex systems maintenance, project planning) collections of candidate high-quality schedules. Beyond yielding schedules of high quality for a particular optimality criterion, the collection of schedules will allow the selection of a schedule that balances best amongst a collection of optimality criteria. In addition, the collection of schedules will allow flexibility in the choice of a schedule that best integrates with other elements of the logistics planning and optimization system. The work will also contribute to the computational tools and methodologies available for the solution of linear programs that arise in scheduling and resource allocation problems.