Algorithms for minimizing total cost,bottleneck time and bottleneck shipment in transportation problems

We consider the transportation problem of determining nonnegative shipments from a set of m warehouses with given availabilities to a set of n markets with given requirements. Three objectives are defined for each solution: (i) total cost, TC, (ii) bottleneck time, BT (i.e., maximum transportation time for a positive shipment), and (iii) bottleneck shipment, SB (i.e., total shipment over routes with bottleneck time). An algorithm is given for determining all efficient (pareto-optimal or nondominated) (TC, BT) solution pairs. The special case of this algorithm when all the unit cost coefficients are zero is shown to be the same as the algorithms for minimizing BT. provided by Szwarc and Hammer. This algorithm for minimizing BT is shown to be computationally superior. Transportation or assignment problems with m=n=100 average about a second on the UNIVAC 1108 computer (FORTRAN V)) to the threshold algorithm for minimizing BT. The algorithm is then extended to provide not only all the efficient (TC, BT) solution pairs but also, for each such BT, all the efficient (TC, SB) solution pairs. The algorithms are based on the cost operator theory of parametric programming for the transportation problem developed by the authors.     

Applications of renewal theory in analysis of the free-replacement warranty

Under a free-replacement warranty of duration W, the customer is provided, for an initial cost of C, as many replacement items as needed to provide service for a period W. Payments of C are not made at fixed intervals of length W, but in random cycles of length Y = W + γ(W), where γ(W) is the (random) remaining life-time of the item in service W time units after the beginning of a cycle. The expected number of payments over the life cycle, L, of the item is given by M_Y(L), the renewal function for the random variable Y. We investigate this renewal function analytically and numerically and compare the latter with known asymptotic results. The distribution of Y, and hence the renewal function, depends on the underlying failure distribution of the items. Several choices for this distribution, including the exponential, uniform, gamma and Weibull, are considered.     

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     

A general treatment of upper unbounded and bounded hitchcock problems

This paper is designed to treat (a) the problem of the determination of the absolute minimum cost, with the associated assignments, when there is no limit, N, on the number of parcels available for shipment in a modified Hitchcock problem. This is accomplished with the use of a transformed cost matrix. C*, to which the so-called transportation paradox does not apply. The general Hitchcock solution using C* gives the cost T*, which is the absolute minimum cost of the original problem, as well as sets of assignments which are readily transformed to give the general assignments of the original problem. The sum of these latter assignments gives the value of N_u, the unbounded N for minimum cost. In addition, this paper is designed to show (b) how the method of reduced matrices may be used, (c) how a particular Hitchcock solution can be used to determine a general solution so that one solution using C* can provide the general answer, (d) how the results may be modified to apply to problems with fixed N, and hence (e) to determine the function of the decreasing T as N approaches N_u, and finally (f) to provide a treatment when the supplies at origin i and/or the demands at destination j, are bounded.     

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.     

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 analysis of some algorithms for generating random variates with a given hazard rate

We analyze the expected time performance of two versions of the thinning algorithm of Lewis and Shedler for generating random variates with a given hazard rate on [0,∞]. For thinning with fixed dominating hazard rate g(x) = c for example, it is shown that the expected number of iterations is cE(X) where X is the random variate that is produced. For DHR distributions, we can use dynamic thinning by adjusting the dominating hazard rate as we proceed. With the aid of some inequalities, we show that this improves the performance dramatically. For example, the expected number of iterations is bounded by a constant plus E(log₊(h(0)X)) (the logarithmic moment of X).     

Estimating critical path and arc probabilities in stochastic activity networks

