Parallel machine scheduling: A probabilistic analysis

The minimum makespan of the general parallel machine scheduling problem with m machines and n jobs is studied. As for a number of other important combinatorial problems, the theory of empirical processes proves to be a very elegant and powerful tool for the probabilistic analysis of the solution value. It is used in this paper to derive a scheduling constant θ such that, for random processing times, the minimum makespan almost surely grows as θn when n goes to infinity. Moreover, a thorough probabilistic analysis is performed on the difference between the minimum makespan and θn. Explicit expressions for the scheduling constant are given for an arbitrary number of unrelated machines with identically distributed processing times (with an increasing failure rate), and for an arbitrary number of uniform machines and generally distributed processing times. © 1996 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.     

Optimal force mix in heterogeneous combat

This article presents models for determining the optimum number of Red weapons required to win a heterogeneous combat in which m(m> 1) types of Red weapons face a single type of Blue weapon under a newly defined termination policy. Red aims at either minimizing the total cost or maximizing the aggregated remaining force strength. Kuhn-Tucker and simulated annealing techniques are used for obtaining the optimal solution. The methodology is illustrated by analysing heterogeneous combat to determine (i) the feasibility of introducing new types of weapons and (ii) the number of weapons required to win if a specific type of weapon, say infantry, dominates. © 1995 John Wiley & Sons, Inc.     

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.     

Maintenance of a device with age-dependent exponential failures

We consider a device that deteriorates over time according to a Markov process so that the failure rate at each state is constant. The reliability of the device is characterized by a Markov renewal equation, and an IFRA (increasing failure rate on average) property of the lifetime is obtained. The optimal replacement and repair problems are analyzed under various cost structures. Furthermore, intuitive and counterintuitive characterizations of the optimal policies and results on some interesting special problems are presented. © 1992 John Wiley & Sons, Inc.     

An exact ceiling point algorithm for general integer linear programming

We present an algorithm called the exact ceiling point algorithm (XCPA) for solving the pure, general integer linear programming problem (P). A recent report by the authors demonstrates that, if the set of feasible integer solutions for (P) is nonempty and bounded, all optimal solutions for (P) are “feasible 1-ceiling points,” roughly, feasible integer solutions lying on or near the boundary of the feasible region for the LP-relaxation associated with (P). Consequently, the XCPA solves (P) by implicitly enumerating only feasible 1-ceiling points, making use of conditional bounds and “double backtracking.” We discuss the results of computational testing on a set of 48 problems taken from the literature.     

On the bivariate negative binomial distribution of mitchell and paulson

The bivariate negative binomial distribution of Mitchell and Paulson [17] for the case b = c = 0 is shown to be equivalent to the accident proneness model of Edwards and Gurland [4] and Subrahmaniam [19,20]. The diagonal series expansion of its joint probability function is then derived. Two other formulations of this distribution are also considered: (i) as a mixture model, which showed how it arises as the discrete analogue to the Wicksell-Kibble bivariate gamma distribution, and (ii) as a consequence of the linear birth-and-death process with immigration.     

State information lag markov decision process with control limit rule

In the framework of a discrete Markov decision process with state information lag, this article suggests a way for selecting an optimal policy using the control limit rule. The properties sufficient for an optimal decision rule to be contained in the class of control limit rules are also studied. The degradation in expected reward from that of the perfect information process provides a measure of the potential value of improving the information system.     

A reliability model with states of partial operation

This article generalizes the classical dichotomic reliability model to include states of partial operation. The generalized model can be considered as a special case of a general jump process. Both continuous and discrete state spaces are included. The relationship to cumulative damage shock models is discussed. Properties of the model are investigated and these are illustrated via examples. The equivalence of three forms of component independence is proved, but this equivalence does not generalize to the property of zero covariance. Alternative forms of series and parallel connections and the effect of component replacement are discussed.