Search NASA⌕ Search

SEARCH · Search NASA

Results for “Heuristic 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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
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 NTRS1989

Focus of attention in an activity-based scheduler

Earlier research in job shop scheduling has demonstrated the advantages of opportunistically combining order-based and resource-based scheduling techniques. An even more flexible approach is investigated where each activity is considered a decision point by itself. Heuristics to opportunistically select the next decision point on which to focus attention (i.e., variable ordering heuristics) and the next decision to be tried at this point (i.e., value ordering heuristics) are described that probabilistically account for both activity precedence and resource requirement interactions. Preliminary experimental results indicate that the variable ordering heuristic greatly increases search efficiency. While least constraining value ordering heuristics have been advocated in the literature, the experimental results suggest that other value ordering heuristics combined with our variable-ordering heuristic can produce much better schedules without significantly increasing search.

Sadeh, Norman↗
DOE OSTI2026

Safe Deep Reinforcement Learning for Robust Frequency and Voltage-Constrained Networked Microgrid Restoration

Here, this paper proposes a safe soft actor-critic reinforcement learning (RL) algorithm–based controller for networked microgrid restoration. It formulates the post black-start start as a finite-horizon constrained Markov decision process. The RL agent co-optimizes real and reactive power set-points for both grid-forming and grid-following inverters under explicit voltage and frequency constraints, while enforcing proper power sharing via the Mean Active Power Sharing Index (MPSI) and Mean Reactive Power Sharing Index (MQSI). Numerical results obtained on the IEEE 123-bus distribution system show that the proposed method achieves a mean voltage build-up time of 0.01 s without breaching the 5% sharing-violation budget under various load scenarios, considering MPSI and MQSI indices. These findings demonstrate that the proposed method yields fast and safe black-start schedules without resorting to heuristic penalties.

