Technical note: Find a hidden “treasure”

This paper deals with a two searchers game and it investigates the problem of how the possibility of finding a hidden object simultaneously by players influences their behavior. Namely, we consider the following two‐sided allocation non‐zero‐sum game on an integer interval [1,n]. Two teams (Player 1 and 2) want to find an immobile object (say, a treasure) hidden at one of n points. Each point i ∈ [1,n] is characterized by a detection parameter λ_i (μ_i) for Player 1 (Player 2) such that p_i(1 ? exp(?λ_ix_i)) (p_i(1 ? exp(?μ_iy_i))) is the probability that Player 1 (Player 2) discovers the hidden object with amount of search effort x_i (y_i) applied at point i where p_i ∈ (0,1) is the probability that the object is hidden at point i. Player 1 (Player 2) undertakes the search by allocating the total amount of effort X(Y). The payoff for Player 1 (Player 2) is 1 if he detects the object but his opponent does not. If both players detect the object they can share it proportionally and even can pay some share to an umpire who takes care that the players do not cheat each other, namely Player 1 gets q₁ and Player 2 gets q₂ where q₁ + q₂ ≤ 1. The Nash equilibrium of this game is found and numerical examples are given. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Distribution of sample correlation coefficients

Let (Y, X_l,…, X_K) be a random vector distributed according to a multivariate normal distribution where X_l,…, X_K are considered as predictor variables and y is the predictand. Let r_i, and R_i denote the population and sample correlation coefficients, respectively, between Y and X_i. The population correlation coefficient r_i is a measure of the predictive power of X_i. The author has derived the joint distribution of R_l,…, R_K and its asymptotic property. The given result is useful in the problem of selecting the most important predictor variable corresponding to the largest absolute value of r_i.     

Optimal policies for M/M/m queue with two different kinds of (N,T)‐policies

In this paper, two different kinds of (N, T)‐policies for an M/M/m queueing system are studied. The system operates only intermittently and is shut down when no customers are present any more. A fixed setup cost of K > 0 is incurred each time the system is reopened. Also, a holding cost of h > 0 per unit time is incurred for each customer present. The two (N, T)‐policies studied for this queueing system with cost structures are as follows: (1) The system is reactivated as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T, and (2) the system is reactivated as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. The equations satisfied by the optimal policy (N*, T*) for minimizing the long‐run average cost per unit time in both cases are obtained. Particularly, we obtain the explicit optimal joint policy (N*, T*) and optimal objective value for the case of a single server, the explicit optimal policy N* and optimal objective value for the case of multiple servers when only predefined customers number N is measured, and the explicit optimal policy T* and optimal objective value for the case of multiple servers when only predefined time units T is measured, respectively. These results partly extend (1) the classic N or T policy to a more practical (N, T)‐policy and (2) the conclusions obtained for single server system to a system consisting of m (m ≥ 1) servers. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 240–258, 2000     

Deterministic and stochastic scheduling with teamwork tasks

We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f₁(C₁), f₂(C₂), … , f_n(C_n)), where f_i(C_i) is a general, nondecreasing function of the completion time C_i of task i. We show that the optimal sequence to minimize the maximum cost MC = max f_i(C_i) can be derived by a simple rule if there exists an order f₁(t) ≤ … ≤ f_n(t) for all t between the functions {f_i(t)}. We further show that the optimal sequence to minimize the total cost TC = ∑ f_i(C_i) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

The asymptotic distribution of order statistics

For each n., X₁(n), X₂(n), …, X_n(n) are IID, with common pdf f_n(x). y₁(n) < … < Y_n (n) are the ordered values of X₁ (n), …, X_n(n). K_n is a positive integer, with lim K_n = ∞. Under certain conditions on K_n and f_n (x), it was shown in an earlier paper that the joint distribution of a special set of K_n + 1 of the variables Y₁ (n), …, Y_n (n) can be assumed to be normal for all asymptotic probability calculations. In another paper, it was shown that if f_n (x) approaches the pdf which is uniform over (0, 1) at a certain rate as n increases, then the conditional distribution of the order statistics not in the special set can be assumed to be uniform for all asymptotic probability calculations. The present paper shows that even if f_n (x) does not approach the uniform distribution as n increases, the distribution of the order statistics contained between order statistics in the special set can be assumed to be the distribution of a quadratic function of uniform random variables, for all asymptotic probability calculations. Applications to statistical inference are given.     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

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     

