Pseudo-monotonic interval programming

A pseudo-monotonic interval program is a problem of maximizing f(x) subject to x ε X = {x ε Rⁿ | a < Ax < b, a, b ε R^m} where f is a pseudomonotonic function on X, the set defined by the linear interval constraints. In this paper, an algorithm to solve the above program is proposed. The algorithm is based on solving a finite number of linear interval programs whose solutions techniques are well known. These optimal solutions then yield an optimal solution of the proposed pseudo-monotonic interval program.     

Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem

In this paper we present a new formulation of the quadratic assignment problem. This is done by transforming the quadratic objective function into a linear objective function by introducing a number of new variables and constraints. The resulting problem is a 0-1 linear integer program with a highly specialized structure. This permits the use of the partitioning scheme of Benders where only the original variables need be considered. The algorithm described thus iterates between two problems. The master problem is a pure 0-1 integer program, and the subproblem is a transportation problem whose optimal solution is shown to be readily available from the master problem in closed form. Computational experience on problems available in the literature is provided.     

A versatile scheme for ranking the extreme points of an assignment polytope

A cutting plane scheme embedded in an implicit enumeration framework is proposed for ranking the extreme points of linear assignment problems. This method is capable of ranking any desired number of extreme points at each possible objective function value. The technique overcomes storage difficulties by being able to perform the ranking at any particular objective function value independently of other objective values. Computational experience on some test problems is provided.     

Optimal admission pricing and service rate control of an M[x]/M/s queue with reneging

In this article we consider the optimal control of an M^[X]/M/s queue, s ≧ 1. In addition to Poisson bulk arrivals we incorporate a reneging function. Subject to control are an admission price p and the service rate μ. Thus, through p, balking response is induced. When i customers are present a cost h(i,μ,p) per unit time is incurred, discounted continuously. Formulated as a continuous time Markov decision process, conditions are given under which the optimal admission price and optimal service rate are each nondecreasing functions of i. In Section 4 we indicate how the infinite state space may be truncated to a finite state space for computational purposes.     

Multivariate age-dependent imperfect repair

In this article we consider models of systems whose components have dependent life lengths with specific multivariate distributions. Upon failure, components are repaired. Two types of repair are distinguished. After perfect repair, a unit has the same life distribution as a new item. After imperfect repair, a unit has the life distribution of an item which is of the same age but has never failed. We study a model in which the mechanism for determining the nature of the repair is age dependent.     

Equivalence relations in the theory of repetitive consumption

Preference for food in the function of the time since last consumption and total preference in the function of eating frequency are equivalent mathematical representations of attitudes governing food consumption. The observed and postulated properties of these functions imply a formal correspondence between preference maximizing and variety seeking behavior.     

An analysis of single item inventory systems with returns

Inventory systems with returns are systems in which there are units returned in a repairable state, as well as demands for units in a serviceable state, where the return and demand processes are independent. We begin by examining the control of a single item at a single location in which the stationary return rate is less than the stationary demand rate. This necessitates an occasional procurement of units from an outside source. We present a cost model of this system, which we assume is managed under a continuous review procurement policy, and develop a solution method for finding the policy parameter values. The key to the analysis is the use of a normally distributed random variable to approximate the steady-state distribution of net inventory. Next, we study a single item, two echelon system in which a warehouse (the upper echelon) supports N(N ? 1) retailers (the lower echelon). In this case, customers return units in a repairable state as well as demand units in a serviceable state at the retailer level only. We assume the constant system return rate is less than the constant system demand rate so that a procurement is required at certain times from an outside supplier. We develop a cost model of this two echelon system assuming that each location follows a continuous review procurement policy. We also present an algorithm for finding the policy parameter values at each location that is based on the method used to solve the single location problem.     

Scheduling of stochastic tasks on two parallel processors

We consider the problem of scheduling n tasks on two identical parallel processors. We show both in the case when the processing times for the n tasks are independent exponential random variables, and when they are independent hyperexponentials which are mixtures of two fixed exponentials, that the policy of performing tasks with longest expected processing time (LEPT) first minimizes the expected makespan, and that in the hyperexponential case the policy of performing tasks with shortest expected processing time (SEPT) first minimizes the expected flow time. The approach is simpler than the dynamic programming approach recently employed by Bruno and Downey.     

M/M/1 queues with interdependent arrival and service processes

We study via simulation an M/M/1 queueing system with the assumption that a customer's service time and the interarrival interval separating his arrival from that of his predecessor are correlated random variables having a bivariate exponential distribution. We show that positive correlation reduces the mean and variance of the total waiting time and that negative correlation has the opposite effect. By using spectral analysis and a nonparametric test applied to the sample power spectra associated with certain simulated waiting times we show the effect to be statistically significant.