Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

I Will Follow: Smart Power and the Management of Wartime Alliances

Abstract

This paper employs the concept of smart power to construct an analytical framework for assessing wartime alliance management. It makes two arguments. First, wartime sources of soft power differ from those obtaining during peacetime. Second, the coerciveness with which an alliance leader wields hard power towards actual or prospective allies should vary inversely with the amount of soft power it possesses. The smart power framework illuminates three types of alliance management failure. The paper’s key contentions are illustrated with examples furnished from the record of US alliance leadership since World War II.     

Some aging properties of parallel and series systems with a random number of components

In this article, we study aging properties of parallel and series systems with a random number of components. We show that the decreasing likelihood ratio property is closed under the formation of random minima. We also show, by counterexamples, that other aging properties are not closed under the formation of random minima or maxima. Some mistakes in the literature are corrected. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 238–243, 2014     

An interactive approach to multicriteria sorting for quasiconcave value functions

In this article, we develop an interactive algorithm to place alternatives in ordered preference classes for a decision maker (DM) with an increasing quasiconcave value function. Such value functions are quite general in that they include linear and concave value functions. Our aim is to elicit sorting information from the DM as few times as possible; our algorithm places other alternatives using previous responses from the DM utilizing properties of quasiconcave value functions. As an application, we sort 81 global MBA programs into preference classes using criteria such as alumni career progress, idea generation, and diversity. We study the performance of our proposed algorithm, when we change the number of criteria, number of alternatives, and introduce response errors. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 447–457, 2014     

Index policies for the routing of background jobs

Arriving (generic) jobs may be processed at one of several service stations, but only when no other (dedicated) jobs are waiting there. We consider the problem of how to route these incoming background jobs to make best use of the spare service capacity available at the stations. We develop an approximative approach to Whittle's proposal for restless bandits to obtain an index policy for routing. The indices concerned are increasing and nonlinear in the station workload. A numerical study testifies to the strong performance of the index policies developed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Exact likelihood inference for the exponential distribution under generalized Type‐I and Type‐II hybrid censoring

Chen and Bhattacharyya [Exact confidence bounds for an exponential parameter under hybrid censoring, Commun Statist Theory Methods 17 (1988), 1857–1870] considered a hybrid censoring scheme and obtained the exact distribution of the maximum likelihood estimator of the mean of an exponential distribution along with an exact lower confidence bound. Childs et al. [Exact likelihood inference based on Type‐I and Type‐II hybrid censored samples from the exponential distribution, Ann Inst Statist Math 55 (2003), 319–330] recently derived an alternative simpler expression for the distribution of the MLE. These authors also proposed a new hybrid censoring scheme and derived similar results for the exponential model. In this paper, we propose two generalized hybrid censoring schemes which have some advantages over the hybrid censoring schemes already discussed in the literature. We then derive the exact distribution of the maximum likelihood estimator as well as exact confidence intervals for the mean of the exponential distribution under these generalized hybrid censoring schemes. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Higher‐order Markov chain models for categorical data sequences*

In this paper we study higher‐order Markov chain models for analyzing categorical data sequences. We propose an efficient estimation method for the model parameters. Data sequences such as DNA and sales demand are used to illustrate the predicting power of our proposed models. In particular, we apply the developed higher‐order Markov chain model to the server logs data. The objective here is to model the users' behavior in accessing information and to predict their behavior in the future. Our tests are based on a realistic web log and our model shows an improvement in prediction. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Strategies for managing the flexible capacity in the airline industry

The ability to effectively match supply and demand under uncertainty can result in significant revenue benefits in the airline industry. We study the benefits of a Demand Driven Swapping (DDS) approach that takes advantage of the flexibilities in the system and dynamically swaps aircraft as departures near and more accurate demand information is obtained. We analyze the effectiveness of different DDS strategies, characterized by their frequency (how often the swapping decision is revised), in hedging against demand uncertainty. Swapping aircraft several weeks prior to departures will not cause much disturbance to revenue management and operations, but will be based on highly uncertain demands. On the other hand, revising the swapping decision later will decrease the possibility of bad swaps, but at a higher cost of disrupting airport services and operations. Our objective is to provide guidelines on how the flexible (swappable) capacity should be managed in the system. We study analytical models to gain insights into the critical parameters that affect the revenue benefits of the different swapping strategies. Our study determines the conditions under which each of the different DDS strategies is effective. We complement our analysis by testing the proposed DDS strategies on a set of flight legs, using data obtained from United Airlines. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

An algorithm for the solution of a location problem with metric constraints

In many location problems, the solution is constrained to lie within a closed set. In this paper, optimal solutions to a special type of constrained location problem are characterized. In particular, the location problem with the solution constrained to be within a maximum distance of each demand point is considered, and an algorithm for its solution is developed and discussed.     

Optimal location of a single service center of certain types

Hakimi has considered the problem of finding an optimal location for a single service center, such as a hospital or a police station. He used a graph theoretic model to represent the region being serviced. The communities are represented by the nodes while the road network is represented by the ares of the graph. In his work, the objective is one of minimizing the maximum of the shortest distances between the vertices and the service center. In the present work, the region being serviced is represented by a convex polygon and communities are spread over the entire region. The objective is to minimize the maximum of Euclidian distances between the service center and any point in the polygon. Two methods of solution presented are (i) a geometric method, and (ii) a quadratic programming formulation. Of these, the geometric method is simpler and more efficient. It is seen that for a class of problems, the geometric method is well suited and very efficient while the graph theoretic method, in general, will give only approximate solutions in spite of the increased efforts involved. But, for a different class of problems, the graph theoretic approach will be more appropriate while the geometric method will provide only approximate solutions though with ease. Finally, some feasible applications of importance are outlined and a few meaningful extensions are indicated.