Static scheduling of multiple workflows with soft deadlines in non-dedicated heterogeneous environments

Typical patterns of using scientific workflows include their periodical executions using a fixed set of computational resources. Using the statistics from multiple runs, one can accurately estimate task execution and communication times to apply static scheduling algorithms. Several workflows with known estimates could be combined into a set to improve the resulting schedule. In this paper, we consider the mapping of multiple workflows to partially available heterogeneous resources. The problem is how to fill free time windows with tasks from different workflows, taking into account users’ requirements of the urgency of the results of calculations. To estimate quality of schedules for several workflows with various soft deadlines, we introduce the unified metric incorporating levels of meeting constraints and fairness of resource distribution.The main goal of the work was to develop a set of algorithms implementing different scheduling strategies for multiple workflows with soft deadlines in a non-dedicated environment, and to perform a comparative analysis of these strategies. We study how time restrictions (given by resource providers and users) influence the quality of schedules, and which scheme of grouping and ordering the tasks is the most effective for the batched scheduling of non-urgent workflows. Experiments with several types of synthetic and domain-specific sets of multiple workflows show that: (i) the use of information about time windows and deadlines leads to the significant increase of the quality of static schedules, (ii) the clustering-based scheduling scheme outperforms task-based and workflow-based schemes. This was confirmed by an evaluation of studied algorithms on a basis of the CLAVIRE workflow management platform.     

A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department

Nurse scheduling is a critical issue in the management of emergency department. Under the intense work environment, it is imperative to make quality nurse schedules in a most cost and time effective way. To this end, a spreadsheet-based two-stage heuristic approach is proposed for the nurse scheduling problem (NSP) in a local emergency department. First, an initial schedule satisfying all hard constraints is generated by the simple shift assignment heuristic. Second, the sequential local search algorithm is employed to improve the initial schedules by taking soft constraints (nurse preferences) into account. The proposed approach is benchmarked with the existing approach and 0–1 programming. The contribution of this paper is twofold. First, it is one of a few studies in nurse scheduling literature using heuristic approach to generate nurse schedules based on Excel spreadsheet. Therefore, users with little knowledge on linear programming and computer sciences can operate and change the scheduling algorithms easily. Second, while most studies on nurse scheduling are situated in hospitals, this paper attempts to bridge the research gap by investigating the NSP in the emergency department where the scheduling rules are much more restrictive due to the intense and dynamic work environment. Overall, our approach generates satisfactory schedules with higher level of user-friendliness, efficiency, and flexibility of rescheduling as compared to both the existing approach and 0–1 programming.     

On parallelizing the multiprocessor scheduling problem

Existing heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size     

Dynamic critical-path scheduling: an effective technique forallocating task graphs to multiprocessors

In this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures     

Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints

In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. Relative timing constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (Gerber et al., 1995; Han and Lin, 1989; Han et al., 1992; Han and Lin, 1992; Han et al., 1996).One approach in real-time scheduling is to find a total order on a set of N tasks in a scheduling window, and cyclically use this order at run time to execute tasks. However, in the presence of relative timing constraints, if the task execution times are nondeterministic with defined lower and upper bounds, it is not always possible to statically assign task start times at pre-runtime for a given task ordering (Gerber et al., 1995).We develop a technique called dynamic cyclic dispatching as an extension of a parametric dispatching mechanism in (Gerber et al., 1995). An ordered set of N tasks is assumed to be given in a scheduling window and this schedule(ordering) is cyclically repeated at runtime in consecutive scheduling windows. Relative timing constraints between tasks may be defined across scheduling window boundaries as well as within one scheduling window. A task set is defined to be dispatchable if there exists any way in which the tasks can be dispatched with all their timing constraints satisfied. An off-line algorithm is presented to check the dispatchability of a task set and to obtain parametric lower and upper bound functions for task start times if the task set is dispatchable. These parametric bound functions are evaluated at runtime to obtain a valid time interval during which a task can be started. The complexity of this off-line component is shown to be O(n ² N ³) where n is the number of tasks in a scheduling window that have relative timing constraints with tasks in the next scheduling window. An online algorithm can evaluate these bounds in O(N) time.Unlike static approaches which assign fixed start times to tasks in the scheduling window, our approach allows us to flexibly manage the slack times at runtime without sacrificing the dispatchability of tasks. Also, a wider class of relative timing constraints can be imposed to the task set compared to the traditional approaches.     

