Equitable bandwidth allocation in content distribution networks

Applications for content distribution over networks, such as Video‐on‐Demand (VOD), are expected to grow significantly over time. Effective bandwidth allocation schemes that can be repeatedly executed must be deployed since new programs are often installed at various servers while other are deleted. We present a model for bandwidth allocation in a content distribution network that consists of multiple trees, where the root of each tree has a server that broadcasts multiple programs throughout the tree. Each network link has limited capacity and may be used by one or more of these trees. The model is formulated as an equitable resource allocation problem with a lexicographic maximin objective function that attempts to provide equitable service performance for all requested programs at the various nodes. The constraints include link capacity constraints and tree‐like ordering constraints imposed on each of the programs. We present an algorithm that provides an equitable solution in polynomial time for certain performance functions. At each iteration, the algorithm solves single‐link maximin optimization problems while relaxing the ordering constraints. The algorithm selects a bottleneck link, fixes various variables at their lexicographic optimal solution while enforcing the ordering constraints, and proceeds with the next iteration. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Multi‐period maintenance scheduling of tree networks with minimum flow disruption

We introduce a multi‐period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial‐time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP‐hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017     

Batch scheduling with step‐deteriorating processing times to minimize flowtime

Both topics of batch scheduling and of scheduling deteriorating jobs have been very popular among researchers in the last two decades. In this article, we study a model combining these two topics. We consider a classical batch scheduling model with unit‐jobs and batch‐independent setup times, and a model of step‐deterioration of processing times. The objective function is minimum flowtime. The optimal solution of the relaxed version (allowing non‐integer batch sizes) is shown to have a unique structure consisting of two consecutive decreasing arithmetic sequences of batch sizes. We also introduce a simple and efficient rounding procedure that guarantees integer batch sizes. The entire solution procedure requires an effort of O(n) (where nis the number of jobs.) © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

A novel modeling approach for express package carrier planning

Express package carrier networks have large numbers of heavily‐interconnected and tightly‐constrained resources, making the planning process difficult. A decision made in one area of the network can impact virtually any other area as well. Mathematical programming therefore seems like a logical approach to solving such problems, taking into account all of these interactions. The tight time windows and nonlinear cost functions of these systems, however, often make traditional approaches such as multicommodity flow formulations intractable. This is due to both the large number of constraints and the weakness of the linear programming (LP) relaxations arising in these formulations. To overcome these obstacles, we propose a model in which variables represent combinations of loads and their corresponding routings, rather than assigning individual loads to individual arcs in the network. In doing so, we incorporate much of the problem complexity implicitly within the variable definition, rather than explicitly within the constraints. This approach enables us to linearize the cost structure, strengthen the LP relaxation of the formulation, and drastically reduce the number of constraints. In addition, it greatly facilitates the inclusion of other stages of the (typically decomposed) planning process. We show how the use of templates, in place of traditional delayed column generation, allows us to identify promising candidate variables, ensuring high‐quality solutions in reasonable run times while also enabling the inclusion of additional operational considerations that would be difficult if not impossible to capture in a traditional approach. Computational results are presented using data from a major international package carrier. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Managing components for assemble‐to‐order products with lead‐time‐dependent pricing: The full‐shipment model

We study a component inventory planning problem in an assemble‐to‐order environment faced by many contract manufacturers in which both quick delivery and efficient management of component inventory are crucial for the manufacturers to achieve profitability in a highly competitive market. Extending a recent study in a similar problem setting by the same authors, we analyze an optimization model for determining the optimal component stocking decision for a contract manufacturer facing an uncertain future demand, where product price depends on the delivery times. In contrast to our earlier work, this paper considers the situation where the contract manufacturer needs to deliver the full order quantity in one single shipment. This delivery requirement is appropriate for many industries, such as the garment and toy industries, where the economies of scale in transportation is essential. We develop efficient solution procedures for solving this optimization problem. We use our model results to illustrate how the different model parameters affect the optimal solution. We also compare the results under this full‐shipment model with those from our earlier work that allows for multiple partial shipments. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Delivery‐date and capacity management in a decentralized internal market

We study competitive due‐date and capacity management between the marketing and engineering divisions within an engineer‐to‐order (ETO) firm. Marketing interacts directly with the customers and quotes due‐dates for their orders. Engineering is primarily concerned with the efficient utilization of resources and is willing to increase capacity if the cost is compensated. The two divisions share the responsibility for timely delivery of the jobs. We model the interaction between marketing and engineering as a Nash game and investigate the effect of internal competition on the equilibrium decisions. We observe that the internal competition not only degrades the firm's overall profitability but also the serviceability. Finally, we extend our analysis to multiple‐job settings that consider both flexible and inflexible capacity. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

