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.     

An optimum group maintenance policy

In this article we present an optimum maintenance policy for a group of machines subject to stochastic failures where the repair cost and production loss due to the breakdown of machines are minimized. A nomograph was developed for machines with exponential failure time distributions. The optimal schedule time for repair as well as the total repair cost per cycle can be obtained easily from the nomograph. Conditions for the existence of a unique solution for the optimum schedule and the bounds for the schedule are discussed.     

A simple Markov model for the analysis of multiple air combat

It is proposed to describe multiple air-to-air combat having a moderate number of participants with the aid of a stochastic process based on end-game duels. A simple model describing the dominant features of air combat leads to a continuous time discrete-state Markov process. Solution of the forward Kolmogorov equations enables one to investigate the influence of initial force levels and performance parameters on the outcome probabilities of the multiple engagement. As is illustrated, such results may be useful in the decision-making process for aircraft and weapon system development planning. Some comparisons are made with Lanchester models as well as with a semi-Markov model.     

Stochastic duels with round-dependent hit probabilities

The effect of round dependent hit probabilities in the fundamental stochastic duel are examined. The general solution and several specific examples are derived where one side's hit probabilities are improved from round to round. For these specific cases the advantages of round to round improvement are explicitly displayed.