A branch-and-bound algorithm for flow-path design of automated guided vehicle systems

An algorithm for determining the optimal, unidirectional flow path for an automated guided vehicle system with a given facility layout is presented. The problem is formulated as an integer program. The objective is to minimize the total distance traveled by vehicles subject to the constraint that the resulting network consists of a single strongly connected component. A specialized branch-and-bound solution procedure is discussed in detail.     

Bounds for circular error probabilities

Bounds for P(X + X ⩽ k²σ) are given where X₁ and X₂ are independent normal variables having zero means and variances σ, σ, respectively. This is generalized when X₁ and X₂ are dependent variables with known covariance matrix.     

An optimal critical level policy for inventory systems with two demand classes

Traditional inventory systems treat all demands of a given item equally. This approach is optimal if the penalty costs of all customers are the same, but it is not optimal if the penalty costs are different for different customer classes. Then, demands of customers with high penalty costs must be filled before demands of customers with low penalty costs. A commonly used inventory policy for dealing with demands with different penalty costs is the critical level inventory policy. Under this policy demands with low penalty costs are filled as long as inventory is above a certain critical level. If the inventory reaches the critical level, only demands with high penalty costs are filled and demands with low penalty costs are backordered. In this article, we consider a critical level policy for a periodic review inventory system with two demand classes. Because traditional approaches cannot be used to find the optimal parameters of the policy, we use a multidimensional Markov chain to model the inventory system. We use a sample path approach to prove several properties of this inventory system. Although the cost function is not convex, we can build on these properties to develop an optimization approach that finds the optimal solution. We also present some numerical results. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Labor staffing and scheduling models for controlling service levels

The problems of labor staffing and scheduling have received substantial attention in the literature. We introduce two new models of the labor staffing and scheduling problems that avoid the limitations of existing models. Collectively, the models have five important attributes. First, both models ensure the delivery of a minimally acceptable level of service in all periods. Second, one model can identify the least expensive way of delivering a specified aggregate level of customer service (the labor staffing problem and a form of labor scheduling problem). Third, the other model can identify the highest level of service attainable with a fixed amount of labor (the other form of the labor scheduling problem). Fourth, the models enable managers to identify the pareto relationship between labor costs and customer service. Fifth, the models allow a degree of control over service levels that is unattainable with existing models. Because of these attributes, which existing models largely do not possess, we expect these models to have broad applicability in a wide range of organizations operating in both competitive and noncompetitive environments. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 719–740, 1997     

On compounded bivariate poisson distributions

A unified treatment is given for a class of discrete distributions derived by compounding a bivariate Poisson with a bivariate discrete or continuous distribution. Using generating functions a number of interesting results are obtained for probabilities, moments, cumulants, factorial moments, and factorial cumulants. Conditional distributions and regression functions are also examined. Five illustrative examples are presented in detail. © 1994 John Wiley & Sons, Inc.     

Nonpreemptive scheduling of independent tasks with prespecified processor allocations

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented. © 1994 John Wiley & Sons, Inc.     

A generalized model for the economic design of x̄control charts for production systems with increasing failure rate and early replacement

This article generalizes the model for the economic design of x̄-control charts of Duncan [4], starting from the more recent papers of Lorenzen and Vance [8] and Banerjee and Rahim [3]. The classical model of Duncan [4] and its several extensions including the unified model of Lorenzen and Vance [8] assumed exponentially distributed in-control periods and provided uniform sampling schemes. Banerjee and Rahim [3], however, assumed a Weibull-distributed in-control period having an increasing failure rate and used variable sampling intervals. The present article is an extension of the work of Banerjee and Rahim [3], where a general distribution of in-control periods having an increasing failure rate is assumed and the possibility of age-dependent repair before failure is considered. Several different truncated and nontruncated probability models are chosen. It is proposed that economic benefits can be achieved by adopting a nonuniform inspection scheme and by truncating a production cycle when it attains a certain age. Numerical examples are presented to support this proposition. Finally, the effect of model specification in the choice of failure mechanism is investigated. © 1993 John Wiley & Sons, Inc.     

Use of a classifier in a knowledge-based simulation optimization system

This article defines and develops a simulation optimization system based upon response surface classification and the integration of multiple search strategies. Response surfaces are classified according to characteristics that indicate which search technique will be most successful. Typical surface characteristics include statistical measures and topological features, while search techniques encompass response surface methodology, simulated annealing, random search, etc. The classify-then-search process flow and a knowledge-based architecture are developed and then demonstrated with a detailed computer example. The system is useful not only as an approach to optimizing simulations, but also as a means for integrating search techniques and thereby providing the user with the most promising path toward an optimal solution. © 1995 John Wiley & Sons, Inc.     

An exact ceiling point algorithm for general integer linear programming

We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1-ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP-relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1-ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.