Gallop: The Benefits of Wide-Area Computing for Parallel Processing

Internet computing has emerged, as an attractive paradigm for many applications that require access to distributed resources such as telemedicine, collaboratories, and transaction systems. For applications that require high performance, the Internet is assumed to be inappropriate. However, it is possible to obtain high performance for parallel scientific applications in an Internet environment. A wide-area scheduling system called Gallop has been developed to exploit opportunities for high performance using remote Internet resources for these applications. This paper describes the Gallop architecture and scheduling model, and performance results obtained for three parallel applications. The initial results indicate that wide-area parallel processing can lead to better performance even with Internet technology, but that current Internet bandwidth is a major bottleneck for file and binary transfer. This overhead limits the class of suitable applications to those that are large-grained or that will be run multiple times to amortize the transfer cost.     

Distributed constraint optimization with MULBS: A case study on collaborative meeting scheduling

This paper introduces MULBS, a new DCOP (distributed constraint optimization problem) algorithm and also presents a DCOP formulation for scheduling of distributed meetings in collaborative environments. Scheduling in CSCWD can be seen as a DCOP where variables represent time slots and values are resources of a production system (machines, raw-materials, hardware components, etc.) or management system (meetings, project tasks, human resources, money, etc). Therefore, a DCOP algorithm must find a set of variable assignments that maximize an objective function taking constraints into account. However, it is well known that such problems are NP-complete and that more research must be done to obtain feasible and reliable computational approaches. Thus, DCOP emerges as a very promising technique: the search space is decomposed into smaller spaces and agents solve local problems, collaborating in order to achieve a global solution. We show with empirical experiments that MULBS outperforms some of the state-of-the-art algorithms for DCOP, guaranteeing high quality solutions using less computational resources for the distributed meeting scheduling task.     

IPSS: A Hybrid Approach to Planning and Scheduling Integration

Recently, the areas of planning and scheduling in artificial intelligence (AI) have witnessed a big push toward their integration in order to solve complex problems. These problems require both reasoning on which actions are to be performed as well as their precedence constraints (planning) and the reasoning with respect to temporal constraints (e.g., duration, precedence, and deadline); those actions should satisfy the resources they use (scheduling). This paper describes IPSS (integrated planning and scheduling system), a domain independent solver that integrates an AI planner that synthesizes courses of actions with constraint-based techniques that reason based upon time and resources. IPSS is able to manage not only simple precedence constraints, but also more complex temporal requirements (as the Allen primitives) and multicapacity resource usage/consumption. The solver is evaluated against a set of problems characterized by the use of multiple agents (or multiple resources) that have to perform tasks with some temporal restrictions in the order of the tasks or some constraints in the availability of the resources. Experiments show how the integrated reasoning approach improves plan parallelism and gains better makespans than some state-of-the-art planners where multiple agents are represented as additional fluents in the problem operators. It also shows that IPSS is suitable for solving real domains (i.e., workflow problems) because it is able to impose temporal windows on the goals or set a maximum makespan, features that most of the planners do not yet incorporate     

Optimal-in-expectation redistribution mechanisms

Many important problems in multiagent systems involve the allocation of multiple resources among the agents. If agents are self-interested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-known VCG mechanism allocates the items efficiently, is strategy-proof (agents have no incentive to lie), and never runs a deficit. Nevertheless, the agents may have to make large payments to a party outside the system of agents, leading to decreased utility for the agents. Recent work has investigated the possibility of redistributing some of the payments back to the agents, without violating the other desirable properties of the VCG mechanism.Previous research on redistribution mechanisms has resulted in a worst-case optimal redistribution mechanism, that is, a mechanism that maximizes the fraction of VCG payments redistributed in the worst case. In contrast, in this paper, we assume that a prior distribution over the agents' valuations is available, and our goal is to maximize the expected total redistribution.In the first part of this paper, we study multi-unit auctions with unit demand. We analytically solve for a mechanism that is optimal among linear redistribution mechanisms. We also propose discretized redistribution mechanisms. We show how to automatically solve for the optimal discretized redistribution mechanism for a given discretization step size, and show that the resulting mechanisms converge to optimality as the step size goes to zero. We present experimental results showing that for auctions with many bidders, the optimal linear redistribution mechanism redistributes almost everything, whereas for auctions with few bidders, we can solve for the optimal discretized redistribution mechanism with a very small step size.In the second part of this paper, we study multi-unit auctions with nonincreasing marginal values. We extend the notion of linear redistribution mechanisms, previously defined only in the unit demand setting, to this more general setting. We introduce a linear program for finding the optimal linear redistribution mechanism. This linear program is unwieldy, so we also introduce one simplified linear program that produces relatively good linear redistribution mechanisms. We conjecture an analytical solution for the simplified linear program.     

