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 absolute approximation algorithm for scheduling unrelated machines

Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 ? 1/m)p_max, p} is presented, where p_max is the largest job processing time and p is the mth element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p_max. The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm²) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Graph distance‐dependent labeling related to code assignment in computer networks

For nonnegative integers d₁, d₂, and L(d₁, d₂)‐labeling of a graph G, is a function f : V(G) → {0, 1, 2, …} such that |f(u) − f(v)| ≥ d_i whenever the distance between u and v is i in G, for i = 1, 2. The L(d₁, d₂)‐number of G, λ(G) is the smallest k such that there exists an L(d₁, d₂)‐labeling with the largest label k. These labelings have an application to a computer code assignment problem. The task is to assign integer “control codes” to a network of computer stations with distance restrictions, which allow d₁ ≤ d₂. In this article, we will study the labelings with (d₁, d₂) ∈ {(0, 1), (1, 1), (1, 2)}. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Estimating moments of the minimum order statistic from normal populations—a bayesian approach

Let Yⁱ ∽ N(θⁱ, σ), i = 1, …, p, be independently distributed, where θⁱ and σ are unknown. A Bayesian approach is used to estimate the first two moments of the minimum order statistic, W = min (Y¹, …, Y^p). In order to compute the Bayes estimates, one has to evaluate the predictive densities of the Yⁱ's conditional on past data. Although the required predictive densities are complicated in form, an efficient algorithm to calculate them has been developed and given in the article. An application of the Bayesian method in a continuous-review control model with multiple suppliers is discussed. © 1994 John Wiley & Sons, Inc.     

Inventory policies for a make‐to‐order system with a perishable component and fixed ordering cost

We consider a make‐to‐order production system where two major components, one nonperishable (referred to as part 1) and one perishable (part 2), are needed to fulfill a customer order. In each period, replenishment decisions for both parts need to be made jointly before demand is realized and a fixed ordering cost is incurred for the nonperishable part. We show that a simple (s_n,S,S) policy is optimal. Under this policy, S along with the number of backorders at the beginning of a period if any and the availability of the nonperishable part (part 1) determines the optimal order quantity of the perishable part (part 2), while (s_n,S) guide when and how much of part 1 to order at each state. Numerical study demonstrates that the benefits of using the joint replenishment policy can be substantial, especially when the unit costs are high and/or the profit margin is low. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Confidence intervals for ranked means

Suppose that observations from populations π₁, …, π_k (k ≥ 1) are normally distributed with unknown means μ₁., μ_k, respectively, and a common known variance σ². Let μ_[1] μ … ≤ μ_[k] denote the ranked means. We take n independent observations from each population, denote the sample mean of the n observation from π₁ by X _i (i = 1, …, k), and define the ranked sample means X _[1] ≤ … ≤ X _[k]. The problem of confidence interval estimation of μ₍₁₎, …,μ_[k] is stated and related to previous work (Section 1). The following results are obtained (Section 2). For i = 1, …, k and any γ(0 < γ < 1) an upper confidence interval for μ_[i] with minimal probability of coverage γ is (? ∞, X _[i]+ h) with h = (σ/n^1/2) Φ^?1(γ^1/k-i+1), where Φ(·) is the standard normal cdf. A lower confidence interval for μ_[i] with minimal probability of coverage γ is (X _i[i] – g, + ∞) with g = (σ/n^1/2) Φ^?1(γ^1/i). For the upper confidence interval on μ_[i] the maximal probability of coverage is 1– [1 – γ^1/k-i+1]ⁱ, while for the lower confidence interval on μ_[i] the maximal probability of coverage is 1–[1– γ^1/i] ^k-i+¹. Thus the maximal overprotection can always be calculated. The overprotection is tabled for k = 2, 3. These results extend to certain translation parameter families. It is proven that, under a bounded completeness condition, a monotone upper confidence interval h(X ₁, …, X _k) for μ_[i] with probability of coverage γ(0 < γ < 1) for all μ = (μ_[1], …,μ_[k]), does not exist.     

Some results of the queueing system E/M/c

This paper analyses the E/M/c queueing system and shows how to calculate the expected number in the system, both at a random epoch and immediately preceding an arrival. These expectations are expressed in terms of certain initial probabilities which are determined by linear equations. The advantages and disadvantages of this method are also discussed.     

