Estimating component characteristics from system failure‐time data

Suppose that failure times are available from a random sample of N systems of a given, fixed design with components which have i.i.d. lifetimes distributed according to a common distribution F. The inverse problem of estimating F from data on observed system lifetimes is considered. Using the known relationship between the system and component lifetime distributions via signature and domination theory, the nonparametric maximum likelihood estimator _N(t) of the component survival function (t) is identified and shown to be accessible numerically in any application of interest. The asymptotic distribution of _N(t) is also identified, facilitating the construction of approximate confidence intervals for (t) for N sufficiently large. Simulation results for samples of size N = 50 and N = 100 for a collection of five parametric lifetime models demonstrate the utility of the recommended estimator. Possible extensions beyond the i.i.d. framework are discussed in the concluding section. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Bin‐packing problem with concave costs of bin utilization

We consider a generalized one‐dimensional bin‐packing model where the cost of a bin is a nondecreasing concave function of the utilization of the bin. Four popular heuristics from the literature of the classical bin‐packing problem are studied: First Fit (FF), Best Fit (BF), First Fit Decreasing (FFD), and Best Fit Decreasing (BFD). We analyze their worst‐case performances when they are applied to our model. The absolute worst‐case performance ratio of FF and BF is shown to be exactly 2, and that of FFD and BFD is shown to be exactly 1.5. Computational experiments are also conducted to test the performance of these heuristics. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Transporting jobs through a two‐machine open shop

We consider the two‐machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a ‐approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Approximation schemes for ordered vector packing problems

In this paper we deal with the d‐dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors a_i, a_j, either a_i is componentwise not smaller than a_j or a_j is componentwise not smaller than a_i. An asymptotic polynomial‐time approximation scheme is constructed for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e., instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017     

Convolutions and generalization of logconcavity: Implications and applications

Additive convolution of unimodal and α‐unimodal random variables are known as an old classic problem which has attracted the attention of many authors in theory and applied fields. Another type of convolution, called multiplicative convolution, is rather younger. In this article, we first focus on this newer concept and obtain several useful results in which the most important ones is that if is logconcave then so are and for some suitable increasing functions ?. This result contains and as two more important special cases. Furthermore, one table including more applied distributions comparing logconcavity of f(x) and and two comprehensive implications charts are provided. Then, these fundamental results are applied to aging properties, existence of moments and several kinds of ordered random variables. Multiplicative strong unimodality in the discrete case is also introduced and its properties are investigated. In the second part of the article, some refinements are made for additive convolutions. A remaining open problem is completed and a conjecture concerning convolution of discrete α‐unimodal distributions is settled. Then, we shall show that an existing result regarding convolution of symmetric discrete unimodal distributions is not correct and an easy alternative proof is presented. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 109–123, 2016     

Technical note: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand

We consider the problem of nonparametric multi-product dynamic pricing with unknown demand and show that the problem may be formulated as an online model-free stochastic program, which can be solved by the classical Kiefer-Wolfowitz stochastic approximation (KWSA) algorithm. We prove that the expected cumulative regret of the KWSA algorithm is bounded above by where κ₁, κ₂ are positive constants and T is the number of periods for any T = 1, 2, … . Therefore, the regret of the KWSA algorithm grows in the order of , which achieves the lower bounds known for parametric dynamic pricing problems and shows that the nonparametric problems are not necessarily more difficult to solve than the parametric ones. Numerical experiments further demonstrate the effectiveness and efficiency of our proposed KW pricing policy by comparing with some pricing policies in the literature.     

Inventory policies for a make‐to‐order system with a perishable component and fixed ordering cost

We consider a make‐to‐order production system where two major components, one nonperishable (referred to as part 1) and one perishable (part 2), are needed to fulfill a customer order. In each period, replenishment decisions for both parts need to be made jointly before demand is realized and a fixed ordering cost is incurred for the nonperishable part. We show that a simple (s_n,S,S) policy is optimal. Under this policy, S along with the number of backorders at the beginning of a period if any and the availability of the nonperishable part (part 1) determines the optimal order quantity of the perishable part (part 2), while (s_n,S) guide when and how much of part 1 to order at each state. Numerical study demonstrates that the benefits of using the joint replenishment policy can be substantial, especially when the unit costs are high and/or the profit margin is low. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

A heuristic for maximizing the number of on‐time jobs on two uniform parallel machines

We consider the problem of maximizing the number of on‐time jobs on two uniform parallel machines. We show that a straightforward extension of an algorithm developed for the simpler two identical parallel machines problem yields a heuristic with a worst‐case ratio bound of at least . We then show that the infusion of a “look ahead” feature into the aforementioned algorithm results in a heuristic with the tight worst‐case ratio bound of , which, to our knowledge, is the tightest worst‐case ratio bound available for the problem. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Scheduling deteriorating jobs to minimize makespan

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J_j grows by w_j with each time unit its start is delayed beyond a given common critical date d. This processing time is p_j if J_j starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n²d(D − d) time and O(nd(D − d)) space, the other runs in p_j)²) time and p_j) space. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998     