基于经济模型的资源代理

网格计算是为解决大规模资源密集型问题而提出的新一代计算平台,是当前并行和分布处理技术的一个发展方向,而资源管理是计算网格的关键技术之一。对各种各样可利用资源的整合和管理是网格应用的基础,而资源的分布性、动态性、异构性、自治性和需要协调一致性使得网格资源的管理调度成为一个棘手的问题。目前基于市场的经济资源管理和调度算法非常适合计算网格中的资源管理问题,但有调度价格不能更改、负载平衡等问题。文中提出了“网格环境下基于经济模型的资源代理”,依靠多维QoS指导的调度策略和经济模型的启发式调节资源价格,改进和优化计算网格资源的分配。     

Tractable combinatorial auctions and b-matching

Auctions are the most widely used strategic game-theoretic mechanisms in the Internet. Auctions have been mostly studied from a game-theoretic and economic perspective, although recent work in AI and OR has been concerned with computational aspects of auctions as well. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging type of auctions. Combinatorial auctions are auctions where agents may submit bids for bundles of goods. Given that finding an optimal allocation of the goods in a combinatorial auction is in general intractable, researchers have been concerned with exposing tractable instances of combinatorial auctions. In this work we expose the use of b-matching techniques in the context of combinatorial auctions, and apply them in a non-trivial manner in order to introduce polynomial solutions for a variety of combinatorial auctions.     

Communication infrastructure in distributed scheduling

The emergence of distributed artificial intelligent (DAI) introduced a new approach to solve scheduling problems by a set of scheduling systems that interact with each other in the problem-solving process. In this paper, we describe a communication infrastructure to handle connection and communication between distributed Internet scheduling systems for distributed applications. First, we present an agent model of distributed scheduling systems where agents can communicate and coordinate activities with each other via an agent communication language. Then, we define the syntax and semantics for the agent communication languages, and negotiation mechanism. Following that, we discuss the design and development of the prototype for the multi-agent scheduling systems. We conclude with a discussion of communication issues for heterogeneous agent-based scheduling systems to solve distributed scheduling problems.     

A framework for meta-level control in multi-agent systems

Sophisticated agents operating in open environments must make decisions that efficiently trade off the use of their limited resources between dynamic deliberative actions and domain actions. This is the meta-level control problem for agents operating in resource-bounded multi-agent environments. Control activities involve decisions on when to invoke and the amount to effort to put into scheduling and coordination of domain activities. The focus of this paper is how to make effective meta-level control decisions. We show that meta-level control with bounded computational overhead allows complex agents to solve problems more efficiently than current approaches in dynamic open multi-agent environments. The meta-level control approach that we present is based on the decision-theoretic use of an abstract representation of the agent state. This abstraction concisely captures critical information necessary for decision making while bounding the cost of meta-level control and is appropriate for use in automatically learning the meta-level control policies.     

A graphical formalism for mixed multi-unit combinatorial auctions

Mixed multi-unit combinatorial auctions are auctions that allow participants to bid for bundles of goods to buy, for bundles of goods to sell, and for transformations of goods. The intuitive meaning of a bid for a transformation is that the bidder is offering to produce a set of output goods after having received a set of input goods. To solve such an auction the auctioneer has to choose a set of bids to accept and decide on a sequence in which to implement the associated transformations. Mixed auctions can potentially be employed for the automated assembly of supply chains of agents. However, mixed auctions can be effectively applied only if we can also ensure their computational feasibility without jeopardising optimality. To this end, we propose a graphical formalism, based on Petri nets, that facilitates the compact represention of both the search space and the solutions associated with the winner determination problem for mixed auctions. This approach allows us to dramatically reduce the number of decision variables required for solving a broad class of mixed auction winner determination problems. An additional major benefit of our graphical formalism is that it provides new ways to formally analyse the structural and behavioural properties of mixed auctions.     

