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     

Reliability of a 2‐dimensional k‐within‐consecutive‐r × s‐out‐of‐m × n:F system

A 2‐dimensional rectangular (cylindrical) k‐within‐consecutive‐r × s‐out‐of‐m × n:F system is the rectangular (cylindrical) m × n‐system if the system fails whenever k components in a r × s‐submatrix fail. This paper proposes a recursive algorithm for the reliability of the 2‐dimensional k‐within‐consecutive‐r × s‐out‐m × n:F system, in the rectangular case and the cylindrical case. This algorithm requires min ( O (mk^r(n?s)), O (nk^s(m?r))), and O (mk^rn) computing time in the rectangular case and the cylindrical case, respectively. The proposed algorithm will be demonstrated and some numerical examples will be shown. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 625–637, 2001.     

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.     

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.     

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     

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     

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     

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     

Openshop scheduling under linear resources constraints

Consider n jobs (J₁, …, J_n), m working stations (M₁, …, M_m) and λ linear resources (R₁, …, R_λ). Job J_i consists of m operations (O_i1, …, O_im). Operation O_ij requires P_k(i, j) units of resource R_k to be realized in an M_j. The availability of resource R_k and the ability of the working station M_h to consume resource R_k, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998     

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     

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     

Selecting review periods for a coordinated multi‐item inventory model with staggered deliveries

Consider an N‐item, periodic review, infinite‐horizon, undiscounted, inventory model with stochastic demands, proportional holding and shortage costs, and full backlogging. For 1 ≤ j ≤ N, orders for item j can arrive in every period, and the cost of receiving them is negligible (as in a JIT setting). Every T_j periods, one reviews the current stock level of item j and decides on deliveries for each of the next T_j periods, thus incurring an item‐by‐item fixed cost k_j. There is also a joint fixed cost whenever any item is reviewed. The problem is to find review periods T₁, T₂, …, T_N and an ordering policy satisfying the average cost criterion. The current article builds on earlier results for the single‐item case. We prove an optimal policy exists, give conditions where it has a simple form, and develop a branch and bound algorithm for its computation. We also provide two heuristic policies with O(N) computational requirements. Computational experiments indicate that the branch and bound algorithm can handle normal demand problems with N ≤ 10 and that both heuristics do well for a wide variety of problems with N ranging from 2 to 200; moreover, the performance of our heuristics seems insensitive to N. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:430–449, 2001     

Consecutive k‐within‐m‐out‐of‐n:F system with exchangeable components

As a generalization of k‐out‐of‐n:F and consecutive k‐out‐of‐n:F systems, the consecutive k‐within‐m‐out‐of‐n:F system consists of n linearly ordered components such that the system fails iff there are m consecutive components which include among them at least k failed components. In this article, the reliability properties of consecutive k‐within‐m‐out‐of‐n:F systems with exchangeable components are studied. The bounds and approximations for the survival function are provided. A Monte Carlo estimator of system signature is obtained and used to approximate survival function. The results are illustrated and numerics are provided for an exchangeable multivariate Pareto distribution. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

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.     

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.     

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.     

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.     

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     

Dynamic lot‐sizing model with production time windows

We consider a dynamic lot‐sizing model with production time windows where each of n demands has earliest and latest production due dates and it must be satisfied during the given time window. For the case of nonspeculative cost structure, an O(nlogn) time procedure is developed and it is shown to run in O(n) when demands come in the order of latest production due dates. When the cost structure is somewhat general fixed plus linear that allows speculative motive, an optimal procedure with O(T⁴) is proposed where T is the length of a planning horizon. Finally, for the most general concave production cost structure, an optimal procedure with O(T⁵) is designed. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Johnson's approximate method for the 3 × n job shop problem

The effectiveness of Johnson's Approximate Method (JAM) for the 3 × n job shop scheduling problems was examined on 1,500 test cases with n ranging from 6 to 50 and with the processing times A_i, B_i, C_i (for item i on machines A, B, C) being uniformly and normally distributed. JAM proved to be quite effective for the case B_i ? max (A_i, C_i) and optimal for B_i, ? min (A_i, C_i).