Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance

The machine scheduling literature does not consider the issue of tool change. The parallel literature on tool management addresses this issue but assumes that the change is due only to part mix. In practice, however, a tool change is caused most frequently by tool wear. That is why we consider here the problem of scheduling a set of jobs on a single CNC machine where the cutting tool is subject to wear; our objective is to minimize the total completion time. We first describe the problem and discuss its peculiarities. After briefly reviewing available theoretical results, we then go on to provide a mixed 0–1 linear programming model for the exact solution of the problem; this is useful in solving problem instances with up to 20 jobs and has been used in our computational study. As our main contribution, we next propose a number of heuristic algorithms based on simple dispatch rules and generic search. We then discuss the results of a computational study where the performance of the various heuristics is tested; we note that the well‐known SPT rule remains good when the tool change time is small but deteriorates as this time increases and further that the proposed algorithms promise significant improvement over the SPT rule. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Analysis of a finite‐buffer bulk‐service queue with discrete‐Markovian arrival process: D‐MAP/Ga,b/1/N

Discrete‐time queues with D‐MAP arrival process are more useful in modeling and performance analysis of telecommunication networks based on the ATM environment. This paper analyzes a finite‐buffer discrete‐time queue with general bulk‐service rule, wherein the arrival process is D‐MAP and service times are arbitrarily and independently distributed. The distributions of buffer contents at various epochs (departure, random, and prearrival) have been obtained using imbedded Markov chain and supplementary variable methods. Finally, some performance measures such as loss probability and average delay are discussed. Numerical results are also presented in some cases. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 345–363, 2003.     

A componentwise index of service measurement in multi‐component systems

In this paper we present a componentwise delay measure for estimating and improving the expected delays experienced by customers in a multi‐component inventory/assembly system. We show that this measure is easily computed. Further, in an environment where the performance of each of the item delays could be improved with investment, we present a solution that aims to minimize this measure and, in effect, minimizes the average waiting time experienced by customers. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 50: 2003     

Dominating sets for rectilinear center location problems with polyhedral barriers

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 647–665, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10038     

From rivals to partners: AirSea Battle and the US air force–navy relationship

AirSea Battle (ASB) has generated significant publicity, controversy, and debate among scholars, analysts, commentators, and observers of US defense strategy. However, a research gap exists concerning formal analysis of the impact of the operational concept on the relationship between the US Air Force (USAF) and the US Navy (USN). The impact of the ASB operational concept on the USAF–USN relationship is examined across the issue areas of strategy, budgets, weapons procurement, and training. These four issue areas represent important areas of historical conflict and competition between the Air Force and Navy. The conclusion is that ASB is ushering in a new era of Air Force–Navy partnership that advances the inter-service dynamic from “jointness” toward integration. The emergent USAF–USN partnership therefore represents a significant development in US defense politics and defense strategy.     

Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

Preemptive parallel‐machine scheduling with a common server to minimize makespan

We consider parallel‐machine scheduling with a common server and job preemption to minimize the makespan. While the non‐preemptive version of the problem is strongly NP‐hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP‐hard even if there is a fixed number of machines. We give a pseudo‐polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP‐hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017     

The long term effects of an aging fleet on operational availability and cost: evidence from the U.S. coast guard

This paper empirically examines whether the aging of a fleet affects operational availability and operating cost using a unique data-set on the 117 47-foot Motor Lifeboats (MLBs) of the United States Coast Guard (USCG). Procured from 1997 to 2003, the 47-foot MLB is the standard lifeboat of the USCG and all 117 MLBs remain in service. The aging of the MLB fleet has resulted in higher annual operating costs and lower operational availability, although the nature of this relationship remains unclear. Our estimation strategy utilizes an error components estimator to examine these issues. We employ three variants of the dependent variables (i.e. the standard logarithmic transformation as is most commonly seen in the literature, inverse hyperbolic sine [IHS], and level outcomes). The point estimates from the standard logarithmic model finds operational availability for the MLBs decreases at a rate between 0.83 and 1.8% per year and cost increases at a rate between 0.33 and 7.81% per year. Similar effects are shown with the IHS and level outcome specifications. In terms of nonlinearity effects, we find the most pronounced changes in operational availability and cost occur for MLBs aged 15 years or more (in comparison to younger MLBs).     

The burglar problem with multiple options

We consider the burglar problem in which a burglar can either retire or choose among different types of burglaries, with each type having its own success probability and reward distribution. Some general structural results are established and, in the case of exponentially distributed reward distributions, a solution technique is presented. The burglar problem's relationship to a stochastic knapsack problem with a random exponentially distributed knapsack capacity is shown. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 359–364, 2014