A forward network simplex algorithm for solving multiperiod network flow problems

An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision-making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.     

The discrete max-min problem

The historic max-min problem is examined as a discrete process rather than in its more usual continuous mode. Since the practical application of the max-min model usually involves discrete objects such as ballistic missiles, the discrete formulation of the problem seems quite appropriate. This paper uses an illegal modification to the dynamic programming process to obtain an upper bound to the max-min value. Then a second but legal application of dynamic programming to the minimization part of the problem for a fixed maximizing vector will give a lower bound to the max-min value. Concepts of optimal stopping rules may be applied to indicate when sufficiently near optimal solutions have been obtained.     

Simulation of multi-echelon macro-inventory policies

Alternative repair part inventory policies are examined for a multi-echelon logistics system. The policies assessed pertain to the design of multi-echelon systems rather than the evaluation of stock level decisions for individual repair parts. Although the context is one of a military inventory system, the policies examined are of importance in nonmilitary systems where item failure rates are low, and only periodic access to resupply is possible.     

A backward recursive technique for optimal sequential sampling plans

This paper presents a procedure akin to dynamic programming for designing optimal acceptance sampling plans for item-by-item inspection. Using a Bayesian procedure, a prior distribution is specified, and a suitable cost model is employed depicting the cost of sampling, accepting or rejecting the lot. An algorithm is supplied which is digital computer oriented.     

Requirements of an “optimizer” for computer simulations

Computer simulation has many advantages. However, one major disadvantage is that, in all too many cases, the attempt to use computer simulation to find an optimum solution to a problem rapidly degenerates into a trial-and-error process. Techniques for overcoming this disadvantage, i. e., for making optimization and computer simulation more compatible, are applicable at two points in the development of the overall computer simulation. Techniques which are used within actual construction of the mathematical models comprising the simulation will be labeled as internal methods, while those which are used after the simulation has been completely developed will be termed external methods Because external methods appear to offer the largest potential payoff, discussion is restricted to these methods, which are essentially search techniques. In addition, the development of an “Optimizer” computer program based on these techniques is suggested Although drawbacks to the use of search techniques in the computer simulation framework exist, these techniques do offer potential for “optimization.” The modification of these techniques to satisfy the requirements of an “Optimizer” is discussed.     

Probabilistic priorities in the M/G/1 queue

A simple method is presented for deriving the mean and variance of the queueing time distribution in an M/G/1 queue when the priorities assigned to customers have an assignment probability distribution. Several examples illustrate the results. The mean and variance of the queueing time distribution for the longest service time discipline are derived, and its disadvantages are discussed.     

Occupational structure in the military and civilian sectors of the economy

This paper focuses on trends in the occupational structure of the military and civilian sectors of the economy. Some implications of these trends for manpower policies for the all-volunteer military establishment are examined.