The parallel machine min-max weighted absolute lateness scheduling problem

Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP-complete even for the single-machine case, and is strongly NP-complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst-case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. © 1994 John Wiley & Sons, Inc.     

A multiserver queue with markovian arrivals and group services with thresholds

We consider a multiserver queueing system in which arrivals are governed by a Markovian arrival process. The system is attended by K identical exponential servers. Under a dynamic probabilistic service rule which depends on two threshold parameters, this model is studied as a Markov process. The steady-state probability vector is shown to be of (modified) matrix-geometric type. Efficient algorithmic procedures for the computation of the steady-state probability vector and some key performance measures of the system are developed. Some numerical examples are discussed. © 1993 John Wiley & Sons, Inc.     

A finite capacity GI/PH/1 queue with group services

We consider a finite-capacity single-server queue in which arrivals occur one at a time, according to a renewal process. The successive service times are mutually independent and have a common phase-type distribution. The customers are served in groups of size at least L, a preassigned threshold value. Explicit analytic expressions for the steady-state queue-length densities at arrivals and at arbitrary time points, and the throughput of the system are obtained. The Laplace-Stieltjes transform of the stationary waiting-time distribution of an admitted customer at points of arrivals is computed. It is shown to be of phase type when the arrival process is also of phase type. Efficient algorithmic procedures for the steady-state analysis of the model are presented. These procedures are used in arriving at an optimal value for L that minimizes the mean waiting time of an admitted customer. A conjecture on the nature of the mean waiting time is proposed.     

Optimal strategies for problems of simultaneous attack against an area defense with impact-point prediction

An area to be defended consists of separated point targets. These targets are subject to an attack in which the offensive weapons are assumed to arrive simultaneously. The defense has area defenders, each of which is capable of intercepting any attacker'. Furthermore, the defense has impact-point prediction, i.e., it has knowledge of each attacker's intended target prior to allocation of the area interceptors. For a given attack, the defense wishes to allocate its interceptors against attackers so as to maximize the expected total survival value of the targets. In its first move, the offense seeks an attack allocation which will minimize expected total surviving value against best defense. We develop an algorithm to determine optimal attack and defense strategies and the optimal value of this sequential min-max problem. Branch-and-bound techniques are used to obtain integer solutions, and illustrative computational results are provided.     

Value added analysis for army equipment modernization

This paper describes the Value Added Analysis methodology which is used as part of the U.S. Army's Planning, Programming, Budgeting, and Execution System to assist the Army leadership in evaluating and prioritizing competing weapon system alternatives during the process of building the Army budget. The Value Added Analysis concept uses a family of models to estimate an alternative system's contribution to the Army's effectiveness using a multiattribute value hierarchy. A mathematical optimization model is then used to simultaneously determine an alternative's cost‐benefit and to identify an optimal mix of weapon systems for inclusion in the Army budget. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 233–253, 1999     

Optimal nonmyopic gambling strategy for the generalized Kelly criterion

We consider the optimal wagers to be made by a gambler who starts with a given initial wealth. The gambler faces a sequence of two-outcome games, i.e., “win” vs. “lose,” and wishes to maximize the expected value of his terminal utility. It has been shown by Kelly, Bellman, and others that if the terminal utility is of the form log x, where x is the terminal wealth, then the optimal policy is myopic, i.e., the optimal wager is always to bet a constant fraction of the wealth provided that the probability of winning exceeds the probability of losing. In this paper we provide a critique of the simple logarithmic assumption for the utility of terminal wealth and solve the problem with a more general utility function. We show that in the general case, the optimal policy is not myopic, and we provide analytic expressions for optimal wager decisions in terms of the problem parameters. We also provide conditions under which the optimal policy reduces to the simple myopic case. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 639–654, 1997     

Maintaining systems with heterogeneous spare parts

We consider the problem of optimally maintaining a stochastically degrading, single‐unit system using heterogeneous spares of varying quality. The system's failures are unannounced; therefore, it is inspected periodically to determine its status (functioning or failed). The system continues in operation until it is either preventively or correctively maintained. The available maintenance options include perfect repair, which restores the system to an as‐good‐as‐new condition, and replacement with a randomly selected unit from the supply of heterogeneous spares. The objective is to minimize the total expected discounted maintenance costs over an infinite time horizon. We formulate the problem using a mixed observability Markov decision process (MOMDP) model in which the system's age is observable but its quality must be inferred. We show, under suitable conditions, the monotonicity of the optimal value function in the belief about the system quality and establish conditions under which finite preventive maintenance thresholds exist. A detailed computational study reveals that the optimal policy encourages exploration when the system's quality is uncertain; the policy is more exploitive when the quality is highly certain. The study also demonstrates that substantial cost savings are achieved by utilizing our MOMDP‐based method as compared to more naïve methods of accounting for heterogeneous spares.     

Continuous sampling plans for markov-dependent production processes

This article discusses the behavior of three continuous sampling plans: continuous sampling plan 1 (CSP 1) and continuous sampling plan 2 (CSP 2) developed by Dodge [5] and Dodge and Torrey [7], and multilevel continuous sampling plan 2 (MLP 2) developed by Lieberman and Solomon [11], when the quality of successive units in a continuous production process follows a two-state time-homogeneous Markov chain. We first derive the average outgoing quality (AOQ) expressions of these plans. Exact procedures for determining the average outgoing quality limit (AOQL) can be obtained only for CSP 1. For CSP 2 and MLP 2 plans, iterative procedures have been used to obtain the AOQL contours. For these plans, it is assumed that the serial correlation coefficient between the two consecutive random variables of the Markov chain is known. In addition, estimation procedures for the coefficient are given. We show that if the serial correlation coefficient of the Markov chain is positive (negative), the AOQL is increased (decreased) as compared to the case when the successive units in the production process follows a Bernoulli pattern. Let r denote the number of production units examined in succession which are found to be of good quality and k denote the inverse of the sampling fraction employed when quality is good. Then if r and k are sufficiently small, it is observed from the graph that, for small departures of the serial correlation coefficient from zero, the AOQL values do not differ significantly for each of the three plans; whereas for sufficiently large values of r and k, the AOQL values differ significantly. Various aspects of these plans, such as their operating characteristics 2 (OC 2) and the serial correlation coefficient, are discussed.