SEARCH · Engineering Papers

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.

SourceResearch connectionFrom yearThrough year

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

At least 91 records · Page 5

All sources NASA NTRS DOE OSTI

NASA NTRS2011

Meta-RaPS Algorithm for the Aerial Refueling Scheduling Problem

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for each fighter aircraft (job) on multiple tankers (machines). ARSP assumes that jobs have different release times and due dates, The total weighted tardiness is used to evaluate schedule's quality. Therefore, ARSP can be modeled as a parallel machine scheduling with release limes and due dates to minimize the total weighted tardiness. Since ARSP is NP-hard, it will be more appropriate to develop a ppro~imate or heuristic algorithm to obtain solutions in reasonable computation limes. In this paper, Meta-Raps-ATC algorithm is implemented to create high quality solutions. Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a recent and promising meta heuristic that is applied by introducing randomness to a construction heuristic. The Apparent Tardiness Rule (ATC), which is a good rule for scheduling problems with tardiness objective, is used to construct initial solutions which are improved by an exchanging operation. Results are presented for generated instances.

Kaplan, Sezgin↗

NASA NTRS1990

Space communications scheduler: A rule-based approach to adaptive deadline scheduling

Job scheduling is a deceptively complex subfield of computer science. The highly combinatorial nature of the problem, which is NP-complete in nearly all cases, requires a scheduling program to intelligently transverse an immense search tree to create the best possible schedule in a minimal amount of time. In addition, the program must continually make adjustments to the initial schedule when faced with last-minute user requests, cancellations, unexpected device failures, quests, cancellations, unexpected device failures, etc. A good scheduler must be quick, flexible, and efficient, even at the expense of generating slightly less-than-optimal schedules. The Space Communication Scheduler (SCS) is an intelligent rule-based scheduling system. SCS is an adaptive deadline scheduler which allocates modular communications resources to meet an ordered set of user-specified job requests on board the NASA Space Station. SCS uses pattern matching techniques to detect potential conflicts through algorithmic and heuristic means. As a result, the system generates and maintains high density schedules without relying heavily on backtracking or blind search techniques. SCS is suitable for many common real-world applications.

Straguzzi, Nicholas↗

DOE OSTI2024

Large-scale simulation-based parametric analysis of an optimal precooling strategy for demand flexibility in a commercial office building

Achieving success with grid-interactive efficient buildings (GEBs) is closely tied to the utilization of flexible loads. A valuable strategy involves the implementation of precooling techniques before high-demand events, such as peak hours, by adjusting zone air temperature setpoints. This leads to a reduction in thermal loads and peak electricity demand during these times, as the building’s thermal mass stores and subsequently releases thermal energy. However, the effectiveness of the pre-cooling optimization is highly contingent on specific conditions such as building thermal properties, weather conditions, utility rate structure, HVAC equipment sizing, etc. Therefore, investigating the impacts of these condition-specific factors is crucial, especially when considering precooling strategies that utilize thermal mass in commercial buildings. In this paper, we first devised a novel heuristic control approach that incorporates parameterized optimal precooling thermostat schedules to enhance demand flexibility in a commercial office building. Subsequently, we conducted a thorough performance evaluation of this control strategy. Here, the optimal thermostat schedule was parameterized using three optimization variables: the precooling start time, the precooling end time, and the precooling temperature setpoint. Utilizing the DOE medium-sized office building as the virtual testbed, we showed that the parameterized schedule effectively approximates model predictive control and requires drastically reduced computational overhead. In addition, we investigated the impact of different influencing factors on the optimal precooling strategy. These factors include building thermal mass, outdoor air conditions, and energy price profiles. Using high-performance computing, we simulated a total of 225 scenarios, consisting of three levels of thermal mass, five typical outdoor air temperature profiles, and fifteen time-of-use price plans. The results demonstrate that optimal thermostat scheduling could save substantial energy cost in medium-sized office buildings with heavy thermal mass but with some energy penalty. Although the potential for cost savings is lower in buildings with low and medium thermal mass, the energy penalty remains consistent in all three thermal mass scenarios. The study also highlights the need to account for zone diversity and recognize that a one-size-fits-all-zone setpoint schedule may not be suitable for all zones and can lead to unnecessary energy wastage. Furthermore, the results highlight that while outdoor air conditions play a role in cost and energy performance, the cooling load exerts a more immediate and substantial influence on cost savings in precooling strategies. Although cost savings are comparable under certain conditions with the same cooling load, observed deviations in energy penalty indicate potential disparities in the efficiency of the HVAC system during the load-shifting process. In addition, the duration of peak pricing and the ratio between peak and off-peak times exhibit clear correlations with cost savings and energy consumption, aligning with intuitive expectations. These findings offer valuable insights for optimizing precooling strategies in office buildings.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

