An experts approach to strategy selection in multiagent meeting scheduling

In the multiagent meeting scheduling problem, agents negotiate with each other on behalf of their users to schedule meetings. While a number of negotiation approaches have been proposed for scheduling meetings, it is not well understood how agents can negotiate strategically in order to maximize their users’ utility. To negotiate strategically, agents need to learn to pick good strategies for negotiating with other agents. In this paper, we show how agents can learn online to negotiate strategically in order to better satisfy their users’ preferences. We outline the applicability of experts algorithms to the problem of learning to select negotiation strategies. In particular, we show how two different experts approaches, plays [3] and Exploration–Exploitation Experts (EEE) [10] can be adapted to the task. We show experimentally the effectiveness of our approach for learning to negotiate strategically.     

Parallel algorithms for certain matrix computations

The complexity of performing matrix computations, such as solving a linear system, inverting a nonsingular matrix or computing its rank, has received a lot of attention by both the theory and the scientific computing communities. In this paper we address some “nonclassical” matrix problems that find extensive applications, notably in control theory. More precisely, we study the matrix equations AX + XA^T = C and AX − XB = C, the “inverse” of the eigenvalue problem (called pole assignment), and the problem of testing whether the matrix [B AB … Aⁿ⁻¹ B] has full row rank. For these problems we show two kinds of PRAM algorithms: on one side very fast, i.e. polylog time, algorithms and on the other side almost linear time and processor efficient algorithms. In the latter case, the algorithms rely on basic matrix computations that can be performed efficiently also on realistic machine models.     

Overrun handling approaches for overload-prone soft real-time systems

Traditional overrun handling approaches for real-time systems enforce some isolation property at the job or task level. This paper shows that by “relaxing” task isolation, it is possible to efficiently deal with overruns in soft real-time systems with highly variable task execution times and proposes Randomized Dropping (RD), a novel overrun handling mechanism. RD is able to bound task overruns in a probabilistic manner, thus providing “soft” task isolation. The paper shows how to combine RD with priority-driven and rate-based scheduling algorithms, and how to analyze the resulting system. Performance evaluation and comparison between simulation and analytical results are discussed.     

Integration of neural networks and genetic algorithms for an intelligent manufacturing controller

This paper addresses the development and implementation of a “controller” for a single manufacturing machine. This prototype will serve as an important tool to study the integration of several functions and the utilization of status data to evaluate scheduling and control decision alternatives. The emphasis is on creating a prediction capability to aid in assessing the long-term system performance impact resulting from decisions made and environmental changes. This prediction capability is implemented by using neural networks, simulation, and genetic algorithms. Neural networks predict the behavior of different sequencing policies available in the system. The contribution of the genetic algorithms to the decision-making process is the development of a “new” scheduling rule based on a “building blocks” procedure initiated by the neural networks     

A personal meeting scheduling agent

When setting up a meeting, meeting participants need to reach a mutual agreement to hold the meeting subject to their personal constraints and preferences. It is a time-consuming process, and a variety of calendaring applications are in use assisting users to schedule meetings. Software applications failed to overcome the constraints of the traditional-scheduling process and works as a supporting tool for managing meeting information. One of the main constraints in automated scheduling is the unavailability of a standard structured communication protocol. In addition, automated scheduling requires other issues to be considered such as automated decision-making paradigm, negotiation strategy selection mechanism, etc. This paper proposes a personal meeting scheduling agent (PMSA) and a personal meeting scheduling protocol (PMSP). PMSP is embedded in the PMSA for handling bilateral and multilateral negotiations. PMSA is designed using model-based, goal-based methodology. Additionally, PMSP is designed following a structured negotiation protocol influenced by simultaneous response protocol. To evaluate all meeting invitations and to make decisions subject to users’ preferences, participants’ profiles, and the schedule availability, this paper utilizes the naïve Bayes model of maximum likelihood Estimation. The PMSP goal is to automatically make decisions and select the appropriate negotiation strategies to avoid or resolve possible meeting conflicts. To demonstrate the feasibility of the proposed PMSP, a simulation environment with experimental results is presented.     

A robot-task conformance index for the design of robotized cells

A robot-task conformance index is introduced. It applies to any manipulator and a broad scope of tasks. Bounded in the [0, 1] range, this dimensionless index is defined within or outside singularities, and remains invariant against changes in units for translations or rotations. It is based on the simultaneous diagonalization of quadratic forms accounting for the “capabilities” of the robot and the “constraints” of the task. The structural and joint properties of the robot are formulated as a repeatability ellipsoid. A sufficient task ellipsoid is construed from the task's domain of constraints. Following the simultaneous diagonalization of both robot and task ellipsoids, minimum containing and maximum contained ellipsoids are deduced. Appropriate volume ratios of these four ellipsoids define the conformance index. Calculations performed in the diagonalized space reduce the computational burden.     

Coordinating patient preferences through automated negotiation: A multiagent systems model for diagnostic services scheduling

