Realignment in the National Football League: Did they do it right?

The National Football League (NFL) in the United States expanded to 32 teams in 2002 with the addition of a team in Houston. At that point, the league was realigned into eight divisions, each containing four teams. We describe a branch‐and‐cut algorithm for minimizing the sum of intradivisional travel distances. We consider first the case where any team can be assigned to any division. We also consider imposing restrictions, such as aligning the AFC (American Football Conference) and the NFC (National Football Conference) separately or maintaining traditional rivalries. We show that the alignment chosen by the NFL does not minimize the sum of intradivisional travel distances, but that it is close to optimal for an alignment that aligns the NFC and AFC separately and imposes some additional restrictions. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 683–701, 2003.     

Simultaneous determination of production and maintenance schedules using in‐line equipment condition and yield information

In many manufacturing environments, equipment condition has a significant impact on product quality, or yield. This paper presents a semi‐Markov decision process model of a single‐stage production system with multiple products and multiple maintenance actions. The model simultaneously determines maintenance and production schedules, accounting for the fact that equipment condition affects the yield of each product differently. It extends earlier work by allowing the expected time between decision epochs to vary by both action and machine state, by allowing multiple maintenance actions, and by treating the outcome of maintenance as less than certain. Sufficient conditions are developed that ensure the monotonicity of both the optimal production and maintenance actions. While the maintenance conditions closely resemble previously studied conditions for this type of problem, the production conditions represent a significant departure from earlier results. The simultaneous solution method is compared to an approach commonly used in industry, where the maintenance and production problems are treated independently. Solving more than one thousand test problems confirms that the combination of both features of the model—accounting for product differences and solving the problems simultaneously—has a significant impact on performance. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Dynamic evacuation routes for personnel on a naval ship

We propose a dynamic escape route system for emergency evacuation of a naval ship. The system employs signals that adapt to the causative contingency and the crew's physical distribution about the ship. A mixed‐integer nonlinear programming model, with underlying network structure, optimizes the evacuation process. The network's nodes represent compartments, closures (e.g., doors and hatches) and intersections, while arcs represent various types of passageways. The objective function integrates two potentially conflicting factors: average evacuation time and the watertight and airtight integrity of the ship after evacuation. A heuristic solves the model approximately using a sequence of mixed‐integer linear approximating problems. Using data for a Spanish frigate, with standard static routes specified by the ship's designers, computational tests show that the dynamic system can reduce average evacuation times, nearly 23%, and can improve a combined measure of ship integrity by up to 50%. In addition, plausible design changes to the frigate yield further, substantial improvements. Published 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

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     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Validation of a strategy for harbor defense based on the use of a min‐max algorithm receding horizon control law

We present a validation of a centralized feedback control law for robotic or partially robotic water craft whose task is to defend a harbor from an intruding fleet of water craft. Our work was motivated by the need to provide harbor defenses against hostile, possibly suicidal intruders, preferably using unmanned craft to limit potential casualties. Our feedback control law is a sample‐data receding horizon control law, which requires the solution of a complex max‐min problem at the start of each sample time. In developing this control law, we had to deal with three challenges. The first was to develop a max‐min problem that captures realistically the nature of the defense‐intrusion game. The second was to ensure the solution of this max‐min problem can be accomplished in a small fraction of the sample time that would be needed to control a possibly fast moving craft. The third, to which this article is dedicated, was to validate the effectiveness of our control law first through computer simulations pitting a computer against a computer or a computer against a human, then through the use of model hovercraft in a laboratory, and finally on the Chesapeake Bay, using Yard Patrol boats. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 247–259, 2016     

Approximations for heavily loaded G/GI/n + GI queues

Motivated by applications to service systems, we develop simple engineering approximation formulas for the steady‐state performance of heavily loaded G/GI/n+GI multiserver queues, which can have non‐Poisson and nonrenewal arrivals and non‐exponential service‐time and patience‐time distributions. The formulas are based on recently established Gaussian many‐server heavy‐traffic limits in the efficiency‐driven (ED) regime, where the traffic intensity is fixed at ρ > 1, but the approximations also apply to systems in the quality‐and‐ED regime, where ρ > 1 but ρ is close to 1. Good performance across a wide range of parameters is obtained by making heuristic refinements, the main one being truncation of the queue length and waiting time approximations to nonnegative values. Simulation experiments show that the proposed approximations are effective for large‐scale queuing systems for a significant range of the traffic intensity ρ and the abandonment rate θ, roughly for ρ > 1.02 and θ > 2.0. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 187–217, 2016     

On allocating one active redundancy to coherent systems with dependent and heterogeneous components' lifetimes

This article studies coherent systems of heterogenous and statistically dependent components' lifetimes. We present a sufficient and necessary condition for a stochastically longer system lifetime resulted by allocating a single active redundancy. For exchangeable components' lifetimes, allocating the redundancy to the component with more minimal path sets is proved to produce a more reliable system, and for systems with stochastic arrangement increasing components' lifetimes and symmetric structure with respect to two components, allocating the redundancy to the weaker one brings forth a larger reliability. Several numerical examples are presented to illustrate the theoretical results as well. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 335–345, 2016     

Stochastic regret minimization for revenue management problems with nonstationary demands

We study an admission control model in revenue management with nonstationary and correlated demands over a finite discrete time horizon. The arrival probabilities are updated by current available information, that is, past customer arrivals and some other exogenous information. We develop a regret‐based framework, which measures the difference in revenue between a clairvoyant optimal policy that has access to all realizations of randomness a priori and a given feasible policy which does not have access to this future information. This regret minimization framework better spells out the trade‐offs of each accept/reject decision. We proceed using the lens of approximation algorithms to devise a conceptually simple regret‐parity policy. We show the proposed policy achieves 2‐approximation of the optimal policy in terms of total regret for a two‐class problem, and then extend our results to a multiclass problem with a fairness constraint. Our goal in this article is to make progress toward understanding the marriage between stochastic regret minimization and approximation algorithms in the realm of revenue management and dynamic resource allocation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 433–448, 2016     

基于BIST的3D SRAM中TSV开路测试算法研究与实现

基于3D-IC技术实现的3D SRAM,其电路中使用了大量的TSV。目前TSV制造工艺尚未成熟,使得TSV容易出现开路或短路故障,从而给3D SRAM的测试带来新的挑战。现有的2D BIST测试方式能够探测到3D SRAM中存在的故障,但并不能判定是TSV故障还是存储器本身故障;TSV专用测试电路虽然能够探测出TSV的故障,但需要特定的测试电路来实现,这就增加了额外的面积开销,同时加大了电路设计复杂度。基于此,本文提出了一种使用测试算法来探测TSV开路故障的方法,在不使用TSV专用测试电路且不增加额外面积开销的情况下通过BIST电路解决3D SRAM中TSV的开路故障检测问题。结果显示该TSV测试算法功能正确,能够准确探测到TSV的开路故障,并快速定位TSV的开路位置。