Search NASA⌕ Search

SEARCH · Search NASA

Results for “scheduling”

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

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 NTRS1991

Analysis of Issues for Project Scheduling by Multiple, Dispersed Schedulers (distributed Scheduling) and Requirements for Manual Protocols and Computer-based Support

Although computerized operations have significant gains realized in many areas, one area, scheduling, has enjoyed few benefits from automation. The traditional methods of industrial engineering and operations research have not proven robust enough to handle the complexities associated with the scheduling of realistic problems. To address this need, NASA has developed the computer-aided scheduling system (COMPASS), a sophisticated, interactive scheduling tool that is in wide-spread use within NASA and the contractor community. Therefore, COMPASS provides no explicit support for the large class of problems in which several people, perhaps at various locations, build separate schedules that share a common pool of resources. This research examines the issue of distributing scheduling, as applied to application domains characterized by the partial ordering of tasks, limited resources, and time restrictions. The focus of this research is on identifying issues related to distributed scheduling, locating applicable problem domains within NASA, and suggesting areas for ongoing research. The issues that this research identifies are goals, rescheduling requirements, database support, the need for communication and coordination among individual schedulers, the potential for expert system support for scheduling, and the possibility of integrating artificially intelligent schedulers into a network of human schedulers.

Richards, Stephen F.↗
NASA NTRS1988

Integrated resource scheduling in a distributed scheduling environment

The Space Station era presents a highly-complex multi-mission planning and scheduling environment exercised over a highly distributed system. In order to automate the scheduling process, customers require a mechanism for communicating their scheduling requirements to NASA. A request language that a remotely-located customer can use to specify his scheduling requirements to a NASA scheduler, thus automating the customer-scheduler interface, is described. This notation, Flexible Envelope-Request Notation (FERN), allows the user to completely specify his scheduling requirements such as resource usage, temporal constraints, and scheduling preferences and options. The FERN also contains mechanisms for representing schedule and resource availability information, which are used in the inter-scheduler inconsistency resolution process. Additionally, a scheduler is described that can accept these requests, process them, generate schedules, and return schedule and resource availability information to the requester. The Request-Oriented Scheduling Engine (ROSE) was designed to function either as an independent scheduler or as a scheduling element in a network of schedulers. When used in a network of schedulers, each ROSE communicates schedule and resource usage information to other schedulers via the FERN notation, enabling inconsistencies to be resolved between schedulers. Individual ROSE schedules are created by viewing the problem as a constraint satisfaction problem with a heuristically guided search strategy.

Zoch, David↗
NASA NTRS2020

Using a Model of Scheduler Runtime to Improve the Effectiveness of Scheduling Embedded in Execution

Scheduling often interacts with execution. When the scheduler is developing a schedule, real time (execution) proceeds. Usually a scheduler cannot modify portions of the schedule expected to start execution prior to the scheduler's expected completion. In deployed systems, often little effort is spent on predicting scheduler runtime and instead an extremely conservative, simple model is used, resulting in loss of performance as less of the schedule can be updated. We develop predictive model(s) of scheduler runtime and use these models to improve scheduler and execution performance. We present several models of scheduler runtime based on a scheduler being deployed onboard NASA's next Mars rover, the M2020 rover Perseverance. The models consider algorithmic complexity, characteristics of the input plan, and prior runtime data. First, we show how these still relatively unsophisticated models can more accurately predict scheduler runtime compared to the static conservative baseline being used for the actual M2020 onboard scheduler. Second, we show how the more accurate scheduler runtime models' tighter (shorter) runtime predictions enable better scheduler performance as measured by makespan and percentage of activities executed. Finally, we discuss a number of future steps to further advance this line of work.

Chi, Wayne↗
NASA NTRSDate not supplied

Crew Autonomy through Self-Scheduling: Scheduling Performance Pilot Study

Within the domain of human spaceflight, crew scheduling for International Space Station (ISS) remains a human-driven planning task. Large teams of flight controllers (called Ops Planners) spend weeks creating violation-free schedules for all crewmembers. As NASA considers long-duration exploration missions, the necessary shift of scheduling and planning management from Ops Planners to crew members requires significant research and investigation of crew performance to complete these scheduling tasks. This pilot study was conducted to evaluate non-expert human performance for the task of planning and scheduling, focusing on scheduling problems that increased in complexity based on the number of activities to be scheduled and the number of planning constraints. Nine non-expert planners were recruited to complete scheduling tasks using Playbook, a scheduling software. The results of this pilot study show that scheduling performance decreased as scheduling workload (i.e. number of activities and percent of activities with planning constraints) increased. This paper provides evidence towards developing a model for scheduling task difficulty and identifies potential implications for future automated aids for flight crew scheduling.

