Greed in resource scheduling

We examine the worst-case performance of a class of heuristic scheduling algorithms commonly referred to as priority-driven or list-scheduling algorithms. It is well known that these algorithms have anomalous, unpredictable performance when used to schedule nonpreemptive tasks with precedence constraints. We present a general method for deriving the worst-case performance of these algorithms. This method is easy to use, yet powerful enough to yield tight performance bounds for many classes of scheduling problems. We demonstrate the method for several problems to show it has wide applicability. We also present several task systems for which list-scheduling algorithms exhibit unavoidable worst-case performance and discuss the general characteristics of these task systems. These task systems are sometimes overlooked in simulation studies; consequently, the results of these studies may be overly optimistic.This work was partially supported by the US Navy. ONR Contract No. NVY N0001489 J1181     

一种基于QoS的自适应网格失效检测器

失效检测器是构建可靠的网格计算环境所必需的基础组件之一.由于网格中存在大量对失效检测有着不同QoS需求的分布式应用,对于一个网格失效检测器来说,为保持其有效性和可扩展性,应该既能够准确提供应用程序所需的失效检测QoS,又能够避免为满足不同QoS而设计多套失效检测器所产生的多余负载.基于QoS基本评价指标,采用PULL模式主动检测策略实现了一种新的失效检测器--GA-FD(adaptive failure detector for grid),可以同时支持多个应用程序定量描述的QoS需求,不需要关于消息行为和时钟同步的任何假设.同时,证明了GA-FD在部分同步模型下可实现一个◇P类的失效检测器,并给出了相应的实验及数据.     

Lower bounds for on-line two-dimensional packing algorithms

Summary Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.This author's work was supported by the Joint Services Electronics Program (U.S. Army, U.S. Navy and U.S. Air Force) under Contract DAAG-29-78-C-0016     

基于任务分配与调度的GSAT算法求解3-SAT问题

基于不同分配策略的云计算任务调度以及任务分配与调度的主要目的,提出了一种新的算法—求解3-SAT问题的基于任务分配与调度的GSAT算法。该算法将3-SAT问题中的每一个变量形成一个任务,在GSAT算法的基础上,引入任务分配与调度指导贪心搜索;同时,在保留原有贪心搜索的前提下,根据任务分配与调度的思想和3-SAT问题的特点,设计了两种新的策略—分配策略和调度策略共同完成整个贪心搜索过程。以标准的SATLAB库中变量个数从 20～250的3 700个不同规模的标准Uniform Random 3-SAT 问题对新的算法的性能进行了合理的测试,并与高效和普通性能改进的GSAT算法的结果作了比较,结果表明,该算法具有更高的成功率和更少的翻转次数。     

The On-Line Multiprocessor Scheduling Problem with Known Sum of the Tasks

In this paper we investigate a semi on-line multiprocessor scheduling problem. The problem is the classical on-line multiprocessor problem where the total sum of the tasks is known in advance. We show an asymptotic lower bound on the performance ratio of any algorithm (as the number of processors gets large), and present an algorithm which has performance ratio at most for any number of processors. When compared with known general lower bounds, this result indicates that the information on the sum of tasks substantially improves the performance ratio of on-line algorithms.     

A cutting and scheduling problem in float glass manufacturing

This paper considers a cutting and scheduling problem of minimizing scrap motivated by float glass manufacturing and introduces the float glass scheduling problem. We relate it to classical problems in the scheduling literature such as no-wait hybrid flow shops and cyclic scheduling. We show that the problem is NP-hard, and identify when each of the problem’s components are polynomially solvable and when they induce hardness. In addition, we propose a simple heuristic algorithm, provide its worst-case performance bounds, and demonstrate that the bounds are tight. When the number of machines is two, the worst-case performance is 5/3.     

Optimal Time-Critical Scheduling via Resource Augmentation

We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.     