Contention-aware scheduling with task duplication

Finding an efficient schedule for a task graph on several processors is a trade-off between maximising concurrency and minimising interprocessor communication. Task duplication is a technique that has been employed to reduce or avoid interprocessor communication. Certain tasks are duplicated on several processors to produce the data locally and avoid the communication among processors. Most of the algorithms using task duplication have been proposed for the classic scheduling model, which allows concurrent communication and ignores contention for communication resources. It is increasingly recognised that this classic model is unrealistic and does not permit creating accurate and efficient schedules. The recently proposed contention model introduces contention awareness into task scheduling by assigning the edges of the task graph to the links of the communication network. It is intuitive that scheduling under such a model benefits even more from task duplication, yet no such algorithm has been proposed as it is not trivial to duplicate tasks under the contention model. This paper proposes a contention-aware task duplication scheduling algorithm. We investigate the fundamentals for task duplication in the contention model and propose an algorithm that is based on state-of-the-art techniques found in task duplication and contention-aware algorithms. An extensive experimental evaluation demonstrates the significant improvements to the speedup of the produced schedules.     

基于动态遗传算法的网格计算任务调度

针对网格任务调度的动态特性,提出一种改进的遗传算法——动态遗传算法(DGA),设计了新的编码机制和适应度函数,以及相应的选择、交叉和变异算子。根据网格系统各服务节点的计算能力、负载及网络状态进行动态调度,不仅使总的完成时间最短,尽量使主机的空闲时间最短,同时满足每个任务的截止时间的要求。在OPNET环境中构建了一个局部网格仿真模型,对所提出的动态遗传算法进行了仿真实验,并与其他常见网格任务调度算法进行了对比,结果表明动态遗传算法具有很好的优化能力,提供了较好的服务质量。     

Converging to periodic schedules for cyclic scheduling problems with resources and deadlines

Cyclic scheduling has been widely studied because of the importance of applications in manufacturing systems and in computer science. For this class of problems, a finite set of tasks with precedence relations and resource constraints must be executed repetitively while maximizing the throughput. Many applications also require that execution schedules be periodic i.e. the execution of each task is repeated with a fixed global period w.The present paper develops a new method to build periodic schedules with cumulative resource constraints, periodic release dates and deadlines. The main idea is to fix the period w, to unwind the cyclic scheduling problem for some number of iterations, and to add precedence relations so that the minimum time lag between two successive executions of any task equals w. Then, using any usual (not cyclic) scheduling algorithm to compute task starting times for the unwound problem, we prove that either the method converges to a periodic schedule of period w or it fails to compute a schedule. A non-polynomial upper bound on the number of iterations to unwind in order to guarantee that cyclic precedence relations and resource constraints are fulfilled is also provided. This method is successfully applied to a real-life problem, namely the software pipelining of inner loops on an embedded VLIW processor core by using a Graham list scheduling algorithm.     

Task clustering and scheduling for distributed memory parallelarchitectures

