Discrete time analysis of MAP/PH/1 vacation queue with gated time‐limited service

We analyse a single‐server queue in which the server goes through alternating periods of vacation and work. In each work period, the server attends to the queue for no more than a fixed length of time, T. The system is a gated one in which the server, during any visit, does not attend to customers which were not in the system before its visit. As soon as all the customers within the gate have been served or the time limit has been reached (whichever occurs first) the server goes on a vacation. The server does not wait in the queue if the system is empty at its arrival for a visit. For this system the resulting Markov chain, of the queue length and some auxiliary variables, is level‐dependent. We use special techniques to carry out the steady state analysis of the system and show that when the information regarding the number of customers in the gate is not critical we are able to reduce this problem to a level‐independent Markov chain problem with large number of boundary states. For this modified system we use a hybrid method which combines matrix‐geometric method for the level‐independent part of the system with special solution method for the large complex boundary which is level‐dependent. This revised version was published online in June 2006 with corrections to the Cover Date.     

Revisiting Some Duality Theorems via the Quasirelative Interior in Convex Optimization

In this paper, we deal with regularity conditions formulated by making use of the quasirelative interior and/or of the quasi-interior of the sets involved, guaranteeing strong duality for a convex optimization problem with cone (and equality) constraints and its Lagrange dual. We discuss also some recent results on this topic, which are proved to have either superfluous or contradictory assumptions. Several examples illustrate the theoretical considerations. Research made during the third author’s two months visit in Chemnitz as part of bilateral project CNR-DFG. The second author was supported by a Graduate Fellowship of the Free State Saxony, Germany.     

Predicting online-purchasing behaviour

This empirical study investigates the contribution of different types of predictors to the purchasing behaviour at an online store. We use logit modelling to predict whether or not a purchase is made during the next visit to the website using both forward and backward variable-selection techniques, as well as Furnival and Wilson's global score search algorithm to find the best subset of predictors. We contribute to the literature by using variables from four different categories in predicting online-purchasing behaviour: (1) general clickstream behaviour at the level of the visit, (2) more detailed clickstream information, (3) customer demographics, and (4) historical purchase behaviour. The results show that predictors from all four categories are retained in the final (best subset) solution indicating that clickstream behaviour is important when determining the tendency to buy. We clearly indicate the contribution in predictive power of variables that were never used before in online purchasing studies. Detailed clickstream variables are the most important ones in classifying customers according to their online purchase behaviour. Though our dataset is limited in size, we are able to highlight the advantage of e-commerce retailers of being able to capture an elaborate list of customer information.     

Quasi-stationary distributions as centrality measures for the giant strongly connected component of a reducible graph

A random walk can be used as a centrality measure of a directed graph. However, if the graph is reducible the random walk will be absorbed in some subset of nodes and will never visit the rest of the graph. In Google PageRank the problem was solved by the introduction of uniform random jumps with some probability. Up to the present, there is no final answer to the question about the choice of this probability. We propose to use a parameter-free centrality measure which is based on the notion of a quasi-stationary distribution. Specifically, we suggest four quasi-stationary based centrality measures, analyze them and conclude that they produce approximately the same ranking.     

Markov-modulated Brownian motions perturbed by catastrophes

ABSTRACT

We consider a one-sided Markov-modulated Brownian motion perturbed by catastrophes that occur at some rates depending on the modulating process. When a catastrophe occurs, the level drops to zero for a random recovery period. Then the process evolves normally until the next catastrophe. We use a semi-regenerative approach to obtain the stationary distribution of this perturbed MMBM. Next, we determine the stationary distribution of two extensions: we consider the case of a temporary change of regime after each recovery period and the case where the catastrophes can only happen above a fixed threshold. We provide some simple numerical illustrations.     

A patient assignment algorithm for home care services

We consider the problem of assigning patients to nurses for home care services. The aim is to balance the workload of the nurses while avoiding long travels to visit the patients. We analyse the case of the CSSS Côte-des-Neiges, Métro and Parc Extension for which a previous analysis has shown that demand fluctuations may create work overload for the nursing staff. We propose a mixed integer programming model with some non-linear constraints and a non-linear objective which we solve using a Tabu Search algorithm. A simplification of the workload measure leads to a linear mixed integer program which we optimize using CPLEX.     

Performance Analysis of a Fluid Production/Inventory Model with State-dependence

