Combination setwise-Bonferroni-type bounds

We consider three classes of lower bounds to P(c) = P (X₁ ≤ c₁,…, X_n ≤ c); Bonferroni-type bounds, product-type bounds and setwise bounds. Setwise probability inequalities are shown to be a compromise between product-type and Bonferroni-type probability inequalities. Bonferroni-type inequalities always hold. Product-type inequalities require positive dependence conditions, but are superior to the Bonferroni-type and setwise bounds when these conditions are satisfied. Setwise inequalities require less stringent positive dependence bound conditions than the product-type bounds. Neither setwise nor Bonferroni-type bounds dominate the other. Optimized setwise bounds are developed. Results pertaining to the nesting of setwise bounds are obtained. Combination setwise-Bonferroni-type bounds are developed in which high dimensional setwise bounds are applied and second and third order Bonferroni-type bounds are applied within each subvector of the setwise bounds. These new combination bounds, which are applicable for associated random variables, are shown to be superior to Bonferroni-type and setwise bounds for moving averages and runs probabilities. Recently proposed upper bounds to P(c) are reviewed. The lower and upper bounds are tabulated for various classes of multivariate normal distributions with banded covariance matrices. The bounds are shown to be surprisingly accurate and are much easier to compute than the inclusion-exclusion bounds. A strategy for employing the bounds is developed. © 1996 John Wiley & Sons, Inc.     

Lower bounds for single-machine scheduling problems

This article addresses deterministic, nonpreemptive scheduling of n jobs with unequal release times on a single machine to minimize the sum of job completion times. This problem is known to be NP-hard. The article compares six available lower bounds in the literature and shows that the lower bound based on the optimal solution to the preemptive version of the problem is the dominant lower bound.     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.     

Distribution free bounds for service constrained (Q,r) inventory systems

A classical and important problem in stochastic inventory theory is to determine the order quantity (Q) and the reorder level (r) to minimize inventory holding and backorder costs subject to a service constraint that the fill rate, i.e., the fraction of demand satisfied by inventory in stock, is at least equal to a desired value. This problem is often hard to solve because the fill rate constraint is not convex in (Q, r) unless additional assumptions are made about the distribution of demand during the lead‐time. As a consequence, there are no known algorithms, other than exhaustive search, that are available for solving this problem in its full generality. Our paper derives the first known bounds to the fill‐rate constrained (Q, r) inventory problem. We derive upper and lower bounds for the optimal values of the order quantity and the reorder level for this problem that are independent of the distribution of demand during the lead time and its variance. We show that the classical economic order quantity is a lower bound on the optimal ordering quantity. We present an efficient solution procedure that exploits these bounds and has a guaranteed bound on the error. When the Lagrangian of the fill rate constraint is convex or when the fill rate constraint does not exist, our bounds can be used to enhance the efficiency of existing algorithms. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 635–656, 2000     

Minimizing the sum of weighted completion times of n-independent jobs when resource availability varies over time: Performance of a simple priority rule

In this article our objective is to evaluate the performance of a WSPT (weighted shortest processing time) rule for scheduling n independent jobs where the resources to process these jobs vary over time and a job can be processed by several processors simultaneously. This problem was raised by Baker and Nuttle [2]. A linear-programming (LP) model is formulated to obtain a lower bound on the minimum value of the weighted completion times. The purpose of the model is to provide a basis for evaluating the WSPT heuristic. 1000 experiments were performed using different resource profiles to test the performance of WSPT. Using WSPT, the weighted completion times were found to be, on the average, 0.2% away from their LP lower bounds.     

Managing waiting times of backordered demands in single‐stage (Q,r) inventory systems

We present a service constrained (Q, r) model that minimizes expected holding and ordering costs subject to an upper bound on the expected waiting time of demands that are actually backordered. We show that, after optimizing over r, the average cost is quasiconvex in Q for logconcave continuous lead time demand distributions. For logconcave discrete lead time demand distributions we find a single‐pass efficient algorithm based on a novel search stopping criterion. The algorithm also allows for bounds on the variability of the service measure. A brief numerical study indicates how the bounds on service impact the optimal average cost and the optimal (Q, r) choice. The discrete case algorithm can be readily adapted to provide a single pass algorithm for the traditional model that bounds the expected waiting time of all demands (backordered or not). © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 557–573, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10028     

Optimal machine capacity expansions with nested limitations under stochastic demand