This article describes a new procedure for estimating parameters of a stochastic activity network of N arcs. The parameters include the probability that path m is the longest path, the probability that path m is the shortest path, the probability that arc i is on the longest path, and the probability that arc i is on the shortest path. The proposed procedure uses quasirandom points together with information on a cutset ? of the network to produce an upper bound of O[(log K)^N?|?|+1/K] on the absolute error of approximation, where K denotes the number of replications. This is a deterministic bound and is more favorable than the convergence rate of 1/K^1/2 that one obtains from the standard error for K independent replications using random sampling. It is also shown how series reduction can improve the convergence rate by reducing the exponent on log K. The technique is illustrated using a Monte Carlo sampling experiment for a network of 16 relevant arcs with a cutset of ? = 7 arcs. The illustration shows the superior performance of using quasirandom points with a cutset (plan A) and the even better performance of using quasirandom points with the cutset together with series reduction (plan B) with regard to mean square error. However, it also shows that computation time considerations favor plan A when K is small and plan B when K is large.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

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     

A solution for queues with instantaneous jockeying and other customer selection rules

This paper presents a general solution for the M/M/r queue with instantaneous jockeying and r > 1 servers. The solution is obtained in matrices in closed form without recourse to the generating function arguments usually used. The solution requires the inversion of two (Z^r?1) × (2^r?1) matrices. The method proposed is extended to allow different queue selection preferences of arriving customers, balking of arrivals, jockeying preference rules, and queue dependent selection along with jockeying. To illustrate the results, a problem previously published is studied to show how known results are obtained from the proposed general solution.     

The solution to an open problem for a caching game

In a caching game introduced by Alpern et al. (Alpern et al., Lecture notes in computer science (2010) 220–233) a Hider who can dig to a total fixed depth normalized to 1 buries a fixed number of objects among n discrete locations. A Searcher who can dig to a total depth of h searches the locations with the aim of finding all of the hidden objects. If he does so, he wins, otherwise the Hider wins. This zero‐sum game is complicated to analyze even for small values of its parameters, and for the case of 2 hidden objects has been completely solved only when the game is played in up to 3 locations. For some values of h the solution of the game with 2 objects hidden in 4 locations is known, but the solution in the remaining cases was an open question recently highlighted by Fokkink et al. (Fokkink et al., Search theory: A game theoretic perspective (2014) 85–104). Here we solve the remaining cases of the game with 2 objects hidden in 4 locations. We also give some more general results for the game, in particular using a geometrical argument to show that when there are 2 objects hidden in n locations and n→∞, the value of the game is asymptotically equal to h/n for h≥n/2. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 23–31, 2016     

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     

Future supply uncertainty in EOQ models

This article deals with an inventory problem where the supply is available only during an interval of (random) length X. The unavailability of supply lasts for a random duration Y. Using concepts from renewal theory, we construct an objective function (average cost/time) in terms of the order-quantity decision variable Q. We develop the individual cost components as order, holding, and shortage costs after introducing two important random variables. Due to the complexity of the objective function when X and Y are general random variables, we discuss two special cases and provide numerical examples with sensitivity analysis on the cost and noncost parameters. The article concludes with a discussion of the comparison of the current model with random yield and random lead-time models. Suggestions for further research are also provided.     

Estimating the probability that a simulated system will be the best

Consider a stochastic simulation experiment consisting of v independent vector replications consisting of an observation from each of k independent systems. Typical system comparisons are based on mean (long‐run) performance. However, the probability that a system will actually be the best is sometimes more relevant, and can provide a very different perspective than the systems' means. Empirically, we select one system as the best performer (i.e., it wins) on each replication. Each system has an unknown constant probability of winning on any replication and the numbers of wins for the individual systems follow a multinomial distribution. Procedures exist for selecting the system with the largest probability of being the best. This paper addresses the companion problem of estimating the probability that each system will be the best. The maximum likelihood estimators (MLEs) of the multinomial cell probabilities for a set of v vector replications across k systems are well known. We use these same v vector replications to form v^k unique vectors (termed pseudo‐replications) that contain one observation from each system and develop estimators based on AVC (All Vector Comparisons). In other words, we compare every observation from each system with every combination of observations from the remaining systems and note the best performer in each pseudo‐replication. AVC provides lower variance estimators of the probability that each system will be the best than the MLEs. We also derive confidence intervals for the AVC point estimators, present a portion of an extensive empirical evaluation and provide a realistic example. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 341–358, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10019     

Reliability of linear multistate multiple sliding window systems

