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     

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     

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     

A hybrid method for simulation factor screening

Factor screening is performed to eliminate unimportant factors so that the remaining important factors can be more thoroughly studied in later experiments. Controlled sequential bifurcation (CSB) and controlled sequential factorial design (CSFD) are two new screening methods for discrete‐event simulations. Both methods use hypothesis testing procedures to control the Type I Error and power of the screening results. The scenarios for which each method is most efficient are complementary. This study proposes a two‐stage hybrid approach that combines CSFD and an improved CSB called CSB‐X. In Phase 1, a prescreening procedure will estimate each effect and determine whether CSB‐X or CSFD will be used for further screening. In Phase 2, CSB‐X and CSFD are performed separately based on the assignment of Phase 1. The new method usually has the same error control as CSB‐X and CSFD. The efficiency, on the other hand, is usually much better than either component method. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Base‐stock policies in capacitated assembly systems: Convexity properties

We study an assembly system with a single finished product managed using an echelon base‐stock or order‐up‐to policy. Some or all operations have capacity constraints. Excess demand is either backordered in every period or lost in every period. We show that the shortage penalty cost over any horizon is jointly convex with respect to the base‐stock levels and capacity levels. When the holding costs are also included in the objective function, we show that the cost function can be written as a sum of a convex function and a concave function. Throughout the article, we discuss algorithmic implications of our results for making optimal inventory and capacity decisions in such systems.© 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Route optimization for multiple searchers

We consider a discrete time‐and‐space route‐optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically moving targets. This article formulates a novel convex mixed‐integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, and target‐ and location‐dependent search effectiveness. We present two solution approaches, one based on the cutting‐plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting‐plane approach solves many realistically sized problem instances in a few minutes, while existing branch‐and‐bound algorithms fail. A specialized cut improves solution time by 50[percnt] in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting‐plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

军用飞机改进改型研制费用的参数估算法

首先分析并建立了军用飞机改进改型研制的费用分解结构,阐明了与新研飞机在各分项费用上的差别。基于当量工程的概念提出了用减缩系数来估算改进改型研制的费用修正和各分项费用的减缩系数的估计方法,结合现有成熟的参数估算模型建立了相应的改进改型研制的费用估算模型。最后,以某型飞机的改型研制费用为例进行了实例分析,结果表明方法与模型具有较好的有效性和实用性。     

Signature based analysis of m‐Consecutive‐k‐out‐of‐n: F systems with exchangeable components

In this article, we study reliability properties of m‐consecutive‐k‐out‐of‐n: F systems with exchangeable components. We deduce exact formulae and recurrence relations for the signature of the system. Closed form expressions for the survival function and the lifetime distribution as a mixture of the distribution of order statistics are established as well. These representations facilitate the computation of several reliability characteristics of the system for a given exchangeable joint distribution or survival function. Finally, we provide signature‐based stochastic ordering results for the system's lifetime and investigate the IFR preservation property under the formulation of m‐consecutive‐k‐out‐of‐n: F systems. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Improving series and parallel systems through mixtures of duplicated dependent components

We discuss suitable conditions such that the lifetime of a series or of a parallel system formed by two components having nonindependent lifetimes may be stochastically improved by replacing the lifetimes of each of the components by an independent mixture of the individual components' lifetimes. We also characterize the classes of bivariate distributions where this phenomenon arises through a new weak dependence notion. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011