共查询到20条相似文献,搜索用时 15 毫秒
1.
信任约束下的网格工作流任务调度算法* 总被引:1,自引:0,他引:1
提出了信任约束下的网格工作流任务调度算法。该算法结合直接经验和推荐经验计算资源的信任度,根据任务在候选资源上的执行时间确定关键任务,然后选择满足执行时间和信任综合函数的资源。实验结果表明。该算法不仅缩短了工作流的完成时间,而且提高了调度的成功率。 相似文献
2.
3.
Resource provisioning strategies are crucial for workflow scheduling problems which are widespread in cloud computing. The main challenge lies in determining the amounts of reserved and on-demand resources to meet users’ requirements. In this paper, we consider the cloud workflow scheduling problem with hybrid resource provisioning to minimize the total renting cost, which is NP-hard and has not been studied yet. An iterative population-based meta-heuristic is developed. According to the shift vectors obtained during the search procedure, timetables are computed quickly. The appropriate amounts of reserved and on-demand resources are determined by an incremental optimization method. The utilization of each resource is balanced in a swaying way, in terms of which the probabilistic matrix is updated for the next iteration. The proposed algorithm is compared with modified existing algorithms for similar problems. Experimental results demonstrate effectiveness and efficiency of the proposed algorithm. 相似文献
4.
《Parallel Computing》2013,39(10):567-585
We examine the problem of reliable workflow scheduling with less resource redundancy. As scheduling workflow applications in heterogeneous systems, either for optimizing the reliability or for minimizing the makespan, are NP-Complete problems, we alternatively find schedules for meeting specific reliability and deadline requirements. First, we analyze the reliability of a given schedule using two important definitions: Accumulated Processor Reliability (APR) and Accumulated Communication Reliability (ACR). Second, inspired by the reliability analysis, we present three scheduling algorithms: RR algorithm schedules least Resources to meet the Reliability requirement; DRR algorithm extends RR by further considering the Deadline requirement; and dynamic algorithm schedules tasks dynamically: It avoids the “Chain effect” caused by uncertainties on the task execution time estimates, and relieves the impact from the inaccuracy on failure estimation. Finally, the empirical evaluation shows that our algorithms can save a significant amount of computation and communication resources when performing a similar reliability compared to Fault-Tolerant-Scheduling-Algorithm (FTSA) algorithm. 相似文献
5.
B.M. Worrall 《Computers & Industrial Engineering》1986,11(1-4):199-203
This paper describes the development of a job shop scheduling system, which is based upon dynamic scheduling rules incorporating customer importance and/or order priority under constrained resources. An important part of the system is the development of a forecasting method for determining the estimated completion time for a job by estimating the future work load on the shop. The system has been developed from the analysis of the maintenance operations of a large petrochemical plant. The use of the computer programs which have been developed will be illustrated. 相似文献
6.
研究了工作流中时间分配问题。在具体活动基础上增加标记活动,以记录所在路由分支的资源使用情况; 将时间看作一种不可更新资源,并将时间资源分为私有资源、公有资源和双重资源三类; 提出了一种路由结构的时间资源分析方法和分配算法,根据不同路由分支的特点及初始分配资源在实际执行过程中的使用情况,通过裂变与聚合进行时间资源再分配,保证整个工作流的顺利完成。通过实例说明工作流图中时间资源分配过程。 相似文献
7.
In project scheduling by network analysis, traditional critical path methods fail to include resource considerations. Other methods must be used to allow for resource considerations. This article explores one area of resource considerations: project scheduling under resource constraints. The specific case investigated is the single resource, single project schedule. A model, entitled the GENRES search model, is developed. The model utilizes Brooks Algorithm (BAG) to generate the project schedule. The criteria used are various weighted combinations of ACTIM and ACTRES (Bedworth, Industrial Systems). The best project schedule is that which gives the least project duration.The GENRES model was found effective in finding project durations equal to or less than that of ACTIM, ACTRES or TIMRES (the combination of ACTIM and ACTRES with each given equal weight). The research also found that when the project completion time found by the algorithm approaches the critical path duration, resource leveling may be preferred. 相似文献
8.
Automated Guided Vehicles (AGVs) form a large and important part of the logistics transportation systems in today's industry and are widely used, especially in Europe. Today's AGV-systems offered by global manufacturers almost all operate under some form of centralized control where a single central controller coordinates the entire fleet of AGVs. There is a trend towards decentralized control of these systems where AGVs make individual decisions that promote the flexibility, robustness and scalability of transport. However, its practical implementation seems to be in its infancy. In addition to the lack of practical implementation of decentralized control in industrial AGV-systems, we have observed a research gap in intelligent resource management of AGV-systems, which we have tried to address in previous work by proposing a more intelligent resource management approach. In this paper, we have addressed both the perceived lack of practical decentralized AGV control and the lack of intelligent resource management by proposing a decentralized task allocation algorithm based on sequential single-item auctions, taking into account resource constraints, and in which our intelligent resource management approach from previous work is introduced. We have benchmarked our new approach to a genetic algorithm-based task-allocation solver that uses “threshold-100”-charging as a resource management strategy. The result of the proposal is a decentralized task-allocation architecture under resource constraints that could be used in current AGV-systems to add more decentralized features to the fleet. 相似文献
9.
This paper focuses on task allocation with single-task robots, multi-robot tasks and instantaneous assignment, which has been shown to be strongly NP-hard. Although this problem has been studied extensively, few efficient approximation algorithms have been provided due to its inherent complexity. In this paper, we first provide discussions and analyses for two natural greedy heuristics for solving this problem. Then, a new greedy heuristic is introduced, which considers inter-task resource constraints to approximate the influence between different assignments in task allocation. Instead of only looking at the utility of the assignment, our approach computes the expected loss of utility (due to the assigned robots and task) as an offset and uses the offset utility for making the greedy choice. A formal analysis is provided for the new heuristic, which reveals that the solution quality is bounded by two different factors. A new algorithm is then provided to approximate the new heuristic for performance improvement. Finally, for more complicated applications, we extend this problem to include general task dependencies and provide a result on the hardness of approximating this new formulation. Comparison results with the two natural heuristics in simulation are provided for both formulations, which show that the new approach achieves improved performance. 相似文献
10.
Project scheduling problem is to make a schedule for allocating the loans to a project such that the total cost and the completion time of the project are balanced under some constraints. This paper presents an uncertain project scheduling problem, of which both the duration times and the resources allocation times are uncertain variables. An uncertain programming model with multiple objectives is obtained, whose first objective is to minimize the total cost, and second objective is to minimize the overtime. Genetic algorithm is employed to solve the proposed uncertain project scheduling model, and its efficiency is illustrated by a numerical experiment. 相似文献
11.
12.
针对嵌入式系统中大多数任务执行算法不考虑目标成本问题,提出了一种基于多目标全局约束的任务分配和调度算法。算法使用约束逻辑编程来对任务执行资源如处理单元、通信设备以及代码和数据存储量的使用进行多目标全局约束。算法假设ROM和RAM分别用于代码存储和数据存储,算法还考虑数据在数据存储器中的位置。实验结果表明,尽管在多个约束条件下,提出的任务分配和调度算法无论在代码存储和数据存储量使用方面,还是在对任务有效求解方面都能取得比普遍采用的贪婪调度算法更好的结果。 相似文献
13.
This research investigates the production scheduling problems under maximum power consumption constraints. Probabilistic models are developed to model dispatching-dependent and stochastic machine energy consumption. A multi-objective scheduling algorithm called the energy-aware scheduling optimization method is proposed in this study to enhance both production and energy efficiency. The explicit consideration of the probabilistic energy consumption constraint and the following factors makes this work distinct from other existing studies in the literature: 1) dispatching-dependent energy consumption of machines, 2) stochastic energy consumption of machines, 3) parallel machines with different production rates and energy consumption pattern, and 4) maximum power consumption constraints. The proposed three-stage algorithm can quickly generate near-optimal solutions and outperforms other algorithms in terms of energy efficiency, makespan, and computation time. While minimizing the total energy consumption in the first and second stages, the proposed algorithm generates a detailed production schedule under the probabilistic constraint of peak energy consumption in the third stage. Numerical results show the superiority of the scheduling solution with regard to quality and computational time in real problems instances from manufacturing industry. While the scheduling solution is optimal in total energy consumption, the makespan is within 0.6 % of the optimal on average. 相似文献
14.
Resource allocation cannot reach equilibrium in one‐off game in grid environment because of the bounded rationality of the users. To address this issue, an evolutionary game algorithm for grid resource allocation is proposed in this paper. The evolutionary game theory is introduced to study the selection process of user strategy from the dynamic viewpoint. Firstly, the problem of multiple users competing for a common resource is formulated as a symmetric game. Secondly, replicated dynamic mechanism is used to produce the evolutionary stable point that leads to a satisfied allocation scenario. Finally, the relationships among the evolutionary stable point, valuation functions, and convergence time are discussed in detail. The results of the experiments show that the proposed evolutionary game algorithm is convergent and generates better utility results compared with the classical game algorithm. Copyright © 2009 John Wiley & Sons, Ltd. 相似文献
15.
This paper aims to propose a distributed task allocation algorithm for a team of robots that have constraints on energy resources and operate in an unknown dynamic environment. The objective of the allocation is to maximize task completion ratio while minimizing resource usage. The approach we propose is inspired by the social welfare in economics that helps extend the combined operational lifetime of the team by balancing resource consumptions among robots. This social welfare based task allocation method positions a robot team appropriately in preparedness for dynamic future events and enables to achieve the objectives of the system flexibly depending on the application context. Our simulation-based experiments show that the proposed algorithm outperforms a typical market-based approach in various scenarios. 相似文献
16.
Fabrizio Marinelli Salvatore Nocella Fabrizio Rossi Stefano Smriglio 《Computers & Operations Research》2011
The data exchange between ground stations and satellite constellations is becoming a challenging task, as more and more communication requests must be daily scheduled on a few, expensive stations located all around the Earth. Most of the scheduling procedures adopted in practice cannot cope with such complexity, and the development of optimization-based tools is strongly spurred. 相似文献
17.
In this paper we discuss exact and approximation algorithms for scheduling a single machine with additional non-renewable resource constraints. Given the initial stock levels of some non-renewable resources (e.g., raw materials, fuel, money), and time points along with replenishment quantities, a set of resource consuming jobs has to be scheduled on the machine such that there are enough resources for starting each job, and the makespan is minimized. We show that the problem admits a pseudo-polynomial time algorithm when the number of replenishments is not part of the input, and also present an FPTAS when there is only a single resource, and it is replenished only once. We also describe a PTAS for the problem with a constant number of replenishments. 相似文献
18.
The system capacity for future mobile communication needs to be increased to fulfill the emerging requirements of mobile services and innumerable applications. The cellular topology has for long been regarded as the most promising way to provide the required increase in capacity. However with the emerging densification of cell deployments, the traditional cellular structure limits the efficiency of the resource, and the coordination between different types of base stations is more complicated and entails heavy cost. Consequently, this study proposes frameless network architecture (FNA) to release the cell boundaries, enabling the topology needed to implement the FNA resource allocation strategy. This strategy is based on resource pooling incorporating a new resource dimension-antenna/antenna array. Within this architecture, an adaptive resource allocation method based on genetic algorithm is proposed to find the optimal solution for the multi-dimensional resource allocation problem. Maximum throughput and proportional fair resource allocation criteria are considered. The simulation results show that the proposed architecture and resource allocation method can achieve performance gains for both criteria with a relatively low complexity compared to existing schemes. 相似文献
19.
资源受限项目调度问题(RCPSP)是最具代表性的项目调度问题之一,针对实际情况中考虑资源投入的必要性,建立一种以资源投入为变量的基于广义资源日历约束的项目调度优化模型.首先,引入组合优先关系的概念对广义资源日历的概念和具体内容进行整合和完善,为了避免传统网络图在表示组合优先关系时出现的网络循环等弊端,使用节点表示活动开始和结束的瞬时状态改进节点网络图;其次,考虑活动优先关系、活动持续时间、不可更新资源总量和资源日历约束,以项目工期最短和项目成本最小为优化目标,运用CP优化器求解所建立的多目标优化模型;最后,通过设计仿真算例并进行数值实验验证模型的准确性和高效性. 相似文献