Maximizing the value of a space mission

The problem of selecting and scheduling projects to maximize the scientific, military or commercial value of a space mission has been the subject of ongoing studies for several years. The typical outcome of such studies, even after many man-years of effort, is a heuristic solution with no comparison with optimality. We depart from the traditional, knowledge-based systems, approach and describe a machine scheduling model for the problem. The problem, which is similar to a longest path problem with time windows, is NP-complete in the strong sense. A number of heuristic methods are described, and computational tests reveal that they routinely deliver very close to optimal solutions. We describe two upper bounding procedures, based upon a preemptive relaxation of the problem, and upon the use of Lagrangean relaxation. The heuristics and bounding procedures are incorporated into a dynamic programming algorithm, which can solve to optimality randomly generated problem instances with one hundred or more projects. We further demonstrate how, if problems are too large to be solved optimally, a limited-enumeration version of this algorithm can be used to provide very accurate heuristic solutions. We also examine some special cases and variants of the problem.