NASA NTRS1994

The Final Approach Spacing Tool

A system for assisting terminal area air traffic controllers in the management and control of arrival traffic, referred to as the Final Approach Spacing Tool (FAST), is being developed at NASA Ames Research Center. In a cooperative program, NASA and FAA have efforts underway to install and evaluate the system at the Dallas/Fort Worth Terminal Radar Approach Control facility. This paper will review the software architecture, the algorithms components, and the human-machine interface. The system is based on continuous updates of a detailed trajectory analyses of all arrival aircraft. FAST interprets the results of these trajectory analyses to build an efficient and procedurally acceptable plan for the arrival traffic that consists of a sequence, schedule, and runway assignment. The system utilizes a heuristically-based conflict resolution algorithm to build a solution trajectory that satisfies the plan, It extracts a series of speed and heading advisories from the solution trajectory to assist the controller in efficiently managing and controlling the arrival traffic down to the runway. The advisories are displayed in a graphical format to the controller. In addition to the radar tracking data, the system also relies on a series of data bases. These data bases contain aircraft performance models, airline preferred operational procedures, airspace structure, air traffic procedural models, and a three dimensional wind model. Field evaluation of FAST is expected to begin in 1994.

Davis, Thomas J.↗

NASA NTRS1991

User interface issues in supporting human-computer integrated scheduling

Explored here is the user interface problems encountered with the Operations Missions Planner (OMP) project at the Jet Propulsion Laboratory (JPL). OMP uses a unique iterative approach to planning that places additional requirements on the user interface, particularly to support system development and maintenance. These requirements are necessary to support the concepts of heuristically controlled search, in-progress assessment, and iterative refinement of the schedule. The techniques used to address the OMP interface needs are given.

Cooper, Lynne P.↗

NASA NTRS1988

Expert system for on-board satellite scheduling and control

An Expert System is described which Rockwell Satellite and Space Electronics Division (S&SED) is developing to dynamically schedule the allocation of on-board satellite resources and activities. This expert system is the Satellite Controller. The resources to be scheduled include power, propellant and recording tape. The activities controlled include scheduling satellite functions such as sensor checkout and operation. The scheduling of these resources and activities is presently a labor intensive and time consuming ground operations task. Developing a schedule requires extensive knowledge of the system and subsystems operations, operational constraints, and satellite design and configuration. This scheduling process requires highly trained experts anywhere from several hours to several weeks to accomplish. The process is done through brute force, that is examining cryptic mnemonic data off line to interpret the health and status of the satellite. Then schedules are formulated either as the result of practical operator experience or heuristics - that is rules of thumb. Orbital operations must become more productive in the future to reduce life cycle costs and decrease dependence on ground control. This reduction is required to increase autonomy and survivability of future systems. The design of future satellites require that the scheduling function be transferred from ground to on board systems.

Barry, John M.↗

DOE OSTI2024

Aerial drone fleet deployment optimization with endogenous battery replacements for direct delivery of time-sensitive products

Aerial drones offer a distinct potential to reduce the delivery time and energy consumption for the delivery of time-sensitive and small products. However, there is still a need in the relevant industry to understand the performance of drone-based delivery under different business needs and drone operating conditions. We studied a drone deployment optimization problem for direct delivery of time-sensitive products with release dates to customers maintaining a specified time window. This paper presents a new mixed-integer programming model, new valid inequalities, a new greedy heuristic algorithm, and a Genetic algorithm to help business owners optimally schedule and route their drone fleet minimizing the required fleet size, the required number of additional batteries, and total energy consumption. A realistic feature of the optimization method is that instead of replacing the drone battery after each return to the depot, it keeps track of the remaining energy in the drone battery and decides on battery replacements accounting for the drone routing and the user-specified minimum required battery energy. Numerical results based on real data from drone flight tests and prepared food delivery industry provide insights into the effect of different practical drone operating parameters on the required fleet size, the required number of battery replacements, and energy consumption. Here, results demonstrate that the proposed heuristic algorithm substantially outperforms the accelerated CPLEX in runtime while sacrificing the solution quality by a small amount. Additionally, results show that using a mixed fleet of hexacopter and quadcopter drones reduces the total energy consumption by 48.52% compared to using a homogeneous fleet of only hexacopters.

Drone energy consumption↗

NASA NTRS1992