Operational efficiency of decentralized Internet auction mechanisms

The recent consumer-to-consumer (C2C) Internet auction boom at eBay, Yahoo, Amazon, and other sites has added new theoretical challenges to the science of auctions. This paper uses experiments with economically-motivated human subjects to measure the operational efficiency of decentralized Internet auction mechanisms as they compare to centralized double auction mechanisms. Subjects are recruited randomly from the undergraduate population of a large urban university to be buyers or sellers in a simulated trading environment. They are randomly assigned costs and values for 10 units of a virtual product. During the experiment subjects trade these units through computer terminals in auctions similar to those held on eBay and generate profits, which subjects receive at the end of the experiment. The paper uses data from this experiment and previous laboratory experiments to compare operational efficiency and convergence pattern of prices to equilibrium levels in continuous double auctions versus online Internet auctions based on two variables: auction size and time. Experimental results suggest that, because of their decentralized nature, Internet auctions require a few more participants and more time to achieve operational efficiency levels than centralized markets which use continuous double auction mechanisms.     

Secure outsourcing of sequence comparisons

Internet computing technologies, like grid computing, enable a weak computational device connected to such a grid to be less limited by its inadequate local computational, storage, and bandwidth resources. However, such a weak computational device (PDA, smartcard, sensor, etc.) often cannot avail itself of the abundant resources available on the network because its data are sensitive. This motivates the design of techniques for computational outsourcing in a privacy-preserving manner, i.e., without revealing to the remote agents whose computational power is being used either one’s data or the outcome of the computation. This paper investigates such secure outsourcing for widely applicable sequence comparison problems and gives an efficient protocol for a customer to securely outsource sequence comparisons to two remote agents. The local computations done by the customer are linear in the size of the sequences, and the computational cost and amount of communication done by the external agents are close to the time complexity of the best known algorithm for solving the problem on a single machine.     

SANet: a service-agent network for call-center scheduling

We consider a network of service-providing agents, where different agents have different capabilities, availability, and cost to solve problems. These characteristics are particularly important in practice for semi-automated call centers which provide quality customer service in real time. We have developed SANet, a service agent network for call center automation, to serve as an experimental testbed for our research. SANet can select appropriate agents to provide better solutions for customer problems according to the changing capabilities and availability of service agents in the network. It can also add or delete appropriate agents to balance problem-solving quality, efficiency, and cost according to the number and types of incoming customer problems. On this network, each service agent can be a human service agent, an automated software service agent, or a combination of the two. This paper describes the architecture, a problem scheduling algorithm and an agent assignment algorithm on the SANet. We highlight an application in which we apply SANet to a call-center scheduling problem for a cable-TV company. Finally, we show the efficiency and adaptability of our system via experimental results and discuss related works.     

具有惩罚功能的可信机制研究

网格计算是一项新的分布式计算技术,它可以把分散的各种互联网资源集成为一个统一的平台,实现组织间的资源共享和协作。在实际环境中,网格作业调度必须考虑各个独立、自治组织的个体利益。针对这个问题,本文描述了一种适用于可信机制运作的网格体系结构,并阐述了它的功能组件,同时提出了具有惩罚功能的可信机制,并通过模拟实验证明了算法的有效性。     

基于反馈控制的实时调度算法设计与实现

传统的实时调度算法在运行环境不可预测的嵌入式操作系统中应用时,要求系统预留大量的CPU资源,而且在稳定性和精确性等方面存在不足.文章为解决这些问题提出了基于反馈控制的实时调度算法,仿真表明该算法相对传统算法而言,提高了系统的CPU利用率,并降低了任务的截止期限错过率.     

Cooperative scheduling mechanism for large-scale peer-to-peer computing systems

