Allocating flexible servers in serial systems with switching costs

Consider a firm that operates a make-to-order serial production system and employs a cross-trained workforce. We model such a firm as a tandem queuing system in which flexible servers can be allocated across stations, and assume that a switching cost is charged when servers move between stations. We show that even in the two-station two-server case the optimal policy follows a complex state-dependent structure that may be difficult to implement in practice. We propose three alternate heuristic policies and assess their performance. We show that a simpler policy which only moves one server can achieve close to optimal results.     

Analysis of job transfer policies in systems with unreliable servers

We consider a system where incoming jobs may be executed at different servers, each of which goes through alternating periods of being available and unavailable. Neither the states of the servers nor the relevant queue sizes are known at moments of arrival. Hence, a load balancing mechanism that relies on random time-out intervals and job transfers from one queue to another is adopted. The object is to minimize a cost function which may include holding costs and transfer costs. A model of a single queue with an unreliable server and timeouts is analyzed first. The results are then used to obtain an approximate solution for arbitrary number of queues. Several transfer policies are evaluated and compared.     

Hierarchical location–allocation models for congested systems

In this paper we address the issue of locating hierarchical facilities in the presence of congestion. Two hierarchical models are presented, where lower level servers attend requests first, and then, some of the served customers are referred to higher level servers. In the first model, the objective is to find the minimum number of servers and their locations that will cover a given region with a distance or time standard. The second model is cast as a maximal covering location (MCL) formulation. A heuristic procedure is then presented together with computational experience. Finally, some extensions of these models that address other types of spatial configurations are offered.     

Optimal control of parallel server systems with many servers in heavy traffic

We consider a parallel server system that consists of several customer classes and server pools in parallel. We propose a simple robust control policy to minimize the total linear holding and reneging costs. We show that this policy is asymptotically optimal under the many-server heavy traffic regime for parallel server systems when the service times are only server pool dependent and exponentially distributed. J.G. Dai’s research supported in part by National Science Foundation grants CMMI-0727400 and CNS-0718701, and by an IBM Faculty Award.     

Static and dynamic server allocation in systems with on/off sources

A system consisting of a number of servers, where demands of different types arrive in bursts (modelled by interrupted Poisson processes), is examined in the steady state. The problem is to decide how many servers to allocate to each job type, so as to minimize a cost function expressed in terms of average queue sizes. First, an exact analysis is provided for an isolated IPP/M/n queue. The results are used to compute the optimal static server allocation policy. The latter is then compared to four heuristic policies which employ dynamic switching of servers from one queue to another (such switches take time and hence incur costs). This work was carried out in the framework of the collaborative project DOPCHE (Dynamic Operative Policies for Commercial Hosting Environments), funded by the UK Engineering and Physical Sciences Research Council under its E-Science programme. The support of the Network of Excellence EuroNGI, funded by the EU, is also acknowledged.     

Optimal resource allocation and scheduling for?the?CELL BE platform

Resource allocation and scheduling for multicore platforms is one of the most critical challenges in today??s embedded computing. In this paper we focus on a well-known multicore platform, namely the Cell BE processor, and we address the problem of allocating and scheduling its processors, communication channels and memories, with the goal of minimizing execution time for complex data streaming applications. We propose three complete approaches that optimally solve the problem and prove optimality. The first is based on the recursive application of the Logic Based Benders decomposition, resulting in a three stage algorithm. The second is a pure CP approach while the third is a hybrid approach integrating the first two. Extensive experimental evaluation shows the features of each approach and its effectiveness on a specific instance structure.     

Asymptotically optimal interruptible service policies for?scheduling jobs in a diffusion regime with?nondegenerate slowdown

A?parallel server system is considered, with I customer classes and many servers, operating in a heavy traffic diffusion regime where the queueing delay and service time are of the same order of magnitude. Denoting by $\widehat{X}^{n}$ and $\widehat{Q}^{n}$ , respectively, the diffusion scale deviation of the headcount process from the quantity corresponding to the underlying fluid model and the diffusion scale queue-length, we consider minimizing r.v.??s of the form $c^{n}_{X}=\int_{0}^{u}C(\widehat{X}^{n}(t))\,dt$ and $c^{n}_{Q}=\int_{0}^{u}C(\widehat{Q}^{n}(t))\,dt$ over policies that allow for service interruption. Here, C:? ^I ???₊ is continuous, and u>0. Denoting by ?? the so-called workload vector, it is assumed that $C^{*}(w):=\min\{C(q):q\in\mathbb{R}_{+}^{\mathbf{I}},\theta\cdot q=w\}$ is attained along a continuous curve as w varies in ?₊. We show that any weak limit point of $c^{n}_{X}$ stochastically dominates the r.v. $\int_{0}^{u}C^{*}(W(t))\,dt$ for a suitable reflected Brownian motion W and construct a sequence of policies that asymptotically achieve this lower bound. For $c^{n}_{Q}$ , an analogous result is proved when, in addition, C ^? is convex. The construction of the policies takes full advantage of the fact that in this regime the number of servers is of the same order as the typical queue-length.     

On active redundancy allocation for coherent systems—from the viewpoint of minimal cut decomposition

This paper deals with coherent systems with one active redundancy. For systems with the subclass of minimal cuts associated with one component covering that of another, assigning the redundancy to the former component is proved to bring forth a more reliable redundant system. As for symmetric systems with lower tail permutation decreasing component lifetimes, allocating the redundancy to the less reliable component results in a longer system lifetime. Several numerical examples are also presented to illustrate the new findings.     

The multiple server effect: Optimal allocation of servers to stations with different service‐time distributions in tandem queueing networks

