The shuttle dispatch problem with compound Poisson arrivals: Controls at two terminals

We consider the control of an infinite capacity shuttle which transports passengers between two terminals. The passengers arrive at each terminal according to a compound Poisson process and the travel time from one terminal to the other is a random variable following an arbitrary distribution. The following control limit policy is considered: dispatch the shuttle at terminali, at the instant that the total number of passengers waiting at terminali reaches or exceeds a predetermined control limitm _i . The objective of this paper is to obtain the mean waiting time of an arbitrary passenger at each terminal for given control valuesm ₁ andm ₂. We also discuss a search procedure to obtain the optimal control values which minimize the total expected cost per unit time under a linear cost structure.     

Single–machine scheduling with random machine breakdowns and randomly compressible processing times

This work presents a model of single–machine scheduling problem. The machine is failure–prone and subject to random breakdowns. The processing time is a deterministic sequence that is randomly compressible, which may be from the introduction of new technology or addition of new equipment. Taking into account the cost for the random breakdowns and the random compressible processing time, our objective is to find the optimal scheduling policy to minimize an objective function. Under simple conditions, it is shown that the optimal sequence possesses a V-shape property     

FRACTOP: A Geometric Partitioning Metaheuristic for Global Optimization

We propose a new metaheuristic, FRACTOP, for global optimization. FRACTOP is based on the geometric partitioning of the feasible region so that search metaheuristics such as Simulated Annealing (SA), or Genetic Algorithms (GA) which are activated in smaller subregions, have increased reliability in locating the global optimum. FRACTOP is able to incorporate any search heuristic devised for global optimization. The main contribution of FRACTOP is that it provides an intelligent guidance (through fuzzy measures) in locating the subregion containing the global optimum solution for the search heuristics imbedded in it. By executing the search in nonoverlapping subregions, FRACTOP eliminates the repetitive visits of the search heuristics to the same local area and furthermore, it becomes amenable for parallel processing. As FRACTOP conducts the search deeper into smaller subregions, many unpromising subregions are discarded from the feasible region. Thus, the initial feasible region gains a fractal structure with many space gaps which economizes on computation time. Computational experiments with FRACTOP indicate that the metaheuristic improves significantly the results obtained by random search (RS), SA and GA.     

Optimal replacement policy for a deteriorating system with increasing repair times

This paper considers an optimal maintenance policy for a practical and reparable deteriorating system subject to random shocks. Modeling the repair time by a geometric process and the failure mechanism by a generalized δ-shock process, we develop an explicit expression of the long-term average cost per time unit for the system under a threshold-type replacement policy. Based on this average cost function, we propose a finite search algorithm to locate the optimal replacement policy N^∗ to minimize the average cost rate. We further prove that the optimal policy N^∗ is unique and present some numerical examples. Many practical systems fit the model developed in this paper.     

Optimal Operating Policy for a Random Additional Service Facility

This paper studies the steady state behaviour of a Markovian queue wherein there is a regular service facility serving the units one by one. A search for an additional service facility for the service of a group of units is started when the queue length increases to K (0 < K < L), where L is the maximum waiting space. The search is dropped when the queue length reduces to some tolerable fixed size L - N. The availability time of an additional service facility is a random variable. The model is directed towards finding the optimal operating policy (N,K) for a queueing system with a linear cost structure.     

Control Policies for Inventory with Service Time

Abstract

This article introduces an additional control policy—the N-policy–into (s, S) inventory system with positive service time. Under specified interarrival and service time distributions, which are independent of each other, we obtain the necessary and sufficient condition for the system to be stable. We also obtain the optimal values of the control variables s, S, and N; it is seen that the cost function attains the minimum value at s = 0. It is also shown that the cost function is separately convex in the variables S and N. Numerical illustrations are provided. Several measures of performance of the system are evaluated.     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

Random walks and an O*(n5) volume algorithm for convex bodies

Given a high dimensional convex body K⊆ℝⁿ by a separation oracle, we can approximate its volume with relative error ε, using O*(n⁵) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing; and a stepwise interlacing of rounding and sampling. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 1–50, 1997     

Dynamic pricing inventory control under fixed cost and lost sales

This paper studies a periodic review pricing and inventory replenishment problem which encounters stochastic demands in multiple periods. In many inventory control problems, the unsatisfied demand is traditionally assumed to be backlogged but in this paper is assumed to be lost. In many practical problems, a consumer who could not buy what he/she wants in one store is not willing to wait until that store restocks it but tries to buy alternatives in other stores. Also, in this paper, the random variable for the demand function is assumed to be general, which means that any probability function for the random variable can be applied to our result. Cost terms consist of the holding cost by the leftover, the shortage cost by lost sales, and the strictly positive fixed ordering cost. The objective of this paper is to dynamically and simultaneously decide the optimal selling price and replenishment in each period by maximizing the expected profit over the finite selling horizon. We show that, under the general assumption on the random variable for the demand, the objective function is K$K$-concave, an (s,S)$(s\text{,}S)$ policy is optimal for the replenishment and the optimal price is determined based on the inventory level after the replenishment in each period.     

Threshold start-up control policy for polling systems