planning↗
NASA NTRSDate not supplied

Crew Autonomy Through Self-Scheduling: Scheduling Performance Pilot Study

Within the domain of human spaceflight, crew scheduling for International Space Station (ISS) remains a human-driven planning task. Large teams of flight controllers (called Ops Planners) spend weeks creating violation-free schedules for all crewmembers. As NASA considers long-duration exploration missions, the necessary shift of scheduling and planning management from Ops Planners to crew members requires significant research and investigation of crew performance to complete these scheduling tasks. This pilot study was conducted to evaluate non-expert human performance for the task of planning and scheduling, focusing on scheduling problems that increased in complexity based on the number of activities to be scheduled and the number of planning constraints. Nine non-expert planners were recruited to complete scheduling tasks using Playbook, a scheduling software. The results of this pilot study show that scheduling performance decreased as scheduling workload (i.e. number of activities and percent of activities with planning constraints) increased. This paper provides evidence towards developing a model for scheduling task difficulty and identifies potential implications for future automated aids for flight crew scheduling.

planning↗
NASA NTRS1984

Wave scheduling - Decentralized scheduling of task forces in multicomputers

Decentralized operating systems that control large multicomputers need techniques to schedule competing parallel programs called task forces. Wave scheduling is a probabilistic technique that uses a hierarchical distributed virtual machine to schedule task forces by recursively subdividing and issuing wavefront-like commands to processing elements capable of executing individual tasks. Wave scheduling is highly resistant to processing element failures because it uses many distributed schedulers that dynamically assign scheduling responsibilities among themselves. The scheduling technique is trivially extensible as more processing elements join the host multicomputer. A simple model of scheduling cost is used by every scheduler node to distribute scheduling activity and minimize wasted processing capacity by using perceived workload to vary decentralized scheduling rules. At low to moderate levels of network activity, wave scheduling is only slightly less efficient than a central scheduler in its ability to direct processing elements to accomplish useful work.

Van Tilborg, A. M.↗
NASA NTRS1992

Completable scheduling: An integrated approach to planning and scheduling

The planning problem has traditionally been treated separately from the scheduling problem. However, as more realistic domains are tackled, it becomes evident that the problem of deciding on an ordered set of tasks to achieve a set of goals cannot be treated independently of the problem of actually allocating resources to the tasks. Doing so would result in losing the robustness and flexibility needed to deal with imperfectly modeled domains. Completable scheduling is an approach which integrates the two problems by allowing an a priori planning module to defer particular planning decisions, and consequently the associated scheduling decisions, until execution time. This allows a completable scheduling system to maximize plan flexibility by allowing runtime information to be taken into consideration when making planning and scheduling decision. Furthermore, through the criteria of achievability placed on deferred decision, a completable scheduling system is able to retain much of the goal-directedness and guarantees of achievement afforded by a priori planning. The completable scheduling approach is further enhanced by the use of contingent explanation-based learning, which enables a completable scheduling system to learn general completable plans from example and improve its performance through experience. Initial experimental results show that completable scheduling outperforms classical scheduling as well as pure reactive scheduling in a simple scheduling domain.

Gervasio, Melinda T.↗
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↗
NASA NTRS2016

Schedule Matters: Understanding the Relationship between Schedule Delays and Costs on Overruns

This paper examines the relationship between schedule delays and cost overruns on complex projects. It is generally accepted by many project practitioners that cost overruns are directly related to schedule delays. But what does "directly related to" actually mean? Some reasons or root causes for schedule delays and associated cost overruns are obvious, if only in hindsight. For example, unrealistic estimates, supply chain difficulties, insufficient schedule margin, technical problems, scope changes, or the occurrence of risk events can negatively impact schedule performance. Other factors driving schedule delays and cost overruns may be less obvious and more difficult to quantify. Examples of these less obvious factors include project complexity, flawed estimating assumptions, over-optimism, political factors, "black swan" events, or even poor leadership and communication. Indeed, is it even possible the schedule itself could be a source of delay and subsequent cost overrun? Through literature review, surveys of project practitioners, and the authors' own experience on NASA programs and projects, the authors will categorize and examine the various factors affecting the relationship between project schedule delays and cost growth. The authors will also propose some ideas for organizations to consider to help create an awareness of the factors which could cause or influence schedule delays and associated cost growth on complex projects.