The quay crane scheduling problem with time windows

The quay crane scheduling problem consists of scheduling tasks for loading and unloading containers on cranes that are assigned to a vessel for its service. This article introduces a new approach for quay crane scheduling, where the availability of cranes at a vessel is restricted to certain time windows. The problem is of practical relevance, because container terminal operators frequently redeploy cranes among vessels to speed up the service of high‐priority vessels while serving low‐priority vessels casually. This article provides a mathematical formulation of the problem and a tree‐search‐based heuristic solution method. A computational investigation on a large set of test instances is used to evaluate the performance of the heuristic and to identify the impact of differently structured crane time windows on the achievable vessel handling time. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Chance‐constrained multi‐terminal network design problems

We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum‐cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose two scenario‐based Steiner cut formulations, study the strength of the proposed valid inequalities, and develop a branch‐and‐cut solution method. We also propose an LP‐based separation for the scenario‐based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of the directed Steiner cuts for the deterministic Steiner tree problem. In our computational study, we test our branch‐and‐cut method on instances adapted from graphs in SteinLib Testdata Library with up to 100 nodes, 200 edges, and 17 terminals. The performance of our branch‐and‐cut method demonstrates the strength of the scenario‐based formulations and the benefit from adding the additional valid inequalities that we propose. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 321–334, 2015     

Approximation algorithms for capacitated stochastic inventory systems with setup costs

We develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014     

表示结构化知识的神经网络模型

研究和设计了一种高度结构化的神经网络模型ＨＳＮＮ,它能方便地对结构化知识进行表示和处理。文中给出了ＨＳＮＮ的设计过程,并讨论了ＨＳＮＮ在继承、非单调推理和信息检索等方面的应用     

Risk‐sensitive sizing of responsive facilities

We develop a risk‐sensitive strategic facility sizing model that makes use of readily obtainable data and addresses both capacity and responsiveness considerations. We focus on facilities whose original size cannot be adjusted over time and limits the total production equipment they can hold, which is added sequentially during a finite planning horizon. The model is parsimonious by design for compatibility with the nature of available data during early planning stages. We model demand via a univariate random variable with arbitrary forecast profiles for equipment expansion, and assume the supporting equipment additions are continuous and decided ex‐post. Under constant absolute risk aversion, operating profits are the closed‐form solution to a nontrivial linear program, thus characterizing the sizing decision via a single first‐order condition. This solution has several desired features, including the optimal facility size being eventually decreasing in forecast uncertainty and decreasing in risk aversion, as well as being generally robust to demand forecast uncertainty and cost errors. We provide structural results and show that ignoring risk considerations can lead to poor facility sizing decisions that deteriorate with increased forecast uncertainty. Existing models ignore risk considerations and assume the facility size can be adjusted over time, effectively shortening the planning horizon. Our main contribution is in addressing the problem that arises when that assumption is relaxed and, as a result, risk sensitivity and the challenges introduced by longer planning horizons and higher uncertainty must be considered. Finally, we derive accurate spreadsheet‐implementable approximations to the optimal solution, which make this model a practical capacity planning tool.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A three‐stage procurement optimization problem under uncertainty

