Single-machine scheduling with early and tardy completion costs

We address a single-machine scheduling problem in which penalties are assigned for early and tardy completion of jobs. These penalties are common in industrial settings where early job completion can cause the cash commitment to resources in a time frame earlier than needed, giving rise to early completion penalties. Tardiness penalties arise from a variety of sources, such as loss of customer goodwill, opportunity costs of lost sales, and direct cash penalties. Accounting for earliness cost makes the performance measure nonregular, and this nonregularity has apparently discouraged researchers from seeking solutions to this problem. We found that it is not much more difficult to design an enumerative search for this problem than it would be if the performance measure were regular. We present and demonstrate an efficient timetabling procedure which can be embedded in an enumerative algorithm allowing the search to be conducted over the domain of job permutations.© 1993 John Wiley & Sons, Inc.     

Discrete repairable reliability systems

Consider a reliability system consisting of n components. The failures and the repair completions of the components can occur only at positive integer-valued times k ϵ N₊₊ ϵ (1, 2, …). At any time k ϵ N₊₊ each component can be in one of two states: up (i.e., working) or down (i.e., failed and in repair). The system state is also either up or down and it depends on the states of the components through a coherent structure function τ. In this article we formulate mathematically the above model and we derive some of its properties. In particular, we identify conditions under which the first failure times of two such systems can be stochastically ordered. A variety of special cases is used in order to illustrate the applications of the derived properties of the model. Some instances in which the times of first failure have the NBU (new better than used) property are pointed out. © 1993 John Wiley & Sons, Inc.     

Multiobjective flow-shop scheduling

Previous research on the scheduling of multimachine systems has generally focused on the optimization of individual performance measures. This article considers the sequencing of jobs through a multimachine flow shop, where the quality of the resulting schedule is evaluated according to the associated levels of two scheduling criteria, schedule makespan (C_max) and maximum job tardiness (T_max). We present constructive procedures that quantify the trade-off between C_max and T_max. The significance of this trade-off is that the optimal solution for any preference function involving only C_max and T_max must be contained among the set of efficient schedules that comprise the trade-off curve. For the special case of two-machine flow shops, we present an algorithm that identifies the exact set of efficient schedules. Heruistic procedures for approximating the efficient set are also provided for problems involving many jobs or larger flow shops. Computational results are reported for the procedures which indicate that both the number of efficient schedules and the error incurred by heuristically approximating the efficient set are quite small.     

On estimating population characteristics from record-breaking observations II. Nonparametric results

Consider an experiment in which only record-breaking values (e.g., values smaller than all previous ones) are observed. The data available may be represented as X₁,K₁,X₂,K₂, …, where X₁,X₂, … are successive minima and K₁,K₂, … are the numbers of trials needed to obtain new records. Such data arise in life testing and stress testing and in industrial quality-control experiments. When only a single sequence of random records are available, efficient estimation of the underlying distribution F is possible only in a parametric framework (see Samaniego and Whitaker [9]). In the present article we study the problem of estimating certain population quantiles nonparametrically from such data. Furthermore, under the assumption that the process of observing random records can be replicated, we derive and study the nonparametric maximum-likelihood estimator F̂ of F. We establish the strong uniform consistency of this estimator as the number of replications grows large, and identify its asymptotic distribution theory. The performance of F̂ is compared to that of two possible competing estimators.     

A continuous game of ambush

The article considers a two-person competitive problem in which a traveller wishes to choose a path across a rectangle from left to right in such a way as to avoid being ambushed by his adversary who has placed obstacles within the rectangle. Our results supplement those that have already been obtained by Ruckle and they indicate that, under certain conditions, the players need to adopt rather sophisticated strategies if they are to act optimally. This suggests that a complete solution to the problem could be difficult.     

A generalized inspection game

The paper addresses the problem of a patrol trying to stop smugglers who are attempting to ship a cargo of perishable contraband across a strait in one of M time units. The situation was modeled as a two-person zero-sum game of exhaustion by Thomas and Nisgav and this article extends their results. The game has many characteristics in common with the Inspection Game in Owen's book on Game Theory; this Inspection Game is generalized and the relations between the two games are discussed.     

Estimating component characteristics from system failure‐time data

Suppose that failure times are available from a random sample of N systems of a given, fixed design with components which have i.i.d. lifetimes distributed according to a common distribution F. The inverse problem of estimating F from data on observed system lifetimes is considered. Using the known relationship between the system and component lifetime distributions via signature and domination theory, the nonparametric maximum likelihood estimator _N(t) of the component survival function (t) is identified and shown to be accessible numerically in any application of interest. The asymptotic distribution of _N(t) is also identified, facilitating the construction of approximate confidence intervals for (t) for N sufficiently large. Simulation results for samples of size N = 50 and N = 100 for a collection of five parametric lifetime models demonstrate the utility of the recommended estimator. Possible extensions beyond the i.i.d. framework are discussed in the concluding section. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010