Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Task 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 NTRS1986

On scheduling tasks with a quick recovery from failure

Multiprocessors used in life-critical real-time systems must recover quickly from failure. Part of this recovery consists of switching to a new task schedule which ensures that hard deadlines for critical tasks continue to be met. A dynamic programming algorithm is presented that ensures that backup, or contingency, schedules can be efficiently embedded within the original, 'primary' schedule to ensure that hard deadlines continue to be met in the face of up to a given maximum number of processor failures. Several illustrative examples are included.

Krishna, C. M.↗
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 NTRS2007

In-Space Crew-Collaborative Task Scheduling

For all past and current human space missions, the final scheduling of tasks to be done in space has been devoid of crew control, flexibility, and insight. Ground controllers, with minimal input from the crew, schedule the tasks and uplink the timeline to the crew or uplink the command sequences to the hardware. Prior to the International Space Station (ISS), the crew could make requests about tomorrow s timeline, they could omit a task, or they could request that something in the timeline be delayed. This lack of control over one's own schedule has had negative consequences. There is anecdotal consensus among astronauts that control over their own schedules will mitigate the stresses of long duration missions. On ISS, a modicum of crew control is provided by the job jar. Ground controllers prepare a task list (a.k.a. "job jar") of non-conflicting tasks from which jobs can be chosen by the in space crew. Because there is little free time and few interesting non-conflicting activities, the task-list approach provides little relief from the tedium of being micro-managed by the timeline. Scheduling for space missions is a complex and laborious undertaking which usually requires a large cadre of trained specialists and suites of complex software tools. It is a giant leap from today s ground prepared timeline (with a job jar) to full crew control of the timeline. However, technological advances, currently in-work or proposed, make it reasonable to consider scheduling a collaborative effort by the ground-based teams and the in-space crew. Collaboration would allow the crew to make minor adjustments, add tasks according to their preferences, understand the reasons for the placement of tasks on the timeline, and provide them a sense of control. In foreseeable but extraordinary situations, such as a quick response to anomalies and extended or unexpected loss of signal, the crew should have the autonomous ability to make appropriate modifications to the timeline, extend the timeline, or even start over with a new timeline. The Vision for Space Exploration (VSE), currently being pursued by the National Aeronautics and Space Administration (NASA), will send humans to Mars in a few decades. Stresses on the human mind will be exacerbated by the longer durations and greater distances, and it will be imperative to implement stress-reducing innovations such as giving the crew control of their daily activities.

Jaap, John↗
NASA NTRS1988

Ada task scheduling: A focused Ada investigation

The types of control that are important for real time task scheduling are discussed. Some closely related real time issues are mentioned and major committee and research activities in this area are delineated. Although there are some problems with Ada and its real time task scheduling, Ada presents fewer than any known alternative. Ada was designed for the domain of real time embedded systems, but Ada compilers may not contain a level of task scheduling support that is adequate for all real time applications. The question addressed is which implementations of Ada's task scheduling are adequate for effective real time systems for NASA applications.

Legrand, Sue↗
NASA NTRSDate not supplied

Towards a Characterization of Scheduling Task Complexity

Future long-duration missions will require astronauts to act more autonomously, manage their schedules, and replan timelines as anomalies and discoveries occur. Astronauts are not professional planners, however, and the complexity of schedules that novice planners can complete successfully is not fully understood. To identify the primary factors which contribute to scheduling task complexity, we conducted a human-in-the-loop study and developed planning algorithms to investigate how the type and amount of constraints affect the difficulty of scheduling and rescheduling. We created rankings of difficulty using a combination of human performance metrics from experimental planning tasks and metrics describing the final plans that participants scheduled. Using the results of our scheduling and rescheduling algorithm algorithms, we created a similar ranking with which to compare. We created rankings which compared well between the experimental and algorithm results for the scheduling task, but the rescheduling task proved more difficult to estimate.

scheduling↗
NASA NTRSDate not supplied

Towards a Characterization of Scheduling Task Complexity