Over recent years, peer-to-peer (P2P) systems have become an important part of Internet. Millions of users have been attracted to their structures and services. P2P computing is a distributed computing paradigm that uses Internet to connect thousands, or even millions, of users into a single large virtual computer based on the sharing of computational resources. One of the most critical aspects to the design of P2P computing systems is the development of scheduling techniques to manage the computational resources efficiently and in a scalable way. This paper proposes a cooperative scheduling mechanism with a two-level topology designed to work on large-scale distributed computing P2P systems. Our main contribution is proposing three criteria that only use local information to schedule tasks thus providing scalability to the overall scheduling system. By setting up these three criteria, the system can be easily adapted to work efficiently with very different kinds of distributed applications. The extensive experimentation carried out justifies the importance of good scheduling in such heterogeneous systems, but also emphasizes the importance of having a scheduling algorithm capable of being adapted to the requirements of different kinds of application.     

Resource scheduling and load balancing in distributed robotic control systems

This paper describes the latest advances made to a software architecture designed to control multiple miniature robots. As the robots themselves have very limited computational capabilities, a distributed control system is needed to coordinate tasks among a large number of robots. Two of the major challenges facing such a system are the scheduling of access to system resources and the distribution of work across multiple workstations. This paper discusses solutions to these problems in the context of a distributed surveillance task.     

Binary integer programming formulations for scheduling in market-driven foundries

This paper describes the development and solution of binary integer formulations for production scheduling problems in market-driven foundries. This industrial sector is comprised of small and mid-sized companies with little or no automation, working with diversified production, involving several different metal alloy specifications in small tailor-made product lots. The characteristics and constraints involved in a typical production environment at these industries challenge the formulation of mathematical programming models that can be computationally solved when considering real applications. However, despite the interest on the part of these industries in counting on effective methods for production scheduling, there are few studies available on the subject. The computational tests prove the robustness and feasibility of proposed models in situations analogous to those found in production scheduling at the analyzed industrial sector.     

History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence

In this paper, we extend job scheduling models to include aspects of history-dependent scheduling, where setup times for a job are affected by the aggregate activities of all predecessors of that job. Traditional approaches to machine scheduling typically address objectives and constraints that govern the relative sequence of jobs being executed using available resources. This paper optimises the operations of multiple unrelated resources to address sequential and history-dependent job scheduling constraints along with time window restrictions. We denote this consolidated problem as the general precedence scheduling problem (GPSP). We present several applications of the GPSP and show that many problems in the literature can be represented as special cases of history-dependent scheduling. We design new ways to model this class of problems and then proceed to formulate it as an integer program. We develop specialized algorithms to solve such problems. An extensive computational analysis over a diverse family of problem data instances demonstrates the efficacy of the novel approaches and algorithms introduced in this paper.     

基于分布式深度强化学习的微电网实时优化调度

随着海量新能源接入到微电网中, 微电网系统模型的参数空间成倍增长, 其能量优化调度的计算难度不断上升. 同时, 新能源电源出力的不确定性也给微电网的优化调度带来巨大挑战. 针对上述问题, 本文提出了一种基于分布式深度强化学习的微电网实时优化调度策略. 首先, 在分布式的架构下, 将主电网和每个分布式电源看作独立智能体. 其次, 各智能体拥有一个本地学习模型, 并根据本地数据分别建立状态和动作空间, 设计一个包含发电成本、交易电价、电源使用寿命等多目标优化的奖励函数及其约束条件. 最后, 各智能体通过与环境交互来寻求本地最优策略, 同时智能体之间相互学习价值网络参数, 优化本地动作选择, 最终实现最小化微电网系统运行成本的目标. 仿真结果表明, 与深度确定性策略梯度算法(Deep Deterministic Policy Gradient, DDPG)相比, 本方法在保证系统稳定以及求解精度的前提下, 训练速度提高了17.6%, 成本函数值降低了67%, 实现了微电网实时优化调度.     

计算网格中的资源选择与调度算法

针对文中描述的计算网格资源环境模型,构造了一种分布式的层次型任务调度模型,任务调度分为计算资源站点的选择以及资源站点内部的本地调度两层进行。通过研究该调度模型,提出了一种基于双目标衡量函数的资源选择算法,该算法可以通过设置相关参数动态调节响应时间和价格在总目标中所占比重。试验结果表明能够选择综合满足响应时间和价格这两个目标的计算资源,以适应用户的不同需求。