Approximation-Based Techniques for Resource-Constrained Scheduling Problems

该项目旨在开发一个用于解决多目标资源受限调度问题的算法工具。目标是：(1)推广和实现基于为简单但相关的模型提供最佳(分析)最坏情况性能保证的技术的算法；(2)开发在复杂和现实的资源受限的项目调度环境中对算法进行最坏情况分析的工具；(3)评估研究伙伴提供的实际应用的性能，包括由Sandia国家实验室提供的大型且复杂的维护调度问题；以及(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.