Future long-duration missions will require astronauts to act more autonomously, manage their schedules, and replan timelines as anomalies and discoveries occur. Astronauts are not professional planners, however, and the complexity of schedules that novice planners can complete successfully is not fully understood. To identify the primary factors which contribute to scheduling task complexity, we conducted a human-in-the-loop study and developed planning algorithms to investigate how the type and amount of constraints affect the difficulty of scheduling and rescheduling. We created rankings of difficulty using a combination of human performance metrics from experimental planning tasks and metrics describing the final plans that participants scheduled. Using the results of our scheduling and rescheduling algorithm algorithms, we created a similar ranking with which to compare. We created rankings which compared well between the experimental and algorithm results for the scheduling task, but the rescheduling task proved more difficult to estimate.

scheduling↗
NASA NTRS2023

Framework for Extensible, Asynchronous Task Scheduling (FEATS) in Fortran

Most parallel scientific programs contain compiler directives (pragmas) such as those from OpenMP, explicit calls to runtime library procedures such as those implementing the Message Passing Interface (MPI), or compiler-specific language extensions such as those provided by CUDA. By contrast, the recent Fortran standards empower developers to express parallel algorithms without directly referencing lower-level parallel programming models. Fortran’s parallel features place the language within the Partitioned Global Address Space (PGAS) class of programming models. When writing programs that exploit data-parallelism, application developers often find it straightforward to develop custom parallel algorithms. Problems involving complex, heterogeneous, staged calculations, however, pose much greater challenges. Such applications require careful coordination of tasks in a manner that respects dependencies prescribed by a directed acyclic graph. When rolling one’s own solution proves difficult, extending a customizable framework becomes attractive. The paper presents the design, implementation, and use of the Framework for Extensible Asynchronous Task Scheduling (FEATS), which we believe to be the first task-scheduling tool written in modern Fortran. We describe the benefits and compromises associated with choosing Fortran as the implementation language, and we propose ways in which future Fortran standards can best support the use case in this paper.

Modern Fortran↗
NASA NTRS2006

In-Space Crew-Collaborative Task Scheduling

As humans venture farther from earth for longer durations, it will become essential for those on the journey to have significant control over the scheduling of their own activities as well as the activities of their companion systems and robots. However, there are many reasons why the crew will not do all the scheduling; timelines will be the result of collaboration with ground personnel. Emerging technologies such as in-space message buses, delay-tolerant networks, and in-space internet will be the carriers on which the collaboration rides. Advances in scheduling technology, in the areas of task modeling, scheduling engines, and user interfaces will allow the crew to become virtual scheduling experts. New concepts of operations for producing the timeline will allow the crew and the ground support to collaborate while providing safeguards to ensure that the mission will be effectively accomplished without endangering the systems or personnel.

Jaap, John↗
NASA NTRS2006

In-Space Crew-Collaborative Task Scheduling

As humans venture farther from Earth for longer durations, it will become essential for those on the journey to have significant control over the scheduling of their own activities as well as the activities of their companion systems and robots. However, the crew will not do all the scheduling; timelines will be the result of collaboration with ground personnel. Emerging technologies such as in-space message buses, delay-tolerant networks, and in-space internet will be the carriers on which the collaboration rides. Advances in scheduling technology, in the areas of task modeling, scheduling engines, and user interfaces will allow the crew to become virtual scheduling experts. New concepts of operations for producing the timeline will allow the crew and the ground support to collaborate while providing safeguards to ensure that the mission will be effectively accomplished without endangering the systems or personnel.

Jaap, John↗
NASA NTRS2006

Remote Collaboration on Task Scheduling for Humans at Mars

As humans venture farther from Earth for longer durations, it will become essential for those on the journey to have significant control over the scheduling of their own activities as well as the activities of their companion systems and robots. However, the crew will not do all the scheduling; timelines will be the result of collaboration with ground personnel. Emerging technologies such as in-space message buses, delay-tolerant networks, and in-space internet will be the carriers on which the collaboration rides. Advances in scheduling technology, in the areas of task modeling, scheduling engines, and user interfaces will allow the crew to become virtual scheduling experts. New concepts of operations for producing the timeline will allow the crew and the ground support to collaborate while providing safeguards to ensure that the mission will be effectively accomplished without endangering the systems or personnel.