A note on scheduling parallel machines subject to breakdown and repair

In this paper we consider n jobs and a number of machines in parallel. The machines are identical and subject to breakdown and repair. The number may therefore vary over time and is at time t equal to m(t). Preemptions are allowed. We consider three objectives, namely, the total completion time, ∑ C_j, the makespan C_max, and the maximum lateness L_max. We study the conditions on m(t) under which various rules minimize the objective functions under consideration. We analyze cases when the jobs have deadlines to meet and when the jobs are subject to precedence constraints. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A O(nm log(U/n)) time maximum flow algorithm

In this paper, we present an O(nm log(U/n)) time maximum flow algorithm. If U = O(n) then this algorithm runs in O(nm) time for all values of m and n. This gives the best available running time to solve maximum flow problems satisfying U = O(n). Furthermore, for unit capacity networks the algorithm runs in O(n^2/3m) time. It is a two‐phase capacity scaling algorithm that is easy to implement and does not use complex data structures. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 511–520, 2000     

A compound measure of dependability for systems modeled by continuous-time absorbing Markov processes

The Markov analysis of reliability models frequently involves a partitioning of the state space into two or more subsets, each corresponding to a given degree of functionality of the system. A common partitioning is G ∪ B ∪ {o}, where G (good) and B (bad) stand, respectively, for fully and partially functional sets of system states; o denotes system failure. Visits to B may correspond to, for instance, reparable system downtimes, whereas o will stand for irrecoverable system failure. Let T_G and N_B stand, respectively, for the total time spent in G, and the number of visits to B, until system failure. Both T_G and N_B are familiar system performance measures with well-known cumulative distribution functions. In this article a closed-form expression is established for the probability Pr[T_G <> t, N_B ≤ n], a dependability measure with much intuitive appeal but which hitherto seems not to have been considered in the literature. It is based on a recent result on the joint distribution of sojourn times in subsets of the state space by a Markov process. The formula is explored numerically by the example of a power transmission reliability model. © 1996 John Wiley & Sons, Inc.     

Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness

We study a parallel machine scheduling problem, where a job j can only be processed on a specific subset of machines M_j, and the M_j subsets of the n jobs are nested. We develop a two‐phase heuristic for minimizing the total weighted tardiness subject to the machine eligibility constraints. In the first phase, we compute the factors and statistics that characterize a problem instance. In the second phase, we propose a new composite dispatching rule, the Apparent Tardiness Cost with Flexibility considerations (ATCF) rule, which is governed by several scaling parameters of which the values are determined by the factors obtained in the first phase. The ATCF rule is a generalization of the well‐known ATC rule which is very widely used in practice. We further discuss how to improve the dispatching rule using some simple but powerful properties without requiring additional computation time, and the improvement is quite satisfactory. We apply the Sequential Uniform Design Method to design our experiments and conduct an extensive computational study, and we perform tests on the performance of the ATCF rule using a real data set from a large hospital in China. We further compare its performance with that of the classical ATC rule. We also compare the schedules improved by the ATCF rule with what we believe are Near Optimal schedules generated by a general search procedure. The computational results show that especially with a low due date tightness, the ATCF rule performs significantly better than the well‐known ATC rule generating much improved schedules that are close to the Near Optimal schedules. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 249–267, 2017     

Steady-state analysis of load balancing with Coxian-2 distributed service times

This paper studies load balancing for many-server (N servers) systems. Each server has a buffer of size b ? 1, and can have at most one job in service and b ? 1 jobs in the buffer. The service time of a job follows the Coxian-2 distribution. We focus on steady-state performance of load balancing policies in the heavy traffic regime such that the normalized load of system is λ = 1 ? N^?α for 0 < α < 0.5. We identify a set of policies that achieve asymptotic zero waiting. The set of policies include several classical policies such as join-the-shortest-queue (JSQ), join-the-idle-queue (JIQ), idle-one-first (I1F) and power-of-d-choices (Po d) with d = O(N^α log N). The proof of the main result is based on Stein's method and state space collapse. A key technical contribution of this paper is the iterative state space collapse approach that leads to a simple generator approximation when applying Stein's method.     

The discrete search problem and the construction of optimal allocations

