ATTEND: Analytical Tools to Evaluate Negotiation Difficulty

摘要

The ATTEND (Analytical Tools To Evaluate Negotiation Difficulty) project was established to study computational complexity issues arising in complex dynamic and large-scale real-world problems requiring finding 'good- enough/soon- enough' assignments of resources to tasks. 'Good-enough/soon- enough' problems arise in situations where finding the best solution obtainable within time limits was preferable to finding an optimal solution in unbounded time. Examples range from real-time fire control problems in which time is of the essence to operational risk management and logistics problems in which size and complexity make it computationally infeasible to seek full optimality. Scope: The effort focused upon flight operations scheduling problems exemplifying challenges faced by Marines Corps flight schedulers for AV8-B- Harrier aircraft in Marine Aircraft Group 13. Methods: Our approach mapped resource allocation planning and scheduling problems to formal declarative representations which could then be solved and characterized using available state-of-the-art constraint solvers. Major Findings Including Results Conclusions and Recommendations: ATTEND showed the effectiveness of a multi- phase hybrid approach to solve computationally hard real-world problems: combining multiple solvers proved to be orders of magnitude more efficient that any individual solver that has been built or proposed for problems of the class which was studied.