Market-based pricing in grids: On strategic manipulation and computational cost

Grid technologies and the related concepts of utility computing and cloud computing enable the dynamic sourcing of computer resources and services, thus allowing enterprises to cut down on hardware and software expenses and to focus on key competencies and processes. Resources are shared across administrative boundaries, e.g. between enterprises and/or business units. In this dynamic and inter-organizational setting, scheduling and pricing become key challenges. Market mechanisms show promise for enhancing resource allocation and pricing in grids. Current mechanisms, however, are not adequately able to handle large-scale settings with strategic users and providers who try to benefit from manipulating the mechanism. In this paper, a market-based heuristic for clearing large-scale grid settings is developed. The proposed heuristic and pricing schemes find an interesting match between scalability and strategic behavior.     

A cops and robber game in multidimensional grids

We theoretically analyze the ‘cops and robber’ game for the first time in a multidimensional grid. It is shown that in an n-dimensional grid, at least n cops are necessary if one wants to catch the robber for all possible initial configurations. We also present a set of cop strategies for which n cops are provably sufficient to catch the robber. Further, we revisit the game in a two-dimensional grid and provide an independent proof of the fact that the robber can be caught even by a single cop under certain conditions.     

The benefit of preemption with respect to the ℓp norm

We establish tight bounds on the benefit of preemption with respect to the ${?}_p$ norm minimization objective for identical machines and for two uniformly related machines (based on their speed ratio). This benefit of preemption is the supremum ratio between the optimal costs of non-preemptive and preemptive schedules.     

Analysis of stochastic problem decomposition algorithms in computational grids

Stochastic programming usually represents uncertainty discretely by means of a scenario tree. This representation leads to an exponential growth of the size of stochastic mathematical problems when better accuracy is needed. Trying to solve the problem as a whole, considering all scenarios together, yields to huge memory requirements that surpass the capabilities of current computers. Thus, decomposition algorithms are employed to divide the problem into several smaller subproblems and to coordinate their solution in order to obtain the global optimum. This paper analyzes several decomposition strategies based on the classical Benders decomposition algorithm, and applies them in the emerging computational grid environments. Most decomposition algorithms are not able to take full advantage of all the computing power available in a grid system because of unavoidable dependencies inherent to the algorithms. However, a special decomposition method presented in this paper aims at reducing dependency among subproblems, to the point where all the subproblems can be sent simultaneously to the grid. All algorithms have been tested in a grid system, measuring execution times required to solve standard optimization problems and a real-size hydrothermal coordination problem. Numerical results are shown to confirm that this new method outperforms the classical ones when used in grid computing environments.     

Online cardinality constrained scheduling

In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines.     

Job scheduling, cooperation, and control

This paper studies one machine job scheduling situations where clients can have more than one job to be processed and where a job can be of interest for different players. Corresponding cooperative games are introduced and a result on balancedness is provided.     

Finding improving directions in Lagrangian relaxation by fictitious play: A NASA scheduling application

An improving direction for Lagrangian dual prices can be found by solving (or solving approximately) a two person zero-sum game. While this method is impractical in many situations, its practical use is illustrated in a scheduling application. In this implementation, the game is solved approximately by fictitious play.     

Modeling cooperation on a class of distribution problems

In this paper we study models of cooperation between the nodes of a network that represents a distribution problem. The distribution problem we propose arises when, over a graph, a group of nodes offers certain commodity, some other nodes require it and a third group of nodes neither need this material nor offer it but they are strategically relevant to the distribution plan. The delivery of one unit of material to a demand node generates a fixed profit, and the shipping of the material through the arcs has an associated cost. We show that in such a framework cooperation is beneficial for the different parties. We prove that the cooperative situation arising from this distribution problem is totally balanced by finding a set of stable allocations (in the core of an associated cooperative game). In order to overcome certain fairness problems of these solutions, we introduce two new solution concepts and study their properties.     

Web server load balancing: A queueing analysis

Over the last few years, the Web-based services, more specifically different types of E-Commerce applications, have become quite popular, resulting in exponential growth in the Web traffic. In many situations, this has led to unacceptable response times and unavailability of services, thereby driving away customers. Many companies are trying to address this problem using multiple Web servers with a front-end load balancer. Load balancing has been found to provide an effective and scalable way of managing the ever-increasing Web traffic. However, there has been little attempt to analyze the performance characteristics of a system that uses a load balancer. This paper presents a queuing model for analyzing load balancing with two Web servers. We first analyze the centralized load balancing model, derive the average response time and the rejection rate, and compare three different routing policies at the load balancer. We then extend our analysis to the distributed load balancing and find the optimal routing policy that minimizes the average response time.     

Control and voting power in corporate networks: Concepts and computational aspects

