NRAO Home  >  Green Bank  |  Wiki Topic:    GB > Dynamic > ADASS2008
   Changes | Index | Search | Go

ADASS 2008 Preparation

A few notes:

  1. All titles should start with "The GBT Dynamic Scheduling System:..."

Overview Talk - Karen

Posters

Ranking Algorithm (PN 5.2) - Dana

Scheduling Algorithms - Eric

On the theoretical side, assigning a numerical value to a telescope period is only one piece of the puzzle. The other piece consists of using that score to determine the best global arrangement of 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 brute-force 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.

Web Framework - Paul

Scheduling System (see 'The GBT Dynamic Scheduling System: A New Scheduling Paradigm') are discussed, focusing on languages, frameworks, and tools. We use a popular Python web framework, TurboGears?, to take advantage of the extensive web services the system provides. TurboGears? is a model-view-controller framework, which aggregates SQLAlchemy, Genshi, and CherryPy? respectively. On top of this framework, Javascript (Prototype, script.aculo.us) and cascading style sheets (Blueprint) are used for desktop-quality web pages.

Observer's Perspective - Jim

To make the most efficient use of telescope time, the NRAO is implementing a Dynamic Scheduling System (DSS) for the Robert C. Byrd Green Bank Telescope (GBT). The DSS aims to match observing projects to the existing weather and other observing conditions, without sacrificing observers' interactive control of their experiments. To meet this goal, the DSS schedules not observing scripts but rather blocks of time during which an observer can attend to the observation and control the telescope, often from a remote location. The DSS generates a new schedule every day, for the 24-hour period beginning one day hence. Observers therefore must be prepared to run observations with 24 - 48 hours notice. Being available and ready to observe on short notice requires observers to adopt a mindset and set of practices unlike their experiences with other telescopes. While these may be an inconvenience for some, the benefits are substantial, the primary one being astronomers are almost assured of observing in appropriate weather and getting high quality data. While observers should expect to be "on the ready" at all times, the DSS does give them the opportunity to black-out time ranges to avoid for scheduling. In addition to the scheduling algorithms, the DSS team has developed a set of software tools to help observers manage their projects, to notify observers of scheduling news, and to help observers anticipate when their projects will get scheduled. In this contribution we will report observers' experiences from the first tests of the GBT DSS, which took place from June 1 - September 30, 2008.

Scheduler's Perspective - Jules

Before June 2008, scheduling at the Robert C. Byrd Green Bank Telescope (GBT) was accomplished using two templates, one a high frequency (>4.8 GHz) schedule to run in good weather, the other low frequency. These were constructed and maintained by the GBT telescope scheduler. The beta testing of the Dynamic Scheduling System (DSS) has provided a a more efficient method of interleaving the various types of observing sessions. For summer 2008, these sessions were divided into three groups - fixed such as coordinated VLBI observations, windowed such as pulsar monitoring, and open that can run at any time. Although there are inefficiencies and limitations in the System from the scheduler's perspective, a particularly valuable feature is the ability to handle flexible scheduling of high frequency projects based on weather forecasts. We describe the new scheduling process in some detail and its impact on observers from the scheduler's viewpoint. Finally we suggest improvements that will be incorporated into future DSS releases.

Software Engineer's Perspective - Mike

During the summer trimester of 2008, all observations on the Robert C. Byrd Green Bank Telescope (GBT) were scheduled using the new Dynamic Scheduling System (DSS). Beta testing exercised the policies, algorithms, and software developed for the DSS project. Since observers are located all over the world, the DSS was implemented as a web application. Technologies such as iCalendar, RSS feeds, email, and instant messaging are used to transfer as much or as little information to observers based on their desires. We discuss the software engineering challenges leading to our implementation and relate our adaptation of agile development practices to design and develop the DSS. Additionally, we describe handling differences in expected versus actual initial conditions. We then identify lessons learned from beta testing and present conclusions.

Scheduling Probabilities - Mark

Because of variable local weather in Green Bank, West Virginia, along with the wide frequency coverage of the Robert C. Byrd Green Bank Telescope (GBT), substantial improvement in efficient use of telescope time is possible by dynamically scheduling observers within a time range when weather forecasts are reliable; however, using the best forecasts would require observers to be constantly "on-call." During the 2008 summer trimester beta testing, the GBT Dynamic Scheduling System (DSS) attempted to mitigate this inherent conflict by 1) compromising between the best weather forecasts vs. short-term observer notification, and 2) providing earlier indicators of the likelihood of being selected by the scheduling algorithms. These indicators were derived from simulations based on Green Bank weather forecasts from previous years and from relative project rankings covering the entire time range of available weather forecasts. We report our experience on the generation of the information, its presentation, and its use by observers.

Demo

The Robert C. Byrd Green Bank Telescope (GBT) Dynamic Scheduling System (DSS) aims to maximize the observing efficiency of the telescope, while maintaining its signal characteristics: data quality, ease of use and flexibility. Observations are scheduled on the basis of weather, sky coordinates, radio-frequency interference (RFI) and other local parameters. Observing projects are divided into a number of possible observing sessions, which may be classified as Fixed, Open or Windowed. Observations are scheduled with a minimum of 24-hour notice, and observers are able to schedule blackout times and dates for which they will not be available. To accommodate the <20% of the time when schedules can change due to, e.g. a sudden change in the weather, certain projects can be designated as backup and be run either by the telescope operator or by an observer who has elected to be called upon with no prior notice.

The scheduling algorithm then uses all available data to determine the most efficient schedule for the GBT over the subsequent 24-hours. This demonstration presents an overview of the GBT DSS including the ranking and scheduling algorithms, scheduling probabilities generation, the web framework for the system, and a summary of the beta testing which was held from June - September, 2008

Birds Of a Feather (BOF) discussion

Web Technologies

The renaissance of the web has driven development of many new technologies to that have forever changed the way we write software. The resulting tools have been applied to both solve problems and created new ones in a wide range of domains. This discussion covers how these technologies are being used in the scientific computing community.

We'd like to start a BOF on Telescope Scheduling, but:

-- MikeMcCarty - 09 Jul 2008

Topic ADASS2008 . { Edit | Attach | Ref-By | Printable | Diffs | r1.42 | > | r1.41 | > | r1.40 | More }
Revision r1.42 - 04 Sep 2008 - 15:54 GMT - MikeMcCarty
Parents: WebHome 		Content copyright © 1999-2007 by the contributing authors.
All material on this collaboration platform is the property of the contributing authors.