共查询到20条相似文献,搜索用时 31 毫秒
1.
Alexandra Olteanu Florin Pop Ciprian Dobre Valentin Cristea 《Computers & Mathematics with Applications》2012,63(9):1409-1423
Scheduling is a key component for performance guarantees in the case of distributed applications running in large scale heterogeneous environments. Another function of the scheduler in such system is the implementation of resilience mechanisms to cope with possible faults. In this case resilience is best approached using dedicated rescheduling mechanisms. The performance of rescheduling is very important in the context of large scale distributed systems and dynamic behavior. The paper proposes a generic rescheduling algorithm. The algorithm can use a wide variety of scheduling heuristics that can be selected by users in advance, depending on the system’s structure. The rescheduling component is designed as a middleware service that aims to increase the dependability of large scale distributed systems. The system was evaluated in a real-world implementation for a Grid system. The proposed approach supports fault tolerance and offers an improved mechanism for resource management. The evaluation of the proposed rescheduling algorithm was performed using modeling and simulation. We present experimental results confirming the performance and capabilities of the proposed rescheduling algorithm. 相似文献
2.
Most semiconductor manufacturing systems (SMS) operate in a highly dynamic and unpredictable environment. The production rescheduling strategy addresses uncertainty and improves SMS performance. The rescheduling framework of SMS is presented as layered scheduling strategies with an optimization rescheduling decision mechanism. A fuzzy neural network (FNN) based rescheduling decision model is implemented which can rapidly choose an optimized rescheduling strategy to schedule the semiconductor wafer fabrication lines according to current system disturbances. The mapping between the input of FNN, such as disturbances, system state parameters, and the output of FNN, optimal rescheduling strategies, is constructed. An example of a semiconductor fabrication line in Shanghai is given. The experimental results demonstrate the effectiveness of proposed FNN-based rescheduling decision mechanism approach over the alternatives such as back-propagation neural network (BPNN) and multivariate regression (MR). 相似文献
3.
Constructing deliberative real-time AI systems is challenging due to the high execution-time variance in AI algorithms and
the requirement of worst-case bounds for hard real-time guarantees, often resulting in poor use of system resources. Using
a motivating case study, the general problem of resource usage maximization is addressed. We approach the issues by employing
a hybrid task model for anytime algorithms, which is supported by recent advances in fixed priority scheduling for imprecise
computation. In particular, with a novel scheduling scheme based on Dual Priority Scheduling, hard tasks are guaranteed by
schedulability analysis and scheduled in favor of optional and anytime components which are executed whenever possible for
enhancing system utility. Simulation studies show satisfactory performance on the case study with the application of the scheduling
scheme. We also suggest how aperiodic tasks can be scheduled effectively within the framework and how tasks can be prioritized
based on their utilities by an efficient algorithm. These works form a comprehensive package of scheduling model, analysis,
and algorithms based on fixed priority scheduling, providing a versatile platform where real-time AI applications can be suitably
facilitated.
相似文献
Alan BurnsEmail: |
4.
动态生产调度管理系统的研究与实现 总被引:3,自引:0,他引:3
本文基于知识发现提出了一类动态调度算法的框架,在此基础上,基于数据仓库建立
了动态调度管理系统的体系结构,并采用面向对象(Object-Oriented,O-O)技术,分析
和设计了动态调度管理系统,最后阐明了所提方法的优点. 相似文献
5.
Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and Methods 总被引:14,自引:0,他引:14
Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice. 相似文献
6.
Grids offer best effort services to users. Service level agreements offer the opportunity to provide guarantees upon services offered, in such a way that it captures the users' requirements, while also considering concerns of the service providers. This is achieved via a process of converging requirements and service cost values from both sides towards an agreement. This paper presents the intelligent scheduling for quality of service market‐oriented mechanism for brokering guarantees upon completion time and cost for jobs submitted to a batch‐oriented compute service. Web Services agreement (negotiation) is used along with the planning of schedules in determining pricing, ensuring that jobs become prioritised depending on their budget constraints. An evaluation is performed to demonstrate how market mechanisms can be used to achieve this, whilst also showing the effects that scheduling algorithms can have upon the market in terms of rescheduling. The evaluation is completed with a comparison of the broker's capabilities in relation to the literature. Copyright © 2014 John Wiley & Sons, Ltd. 相似文献
7.
8.
This paper proposes a new duplication-based task scheduling algorithm for distributed heterogeneous computing (DHC) systems.
For such systems, many researchers have focused on solving the NP-complete problem of scheduling directed acyclic task graphs
to minimize the makespan. However, the heterogeneity of computational resources and communication mechanisms poses some major
obstacles to achieving high parallel efficiency. This paper proposes a heuristic strategy called the Dominant Predecessor
Duplication (DPD) scheduling algorithm, which allows for system heterogeneities and communication bandwidth to exploit the
potential of parallel processing. This algorithm can improve system utilization and avoid redundant resource consumption,
resulting in better schedules. Experimental results show that the system heterogeneities and program structures of applications
affect scheduling performance, and that our presented algorithm is better able to avoid these problems than those presented
in previous literature. Here, we show that our algorithm can be applied to design efficient distributed systems to overcome
performance bottlenecks caused by system heterogeneities.
相似文献
Chao-Tung YangEmail: |
9.
10.
针对敏捷制造调度环境的不确定性、动态性以及混合流水车间(HFS)调度问题的特点,设计了一种基于多Agent的混合流水车间动态调度系统,系统由管理Agent、策略Agent、工件Agent和机器Agent构成。首先提出一种针对混合流水车间环境的插值排序(HIS)算法并集成于策略Agent中,该算法适用于静态调度和多种动态事件下的动态调度。然后,设计了各类Agent间的协调机制,在生产过程中所有Agent根据各自的行为逻辑独立工作并互相协调。在发生动态事件时,策略Agent调用HIS算法根据当前车间状态产生工件序列,随后各Agent根据生成的序列继续进行协调直到完成生产。最后进行了发生机器故障、订单插入情况下的重调度以及在线调度等动态调度的实例仿真,结果表明对于这些问题,HIS算法的求解效果均优于调度规则,特别是在故障重调度中,HIS算法重调度前后的Makespan一致度达97.6%,说明系统能够灵活和有效地处理混合流水车间动态调度问题。 相似文献
11.
Simultaneous transmission of multiple high quality video streams from a server to the clients is becoming an increasingly
important class of traffic in a network of workstations or cluster environment. With a powerful symmetric multiprocessor (SMP)
as the server and a high-speed network, such transmission is practicable from a hardware point of view. However, the actual
construction of such a video data server system entails tackling a number of difficult problems related to the provision of
strict quality of service (QoS) guarantees. Among others, the smoothing and scheduling of multiple video packet streams are
two crucial issues. Smoothing is concerned with reducing the rate variability of video streams in view of the fact that video
data are usually compressed in a variable bit rate fashion. Scheduling is important to guarantee the requested QoS levels
while maximizing the utilization of the resources. Although much work on smoothing has been done, it is not clear which scheduling
scheme is suitable for multiplexing smoothed video data to the network. In this paper we present an extensive performance
study of the EDF and RM scheduling algorithms which are modified to provide QoS guarantees for smoothed video data. With a
probabilistic definition of QoS, admission control conditions are incorporated into the two algorithms. Furthermore, a counter-based
scheduling module is included as the core scheduling mechanism which adaptively adjusts the actual QoS levels assigned to
requests. Our theoretical analysis of the two modified algorithms, called QEDF and QRM, shows that the QRM algorithm is more
robust than the QEDF algorithm for different workload and utilization conditions. We also propose to use a new metric called
meta-QoS to quantify the overall performance of a packet scheduler given a set of simultaneous requests. In our experiments
based on an SMP-based Linux platform, we find that the QRM algorithm can sustain a rather stable level of meta-QoS even when
the workload and utilization levels are increased. On the other hand, the QEDF algorithm, due to its conservative admission
control policy, is found to be not suitable for a high level of utilization and a large number of requests. In view of the
lower complexity of the QRM algorithm, it seems that the QRM approach is a more suitable candidate for packet scheduling in
the client-server environment considered in our study.
相似文献
Yu-Kwong Kwok (Corresponding author)Email: |
12.
《Computer Networks》1999,31(18):1879-1889
This paper studies an alternative scheduling mechanism of general limited service discipline for a distributed communication system, where the distributed system has a modular architecture and the module has tasks in the queue. We successfully analyze the system by way of imbedded Markov chains and use a recursive method to derive the mean waiting time of task. The arrival processes for modules are assumed to be Poisson processes; the service time of a task in queues and the walking time between queues are assumed to be generally distributed. We also presents an optimal-pattern design of the general limited scheduling mechanism for the distributed communication system via a genetic algorithm. A distributed communication system, if designed with the general limited scheduling mechanism and its optimal pattern, can be flexible to meet the system requirements as much as possible. 相似文献
13.
14.
Xiaoyong Tang Kenli Li Renfa Li Bharadwaj Veeravalli 《Journal of Parallel and Distributed Computing》2010
Heterogeneous computing systems are promising computing platforms, since single parallel architecture based systems may not be sufficient to exploit the available parallelism with the running applications. In some cases, heterogeneous distributed computing (HDC) systems can achieve higher performance with lower cost than single-machine supersystems. However, in HDC systems, processors and networks are not failure free and any kind of failure may be critical to the running applications. One way of dealing with such failures is to employ a reliable scheduling algorithm. Unfortunately, most existing scheduling algorithms for precedence constrained tasks in HDC systems do not adequately consider reliability requirements of inter-dependent tasks. In this paper, we design a reliability-driven scheduling architecture that can effectively measure system reliability, based on an optimal reliability communication path search algorithm, and then we introduce reliability priority rank (RRank) to estimate the task’s priority by considering reliability overheads. Furthermore, based on directed acyclic graph (DAG) we propose a reliability-aware scheduling algorithm for precedence constrained tasks, which can achieve high quality of reliability for applications. The comparison studies, based on both randomly generated graphs and the graphs of some real applications, show that our scheduling algorithm outperforms the existing scheduling algorithms in terms of makespan, scheduling length ratio, and reliability. At the same time, the improvement gained by our algorithm increases as the data communication among tasks increases. 相似文献
15.
Xiaofeng Yu Yan Zhang Tian Zhang Linzhang Wang Jun Hu JianHua Zhao Xuandong Li 《Information Systems Frontiers》2007,9(4):391-409
The growing scale and complexity of the enterprise computing systems under distributed and heterogeneous environments present
new challenges to system development, integration, and maintenance. In this paper, we present a model driven Web service development
framework to combat these challenges. The framework capitalizes on the unified modeling language (UML) profile for enterprise
distributed object computing (EDOC), MDA (model-driven architecture) and Web services. Within the framework, firstly, a general
PIM (platform independent models) is created using the EDOC CCA structural specification and CCA choreography specification
which defines the general functions of a system. Secondly, the general PIM is broken down into sub-PIMs according to functional
decomposition, each of which can provide service independently and will be implemented in a Web service. Thirdly, all of the
PIMs are transformed to Web service interface models for publication and invoking. Afterward, transform each PIM to a BPEL
specified Web service orchestration model. Finally, supported by model transform techniques, the sub EDOC PIMs are implemented
into Web services on specific platforms. Automatic model transformation is the key to this framework, therefore, the transformation
from EDOC CCA models to WSDL specified Web service interface models and the transformation from EDOC CCA models to BPEL specified
Web service orchestration models are deeply discussed, and the detailed transformation rules are proposed. A case study is
also provided to demonstrate the effectiveness of these rules and the merits of this framework.
相似文献
Xuandong Li (Corresponding author)Email: |
16.
Pung Hung Keng Hsu Wynne Sapkota B.S. Wong W.C. 《Multimedia Tools and Applications》2000,12(2-3):209-233
Advance object oriented computing platform such as the Common Object Request Broker Architecture (CORBA) provides a conducive and standardized framework for the development of distributed applications. Most of the off-the-shelf CORBA are implemented over legacy network transports and distributed processing platforms such as TCP/IP and RPC. They are not suitable for real-time applications due to their high processing overheads, and lack of features and mechanisms in supporting quality of service both at the network level and at the end-host level. To overcome this limitation we have designed and implemented a CORBA-based Real Time Stream Service (RTSS) that allows real-time streams to be managed through the CORBA channel but by-passing the heavy CORBA protocol stacks. RTSS aims to achieve an integrated QOS framework that incorporates both host scheduling and end-to-end network-level QOS to better support the processing of distributed multimedia applications over ATM networks. For host scheduling, a novel scheme of frequency-based scheduling mechanism has been proposed to cope with dynamic CPU load condition. The scheme has been implemented for a stand-alone host and will be extended to the networked environment. At the network-level QOS, RTSS provides object-oriented application programming interfaces (APIs) which guarantee end-to-end QOS when operating directly over ATM adaptation layers. The benefits of RTSS for the development of real-time multimedia distributed applications are demonstrated through a number of experiments. 相似文献
17.
High-performance parallel and scientific applications are composed of multiple processes running on distinct CPUs that communicate
frequently. Due to the synchronization needs of such applications, performance is greatly hampered if their processes are
not scheduled simultaneously on the CPUs. Implicit coscheduling (ICS) is a well-known technique to address this problem in
multi-programmed clusters, however, traditional ICS schemes do not incorporate steps to adequately deal with priority boost
conflicts, leading to significantly degraded performance. In this paper, we propose the use of runtime difference in contention across nodes to provide more sophisticated coscheduling decisions in response to the conflicts. We also present a novel coscheduling
scheme termed PROC (Process ReOrdering-based Coscheduling) that adaptively regulates the scheduling sequence of conflicting
processes based on the rescheduling latency of their correspondents in remote nodes. We perform extensive simulation-based
experiments using both synthetic and realistic workloads to analyze the performance of PROC compared to alternatives such
as local scheduling, a widely used batch scheduling, gang scheduling, and existing ICS schemes. The results show that all
ICS schemes commonly experience priority boost conflicts, and that the proposed PROC significantly outperforms other ICS alternatives
(or batch scheduling) by up to 50.4% (or 72.5%) in the average job response time. This improvement is achieved by reducing
wasted idle time and spinning time without sacrificing fairness.
相似文献
Seung-Ryoul MaengEmail: |
18.
F. Berman H. Casanova A Chien K. Cooper H. Dail A. Dasgupta W. Deng J. Dongarra L. Johnsson K. Kennedy C. Koelbel B. Liu X. Liu A. Mandal G. Marin M. Mazina J. Mellor-Crummey C. Mendes A. Olugbile M. Patel D. Reed Z. Shi O. Sievert H. Xia A. YarKhan 《International journal of parallel programming》2005,33(2-3):209-229
The goal of the Grid Application Development Software (GrADS) Project is to provide programming tools and an execution environment to ease program development for the Grid. This paper presents recent extensions to the GrADS software framework: a new approach to scheduling workflow computations, applied to a 3-D image reconstruction application; a simple stop/migrate/restart approach to rescheduling Grid applications, applied to a QR factorization benchmark; and a process-swapping approach to rescheduling, applied to an N-body simulation. Experiments validating these methods were carried out on both the GrADS MacroGrid (a small but functional Grid) and the MicroGrid (a controlled emulation of the Grid). 相似文献
19.
In this paper we present an application of computational reflection in the programming oftime-dependent systems. A time-dependent system performs its tasks according to timing specifications specified within the system or imposed from outside the system. Reflective techniques can be applied to programming time-dependent systems because (1) some application programs require the introduction of a new language construct for specifying timing requirements and (2) different applications may require domain-specific scheduling algorithms. To allow a programmer to add or modify language constructs or scheduling algorithms, however, a clear reflective architecture and program interfaces must be provided. This paper proposes a concurrent object-based reflective architecture (R 2 architecture) for time-dependent computing. This architecture is based on anindividual reflection scheme and introduces new meta-level objects (real-time meta objects) that are responsible for time-dependent capabilities. An alarm-clock object and a scheduler object are introduced, and message protocols between them and real-time meta objects are defined. We implemented this architecture on ABCL/R2 and created the Sampled Sound Player program as an application. With this application we provided three different scheduler objects and measured the impact of different scheduling algorithms on sound playback. The measured results show that a scheduler with more complex computations at the meta level exhibited less scheduling overhead, thus was capable of better sound playback. The other example, Time-dependent Graceful Degradation Scheme, demonstrates the programming of functionality degradation triggered by failure to satisfy timing specifications. 相似文献
20.
受恶劣天气影响的船舶调度是一个非常复杂的优化问题,也是班轮公司重点关注的问题之一。为此,针对某航运网络上的一家班轮公司的所有营运船舶,以获知设计的多阶段重调度机制时段内最新预报的天气信息和这些船舶的实时位置为前提,重点考虑班轮船期表的限制并兼顾港口间航速变化和船舶容量等现实约束,构建了以固定计划期内所有船舶的航运总成本最小为优化目标的非线性数学模型,并设计了嵌入基因修复算子的改进遗传算法用于求解该模型。由此,可以给出集成租船直运、跨航线调船、反挂和货物中转等解决策略的最佳多阶段重调度方案。通过对大、中、小规模的算例进行实验,实验结果表明,可知与传统等待办法相比,多阶段重调度节约了总航运成本的15%以上,验证了所提模型和方案的有效性;与Cplex相比,改进遗传算法的运算效率大大提高,且偏差值均在5%以内,而与蚁群优化(ACO)算法、禁忌搜索(TS)算法、量子差分进化(QDE)算法相比,改进遗传算法能在有效时间内降低10%左右的成本,验证了算法的科学性。所提方法可为班轮公司的实际船舶调度提供参考。 相似文献