Article ID: | iaor20042185 |
Country: | Netherlands |
Volume: | 7 |
Issue: | 1 |
Start Page Number: | 87 |
End Page Number: | 103 |
Publication Date: | Mar 2003 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Vasquez Michael, Hao Jin-Kao |
Keywords: | scheduling, programming: goal |
This paper introduces tight upper bounds for the daily photograph scheduling problem of earth observation satellites. These bounds, which were unavailable until now, allow us to assess the quality of the heuristic solutions obtained previously. These bounds are obtained with a partition-based approach following the ‘divide and pas conquer’ principle. Dynamic programming and tabu search are conjointly used in this approach. We present also simplex-based linear programming relaxation and a relaxed knapsack approach for the problem.