This paper proposes to rely on power indices to measure the amount of control held by individual shareholders in corporate networks. The value of the indices is determined by a complex voting game viewed as the composition of interlocked weighted majority games; the compound game reflects the structure of shareholdings. The paper describes an integrated algorithmic approach which allows to deal efficiently with the complexity of computing power indices in shareholding networks, irrespective of their size or structure. In particular, the approach explicitly accounts for the presence of float and of cyclic shareholding relationships. It has been successfully applied to the analysis of real-world financial networks.     

Can international environmental cooperation be bought: Comment

Fuentes-Albero and Rubio (2010) analytically examine the effects of the countries’ heterogeneity on the international environmental cooperation. They consider two types of countries having different abatement costs in one case and different environmental damages in another case. Furthermore it is analyzed whether a self-financed transfer system can diminish these heterogeneity effects. The paper shows for both scenarios of asymmetry and no transfers that the maximum level of cooperation consists of three countries of the same type. For the case of heterogeneity in environmental damages, Fuentes-Albero and Rubio conclude that an agreement between one type 1 and one type 2 country is also self-enforcing given that the differences in the damages are not very large. In this comment, the derivation of the last mentioned result is shown to be incorrect by proving that this coalition is not self-enforcing.     

The computational complexity of evolutionarily stable strategies

The concept of evolutionarily stable strategies (ESS) has been central to applications of game theory in evolutionary biology, and it has also had an influence on the modern development of game theory. A regular ESS is an important refinement the ESS concept. Although there is a substantial literature on computing evolutionarily stable strategies, the precise computational complexity of determining the existence of an ESS in a symmetric two-player strategic form game has remained open, though it has been speculated that the problem is -hard. In this paper we show that determining the existence of an ESS is both -hard and -hard, and that the problem is contained in , the second level of the polynomial time hierarchy. We also show that determining the existence of a regular ESS is indeed -complete. Our upper bounds also yield algorithms for computing a (regular) ESS, if one exists, with the same complexities.     

Syzygies of grids of projective lines

In this paper we study the syzygy modules of a grid or a fat grid of . We compute the minimal free resolution for the ideal of a complete grid in , and we conjecture this resolution in . Moreover we compute the minimal free resolution for the ideal of an incomplete grid of . We also conjecture the minimal free resolution for the ideal of a fat complete grid in .      

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

The Harsanyi value for nontransferable utility games with restricted cooperation

A nontransferable utility (NTU) game assigns a set of feasible pay-off vectors to each coalition. In this article, we study NTU games in situations in which there are restrictions on coalition formation. These restrictions will be modelled through interior structures, which extend some of the structures considered in the literature on transferable utility games for modelling restricted cooperation, such as permission structures or antimatroids. The Harsanyi value for NTU games is extended to the set of NTU games with interior structure.     

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

On exploring the genetic algorithm for modeling the evolution of cooperation in a population

In this paper, we propose a genetic algorithm approximation for modeling a population which individuals compete with each other based on prisoner’s dilemma game. Players act according to their genome, which gives them a strategy (phenotype); in our case, a probability for cooperation. The most successful players will produce more offspring and that depends directly of the strategy adopted. As individuals die, the newborns parents will be those fittest individuals in a certain spatial region. Four different fitness functions are tested to investigate the influence in the evolution of cooperation. Individuals live in a lattice modeled by probabilistic cellular automata and play the game with some of their neighborhoods. In spite of players homogeneously distributed over the space, a mean-field approximation is presented in terms of ordinary differential equations.     

Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems

It is well-known that the power-of-d choices routing algorithm maximizes throughput and is heavy-traffic optimal in load balancing systems with homogeneous servers. However, if the servers are heterogeneous, throughput optimality does not hold in general. We find necessary and sufficient conditions for throughput optimality of power-of-d choices when the servers are heterogeneous, and we prove that almost the same conditions are sufficient to show heavy-traffic optimality. Additionally, we generalize the sufficient condition for throughput optimality to a larger class of routing policies.     

Balancing and scheduling tasks in assembly lines with sequence-dependent setup times

The classical Simple Assembly Line Balancing Problem (SALBP) has been widely enriched over the past few years with many realistic approaches and much effort has been made to reduce the distance between the academic theory and the industrial reality. Despite this effort, the scheduling of the execution of tasks assigned to every workstation following the balancing of the assembly line has been scarcely reported in the scientific literature. This is supposed to be an operational concern that the worker should solve himself, but in several real environments, setups between tasks exist and optimal or near-optimal tasks schedules should be provided inside each workstation. The problem presented in this paper adds sequence-dependent setup time considerations to the classical SALBP in the following way: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time. After formulating a mathematical model for this innovative problem and showing the high combinatorial nature of the problem, eight different heuristic rules and a GRASP algorithm are designed and tested for solving the problem in reasonable computational time.