Abstract
Most spacecraft have extremely limited resources compared with the state of the art in computer science and most missions have ambitious scientific goals, such as in the case of fly-bys like Voyager and Ulysses where there are limited windows of opportunity for achieving these goals. As a result, the scheduling of spacecraft experiments is a complete NP-hard problem for which an efficient solution procedure producing acceptable results is yet to be found. We describe the application of combinatorial optimization techniques to the automatic spacecraft scheduling problem. The sequencing problem is the search over the candidate sequences of experiments for a sequence that maximizes thevalue of the science conducted while minimizing constraint conflicts. A voluminous literature exists on planning and scheduling problems. Early approaches to solving these problems focused on analytical models, where the models were often based on techniques from mathematical programming and stochastic processes. While numerous advances have been made, many researchers have looked towards less traditional approaches to problems of this nature in order to solve the large-scale problems often encountered in practical applications. These approaches have still been based on the formulation of a mathematical model; however, heuristic procedures have been used to generate schedules that are considered good but not guaranteed to be optimal. There are several solution approaches that we believe can be successfully integrated with mathematical programming techniques to create a new solution paradigm addressing large-scale spacecraft scheduling optimization problems. These are Simulated Annealing (SA), Random Search, Tabu Search, and a diversification technique for Random Hill Climbing termed Strategic Oscillation. The power of these techniques lies in their ability to treat the objective function as a black box that returns a measure(s) of the goodness of the sequence; that is, these algorithms do not require a closed-form analytical description of the objective function nor any function derivatives. The algorithms we developed were evaluated by testing scheduling problems. Such testing on reduced size problems indicates the practicality of the proposed algorithms from a performance and timing perspective, while eliminating the need for sophisticated new sequence evaluation software to be developed or the need to integrate the new automation techniques into current software. Our exploratory computational results indicate that pseudo-random search techniques can generate viable sequences in reasonable times. Although the spacecraft scheduling problems used for testing were not based on actual experiment request data, they did match the data structures of actual problems with regard to size and constraint types. Therefore, we believe that the techniques described in this paper present viable approaches to spacecraft sequencing problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Aarts and J. Korst,Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing (Wiley, New York, 1989).
K. Bahrami, E. Biefeld, L. Costello and J. Clien, Space power system scheduling using expert systems,Proc. 21st Intersociety Energy Conversion Engineering Conf., San Diego (August, 1986).
A. Barr and E. Feigenbaum,The Handbook of Artificial Intelligence, Vol. 1 (1981) p. 156.
C. Berner, R. Durham and N. Reilly, Ground data system resource allocation process, NASA PUBl. 3033 for the 1989 Goddard AI Conf. (1989).
E. Biefeld, PLAN-IT: Knowledge-based mission sequencing,Proc. Advances in Intelligent Robotics Systems Conf., Cambridge, MA (October, 1986).
E. Biefeld and L. Cooper, Scheduling with chronology-directed search, AIAA Computers in Aerospace and Exhibit, Monterey, CA (October 3–5, 1989).
E. Biefeld and L. Cooper, Operations mission planner final report, Jet Propulsion Laboratory (March 15, 1990).
D. Biroscak et al., Earth observing system data and information system (EOSDIS): Flight operations segment operations concept, prepared by Computer Sciences Corporation for NASA Goddard Space Flight Center, Contract NAS 5-31500, Task 11 004 (March, 1991).
C. Collins, J. George and E. Zamani, Strategies for automatic planning, JPL Publ. 89-12 (May 1, 1989).
J. Cruz and W. Eggemeyer, A planning and scheduling lexicon, JPL Publ. 89-25 (September 15, 1989).
L. Davis,Genetic Algorithms and Simulated Annealing (Morgan Kaufmann, Los Altos, CA, 1987).
W. Dias, J. Henricks and J. Wong, PLAN-IT: Scheduling assistant for solar system exploration, Telematics and Informatics 4(1987)275–287.
W. Eggemeyer and A. Bowling, Deep space network resource scheduling approach and application,Proc. Space Applications of AI and Robotics, GSFC (May, 1987).
W. Eggemeyer and S. Grenander, PLAN-IT applications and knowledge gained,Workshop on Operations Planning and Scheduling Systems for the Space Station Era, University of Colorado-Boulder, Boulder, CO (August, 1987).
W. Eggemeyer and J. Cruz, PLAN-IT-2: The next generation planning and scheduling tool,Proc. Space Application of AI and Robotics, GSFC (May, 1990).
S. French,Scheduling and Sequencing: An Introduction to the Mathematics of the Job-Shop (Wiley, New York, 1982).
M. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).
F. Glover, Tabu search: Part I, ORSA J. Comp. 1(1989)190–206.
F. Glover, Tabu search: Part II, ORSA J. Comp. 2(1990)4–32.
D. Goldberg,Genetic Algorithms in Search Optimization, and Machine Learning (Addison-Wesley, Reading, MA, 1989).
J.J. Grefenstette,Genetic Algorithms and Their Applications, 1st Int. Conf. (Lawrence Erlbaum Associates, Texas Instruments, Inc., Dallas, 1985).
S. Grenander, Toward the fully capable AI space mission planner, Aerospace America (August, 1985).
S. Grenander, Outward bound: Machine intelligence in deep space, Comp. Mech. Eng. (September, 1986).
N.G. Hall and M. Magazine, Maximizing the value of a space mission,TIMS/ORSA Orlando Meeting (April, 1992).
A. Hertz, Tabu search for large scale timetabling problems, Eur. J. Oper. Res. 54(1991)39–47.
B. Katz and R. Brooks, Understanding natural language for spacecraft sequencing, J. Brit. Interplanet. Soc. 40(1987).
B. Katz, START natural language systems, MIT AI Lab Memo (1987).
M. Laguna, W. Barnes and F. Glover, Tabu search methods for a single machine scheduling problem, J. Int. Manuf. 2(1991)253–260.
E.L. Mooney and R.L. Rardin, Tabu search for a class of scheduling problems, Ann. Oper. Res. 41(1993)253–278.
C. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982).
M. Rokey and S. Grenander, Artificial intelligence planning applications for space exploration and space robotics,Proc. Conf. on Aerospace Application of Artificial Intelligence, Dayton, OH (October, 1986).
M. Rokey and S. Grenander, Planning for space telerobotics: The remote mission specialist, IEEE Expert (June, 1990)8–15.
F. Rotman, Pseudo-random search techniques for spacecraft scheduling, University of Virginia Master's Thesis (May, 1993).
W. Scherer and C. White, A planning and decision aiding procedure for purchasing and launching spacecraft, Interfaces 16(1986)31–40.
J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem, ORSA J. Comp. 2(1990)33–45.
P.J. van Laarhoven, E.H.L. Aarts and J.K. Lenstra, Jobshop scheduling by simulated annealing, Oper. Res. 40(1992)113–125.
S. Vere, Planning in time: Windows and durations for activities and Goals, IEEE Trans. Pattern Anal. Mach. Int. PAMI-5(1983).
E. Taillard, Some efficient heuristic methods for the flowshop sequencing problem, Eur. J. Oper. Res. 47(1990)65–74.
A. Webb, A solution to the DSN optimal scheduling problem using mathematical programming, JPL Publ. EM 312/81–121 (1981).
A. Webb, DSN automated scheduling: Research and prototype development, JPL Publ. D-1710 (August, 1984).
A. Webb, Mathematical programming applications in the scheduling of spacecraft on the NASA deep space network,12th Int. Symp. on Mathematical Programming, MIT (August 5–9, 1985).
D. White,Operational Research (Wiley, New York, 1985).
M. Widmer, Job shop scheduling with tooling constraints: a tabu search approach, J. Oper. Res. Soc. 24(1991)75–82.
H.P. Williams,Model Building in Mathematical Programming (Wiley, New York, 1991).
D.L. Woodruff and M.L. Spearman, Sequencing and batching for two classes of jobs with deadlines and setup times, Prod. Oper. Manag. 1(1992)87–102.
E. Zamani, J. George, C. Collins and B. Zimmerman, Spacecraft activity planning tool using object-oriented techniques,Tools '89 Conf., Paris (1989).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Scherer, W.T., Rotman, F. Combinatorial optimization techniques for spacecraft scheduling automation. Ann Oper Res 50, 525–556 (1994). https://doi.org/10.1007/BF02085657
Issue Date:
DOI: https://doi.org/10.1007/BF02085657