Optimal refueling strategies for a mixed-vehicle fleet

The problem treated here involves a mixed fleet of vehicles comprising two types of vehicles: K₁ tanker-type vehicles capable of refueling themselves and other vehicles, and K₂ nontanker vehicles incapable of refueling. The two groups of vehicles have different fuel capacities as well as different fuel consumption rates. The problem is to find the tanker refueling sequence that maximizes the range attainable for the K₂ nontankers. A tanker refueling sequence is a partition of the tankers into m subsets (2 ≤ m ≤ K₁). A given sequence of the partition provides a realization of the number of tankers participating in each successive refueling operation. The problem is first formulated as a nonlinear mixed-integer program and reduced to a linear program for a fixed sequence which may be solved by a simple recursive procedure. It is proven that a “unit refueling sequence” composed of one tanker refueling at each of K₁ refueling operations is optimal. In addition, the problem of designing the “minimum fleet” (minimum number of tankers) required for a given set of K₂ nontankers to attain maximal range is resolved. Also studied are extensions to the problem with a constraint on the number of refueling operations, different nontanker recovery base geometry, and refueling on the return trip.     

Asymptotically optimal component assembly plans in repairable systems and server allocation in parallel multiserver queues

T identical exponential lifetime components out of which G are initially functioning (and B are not) are to be allocated to N subsystems, which are connected either in parallel or in series. Subsystem i, i = 1,…, N, functions when at least K_i of its components function and the whole system is maintained by a single repairman. Component repair times are identical independent exponentials and repaired components are as good as new. The problem of the determination of the assembly plan that will maximize the system reliability at any (arbitrary) time instant t is solved when the component failure rate is sufficiently small. For the parallel configuration, the optimal assembly plan allocates as many components as possible to the subsystem with the smallest K_i and allocates functioning components to subsystems in increasing order of the K_i's. For the series configuration, the optimal assembly plan allocates both the surplus and the functioning components equally to all subsystems whenever possible, and when not possible it favors subsystems in decreasing order of the K_i's. The solution is interpreted in the context of the optimal allocation of processors and an initial number of jobs in a problem of routing time consuming jobs to parallel multiprocessor queues. © John Wiley & Sons, Inc. Naval Research Logistics 48: 732–746, 2001     

Vehicle fleet refueling strategies to maximize operational range

The focus of this research is on self-contained missions requiring round-trip vehicle travel from a common origin. For a single vehicle the maximal distance that can be reached without refueling is defined as its operational range. Operational range is a function of a vehicle's fuel capacity and fuel consumption characteristics. In order to increase a vehicle's range beyond its operational range replenishment from a secondary fuel source is necessary. In this article, the problem of maximizing the range of any single vehicle from a fleet of n vehicles is investigated. This is done for four types of fleet configurations: (1) identical vehicles, (2) vehicles with identical fuel consumption rates but different fuel capacities, (3) vehicles which have the same fuel capacity but different fuel consumption rates, and (4) vehicles with both different fuel capacities and different consumption rates. For each of the first three configurations the optimal refueling policy that provides the maximal range is determined for a sequential refueling chain strategy. In such a strategy the last vehicle to be refueled is the next vehicle to transfer its fuel. Several mathematical programming formulations are given and their solutions determined in closed form. One of the major conclusions is that for an identical fleet the range of the farthest vehicle can be increased by at most 50% more than the operational range of a single vehicle. Moreover, this limit is reached very quickly with small values of n. The performance of the identical fleet configuration is further investigated for a refueling strategy involving a multiple-transfer refueling chain, stochastic vehicle failures, finite refueling times, and prepositioned fleets. No simple refueling ordering rules were found for the most general case (configuration 4). In addition, the case of vehicles with different fuel capacities is investigated under a budget constraint. The analysis provides several benchmarks or bounds for which more realistic structures may be compared. Some of the more complex structures left for future study are described.     

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.     

Cyclical job sequencing on multiple sets of identical machines

The problem posed in this paper is to sequence or route n jobs, each originating at a particular location or machine, undergoing r?1 operations or repairs, and terminating at the location or machine from which it originated. The problem is formulated as a 0-1 integer program, with block diagonal structure, comprised of r assignment subproblems; and a joint set of constraints to insure cyclical squences. To obtain integer results the solutions to each subproblem are ranked as required and combinations thereof are implicitly enumerated. The procedure may be terminated at any step to obtain an approximate solution. Some limited computational results are presented.     

The mixed ordering policy in periodic review stochastic multi-commodity inventory systems