Selim, Alaa [Dartmouth College, Hanover, NH (Unite↗
NASA NTRS2016

SARDA Surface Schedulers

Provide an overview of algorithms used in SARDA (Spot and Runway Departure Advisor) HITL (Human-in-the-Loop) simulation for Dallas Fort-Worth International Airport and Charlotte Douglas International airport. Outline a multi-objective dynamic programming (DP) based algorithm that finds the exact solution to the single runway scheduling (SRS) problem, and discuss heuristics to restrict the search space for the DP based algorithm and provide improvements.

runways scheduling↗
NASA NTRS1993

Prediction-based dynamic load-sharing heuristics

The authors present dynamic load-sharing heuristics that use predicted resource requirements of processes to manage workloads in a distributed system. A previously developed statistical pattern-recognition method is employed for resource prediction. While nonprediction-based heuristics depend on a rapidly changing system status, the new heuristics depend on slowly changing program resource usage patterns. Furthermore, prediction-based heuristics can be more effective since they use future requirements rather than just the current system state. Four prediction-based heuristics, two centralized and two distributed, are presented. Using trace driven simulations, they are compared against random scheduling and two effective nonprediction based heuristics. Results show that the prediction-based centralized heuristics achieve up to 30 percent better response times than the nonprediction centralized heuristic, and that the prediction-based distributed heuristics achieve up to 50 percent improvements relative to their nonprediction counterpart.

Goswami, Kumar K.↗
NASA NTRS2021

Scheduling the NASA Deep Space Network with Deep Reinforcement Learning

With three complexes spread evenly across the Earth, NASA’s Deep Space Network (DSN) is the primary means of communications as well as a significant scientific instrument for dozens of active missions around the world. A rapidly rising number of spacecraft and increasingly complex scientific instruments with higher bandwidth requirements have resulted in demand that exceeds the network’s capacity across its 12 antennae. The existing DSN scheduling process operates on a rolling weekly basis and is time-consuming; for a given week, generation of the final baseline schedule of spacecraft tracking passes takes roughly 5 months from the initial requirements submission deadline, with several weeks of peer-to-peer negotiations in between. This paper proposes a deep reinforcement learning (RL) approach to generate candidate DSN schedules from mission requests and spacecraft ephemeris data with demonstrated capability to address real-world operational constraints. A deep RL agent is developed that takes mission requests for a given week as input, and interacts with a DSN scheduling environment to allocate tracks such that its reward signal is maximized. A comparison is made between an agent trained using Proximal Policy Optimization and its random, untrained counterpart. The results represent a proof-of-concept that, given a well-shaped reward signal, a deep RL agent can learn the complex heuristics used by experts to schedule the DSN. A trained agent can potentially be used to generate candidate schedules to bootstrap the scheduling process and thus reduce the turnaround cycle for DSN scheduling.

Wilson, Brian↗
NASA NTRS1987

Scheduling spacecraft operations

A prototype scheduling system named MAESTRO currently under development is being used to explore possible approaches to the spacecraft operations scheduling problem. Results indicate that the appropriate combination of heuristic and other techniques can provide an acceptable solution to the scheduling problem over a wide range of operational scenarios and management approaches. These can include centralized or distributed instrument or systems control, batch or incremental scheduling, scheduling loose resource envelopes or exact profiles, and scheduling with varying degrees of user intervention. Techniques used within MAESTRO to provide this flexibility and power include constraint propagation mechanisms, multiple asynchronous processes, prioritized transaction-based command management, resource opportunity calculation, user-alterable selection and placement mechanisms, and maintenance of multiple schedules and resource profiles. These techniques and scheduling complexities requiring them are discussed.

Britt, Daniel L.↗
NASA NTRS1987

Automated problem scheduling and reduction of synchronization delay effects

It is anticipated that in order to make effective use of many future high performance architectures, programs will have to exhibit at least a medium grained parallelism. A framework is presented for partitioning very sparse triangular systems of linear equations that is designed to produce favorable preformance results in a wide variety of parallel architectures. Efficient methods for solving these systems are of interest because: (1) they provide a useful model problem for use in exploring heuristics for the aggregation, mapping and scheduling of relatively fine grained computations whose data dependencies are specified by directed acrylic graphs, and (2) because such efficient methods can find direct application in the development of parallel algorithms for scientific computation. Simple expressions are derived that describe how to schedule computational work with varying degrees of granularity. The Encore Multimax was used as a hardware simulator to investigate the performance effects of using the partitioning techniques presented in shared memory architectures with varying relative synchronization costs.

Saltz, Joel H.↗
NASA NTRS1987

Scheduling periodic jobs using imprecise results

One approach to avoid timing faults in hard, real-time systems is to make available intermediate, imprecise results produced by real-time processes. When a result of the desired quality cannot be produced in time, an imprecise result of acceptable quality produced before the deadline can be used. The problem of scheduling periodic jobs to meet deadlines on a system that provides the necessary programming language primitives and run-time support for processes to return imprecise results is discussed. Since the scheduler may choose to terminate a task before it is completed, causing it to produce an acceptable but imprecise result, the amount of processor time assigned to any task in a valid schedule can be less than the amount of time required to complete the task. A meaningful formulation of the scheduling problem must take into account the overall quality of the results. Depending on the different types of undesirable effects caused by errors, jobs are classified as type N or type C. For type N jobs, the effects of errors in results produced in different periods are not cumulative. A reasonable performance measure is the average error over all jobs. Three heuristic algorithms that lead to feasible schedules with small average errors are described. For type C jobs, the undesirable effects of errors produced in different periods are cumulative. Schedulability criteria of type C jobs are discussed.

Chung, Jen-Yao↗
NASA NTRS1992

Autonomous power system: Integrated scheduling

The Autonomous Power System (APS) project at NASA Lewis Research Center is designed to demonstrate the abilities of integrated intelligent diagnosis, control and scheduling techniques to space power distribution hardware. 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 determine system configuration, and power hardware (Brassboard) to simulate a space-based power system. Faults can be introduced into the Brassboard and in turn, be diagnosed and corrected by APEX and AIPS. The Autonomous Intelligent Power Scheduler controls the execution of loads attached to the Brassboard. Each load must be executed in a manner that efficiently utilizes available power and satisfies all load, resource, and temporal constraints. In the case of a fault situation on the Brassboard, AIPS dynamically modifies the existing schedule in order to resume efficient operation conditions. A database is kept of the power demand, temporal modifiers, priority of each load, and the power level of each source. AIPS uses a set of heuristic rules to assign start times and resources to each load based on load and resource constraints. A simple improvement engine based upon these heuristics is also available to improve the schedule efficiency. This paper describes the operation of the Autonomous Intelligent Power Scheduler as a single entity, as well as its integration with APEX and the Brassboard. Future plans are discussed for the growth of the Autonomous Intelligent Power Scheduler.

Ringer, Mark J.↗
NASA NTRS1994

A criterion autoscheduler for long range planning

A constraint-based scheduling system called SPIKE is used to create long-term schedules for the Hubble Space Telescope. A meta-level scheduler called the Criterion Autoscheduler for Long range planning (CASL) was created to guide SPIKE's schedule generation according to the agenda of the planning scientists. It is proposed that sufficient flexibility exists in a schedule to allow high level planning heuristics to be applied without adversely affected crucial constraints such as spacecraft efficiency. This hypothesis is supported by test data which is described.

Sponsler, Jeffrey L.↗
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 NTRS1994

DTS: Building custom, intelligent schedulers

DTS is a decision-theoretic scheduler, built on top of a flexible toolkit -- this paper focuses on how the toolkit might be reused in future NASA mission schedulers. The toolkit includes a user-customizable scheduling interface, and a 'Just-For-You' optimization engine. The customizable interface is built on two metaphors: objects and dynamic graphs. Objects help to structure problem specifications and related data, while dynamic graphs simplify the specification of graphical schedule editors (such as Gantt charts). The interface can be used with any 'back-end' scheduler, through dynamically-loaded code, interprocess communication, or a shared database. The 'Just-For-You' optimization engine includes user-specific utility functions, automatically compiled heuristic evaluations, and a postprocessing facility for enforcing scheduling policies. The optimization engine is based on BPS, the Bayesian Problem-Solver (1,2), which introduced a similar approach to solving single-agent and adversarial graph search problems.

Hansson, Othar↗
NASA NTRS1991

The min-conflicts heuristic: Experimental and theoretical results

This paper describes a simple heuristic method for solving large-scale constraint satisfaction and scheduling problems. Given an initial assignment for the variables in a problem, the method operates by searching through the space of possible repairs. The search is guided by an ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. We demonstrate empirically that the method performs orders of magnitude better than traditional backtracking techniques on certain standard problems. For example, the one million queens problem can be solved rapidly using our approach. We also describe practical scheduling applications where the method has been successfully applied. A theoretical analysis is presented to explain why the method works so well on certain types of problems and to predict when it is likely to be most effective.

Minton, Steven↗
NASA NTRS1992

Experiments with a decision-theoretic scheduler

This paper describes DTS, a decision-theoretic scheduler designed to employ state-of-the-art probabilistic inference technology to speed the search for efficient solutions to constraint-satisfaction problems. Our approach involves assessing the performance of heuristic control strategies that are normally hard-coded into scheduling systems, and using probabilistic inference to aggregate this information in light of features of a given problem. BPS, the Bayesian Problem-Solver, introduced a similar approach to solving single-agent and adversarial graph search problems, yielding orders-of-magnitude improvement over traditional techniques. Initial efforts suggest that similar improvements will be realizable when applied to typical constraint-satisfaction scheduling problems.

Hansson, Othar↗
NASA NTRS1990

Intelligent perturbation algorithms for space scheduling optimization

The optimization of space operations is examined in the light of optimization heuristics for computer algorithms and iterative search techniques. Specific attention is given to the search concepts known collectively as intelligent perturbation algorithms (IPAs) and their application to crew/resource allocation problems. IPAs iteratively examine successive schedules which become progressively more efficient, and the characteristics of good perturbation operators are listed. IPAs can be applied to aerospace systems to efficiently utilize crews, payloads, and resources in the context of systems such as Space-Station scheduling. A program is presented called the MFIVE Space Station Scheduling Worksheet which generates task assignments and resource usage structures. The IPAs can be used to develop flexible manifesting and scheduling for the Industrial Space Facility.

Kurtzman, Clifford R.↗
NASA NTRS1993

Decision-theoretic control of EUVE telescope scheduling

This paper describes a decision theoretic scheduler (DTS) designed to employ state-of-the-art probabilistic inference technology to speed the search for efficient solutions to constraint-satisfaction problems. Our approach involves assessing the performance of heuristic control strategies that are normally hard-coded into scheduling systems and using probabilistic inference to aggregate this information in light of the features of a given problem. The Bayesian Problem-Solver (BPS) introduced a similar approach to solving single agent and adversarial graph search patterns yielding orders-of-magnitude improvement over traditional techniques. Initial efforts suggest that similar improvements will be realizable when applied to typical constraint-satisfaction scheduling problems.

Hansson, Othar↗
NASA NTRS2019

Modeling Deicing Operations in Departure Scheduling Using Fast Time Simulation

In winter snow conditions, aircraft need inspection for deicing service before takeoff. Deicing service is a procedure to remove frost, ice, slush, or snow from aircraft for safe operation. Deicing operations vary by airport in many ways. Some airports have designated deicing zones, whereas some use a closed runway or terminal area to perform the procedure. Nonetheless, deicing operations add extra workloads to controllers, and cause increased taxi traffic on the ground. NASA and Korea Aerospace Research Institute (KARI) have been collaborating to model deicing operations at Incheon International Airport (ICN). This paper describes the deicing model and the study of deicing operations in departure scheduling using fast time simulations. The deicing model uses a heuristic algorithm for deicing zone assignment. In the fast time simulations, the model uses probability distributions derived from actual operation data to model deicing request and deicing zone time. It is envisioned that such a deicing model can be useful in airport surface scheduling to provide decision support and improve traffic management performance in winter snow operations.

modeling and simulation↗