Weighted vertex packing problem for specially structured geometric graphs

Consider a set of vertices V = {1, 2,…, n} placed on a two-dimensional Euclidean plane R² with each vertex attached a nonnegative weight w: V → R. For a given constant d>0, the geometric graph G = (V, E) is defined to have edge set E = {(i, j): d_ij ⩽ d} with d_ij being the Euclidean distance between vertices i and j. The geometric vertex packing (GVP) problem, which is often called the independent set problem, is defined as selecting the set of pairwise nonadjacent vertices with maximum total weight. We limit our attention to the special case that no vertex is within a distance βd of any other vertices where 0 ⩽ β < 1. A special value of β (= 1/2) is referred to frequently because of its correspondence to a manufacturing problem in circuit board testing. In this article we show that the weighted vertex packing problem for the specially structured geometric graph (SGVP) defined with the above restriction is NP-complete even for the case that all vertex weights are unity and for any β. Polynomial procedures have been designed for generating cuts to obtain tight LP upper bounds for the SGVP. Two heuristics with bounded worst-case performance are applied to the LP solution to produce a feasible solution and a lower bound. We then use a branch-and-bound procedure to solve the problem to optimality. Computational results on large-scale SGVP problems will be discussed. © 1995 John Wiley & Sons, Inc.     

Scheduling multiple products on parallel machines with setup costs

We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time p_i to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of n_i units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost c is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo‐polynomial time. The polynomiality or pseudo‐polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89–96) and Zangwill (Oper Res 14 (1966), 486–507; Manage Sci 15 (1969), 506–527). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling deteriorating jobs to minimize makespan

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J_j grows by w_j with each time unit its start is delayed beyond a given common critical date d. This processing time is p_j if J_j starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n²d(D − d) time and O(nd(D − d)) space, the other runs in p_j)²) time and p_j) space. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

Readiness and the optimal redeployment of resources

This paper considers the problem of the optimal redeployment of a resource among different geographical locations. Initially, it is assumed that at each location i, i = 1,…, n, the level of availability of the resource is given by a₁ ≧ 0. At time t > 0, requirements R_f(t) ≧ 0 are imposed on each location which, in general, will differ from the a₁. The resource can be transported from any one location to any other in magnitudes which will depend on t and the distance between these locations. It is assumed that ΣR_j > Σa_t The objective function consideis, in addition to transportation costs incurred by reallocation, the degree to which the resource availabilities after redeployment differ from the requirements. We shall associate the unavailabilities at the locations with the unreadiness of the system and discuss the optimal redeployment in terms of the minimization of the following functional forms: \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj) + } $\end{document} transportation costs, Max \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {Max}\limits_j \,[kj(Rj - yj)] + $\end{document} transportation costs, and \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj)^2 + } $\end{document} transportation costs. The variables y_j represent the final amount of the resource available at location j. No benefits are assumed to accrue at any location if y_j > R_j. A numerical three location example is given and solved for the linear objective.     

Asymptotic inference about a density function at an end of its range

For each n, X₁(n),…X_n(n) are independent and identically distributed random variables, with common probability density function Where c, θ, α, and r(y) are all unknown. It is shown that we can make asymptotic inferences about c, θ, and α, when r(y) satisfies mild conditions.     

On a sequential rule for estimating the location parameter of an exponential distribution

Let us assume that observations are obtained at random and sequentially from a population with density function In this paper we consider a sequential rule for estimating μ when σ is unknown corresponding to the following class of cost functions In this paper we consider a sequential rule for estimating μ when σ is unknown corresponding to the following class of cost functions Where δ(X_I,…,X_N) is a suitable estimator of μ based on the random sample (X₁,…, X_N), N is a stopping variable, and A and p are given constants. To study the performance of the rule it is compared with corresponding “optimum fixed sample procedures” with known σ by comparing expected sample sizes and expected costs. It is shown that the rule is “asymptotically efficient” when absolute loss (p=-1) is used whereas the one based on squared error (p = 2) is not. A table is provided to show that in small samples similar conclusions are also true.     

The knapsack problem: A survey

