Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A search game on a cyclic graph

There is a finite cyclic graph. The hider chooses one of all nodes except the specified one, and he hides an (immobile) object there. At the beginning the seeker is at the specified node. After the seeker chooses an ordering of the nodes except the specified one, he examines each nodes in that order until he finds the object, traveling along edges. It costs an amount when he moves from a node to an adjacent one and also when he checks a node. While the hider wishes to maximize the sum of the traveling costs and the examination costs which are required to find the object, the seeker wishes to minimize it. The problem is modeled as a two‐person zero‐sum game. We solve the game when unit costs (traveling cost + examination cost) have geometrical relations depending on nodes. Then we give properties of optimal strategies of both players. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Bivariate models from univariate life distributions: A characterization cum modeling approach

Bivariate life distribution models are of importance for studying interdependent components. We present a generic approach by introducing a new concept of characterized model in stead of a characterized distribution. It strikes a balance between characterization and modeling approaches to eliminate their individual limitations and incorporate their respective strengths. The proposed model, being a characterized one, admits many important properties irrespective of the choice of marginal distributions. The retention of univariate IFR, DFR, IFRA, DFRA, NBU, and NWU class properties in the bivariate setup has been ensured along with some results on series combinations and convolution. No other models, available in the literature, can ensure simultaneous retention of these fundamental and extremely important class properties. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Flow shop scheduling with earliness,tardiness, and intermediate inventory holding costs

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work‐in‐process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig‐Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig‐Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near‐optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly ????‐hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near‐optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Warranty costs: An age‐dependent failure/repair model

An age‐dependent repair model is proposed. The notion of the “calendar age” of the product and the degree of repair are used to define the virtual age of the product. The virtual failure rate function and the virtual hazard function related to the lifetime of the product are discussed. Under a nonhomogeneous Poisson process scenario the expected warranty costs for repairable products associated with linear pro‐rata, nonrenewing free replacement and renewing free replacement warranties are evaluated. Illustration of the results is given by numerical and graphical examples. © 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     

On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A general approach to the shape of failure rate and MRL functions

Failure rate and mean residual life are two important characteristics for studying reliability of products. In literature, some work studied the shape of failure rate function based on the knowledge of the associated probability density function; some other work investigated the shape of mean residual life function based on the shape of the associated failure rate function separately for continuous case and discrete case. In this article, a general approach is developed which can be applied to the aforementioned studies. © 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     

R-C系统中由表面散射引起的视场内杂散光分布

推导了R-C系统焦平面上由主镜和次镜表面散射引起的视场内杂散光分布的近似解析表达式.针对典型R-C系统的视场内杂散光分布,由近似表达式得到的计算结果与利用商业光学仿真软件得到的模拟结果具有较好的一致性,说明了近似表达式的正确性.与焦平面上无像差衍射光分布相比较,可以方便地分析强光入射时R-C系统焦平面上不同区域的饱和机制.研究结果表明,对于典型的R-C系统,探测器表面上以几何像点为中心,半径为2.5mm的范围内,衍射光是引起探测器饱和的主要因素;在此范围外,表面散射造成探测器的饱和.该结果为进一步研究强光饱和实验,解释有关现象提供理论分析基础.