Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)


Department of Operational Sciences

First Advisor

Dennis C. Dietz, PhD


Over the last two decades, our military forces have been working to incorporate the latest computer technology into the combat planning process. The earliest efforts use word processors, spreadsheets, and databases to organize planning data and to display high level summaries for commanders. Later efforts perform feasibility checks as missions are planned to insure that the necessary resources are available and that the assets requested are capable of meeting the assigned scheduling requirements. Some of the most recent computer planning tools have included the capability to automatically plan individual missions or groups of missions. These automated efforts have been heuristic in nature due to the time limitations inherent to real-time combat planning. The methodologies in this research offer effective optimal alternatives to the limited heuristics available in the current combat planning tools. This research formulates and solves a new class of project scheduling problems with applications to both military and civilian planning. It is shown that the solution space for this class of problems may be reduced in order to improve the effectiveness of both optimal and heuristic solution methodologies. In addition, a general method for extending implicit enumeration algorithms to obtain k-best solution sets is developed. The reduced solution space and the general k-best solutions methodology are exploited to develop several efficient solution approaches for this new class of problems; an implicit enumeration algorithm, a decomposition approach, an evolutionary algorithm, and a hybrid decomposition approach. The applicability and flexibility of the methodology are demonstrated with a case study that focuses on the force level planning of combat missions for an air campaign. While the focus of the case study is combat planning, the concepts illustrated are applicable to the general field of program and project management.

AFIT Designator


DTIC Accession Number