Satellite Imaging Scheduling: Algorithm Design and Application
Date Issued
2005
Date
2005
Author(s)
Lin, Wei-Cheng
DOI
en-US
Abstract
This thesis presents the research and development of a novel imaging scheduling system for the newest generation of low-orbit, earth observation satellite, FORMOSAT-2. FORMOSAT-2 passes through Taiwan twice daily in approximately 10 minutes each time. The mission of FORMOSAT-2 is to perform near real-time, remote imaging of ocean and landmass in the vicinity of Taiwan. The daily imaging scheduling problem of FORMOSAT-2 includes considerations of various imaging requests (jobs) with different reward opportunities, changeover efforts between two consecutive imaging operations (tasks), cloud coverage effects, and the availability of satellite resource. It belongs to a class of single-machine scheduling problems with salient features of job-assembly characteristic, sequence-dependent setup effect, and the constraint of operating time window. The scheduling problem is first formulated as a monolithic integer programming problem, which is NP-hard in computational complexity. An approximation of the weighted penalty of incomplete jobs by penalties of individual tasks facilitates a separable integer programming problem. For problems of such high complexity, dynamic programming and exhaustive search techniques are either too time-consuming or impractical for optimal solutions. Rule-based or heuristic approaches can reduce the computation time drastically but the resultant optimality may be unsatisfactory.
In view of the separable problem structure and researching findings about imaging scheduling of SPOT-5 in the literature, two solution approaches, Lagrangian relaxation and Tabu search, are adopted for novel solution algorithm design and investigation of their effectiveness. The Lagrangian relaxation algorithm design exploits the separable problem structure and relaxes coupling constraints with setup effect to decompose the problem into independent subproblem, each being a simple search for one task’s beginning imaging time within its time window. To solve the dual problem, Lagrangian multipliers are iteratively updated by subgradient (SG) method. For simplicity, a greedy-based feasibility adjustment heuristic is implemented to modify a dual solution into a feasible primal solution. It consists of constraint-violation resolving and task rescheduling. This heuristic is quick in computation and east to implement which exploits the separable problem structure and takes advantage of Lagrangian multipliers obtained from solving the dual. The Tabu search algorithm design integrates some important ideas including a greedy-based searching process, boundary extension by constraint relaxation, a dynamic Tabu tenure mechanism, intensification, and diversification. Core to three Tabu steps, Exploration, Intensification, and Diversification, are simply the greedy-based task’s insertion-and-removal process over partially constrained search space with the evaluation of primal objective function.
Numerical results of 40 classes of 400 realistic instances indicate that Lagrangian relaxation algorithm achieves near-optimal dual solutions and has an advantage in computational efficiency. With the help of intensification and diversification, Tabu search algorithm is superior in optimality. Furthermore, two hybrid schemes, CASCADE and COMBINATION, are designed for performance improvement. CASCADE adopts Tabu search techniques to improve the solution quality of Lagrangian relaxation algorithm directly. COMBINATION then deals with the development of Tabu search-based feasibility adjustment heuristic in Lagrangian relaxation algorithm. Numerical results of 7 classes of 70 test cases for 10-minute scheduling time horizon indicate that the two hybrid algorithms improve the solution quality of Lagrangian relaxation algorithm significantly. Under the same TS iteration process (maximum iteration number and program), there are no significant differences on optimality among two hybrid algorithm and pure TS algorithm. It is concluded that the design of feasibility adjustment heuristic has significant impact on the performance of Lagrangian relaxation algorithm. Tabu search algorithm is independent on the initial schedule. Since using the solutions of Lagrangian relaxation algorithm as initial schedules to Tabu search algorithm did not bring better solutions. This is because the Diversification Tabu step has done exclusive exploration over diverse schedules, which helps Tabu search algorithm to escape from trapping in a local optimum. In conclusion, Tabu search algorithm design is good at solving the daily imaging scheduling problem of FORMOSAT-2.
Subjects
拉氏釋限法
禁制搜尋法
混合演算法
衛星排程
地面觀測衛星
最佳化
整數規劃
Satellite Scheduling
Earth Observation Sateiilte
Integer Programming
Lagrangian Relaxation
Optimization
Tabu Search
Hybrid Algorithm
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-D86921013-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):ee807295565392135c36da8e1d650650