Job scheduling and processor allocation for grid computing on metacomputers

Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model is proposed for modeling communication heterogeneity on computational grids. A processor allocation algorithm is developed which always finds an optimal processor allocation that minimizes the effective execution time of a job when the job is being scheduled. It is proven that the list scheduling (LS) algorithm can achieve reasonable worst-case performance bound in grid environments supporting distributed supercomputing with large applications. We compare the performance of various job scheduling and processor allocation algorithms for grid computing on metacomputers. We evaluate the performance of 128 combinations of two job scheduling algorithms, four initial job ordering strategies, four processor allocation algorithms, and four metacomputers by extensive simulation. It is found that the combination of largest job first (LJF) initial job ordering and minimum effective execution time (MEET) or largest machine first (LMF) processor allocation algorithm yields the best average-case performance, and the choice of FCFS and LS depends on the range of job sizes. It is also observed that communication heterogeneity does have significant impact on schedule lengths.     

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.     

Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems

The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes.     

基于改进DPSO的网格资源调度算法

基于市场经济模型的网格资源调度问题是一个典型的离散问题及NP-Hard问题,考虑到离散粒子群优化算法在解决离散问题上的有效性,本文在现有算法的研究基础上,提出一种基于改进的离散粒子群优化算法的网格资源分配和任务调度算法,并采用GridSim模拟器对相关算法进行仿真模拟实验和比较。实验结果表明,本文提出的调度算法在作业完成时间、综合性能以及资源的负载平衡方面均具有较大的优势。     

Non-Preemptive Real-Time Scheduling of Multimedia Tasks

Motivated by the special characteristics of multimedia tasks, we consider non-preemptive scheduling of tasks where there exists no (or very limited) information concerning the tasks before they are released. We present impossibility results and analyze algorithms for non-preemptive scheduling in single processor and multiprocessor systems. To evaluate our algorithm we assume that system obtains a value that is proportional to the processing time of the task whenever a task is completed by its deadline. Competitive analysis is used, where the goal is to keep the total value obtained by an on-line algorithm bounded by a function of the total value obtained by an off-line algorithm. In particular, one set of our results considers the competitive ratio of scheduling algorithm when the length of the tasks is not greater than C_max (and not smaller than C_min ). We show that the performance of a scheduling algorithm is improved dramatically when the release time of the tasks is O(C_max) prior to their deadline; achieving a competitive ratio that is close to one.     

Energy efficient scheduling of parallel tasks on multiprocessor computers

In this paper, scheduling parallel tasks on multiprocessor computers with dynamically variable voltage and speed are addressed as combinatorial optimization problems. Two problems are defined, namely, minimizing schedule length with energy consumption constraint and minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor and multicore processor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems and environments where timing constraint is a major requirement. Our scheduling problems are defined such that the energy-delay product is optimized by fixing one factor and minimizing the other. It is noticed that power-aware scheduling of parallel tasks has rarely been discussed before. Our investigation in this paper makes some initial attempt to energy-efficient scheduling of parallel tasks on multiprocessor computers with dynamic voltage and speed. Our scheduling problems contain three nontrivial subproblems, namely, system partitioning, task scheduling, and power supplying. Each subproblem should be solved efficiently, so that heuristic algorithms with overall good performance can be developed. The above decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. A unique feature of our work is to compare the performance of our algorithms with optimal solutions analytically and validate our results experimentally, not to compare the performance of heuristic algorithms among themselves only experimentally. The harmonic system partitioning and processor allocation scheme is used, which divides a multiprocessor computer into clusters of equal sizes and schedules tasks of similar sizes together to increase processor utilization. A three-level energy/time/power allocation scheme is adopted for a given schedule, such that the schedule length is minimized by consuming given amount of energy or the energy consumed is minimized without missing a given deadline. The performance of our heuristic algorithms is analyzed, and accurate performance bounds are derived. Simulation data which validate our analytical results are also presented. It is found that our analytical results provide very accurate estimation of the expected normalized schedule length and the expected normalized energy consumption and that our heuristic algorithms are able to produce solutions very close to optimum.     

Optimal Time-Critical Scheduling via Resource Augmentation

Abstract. We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

Approximation techniques for response-time analysis of static-priority tasks

We consider sporadic tasks with static priorities and constrained deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing worst-case response times for this task model. Some applications require to evaluate efficiently upper bounds of response times. For this purpose, we propose parametric algorithms that allow to make a tradeoff between quality of results and computational effort according to an input accuracy parameter. In this paper, we present a parametric polynomial-time algorithm for computing upper bounds of worst-case response times, that is based on an improved fptas (Fully Polynomial Time Approximation Scheme). Then, we show that our bound does not achieve constant error bound in comparison with the exact worst-case response time. However, using the resource augmentation technique, we obtain a performance guarantee that allows to define a compromise between our response-time bound and processor capacity requirements. The algorithm average behavior is then analyzed through numerical experimentations.     