This paper proposes a new model that generalizes the linear consecutive k‐out‐of‐r‐from‐n:F system to multistate case with multiple failure criteria. In this model (named linear multistate multiple sliding window system) the system consists of n linearly ordered multistate elements (MEs). Each ME can have different states: from complete failure up to perfect functioning. A performance rate is associated with each state. Several functions are defined for a set of integer numbers ρ in such a way that for each r ∈ ρ corresponding function f_r produces negative values if the combination of performance rates of r consecutive MEs corresponds to the unacceptable state of the system. The system fails if at least one of functions f_r for any r consecutive MEs for r ∈ ρ produces a negative value. An algorithm for system reliability evaluation is suggested which is based on an extended universal moment generating function. Examples of system reliability evaluation are presented. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Open-shop scheduling problems with dominated machines

This article deals with special cases of open-shop scheduling where n jobs have to be processed by m, m ?3, machines to minimize the schedule length. The main result obtained is an O(n) algorithm for the three-machine problem with a dominated machine.     

Single‐warehouse multi‐retailer inventory systems with full truckload shipments

We consider a multi‐stage inventory system composed of a single warehouse that receives a single product from a single supplier and replenishes the inventory of n retailers through direct shipments. Fixed costs are incurred for each truck dispatched and all trucks have the same capacity limit. Costs are stationary, or more generally monotone as in Lippman (Management Sci 16, 1969, 118–138). Demands for the n retailers over a planning horizon of T periods are given. The objective is to find the shipment quantities over the planning horizon to satisfy all demands at minimum system‐wide inventory and transportation costs without backlogging. Using the structural properties of optimal solutions, we develop (1) an O(T²) algorithm for the single‐stage dynamic lot sizing problem; (2) an O(T³) algorithm for the case of a single‐warehouse single‐retailer system; and (3) a nested shortest‐path algorithm for the single‐warehouse multi‐retailer problem that runs in polynomial time for a given number of retailers. To overcome the computational burden when the number of retailers is large, we propose aggregated and disaggregated Lagrangian decomposition methods that make use of the structural properties and the efficient single‐stage algorithm. Computational experiments show the effectiveness of these algorithms and the gains associated with coordinated versus decentralized systems. Finally, we show that the decentralized solution is asymptotically optimal. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

A total tardiness problem with preprocessing included

A special case of the two-machine flow-shop total tardiness problem is defined by assuming that the first machine is dedicated to preprocessing and that the second machine performs the main operation, which is longer than preprocessing for each job. It is also assumed that customer orders (jobs) contain varying numbers of otherwise similar parts; therefore orders with longer main processing times have longer preprocessing times as well. The new problem (F2/ppc/T ) is solved by exploiting its structure and its relationship to the single-machine (1//T ) and the two-machine flow-shop (F2//T¯) total tardiness problems. It is shown that shortest-processing-time ordering minimizes the average job completion time in the F2/ppc/T setting. This result leads to the development of dominance conditions to determine a priori the order of some jobs in an optimal F2/ppc/T sequence. These dominance conditions are then embedded in a branch-and-bound algorithm, which is shown to be computationally efficient. A polynomial-time heuristic is also developed for F2/ppc/T . It is concluded that the additional structure of F2/ppc/T (compared to the general F2//T problem) results in highly efficient solution algorithms for it. © 1996 John Wiley & Sons, Inc.     

Linear compound algorithms for the partitioning problem

For a given set S of nonnegative integers the partitioning problem asks for a partition of S into two disjoint subsets S₁ and S₂ such that the sum of elements in S₁ is equal to the sum of elements in S₂. If additionally two elements (the kernels) r₁, r₂ ∈ S are given which must not be assigned to the same set S_i, we get the partitioning problem with kernels. For these NP‐complete problems the authors present two compound algorithms which consist both of three linear greedylike algorithms running independently. It is shown that the worst‐case performance of the heuristic for the ordinary partitioning problem is 12/11, while the second procedure for partitioning with kernels has a bound of 8/7. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 593–601, 2000