Quadratic forms in spherical random variables: Generalized noncentral x2 distribution

Let X denote a random vector with a spherically symmetric distribution. The density of U = X'X, called a “generalized chi-square,” is derived for the noncentral case, when μ = E(X) ≠ 0. Explicit series representations are found in certain special cases including the “generalized spherical gamma,” the “generalized” Laplace and the Pearson type VII distributions. A simple geometrical representation of U is shown to be useful in generating random U variates. Expressions for moments and characteristic functions are also given. These densities occur in offset hitting probabilities.     

Inventory control of by-products

The system to be controlled produces n products simultaneously in fixed proportions every time it is activated. Demands for the products in any period are components of an n dimensional vector random variable with known distribution function. Cases of excess demands backlogged and excess demands lost are considered. In the former the notion of k convexity can be generalized to guarantee relatively simple form for the optimal policy in an n decision problem. In the latter, this generalization was not successful although when there is no setup cost, a convexity argument can be used to show that the optimal policy has a simple form.     

Minimum-cost flows in convex-cost networks

An algorithm is given for solving minimum-cost flow problems where the shipping cost over an arc is a convex function of the number of units shipped along that arc. This provides a unified way of looking at many seemingly unrelated problems in different areas. In particular, it is shown how problems associated with electrical networks, with increasing the capacity of a network under a fixed budget, with Laplace equations, and with the Max-Flow Min-Cut Theorem may all be formulated into minimum-cost flow problems in convex-cost networks.     

The bounded interval generalized assignment model

The bounded interval generalized assignment model is a “many-for-one” assignment model. Each task must be assigned to exactly one agent; however, each agent can be assigned multiple tasks as long as the agent resource consumed by performing the assigned tasks falls within a specified interval. The bounded interval generalized assignment model is formulated, and an algorithm for its solution is developed. Algorithms for the bounded interval versions of the semiassignment model and sources-to-uses transportation model are also discussed.     

Comparing alternating renewal processes

Sufficient conditions are given for stochastic comparison of two alternating renewal processes based on the concept of uniformization. The result is used to compare component and system performance processes in maintained reliability systems.     

A proof for the longest-job-first policy in one-machine scheduling

We consider a one-machine scheduling problem with earliness and tardiness penalties. All jobs are assigned a common due date and the objective is to minimize the total penalty due to job earliness and tardiness. We are interested in finding the optimal combination of the common due-date value and the job sequence. Despite the fact that this problem in general is very hard to solve, we prove that there exists at least a common property for all optimal solutions: The first job in an optimal sequence is one of the longest jobs. We also prove that this property holds for a general class of unimodal penalty functions.     

An exact algorithm for the maximal covering problem

This article develops a robust, exact algorithm for the maximal covering problem (MCP) using dual-based solution methods and greedy heuristics in branch and bound. Based on tests using randomly generated problems with problem parameters similar to those in the existing literature, the hybrid approach developed in this work appears to be effective over a wide range of MCP model parameters. The method is further validated on problems constructed from three real-world data sets. The extensive computational study compares the new method with other existing exact methods using problems that are as big, or larger than, those used in previous work on MCP. The results show that the proposed method is effective in most instances of MCP. In particular, it is shown that bounding schemes using Lagrangian relaxation are effective on MCP as a method of obtaining both exact and heuristic solutions. © 1996 John Wiley & Sons, Inc.