Overruns↗
NASA NTRSDate not supplied

The Path to Crew Autonomy - Situational Awareness in Scheduling and Rescheduling Tasks for Novice Schedulers

To increase crew autonomy for long duration exploration-class missions (LDEM), certain mission support tasks need to be completed by crew. Currently, crew activities are scheduled over the course of several weeks by ground-based experts with years of experience-based training. These experts display extensive amounts of situational awareness (SA) throughout task execution by maintaining a mental model of additional factors during scheduling such as constraints (e.g. physical space/layout), abilities and skills of the crew, and crew preferences allowing them to anticipate and mitigate potential issues. Thus, situational awareness is a key component for crews to manage their own schedules. In this paper, we examined situational awareness in novice schedulers in both a scheduling and rescheduling task. Our findings indicate that there is no significant difference between scheduling and rescheduling tasks for the development of SA in novice schedulers. Additionally, our experiment shows that novice schedulers are less able to develop sufficient SA for constraints that are dependent on one or more activities. Thus, we propose that software aids may be useful to support novice schedulers and increase SA in scheduling/rescheduling tasks. This work is vital to ensure the successful transfer of mission support tasks to the crew for future LDEM.

situation awareness↗
NASA NTRSDate not supplied

Exploring Self-Scheduling Strategies and Heuristics in Novice Schedulers

Missions beyond low Earth orbit will require crews to act with greater autonomy. Increasing communication delays will require crews to take on tasks currently supported by Mission Control, including the involved process of scheduling and rescheduling their own complex spaceflight timelines to fit a variety of restrictions and constraints. Astronauts, unlike Mission Control, are not expert planners, however, and determining simple strategies and heuristics that enable them to schedule successfully can increase the range of problems they can solve successfully. In two human-in-the-loop scheduling experiments, we analyzed 1) common strategies among novice schedules, and 2) the development of self-scheduling heuristics. We find that, even when participants are instructed to follow a given strategy, they rapidly develop their own self-scheduling heuristics as they learn to successfully complete the scheduling task. Participants conducting naturally learn to schedule activities with the most constraints first, while participants vary in heuristics in the rescheduling task.

self-scheduling↗
NASA NTRSDate not supplied

Exploring Self-Scheduling Strategies and Heuristics in Novice Schedulers

Missions beyond low Earth orbit will require crews to act with greater autonomy. Increasing communication delays will require crews to take on tasks currently supported by Mission Control, including the involved process of scheduling and rescheduling their own complex spaceflight timelines to fit a variety of restrictions and constraints. Unlike Mission Control, astronauts are not expert planners, and determining strategies and heuristics that enable crews to schedule successfully may increase the range of problems they can solve. In two human-in-the-loop scheduling experiments, we analyzed 1) common strategies among novice schedulers and 2) the development of self-scheduling heuristics. We find that, even when participants are instructed to follow a given strategy, they rapidly develop their own self-scheduling heuristics as they learn to successfully complete the scheduling task. While scheduling, participants naturally learn to arrange activities with the most constraints first, whereas while rescheduling, they display greater variability in their heuristics.

self-scheduling↗
NASA NTRS1996

Investigations into Generalization of Constraint-Based Scheduling Theories with Applications to Space Telescope Observation Scheduling

This final report summarizes research performed under NASA contract NCC 2-531 toward generalization of constraint-based scheduling theories and techniques for application to space telescope observation scheduling problems. Our work into theories and techniques for solution of this class of problems has led to the development of the Heuristic Scheduling Testbed System (HSTS), a software system for integrated planning and scheduling. Within HSTS, planning and scheduling are treated as two complementary aspects of the more general process of constructing a feasible set of behaviors of a target system. We have validated the HSTS approach by applying it to the generation of observation schedules for the Hubble Space Telescope. This report summarizes the HSTS framework and its application to the Hubble Space Telescope domain. First, the HSTS software architecture is described, indicating (1) how the structure and dynamics of a system is modeled in HSTS, (2) how schedules are represented at multiple levels of abstraction, and (3) the problem solving machinery that is provided. Next, the specific scheduler developed within this software architecture for detailed management of Hubble Space Telescope operations is presented. Finally, experimental performance results are given that confirm the utility and practicality of the approach.

Muscettola, Nicola↗
NASA NTRS2005

