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.     

Fixed priority scheduling of tasks with arbitrary precedence constraints in distributed hard real-time systems

This paper considers the schedulability analysis of real-time distributed applications where tasks may present arbitrary precedence relations. It is assumed that tasks are periodic or sporadic and dynamically released. They have fixed priorities and hard end-to-end deadlines that are equal to or less than the respective period. We develop a method to transform arbitrary precedence relations into release jitter. By eliminating all precedence relations in the task set one can apply any available schedulability test that is valid for independent task sets.     

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.     

满足偏序约束的在线调度

具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束,又要满足任务间执行的偏序约束。基于并行拓扑排序,提出一种新的在线调度算法,该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置,能够处理释放时间任意的任务集。给出该算法的原理和设计,并通过示例分析和比较对算法进行验证。     

Average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems

We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound; however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times.     

The parallel complexity of scheduling with precedence constraints

We study the problem of parallel computation of a schedule for a system of n unit-length tasks on m identical machines, when the tasks are related by a set of precedence constraints. We present NC algorithms for computing an optimal schedule in the case where m, the number of available machines, does not vary with time and the precedence constraints are represented by a collection of outtrees. The algorithms run on an exclusive read, exclusive write (EREW) PRAM. Their complexities are O(log n) and O((log n)²) parallel time using O(n²) and O(n) processors, respectively. The schedule computed by our algorithms is a height-priority schedule. As a complementary result we show that it is very unlikely that computing such a schedule is in NC when any of the above conditions is significantly relaxed. We prove that the problem is P-complete under logspace reductions when the precedence constraints are a collection of intrees and outtrees, or for a collection of outtrees when the number of available machines is allowed to increase with time. The time span of a height-priority schedule for an arbitrary precedence constraints graph is at most 2 − 1/(m − 1) times longer than the optimal (N. E Chen and C. L. Liu, Proc. 1974 Sagamore Computer Conference on Parallel Processing, T. Fend (Ed.), Springer-Verlag, Berlin, 1975, pp. 1–16). Whereas it is P-complete to produce the classical height-priority schedules even for very restricted precedence constraints graphs, we present a simple NC parallel algorithm which produces a different schedule that is only 2 − 1/m times the optimal.     

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.     

具有优先链约束的网格作业多资源调度问题

网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型P_m|fix,p=1,chain|C_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的。     

Scheduling PVM Tasks

This paper describes a PVM task scheduler designed and implemented by the authors.The scheduler supports selecting idle workstations,scheduling pool tasks and dynamically produced subtasks.It can improve resource utilization,reduce job response time and simplify programming.     

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     

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.     

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.