SEARCH · Engineering Papers
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.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
Cost estimates and funding schedules are presented for a given configuration and costing ground rules. Cost methodology is described and the cost evolution from a baseline configuration to a selected configuration is given, emphasizing cases in which cost was a design driver. Programmatic cost avoidance techniques are discussed.
Data and analyses related to a variety of algorithms for solving typical large-scale scheduling and resource allocation problems are presented. The capabilities and deficiencies of various alternative problem solving strategies are discussed from the viewpoint of computer system design.
Explore the source record for details and available documents.
This paper assesses the resilience of scheduled Performance-Based Navigation (PBN) arrival operations. Resilience is defined as an ability to return to nominal operations following a schedule perturbation. Results from a Human-in-the- Loop (HITL) experiment that included off-nominal events to perturb the schedule are described. The schedule comes from a precision trajectory-based arrival manager. The experiment collected data regarding the response to perturbed schedules in three conditions, where: 1) a disturbance rejection algorithm made schedule adjustments automatically, 2) a Traffic Management Coordinator (TMC) participant made schedule adjustments manually, or 3) no schedule adjustments were made. Analyses showed that the simulation’s scheduled PBN operations have inherent resilience, recovering from more than half of the perturbed schedules even with no schedule adjustments. Resilience to the same off-nominal events improved with schedule adjustments; an increased proportion of perturbed schedules recovered within the length of operation run, and the average duration of the schedule’s perturbed state decreased. Compared to the manual schedule adjustments condition, a greater number of schedule adjustments occurred for the same off-nominal events in the automated condition. However, perturbed schedules were recovered more frequently and perturbations were less severe in the automated condition. Subjective and objective workload in the manual and the automated schedule adjustment conditions were similar to the no schedule adjustment condition.
Understanding the reasoning behind the behavior of an auto- mated scheduling system is essential to ensure that it will be trusted and consequently used to its full capabilities in critical applications. In cases where a scheduler schedules activities in an invalid location, it is usually easy for the user to infer the missing constraint by inspecting the schedule with the in- valid activity to determine the missing constraint. If a sched- uler fails to schedule activities because constraints could not be satisfied, determining the cause can be more challenging. In such cases it is important to understand which constraints caused the activities to fail to be scheduled and how to al- ter constraints to achieve the desired schedule. In this pa- per, we describe such a scheduling system for NASA’s Mars 2020 Perseverance Rover, as well as Crosscheck, an explain- able scheduling tool that explains the scheduler behavior. The scheduling system and Crosscheck are the baseline for oper- ational use to schedule activities for the Mars 2020 rover. As we describe, the scheduler generates a schedule given a set of activities and their constraints and Crosscheck: (1) provides a visual representation of the generated schedule; (2) analyzes and explains why activities failed to schedule given the con- straints provided; and (3) provides guidance on potential con- straint relaxations to enable the activities to schedule in future scheduler runs.
The Night Projects Directorate at NASA's Marshall Space Flight Center is developing a new planning and scheduling environment and a new scheduling algorithm to enable a paradigm shift in planning and scheduling concepts. Over the past 33 years Marshall has developed and evolved a paradigm for generating payload timelines for Skylab, Spacelab, various other Shuttle payloads, and the International Space Station. The current paradigm starts by collecting the requirements, called ?ask models," from the scientists and technologists for the tasks that are to be scheduled. Because of shortcomings in the current modeling schema, some requirements are entered as notes. Next, a cadre with knowledge of vehicle and hardware modifies these models to encompass and be compatible with the hardware model; again, notes are added when the modeling schema does not provide a better way to represent the requirements. Finally, the models are modified to be compatible with the scheduling engine. Then the models are submitted to the scheduling engine for automatic scheduling or, when requirements are expressed in notes, the timeline is built manually. A future paradigm would provide a scheduling engine that accepts separate science models and hardware models. The modeling schema would have the capability to represent all the requirements without resorting to notes. Furthermore, the scheduling engine would not require that the models be modified to account for the capabilities (limitations) of the scheduling engine. The enabling technology under development at Marshall has three major components: (1) A new modeling schema allows expressing all the requirements of the tasks without resorting to notes or awkward contrivances. The chosen modeling schema is both maximally expressive and easy to use. It utilizes graphical methods to show hierarchies of task constraints and networks of temporal relationships. (2) A new scheduling algorithm automatically schedules the models without the intervention of a scheduling expert. The algorithm is tuned for the constraint hierarchies and the complex temporal relationships provided by the modeling schema. It has an extensive search algorithm that can exploit timing flexibilities and constraint and relationship options. (3) An innovative architecture allows multiple remote users to simultaneously model science and technology requirements and other users to model vehicle and hardware characteristics. The architecture allows the remote users to submit scheduling requests directly to the scheduling engine and immediately see the results. These three components are integrated so that science and technology experts with no knowledge of the vehicle or hardware subsystems and no knowledge of the internal workings of the scheduling engine have the ability to build and submit scheduling requests and see the results. The immediate feedback will hone the users' modeling skills and ultimately enable them to produce the desired timeline. This paper summarizes the three components of the enabling technology and describes how this technology would make a new paradigm possible.
A departure metering concept to be demonstrated at Charlotte Douglas International Airport (CLT) will integrate strategic and tactical surface scheduling components to enable the respective collaborative decision making and improved efficiency benefits these two methods of scheduling provide. This study analyzes the effect of tactical scheduling on strategic scheduler predictability. Strategic queue predictions and target gate pushback times to achieve a desired queue length are compared between fast time simulations of CLT surface operations with and without tactical scheduling. The use of variable departure rates as a strategic scheduler input was shown to substantially improve queue predictions over static departure rates. With target queue length calibration, the strategic scheduler can be tuned to produce average delays within one minute of the tactical scheduler. However, root mean square differences between strategic and tactical delays were between 12 and 15 minutes due to the different methods the strategic and tactical schedulers use to predict takeoff times and generate gate pushback clearances. This demonstrates how difficult it is for the strategic scheduler to predict tactical scheduler assigned gate delays on an individual flight basis as the tactical scheduler adjusts departure sequence to accommodate arrival interactions. Strategic/tactical scheduler compatibility may be improved by providing more arrival information to the strategic scheduler and stabilizing tactical scheduler changes to runway sequence in response to arrivals.
The Flight Projects Directorate at NASA's Marshall Space Flight Center is developing a new planning and scheduling environment and a new scheduling algorithm to enable a paradigm shift in planning and scheduling concepts. Over the past 33 years Marshall has developed and evolved a paradigm for generating payload timelines for Skylab, Spacelab, various other Shuttle payloads, and the International Space Station. The current paradigm starts by collecting the requirements, called "tasks models," from the scientists and technologists for the tasks that they want to be done. Because of shortcomings in the current modeling schema, some requirements are entered as notes. Next a cadre with knowledge of vehicle and hardware modifies these models to encompass and be compatible with the hardware model; again, notes are added when the modeling schema does not provide a better way to represent the requirements. Finally, another cadre further modifies the models to be compatible with the scheduling engine. This last cadre also submits the models to the scheduling engine or builds the timeline manually to accommodate requirements that are expressed in notes. A future paradigm would provide a scheduling engine that accepts separate science models and hardware models. The modeling schema would have the capability to represent all the requirements without resorting to notes. Furthermore, the scheduling engine would not require that the models be modified to account for the capabilities (limitations) of the scheduling engine. The enabling technology under development at Marshall has three major components. (1) A new modeling schema allows expressing all the requirements of the tasks without resorting to notes or awkward contrivances. The chosen modeling schema is both maximally expressive and easy to use. It utilizes graphics methods to show hierarchies of task constraints and networks of temporal relationships. (2) A new scheduling algorithm automatically schedules the models without the intervention of a scheduling expert. The algorithm is tuned for the constraint hierarchies and the complex temporal relationships provided by the modeling schema. It has an extensive search algorithm which can exploit timing flexibilities and constraint and relationship options. (3) A web-based architecture allows multiple remote users to simultaneously model science and technology requirements and other users to model vehicle and hardware characteristics. The architecture allows the users to submit scheduling requests directly to the scheduling engine and immediately see the results. These three components are integrated so that science and technology experts with no knowledge of the vehicle or hardware subsystems and no knowledge of the internal workings of the scheduling engine have the ability to build and submit scheduling requests and see the results. The immediate feedback will hone the users' modeling skills and ultimately enable them to produce the desired timeline. This paper summarizes the three components of the enabling technology and describes how this technology would make a new paradigm possible.
Weather can cause flight diversions, passenger delays, additional fuel consumption and schedule disruptions at any high volume airport. The impacts are particularly acute at the Ted Stevens Anchorage International Airport in Anchorage, Alaska due to its importance as a major international portal. To minimize the impacts due to weather, a multi-stage scheduling process is employed that is iteratively executed, as updated aircraft demand and/or airport capacity data become available. The strategic scheduling algorithm assigns speed adjustments for flights that originate outside of Anchorage Center to achieve the proper demand and capacity balance. Similarly, an internal departure-scheduling algorithm assigns ground holds for pre-departure flights that originate from within Anchorage Center. Tactical flight controls in the form of airborne holding are employed to reactively account for system uncertainties. Real-world scenarios that were derived from the January 16, 2012 Anchorage visibility observations and the January 12, 2012 Anchorage arrival schedule were used to test the initial implementation of the scheduling algorithm in fast-time simulation experiments. Although over 90% of the flights in the scenarios arrived at Anchorage without requiring any delay, pre-departure scheduling was the dominant form of control for Anchorage arrivals. Additionally, tactical scheduling was used extensively in conjunction with the pre-departure scheduling to reactively compensate for uncertainties in the arrival demand. For long-haul flights, the strategic scheduling algorithm performed best when the scheduling horizon was greater than 1,000 nmi. With these long scheduling horizons, it was possible to absorb between ten and 12 minutes of delay through speed control alone. Unfortunately, the use of tactical scheduling, which resulted in airborne holding, was found to increase as the strategic scheduling horizon increased because of the additional uncertainty in the arrival times of the aircraft. Findings from these initial experiments indicate that it is possible to schedule arrivals into Anchorage with minimal delays under low-visibility conditions with less disruption to high-cost, international flights.
Objective: Investigate the effects on human performance as a function of scheduling task complexity for novice schedulers creating spaceflight timelines. Background: Future astronauts will be expected to self-schedule, yet will not be experts in creating timelines that meet complex constraints inherent to spaceflight operations. Method: Conducted a within-subject experiment to measure scheduling efficiency, effectiveness, workload and situation awareness while varying scheduling task complexity factors, namely number of constraints and types of constraints. Results: Fifteen participants completed various scheduling problems. Performance differences were identified between the independent variables. There was a main effect due to the number of constraints and type of constraint for efficiency, effectiveness, and workload. Significant interactions were observed in situation awareness and workload for certain types of constraints. Results also suggest that a lower number of constraints may be manageable by novice schedulers when compared to scheduling activities without constraints. Conclusion: Results suggest that novice schedulers performance decreases with high number of constraints and future scheduling aids may have to be targeted to type of constraint. Application: Knowledge on the effect of scheduling task complexity will help design scheduling systems that will enable self-scheduling for future astronauts. It will also inform other domains that conduct complex scheduling, such as nursing and manufacturing.
The Platform Management System was established to coordinate the operation of platform systems and instruments. The management functions are split between ground and space components. Since platforms are to be out of contact with the ground more than the manned base, the on-board functions are required to be more autonomous than those of the manned base. Under this concept, automated replanning and rescheduling, including on-board real-time schedule maintenance and schedule repair, are required to effectively and efficiently meet Space Station Freedom mission goals. In a FY88 study, we developed several promising alternatives for automated platform planning and scheduling. We recommended both a specific alternative and a phased approach to automated platform resource scheduling. Our recommended alternative was based upon use of exactly the same scheduling engine in both ground and space components of the platform management system. Our phased approach recommendation was based upon evolutionary development of the platform. In the past year, we developed platform scheduler requirements and implemented a rapid prototype of a baseline platform scheduler. Presently we are rehosting this platform scheduler rapid prototype and integrating the scheduler prototype into two Goddard Space Flight Center testbeds, as the ground scheduler in the Scheduling Concepts, Architectures, and Networks Testbed and as the on-board scheduler in the Platform Management System Testbed. Using these testbeds, we will investigate rescheduling issues, evaluate operational performance and enhance the platform scheduler prototype to demonstrate our evolutionary approach to automated platform scheduling. The work described in this paper was performed prior to Space Station Freedom rephasing, transfer of platform responsibility to Code E, and other recently discussed changes. We neither speculate on these changes nor attempt to predict the impact of the final decisions. As a consequence some of our work and results may be outdated when this paper is published.
NASA has recently deployed a new mid-range scheduling system for the antennas of the Deep Space Network (DSN), called Service Scheduling Software, or S(sup 3). This system is architected as a modern web application containing a central scheduling database integrated with a collaborative environment, exploiting the same technologies as social web applications but applied to a space operations context. This is highly relevant to the DSN domain since the network schedule of operations is developed in a peer-to-peer negotiation process among all users who utilize the DSN (representing 37 projects including international partners and ground-based science and calibration users). The initial implementation of S(sup 3) is complete and the system has been operational since July 2011. S(sup 3) has been used for negotiating schedules since April 2011, including the baseline schedules for three launching missions in late 2011. S(sup 3) supports a distributed scheduling model, in which changes can potentially be made by multiple users based on multiple schedule "workspaces" or versions of the schedule. This has led to several challenges in the design of the scheduling database, and of a change proposal workflow that allows users to concur with or to reject proposed schedule changes, and then counter-propose with alternative or additional suggested changes. This paper describes some key aspects of the S(sup 3) system and lessons learned from its operational deployment to date, focusing on the challenges of multi-user collaborative scheduling in a practical and mission-critical setting. We will also describe the ongoing project to extend S(sup 3) to encompass long-range planning, downtime analysis, and forecasting, as the next step in developing a single integrated DSN scheduling tool suite to cover all time ranges.
Previous work introduced the concept of using tactical shortcut options to improve schedule conformance in terminal airspace. When a scheduling point is congested, aircraft are scheduled to longer nominal paths, holding shortcut path options in reserve for tactical use if an aircraft is late, thereby improving the schedule conformance, reducing the required scheduling buffer, and increasing throughput. When the scheduling point is less congested, aircraft may be scheduled to the shorter path with original larger scheduling buffers. Previous work focused on a single generic merge point serving aircraft with uniform arrival precision. This paper extends the previous concept to enhance the performance of time-based arrival management and consider mixed aircraft performance. Aircraft equipped to achieve a high degree of schedule conformance may be scheduled to the shorter path under the same conditions that a less equipped aircraft would be scheduled to the longer path, giving the equipped aircraft an advantage that can be seamlessly integrated into the scheduler. The arrival scheduler with shortcut path options for mixed aircraft performance is applied to a model of first-come first-served terminal metering at Los Angeles International Airport. Whereas clear system benefits were found for tactical shortcut routing and higher percentages of equipped aircraft, very little advantage could be seen for equipped over unequipped aircraft that could be used to incentivize early equipage.
NASA’s future long-duration exploration missions (LDEMs) will encounter increasing communication transmission delays as they move farther from Earth-based ground stations. This necessitates a new approach, as crews can no longer rely on real-time support from ground planners and must self-schedule their own operational timelines effectively and efficiently. To enable this transition, our team has developed Playbook, a mission planning and scheduling tool. Our research focuses on quantifying scheduling performance using Playbook to inform the design and development of future features to streamline timeline creation. We also aim to propose standards and guidelines for autonomous crews in LDEMs. In the past year, we have focused on further validating and quantifying the effects of countermeasure aids on self-scheduling performance. There are two software aids in Playbook (self-scheduling platform): Suggested Fixes, which propose an edit to resolve violations within a timeline, and No-Go Zones, which highlight where activities should not be scheduled on a timeline. We have made significant progress in HERA Campaign 7 (C7) data collection, increasing the number of days crew must self-schedule from 4 to 8. As a result, almost 20% of the mission is self-scheduled by the analog astronauts. We have also started data collection on a controlled lab experiment designed to quantify performance effects due to the countermeasures. We expect to present the preliminary results from both efforts. Finally, we have conducted an exploratory analysis of NASA’s HERA Campaign 6 (C6), investigating the mission-level impacts of self-scheduling. We derived basic patterns and descriptive statistics to better characterize crew autonomy through self-scheduling. We also assessed if there are any individual indicators of preference for self-scheduling, such as experience or predilection for autonomy. Preliminary analysis indicates that the HERA C6 crew self-scheduled one out of four flexible activities, indicating unprompted adoption of self-scheduling as a concept of operation for crew autonomy.
Improving the performance of job executions is an important goal of HPC batch job schedulers, such as minimizing job waiting time, slowdown, or completion time. Such a goal is often accomplished using carefully designed heuristics based on job features, such as job size and job duration. However, these heuristics overlook important runtime factors (e.g., cluster availability and waiting job patterns), which may vary across time and make a previously sound scheduling decision not hold any longer. In this study, we propose a new approach to incorporate runtime factors into batch job scheduling for better job execution performance. The key idea is to add a scheduling inspector on top of the base job scheduler to scrutinize its scheduling decisions. The inspector will take the runtime factors into consideration and accordingly determine the fitness of the scheduled job. It then either accepts the scheduled job or rejects it and asks the base schedulers to try again later. We realize such an inspector, namely SchedInspector, by leveraging the intelligence of reinforcement learning. Through extensive experiments, we show SchedInspector can intelligently integrate the runtime factors into various batch job scheduling policies, including the state-of-the-art one, to gain better job execution performance, such as smaller average bounded job slowdown (up to 69% better) or average job waiting time (up to 52% better), across various real-world workloads. We also show that although rejecting scheduling decisions may leave the resources idle hence affect the system utilization, SchedInspector is able to achieve the job execution performance improvement with marginal impact on the system utilization (typically less than 1%). We consider one key advantage of SchedInspector is it automatically learns to work with and improve existing job scheduling policies without changing them, which makes it promising to serve as a generic enhancer for various batch job scheduling policies.
In this article, we present an approach to systematically examine the schedulability of distributed storage systems, identify their scheduling problems, and enable effective scheduling in these systems. We use Thread Architecture Models (TAMs) to describe the behavior and interactions of different threads in a system, and show both how to construct TAMs for existing systems and utilize TAMs to identify critical scheduling problems. We specify three schedulability conditions that a schedulable TAM should satisfy: completeness, local enforceability, and independence; meeting these conditions enables a system to easily support different scheduling policies. We identify five common problems that prevent a system from satisfying the schedulability conditions, and show that these problems arise in existing systems such as HBase, Cassandra, MongoDB, and Riak, making it difficult or impossible to realize various scheduling disciplines. We demonstrate how to address these schedulability problems using both direct and indirect solutions, with different trade-offs. To show how to apply our approach to enable scheduling in realistic systems, we develop Tamed-HBase and Muzzled-HBase, sets of modifications to HBase that can realize the desired scheduling disciplines, including fairness and priority scheduling, even when presented with challenging workloads.
The Autonomous Power System (APS) project at NASA LeRC is designed to demonstrate the applications of integrated intelligent diagnosis, control, and scheduling techniques to space power distribution systems. The project consists of three elements: the Autonomous Power Expert System (APEX) for Fault Diagnosis, Isolation, and Recovery (FDIR); the Autonomous Intelligent Power Scheduler (AIPS) to efficiently assign activities start times and resources; and power hardware (Brassboard) to emulate a space-based power system. The AIPS scheduler was tested within the APS system. This scheduler is able to efficiently assign available power to the requesting activities and share this information with other software agents within the APS system in order to implement the generated schedule. The AIPS scheduler is also able to cooperatively recover from fault situations by rescheduling the affected loads on the Brassboard in conjunction with the APEX FDIR system. AIPS served as a learning tool and an initial scheduling testbed for the integration of FDIR and automated scheduling systems. Many lessons were learned from the AIPS scheduler and are now being integrated into a new scheduler called SCRAP (Scheduler for Continuous Resource Allocation and Planning). This paper will service three purposes: an overview of the AIPS implementation, lessons learned from the AIPS scheduler, and a brief section on how these lessons are being applied to the new SCRAP scheduler.