Search NASA⌕ Search

SEARCH · Search NASA

Results for “stochastic 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.

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

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2015

A Stochastic Scheduler for Integrated Arrival, Departure and Surface Operations in Los Angeles

In terminal airspace, integrating arrivals, departures, and surface operations with competing resources provides the potential of improving operational efficiency by removing barriers between different operations. This work develops a centralized stochastic scheduler for operations in a terminal area including airborne and surface operations using Non-dominated sorting genetic algorithm and Monte Carlo simulations. The scheduler handles completing resources between different flows, such as runway allocations, runway crossing, departure fixes, and other interaction way points between arrivals and departures. Meanwhile, the scheduler also takes time-varied uncertainties into account when optimizing schedules. The scheduler is run sequentially to identify the best and robust schedule for the next planning window. Resulting schedules decide the routes, speed or delays, and runway assignments with separation constraints at mergingdiverging waypoints in the air and crossing and separations on runways. The Los Angels terminal area was used as an example. The implementation of this stochastic scheduler for integrated arrival, departure and surface operations is completed. And several preliminary runs are finished for over 1,200 flights in LAX in a typical day. Sensitivity studies on various planning window sizes are presented, which shows that trade-off exits between planning window size and achievable minimum delay. Preliminary results on runway usage are also presented in this abstract. Because arrivals on the outer runways have to be followed by crossings on the inner runways, algorithmic runway allocation prefers inner runways for arrivals and outer runways for departures. More results will be presented in the final paper. And current terminal arrival and departure procedures based on first-come-first-serve procedure will also be set up and used as a baseline for comparison.

integrated scheduler↗
NASA NTRS1999

Stochastic Modeling of Airlines' Scheduled Services Revenue

Airlines' revenue generated from scheduled services account for the major share in the total revenue. As such, predicting airlines' total scheduled services revenue is of great importance both to the governments (in case of national airlines) and private airlines. This importance stems from the need to formulate future airline strategic management policies, determine government subsidy levels, and formulate governmental air transportation policies. The prediction of the airlines' total scheduled services revenue is dealt with in this paper. Four key components of airline's scheduled services are considered. These include revenues generated from passenger, cargo, mail, and excess baggage. By addressing the revenue generated from each schedule service separately, air transportation planners and designers are able to enhance their ability to formulate specific strategies for each component. Estimation results clearly indicate that the four stochastic processes (scheduled services components) are represented by different Box-Jenkins ARIMA models. The results demonstrate the appropriateness of the developed models and their ability to provide air transportation planners with future information vital to the planning and design processes.

Hamed, M. M.↗
NASA NTRS1999

Stochastic Modeling of Airlines' Scheduled Services Revenue

Airlines' revenue generated from scheduled services account for the major share in the total revenue. As such, predicting airlines' total scheduled services revenue is of great importance both to the governments (in case of national airlines) and private airlines. This importance stems from the need to formulate future airline strategic management policies, determine government subsidy levels, and formulate governmental air transportation policies. The prediction of the airlines' total scheduled services revenue is dealt with in this paper. Four key components of airline's scheduled services are considered. These include revenues generated from passenger, cargo, mail, and excess baggage. By addressing the revenue generated from each schedule service separately, air transportation planners and designers arc able to enhance their ability to formulate specific strategies for each component. Estimation results clearly indicate that the four stochastic processes (scheduled services components) are represented by different Box-Jenkins ARIMA models. The results demonstrate the appropriateness of the developed models and their ability to provide air transportation planners with future information vital to the planning and design processes.

Hamed, M. M.↗
NASA NTRS2005

A Strategy for Autogeneration of Space Shuttle Ground Processing Simulation Models for Project Makespan Estimations

Space Shuttle Processing is a complicated and highly variable project. The planning and scheduling problem, categorized as a Resource Constrained - Stochastic Project Scheduling Problem (RC-SPSP), has a great deal of variability in the Orbiter Processing Facility (OPF) process flow from one flight to the next. Simulation Modeling is a useful tool in estimation of the makespan of the overall process. However, simulation requires a model to be developed, which itself is a labor and time consuming effort. With such a dynamic process, often the model would potentially be out of synchronization with the actual process, limiting the applicability of the simulation answers in solving the actual estimation problem. Integration of TEAMS model enabling software with our existing schedule program software is the basis of our solution. This paper explains the approach used to develop an auto-generated simulation model from planning and schedule efforts and available data.