Level workforce planning for multistage transfer lines

In this article, we define two different workforce leveling objectives for serial transfer lines. Each job is to be processed on each transfer station for c time periods (e.g., hours). We assume that the number of workers needed to complete each operation of a job in precisely c periods is given. Jobs transfer forward synchronously after every production cycle (i.e., c periods). We study two leveling objectives: maximin workforce size () and min range (R). Leveling objectives produce schedules where the cumulative number of workers needed in all stations of a transfer line does not experience dramatic changes from one production cycle to the next. For and a two‐station system, we develop a fast polynomial algorithm. The range problem is known to be NP‐complete. For the two‐station system, we develop a very fast optimal algorithm that uses a tight lower bound and an efficient procedure for finding complementary Hamiltonian cycles in bipartite graphs. Via a computational experiment, we demonstrate that range schedules are superior because not only do they limit the workforce fluctuations from one production cycle to the next, but they also do so with a minor increase in the total workforce size. We extend our results to the m‐station system and develop heuristic algorithms. We find that these heuristics work poorly for min range (R), which indicates that special structural properties of the m‐station problem need to be identified before we can develop efficient algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 577–590, 2016     

Level product form QSF processes and an analysis of queues with Coxian interarrival distribution

In this article, we study a class of Quasi‐Skipfree (QSF) processes where the transition rate submatrices in the skipfree direction have a column times row structure. Under homogeneity and irreducibility assumptions we show that the stationary distributions of these processes have a product form as a function of the level. For an application, we will discuss the ‐queue that can be modeled as a QSF process on a two‐dimensional state space. In addition, we study the properties of the stationary distribution and derive monotonicity of the mean number of the customers in the queue, their mean sojourn time and the variance as a function of for fixed mean arrival rate. © 2016 Wiley Periodicals, Inc. Naval Research Logisticsxs 66:57–72, 2019     

Approximation algorithms for sequential batch‐testing of series systems

We introduce and study a generalization of the classic sequential testing problem, asking to identify the correct state of a given series system that consists of independent stochastic components. In this setting, costly tests are required to examine the state of individual components, which are sequentially tested until the correct system state can be uniquely identified. The goal is to propose a policy that minimizes the expected testing cost, given a‐priori probabilistic information on the stochastic nature of each individual component. Unlike the classic setting, where variables are tested one after the other, we allow multiple tests to be conducted simultaneously, at the expense of incurring an additional set‐up cost. The main contribution of this article consists in showing that the batch testing problem can be approximated in polynomial time within factor , for any fixed . In addition, we explain how, in spite of its highly nonlinear objective function, the batch testing problem can be formulated as an approximate integer program of polynomial size, while blowing up its expected cost by a factor of at most . Finally, we conduct extensive computational experiments, to demonstrate the practical effectiveness of these algorithms as well as to evaluate their limitations. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 275–286, 2016     

Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.     

Improved bounds for batch scheduling with nonidentical job sizes

Here, we revisit the bounded batch scheduling problem with nonidentical job sizes on single and parallel identical machines, with the objective of minimizing the makespan. For the single machine case, we present an algorithm which calls an online algorithm (chosen arbitrarily) for the one‐dimensional bin‐packing problem as a sub‐procedure, and prove that its worst‐case ratio is the same as the absolute performance ratio of . Hence, there exists an algorithm with worst‐case ratio , which is better than any known upper bound on this problem. For the parallel machines case, we prove that there does not exist any polynomial‐time algorithm with worst‐case ratio smaller than 2 unless P = NP, even if all jobs have unit processing time. Then we present an algorithm with worst‐case ratio arbitrarily close to 2. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 351–358, 2014     

On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

A finiteness proof for modified dantzig cuts in integer programming

Let be a basic solution to the linear programming problem subject to: where R is the index set associated with the nonbasic variables. If all of the variables are constrained to be nonnegative integers and x_u is not an integer in the basic solution, the linear constraint is implied. We prove that including these “cuts” in a specified way yields a finite dual simplex algorithm for the pure integer programming problem. The relation of these modified Dantzig cuts to Gomory cuts is discussed.     

The knapsack problem: A survey

A unifying survey of the literature related to the knapsack problem; that is, maximize \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_i {v_i x_{i,} } $\end{document}, subject to \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_j {w_i x_i W} $\end{document} and x_i ? 0, integer; where v_i, w_i and W are known integers, and w_i (i = 1, 2, …, N) and W are positive. Various uses, including those in group theory and in other integer programming algorithms, as well as applications from the literature, are discussed. Dynamic programming, branch and bound, search enumeration, heuristic methods, and other solution techniques are presented. Computational experience, and extensions of the knapsack problem, such as to the multi-dimensional case, are also considered.