Combining Decomposition and Hybrid Algorithms for the Satellite Range Scheduling Problem | Posted on:2013-04-23 | Degree:M.A.Sc | Type:Thesis | University:University of Toronto (Canada) | Candidate:Feng, Ti Kan | Full Text:PDF | GTID:2458390008467266 | Subject:Operations Research | Abstract/Summary: | | 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. | Keywords/Search Tags: | Scheduling problem, Murrsp, Decomposition, Hybrid, Algorithms | | Related items |
| |
|