SEARCH · Engineering Papers

Results for “SCHEDULING”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 73 records · Page 4

All sources NASA NTRS DOE OSTI

NASA NTRS1988

Space station payload operations scheduling with ESP2

The Mission Analysis Division of the Systems Analysis and Integration Laboratory at the Marshall Space Flight Center is developing a system of programs to handle all aspects of scheduling payload operations for Space Station. The Expert Scheduling Program (ESP2) is the heart of this system. The task of payload operations scheduling can be simply stated as positioning the payload activities in a mission so that they collect their desired data without interfering with other activities or violating mission constraints. ESP2 is an advanced version of the Experiment Scheduling Program (ESP) which was developed by the Mission Integration Branch beginning in 1979 to schedule Spacelab payload activities. The automatic scheduler in ESP2 is an expert system that embodies the rules that expert planners would use to schedule payload operations by hand. This scheduler uses depth-first searching, backtracking, and forward chaining techniques to place an activity so that constraints (such as crew, resources, and orbit opportunities) are not violated. It has an explanation facility to show why an activity was or was not scheduled at a certain time. The ESP2 user can also place the activities in the schedule manually. The program offers graphical assistance to the user and will advise when constraints are being violated. ESP2 also has an option to identify conflict introduced into an existing schedule by changes to payload requirements, mission constraints, and orbit opportunities.

Stacy, Kenneth L.↗

NASA NTRS1992

The application of artificial intelligence to astronomical scheduling problems

Efficient utilization of expensive space- and ground-based observatories is an important goal for the astronomical community; the cost of modern observing facilities is enormous, and the available observing time is much less than the demand from astronomers around the world. The complexity and variety of scheduling constraints and goals has led several groups to investigate how artificial intelligence (AI) techniques might help solve these kinds of problems. The earliest and most successful of these projects was started at Space Telescope Science Institute in 1987 and has led to the development of the Spike scheduling system to support the scheduling of Hubble Space Telescope (HST). The aim of Spike at STScI is to allocate observations to timescales of days to a week observing all scheduling constraints and maximizing preferences that help ensure that observations are made at optimal times. Spike has been in use operationally for HST since shortly after the observatory was launched in Apr. 1990. Although developed specifically for HST scheduling, Spike was carefully designed to provide a general framework for similar (activity-based) scheduling problems. In particular, the tasks to be scheduled are defined in the system in general terms, and no assumptions about the scheduling timescale are built in. The mechanisms for describing, combining, and propagating temporal and other constraints and preferences are quite general. The success of this approach has been demonstrated by the application of Spike to the scheduling of other satellite observatories: changes to the system are required only in the specific constraints that apply, and not in the framework itself. In particular, the Spike framework is sufficiently flexible to handle both long-term and short-term scheduling, on timescales of years down to minutes or less. This talk will discuss recent progress made in scheduling search techniques, the lessons learned from early HST operations, the application of Spike to other problem domains, and plans for the future evolution of the system.

Johnston, Mark D.↗

NASA NTRS2008

DSN Scheduling Engine

The DSN (Deep Space Network) Scheduling Engine targets all space missions that use DSN services. It allows clients to issue scheduling, conflict identification, conflict resolution, and status requests in XML over a Java Message Service interface. The scheduling requests may include new requirements that represent a set of tracks to be scheduled under some constraints. This program uses a heuristic local search to schedule a variety of schedule requirements, and is being infused into the Service Scheduling Assembly, a mixed-initiative scheduling application. The engine resolves conflicting schedules of resource allocation according to a range of existing and possible requirement specifications, including optional antennas; start of track and track duration ranges; periodic tracks; locks on track start, duration, and allocated antenna; MSPA (multiple spacecraft per aperture); arraying/VLBI (very long baseline interferometry)/delta DOR (differential one-way ranging); continuous tracks; segmented tracks; gap-to-track ratio; and override or block-out of requirements. The scheduling models now include conflict identification for SOA(start of activity), BOT (beginning of track), RFI (radio frequency interference), and equipment constraints. This software will search through all possible allocations while providing a best-effort solution at any time. The engine reschedules to accommodate individual emergency tracks in 0.2 second, and emergency antenna downtime in 0.2 second. The software handles doubling of one mission's track requests over one week (to 42 total) in 2.7 seconds. Further tests will be performed in the context of actual schedules.