This paper studies capacity expansions for a production facility that faces uncertain customer demand for a single product family. The capacity of the facility is modeled in three tiers, as follows. The first tier consists of a set of upper bounds on production that correspond to different resource types (e.g., machine types, categories of manpower, etc.). These upper bounds are augmented in increments of fixed size (e.g., by purchasing machines of standard types). There is a second‐tier resource that constrains the first‐tier bounds (e.g., clean room floor space). The third‐tier resource bounds the availability of the second‐tier resource (e.g., the total floor space enclosed by the building, land, etc.). The second and third‐tier resources are expanded at various times in various amounts. The cost of capacity expansion at each tier has both fixed and proportional elements. The lost sales cost is used as a measure for the level of customer service. The paper presents a polynomial time algorithm (FIFEX) to minimize the total cost by computing optimal expansion times and amounts for all three types of capacity jointly. It accommodates positive lead times for each type. Demand is assumed to be nondecreasing in a “weak” sense. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Assembly of systems having maximum reliability

The first problem considered in this paper is concerned with the assembly of independent components into parallel systems so as to maximize the expected number of systems that perform satisfactorily. Associated with each component is a probability of it performing successfully. It is shown that an optimal assembly is obtained if the reliability of each assembled system can be made equal. If such equality is not attainable, then bounds are given so that the maximum expected number of systems that perform satisfactorily will lie within these stated bounds; the bounds being a function of an arbitrarily chosen assembly. An improvement algorithm is also presented. A second problem treated is concerned with the optimal design of a system. Instead of assembling given units, there is an opportunity to “control” their quality, i.e., the manufacturer is able to fix the probability, p, of a unit performing successfully. However, his resources, are limited so that a constraint is imposed on these probabilities. For (1) series systems, (2) parallel systems, and (3) k out of n systems, results are obtained for finding the optimal p's which maximize the reliability of a single system, and which maximize the expected number of systems that perform satisfactorily out of a total assembly of J systems.     

A vertex-closing approach to the p-center problem

This article uses a vertex-closing approach to investigate the p-center problem. The optimal set of vertices to close are found in imbedded subgraphs of the original graph. Properties of these subgraphs are presented and then used to characterize the optimal solution, to establish a priori upper and lower bounds, to establish refined lower bounds, and to verify the optimality of solutions. These subgraphs form the foundation of two polynomial algorithms of complexity O(|E| log |E|) and O(|E|²). The algorithms are proven to converge to an optimum for special cases, and computational evidence is provided which suggests that they produce very good solutions more generally. Both algorithms perform very well on problems where p is large relative to the number of vertices n, specifically, when p/n ≥ 0.30. One of the algorithms is especially efficient for solving a sequence of problems on the same graph.     

The inventory packing problem

We study the problem of finding the minimum number of identical storage areas required to hold n items for which demand is known and constant. The replenishments of the items within a single storage area may be time phased so as to minimize the maximum total storage capacity required at any time. This is the inventory-packing problem, which can be considered as a variant of the well-known bin-packing problem, where one constraint is nonlinear. We study the worst-case performance of six heuristics used for that earlier problem since the recognition version of the inventory-packing problem is shown to be NP complete. In addition, we describe several new heuristics developed specifically for the inventory-packing problem, and also study their worst-case performance. Any heuristic which only opens a bin when an item will not fit in any (respectively, the last) open bin needs, asymptotically, no more than 25/12 (resp., 9/4) times the optimal number of bins. Improved performance bounds are obtainable if the range from which item sizes are taken is known to be restricted. Extensive computational testing indicates that the solutions delivered by these heuristics are, for most problems, very close to optimal in value.     

Periodic review inventory management with contingent use of two freight modes with fixed costs

We study a stochastic inventory model of a firm that periodically orders a product from a make‐to‐order manufacturer. Orders can be shipped by a combination of two freight modes that differ in lead‐times and costs, although orders are not allowed to cross. Placing an order as well as each use of each freight mode has a fixed and a quantity proportional cost. The decision of how to allocate units between the two freight modes utilizes information about demand during the completion of manufacturing. We derive the optimal freight mode allocation policy, and show that the optimal policy for placing orders is not an (s,S) policy in general. We provide tight bounds for the optimal policy that can be calculated by solving single period problems. Our analysis enables insights into the structure of the optimal policy specifying the conditions under which it simplifies to an (s,S) policy. We characterize the best (s,S) policy for our model, and through extensive numerical investigation show that its performance is comparable with the optimal policy in most cases. Our numerical study also sheds light on the benefits of the dual freight model over the single freight models. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Bounds on the availability function

This paper gives bounds on the availability function for an alternating renewal process with exponential failure and general repair times. A bound on the error is also given. Several of the bounds with greatest practical consequence are worked out and illustrated. Repair distributions for which a lower bound on availability is easily computed are gamma (integer shape parameter), log normal, and Weibull. Finally, some simulation results for log normal repair versus gamma repair are given.     