Madden, Michael G.↗
NASA NTRS1991

SPIKE: AI scheduling techniques for Hubble Space Telescope

AI (Artificial Intelligence) scheduling techniques for HST are presented in the form of the viewgraphs. The following subject areas are covered: domain; HST constraint timescales; HTS scheduling; SPIKE overview; SPIKE architecture; constraint representation and reasoning; use of suitability functions by scheduling agent; SPIKE screen example; advantages of suitability function framework; limiting search and constraint propagation; scheduling search; stochastic search; repair methods; implementation; and status.

Johnston, Mark D.↗
NASA NTRS2001

Planning and Scheduling for Fleets of Earth Observing Satellites

We address the problem of scheduling observations for a collection of earth observing satellites. This scheduling task is a difficult optimization problem, potentially involving many satellites, hundreds of requests, constraints on when and how to service each request, and resources such as instruments, recording devices, transmitters, and ground stations. High-fidelity models are required to ensure the validity of schedules; at the same time, the size and complexity of the problem makes it unlikely that systematic optimization search methods will be able to solve them in a reasonable time. This paper presents a constraint-based approach to solving the Earth Observing Satellites (EOS) scheduling problem, and proposes a stochastic heuristic search method for solving it.

Frank, Jeremy↗
NASA NTRS2021

Romie: A Domain-Independent Tool for Computer-Aided Robust Operations Management

Romie is a decision support tool based on AI's latest advances in the domain of robust scheduling. Unlike all its predecessors, the tool allows to (i) visually model the operational problem and context entirely (ii) optimize to find near-optimal schedules while taking uncertainty into account and deals with (iii) a combination of various {key performance indicators (KPIs). It comes with a web user interface. Part or all of the modelled activities may be associated to random variables describing their stochastic durations, in order to produce schedules that are robust w.r.t. temporal uncertainty. Hence, depending on the pursued KPIs, the schedules maximize a combination of the following terms: the probability of satisfying the problem constraints, the expected return/efficiency, the expected outcome quality, and even the operators' wellness by minimizing its expected extra-hours. Initially developed for spatial exploration and demonstration in the context of Mars analog missions, this versatile tool is here applied to operations management in both biotechnology manufacturing and robots parametrization in a cave exploration context.

Chien, Steve A.↗
NASA NTRS2011

A Simulation Based Approach to Optimize Berth Throughput Under Uncertainty at Marine Container Terminals

Berth scheduling is a critical function at marine container terminals and determining the best berth schedule depends on several factors including the type and function of the port, size of the port, location, nearby competition, and type of contractual agreement between the terminal and the carriers. In this paper we formulate the berth scheduling problem as a bi-objective mixed-integer problem with the objective to maximize customer satisfaction and reliability of the berth schedule under the assumption that vessel handling times are stochastic parameters following a discrete and known probability distribution. A combination of an exact algorithm, a Genetic Algorithms based heuristic and a simulation post-Pareto analysis is proposed as the solution approach to the resulting problem. Based on a number of experiments it is concluded that the proposed berth scheduling policy outperforms the berth scheduling policy where reliability is not considered.

Golias, Mihalis M.↗
NASA NTRS2003

Scheduling Earth Observing Satellites with Evolutionary Algorithms

We hypothesize that evolutionary algorithms can effectively schedule coordinated fleets of Earth observing satellites. The constraints are complex and the bottlenecks are not well understood, a condition where evolutionary algorithms are often effective. This is, in part, because evolutionary algorithms require only that one can represent solutions, modify solutions, and evaluate solution fitness. To test the hypothesis we have developed a representative set of problems, produced optimization software (in Java) to solve them, and run experiments comparing techniques. This paper presents initial results of a comparison of several evolutionary and other optimization techniques; namely the genetic algorithm, simulated annealing, squeaky wheel optimization, and stochastic hill climbing. We also compare separate satellite vs. integrated scheduling of a two satellite constellation. While the results are not definitive, tests to date suggest that simulated annealing is the best search technique and integrated scheduling is superior.

Globus, Al↗
NASA NTRS2014