Clement, Bradley↗

NASA NTRS2010

Request-Driven Schedule Automation for the Deep Space Network

The DSN Scheduling Engine (DSE) has been developed to increase the level of automated scheduling support available to users of NASA s Deep Space Network (DSN). We have adopted a request-driven approach to DSN scheduling, in contrast to the activity-oriented approach used up to now. Scheduling requests allow users to declaratively specify patterns and conditions on their DSN service allocations, including timing, resource requirements, gaps, overlaps, time linkages among services, repetition, priorities, and a wide range of additional factors and preferences. The DSE incorporates a model of the key constraints and preferences of the DSN scheduling domain, along with algorithms to expand scheduling requests into valid resource allocations, to resolve schedule conflicts, and to repair unsatisfied requests. We use time-bounded systematic search with constraint relaxation to return nearby solutions if exact ones cannot be found, where the relaxation options and order are under user control. To explore the usability aspects of our approach we have developed a graphical user interface incorporating some crucial features to make it easier to work with complex scheduling requests. Among these are: progressive revelation of relevant detail, immediate propagation and visual feedback from a user s decisions, and a meeting calendar metaphor for repeated patterns of requests. Even as a prototype, the DSE has been deployed and adopted as the initial step in building the operational DSN schedule, thus representing an important initial validation of our overall approach. The DSE is a core element of the DSN Service Scheduling Software (S(sup 3)), a web-based collaborative scheduling system now under development for deployment to all DSN users.

Johnston, Mark D.↗

NASA NTRS2018

Spacecraft Block Scheduling for NASA’s Deep Space Network

Currently, NASA’s Deep Space Network (DSN) is responsible for uplink to, downlink from, and/or tracking of dozens of missions for space agencies across the world. The DSN scheduling process starts about four months prior to the start of the schedule week, a process in which requirements are deﬁned and then the schedule is created, de-conﬂicted, and negotiated over the next 2–3 weeks with a team of mission representatives. Now scheduled for late 2019, Exploration Mission1 (EM-1) will deploy upwards of 12 SmallSat missions that will be served by the DSN. This will increase the DSN’s actively serviced spacecraft by up to 30%, further increasing the diﬃculty of meeting all mission needs via the over subscribed network. To mitigate their impact on DSN scheduling, a block scheduling process is proposed for scheduling the SmallSats. Block scheduling consists of aggregating spacecraft together into larger “pseudo-spacecraft” based on geometric alignment that then follow the same process as any other DSN mission to receive segments of track time. These tracks are then decomposed into tracks for individual users based on their speciﬁc requirements. This paper describes a full novel scheduling tool set for building candidate blocks, evaluating the eﬃcacy of these blocks, and optimal and suboptimal de-blocking schemes. To demonstrate these developed tools, results from three simulations are presented: a blocking example with lunar SmallSats, blocking potential in the greater DSN spacecraft catalog, and opportunistic multiple spacecraft per aperture potential for the DSN spacecraft catalog. Block scheduling has the potential to reduce overhead and scheduling resources for the EM-1 SmallSats while also providing them with a better means to meet their mission requirements.

Bilén, Sven G.↗

NASA NTRS1988

A prototype combinatorial scheduler for space-borne observational instruments

A prototype scheduler has been developed for observations to be carried out by the NASA Gamma Ray Observatory. The purpose of the scheduling system is to provide an automated method to determine optimized schedules conforming to all scheduling guidelines. Strategies used in creating COMPTEL/EGRET schedules and in scheduling OSSE targets are examined. It is concluded that the hybrid scheduler creates optimal schedules, or very nearly optimal schedules, and reduces the estimated scheduling time by 18 or 19 orders of magnitude, from about 10 to the 14th years to as few as 561 seconds.