This paper presents a multiagent systems model for patient diagnostic services scheduling. We assume a decentralized environment in which patients are modeled as self-interested agents who behave strategically to advance their own benefits rather than the system wide performance. The objective is to improve the utilization of diagnostic imaging resources by coordinating patient individual preferences through automated negotiation. The negotiation process consists of two stages, namely patient selection and preference scheduling. The contract-net protocol and simulated annealing based meta-heuristics are used to design negotiation protocols at the two stages respectively. In terms of game theoretic properties, we show that the proposed protocols are individually rational and incentive compatible. The performance of the preference scheduling protocol is evaluated by a computational study. The average percentage gap analysis of various configurations of the protocol shows that the results obtained from the protocol are close to the optimal ones. In addition, we present the algorithmic properties of the preference scheduling protocol through the validation of a set of eight hypotheses.     

Efficient algorithms for automatic viewer orientation

The calculation of a perspective image of an object involves the position and orientation of the viewer. In many graphics applications the viewpoint and object are fixed, and an orientation is sought in which the object is “centered” in the field of view. Previous work has proposed that the viewing direction be the axis of the narrowest circular cone emanating from the viewpoint and containing the object, and has shown how this direction can be calculated based on the viewpoint and a set of n object points which includes the object's extreme points. This paper presents algorithms which efficiently accomplish this task, in O(n) average and O(n log(n)) worst-case time. The orientation problem is converted into a problem in spherical geometry, and the proposed algorithms are based on existing algorithms for the analogous plane geometry problems.     

A heuristic algorithm for group scheduling

Group technology is a rapidly developing productivity improvement tool that can have a significant impact on the development of totally integrated manufacturing facilities and flexible manufacturing systems. Production scheduling associated with group technology is called “Group Scheduling”. There are many heuristic algorithms developed for general job shop applications based on unrealistic hypothesis, complicated computations etc., which are not addressed to group scheduling. In this paper, from the existing algorithms for group scheduling, a heuristic algorithm has been developed and programmed for computer/microcomputer applications. The developed algorithm has been used to determine the optimal group and the optimal job sequence for a batch type production process with functional layout. The developed algorithm is far simpler and easier to compute, compared to the other similar heuristic algorithms and certainly in comparison to other optimization methods such as branch and bound method.     

Keynote paper: Architectures for integrating manufacturing activities and enterprises

This paper is a summary of the major technical report (Williams et al., 1993) of the IFAC/IFIP Task Force on Architectures for Integrating Manufacturing Activities and Enterprises. It presents a synopsis of the investigations of pertinent architectures undertaken, and the findings generated relating to the suitability of various architectures for the integration task. It also presents the Task Force's recommendations for achieving a “complete” architecture in terms of the necessary capabilities by “completing” a currently available architecture. The Task Force also outlined how a “best” architecture could be achieved by selecting and combining the best features of the available architectures.     

Complex random sample scheduling and its application to an N/M/F/Fmax problem

“Complex Random Sample Scheduling(CRSS)” was proposed in this paper as an efficient heuristic method for solving any permutation scheduling problems. To show the effectiveness of the proposed CRSS, it was applied to an N-job, M-machine, permutation flowshop scheduling problem to minimize makespan, N/M/F/F_max. Numerical experiments made it clear that the proposed CRSS provides a schedule very close to the near-optimal schedule obtained by the existing promising heuristic methods such as taboo search and simulated annealing, within less computation time than these heuristic methods.     

Modelling topological spatial relations: Strategies for query processing

This paper investigates the processing of spatial queries with topological constraints, for which current database solutions are inappropriate. Topological relations, such as disjoint, meet, overlap, inside, and contains, have been well defined by the 9-intersection, a comprehensive model for binary topological relations. We focus on two types of queries: (1) “Which objects have a stated topological relation with a given spatial object?” and (2) “What is the topological relation between two given spatial objects?” Such queries are processed at two levels of detail. First, Minimum Bounding Rectangles are used as an approximation of the objects' geometry and as a means of identifying candidates that might satisfy the query. Next, the nine intersections that determine the topological relations between candidate pairs are calculated. We present algorithms for minimizing these computations. Considerable performance can be gained by exploiting the semantics of spatial relations. We also compare the approach for a naive cost model, which assumes that all relations have the same frequency of occurrence, with a refined cost model, which considers the probability of occurrence of the topological relations. The strategies presented here have three key benefits: (1) they are based on a well-defined formalism; (2) they are customizable; and (3) they can take into account important statistical information about the data.     

改进K-means聚类的云任务调度算法

针对云任务调度中存在的效率低、费用高等问题,提出一种基于改进K-means聚类算法的云任务调度算法。依据虚拟资源的硬件属性,使用改进聚类算法对虚拟资源进行聚类划分;计算任务偏好,使不同偏好的任务在不同的聚类中选择资源;考虑到调度费用问题,对每个聚类使用改进后的Min-min算法进行任务调度。针对K-means聚类算法初始聚类中心随机选取,易陷入局部最优解的问题,对聚类算法进行改进。最后,利用云仿真平台CloudSim进行实验,结果表明,与无聚类的调度算法相比,本文提出的算法在执行效率方面有所提高。     

On the almost-sure sample stability of systems with randomly time-varying delays