Scheduling and rescheduling with iterative repair

This paper describes the GERRY scheduling and rescheduling system being applied to coordinate Space Shuttle Ground Processing. The system uses constraint-based iterative repair, a technique that starts with a complete but possibly flawed schedule and iteratively improves it by using constraint knowledge within repair heuristics. In this paper we explore the tradeoff between the informedness and the computational cost of several repair heuristics. We show empirically that some knowledge can greatly improve the convergence speed of a repair-based system, but that too much knowledge, such as the knowledge embodied within the MIN-CONFLICTS lookahead heuristic, can overwhelm a system and result in degraded performance.

Zweben, Monte↗

NASA NTRS1993

Generation and exploration of aggregation abstractions for scheduling and resource allocation

This paper presents research on the abstraction of computational theories for scheduling and resource allocation. The paper describes both theory and methods for the automated generation of aggregation abstractions and approximations in which detailed resource allocation constraints are replaced by constraints between aggregate demand and capacity. The interaction of aggregation abstraction generation with the more thoroughly investigated abstractions of weakening operator preconditions is briefly discussed. The purpose of generating abstract theories for aggregated demand and resources includes: answering queries about aggregate properties, such as gross feasibility; reducing computational costs by using the solution of aggregate problems to guide the solution of detailed problems; facilitating reformulating theories to approximate problems for which there are efficient problem-solving methods; and reducing computational costs of scheduling by providing more opportunities for variable and value-ordering heuristics to be effective. Experiments are being developed to characterize the properties of aggregations that make them cost effective. Both abstract and concrete theories are represented in a variant of first-order predicate calculus, which is a parameterized multi-sorted logic that facilitates specification of large problems. A particular problem is conceptually represented as a set of ground sentences that is consistent with a quantified theory.

Lowry, Michael R.↗

NASA NTRS1976

Scheduling algorithm for mission planning and logistics evaluation users' guide

The scheduling algorithm for mission planning and logistics evaluation (SAMPLE) program is a mission planning tool composed of three subsystems; the mission payloads subsystem (MPLS), which generates a list of feasible combinations from a payload model for a given calendar year; GREEDY, which is a heuristic model used to find the best traffic model; and the operations simulation and resources scheduling subsystem (OSARS), which determines traffic model feasibility for available resources. The SAMPLE provides the user with options to allow the execution of MPLS, GREEDY, GREEDY-OSARS, or MPLS-GREEDY-OSARS.

Chang, H.↗

NASA NTRS1994

Recursive heuristic classification

The author will describe a new problem-solving approach called recursive heuristic classification, whereby a subproblem of heuristic classification is itself formulated and solved by heuristic classification. This allows the construction of more knowledge-intensive classification programs in a way that yields a clean organization. Further, standard knowledge acquisition and learning techniques for heuristic classification can be used to create, refine, and maintain the knowledge base associated with the recursively called classification expert system. The method of recursive heuristic classification was used in the Minerva blackboard shell for heuristic classification. Minerva recursively calls itself every problem-solving cycle to solve the important blackboard scheduler task, which involves assigning a desirability rating to alternative problem-solving actions. Knowing these ratings is critical to the use of an expert system as a component of a critiquing or apprenticeship tutoring system. One innovation of this research is a method called dynamic heuristic classification, which allows selection among dynamically generated classification categories instead of requiring them to be prenumerated.

Wilkins, David C.↗

NASA NTRS1975

A timeline algorithm for astronomy missions

An algorithm is presented for generating viewing timelines for orbital astronomy missions of the pointing (nonsurvey/scan) type. The algorithm establishes a target sequence from a list of candidate targets in a way which maximizes total viewing time. Two special cases are treated. One concerns dim targets which, due to lighting constraints, are scheduled only during the antipolar portion of each orbit. They normally require long observation times extending over several revolutions. A minimum slew heuristic is employed to select the sequence of dim targets. The other case deals with bright, or short duration, targets, which have less restrictive lighting constraints and are scheduled during the portion of each orbit when dim targets cannot be viewed. Since this process moves much more rapidly than the dim path, an enumeration algorithm is used to select the sequence that maximizes total viewing time.

Moore, J. E.↗

NASA NTRS1988

Contingency rescheduling of spacecraft operations