This article examines a problem faced by a firm procuring a material input or good from a set of suppliers. The cost to procure the material from any given supplier is concave in the amount ordered from the supplier, up to a supplier‐specific capacity limit. This NP‐hard problem is further complicated by the observation that capacities are often uncertain in practice, due for instance to production shortages at the suppliers, or competition from other firms. We accommodate this uncertainty in a worst‐case (robust) fashion by modeling an adversarial entity (which we call the “follower”) with a limited procurement budget. The follower reduces supplier capacity to maximize the minimum cost required for our firm to procure its required goods. To guard against uncertainty, the firm can “protect” any supplier at a cost (e.g., by signing a contract with the supplier that guarantees supply availability, or investing in machine upgrades that guarantee the supplier's ability to produce goods at a desired level), ensuring that the anticipated capacity of that supplier will indeed be available. The problem we consider is thus a three‐stage game in which the firm first chooses which suppliers' capacities to protect, the follower acts next to reduce capacity from unprotected suppliers, and the firm then satisfies its demand using the remaining capacity. We formulate a three‐stage mixed‐integer program that is well‐suited to decomposition techniques and develop an effective cutting‐plane algorithm for its solution. The corresponding algorithmic approach solves a sequence of scaled and relaxed problem instances, which enables solving problems having much larger data values when compared to standard techniques. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Dynamic routing of prioritized warranty repairs

Recent years have seen a strong trend toward outsourcing warranty repair services to outside vendors. In this article we consider the problem of dynamically routing warranty repairs to service vendors when warranties have priority levels. Each time an item under warranty fails, it is sent to one of the vendors for repair. Items covered by higher priority warranty receive higher priority in repair service. The manufacturer pays a fixed fee per repair and incurs a linear holding cost while an item is undergoing or waiting for repair. The objective is to minimize the manufacturer's long‐run average cost. Because of the complexity of the problem, it is very unlikely that there exist tractable ways to find the optimal routing strategies. Therefore, we propose five heuristic routing procedures that are applicable to real‐life problems. We evaluate the heuristics using simulation. The simulation results show that the index‐based “generalized join the shortest queue” policy, which applies a single policy improvement step to an initial state‐independent policy, performs the best among all five heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

The probability of the existence of a feasible flow in a stochastic transportation network

Stochastic transportation networks arise in various real world applications, for which the probability of the existence of a feasible flow is regarded as an important performance measure. Although the necessary and sufficient condition for the existence of a feasible flow represented by an exponential number of inequalities is a well‐known result in the literature, the computation of the probability of all such inequalities being satisfied jointly is a daunting challenge. The state‐of‐the‐art approach of Prékopa and Boros, Operat Res 39 (1991) 119–129 approximates this probability by giving its lower and upper bounds using a two‐part procedure. The first part eliminates all redundant inequalities and the second gives the lower and upper bounds of the probability by solving two well‐defined linear programs with the inputs obtained from the first part. Unfortunately, the first part may still leave many non‐redundant inequalities. In this case, it would be very time consuming to compute the inputs for the second part even for small‐sized networks. In this paper, we first present a model that can be used to eliminate all redundant inequalities and give the corresponding computational results for the same numerical examples used in Prékopa and Boros, Operat Res 39 (1991) 119–129. We also show how to improve the lower and upper bounds of the probability using the multitree and hypermultitree, respectively. Furthermore, we propose an exact solution approach based on the state space decomposition to compute the probability. We derive a feasible state from a state space and then decompose the space into several disjoint subspaces iteratively. The probability is equal to the sum of the probabilities in these subspaces. We use the 8‐node and 15‐node network examples in Prékopa and Boros, Operat Res 39 (1991) 119–129 and the Sioux‐Falls network with 24 nodes to show that the space decomposition algorithm can obtain the exact probability of these classical examples efficiently. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 479–491, 2016     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

Optimal resource allocation and redistribution strategy in military conflicts with Lanchester square law attrition

We address the problem of optimal decision‐making in conflicts based on Lanchester square law attrition model where a defending force needs to be partitioned optimally, and allocated to two different attacking forces of differing strengths and capabilities. We consider a resource allocation scheme called the Time Zero Allocation with Redistribution (TZAR) strategy, where allocation is followed by redistribution of defending forces, on the occurrence of certain decisive events. Unlike previous work on Lanchester attrition model based tactical decision‐making, which propose time sequential tactics through an optimal control approach, the present article focuses on obtaining simpler resource allocation tactics based on a static optimization framework, and demonstrates that the results obtained are similar to those obtained by the more complex dynamic optimal control solution. Complete solution for this strategy is obtained for optimal partitioning of resources of the defending forces. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling recurrent construction

A problem we call recurrent construction involves manufacturing large, complex, expensive products such as airplanes, houses, and ships. Customers order configurations of these products well in advance of due dates for delivery. Early delivery may not be permitted. How should the manufacturer determine when to purchase and release materials before fabrication, assembly, and delivery? Major material expenses, significant penalties for deliveries beyond due dates, and long product makespans in recurrent construction motivate choosing a release timetable that maximizes the net present value of cash flows. Our heuristic first projects an initial schedule that dispatches worker teams to tasks for the backlogged products, and then solves a series of maximal closure problems to find material release times that maximize NPV. This method compares favorably with other well‐known work release heuristics in solution quality for large problems over a wide range of operating conditions, including order strength, cost structure, utilization level, batch policy, and uncertainty level. Computation times exhibit near linear growth in problem size. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

A m‐parallel crane scheduling problem with a non‐crossing constraint

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.