Gilstrap, Lewey O.↗

NASA NTRS1989

A heuristic approach to incremental and reactive scheduling

An heuristic approach to incremental and reactive scheduling is described. Incremental scheduling is the process of modifying an existing schedule if the initial schedule does not meet its stated initial goals. Reactive scheduling occurs in near real-time in response to changes in available resources or the occurrence of targets of opportunity. Only minor changes are made during both incremental and reactive scheduling because a goal of re-scheduling procedures is to minimally impact the schedule. The described heuristic search techniques, which are employed by the Request Oriented Scheduling Engine (ROSE), a prototype generic scheduler, efficiently approximate the cost of reaching a goal from a given state and effective mechanisms for controlling search.

Odubiyi, Jide B.↗

NASA NTRS1992

Distributed project scheduling at NASA: Requirements for manual protocols and computer-based support

The increasing complexity of space operations and the inclusion of interorganizational and international groups in the planning and control of space missions lead to requirements for greater communication, coordination, and cooperation among mission schedulers. These schedulers must jointly allocate scarce shared resources among the various operational and mission oriented activities while adhering to all constraints. This scheduling environment is complicated by such factors as the presence of varying perspectives and conflicting objectives among the schedulers, the need for different schedulers to work in parallel, and limited communication among schedulers. Smooth interaction among schedulers requires the use of protocols that govern such issues as resource sharing, authority to update the schedule, and communication of updates. This paper addresses the development and characteristics of such protocols and their use in a distributed scheduling environment that incorporates computer-aided scheduling tools. An example problem is drawn from the domain of Space Shuttle mission planning.

Richards, Stephen F.↗

NASA NTRS1993

Protocols for distributive scheduling

Richards, Stephen F.↗

NASA NTRS1994

Constraint-based integration of planning and scheduling for space-based observatory management

Progress toward the development of effective, practical solutions to space-based observatory scheduling problems within the HSTS scheduling framework is reported. HSTS was developed and originally applied in the context of the Hubble Space Telescope (HST) short-term observation scheduling problem. The work was motivated by the limitations of the current solution and, more generally, by the insufficiency of classical planning and scheduling approaches in this problem context. HSTS has subsequently been used to develop improved heuristic solution techniques in related scheduling domains and is currently being applied to develop a scheduling tool for the upcoming Submillimeter Wave Astronomy Satellite (SWAS) mission. The salient architectural characteristics of HSTS and their relationship to previous scheduling and AI planning research are summarized. Then, some key problem decomposition techniques underlying the integrated planning and scheduling approach to the HST problem are described; research results indicate that these techniques provide leverage in solving space-based observatory scheduling problems. Finally, more recently developed constraint-posting scheduling procedures and the current SWAS application focus are summarized.

Muscettola, Nicola↗

NASA NTRS1994

A format for the interchange of scheduling models

In recent years a variety of space-activity schedulers have been developed within the aerospace community. Space-activity schedulers are characterized by their need to handle large numbers of activities which are time-window constrained and make high demands on many scarce resources, but are minimally constrained by predecessor/successor requirements or critical paths. Two needs to exchange data between these schedulers have materialized. First, there is significant interest in comparing and evaluating the different scheduling engines to ensure that the best technology is applied to each scheduling endeavor. Second, there is a developing requirement to divide a single scheduling task among different sites, each using a different scheduler. In fact, the scheduling task for International Space Station Alpha (ISSA) will be distributed among NASA centers and among the international partners. The format used to interchange scheduling data for ISSA will likely use a growth version of the format discussed in this paper. The model interchange format (or MIF, pronounced as one syllable) discussed in this paper is a robust solution to the need to interchange scheduling requirements for space activities. It is highly extensible, human-readable, and can be generated or edited with common text editors. It also serves well the need to support a 'benchmark' data case which can be delivered on any computer platform.

Jaap, John P.↗

NASA NTRS1998

A Photo Album of Earth Scheduling Landsat 7 Mission Daily Activities

