John A. Flory

Date of Award


Document Type


Degree Name

Master of Science in Operations Research


Department of Operational Sciences

First Advisor

Jeffery P. Kharoufeh, PhD


This thesis addresses the problem of optimally selecting and specifying satellite payloads for inclusion on a satellite bus to be launched into a constellation. The objective is to select and specify payloads so that the total lifetime utility of the constellation is maximized. The satellite bus is limited by finite power, weight, volume, and cost constraints. This problem is modeled as a classical knapsack problem in one and multiple dimensions, and dynamic programming and binary integer programming formulations are provided to solve the problem. Due to the computational complexity of the problem, the solution techniques include exact methods as well as four heuristic procedures including a greedy heuristic, two norm-based heuristics, and a simulated annealing heuristic. The performance of the exact and heuristic approaches is evaluated on the basis of solution quality and computation time by solving a series of notional and randomly-generated problem instances. The numerical results indicate that, when an exact solution is required for a moderately-sized constellation, the integer programming formulation is most reliable in solving the problem to optimality. However, if the problem size is very large, and near-optimal solutions are acceptable, then the simulated annealing algorithm performs best among the heuristic procedures.

AFIT Designator


DTIC Accession Number