Analysis of the greedy approach in problems of maximum k-coverage

In this paper, we consider a general covering problem in which k subsets are to be selected such that their union covers as large a weight of objects from a universal set of elements as possible. Each subset selected must satisfy some structural constraints. We analyze the quality of a k-stage covering algorithm that relies, at each stage, on greedily selecting a subset that gives maximum improvement in terms of overall coverage. We show that such greedily constructed solutions are guaranteed to be within a factor of 1 − 1/e of the optimal solution. In some cases, selecting a best solution at each stage may itself be difficult; we show that if a β-approximate best solution is chosen at each stage, then the overall solution constructed is guaranteed to be within a factor of 1 − 1/e^β of the optimal. Our results also yield a simple proof that the number of subsets used by the greedy approach to achieve entire coverage of the universal set is within a logarithmic factor of the optimal number of subsets. Examples of problems that fall into the family of general covering problems considered, and for which the algorithmic results apply, are discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 615–627, 1998     

Automated air load planning

We describe the development of a heuristic algorithm for determining efficient 2-dimensional packings in cargo aircraft where cargo placement constraints are critically important in determining the feasibility of packing locations. We review the performance of a new algorithm versus some traditional ones for aircraft loading. The algorithm is also tested in a more generalized setting where there exist no additional constraints on items, to suggest applicability in other environments. The new algorithm has been used worldwide in the Automated Air Load Planning System (AALPS) for cargo aircraft loading, with much success. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 751–768, 1998     

When chaos reigns: responding to complex emergencies

This article discusses the impact of Complex Humanitarian Emergencies on the delivery of humanitarian aids. Complex emergencies were the results of long-term political and social disputes. Its impact brings about public health crises like epidemics, malnutrition, and even widespread desperation. In fact, there are four aspects of these crises which complicate public health programs: 1) emergencies are long and recurring; 2) access to the most vulnerable population is often restricted; 3) restructuring health systems in complex emergencies can be futile; and 4) complex emergencies often result in mass forced migration. What makes matters worse is the breakdown of health networks which collapse early in complex emergencies, leading to extensive losses of human health resources. Not only that, health facilities and transportation, infrastructure are often decimated in complex emergencies, and regional hospitals, district health posts, laboratories, and primary care outposts are similarly abandoned or destroyed. Moreover, because it is difficult to predict the course of these emergencies, ascertaining the optimal time to intervene and to invest in materials and facilities that could be lost to renewed fighting can be impossible. To solve this problem requires a coordinated effort. It should also focus on resources, early warning systems, preparedness measures, ongoing career training of relief workers, and prepositioning of relief supplies.     

交互式管理信息系统生成工具的设计与构造

本文根据作者近年来研制交互式管理信息系统(MIS)生成工具的实践,阐述了一个人机界面友好的交互式MIS生成工具的设计与实现。这个工具本身是交互式系统,生成的MIS也是交互式系统。它是根据交互式系统的一般结构,采用控制结构上悬挂模板的方式来构造和组装(MIS)软件产品。     

An efficient algorithm for the location-allocation problem with rectangular regions

The location-allocation problem for existing facilities uniformly distributed over rectangular regions is treated for the case where the rectilinear norm is used. The new facilities are to be located such that the expected total weighted distance is minimized. Properties of the problem are discussed. A branch and bound algorithm is developed for the exact solution of the problem. Computational results are given for different sized problems.     

Remarks on a univariate shock model with some bivariate generalizations

In a 1973 paper J. D. Esary, A. W. Marshall, and F. Proschan [5] considered a shock model giving rise to various nonparametric classes of life distributions of interest in reliability theory. A number of authors have extended these results in a variety of directions. In this paper, alternative proofs of the increasing failure rate (IFR) and decreasing mean residual life (DMRL) results are given which do not make use of the theory of total positivity. Some bivariate extensions are then obtained using a shock model similar to that originally used by H. W. Block, A. S. Paulson, and R. C. Kohberger [2] to unify various bivariate exponential distributions.     

Approximate decision rules for continuous review inventory systems

Constrained multi-item inventory models have long presented signifcant computational problems. This article presents a general algorithm to obtain simultaneous solutions for order quantities and safety stocks for each line item in an inventory, while satisfying constraints on average inventory investment and reordering workload. Computational experience is presented that demonstrates the algorithm's efficiency in handling large-scale applications. Decision rules for several customer service objectives are developed, with a discussion of the characteristics of the inventory systems in which each objective would be most appropriate. The decision rules are approximations, based on the assumptions commonly used in practice.     

An economic sequential screening procedure for limited failure populations

An economic sequential screening procedure is considered for limited failure populations in which defective items fail soon after they are put in operation and nondefective ones never fail during the technical life of the items. A cost model is constructed that involves screening test cost and external failure cost. A sequential scheme that minimizes the expected cost is derived from the solution of a dynamic programming formulation and the optimal decision at each stage is obtained in a closed form. © 1994 John Wiley & Sons, Inc.     

The applicability of acceptance sampling with respect to process stability and control

This article examines the applicability of acceptance sampling and the effectiveness of Deming's kp rule in relation to the degree of process stability achieved through statistical process control techniques. A discrete-event simulation model is used to characterize the correlation between the number of defective units in a randomly drawn sample versus in the remainder of a lot, in response to a number of system and control chart parameters. The model reveals that such correlation is typically present when special causes of variation affect the production process from time to time, even though the process is tightly monitored through statistical process control. Comparison of these results to an analogous mixed binomial scenario reveals that the mixed binomial model overstates the correlation in question if the state of the process is not necessarily constant during lot production. A generalization of the kp analysis is presented that incorporates the possibility of dependence between a sample and the unsampled portion of the lot. This analysis demonstrates that acceptance sampling is generally ineffective for lots generated by a process subject to statistical process control, despite the fact that the number of defectives in the sample and in the remainder of the lot are not strictly independent. © 1994 John Wiley & Sons, Inc.     

Control variable methods in the simulation of a model of a multiprogrammed computer system

One approach to the evaluation of the performance of multiprogranmed computer systems includes the development of Monte Carlo simulations of transitions of programs within such systems, and their strengthening by control variable and concomitant variable methods. An application of such a combination of analytical, numerical, and Monte Carlo approaches to a model of system overhead in a paging machine is presented.