Research Information System
American Control Conference 2009, Missouri, United States Of America, 10 - 12 June 2009, pp.5198-5199
In this work, we focus on solving large-scale UAV fleets scheduling problem in dynamically changing (i.e. external event-driven or operator induced selection) scenarios. This autonomous scheduling of planned tasks and allocation of resources is designed to provide real-time decision support to the operator for problem sizes that is intractable or infeasible by one or a set of operators. We begin by analyzing the computational complexity of a well-known Solve & Robustify approach that generates robust and flexible schedules and propose the temporal space partition approach for decreasing the computationally expensive solve step. The improved algorithm, which is refereed as Earliest Start Time Algorithm with Partitioning (ESTA(P)), divides the larger problem into smaller subproblems by partitioning the temporal space and then iteratively solves the subproblems. Benchmark problem comparisons with the classical ESTA formulation for two hundred tasks indicates that the proposed temporal space partitioning approach improves the computation time forty-fold while only incurring five percent increase in the total completion of the tasks.