We study the long-run average performance of a fluid production/ inventory model which alternates between ON periods and OFF periods. During ON periods of random lengths items are added continuously, at some state-dependent rate, to the inventory. During OFF periods the content decreases (again at some state-dependent rate) back to some basic level. We derive the pertinent reward functionals in closed form. For this analysis the steady-state distributions of the stock level process and its jump counterpart are required. In several examples we use the obtained explicit formulas to maximize the long-run average net revenue numerically.      

A priori orienteering with time windows and stochastic wait times at customers

In the pharmaceutical industry, sales representatives visit doctors to inform them of their products and encourage them to become an active prescriber. On a daily basis, pharmaceutical sales representatives must decide which doctors to visit and the order to visit them. This situation motivates a problem we more generally refer to as a stochastic orienteering problem with time windows (SOPTW), in which a time window is associated with each customer and an uncertain wait time at a customer results from a queue of competing sales representatives. We develop a priori routes with the objective of maximizing expected sales. We operationalize the sales representative’s execution of the a priori route with relevant recourse actions and derive an analytical formula to compute the expected sales from an a priori tour. We tailor a variable neighborhood search heuristic to solve the problem. We demonstrate the value of modeling uncertainty by comparing the solutions to our model to solutions of a deterministic version using expected values of the associated random variables. We also compute an empirical upper bound on our solutions by solving deterministic instances corresponding to perfect information.     

SLE Boundary Visits

We study the probabilities with which chordal Schramm–Loewner evolutions (SLE) visit small neighborhoods of boundary points. We find formulas for general chordal SLE boundary visiting probability amplitudes, also known as SLE boundary zig-zags or order refined SLE multi-point Green’s functions on the boundary. Remarkably, an exact answer can be found to this important SLE question for an arbitrarily large number of marked points. The main technique employed is a spin chain–Coulomb gas correspondence between tensor product representations of a quantum group and functions given by Dotsenko–Fateev type integrals. We show how to express these integral formulas in terms of regularized real integrals, and we discuss their numerical evaluation. The results are universal in the sense that apart from an overall multiplicative constant the same formula gives the amplitude for many different formulations of the SLE boundary visit problem. The formula also applies to renormalized boundary visit probabilities for interfaces in critical lattice models of statistical mechanics: we compare the results with numerical simulations of percolation, loop-erased random walk, and Fortuin–Kasteleyn random cluster models at Q = 2 and Q = 3, and find good agreement.     

Asymptotic behavior of positive solution branches of elliptic problems with linear part at resonance

We consider Dirichlet problems for semilinear elliptic equations whose linear part is at resonance. For various types of nonlinearities we provide sufficient conditions for the solvability of these problems for certain types of forcing terms. Depending upon the dimension of the independent variable and the shape of the domain, we obtain multiple existence results and show that in some cases infinitely many solutions may exist.Dedicated to Klaus Kirchgässner on the occasion of his 60th birthdayThe authors' work on this project has been supported by several institutions and thanks are due to the University of Utah for granting Schaaf a one year's visiting professorship during 1989–1990, to the DFG and the University of Stuttgart for providing Schmitt with the opportunity to visit that institution during the summer semester 1989. Final preparation was supported by a grant from NSF.     

Processing-plus-wait due dates in single-machine scheduling

We study the problem of schedulingn jobs on a single machine. Each job is assigned a processing-plus-wait due date, which is an affine-linear function of its processing time. The objective is to minimize the symmetric earliness and tardiness costs. We analyze a combined decision model which includes computing both the optimal job sequence and optimal due date parameters. For the quadratic objective function, we propose a heuristic solution based on a bicriterion approach. Additionally, we provide computational results to compare this model with two simpler models. For the maximum objective function, we show that it is efficiently solved by the shortest processing time sequence.Part of this research was undertaken during a visit of the first author at the University of Manitobe, Canada in 1991. This visit was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The numerical results were obtained with the assistance of T. P. Lindenthal. The authors are thankful for his help.     

An extremal constrained routing problem with internal losses

We consider the following problem: one has to visit a finite number of sets and perform certain work on each of them. The work is accompanied by certain (internal) losses. Themovements from some set to another one are constrained and accompanied by external (aggregated additively) losses. We propose a “through” variant of the dynamic programming method, formulate an equivalent reconstruction problem, and develop an optimal algorithm based on an efficient dynamic programming algorithm.     

建设项目动态联盟伙伴信用评价

