Decentralized multi-robot allocation of tasks with temporal and precedence constraints

Abstract

We present an auction-based method for a team of robots to allocate and execute tasks that have temporal and precedence constraints. Temporal constraints are expressed as time windows, within which a task must be executed. The robots use our priority-based iterated sequential single-item auction algorithm to allocate tasks among themselves and keep track of their individual schedules. A key innovation is in decoupling precedence constraints from temporal constraints and dealing with them separately. We demonstrate the performance of the allocation method and show how it can be extended to handle failures and delays during task execution. We leverage the power of simulation as a tool to analyze the robustness of schedules. Data collected during simulations are used to compute well-known indexes that measure the risk of delay and failure in the robots’ schedules. We demonstrate the effectiveness of our method in simulation and with real robot experiments.     

Dynamic scheduling of real-time tasks under precedence constraints

While scheduling theory has been developed over a long period of time, it is important to note that most results concern problems with static characteristics. However, a real-time system is dynamic and requires on-line and adaptive scheduling strategies. So, an important aspect of real-time systems research is to devise methods flexible enough to react to a dynamic change of processor load and to attempt to schedule all the tasks judiciously.In this paper, we are particularly concerned with the problem of scheduling tasks which are of two kinds: periodic and sporadic, on a monoprocessor machine. Periodic tasks are independent, run cyclically and their characteristics are known in advance. In addition, we allow for the unpredictable occurrence of aperiodic task groups, with timing and precedence constraints. Clearly, the main problem is to devise a schedulability test that makes it possible to decide whether a new occurring group can be accepted, without upsetting the tight timing behavior requirements.We present an optimal acceptance test which returns a decision on the basis of the current state of processor load and by considering tasks to be scheduled according to the well known preemptive algorithm Earliest Deadline. The acceptance algorithm and a complexity analysis are presented.     

On scheduling tasks with exponential service times and in-tree precedence constraints

Summary In this paper we extend the work of Chandy and Reynolds in which they considered the problem of scheduling tasks on two identical processors. The processing times of the tasks are independent, identically distributed exponential random variables. The tasks are subject to in-tree precedence constraints. Chandy and Reynolds have shown that the expected value of the makespan is minimized if and only if the scheduling policy is Highest-Level-First (HLF). We extend their result by showing that a policy maximizes the probability that all tasks finish by some time t0 if and only if the policy is HLF. Additionally, we show that a policy maximizes the probability that the sum of the finishing times of all the tasks is less than some value s0 if and only if the policy is HLF.This work has been partially supported by a Lady Davis Fellowship at the Technion, Haifa Israel; by the Research Institute for Advanced Computer Science at the NASA Ames Research Center, Moffett Field CA; and by NSF Grant MCS 80-04257.     

Scheduling jobs with mixed processing times,arbitrary precedence constraints and maximum cost criterion

We consider single-machine scheduling problems with variable job processing times, arbitrary precedence constraints and maximum cost criterion. We show how to solve the problems in polynomial time in the cases when job processing times are described by functions of the same type or when they are mixed, i.e. some of them are fixed, while the other ones are variable and take into account the effects of learning, ageing or job deterioration.     

Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics

In this paper, we discuss a scheduling problem for parallel batch machines where the jobs have ready times. Problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). In addition, we consider precedence constraints among the jobs. Such constraints arise, for example, in scheduling subproblems of the shifting bottleneck heuristic when complex job shop scheduling problems are tackled. We use the total weighted tardiness as the performance measure to be optimized. Hence, the problem is NP-hard and we have to rely on heuristic solution approaches. We consider a variable neighborhood search (VNS) scheme and a greedy randomized adaptive search procedure (GRASP) to compute efficient solutions. We assess the performance of the two metaheuristics based on a large set of randomly generated problem instances and based on instances from the literature. The obtained computational results demonstrate that VNS is a very fast heuristic that quickly leads to high-quality solutions, whereas the GRASP is slightly outperformed by the VNS approach. However, the GRASP approach has the advantage that it can be parallelized in a more natural manner compared to VNS.     

On a parallel machine scheduling problem with precedence constraints

We characterize a nontrivial special case with a polynomial-time algorithm for a well-known parallel machine scheduling problem with precedence constraints, with a fixed number of machines, and with tasks of unit length. The special case is related to instances with given maximum path length and maximum degree of the task precedence graph. The method is based on the observation that the number of tasks is either small and bounded by a constant depending on the maximum path length and maximum degree, or alternatively, the number of tasks is large, giving a “dense” schedule.     

Parallel machine scheduling with precedence constraints and setup times

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. These problems are strongly NP-hard and it is even conjectured that no list scheduling algorithm can be defined without explicitly considering jointly scheduling and resource allocation. We propose dominance conditions based on the analysis of the problem structure and an extension to setup times of the energetic reasoning constraint propagation algorithm. An exact branch-and-bound procedure and a climbing discrepancy search (CDS) heuristic based on these components are defined. We show how the proposed dominance rules can still be valid in the CDS scheme. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.     

Scheduling multiprocessor tasks with genetic algorithms

In the multiprocessor scheduling problem, a given program is to be scheduled in a given multiprocessor system such that the program's execution time is minimized. This problem being very hard to solve exactly, many heuristic methods for finding a suboptimal schedule exist. We propose a new combined approach, where a genetic algorithm is improved with the introduction of some knowledge about the scheduling problem represented by the use of a list heuristic in the crossover and mutation genetic operations. This knowledge-augmented genetic approach is empirically compared with a “pure” genetic algorithm and with a “pure” list heuristic, both from the literature. Results of the experiments carried out with synthetic instances of the scheduling problem show that our knowledge-augmented algorithm produces much better results in terms of quality of solutions, although being slower in terms of execution time     

