Makespan minimization for m parallel identical processors

We introduce an algorithm, called TMO (Two-Machine Optimal Scheduling) which minimizes the makespan for two identical processors. TMO employs lexicographic search in conjunction with the longest-processing time sequence to derive an optimal schedule. For the m identical parallel processors problem, we propose an improvement algorithm, which improves the seed solution obtained by any existing heuristic. The improvement algorithm, called Extended TMO, breaks the original m-machine problem into a set of two-machine problems and solves them repeatedly by the TMO. A simulation study is performed to evaluate the effectiveness of the proposed algorithms by comparing it against three existing heuristics: LPT (Graham, [11]), MULTIFIT (Coffman, Garey, and Johnson, [6]), and RMG (Lee and Massey, [17]). The simulation results show that: for the two processors case, the TMO performs significantly better than LPT, MULTIFIT, and RMG, and it generally takes considerably less CPU time than MULTIFIT and RMG. For the general parallel processors case, the Extended TMO algorithm is shown to be capable of greatly improving any seed solution. © 1995 John Wiley & Sons, Inc.     

A replacement model with overhauls and repairs

This article generalizes the classical periodical replacement model with minimal repair by considering the effect of the overhaul, which is assumed to be able to rejuvenate the system. The generalization is based on the notion of the virtual age of a system introduced by Kijima, Morimura, and Suzuki [“Periodical Replacement Problem without Assuming Minimal Repair,” European Journal of Operational Research, 37 , 194–203 (1988)]. © 1995 John Wiley & Sons, Inc.     

Scheduling customer arrivals to a stochastic service system

An efficient algorithm for determining the optimal arrival schedule for customers in a stochastic service system is developed. All customers arrive exactly when scheduled, and service times are modeled as iid Erlang random variables. Costs are incurred at a fixed rate per unit of time each customer waits for service, and an additional cost is incurred for every unit of time the server operates beyond a scheduled closing time. The objective is to minimize total operating cost. This type of problem arises in many operational contexts including transportation, manufacturing, and appointment‐based services. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 549–559, 1999     

The effect of process adjustment error on X̄ chart design

The existing literature on economic design of X̄ process control charts generally assumes perfect process adjustment, such that the process mean is returned to an exactly centered “in control” state following any real or false alarm control chart signal. This paper presents a model which demonstrates the effects of imperfect process adjustment on the economically designed control chart parameters. The model demonstrates that the optimal control limit width depends fundamentally on the precision with which the process can be adjusted. The greater the process adjustment error, all else constant, the wider will be the optimal control limits, in order to alleviate the potential for process overcontrol and tampering effects. By endogenously modeling these effects, the new model helps to rectify the problem of poor statistical properties for which the economic design approach has been criticized. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 597–612, 1999     

Preservation of unimodality under shock models

A number of results pertaining to preservation of aging properties (IFR, IFRA etc.) under various shock models are available in the literature. Our aim in this paper is to examine in the same spirit, the preservation of unimodality under various shock models. For example, it is proved that in a non-homogeneous Poisson shock model if {p_k}_K≥0, the sequence of probabilities with which the device fails on the kth shock, is unimodal then under some suitable conditions on the mean value function Λ (t), the corresponding survival function is also unimodal. The other shock models under which the preservation of unimodality is considered in this paper are pure birth shock model and a more general shock model in which shocks occur according to a general counting process. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 952–957, 1999     

Test selection for a mass screeening program

Periodic mass screening is the scheduled application of a test to all members of a population to provide early detection of a randomly occurring defect or disease. This paper considers periodic mass screening with particular reference to the imperfect capacity of the test to detect an existing defect and the associated problem of selecting the kind of test to use. Alternative kinds of tests differ with respect to their reliability characteristics and their cost per application. Two kinds of imperfect test reliability are considered. In the first case, the probability that the test will detect an existing defect is constant over all values of elapsed time since the incidence of the defect. In the second case, the test will detect the defect if, and only if, the lapsed time since incidence exceeds a critical threshold T which characterizes the test. The cost of delayed detection is an arbitrary increasing function (the “disutility function”) of the duration of the delay. Expressions for the long-run expected disutility per unit time are derived for the above two cases along with results concerning the best choice of type of test (where the decision rules make reference to characteristics of the disutility function).     

War reserve spares kits supplemented by normal operating assets

In peacetime, base stock levels of spares are determined on the assumption of normal resupply from the depot. In the event of war, however, a unit must be prepared to operate from stock on hand for a period of time without being resupplied from the depot. This paper describes a mathematical model for determining such war reserve spares (WRS) requirements. Specifically, the model solves the following kind of optimization problem: find the least-cost WRS kits that will keep the probability of a stockout after K cannibalizations less than or equal to some target objective α. The user of the model specifies the number of allowable cannibalizations, and the level of protection that the kit is supposed to provide. One interesting feature of this model is that in the probability computation it takes into account the possiblility of utilizing normal base operating assets. Results of a sensitivity analysis indicate that if peacetime levels were explicitly taken into account when designing a WRS kit, a cost saving of nearly 40 percent could be effected without degrading base supply performance in wartime.     

A hard knapsack problem

In this article we develop a class of general knapsack problems which are hard for branch and bound algorithms. The number of alternate optimal solutions for these problems grows exponentially with problem parameters. In addition the LP bound is shown to be ineffective. Computational tests indicate that these problems are truly difficult for even very small problems. Implications for the testing of algorithms using randomly generated problems is discussed.     

Warranty reserving

This paper considers a problem of warranty reserving, namely, the current practice of setting aside part of a product revenue to meet future claims arising from the warranty. We define a Compound Poisson stochastic model for warranty claims and reserve and obtain, using a sample paths technique, the long-run probability distribution of a warranty reserves, managed under alternative warranties and reserve policies.     

A duality model for a generalized minmax program

We consider a generalized minmax programming problem, and establish, under certain weaker convexity assumptions, the Fritz John sufficient optimality conditions for such a problem. A dual program is introduced and using those optimality conditions duality theorems are proved relating the dual and the primal. Duality for the generalized fractional programming problem is considered as an application of the results proved.