Maximizing the value of a space mission. (English) Zbl 0813.90078

Summary: 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 to 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.


90B90 Case-oriented studies in operations research
90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Arkin, E. M.; Silverberg, E. B., Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, 18, 1-8 (1987) · Zbl 0636.90042
[2] Barnes, E. R.; Hoffman, A. J., On transportation problems with upper bounds on leading rectangles, SIAM Journal on Algebraic and Discrete Methods, 6, 487-496 (1985) · Zbl 0589.90056
[3] Biefeld, E. W., Plan-It: Knowledge-based mission sequencing, (Technical Report (1989), Jet Propulsion Laboratory: Jet Propulsion Laboratory Pasadena, CA)
[4] Biefeld, E. W.; Cooper, L. P., Replanning and iterative refinement in mission scheduling, (Technical Report (1988), Jet Propulsion Laboratory: Jet Propulsion Laboratory Pasadena, CA)
[5] Bratley, P.; Florian, M.; Robillard, P., Scheduling with earliest start and due date constraints on multiple machines, Naval Research Logistics Quarterly, 22, 163-175 (1975)
[6] Desrochers, M.; Soumis, F., A generalized permanent labeling algorithm for the shortest path problem with time windows, Infor, 26, 191-212 (1988) · Zbl 0652.90097
[7] Desrosiers, J.; Pelletier, J.; Soumis, F., Plus court chemin avec contraintes d’horaires, Rairo, 17, 357-377 (1983) · Zbl 0528.90082
[8] Desrosiers, J.; Soumis, F.; Desrochers, M., Routing with time windows by column generation, Networks, 14, 545-565 (1984) · Zbl 0571.90088
[9] Dessouky, M. I.; Moray, N. P.; van de Velde, S. L., Single machine scheduling with expiration dates, (presented at ORSA/TIMS National Conference. presented at ORSA/TIMS National Conference, Philadelphia, October 1990 (1990))
[10] Evans, J. R., The factored transportation problem, Management Science, 30, 1021-1024 (1984) · Zbl 0554.90075
[11] Ford, L. R.; Fulkerson, D. R., Flows in networks (1962), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0139.13701
[12] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with spread-time constraints, Operations Research, 35, 849-858 (1987) · Zbl 0638.90055
[13] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with working-time constraints, Operations Research, 37, 395-403 (1989) · Zbl 0672.90074
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[15] Gertsbakh, I.; Stern, H. I., Minimal resources for fixed and variable job schedules, Operations Research, 26, 68-85 (1978) · Zbl 0371.90058
[16] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimiaation and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[17] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Mathematical Programming, 6, 62-88 (1974) · Zbl 0284.90057
[18] Kolen, A. W.J.; Kroon, L. G., On the computational complexity of (maximum) shift class scheduling, (Research Memorandum No. 89.035 (1989), Faculty of Economics, Limburg University: Faculty of Economics, Limburg University Maastricht, Netherlands)
[19] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.