A unifying survey of the literature related to the knapsack problem; that is, maximize \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_i {v_i x_{i,} } $\end{document}, subject to \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_j {w_i x_i W} $\end{document} and x_i ? 0, integer; where v_i, w_i and W are known integers, and w_i (i = 1, 2, …, N) and W are positive. Various uses, including those in group theory and in other integer programming algorithms, as well as applications from the literature, are discussed. Dynamic programming, branch and bound, search enumeration, heuristic methods, and other solution techniques are presented. Computational experience, and extensions of the knapsack problem, such as to the multi-dimensional case, are also considered.     

Vehicle routing problems with regular objective functions on a path

We investigate the problem of scheduling a fleet of vehicles to visit the customers located on a path to minimize some regular function of the visiting times of the customers. For the single‐vehicle problem, we prove that it is pseudopolynomially solvable for any minsum objective and polynomially solvable for any minmax objective. Also, we establish the NP‐hardness of minimizing the weighted number of tardy customers and the total weighted tardiness, and present polynomial algorithms for their special cases with a common due date. For the multivehicle problem involving n customers, we show that an optimal solution can be found by solving or O(n) single‐vehicle problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 34–43, 2014     

An alternative proof of the IFRA property of some shock models

Let , where A (t)/t is nondecreasing in t, {P(k)^1/k} is nonincreasing. It is known that H(t) = 1 — H (t) is an increasing failure rate on the average (IFRA) distribution. A proof based on the IFRA closure theorem is given. H(t) is the distribution of life for systems undergoing shocks occurring according to a Poisson process where P (k) is the probability that the system survives k shocks. The proof given herein shows there is an underlying connection between such models and monotone systems of independent components that explains the IFRA life distribution occurring in both models.     

Proportionate flow shop: New complexity results and models with due date assignment

It is known that the proportionate flow shop minimum makespan $Fm/prpt/C_{\max }$ problem is solved optimally by any permutation job sequence. We show that the $Fm/prpt/C_{\max }$ problem is at least ordinary NP‐hard when missing operations are allowed and present some solvable cases. We then consider the standard proportionate flow shop problem (with no missing operations) and show that the solution algorithms for a class of single‐machine due date assignment problems can be extended/generalized to the corresponding proportionate flow shop problems. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 98–106, 2015     

A stochastic assignment problem

There are n boxes with box i having a quota value Balls arrive sequentially, with each ball having a binary vector attached to it, with the interpretation being that if X_i = 1 then that ball is eligible to be put in box i. A ball's vector is revealed when it arrives and the ball can be put in any alive box for which it is eligible, where a box is said to be alive if it has not yet met its quota. Assuming that the components of a vector are independent, we are interested in the policy that minimizes, either stochastically or in expectation, the number of balls that need arrive until all boxes have met their quotas. © 2014 Wiley Periodicals, Inc. 62:23–31, 2015     

Estimating a survival curve when new is better than used with respect to a distinguished set

Hollander, Park, and Proschan define a survival function S of a positive random variable X to be new better than used at age t₀ (NBU-{t₀}) if S satisfies $ \begin{array}{*{20}c} {\frac{{S(x + t_0)}}{{S\left({t_0} \right)}} \le S\left(x \right),} & {{\rm for}\,{\rm all}\,x\, \ge \,0,} \\ \end{array}$ where S(x) = P(X > x). The NBU-{t₀} class is a special case of the NBU-A family of survival distributions, where A is a subset of [0, ∞). These families introduce a variety of modeling possibilities for use in reliability studies. We treat problems of nonparametric estimation of survival functions from these classes by estimators which are themselves members of the classes of interest. For a number of such classes, a recursive estimation technique is shown to produce closed-form estimators which are strongly consistent and converge to the true survival distribution at optimal rates. For other classes, additional assumptions are required to guarantee the consistency of recursive estimators. As an example of the latter case, we demonstrate the consistency of a recursive estimator for S ∈ NBU-[t₀, ∞) based on lifetime data from items surviving a preliminary “burn-in” test. The relative precision of the empirical survival curve and several recursive estimators of S are investigated via simulation; the results provide support for the claim that recursive estimators are superior to the empirical survival curve in restricted nonparametric estimation problems of the type studied here.