Approximation-Based Techniques for Resource-Constrained Scheduling Problems

点击翻译按钮获取中文摘要

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.