Daily Imaging Scheduling of an Earth Observation Satellite
- 22 February 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans
- Vol. 35 (2), 213-223
- https://doi.org/10.1109/tsmca.2005.843380
Abstract
This work presents the development of a daily imaging scheduling system for a low-orbit, Earth observation satellite. The daily imaging scheduling problem of satellite considers various imaging requests with different reward opportunities, changeover efforts between two consecutive imaging tasks, cloud-coverage effects, and the availability of the spacecraft resource. It belongs to a class of single-machine scheduling problems with salient features of sequence-dependent setup, job assembly, and the constraint of operating time windows. The scheduling problem is formulated as an integer-programming problem, which is NP-hard in computational complexity. Lagrangian relaxation and linear search techniques are adopted to solve this problem. In order to demonstrate the efficiency and effectiveness of our solution methodology, a Tabu search-based algorithm is implemented, which is modified from the algorithm in Vasquez and Hao, 2001. Numerical results indicate that the approach is very effective to generate a near-optimal, feasible schedule for the imaging operations of the satellite. It is efficient in applications to the real problems. The Lagrangian-relaxation approach is superior to the Tabu search one in both optimality and computation time.Keywords
This publication has 10 references indexed in Scilit:
- Selecting and scheduling observations of agile satellitesAerospace Science and Technology, 2002
- A “Logic-Constrained” Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation SatelliteComputational Optimization and Applications, 2001
- Three Scheduling Algorithms Applied to the Earth Observing Systems DomainManagement Science, 2000
- Scheduling flexible flow shops with sequence-dependent setup effectsIEEE Transactions on Robotics and Automation, 2000
- Maximizing the value of a space missionEuropean Journal of Operational Research, 1994
- Impact of sequence-dependent setup time on job shop scheduling performanceInternational Journal of Production Research, 1994
- Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup timesInternational Journal of Production Research, 1994
- Scheduling of manufacturing systems using the Lagrangian relaxation techniqueIEEE Transactions on Automatic Control, 1993
- Scheduling jobs with simple precedence constraints on parallel machinesIEEE Control Systems Magazine, 1990
- Validation of subgradient optimizationMathematical Programming, 1974