Optimal arrangement of systems

To location L_i we are to allocate a “generator” and n_i “machines” for i = 1, …,k, where n₁ … n₁ ≧ … ≧ n_k. Although the generators and machines function independently of one another, a machine is operable only if it and the generator at its location are functioning. The problem we consider is that of finding the arrangement or allocation optimizing the number of operable machines. We show that if the objective is to maximize the expected number of operable machines at some future time, then it is best to allocate the best generator and the n₁ best machines to location L₁, the second-best generator and the n₂-next-best machines to location L₂, etc. However, this arrangement is not always stochastically optimal. For the case of two generators we give a necessary and sufficient condition that this arrangement is stochastically best, and illustrate the result with several examples.     

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).     

Scheduling with earliest start and due date constraints on multiple machines

We consider the scheduling of n jobs on m identical machines when the jobs become available for processing at ready times a_i, a_i, ? 0, require d_i time units for processing and must be completed by times b_i for i = 1, 2, … n. The objective chosen is that of minimizing the total elapsed time to complete all jobs subject to the ready time and due date constraints, preemption is not allowed. We present a multi-stage solution algorithm for this problem that is based on an implicit enumeration procedure and also uses the labelling type algorithm which solves the problem when preemption is allowed.     

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.     

The determination of optimal base-stock inventory policy when the costs of under- and oversupply are uncertain

This article considers the determination of the optimal base-stock inventory policy for the newsboy inventory model when there is uncertainty about either or both of its basic cost inputs: either C_u, the marginal cost of an undersupply mistake, or C_o, the marginal cost of an oversupply mistake. Such uncertainties often arise in implementing the newsboy model, especially with respect to C_u, whose value depends mostly on the often-imponderable economic consequences of a lost sale or backorder. Given this uncertainty, we use decision theory to propose and analyze two measures of policy “goodness” and two base-stock selection criteria, which in combination provide four alternative “optimal” base-stock policies. Formulas and/or conditions defining each alternative policy are provided. Our empirical study indicates that the recommended policy can be quite sensitive to the measure/criterion chosen, and that the consequences of the wrong choice can be quite considerable.     

Mathematical aspects of the 3 × n job-shop sequencing problem

The paper discusses mathematical properties of the well-known Bellman-Johnson 3 × n sequencing problem. Optimal rules for some special cases are developed. For the case min B_i ≥ maxA_j we find an optimal sequence of the 2 × n problem for machines B and C and move one item to the front of the sequence to minimize (7); when min B_i ≥ max C_j we solve a 2 × n problem for machines A and B and move one item to the end of the optimal sequence so as to minimize (9). There is also given a sufficient optimality condition for a solution obtained by Johnson's approximate method. This explains why this method so often produces an optimal solution.     

A heterogeneous arrival and service queueing loss model

Consider a single-server exponential queueing loss system in which the arrival and service rates alternate between the paris (γ₁, γ₁), and (γ₂, μ₂), spending an exponential amount of time with rate cμ_i in (γ_i, μ_i), i = 1.2. It is shown that if all arrivals finding the server busy are lost, then the percentage of arrivals lost is a decreasing function of c. This is in line with a general conjecture of Ross to the effect that the “more nonstationary” a Poisson arrival process is, the greater the average customer delay (in infinite capacity models) or the greater the precentage of lost customers (in finite capacity models). We also study the limiting cases when c approaches 0 or infinity.     

Decomposition algorithms for minimal cut problems

Consider a network G(N. A) with n nodes, where node 1 designates its source node and node n designates its sink node. The cuts (Z_i, =), i= 1…, n - 1 are called one-node cuts if 1 ? Z_i,. n q Z_i, Z₁-_? {1}, Z_i ? Z_i+1 and Z_i and Z_i+l differ by only one node. It is shown that these one-node cuts decompose G into 1 m n/2 subnetworks with known minimal cuts. Under certain circumstances, the proposed one-node decomposition can produce a minimal cut for G in 0(n² ) machine operations. It is also shown that, under certain conditions, one-node cuts produce no decomposition. An alternative procedure is also introduced to overcome this situation. It is shown that this alternative procedure has the computational complexity of 0(n³).     

A note on minimizing the expected makespan in flowshops subject to breakdowns

Consider a two machine flow shop and n jobs. The processing time of job j on machine i is equal to the random variable X_ij One of the two machines is subject to breakdown and repair. The objective is to find the schedule that minimizes the expected makespan. Two results are shown. First, ifP(X_2j ≧ X_1j) = 1 for all j and the random variables X₁₁, X₁₂,…, X_1n are likelihood ratio ordered, then the SEPT sequence minimizes the expected makespan when machine 2 is subject to an arbitrary breakdown process; if P(X_1j≧X_2j) = 1 and X₂₁, X₂₂,….,X_2n are likelihood ratio ordered, then the LEPT sequence minimizes the expected makespan when machine 1 is subject to an arbitrary breakdown process. A generalization is presented for flow shops with m machines. Second, consider the case where X_1j and X_2j are i.i.d. exponentially distributed with rate λ_j. The SEPT sequence minimizes the expected makespan when machine 2 is subject to an arbitrary breakdown process and the LEPT sequence is optimal when machine 1 is subject to an arbitrary breakdown process. © 1995 John Wiley & Sons, Inc.     