Scheduling precedence constrained task graphs with non-negligibleintertask communication onto multiprocessors

The multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence constrained task graph (representing a parallel program) onto the processors of a multiprocessor in a way that minimizes the completion time. Since this problem is known to be NP-hard in the strong sense in all but a few very restricted eases, heuristic algorithms are being developed which obtain near optimal schedules in a reasonable amount of computation time. We present an efficient heuristic algorithm for scheduling precedence constrained task graphs with nonnegligible intertask communication onto multiprocessors taking contention in the communication channels into consideration. Our algorithm for obtaining satisfactory suboptimal schedules is based on the classical list scheduling strategy. It simultaneously exploits the schedule-holes generated in the processors and in the communication channels during the scheduling process in order to produce better schedules. We demonstrate the effectiveness of our algorithm by comparing with two competing heuristic algorithms available in the literature     

Scheduling on-demand broadcast with timing constraints

In a distributed system, broadcasting is an efficient way to dispense data in certain highly dynamic environments. While there are several well-known on-line broadcast scheduling strategies that minimize wait time, there has been little research that considers on-demand broadcasting with timing constraints. One application which could benefit from a strategy for on-demand broadcast with timing constraints is a real-time database system. Scheduling strategies are needed in real-time databases that identify which data item to broadcast next in order to minimize missed deadlines. The scheduling decisions required in a real-time broadcast system allow the system to be modeled as a Markov Decision Process (MDP). In this paper, we analyze the MDP model and determine that finding an optimal solution is a hard problem in PSPACE. We propose a scheduling approach, called Aggregated Critical Requests (ACR), which is based on the MDP formulation and present two algorithms based on this approach. ACR is designed for timely delivery of data to clients in order to maximize the reward by minimizing the deadlines missed. Results from trace-driven experiments indicate the ACR approach provides a flexible strategy that can outperform existing strategies under a variety of factors.     

Task scheduling with precedence constraints to minimize the total completion time

The authors study the problem of scheduling a set of tasks with known execution times and arbitrary precedence constraints to computing systems. The objective function used to measure the performance of a schedule in this paper is the sum of completion times of all tasks, which is called total completion time. Finding the minimum total completion time of tasks with precedence constraints on the uniprocessor system is known to be NP-complete, let alone on the multiprocessor system (Garey and Johnson 1979) Based on the well-known A? algorithm proposed in the field of artificial intelligence (Nilson 1980) two algorithms are developed to solve efficiently the scheduling problems on the uniprocessor system and multiprocessor system. Some evaluation functions are proposed to accelerate the search of an optimal schedule. A table named the backwards range-limited table is used to assist the computation of the evaluation function. Experimental results show that the proposed approaches can achieve the optimal schedule with greatly reduced search tree size, especially when bounding rules are applied.     

Single machine scheduling with precedence constraints and positionally dependent processing times

In many real-life situations the processing conditions in scheduling models cannot be viewed as given constants since they vary over time thereby affecting actual durations of jobs. We consider single machine scheduling problems of minimizing the makespan in which the processing time of a job depends on its position (with either cumulative deterioration or exponential learning). It is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements. This can be modeled by imposing precedence constraints on the set of jobs. We consider scheduling models with positional deterioration or learning under precedence constraints that are built up iteratively from the prime partially ordered sets of a bounded width (this class of precedence constraints includes, in particular, series-parallel precedence constraints). We show that objective functions of the considered problems satisfy the job module property and possess the recursion property. As a result, the problems under consideration are solvable in polynomial time.     

Job shop scheduling with setup times, deadlines and precedence constraints

In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art. Paper presented in New York at MISTA 2005. E. Balas supported by the National Science Foundation through grant DMI-9802773 and by the Office of Naval Research through contract #N00014-97-1-0133.     

Scheduling processes with release times, deadlines, precedence andexclusion relations

An algorithm that finds an optimal schedule on a single processor for a given set of processes is presented. Each process starts executing after its release time and completes its computation before its deadline and a given set of precedence relations and exclusion relations defined on ordered pairs of process segments are satisfied. This algorithm can be applied to the important and previously unsolved problem of automated pre-run-time scheduling of processes with arbitrary precedence and exclusion in hard-real-time systems     

Exact algorithms for single-machine scheduling with time windows and precedence constraints

We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unit-time delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branch-and-bound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving medium-sized instances, and that it compares favorably with existing methods for special cases of the problem.     

Scheduling of coupled tasks with unit processing times

The coupled tasks scheduling problem was originally introduced for modeling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on a single processor, under the assumptions that all processing times are equal to 1, the gap has exact integer length L and the precedence constraints are strict. We prove that the general problem, when L is part of the input and the precedence constraints graph is a general graph, is NP-hard in the strong sense. We also show that the special case when L=2 and the precedence constraints graph is an in-tree or an out-tree, can be solved in O(n) time.     

Optimal flow control in acyclic networks with uncontrollable routings and precedence constraints

This paper introduces a novel optimal flow control problem that seeks to convey a specified amount of fluid to each of the nodes of an acyclic digraph with a single source node, while minimizing the total amount of fluid inducted into the network. Two factors complicating the aforementioned task are (i) the presence of nodes with uncontrollable routing of the traversing flow and (ii) a set of precedence constraints regarding the satisfaction of the nodal fluid requirements. It is shown that the considered problem can be naturally formulated as a continuous-time optimal control problem that can be reduced to a hybrid optimal control problem with controlled switching. This property subsequently enables the solution of the considered problem through a Mixed Integer Programming formulation. Additional results in the paper establish the NP-hardness of the considered problem, highlight its affinity to some well known scheduling problems, and offer guidelines that can alleviate the increased problem complexity.