Landsat7 is a member of a new generation of Earth observation satellites. Landsat7 will carry on the mission of the aging Landsat 5 spacecraft by acquiring high resolution, multi-spectral images of the Earth surface for strategic, environmental, commercial, agricultural and civil analysis and research. One of the primary mission goals of Landsat7 is to accumulate and seasonally refresh an archive of global images with full coverage of Earth's landmass, less the central portion of Antarctica. This archive will enable further research into seasonal, annual and long-range trending analysis in such diverse research areas as crop yields, deforestation, population growth, and pollution control, to name just a few. A secondary goal of Landsat7 is to fulfill imaging requests from our international partners in the mission. Landsat7 will transmit raw image data from the spacecraft to 25 ground stations in 20 subscribing countries. Whereas earlier Landsat missions were scheduled manually (as are the majority of current low-orbit satellite missions), the task of manually planning and scheduling Landsat7 mission activities would be overwhelmingly complex when considering the large volume of image requests, the limited resources available, spacecraft instrument limitations, and the limited ground image processing capacity, not to mention avoidance of foul weather systems. The Landsat7 Mission Operation Center (MOC) includes an image scheduler subsystem that is designed to automate the majority of mission planning and scheduling, including selection of the images to be acquired, managing the recording and playback of the images by the spacecraft, scheduling ground station contacts for downlink of images, and generating the spacecraft commands for controlling the imager, recorder, transmitters and antennas. The image scheduler subsystem autonomously generates 90% of the spacecraft commanding with minimal manual intervention. The image scheduler produces a conflict-free schedule for acquiring images of the "best" 250 scenes daily for refreshing the global archive. It then equitably distributes the remaining resources for acquiring up to 430 scenes to satisfy requests by international subscribers. The image scheduler selects candidate scenes based on priority and age of the requests, and predicted cloud cover and sun angle at each scene. It also selects these scenes to avoid instrument constraint violations and maximizes efficiency of resource usage by encouraging acquisition of scenes in clusters. Of particular interest to the mission planners, it produces the resulting schedule in a reasonable time, typically within 15 minutes.

Potter, William↗

NASA NTRS1994

Managing Action Duration Uncertainty with Just-In-Case Scheduling

Some applications involve automatic generation and execution of schedules that contain actions with uncertain durations. Such uncertainty can cause schedules to break during execution. This paper presents a technique, called Just-In-Case scheduling or JIC, for building robust schedules that tend not to break. The technique implements the common sense idea of being prepared for likely errors, just in case they should occur. The JIC algorithm analyzes a given schedule, determines where it is likely to break, reinvokes the scheduler to generate a contingent schedule for each highly probable break case, and produces a "multiply contingent" schedule. The technique was developed for a real telescope scheduling problem, and the paper presents empirical results showing that Just-In-Case scheduling performs extremely well for this problem.

Bresina, John↗

NASA NTRS2000

Putting ROSE to Work: A Proposed Application of a Request-Oriented Scheduling Engine for Space Station Operations

Scheduling engines are found at the core of software systems that plan and schedule activities and resources. A Request-Oriented Scheduling Engine (ROSE) is one that processes a single request (adding a task to a timeline) and then waits for another request. For the International Space Station, a robust ROSE-based system would support multiple, simultaneous users, each formulating requests (defining scheduling requirements), submitting these requests via the internet to a single scheduling engine operating on a single timeline, and immediately viewing the resulting timeline. ROSE is significantly different from the engine currently used to schedule Space Station operations. The current engine supports essentially one person at a time, with a pre-defined set of requirements from many payloads, working in either a "batch" scheduling mode or an interactive/manual scheduling mode. A planning and scheduling process that takes advantage of the features of ROSE could produce greater customer satisfaction at reduced cost and reduced flow time. This paper describes a possible ROSE-based scheduling process and identifies the additional software component required to support it. Resulting changes to the management and control of the process are also discussed.

Jaap, John↗

NASA NTRS2004

