We describe an innovative solution to the problem of scheduling astronomy observations for the Stratospheric Ob-servatory for Infrared Astronomy, an airborne observatory. The problem contains complex constraints relating the feasi-bility of an astronomical observation to the position and time at which the observation begins, telescope elevation limits and available fuel. Solving the problem requires making discrete choices (e.g. selection and sequencing of observa-tions) and continuous ones (e.g. takeoff time and setting up observations by repositioning the aircraft). The problem also includes optimization criteria such as maximizing observing time while simultaneously minimizing total flight time. We describe a method to search for good flight plans that satisfy all constraints. This novel approach combines heuristic search, biased stochastic sampling, continuous optimization techniques, and well-founded approximations that eliminate feasible solutions but greatly reduce computation time.