A threshold start-up policy is appealing for manufacturing (service) facilities that incur a cost for keeping the machine (server) on, as well as for each restart of the server from its dormant state. Analysis of single product (customer) systems operating under such a policy, also known as the N-policy, has been available for some time. This article develops mathematical analysis for multiproduct systems operating under a cyclic exhaustive or globally gated service regime and a threshold start-up rule. It pays particular attention to modeling switchover (setup) times. The analysis extends/unifies existing literature on polling models by obtaining as special cases, the continuously roving server and patient server polling models on the one hand, and the standard M/G/1 queue with N-policy, on the other hand. We provide a computationally efficient algorithm for finding aggregate performance measures, such as the mean waiting time for each customer type and the mean unfinished work in system. We show that the search for the optimal threshold level can be restricted to a finite set of possibilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal lot size and inspection policy for products sold with warranty

This paper develops a mathematical model to jointly determine the optimal lot size and product inspection policy for a deteriorating production system, when products are sold with free minimal repair warranty. Due to system deterioration, a last-K product inspection scheme is proposed, under which the last K products in a production lot are inspected and nonconforming products found are reworked. Based on the model, we show that there exist a unique optimal lot size and a corresponding inspection policy such that the expected total cost per unit time is minimized. Since there is no closed-form expression for the optimal lot size, an upper bound and approximate solutions are obtained to facilitate the search process. Furthermore, an algorithm is provided to efficiently search for the optimal policy and the performance of the optimal policy is evaluated through numerical examples.     

Optimality of D-Policies for an M/G/1 Queue with a Removable Server

We consider an M/G/1 queue with a removable server. When a customer arrives, the workload becomes known. The cost structure consists of switching costs, running costs, and holding costs per unit time which is a nonnegative nondecreasing right-continuous function of a current workload in the system. We prove an old conjecture that D-policies are optimal for the average cost per unit time criterion. It means that for this criterion there is an optimal policy that either runs the server all the time or switches the server off when the system becomes empty and switches it on when the workload reaches or exceeds some threshold D.     

Approximate Implementations of Pure Random Search in the Presence of Noise

We discuss the noisy optimisation problem, in which function evaluations are subject to random noise. Adaptation of pure random search to noisy optimisation by repeated sampling is considered. We introduce and exploit an improving bias condition on noise-affected pure random search algorithms. Two such algorithms are considered; we show that one requires infinite expected work to proceed, while the other is practical.Supported by a Bright Future Scholarship administered by the Foundation for Research, Science and Technology, New Zealand     

Dynamic lot-sizing with setup cost reduction

One of the fundamental tenets of the Just-in-Time (JIT) manufacturing philosophy is that reduction or even elimination of inventory conserves valuable resources and reduces wasteful spending. In many cases, to achieve inventory reductions requires investment in reduction of setup costs. For this reason, certain proposals for incorporating means for reducing setup costs into classical production-inventory models have been offered in recent years. This article considers a dynamic lot-sizing model M where the values of the setup costs can be reduced by various amounts depending upon the level of funds R committed to this reduction. We show that for each fixed value of R, the model can be represented as a shortest path problem. By minimizing the optimal value function V(R) of the shortest path problem over R, model M can, in theory, be solved. In practice, the viability of this approach depends crucially upon the properties of the function V. Since these properties depend upon the nature of the setup cost function K used in model M, we analyze how V varies as K varies. This allows us to propose two exact, finite algorithms for solving model M, one for the case when K is a concave function, the other for the case when K is convex. Computational results for the convex case are presented. The problems solved demonstrate that, in practice, setup cost reductions chosen according to model M have the potential to significantly reduce both inventory levels and total costs.     

On the Diaconis-Shahshahani Method in Random Matrix Theory

If Γ is a random variable with values in a compact matrix group K, then the traces Tr(Γ^j) (j ∊ N) are real or complex valued random variables. As a crucial step in their approach to random matrix eigenvalues, Diaconis and Shahshahani computed the joint moments of any fixed number of these traces if Γ is distributed according to Haar measure and if K is one of U_n, O_n or Sp_n, where n is large enough. In the orthogonal and symplectic cases, their proof is based on work of Ram on the characters of Brauer algebras. The present paper contains an alternative proof of these moment formulae. It invokes classical invariant theory (specifically, the tensor forms of the First Fundamental Theorems in the sense of Weyl) to reduce the computation of matrix integrals to a counting problem, which can be solved by elementary means.     

Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands

We consider the problem of finding the optimal routing of a single vehicle that delivers K different products to N customers according to a particular customer order. The demands of the customers for each product are assumed to be random variables with known distributions. Each product type is stored in its dedicated compartment in the vehicle. Using a suitable dynamic programming algorithm we find the policy that satisfies the demands of the customers with the minimum total expected cost. We also prove that this policy has a specific threshold-type structure. Furthermore, we investigate a corresponding infinite-time horizon problem in which the service of the customers does not stop when the last customer has been serviced but it continues indefinitely with the same customer order. It is assumed that the demands of the customers at different tours have the same distributions. It is shown that the discounted-cost optimal policy and the average-cost optimal policy have the same threshold-type structure as the optimal policy in the original problem. The theoretical results are illustrated by numerical examples.     

Generalizations in the linear search problem

A major part of the paper deals with the linear search problem in which the cost function is a strictly increasing convex functionf satisfyingf(0)=0. It is shown that a number of results previously established for the casef(t)=t ^α can be extended to the convex case; in particular a sufficient condition for the existence of a minimizing search strategy of a simple form is obtained for the convex case. Numerous results are obtained on the existence or otherwise of terminating and non-terminating optimal search strategies for cost functions already occurring in the literature.     

Tabu Search When Noise is Present: An Illustration in the Context of Cause and Effect Analysis

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.