Optimizing Integrated Terminal Airspace Operations Under Uncertainty

In the terminal airspace, integrated departures and arrivals have the potential to increase operations efficiency. Recent research has developed geneticalgorithm- based schedulers for integrated arrival and departure operations under uncertainty. This paper presents an alternate method using a machine jobshop scheduling formulation to model the integrated airspace operations. A multistage stochastic programming approach is chosen to formulate the problem and candidate solutions are obtained by solving sample average approximation problems with finite sample size. Because approximate solutions are computed, the proposed algorithm incorporates the computation of statistical bounds to estimate the optimality of the candidate solutions. A proof-ofconcept study is conducted on a baseline implementation of a simple problem considering a fleet mix of 14 aircraft evolving in a model of the Los Angeles terminal airspace. A more thorough statistical analysis is also performed to evaluate the impact of the number of scenarios considered in the sampled problem. To handle extensive sampling computations, a multithreading technique is introduced.

air traffic optimization↗
NASA NTRS2000

Stardust Navigation Covariance Analysis

The Stardust spacecraft was launched on February 7, 1999 aboard a Boeing Delta-II rocket. Mission participants include the National Aeronautics and Space Administration (NASA), the Jet Propulsion Laboratory (JPL), Lockheed Martin Astronautics (LMA) and the University of Washington. The primary objective of the mission is to collect in-situ samples of the coma of comet Wild-2 and return those samples to the Earth for analysis. Mission design and operational navigation for Stardust is performed by the Jet Propulsion Laboratory (JPL). This paper will describe the extensive JPL effort in support of the Stardust pre-launch analysis of the orbit determination component of the mission covariance study. A description of the mission and it's trajectory will be provided first, followed by a discussion of the covariance procedure and models. Predicted accuracy's will be examined as they relate to navigation delivery requirements for specific critical events during the mission. Stardust was launched into a heliocentric trajectory in early 1999. It will perform an Earth Gravity Assist (EGA) on January 15, 2001 to acquire an orbit for the eventual rendezvous with comet Wild-2. The spacecraft will fly through the coma (atmosphere) on the dayside of Wild-2 on January 2, 2004. At that time samples will be obtained using an aerogel collector. After the comet encounter Stardust will return to Earth when the Sample Return Capsule (SRC) will separate and land at the Utah Test Site (UTTR) on January 15, 2006. The spacecraft will however be deflected off into a heliocentric orbit. The mission is divided into three phases for the covariance analysis. They are 1) Launch to EGA, 2) EGA to Wild-2 encounter and 3) Wild-2 encounter to Earth reentry. Orbit determination assumptions for each phase are provided. These include estimated and consider parameters and their associated a-priori uncertainties. Major perturbations to the trajectory include 19 deterministic and statistical maneuvers planned for the mission. The spacecraft is three axis stabilized and has unbalanced thrusters for attitude control. Accelerations due to the attitude control system are treated stochastically. The tracking scenario for the study is patterned after the actual schedule employed during the different phases of the mission. Conventional X-band two-way Doppler and SRA range data was simulated and the standard accuracy for these data types was assumed throughout most of the mission. However, a deweighting scheme was used for the Doppler data during times of low Sun-Earth-Probe angles, especially in the case of the DSM. Optical data is assumed to be available starting at 50 days prior to the comet encounter. The optical data will be used to improve the ephemeris of Wild-2, which is considered crucial to properly target the comet flyby. Results of the covariance analysis are presented for all mission phases. Navigation capability will be discussed in terms of the uncertainty in the encounter B-Plane (B.R and B.T) and linearized time of flight. Delivery errors based on the final maneuver prior to the comet encounter will be presented. The most stringent navigation requirement is for the Earth reentry. The uncertainty in the flight path angle must be less than 0.02 degree (orbit determination and maneuver performance) to assure successful recovery of the SRC. Results presented show that this requirement can be met.

Menon, Premkumar R.↗
NASA NTRS2004

A Comparison of Techniques for Scheduling Earth-Observing Satellites