Traditionally, studies on tandem queueing networks concentrate on systems with infinite buffers, exponential service times, and/or single servers where solutions are more tractable. Less research can be found on more general, less tractable systems. We examine multipleserver systems with finite buffers and nonexponential service times, studying the effects of coefficient of variation (cv) of the servicetime distribution on the throughput of these systems, where cv differs among stations.Starting with the single station, we examine the effects of cv and the number of servers at the station on the distribution of interdeparture times. This insight helps explain the differences in throughput seen in the single (fast) server vs. multiple (slow) server problem. These results, in turn, shed light on the server allocation problem when cv differs among stations. We present some observations, as well as the intuition behind them.     

Sequential location—allocation of public facilities in one- and two-dimensional space: Comparison of several policies

The present paper examines the sequential location—allocation problems of public facilities in one- and two-dimensional space under several policies. It is shown that the efficiency loss due to the adoption of a myopic policy is not so large, contrary to common belief, provided that the efficiency can be measured by the total transportation cost of users and by the total capacity of facilities. If the total serving area is sufficiently narrow, then the spatial allocations of optimal solutions in two-dimensional problems can be closely approximated by those in one-dimensional problems.     

A natural order in dynamical systems based on Conley–Markov matrices

We introduce a natural order to study properties of dynamical systems, especially their invariant sets. The new concept is based on the classical Conley index theory and transition probabilities among neighborhoods of different invariant sets when the dynamical systems are perturbed by white noises. The transition probabilities can be determined by the Fokker–Planck equation and they form a matrix called a Markov matrix. In the limiting case when the random perturbation is reduced to zero, the Markov matrix recovers the information given by the Conley connection matrix. The Markov matrix also produces a natural order from the least to the most stable invariant sets for general dynamical systems. In particular, it gives the order among the local extreme points if the dynamical system is a gradient-like flow of an energy functional. Consequently, the natural order can be used to determine the global minima for gradient-like systems. Some numerical examples are given to illustrate the Markov matrix and its properties.     

Homoclinic orbits for a class of singular second order Hamiltonian systems in ?3

We consider a conservative second order Hamiltonian system $\ddot q + \nabla V(q) = 0$ in ?³ with a potential V having a global maximum at the origin and a line l ?? {0} = ? as a set of singular points. Under a certain compactness condition on V at infinity and a strong force condition at singular points we study, by the use of variational methods and geometrical arguments, the existence of homoclinic solutions of the system.     

A Stackelberg game model for resource allocation in cargo container security

This paper presents a game theoretic model that analyzes resource allocation strategies against an adaptive adversary to secure cargo container transportation. The defender allocates security resources that could interdict an unauthorized weapon insertion inside a container. The attacker observes the defender’s security strategy and chooses a site to insert the weapon. The attacker’s goal is to maximize the probability that the weapon reaches its target. The basic model includes a single container route. The results in the basic model suggest that in equilibrium the defender should maintain an equal level of physical security at each site on the cargo container’s route. Furthermore, the equilibrium levels of resources to interdict the weapon overseas increase as a function of the attacker’s capability to detonate the weapon remotely at a domestic seaport. Investment in domestic seaport security is highly sensitive to the attacker’s remote detonation capability as well. The general model that includes multiple container routes suggests that there is a trade-off between the security of foreign seaports and the physical security of sites including container transfer facilities, container yards, warehouses and truck rest areas. The defender has the flexibility to shift resources between non-intrusive inspections at foreign seaports and physical security of other sites on the container route. The equilibrium is also sensitive to the cost effectiveness of security investments.     

Lagrangian–Eulerian methods for uniqueness in hydrodynamic systems

We present a Lagrangian–Eulerian strategy for proving uniqueness and local existence of solutions of limited smoothness for a class of incompressible hydrodynamic models including Oldroyd-B type complex fluid models and zero magnetic resistivity magneto-hydrodynamics equations.     

A memetic algorithm based on a NSGAII scheme for the flexible job-shop scheduling problem

The Flexible Job-Shop Scheduling Problem is concerned with the determination of a sequence of jobs, consisting of many operations, on different machines, satisfying several parallel goals. We introduce a Memetic Algorithm, based on the NSGAII (Non-Dominated Sorting Genetic Algorithm II) acting on two chromosomes, to solve this problem. The algorithm adds, to the genetic stage, a local search procedure (Simulated Annealing). We have assessed its efficiency by running the algorithm on multiple objective instances of the problem. We draw statistics from those runs, which indicate that this Memetic Algorithm yields good and low-cost solutions.     

A selection algorithm for ∊-optimal policies in undiscounted maekovian decision problems

In many real-world problems it is interesting to know the whole set of optimal or e-optimal policies of a finite-state, finite-action undiscounted Markovian Decision Problem. For finding all optimal or e-optimal policies of such a given problem we present in many real-world problems it is interesting to know the whole set of optimal or e-optimal policies of a finite-state, finite-action undiscounted Markovian Decision Problem. For finding all optimal or e-optimal policies of such a given problem we present sideration of subproblems which will be solved by Howard'S policy iteration.     

Exponential behaviour of the Butkovi?-Zimmermann algorithm for solving two-sided linear systems in max-algebra

In [P. Butkovi?, K. Zimmermann, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics 154 (3) (2006) 437-446] an ingenious algorithm for solving systems of two-sided linear equations in max-algebra was given and claimed to be strongly polynomial. However, in this note we give a sequence of examples showing exponential behaviour of the algorithm. We conclude that the problem of finding a strongly polynomial algorithm is still open.     

Scatteing for hydrogen-like systems in a constant magnetic field ∗∗

We prove asymptotic completeness for a system of two particles with opposite charges interacting via a long-range potential decaying faster than |r|^-1/2 at infinity in a homogeneous magnetic field. In particular, our result implies asymptotic completeness for the hydrogen atom with finite nuclear mass in a uniform magnetic field, which has not been proven previously.