Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date

We consider a single-machine scheduling problem in which all jobs have the same due date and penalties are assessed for both early and late completion of jobs. However, earliness and tardiness are penalized at different rates. The scheduling objective is to minimize either the weighted sum of absolute deviations (WSAD) or the weighted sum of squared deviations (WSSD). For each objective we consider two versions of the problem. In the unconstrained version an increase in the due date does not yield any further decrease in the objective function. We present a constructive algorithm for the unconstrained WSAD problem and show that this problem is equivalent to the two-parallel, nonidentical machine, mean flow-time problem. For the unconstrained WSSD and the constrained WSAD and WSSD problems we propose implicit enumeration procedures based on several dominance conditions. We also report on our computational experience with the enumeration procedures.     

On the use of lexicographic min cost flows in evacuation modeling

Building evacuation problems can be represented as dynamic network-flow problems [3]. The underlying network structure of a building evolves through time yielding a time-expanded network (a dynamic network). Usually in such evacuation problems involving time, more than one objective function is appropriate. For example, minimizing the total evacuation time and evacuating a portion of the building as early as possible are two such objectives. In this article we show that lexicographical optimization is applicable in handling such multiple objectives. Minimizing the total evacuation time while avoiding cyclic movements in a building and “priority evacuation” are treated as lexicographical min cost flow problems.     

The dynamic transshipment problem

We investigate the strategy of transshipments in a dynamic deterministic demand environment over a finite planning horizon. This is the first time that transshipments are examined in a dynamic or deterministic setting. We consider a system of two locations which replenish their stock from a single supplier, and where transshipments between the locations are possible. Our model includes fixed (possibly joint) and variable replenishment costs, fixed and variable transshipment costs, as well as holding costs for each location and transshipment costs between locations. The problem is to determine how much to replenish and how much to transship each period; thus this work can be viewed as a synthesis of transshipment problems in a static stochastic setting and multilocation dynamic deterministic lot sizing problems. We provide interesting structural properties of optimal policies which enhance our understanding of the important issues which motivate transshipments and allow us to develop an efficient polynomial time algorithm for obtaining the optimal strategy. By exploring the reasons for using transshipments, we enable practitioners to envision the sources of savings from using this strategy and therefore motivate them to incorporate it into their replenishment strategies. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:386–408, 2001     

Sequential and systematic sampling plans for the Markov‐dependent production process

Acceptance sampling plans are used to assess the quality of an ongoing production process, in addition to the lot acceptance. In this paper, we consider sampling inspection plans for monitoring the Markov‐dependent production process. We construct sequential plans that satisfy the usual probability requirements at acceptable quality level and rejectable quality level and, in addition, possess the minimum average sample number under semicurtailed inspection. As these plans result in large sample sizes, especially when the serial correlation is high, we suggest new plans called “systematic sampling plans.” The minimum average sample number systematic plans that satisfy the probability requirements are constructed. Our algorithm uses some simple recurrence relations to compute the required acceptance probabilities. The optimal systematic plans require much smaller sample sizes and acceptance numbers, compared to the sequential plans. However, they need larger production runs to make a decision. Tables for choosing appropriate sequential and systematic plans are provided. The problem of selecting the best systematic sampling plan is also addressed. The operating characteristic curves of some of the sequential and the systematic plans are compared, and are observed to be almost identical. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 451–467, 2001     

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     

Response surface analysis of two‐stage stochastic linear programming with recourse

We apply the techniques of response surface methodology (RSM) to approximate the objective function of a two‐stage stochastic linear program with recourse. In particular, the objective function is estimated, in the region of optimality, by a quadratic function of the first‐stage decision variables. The resulting response surface can provide valuable modeling insight, such as directions of minimum and maximum sensitivity to changes in the first‐stage variables. Latin hypercube (LH) sampling is applied to reduce the variance of the recourse function point estimates that are used to construct the response surface. Empirical results show the value of the LH method by comparing it with strategies based on independent random numbers, common random numbers, and the Schruben‐Margolin assignment rule. In addition, variance reduction with LH sampling can be guaranteed for an important class of two‐stage problems which includes the classical capacity expansion model. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 753–776, 1999     

Lateral stock transshipments in a two‐location inventory system with fixed and joint replenishment costs

We address the problem of inventory management in a two‐location inventory system, in which the transshipments are carried out as means of emergency or alternative supply after demand has been realized. This model differs from previous ones as regards its replenishment costs structure, in which nonnegligible fixed replenishment costs and a joint replenishment cost are considered. The single period planning horizon is analyzed, with the form and several properties of the optimal replenishment and transshipment policies developed, discussed and illustrated. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 525–547, 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     

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     

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