Downlink data transmission scheduling algorithms in wireless networks

The problem of downlink data transmission scheduling in wireless networks is studied. It is pointed out that every downlink data transmission scheduling algorithm must have two components to solve the two subproblems of power assignment and transmission scheduling. Two types of downlink data transmission scheduling algorithms are proposed. In the first type, power assignment is performed before transmission scheduling. In the second type, power assignment is performed after transmission scheduling. The performance of two algorithms of the first type which use the equal power allocation method are analyzed. It is shown that both algorithms exhibit excellent worst-case performance and asymptotically optimal average-case performance under the condition that the total transmission power is equally allocated to the channels. In general, both algorithms exhibit excellent average-case performance. It is demonstrated that two algorithms of the second type perform better than the two algorithms of the first type due to the equal time power allocation method. Furthermore, the performance of our algorithms are very close to the optimal and the room for further performance improvement is very limited. It is shown that all the above algorithms can be extended to schedule downlink data transmissions with parallel channels. It is also shown that the simple sequential scheduling algorithm is optimal if the total transmission power is equally allocated to the channels. As an extra contribution, an M/G/1 queueing model for the FCFS queueing discipline is established, and it is observed that increasing the number of channels has more impact on the reduction of the average response time than increasing the total transmission power.     

民航信息交换任务调度方案

民航信息数据交换平台承担了大数据量的分布式传输任务,需要建立完善的任务调度模型和调度算法。基于民航信息交换平台的架构和需求,在分析比较现有的任务调度模型和调度算法基础上,提出适用于数据交换任务调度问题的解决方案,将点对多点数据传输网络映射为带约束的Steiner树模型,并用改进的遗传算法进行求解。实验仿真将此算法与最大带宽优先分配算法对比,结果充分验证了模型的正确性和可行性。     

An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

The current literature of fixed-priority scheduling algorithms relies on sufficient tests to determine if a set of mixed-criticality sporadic tasks is schedulable on a single processor. The drawback of these safe tests is their pessimism, a matter that could be solved if an exact schedulability analysis is used. However, because of the non-deterministic behavior of tasks in the mentioned setups, exact quantification of worst-case response times, needed for the test, is a difficult problem; more precisely, such a quantification needs evaluation of enormous sequences of job executions. The core problem is thus to merge such sequences to make the analysis practical. This paper, for the first time, gives an algorithm for exact worst-case response time characterization of mixed-criticality sporadic real-time tasks executing according to a given fixed-priority scheduler. We use a set of techniques which carefully consider the task properties and their relation to the worst scenarios to prune the analysis state space. We also show an interesting result that if an exact schedulability test is used, the Audsley’s optimal priority assignment algorithm is not applicable to the mixed-criticality case. Accordingly, we need new priority assignment algorithms to work with the exact test; we give a simple task priority assignment algorithm to this aim. The performance of the proposed exact test (in terms of time complexity) is examined and the effectiveness of some heuristic priority assignment algorithms using the test (in terms of the ratio of task sets which are deemed schedulable) are compared.     

Cluster scheduling for real-time systems: utilization bounds and run-time overhead

Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, assuming that an optimal global scheduler is adopted within each cluster, we investigate the worst-case utilization bounds for cluster scheduling with different task allocation/partitioning heuristics. First, we develop a lower limit on the utilization bounds for cluster scheduling with any reasonable task allocation scheme. Then, the lower limit is shown to be the exact utilization bound for cluster scheduling with the worst-fit task allocation scheme. For other task allocation heuristics (such as first-fit, best-fit, first-fit decreasing, best-fit decreasing and worst-fit decreasing), higher utilization bounds are derived for systems with both homogeneous clusters (where each cluster has the same number of processors) and heterogeneous clusters (where clusters have different number of processors). In addition, focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware task allocation heuristic with the goal of reducing the scheduling overhead (e.g., the number of scheduling points, context switches and task migrations). Simulation results indicate that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters, compared to that of the partitioned scheduling. Moreover, when comparing to the simple generic task allocation scheme (e.g., first-fit), the proposed period-aware task allocation heuristic markedly reduces the scheduling overhead of cluster scheduling with the Bfair scheduler.