This paper addresses the problem of scheduling parallel programs represented as directed acyclic task graphs for execution on distributed memory parallel architectures. Because of the high communication overhead in existing parallel machines, a crucial step in scheduling is task clustering, the process of coalescing fine grain tasks into single coarser ones so that the overall execution time is minimized. The task clustering problem is NP-hard, even when the number of processors is unbounded and task duplication is allowed. A simple greedy algorithm is presented for this problem which, for a task graph with arbitrary granularity, produces a schedule whose makespan is at most twice optimal. Indeed, the quality of the schedule improves as the granularity of the task graph becomes larger. For example, if the granularity is at least 1/2, the makespan of the schedule is at most 5/3 times optimal. For a task graph with n tasks and e inter-task communication constraints, the algorithm runs in O(n(n lg n+e)) time, which is n times faster than the currently best known algorithm for this problem. Similar algorithms are developed that produce: (1) optimal schedules for coarse grain graphs; (2) 2-optimal schedules for trees with no task duplication; and (3) optimal schedules for coarse grain trees with no task duplication     

通用调度框架的改进及其在Linux中的实现

在嵌入式Linux实时系统中,要求内核对不同时问约束的任务采用不同的调度算法.但目前Linux内核采用单一的实时调度模式,不能灵活地执行多种调度算法,也就无法满足实时系统中实时任务的时间约束.引入了一种能够在Linux内核调度中执行多种调度算法的框架,即通用调度框架(GSF),并改进了其中的多算法调用机制,从而更好地在Linux内核中实现GSF.     

Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments

No-wait flow shops with makespan minimization are classified as NP-hard. In this paper, the optimization objective is equivalently transformed to total idle-time minimization. The independence relationship between tasks is analyzed, and objective increment properties are established for the fundamental operators of the heuristics. The quality of the new schedules generated during a heuristic is judged only by objective increments and not by the traditional method, which computes and compares the objective of a whole schedule. Based on objective increments, the time complexity of the heuristic can be decreased by one order. A seed phase is presented to generate an initial solution according to the transformed objective. Construction and improvement phases are introduced by experimental analysis. The FCH （fast composite heuristic） is proposed and compared with the most effective algorithms currently available for the considered problem. Experimental results show that the effectiveness of the FCH is similar to that of the best methods but requires far less computation time. The FCH can also be efficient in real time scheduling and rescheduling for no-wait flow shops.     

A strategy for scheduling tightly coupled parallel applications on clusters

Although various strategies have been developed for scheduling parallel applications with independent tasks, very little work exists for scheduling tightly coupled parallel applications on cluster environments. In this paper, we compare four different strategies based on performance models of tightly coupled parallel applications for scheduling the applications on clusters. In addition to algorithms based on existing popular optimization techniques, we also propose a new algorithm called Box Elimination that searches the space of performance model parameters to determine the best schedule of machines. By means of real and simulation experiments, we evaluated the algorithms on single cluster and multi‐cluster setups. We show that our Box Elimination algorithm generates up to 80% more efficient schedules than other algorithms. We also show that the execution times of the schedules produced by our algorithm are more robust against the performance modeling errors. Copyright © 2009 John Wiley & Sons, Ltd.     

全局信息不全的动态调度问题基于虚拟调度的两级滚动方法

This paper addresses the single-machine scheduling problem with release times mini-mizing the total completion time. Under the circumstance of incomplete global information at each decision time, a two-level rolling scheduling strategy (TRSS) is presented to create the global schedule step by step. The estimated global schedules are established based on a dummy schedule of unknown jobs. The first level is the preliminary scheduling based on the predictive window and the second level is the local scheduling for sub-problems based on the rolling window. Performance analysis demonstrates that TRSS can improve the global schedules. Computational results show that the solution quality of TRSS outperforms that of the existing rolling procedure in most cases.     

Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling

Many DAG scheduling algorithms generate schedules that require prohibitively large number of processors. To address this problem, we propose a generic algorithm, SC, to minimize the processor requirement of any given valid schedule. SC preserves the schedule length of the original schedule and reduces processor count by merging processor schedules and removing redundant duplicate tasks. To the best of our knowledge, this is the first algorithm to address this highly unexplored aspect of DAG scheduling. On average, SC reduced the processor requirement 91, 82, and 72 percent for schedules generated by PLW, TCSD, and CPFD algorithms, respectively. SC algorithm has a low complexity (O{N}³) compared to most duplication-based algorithms. Moreover, it decouples processor economization from schedule length minimization problem. To take advantage of these features of SC, we also propose a scheduling algorithm SDS, having the same time complexity as SC. Our experiments demonstrate that schedules generated by SDS are only 3 percent longer than CPFD (O{N}⁴), one of the best algorithms in that respect. SDS and SC together form a two-stage scheduling algorithm that produces schedules with high quality and low processor requirement, and has lower complexity than the comparable algorithms that produce similar high-quality results.     

Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times