Spacecraft activity scheduling was a focus of attention in artificial intelligence recently. Several scheduling systems were devised which more-or-less successfully address various aspects of the activity scheduling problem, though most of these are not yet mature, with the notable expection of NASA's ESP. Few current scheduling systems, however, make any attempt to deal fully with the problem of modifying a schedule in near-real-time in the event of contingencies which may arise during schedule execution. These contingencies can include resources becoming unavailable unpredictably, a change in spacecraft conditions or environment, or the need to perform an activity not scheduled. In these cases it becomes necessary to repair an existing schedule, disrupting ongoing operations as little as possible. Normal scheduling is just a part of that which must be accomplished during contingency rescheduling. A prototype system named MAESTRO was developed for spacecraft activity scheduling. MAESTRO is briefly described with a focus on recent work in the area of real-time contingency handling. Included is a discussion of some of the complexities of the scheduling problem and how they affect contingency rescheduling, such as temporal constraints between activities, activities which may be interrupted and continued in any of several ways, and different ways to choose a resource complement which will allow continuation of an activity. Various heuristics used in MAESTRO for contingency rescheduling is discussed, as are operational concerns such as interaction of the scheduler with spacecraft subsystems controllers.

Britt, Daniel L.↗

NASA NTRS2008

Deep Space Network Scheduling Using Multi-Objective Optimization with Uncertainty

We have developed a novel technique to incorporate uncertainty modeling within an evolutionary algorithm approach to multi-objective scheduling, with the goal of identifying a Pareto frontier (tradeoff curve) that recognizes the likelihood of events that can impact the schedule outcome. Our approach is particularly applicable to the generation of multiobjective optimized robust schedules, where objectives are assigned a service level, for example that we require an objective value to be greater than or equal to X with Y% confidence. We have demonstrated that such an approach can, for example, minimize scheduling on less reliable resources, based solely on a resource reliability model and not on any ad hoc heuristics. We have also investigated an alternative method of optimizing for robustness, in which we add to the set of objectives a failure risk objective to minimize. We compare the advantages and disadvantages of these two approaches. Future plans for further developing this technology include its application to space-based observatory scheduling problems.

Johnston, Mark D.↗

DOE OSTI2024

Innovating the next generation of commercial smart building software

Nearly 30% of commercial building energy use is wasted due to equipment faults and HVAC controls problems. The result is increased emissions, compromised comfort and productivity, and less reliable coordination of building power needs with a clean grid. The energy impact alone represents $17 billion in potential savings. Today’s smart building software provides a robust solution to address these operational deficiencies. Energy management and information systems (EMIS) are saving up to 9% on average, with two-year paybacks. They are being incorporated into energy management processes, commissioning services, and utility programs. As effective as they are, two barriers prevent even deeper benefits; limited personnel to fix problems once they are identified, and the expense and time to manually implement changes in control systems. In partnership with the research community, the EMIS industry is developing new capabilities to overcome these barriers. Moving beyond siloed products for either fault detection and diagnostics, or optimal control, these new capabilities empower users to not only automatically identify faults, but also to push corrective action, and control improvements to their buildings. In this paper, several areas for enhancements are documented: ‘one-time’ correction of faults such as setpoints, schedules, and economizer lockouts; short-term active testing for automated proportional integral derivative (PID) loop tuning and functional testing; and continuous supervisory control for demand flexibility and year-round efficiency. Results are presented from a pair of partner implementations out of a dozen providers integrating these enhancements into their products, including field tests from across the country, and insights into operator acceptance and integration into operations and maintenance practices.

Casillas, Armando↗

NASA NTRS1994

High performance techniques for space mission scheduling

In this paper, we summarize current research at Carnegie Mellon University aimed at development of high performance techniques and tools for space mission scheduling. Similar to prior research in opportunistic scheduling, our approach assumes the use of dynamic analysis of problem constraints as a basis for heuristic focusing of problem solving search. This methodology, however, is grounded in representational assumptions more akin to those adopted in recent temporal planning research, and in a problem solving framework which similarly emphasizes constraint posting in an explicitly maintained solution constraint network. These more general representational assumptions are necessitated by the predominance of state-dependent constraints in space mission planning domains, and the consequent need to integrate resource allocation and plan synthesis processes. First, we review the space mission problems we have considered to date and indicate the results obtained in these application domains. Next, we summarize recent work in constraint posting scheduling procedures, which offer the promise of better future solutions to this class of problems.

Smith, Stephen F.↗

NASA NTRS1982

A DSN optimal spacecraft scheduling model

A computer model is described which uses mixed-integer linear programming to provide optimal DSN spacecraft schedules given a mission set and specified scheduling requirements. A solution technique is proposed which uses Bender's Method and a heuristic starting algorithm.

Webb, W. A.↗

NASA NTRS1985

An optimal spacecraft scheduling model for the NASA deep space network

Webb, W. A.↗