In a large class of multi-loop control systems, many feedback loops are “closed” through a time-shared digital computer, by means of algorithms which require information from sources which are sampled at a rate which is not synchronized with the sampling of the individual “plants”. This mis-synchronization, coupled with variations in the computer's task load caused by “interrupts”, results in a randomly time-varying delay in the closing of the various feedback loops. Consequently, the dynamics of each controlled “plant” in such a system may be modeled by means of a stochastic delay-differential equation. This paper presents some new research results concerning the sample stability, as opposed to statistical, or ensemble stability, of linear stochastic delay-differential equations.     

An optimization approach for decentralized QoS‐based scheduling based on utility and pricing in Grid computing

This paper presents an optimization approach for decentralized Quality of Service (QoS)‐based scheduling based on utility and pricing in Grid computing. The paper assumes that the quality dimensions can be easily formulated as utility functions to express quality preferences for each task agent. The utility values are calculated by the user‐supplied utility function that can be formulated with the task parameters. The QoS constraint Grid resource scheduling problem is formulated into a utility optimization problem. The QoS‐based Grid resource scheduling optimization is decomposed into two subproblems by applying the Lagrangian method. In the Grid, a Grid task agent acts as a consumer paying for the Grid resource and the resource providers receive profits from task agents. A pricing‐based QoS scheduling algorithm is used to perform optimally decentralized QoS‐based resource scheduling. The experiments investigate the effect of the QoS metrics on the global utility and compare the performance of the proposed algorithm with other economical Grid resource scheduling algorithms. Copyright © 2006 John Wiley & Sons, Ltd.     

Collaborative recommender systems: Combining effectiveness and efficiency

Recommender systems base their operation on past user ratings over a collection of items, for instance, books, CDs, etc. Collaborative filtering (CF) is a successful recommendation technique that confronts the “information overload” problem. Memory-based algorithms recommend according to the preferences of nearest neighbors, and model-based algorithms recommend by first developing a model of user ratings. In this paper, we bring to surface factors that affect CF process in order to identify existing false beliefs. In terms of accuracy, by being able to view the “big picture”, we propose new approaches that substantially improve the performance of CF algorithms. For instance, we obtain more than 40% increase in precision in comparison to widely-used CF algorithms. In terms of efficiency, we propose a model-based approach based on latent semantic indexing (LSI), that reduces execution times at least 50% than the classic CF algorithms.     

网格环境下一种可调目标的启发式调度策略

针对网格环境下不同类型的任务执行时间相差较大的问题,提出了基于任务平均执行时间的忍耐度的概念,重新构造了启发式规则,体现了任务QoS的要求;并将这种服务质量的需求与任务完成时间相结合,给出了一个可调节的局部目标函数,实现了一种基于任务完成时间和任务服务质量的启发式调度算法OA-Sufferage;最后,给出了服务率(service ratio)的概念和定义,定量地衡量任务得到的服务质量.实验结果表明,该策略优先调度那些等待时间相对于执行时间较大的任务,提高了任务的服务率;而且可以通过调节局部目标函数中的偏好因子(preference factor),追求任务完成时间和QoS的不同目标,更加适合开放复杂的网格环境.     

A heuristic index for selecting similar categories in multiple correspondence analysis applied to living donor kidney transplantation

This work introduces a heuristic index (the “tolerance distance”) to define the “closeness” of two variable categories in multiple correspondence analysis (MCA). This index is a weighted Euclidean distance where weightings are based on the “importance” of each MCA axis, and variable categories were considered to be associated when their distances were below the tolerance distance. This approach was applied to a renal transplantation data. The analysed variables were allograft survival and 13 of its putative predictors. A bootstrap-based stability analysis was employed for assessing result reliability. The method identified previously detected associations within the database, such as that between race of donors and recipients, and that between HLA match and Cyclosporine use. A hierarchical clustering algorithm was also applied to the same data, allowing for interpretations similar to those based on MCA. The defined tolerance distance could thus be used as an index of “closeness” in MCA, hence decreasing the subjectivity of interpreting MCA results.     

Constrained multibody system dynamics an automated approach

The governing equations for constrained multibody systems are formulated in a manner suitable for their automated, numerical development and solution. Specifically, the “closed loop” problem of multibody chain systems is addressed.

The governing equations are developed by modifying dynamical equations obtained from Lagrange's form of d'Alembert's principle. This modification, which is based upon a solution of the constraint equations obtained through a “zero eigenvalues theorem,” is, in effect, a contraction of the dynamical equations.

It is observed that, for a system with n generalized coordinates and m constraint equations, the coefficients in the constraint equations may be viewed as “constraint vectors” in n-dimensional space. Then, in this setting the system itself is free to move in the n−m directions which are “orthogonal” to the constraint vectors.     

The evolution of the gingerbread man

Two versions of the evolution of the Gingerbread Man for the iteration z → z^x + c are presented. A previously published version shows an asymmetric evolution as positive real x increases, while a new version shows a symmetric evolution, and several interesting features. Fractal “growth” is described that occurs along certain “shock” lines with this new evolution. A floating “object” appears while approaching certain positive even integer values of x. Finally, a few comments are made about images created from negative values of x.