Enhanced Software for Scheduling Space-Shuttle Processing

The Ground Processing Scheduling System (GPSS) computer program is used to develop streamlined schedules for the inspection, repair, and refurbishment of space shuttles at Kennedy Space Center. A scheduling computer program is needed because space-shuttle processing is complex and it is frequently necessary to modify schedules to accommodate unanticipated events, unavailability of specialized personnel, unexpected delays, and the need to repair newly discovered defects. GPSS implements constraint-based scheduling algorithms and provides an interactive scheduling software environment. In response to inputs, GPSS can respond with schedules that are optimized in the sense that they contain minimal violations of constraints while supporting the most effective and efficient utilization of space-shuttle ground processing resources. The present version of GPSS is a product of re-engineering of a prototype version. While the prototype version proved to be valuable and versatile as a scheduling software tool during the first five years, it was characterized by design and algorithmic deficiencies that affected schedule revisions, query capability, task movement, report capability, and overall interface complexity. In addition, the lack of documentation gave rise to difficulties in maintenance and limited both enhanceability and portability. The goal of the GPSS re-engineering project was to upgrade the prototype into a flexible system that supports multiple- flow, multiple-site scheduling and that retains the strengths of the prototype while incorporating improvements in maintainability, enhanceability, and portability.

Barretta, Joseph A.↗

NASA NTRS2013

Automated Long - Term Scheduling for the SOFIA Airborne Observatory

The NASA Stratospheric Observatory for Infrared Astronomy (SOFIA) is a joint US/German project to develop and operate a gyro-stabilized 2.5-meter telescope in a Boeing 747SP. SOFIA's first science observations were made in December 2010. During 2011, SOFIA accomplished 30 flights in the "Early Science" program as well as a deployment to Germany. The new observing period, known as Cycle 1, is scheduled to begin in 2012. It includes 46 science flights grouped in four multi-week observing campaigns spread through a 13-month span. Automation of the flight scheduling process offers a major challenge to the SOFIA mission operations. First because it is needed to mitigate its relatively high cost per unit observing time compared to space-borne missions. Second because automated scheduling techniques available for ground-based and space-based telescopes are inappropriate for an airborne observatory. Although serious attempts have been made in the past to solve part of the problem, until recently mission operations staff was still manually scheduling flights. We present in this paper a new automated solution for generating SOFIA long-term schedules that will be used in operations from the Cycle 1 observing period. We describe the constraints that should be satisfied to solve the SOFIA scheduling problem in the context of real operations. We establish key formulas required to efficiently calculate the aircraft course over ground when evaluating flight schedules. We describe the foundations of the SOFIA long-term scheduler, the constraint representation, and the random search based algorithm that generates observation and instrument schedules. Finally, we report on how the new long-term scheduler has been used in operations to date.

Civeit, Thomas↗

NASA NTRS2021

A Simulation Study of Bin-and-Sort Policies in a Distributed System for Flights Scheduling

This is a report on the results of a simulation experiment conducted on an automated distributed system for scheduling flights in a shared airspace. The scheduling is carried out by computer systems owned by the private operators of the flights, which interface through a centralized independent server. The scheduling requires determining which of the group of flights at hand (whether owned by the same operator or different ones) are to have the advantage of being scheduled before the others. A chosen method of grouping and prioritizing flights must: have the ability to schedule a flight promptly, prevent scheduling conflicts between pairs of overlapping flight routes, and be computationally feasible. Scheduling flights one by one is the First Come First Served policy. Scheduling too many at a time is infeasible. The type of scheduling policy proposed herein, called bin-and-sort, is an attempt to reach a compromise between these two extremes. Bin-and-sort allows for each operator to choose its criteria for prioritizing its flights, and for the centralized component to use different arbitration criteria. A number of these criteria are used in the simulation presented herein. The results of each criterion choice are reported and analyzed.

flight scheduling↗

NASA NTRS2021

A Simulation Study of Bin-and-Sort Policies in a Distributed System for Flights Scheduling

flight scheduling↗