Closure properties of the relevation transform*

Sufficient conditions under which the relevation of two probability distributions is (i) NBU, (ii) IFRA, (iii) IFR are derived. The result for case (iii) corrects an error in a previous article by Baxter.     

On finding spanning eulerian subgraphs

In this article, we examine the problem of producing a spanning Eulerian subgraph in an undirected graph. After the ?-completeness of the general problem is established, we present polynomial-time algorithms for both the maximization and minimization versions where instances are defined on a restricted class of graphs referred to as series-parallel. Some novelties in the minimization case are discussed, as are heuristic ideas.     

An analysis of degeneracy

Degeneracy in linear programming models has been analyzed for its impacts on algorithmic properties. A complementary analysis here is on what the solutions mean. The framework presented is couched in marginal sensitivity analysis, introducing concepts of “compatible bases” and “transition graphs”.     

Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

Decentralized stockage policies in a multiechelon environment

Characteristics of supply performance at the top echelon of an optimally managed multiechelon supply system are investigated; insights are developed which are useful in devising coordinated single-echelon policies which can approximate the benefits derived from multiechelon management.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.