This paper addresses scheduling problems for tasks with release and execution times. We present a number of efficient and easy to implement algorithms for constructing schedules of minimum makespan when the number of distinct task execution times is fixed. For a set of independent tasks, our algorithm in the single processor case runs in time linear in the number of tasks; with precedence constraints, our algorithm runs in time linear in the sum of the number of tasks and the size of the precedence constraints. In the multi-processor case, our algorithm constructs minimum makespan schedules for independent tasks with uniform execution times. The algorithm runs in O(n log m) time where n is the number of tasks and m is the number of processors. Received September 25, 1997; revised June 11, 1998.     

Hybrid Scheduling of Dynamic Task Graphs with Selective Duplication for Multiprocessors under Memory and Time Constraints

This paper presents a hybrid scheduling methodology for task graphs to multiprocessor embedded systems. The proposed methodology is designed for task graphs which are dynamic in nature due to the presence of conditional tasks as well as tasks whose execution times are unpredictable but bounded. We have presented the methodology as a three phase strategy in which task nodes are mapped to the processors in the first (static mapping) phase. In the second (selective duplication) phase some critical nodes are identified and duplicated for possible rescheduling at run-time depending on the code memory constraints of the processors. The third (online) phase is a run-time scheduling algorithm that performs list scheduling based on actual dynamics of the schedule up to the current time. We show that this technique provides better schedule length (up to 20%) compared to previous techniques which are predominantly static in nature with low overhead and comparable in complexity with existing online techniques. The effects of model parameters like number of processors, memory and various task graph parameters on performance are investigated in this paper.     

A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

Efficient task scheduling is critical to achieving high performance on grid computing environment. The task scheduling on grid is studied as optimization problem in this paper. A heuristic task scheduling algorithm satisfying resources load balancing on grid environment is presented. The algorithm schedules tasks by employing mean load based on task predictive execution time as heuristic information to obtain an initial scheduling strategy. Then an optimal scheduling strategy is achieved by selecting two machines satisfying condition to change their loads via reassigning their tasks under the heuristic of their mean load. Methods of selecting machines and tasks are given in this paper to increase the throughput of the system and reduce the total waiting time. The efficiency of the algorithm is analyzed and the performance of the proposed algorithm is evaluated via extensive simulation experiments. Experimental results show that the heuristic algorithm performs significantly to ensure high load balancing and achieve an optimal scheduling strategy almost all the time. Furthermore, results show that our algorithm is high efficient in terms of time complexity.     

A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks

Efficient task scheduling on heterogeneous distributed computing systems (HeDCSs) requires the consideration of the heterogeneity of processors and the inter-processor communication. This paper presents a two-phase algorithm, called H2GS, for task scheduling on HeDCSs. The first phase implements a heuristic list-based algorithm, called LDCP, to generate a high quality schedule. In the second phase, the LDCP-generated schedule is injected into the initial population of a customized genetic algorithm, called GAS, which proceeds to evolve shorter schedules. GAS employs a simple genome composed of a two-dimensional chromosome. A mapping procedure is developed which maps every possible genome to a valid schedule. Moreover, GAS uses customized operators that are designed for the scheduling problem to enable an efficient stochastic search. The performance of each phase of H2GS is compared to two leading scheduling algorithms, and H2GS outperforms both algorithms. The improvement in performance obtained by H2GS increases as the inter-task communication cost increases.     

一个调度Fork-Join任务图的新算法

任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。