Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders
decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/32239 |
| Date | 21 March 2012 |
| Creators | Feng, Ti Kan |
| Contributors | Beck, J. Christopher |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0017 seconds