In multi-commodity inventory systems with variable setup costs, the mixed ordering policy assumes that commodities may be ordered either individually, or may be arbitrarily grouped for joint ordering. Thus, for a two-commodity system, commodity one or commodity two or commodities one and two may be ordered incurring respectively fixed order costs of K, K₁, or K₂, where max (K₁, K₂) ≤ K ≤ K₁ + K₂, This paper considers a two-commodity periodic review system. The stationary characteristics of the system are analyzed, and, for a special case, explicit solutions are obtained for the distribution of the stock levels at the beginning of the periods. In a numerical example, optimal policy variables are computed, and the mixed ordering policy is compared with individual and joint ordering policies.     

Preservation of unimodality under shock models

A number of results pertaining to preservation of aging properties (IFR, IFRA etc.) under various shock models are available in the literature. Our aim in this paper is to examine in the same spirit, the preservation of unimodality under various shock models. For example, it is proved that in a non-homogeneous Poisson shock model if {p_k}_K≥0, the sequence of probabilities with which the device fails on the kth shock, is unimodal then under some suitable conditions on the mean value function Λ (t), the corresponding survival function is also unimodal. The other shock models under which the preservation of unimodality is considered in this paper are pure birth shock model and a more general shock model in which shocks occur according to a general counting process. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 952–957, 1999     

A note on circular error probabilities

An approximation for P(X² + Y² ≤ K²σ²₁) based on an unpublished result of Kleinecke is derived, where X and Y are independent normal variables having zero means and variances σ²₁ and σ²₂ and σ₁ ≥ σ₂. Also, we provide asymptotic expressions for the probabilities for large values of β = K²(1 - c²)/4c² where c = σ₂/σ₁. These are illustrated by comparing with values tabulated by Harter [6]. Solution of K for specified P and c is also considered. The main point of this note is that simple and easily calculable approximations for P and K can be developed and there is no need for numerical evaluation of integrals.     

On estimating population characteristics from record-breaking observations. i. parametric results

Consider an experiment in which only record-breaking values (e.g., values smaller than all previous ones) are observed. The data available may be represented as X₁,K₁,X₂,K₂, …, where X₁,X₂, … are successive minima and K₁,K₂, … are the numbers of trials needed to obtain new records. We treat the problem of estimating the mean of an underlying exponential distribution, and we consider both fixed sample size problems and inverse sampling schemes. Under inverse sampling, we demonstrate certain global optimality properties of an estimator based on the “total time on test” statistic. Under random sampling, it is shown than an analogous estimator is consistent, but can be improved for any fixed sample size.     

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     

Markov chain analysis of a situation where cannibalization is the only repair activity

This paper considers a group of S identical aircraft, each of which is partitioned into K parts which fail exponentially. The only way in which a failed aircraft can be repaired is by cannibalizing its out-of-commission parts from other failed aircraft. The evolution of the number of good aircraft over time is governed by the transient behavior of an absorbing Markov chain. We can therefore study this behavior by matrix multiplication although the computational problem grows large for K ≥ 3. Some numerical results and some approximations are also provided.     

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     

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     

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.     

Efficient algorithms for flexible job shop scheduling with parallel machines

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .     

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 convexity proofs in location theory

It is often assumed in the facility location literature that functions of the type ø_i(x_i, y) = β_i[(x_i-x)²+(y_i-y)²]^K/2 are twice differentiable. Here we point out that this is true only for certain values of K. Convexity proofs that are independent of the value of K are given.     

A bivariate optimal replacement policy for a cold standby repairable system with repair priority

In this article, an optimal replacement policy for a cold standby repairable system consisting of two dissimilar components with repair priority is studied. Assume that both Components 1 and 2, after repair, are not as good as new, and the main component (Component 1) has repair priority. Both the sequence of working times and that of the components'repair times are generated by geometric processes. We consider a bivariate replacement policy (T,N) in which the system is replaced when either cumulative working time of Component 1 reaches T, or the number of failures of Component 1 reaches N, whichever occurs first. The problem is to determine the optimal replacement policy (T,N)* such that the long run average loss per unit time (or simply the average loss rate) of the system is minimized. An explicit expression of this rate is derived, and then optimal policy (T,N)* can be numerically determined through a two‐dimensional‐search procedure. A numerical example is given to illustrate the model's applicability and procedure, and to illustrate some properties of the optimal solution. We also show that if replacements are made solely on the basis of the number of failures N, or solely on the basis of the cumulative working time T, the former class of policies performs better than the latter, albeit only under some mild conditions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

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.     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999