Scheduling observations by coordinated fleets of Earth Observing Satellites (EOS) involves large search spaces, complex constraints and poorly understood bottlenecks, conditions where evolutionary and related algorithms are often effective. However, there are many such algorithms and the best one to use is not clear. Here we compare multiple variants of the genetic algorithm: stochastic hill climbing, simulated annealing, squeaky wheel optimization and iterated sampling on ten realistically-sized EOS scheduling problems. Schedules are represented by a permutation (non-temperal ordering) of the observation requests. A simple deterministic scheduler assigns times and resources to each observation request in the order indicated by the permutation, discarding those that violate the constraints created by previously scheduled observations. Simulated annealing performs best. Random mutation outperform a more 'intelligent' mutator. Furthermore, the best mutator, by a small margin, was a novel approach we call temperature dependent random sampling that makes large changes in the early stages of evolution and smaller changes towards the end of search.

Globus, Al↗
NASA NTRS2010

Design Considerations for a New Terminal Area Arrival Scheduler

Design of a terminal area arrival scheduler depends on the interrelationship between throughput, delay and controller intervention. The main contribution of this paper is an analysis of the above interdependence for several stochastic behaviors of expected system performance distributions in the aircraft s time of arrival at the meter fix and runway. Results of this analysis serve to guide the scheduler design choices for key control variables. Two types of variables are analyzed, separation buffers and terminal delay margins. The choice for these decision variables was tested using sensitivity analysis. Analysis suggests that it is best to set the separation buffer at the meter fix to its minimum and adjust the runway buffer to attain the desired system performance. Delay margin was found to have the least effect. These results help characterize the variables most influential in the scheduling operations of terminal area arrivals.

Thipphavong, Jane↗
NASA NTRS1990

A coordination theory for intelligent machines

A formal model for the coordination level of intelligent machines is established. The framework of the coordination level investigated consists of one dispatcher and a number of coordinators. The model called coordination structure has been used to describe analytically the information structure and information flow for the coordination activities in the coordination level. Specifically, the coordination structure offers a formalism to (1) describe the task translation of the dispatcher and coordinators; (2) represent the individual process within the dispatcher and coordinators; (3) specify the cooperation and connection among the dispatcher and coordinators; (4) perform the process analysis and evaluation; and (5) provide a control and communication mechanism for the real-time monitor or simulation of the coordination process. A simple procedure for the task scheduling in the coordination structure is presented. The task translation is achieved by a stochastic learning algorithm. The learning process is measured with entropy and its convergence is guaranteed. Finally, a case study of the coordination structure with three coordinators and one dispatcher for a simple intelligent manipulator system illustrates the proposed model and the simulation of the task processes performed on the model verifies the soundness of the theory.

Wang, Fei-Yue↗
NASA NTRS2015

Integration of Uncertain Ramp Area Aircraft Trajectories and Generation of Optimal Taxiway Schedules at Charlotte Douglas (CLT) Airport

The integration of aircraft maneuver characteristics into an optimal taxiway scheduling solution is challenging due to the uncertainties that are intrinsic to ramp area aircraft trajectories. To address the challenge, we build a stochastic model of ramp area aircraft trajectories that is used to generate a probabilistic measure of conflict within the Charlotte Douglas International Airport (CLT) ramp area. Parameters of the conflict distributions are estimated and passed to a Mixed Integer Linear Program that solves for an optimal taxiway schedule constrained to be conflict free in the presence of trajectory uncertainties. Here we extend our previous research by accounting for departing and arriving aircraft whereas our prior formulation only accounted for departing aircraft.

taxiway schedule↗
NASA NTRS1990

An approach to rescheduling activities based on determination of priority and disruptivity

A constraint-based scheduling system called SPIKE is being used to create long term schedules for the Hubble Space Telescope. Feedback for the spacecraft or from other ground support systems may invalidate some scheduling decisions and those activities concerned must be reconsidered. A function rescheduling priority is defined which for a given activity performs a heuristic analysis and produces a relative numerical value which is used to rank all such entities in the order that they should be rescheduled. A function disruptivity is also defined that is used to place a relative numeric value on how much a pre-existing schedule would be changed in order to reschedule an activity. Using these functions, two algorithms (a stochastic neural network approach and an exhaustive search approach) are proposed to find the best place to reschedule an activity. Prototypes were implemented and preliminary testing reveals that the exhaustive technique produces only marginally better results at much greater computational cost.

Sponsler, Jeffrey L.↗