Considerations for Using an Incremental Scheduler for Human Exploration Task Scheduling

As humankind embarks on longer space missions farther from home, the requirements and environments for scheduling the activities performed on these missions are changing. As we begin to prepare for these missions it is appropriate to evaluate the merits and applicability of the different types of scheduling engines. Scheduling engines temporally arrange tasks onto a timeline so that all constraints and objectives are met and resources are not overbooked. Scheduling engines used to schedule space missions fall into three general categories: batch, mixed-initiative, and incremental. This paper presents an assessment of the engine types, a discussion of the impact of human exploration of the moon and Mars on planning and scheduling, and the applicability of the different types of scheduling engines. This paper will pursue the hypothesis that incremental scheduling engines may have a place in the new environment; they have the potential to reduce cost, to improve the satisfaction of those who execute or benefit from a particular timeline (the customers), and to allow astronauts to plan their own tasks.

Jaap, John↗
NASA NTRS2006

Projecting Future Scheduled Airline Demand, Schedules and NGATS Benefits Using TSAM

The Transportation Systems Analysis Model (TSAM) developed by Virginia Tech s Air Transportation Systems Lab and NASA Langley can provide detailed analysis of the effects on the demand for air travel of a full range of NASA and FAA aviation projects. TSAM has been used to project the passenger demand for very light jet (VLJ) air taxi service, scheduled airline demand growth and future schedules, Next Generation Air Transportation System (NGATS) benefits, and future passenger revenues for the Airport and Airway Trust Fund. TSAM can project the resulting demand when new vehicles and/or technology is inserted into the long distance (100 or more miles one-way) transportation system, as well as, changes in demand as a result of fare yield increases or decreases, airport transit times, scheduled flight times, ticket taxes, reductions or increases in flight delays, and so on. TSAM models all long distance travel in the contiguous U.S. and determines the mode choice of the traveler based on detailed trip costs, travel time, schedule frequency, purpose of the trip (business or non-business), and household income level of the traveler. Demand is modeled at the county level, with an airport choice module providing up to three airports as part of the mode choice. Future enplanements at airports can be projected for different scenarios. A Fratar algorithm and a schedule generator are applied to generate future flight schedules. This paper presents the application of TSAM to modeling future scheduled air passenger demand and resulting airline schedules, the impact of NGATS goals and objectives on passenger demand, along with projections for passenger fee receipts for several scenarios for the FAA Airport and Airway Trust Fund.

Dollyhigh, Samuel↗
NASA NTRS1993

Scheduling the future NASA Space Network: Experiences with a flexible scheduling prototype

NASA's Space Network (SN) provides telecommunications and tracking services to low earth orbiting spacecraft. One proposal for improving resource allocation and automating conflict resolution for the SN is the concept of flexible scheduling. In this concept, each Payload Operations Control Center (POCC) will possess a Space Network User POCC Interface (SNUPI) to support the development and management of flexible requests. Flexible requests express the flexibility, constraints, and repetitious nature of the user's communications requirements. Flexible scheduling is expected to improve SN resource utilization and user satisfaction, as well as reduce the effort to produce and maintain a schedule. A prototype testbed has been developed to better understand flexible scheduling as it applies to the SN. This testbed consists of a SNUPI workstation, an SN scheduler, and a flexible request language that conveys information between the two systems. All three are being evaluated by operations personnel. Benchmark testing is being conducted on the scheduler to quantify the productivity improvements achieved with flexible requests.

Happell, Nadine↗
NASA NTRS2019

Crew Autonomy Scheduling: Scheduling Performance Pilot Study

The purpose of this pilot study is to quantify crew performance in self-scheduling through Playbook, a mobile-based scheduling and planning tool. By investigating human performance within the task of self-scheduling, we can further develop countermeasures that can mitigate deficient scheduling performance, and evaluate changes as a result of these countermeasures. Moreover, this research can advise the development of standards and guidelines for autonomous crews in future missions. In human spaceflight today, the task of planning crew member’s schedules falls to Ops Planners. It takes many weeks to plan due to the complex impact each day-to-day activity can have on other activities, crew members, and resources. These impacts are measured as constraints, and these constraints can result in temporal, ordering, or resource requirements. As future spaceflight missions span longer distances and the latency of communication between the crew and Mission Control Center (MCC) increases, the need for crew members to work independently from MCC will also increase. This results in a need for crew members to be able to autonomously plan and adjust their own schedules.

planning↗