The asymptotic joint distribution of the state occupancy times in an alternating renewal process

An alternating renewal process starts at time zero and visits states 1,2,…,r, 1,2, …,r 1,2, …,r, … in sucession. The time spent in state i during any cycle has cumulative distribution function F_i, and the sojourn times in each state are mutually independent, positive and nondegenerate random variables. In the fixed time interval [0,T], let U_i(T) denote the total amount of time spent in state i. In this note, a central limit theorem is proved for the random vector (U_i(T), 1 ≤ i ≤ r) (properly normed and centered) as T → ∞.     

A new outranking‐based approach for assigning alternatives to ordered classes

We consider the problem of assigning alternatives evaluated on several criteria into ordered categories C₁,C₂,…,C_p. This problem is known as the multi‐criteria sorting problem and arises in many situations such as classifying countries into different risk levels based on economical and socio‐political criteria, evaluating credit applications of bank customers. We are interested in sorting methods that are grounded on the construction of outranking relations. Among these, the Electre Tri method requires defining multidimensional profiles that represent the “frontier” separating consecutive categories C_h and C_h+1, and assigns an alternative to categories according to how it compares to each of the profiles. The explicit specification of the profiles of consecutive categories can be difficult for decision makers. We develop a new outranking based sorting method that does not require the explicit definition of profiles. We instead require the decision maker to assign a subset of reference alternatives to the categories. To assign the remaining alternatives, each such alternative is compared to reference alternatives, and assigned to categories accordingly. © 2008 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.     

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 note on a stochastic production-maximizing transportation problem

A stochastic production-maximizing problem with transportation constraints is considered where the production rates, R_ij, of man i — job j combinations are random variables rather than constants. It is shown that for the family of Weibull distributions (of which the Exponential is a special case) with scale parameters λ_ij and shape parameter β, the plan that maximizes the expected rate of the entire line is obtained by solving a deterministic fixed charge transportation problem with no linear costs and with “set-up” cost matrix ‖λ_ij‖.     

An algorithm for separable piecewise convex programming problems

We present a branch and bound algorithm to solve mathematical programming problems of the form: Find x =|(x₁,…x_n) to minimize Σ?_i0(x₁) subject to x?G, l≦x≦L and Σ?_i0(x₁)≦0, j=1,…,m. With l=(l₁,…,l_n) and L=(L₁,…,L_n), each ?_ij is assumed to be lower aemicontinuous and piecewise convex on the finite interval [l_i.L_i]. G is assumed to be a closed convex set. The algorithm solves a finite sequence of convex programming problems; these correspond to successive partitions of the set C={x|l ≦ x ≦L} on the bahis of the piecewise convexity of the problem functions ?_ij. Computational considerations are discussed, and an illustrative example is presented.     

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     

The “signature” of a coherent system and its application to comparisons among systems

Various methods and criteria for comparing coherent systems are discussed. Theoretical results are derived for comparing systems of a given order when components are assumed to have independent and identically distributed lifetimes. All comparisons rely on the representation of a system's lifetime distribution as a function of the system's “signature,” that is, as a function of the vector p= (p₁, … , p_n), where p_i is the probability that the system fails upon the occurrence of the ith component failure. Sufficient conditions are provided for the lifetime of one system to be larger than that of another system in three different senses: stochastic ordering, hazard rate ordering, and likelihood ratio ordering. Further, a new preservation theorem for hazard rate ordering is established. In the final section, the notion of system signature is used to examine a recently published conjecture regarding componentwise and systemwise redundancy. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 507–523, 1999     

Isotonic median regression for orders representable by rooted trees

The isotonic median regression problem arising in statistics is as follows. We are given m observations falling into n sets, the ith set containing m_i observations. The problem requires the determination of n real numbers, the ith being the value “fitted” to each observation in the ith set. These n numbers chosen must satisfy certain (total or partial) order requirements and minimize the distance between the vectors of observed and fitted values in the l₁ norm. We present a simple algorithm, of time complexity O(mn), for calculating isotonic median regression for orders representable by rooted trees. We believe that this algorithm is the best currently available for this problem. The algorithm is validated by a linear programming approach which provides additional insight.     

Stochastic comparisons for single-server queues

We consider single-server queueing systems with the queue discipline “first come, first served,” interarrival times {u_k, k ≥ l}, and service times {u_k, k ≥ l}, where the {u_k} and {u_k} are independent sequences of non-negative random variables that are independently but not necessarily identically distributed. Let X_k = u_k − u_k (k ≥ 1), S₀ 0, S_n = X₁ + X₂ … + X_n(n≥1). It is known that the (possibly nonhomogeneous) random walk {S_n} determines the behavior of the system. In this paper we make stochastic comparisons of two such systems σ₁,σ₂ whose basic random variables X and X are stochastically ordered. The corresponding random walks are also similarly ordered, and this leads to stochastic comparisons of idle times, duration of busy period and busy cycles, number of customers served during a busy period, and output from the system. In the classical case of identical distributions of {u_k} and {u_k} we obtain further comparisons. Our results are for the transient behavior of the systems, not merely for steady state.