| |
 |
| Paper: |
The GBT Dynamic Scheduling System: Scheduling Applications of the Knapsack Problem and Sudoku |
| Volume: |
411, Astronomical Data Analysis Software and Systems XVIII |
| Page: |
351 |
| Authors: |
Sessoms, E.; Clark, M.; Marganian, P.; McCarty, M.; Shelton, A. |
| Abstract: |
We applied algorithmic approaches to both theoretical and practical aspects of scheduling the Robert C. Byrd Green Bank Telescope (GBT).
When using a theoretical approach to scheduling, assigning a numerical value, or score, to a telescope period is only half of the problem. The other half consists of using the score to determine the best global arrangement of the telescope periods in order to maximize the scientific throughput of the telescope. The naive brute-force approach of trying all possible schedules is too computationally expensive. Instead we applied a well-studied approach from operations research, known as dynamic programming. Specifically, we found the so-called “knapsack” algorithm to be a good fit to this problem.
On the other hand, we cannot actually achieve maximum theoretical efficiency due to many practical constraints on telescope scheduling. The most severe practical constraints are fixed periods that must be scheduled at a specific date and time regardless of possible score and windowed periods that must be scheduled in regular, recurring intervals.
The primary difficulty in scheduling fixed and windowed sessions is that they have the potential to conflict and even to generate irresolvable conflicts (double booking). In working on this problem, we realized it shared many characteristics with the game of Sudoku. In Sudoku, there are many possible arrangements of the recurring numbers 1 through 9 (telescope sessions). Some of these are fixed (the hints) and the others must live in windows (distinct groups having one instance each of each digit).
Sudoku puzzles are solved algorithmically using a heuristic-guided bruteforce search. We followed a similar approach. A full brute-force search is, again, too computationally expensive, but we found ways to restrict the search enough to make it feasible. We used a number of heuristics but found the largest gains came from partitioning the problem into distinct subsets than can each be scheduled independently and from ordering the search in such a way that earlier choices had the greatest impact on reducing the computational complexity of later choices. |
|
|
|
|
|
