Transformations of node‐balanced routing problems

This article describes a polynomial transformation for a class of unit‐demand vehicle routing problems, named node‐balanced routing problems (BRP), where the number of nodes on each route is restricted to be in an interval such that the workload across the routes is balanced. The transformation is general in that it can be applied to single or multiple depot, homogeneous or heterogeneous fleet BRPs, and any combination thereof. At the heart of the procedure lies transforming the BRP into a generalized traveling salesman problem (TSP), which can then be transformed into a TSP. The transformed graph exhibits special properties which can be exploited to significantly reduce the number of arcs, and used to construct a formulation for the resulting TSP that amounts to no more than that of a constrained assignment problem. Computational results on a number of instances are presented. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 370–387, 2015     

A note on the forecast performance of temporal aggregation

Earlier research on the effects of nonoverlapping temporal aggregation on demand forecasting showed the benefits associated with such an approach under a stationary AR(1) or MA(1) processes for decision making conducted at the disaggregate level. The first objective of this note is to extend those important results by considering a more general underlying demand process. The second objective is to assess the conditions under which aggregation may be a preferable approach for improving decision making at the aggregate level as well. We confirm the validity of previous results under more general conditions, and we show the increased benefit resulting from forecasting by temporal aggregation at lower frequency time units. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 489–500, 2014     

A branch and bound algorithm for computing optimal replacement policies in consecutive k‐out‐of‐n‐systems

This paper presents a branch and bound algorithm for computing optimal replacement policies in a discrete‐time, infinite‐horizon, dynamic programming model of a binary coherent system with n statistically independent components, and then specializes the algorithm to consecutive k‐out‐of‐n systems. The objective is to minimize the long‐run expected average undiscounted cost per period. (Costs arise when the system fails and when failed components are replaced.) An earlier paper established the optimality of following a critical component policy (CCP), i.e., a policy specified by a critical component set and the rule: Replace a component if and only if it is failed and in the critical component set. Computing an optimal CCP is a optimization problem with n binary variables and a nonlinear objective function. Our branch and bound algorithm for solving this problem has memory storage requirement O(n) for consecutive k‐out‐of‐n systems. Extensive computational experiments on such systems involving over 350,000 test problems with n ranging from 10 to 150 find this algorithm to be effective when n ≤ 40 or k is near n. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 288–302, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10017     

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     

Timing of information acquisition in a competitive environment

This article investigates the impact of timing on sellers' information acquisition strategies in a duopoly setting. Market uncertainty is captured by a representative consumer who has a private taste for the product's horizontal attribute, and both sellers can acquire this information either before (ex‐ante acquisition) or after (ex‐post acquisition) observing their own product qualities. We identify several conflicting effects of information acquisition that vary significantly in its timing and market characteristics. In the monopoly scenario, information acquisition is unambiguously beneficial and ex‐ante acquisition is the dominant option, because it helps a seller not only design the proper product but also craft better pricing strategy. By contrast, when there is competition, information acquisition eliminates the buffer role of market uncertainty and leads to the fiercest production or pricing competition, which makes the subsequent effects of acquisition detrimental, and a seller's payoff is nonmonotonic in terms of its acquisition cost. Moreover, compared with the ex‐ante information acquisition, ex‐post information acquisition normally generates higher sellers' equilibrium payoffs by postponing the timing of acquisition and maintaining product differentiation. Nonetheless, ex‐post information acquisition also provides the seller with greater acquisition incentive and occasionally makes him worse off than that in the ex‐ante scenario. Thus, in a competitive environment, having the option of information acquisition and flexibility in its timing can be both detrimental and irresistible. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 3–22, 2016     

Mixed rules in multi‐issue allocation situations

Multi‐issue allocation situations study problems where an estate must be divided among a group of agents. The claim of each agent is a vector specifying the amount claimed by each agent on each issue. We present a two‐stage rule. First, we divide the estate among the issues following the constrained equal awards rule. Second, the amount assigned to each issue is divided among the agents in proportion to their demands on this issue. We apply the rule to two real‐world problems: the distribution of natural resources between countries and the distribution of budget for education and research between universities.     

Nonlinear pricing with consumer satiation

In various scenarios, consumers may become satiated with products, and the degree of satiation is directly associated with their prior experiences. Confronted with consumer satiation, the seller is unable to either identify consumers who have a higher likelihood of being satiated ex ante or distinguish satiated from non‐satiated consumers ex post. Therefore, the seller should address dynamic selling, valuation uncertainty, and quantity decisions, all of which are important operational issues. We consider a two‐period problem in which consumer types are influenced by their prior consumption experiences. Faced with these consumers, the seller intends to optimize quantities and adjust the prices of the products in each period to maximize revenue. We find that the seller may reduce ex ante production quantity as some consumers become satiated. Moreover, the ex ante quantity is first decreasing and then increasing with regard to the satiation rate. Furthermore, two‐period information asymmetries may provide a rationale for upward distortion in quantity when consumer preferences are highly sensitive to first‐period consumption. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 386–400, 2016     

A characterization of optimal base‐stock levels for a multistage serial supply chain

In this article, we present a multistage model to optimize inventory control decisions under stochastic demand and continuous review. We first formulate the general problem for continuous stages and use a decomposition solution approach: since it is never optimal to let orders cross, the general problem can be broken into a set of single‐unit subproblems that can be solved in a sequential fashion. These subproblems are optimal control problems for which a differential equation must be solved. This can be done easily by recursively identifying coefficients and performing a line search. The methodology is then extended to a discrete number of stages and allows us to compute the optimal solution in an efficient manner, with a competitive complexity. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 32–46, 2016     

Lot streaming with supplier–manufacturer coordination

Lot splitting refers to breaking a production lot into smaller sublots during production. Coordinating lot splitting decisions across multiple stages of a production process is a challenging task. Traditional lot splitting and lot streaming models implicitly assume that the entire system is operated and owned by the same firm, or there exists a coordinator who controls the operation of all machines in the system. In this paper, we consider the situation where the machines in a multiple‐stage production process are owned and managed by different companies. Every item in a given production lot has to go through the processing by the supplier's machine, followed by the manufacturer's machine, and so on. We develop and analyze coordination mechanisms that enable different parties in the supply chain to coordinate their lot splitting decisions so as to achieve a systemwide optimum. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Group testing procedures with quantitative features and incomplete identification

We present a group testing model for items characterized by marker random variables. An item is defined to be good (defective) if its marker is below (above) a given threshold. The items can be tested in groups; the goal is to obtain a prespecified number of good items by testing them in optimally sized groups. Besides this group size, the controller has to select a threshold value for the group marker sums, and the target number of groups which by the tests are classified to consist only of good items. These decision variables have to be chosen so as to minimize a cost function, which is a linear combination of the expected number of group tests and an expected penalty for missing the desired number of good items, subject to constraints on the probabilities of misclassifications. We treat two models of this kind: the first one is based on an infinite population size, whereas the second one deals with the case of a finite number of available items. All performance measures are derived in closed form; approximations are also given. Furthermore, we prove monotonicity properties of the components of the objective function and of the constraints. In several examples, we study (i) the dependence of the cost function on the decision variables and (ii) the dependence of the optimal values of the decision variables (group size, group marker threshold, and stopping rule for groups classified as clean) and of the target functionals (optimal expected number of tests, optimal expected penalty, and minimal expected cost) on the system parameters.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011