Robustness of efficient server assignment policies to service time distributions in finite‐buffered lines

We study the assignment of flexible servers to stations in tandem lines with service times that are not necessarily exponentially distributed. Our goal is to achieve optimal or near‐optimal throughput. For systems with infinite buffers, it is already known that the effective assignment of flexible servers is robust to the service time distributions. We provide analytical results for small systems and numerical results for larger systems that support the same conclusion for tandem lines with finite buffers. In the process, we propose server assignment heuristics that perform well for systems with different service time distributions. Our research suggests that policies known to be optimal or near‐optimal for Markovian systems are also likely to be effective when used to assign servers to tasks in non‐Markovian systems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Fully sequential procedures for comparing constrained systems via simulation

We consider the problem of finding the system with the best primary performance measure among a finite number of simulated systems in the presence of a stochastic constraint on a single real‐valued secondary performance measure. Solving this problem requires the identification and removal from consideration of infeasible systems (Phase I) and of systems whose primary performance measure is dominated by that of other feasible systems (Phase II). We use indifference zones in both phases and consider two approaches, namely, carrying out Phases I and II sequentially and carrying out Phases I and II simultaneously, and we provide specific example procedures of each type. We present theoretical results guaranteeing that our approaches (general and specific, sequential and simultaneous) yield the best system with at least a prespecified probability, and we provide a portion of an extensive numerical study aimed at evaluating and comparing the performance of our approaches. The experimental results show that both new procedures are useful for constrained ranking and selection, with neither procedure showing uniform superiority over the other.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Revenue maximization in two-station tandem queueing systems

We study optimal pricing for tandem queueing systems with finite buffers. The service provider dynamically quotes prices to incoming price sensitive customers to maximize the long-run average revenue. We present a Markov decision process model for the optimization problem. For systems with two stations, general-sized buffers, and two or more prices, we describe the structure of the optimal dynamic pricing policy and develop tailored policy iteration algorithms to find an optimal pricing policy. For systems with two stations but no intermediate buffer, we characterize conditions under which quoting either a high or a low price to all customers is optimal and provide an easy-to-implement algorithm to solve the problem. Numerical experiments are conducted to compare the developed algorithms with the regular policy iteration algorithm. The work also discusses possible extensions of the obtained results to both three-station systems and two-station systems with price and congestion sensitive customers using numerical analysis.     

Adaptive random search for continuous simulation optimization

We present, analyze, and compare three random search methods for solving stochastic optimization problems with uncountable feasible regions. Our adaptive search with resampling (ASR) approach is a framework for designing provably convergent algorithms that are adaptive and may consequently involve local search. The deterministic and stochastic shrinking ball (DSB and SSB) approaches are also convergent, but they are based on pure random search with the only difference being the estimator of the optimal solution [the DSB method was originally proposed and analyzed by Baumert and Smith]. The three methods use different techniques to reduce the effects of noise in the estimated objective function values. Our ASR method achieves this goal through resampling of already sampled points, whereas the DSB and SSB approaches address it by averaging observations in balls that shrink with time. We present conditions under which the three methods are convergent, both in probability and almost surely, and provide a limited computational study aimed at comparing the methods. Although further investigation is needed, our numerical results suggest that the ASR approach is promising, especially for difficult problems where the probability of identifying good solutions using pure random search is small. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Averaging frameworks for simulation optimization with applications to simulated annealing

We present two frameworks for designing random search methods for discrete simulation optimization. One of our frameworks is very broad (in that it includes many random search methods), whereas the other one considers a special class of random search methods called point‐based methods, that move iteratively between points within the feasible region. Our frameworks involve averaging, in that all decisions that require estimates of the objective function values at various feasible solutions are based on the averages of all observations collected at these solutions so far. Also, the methods are adaptive in that they can use information gathered in previous iterations to decide how simulation effort is expended in the current iteration. We show that the methods within our frameworks are almost surely globally convergent under mild conditions. Thus, the generality of our frameworks and associated convergence guarantees makes the frameworks useful to algorithm developers wishing to design efficient and rigorous procedures for simulation optimization. We also present two variants of the simulated annealing (SA) algorithm and provide their convergence analysis as example application of our point‐based framework. Finally, we provide numerical results that demonstrate the empirical effectiveness of averaging and adaptivity in the context of SA. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012