Jaap, John↗
NASA NTRS1994

Task scheduling in dataflow computer architectures

Dataflow computers provide a platform for the solution of a large class of computational problems, which includes digital signal processing and image processing. Many typical applications are represented by a set of tasks which can be repetitively executed in parallel as specified by an associated dataflow graph. Research in this area aims to model these architectures, develop scheduling procedures, and predict the transient and steady state performance. Researchers at NASA have created a model and developed associated software tools which are capable of analyzing a dataflow graph and predicting its runtime performance under various resource and timing constraints. These models and tools were extended and used in this work. Experiments using these tools revealed certain properties of such graphs that require further study. Specifically, the transient behavior at the beginning of the execution of a graph can have a significant effect on the steady state performance. Transformation and retiming of the application algorithm and its initial conditions can produce a different transient behavior and consequently different steady state performance. The effect of such transformations on the resource requirements or under resource constraints requires extensive study. Task scheduling to obtain maximum performance (based on user-defined criteria), or to satisfy a set of resource constraints, can also be significantly affected by a transformation of the application algorithm. Since task scheduling is performed by heuristic algorithms, further research is needed to determine if new scheduling heuristics can be developed that can exploit such transformations. This work has provided the initial development for further long-term research efforts. A simulation tool was completed to provide insight into the transient and steady state execution of a dataflow graph. A set of scheduling algorithms was completed which can operate in conjunction with the modeling and performance tools previously developed. Initial studies on the performance of these algorithms were done to examine the effects of application algorithm transformations as measured by such quantities as number of processors, time between outputs, time between input and output, communication time, and memory size.

Katsinis, Constantine↗
NASA NTRS1989

Scheduling Tasks In Parallel Processing

Algorithms sought to minimize time and cost of computation. Report describes research on scheduling of computations tasks in system of multiple identical data processors operating in parallel. Computational intractability requires use of suboptimal heuristic algorithms. First algorithm called "list heuristic", variation of classical list scheduling. Second algorithm called "cluster heuristic" applied to tightly coupled tasks and consists of four phases. Third algorithm called "exchange heuristic", iterative-improvement algorithm beginning with initial feasible assignment of tasks to processors and periods of time. Fourth algorithm is iterative one for optimal assignment of tasks and based on concept called "simulated annealing" because of mathematical resemblance to aspects of physical annealing processes.

Price, Camille C.↗
NASA NTRS1991

Strategic behavior, workload, and performance in task scheduling

Scheduling theory is proposed as a normative model for strategic behavior when operators are confronted by several tasks, all of which should be completed within a fixed time span, and when they are free to choose the order in which the tasks should be done. Three experiments are described to investigate the effect of knowing the correct scheduling rule on the efficiency of performance, subjective workload, and choice of strategy under different conditions of time pressure. The most potent effects are from time pressure. The reasons for the weak effect of knowing the rules are discussed, and implications for strategic behavior, displays, and decision aids are indicated.

Moray, Neville↗
NASA NTRS1991

A scheduling algorithm for parallelizable dependent tasks

Scheduling a collection of tasks on a multiprocessor consisting of p processors, that minimizes the maximum completion time has attracted a lot of attention in the literature. This paper introduces a new problem of scheduling a task graph on a multiprocessor, called the parallelizable dependent task scheduling problem. Associated with each task, the paper shows the time it takes to run on a uniprocessor, and the speedup that can be obtained by running it on i processors, with i between 1 and p. Also presented are an algorithm for the problem and an analysis of the performance.

Belkhale, Krishna P.↗
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 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 NTRS2021

Human Performance of Novice Schedulers for Complex Spaceflight Operations Timelines

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.

scheduling↗