应用因子分析法对建设项目动态联盟背景下的伙伴信用进行评价。通过网站和问卷调查获取的数据提取出4个公共因子:盈利和成长能力、经营能力、创新能力、履约能力因子;并确定了4个公共因子和16个指标对伙伴信用的影响力度;相关性分析发现,伙伴信用与其绩效密切相关。最后对部分被调研企业中的17个企业的信用水平进行了综合评价,为其采取有效策略提高信用水平提供依据,也为盟主企业选择伙伴提供参考。     

On the stability of a polling system with an adaptive service mechanism

We consider a single-server cyclic polling system with three queues where the server follows an adaptive rule: if it finds one of queues empty in a given cycle, it decides not to visit that queue in the next cycle. In the case of limited service policies, we prove stability and instability results under some conditions which are sufficient but not necessary, in general. Then we discuss open problems with identifying the exact stability region for models with limited service disciplines: we conjecture that a necessary and sufficient condition for the stability may depend on the whole distributions of the primitive sequences, and illustrate that by examples. We conclude the paper with a section on the stability analysis of a polling system with either gated or exhaustive service disciplines.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

Creating lasso-solutions for the traveling salesman problem with pickup and delivery by Tabu search

We consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD) where the same costumers might require both deloverie of goods and pickup of other goods. All the goods should be transported from/to the same depot. A vehicle on a TSPPD-tour could often get some practical problems when arranging the load. Even if the vehicle has enough space for all the pickups, one has to consider that they are stored in a way that doesn't block the delivery for the next customer. In real life problems this occurs for instance for breweries when they deliver bottles of beer or mineral water and collects empty bottles from the same customers on the same tour. In these situations we could relax the constraints of only checking Hamiltonian tours, and also try solutions that can visit customers in a way giving rise to a ‘alsso’ model. A solution which first only delivers bottles until the vehicle is partly unloaded, then do both delivery and pickup at the remaining customers and at last picks up the empty bottle from the first visited customers, could in these situations be better than a pure Hamiltonian tour, at least in a practical setting. To find such solutions, we will use the metaheuristic Tabu Search on some well known TSPPD-problems, and compare them to other kinds of solutions on the same problems.     

On groups of hyperbolic length

We investigate the recently introduced notion of rotation numbers for periodic orbits of interval maps. We identify twist orbits, that is those orbits that are the simplest ones with given rotation number. We estimate from below the topological entropy of a map having an orbit with given rotation number. Our estimates are sharp: there are unimodal maps where the equality holds. We also discuss what happens for maps with larger modality. In the Appendix we present a new approach to the problem of monotonicity of entropy in one-parameter families of unimodal maps. This work was partially done during the first author’s visit to IUPUI (funded by a Faculty Research Grant from UAB Graduate School) and his visit to MSRI (the research at MSRI funded in part by NSF grant DMS-9022140) whose support the first author acknowledges with gratitude. The second author was partially supported by NSF grant DMS-9305899, and his gratitude is as great as that of the first author.     

Well-Posedness Under Relaxed Semicontinuity for Bilevel Equilibrium and Optimization Problems with Equilibrium Constraints

Bilevel equilibrium and optimization problems with equilibrium constraints are considered. We propose a relaxed level closedness and use it together with pseudocontinuity assumptions to establish sufficient conditions for well-posedness and unique well-posedness. These conditions are new even for problems in one-dimensional spaces, but we try to prove them in general settings. For problems in topological spaces, we use convergence analysis while for problems in metric cases we argue on diameters and Kuratowski’s, Hausdorff’s, or Istrǎtescu’s measures of noncompactness of approximate solution sets. Besides some new results, we also improve or generalize several recent ones in the literature. Numerous examples are provided to explain that all the assumptions we impose are very relaxed and cannot be dropped.     

Noise-induced changes to the behaviour of semi-implicit Euler methods for stochastic delay differential equations undergoing bifurcation

We are concerned with estimating parameter values at which bifurcations occur in stochastic delay differential equations. After a brief review of bifurcation, we employ a numerical approach and consider how bifurcation values are influenced by the choice of numerical scheme and the step length and by the level of white noise present in the equation. In this paper we provide a formulaic relationship between the estimated bifurcation value, the level of noise, the choice of numerical scheme and the step length. We are able to show that in the presence of noise there may be some loss of order in the accuracy of the approximation to the true bifurcation value compared to the use of the same approach in the absence of noise.