Suppose one object is hidden in the k-th of n boxes with probability p(k). The boxes are to be searched sequentially. Associated with the j-th search of box k is a cost c(j,k) and a conditional probability q(j,k) that the first j - 1 searches of box k are unsuccessful while the j-th search is successful given that the object is hidden in box k. The problem is to maximize the probability that we find the object if we are not allowed to offer more than L for the search. We prove the existence of an optimal allocation of the search effort L and state an algorithm for the construction of an optimal allocation. Finally, we discuss some problems concerning the complexity of our problem.     

Evaluating methods for the reliability of a large 2‐dimensional rectangular k‐within‐consecutive‐(r,s)‐out‐of‐(m,n):F system

A 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system consists of m × n components, and fails if and only if k or more components fail in an r × s submatrix. This system can be treated as a reliability model for TFT liquid crystal displays, wireless communication networks, etc. Although an effective method has been developed for evaluating the exact system reliability of small or medium‐sized systems, that method needs extremely high computing time and memory capacity when applied to larger systems. Therefore, developing upper and lower bounds and accurate approximations for system reliability is useful for large systems. In this paper, first, we propose new upper and lower bounds for the reliability of a 2‐dimensional rectangular k‐within‐consecutive‐(r, s)‐out‐of‐(m, n):F system. Secondly, we propose two limit theorems for that system. With these theorems we can obtain accurate approximations for system reliabilities when the system is large and component reliabilities are close to one. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Characterizations of the exponential distribution by higher-order gap

Suppose X₁,X₂, ?,X_n is a random sample of size n from a continuous distribution function F(x) and let X_1,n, ≦ X_2,n ≦ ? ≦ X_n,n be the corresponding order statistics. We define the jth-order gap g_i,j as g_i,j = X_i+j,n ? X_i,n, 1 ≦ i < n, 1 ≦ j ≦ n ? i. In this article characterizations of the exponential distribution are given by considering the distributional properties of g_k,n-k, 1 ≦ k ≦ n.     

On estimating the reliability of a component subject to several different stresses (strengths)

This paper is concerned with estimating p = P(X₁ < Y …, X_n < Y) or q =P (X < Y₁, …, X < Y_n) where the X's and Y's are all independent random variables. Applications to estimation of the reliability p from stress-strength relationships are considered where a component is subject to several stresses X₁, X₂, …, X_N whereas its strength, Y, is a single random variable. Similarly, the reliability q is of interest where a component is made of several parts all with their individual strengths Y₁, Y₂ …, Y_N and a single stress X is applied to the component. When the X's and Y's are independent and normal, maximum likelihood estimates of p and q have been obtained. For the case N = 2 and in some special cases, minimum variance unbiased estimates have been given. When the Y's are all exponential and the X is normal with known variance, but unknown mean (or uniform between 0 and θ, θ being unknown) the minimum variance unbiased estimate of q is established in this paper.     

On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Sojourn times in G/M/1 fork‐join networks

We consider a processing network in which jobs arrive at a fork‐node according to a renewal process. Each job requires the completion of m tasks, which are instantaneously assigned by the fork‐node to m task‐processing nodes that operate like G/M/1 queueing stations. The job is completed when all of its m tasks are finished. The sojourn time (or response time) of a job in this G/M/1 fork‐join network is the total time it takes to complete the m tasks. Our main result is a closed‐form approximation of the sojourn‐time distribution of a job that arrives in equilibrium. This is obtained by the use of bounds, properties of D/M/1 and M/M/1 fork‐join networks, and exploratory simulations. Statistical tests show that our approximation distributions are good fits for the sojourn‐time distributions obtained from simulations. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

On the first time a separately maintained parallel system has been down for a fixed time

Consider a system consisting of n separately maintained independent components where the components alternate between intervals in which they are “up” and in which they are “down”. When the i^th component goes up [down] then, independent of the past, it remains up [down] for a random length of time, having distribution F_i[G_i], and then goes down [up]. We say that component i is failed at time t if it has been “down” at all time points s ?[t-A.t]: otherwise it is said to be working. Thus, a component is failed if it is down and has been down for the previous A time units. Assuming that all components initially start “up,” let T denote the first time they are all failed, at which point we say the system is failed. We obtain the moment-generating function of T when n = l, for general F and G, thus generalizing previous results which assumed that at least one of these distributions be exponential. In addition, we present a condition under which T is an NBU (new better than used) random variable. Finally we assume that all the up and down distributions F_i and G_i i = l,….n, are exponential, and we obtain an exact expression for E(T) for general n; in addition we obtain bounds for all higher moments of T by showing that T is NBU.