Inventory policies with quantized ordering

This article studies (nQ, r) inventory policies, under which the order quantity is restricted to be an integer multiple of a base lot size Q. Both Q and r are decision variables. Assuming the one-period expected holding and backorder cost function is unimodal, we develop an efficient algorithm to compute the optimal Q and r. The algorithm is facilitated by simple observations about the cost function and by tight upper bounds on the optimal Q. The total number of elementary operations required by the algorithm is linear in these upper bounds. By using the algorithm, we compare the performance of the optimal (nQ, r) policy with that of the optimal (s, S) policy through a numerical study, and our results show that the difference between them is small. Further analysis of the model shows that the cost performance of an (nQ, r) policy is insensitive to the choice of Q. These results establish that (nQ, r) models are potentially useful in many settings where quantized ordering is beneficial.     

Lagrangian solution of maximum dispersion problems

We address the so‐called maximum dispersion problems where the objective is to maximize the sum or the minimum of interelement distances amongst a subset chosen from a given set. The problems arise in a variety of contexts including the location of obnoxious facilities, the selection of diverse groups, and the identification of dense subgraphs. They are known to be computationally difficult. In this paper, we propose a Lagrangian approach toward their solution and report the results of an extensive computational experimentation. Our results show that our Lagrangian approach is reasonably fast, that it yields heuristic solutions which provide good lower bounds on the optimum solution values for both the sum and the minimum problems, and further that it produces decent upper bounds in the case of the sum problem. For the sum problem, the results also show that the Lagrangian heuristic compares favorably against several existing heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 97–114, 2000     

Probability inequalities via negative dependence for random variables conditioned on order statistics

Distributions are studied which arise by considering independent and identically distributed random variables conditioned on events involving order statistics. It is shown that these distributions are negatively dependent in a very strong sense. Furthermore, bounds are found on the distribution functions. The conditioning events considered occur naturally in reliability theory as the time to system failure for k-out-of-n systems. An application to systems formed with “second-hand” components is given.     

On competitive analysis for polling systems

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.     

On a class of multiple failure mode systems

The primary objective of this work is to introduce and perform a detailed study of a class of multistate reliability structures in which no ordering in the levels of components' performances is necessary. In particular, the present paper develops the basic theory (exact reliability formulae, reliability bounds, asymptotic results) that will make it feasible to investigate systems whose components are allowed to experience m ≥ 2 kinds of failure (failure modes), and their breakdown is described by different families of cut sets in each mode. For illustration purposes, two classical (binary) systems are extended to analogous multiple failure mode structures, and their reliability performance (bounds and asymptotic behavior) is investigated by numerical experimentation. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 167–185, 2002; DOI 10.1002/nav.10007     

Heuristics for multimachine minmax scheduling problems with general earliness and tardiness costs

We consider the problem of scheduling N jobs on M parallel machines so as to minimize the maximum earliness or tardiness cost incurred for each of the jobs. Earliness and tardiness costs are given by general (but job-independent) functions of the amount of time a job is completed prior to or after a common due date. We show that in problems with a nonrestrictive due date, the problem decomposes into two parts. Each of the M longest jobs is assigned to a different machine, and all other jobs are assigned to the machines so as to minimize their makespan. With these assignments, the individual scheduling problems for each of the machines are simple to solve. We demonstrate that several simple heuristics of low complexity, based on this characterization, are asymptotically optimal under mild probabilistic conditions. We develop attractive worst-case bounds for them. We also develop a simple closed-form lower bound for the minimum cost value. The bound is asymptotically accurate under the same probabilistic conditions. In the case where the due date is restrictive, the problem is more complex only in the sense that the set of initial jobs on the machines is not easily characterized. However, we extend our heuristics and lower bounds to this general case as well. Numerical studies exhibit that these heuristics perform excellently even for small- or moderate-size problems both in the restrictive and nonrestrictive due-date case. © 1997 John Wiley & Sons, Inc.     

Failure profiles of coherent systems

In this paper we first introduce and study the notion of failure profiles which is based on the concepts of paths and cuts in system reliability. The relationship of failure profiles to two notions of component importance is highlighted, and an expression for the density function of the lifetime of a coherent system, with independent and not necessarily identical component lifetimes, is derived. We then demonstrate the way that failure profiles can be used to establish likelihood ratio orderings of lifetimes of two systems. Finally we use failure profiles to obtain bounds, in the likelihood ratio sense, on the lifetimes of coherent systems with independent and not necessarily identical component lifetimes. The bounds are relatively easy to compute and use. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004