A new polynomial algorithm for maximum value flow with an efficient parallel implementation

A new algorithm is presented for finding maximal and maximum value flows in directed single-commodity networks. Commonly algorithms developed for this problem find a maximal flow by gradually augmenting (increasing) a feasible flow to a maximal flow. In the presented algorithm, at the beginning of each step or iteration, the flow on arcs is assigned to flow capacity. This may lead to an infeasible flow violating flow conservation at some nodes. During two passes of a MAIN step, consisting of a forward pass and a backward pass, the flow is reduced on some arcs to regain feasibility. The network is then pruned by omitting saturated arcs, and the process is repeated. The parallel implementation of the algorithm applies the two main steps at the same time to the same network. The outputs of the two steps are compared and the processing continues with the higher feasible flow. The algorithm is simple, intuitive, and efficient. © 1993 John Wiley & Sons, Inc.     

Static and dynamic scheduling of customer arrivals to a single-server system

In this article we consider a single-server system whose customers arrive by appointments only. Both static and dynamic scheduling problems are studied. In static scheduling problems, one considers scheduling a finite number of customer arrivals, assuming there is no scheduled customer arrival to the system. In dynamic scheduling problems, one considers scheduling one customer arrival only, assuming that there are a number of scheduled customers already. The expected delay time is recursively computed in terms of customer interarrival times for both cases. The objective is to minimize the weighted customer delay time and the server completion time. The problem is formulated as a set of nonlinear equations. Various numerical examples are illustrated. © 1993 John Wiley & Sons, Inc.     

Jointly constrained order quantities with all-units discounts

In this article we investigate situations where the buyer is offered discounted price schedules from alternative vendors. Given various discount schedules, the buyer must make the best buying decision under a variety of constraints, such as limited storage space and restricted inventory budgets. Solutions to this problem can be utilized by the buyer to improve profitability. EOQ models for multiple products with all-units discounts are readily solvable in the absence of constraints spanning the products. However, constrained discounted EOQ models lack convenient mathematical properties. Relaxing the product-spanning constraints produces a dual problem that is separable, but lack of convexity and smoothness opens the door for duality gaps. In this research we present a set of algorithms that collectively find the optimal order vector. Finally, we present numerical examples using actual data. to illustrate the application of the algorithms. © 1993 John Wiley & Sons, Inc.     

Solving time/cost trade-off problems with discounted cash flows using generalized benders decomposition

In this article we consider a project scheduling problem where there are cash flows throughout the life of the project and where shorter activity durations can be attained by incurring greater direct costs. In particular, the objective of this problem is to determine the activity durations and a schedule of activity start times so that the net present value of cash flows is maximized. We formulate this problem as a mixed-integer nonlinear program which is amenable to solution using the generalized Benders decomposition technique developed by Geoffrion. We test the algorithm on 140 project scheduling problems, the largest of which contains 30 nodes and 64 activities. Our computational results are quite encouraging inasmuch as 123 of the 140 problems require less than 1 CPU second of solution time. © 1993 John Wiley & Sons, Inc.     

Multiechelon inventory systems with lateral supply

We develop approximations to estimate the expected backorders in a multiechelon system in which lateral supply actions between bases are allowed when a backorder occurs. These approximations are easy to compute, and the average absolute error over a wide range of parameter values is less than 4% when items are depot repairable, even when bases are dissimilar. With lateral supply, backorder reductions of 30-50% are not uncommon, and a 72% reduction was observed in two cases. Lateral supply becomes more important with low demand rates. A similar approach was unsuccessful for base-repairable items. However, lateral supply has a beneficial effect only when the lateral supply time is very short, 1/4 or less of the average base repair time. Even in such cases lateral supply is unlikely to be important in an actual application, because base management can expedite repair of critical items.     

A multi-run interactive method for bicriterion optimization problems

This article introduces a new conceptual and methodological framework for the use of decision makers and their interactions with the computer in bicriterion decision making. The new method, called the multirun interactive method, attempts to estimate the prior of the decision maker on his uncertain preference nature using the minimum cross-entropy principle. A computational study is performed with four hypothesized prior distributions under various interaction conditions. Other important aspects related to the method, such as implementation of the method, decision making under certainty, decision making with multiple decision makers, and bicriterion integer programming, are also discussed.     

Scheduling with earliness and tardiness penalties

We show that the deterministic nonpreemptive scheduling problem with earliness and tardiness penalties can be solved in polynomial time for certain forms of an objective function provided that a certain optimization problem can be solved. We give instances where this problem has a solution and show that this generalizes several results from the literature. These results do not require symmetric penalization and the penalty functions need only be lower semicontinuous.     

Optimal resource extraction with uncertain reserves

We consider the problem of finding a plan that maximizes the expected discounted return when extracting a nonrenewable resource having uncertain reserves. An extraction plan specifies the rate at which the resource is extracted as a function of time until the resource is exhausted or the time horizon is reached. The return per unit of resource extracted may depend on the rate of extraction, time, and the amount of resource previously extracted. We apply a new method called the generalized search optimization technique to find qualitative features of optimal plans and to devise algorithms for the numerical calculation of optimal plans.     

Viability analysis: A formulation aid for all classes of network models

Nonviable network models have edges which are forced to zero flow simply by the pattern of interconnection of the nodes. The original nonviability diagnosis algorithm [4] is extended here to cover all classes of network models, including pure, generalized, pure processing, nonconserving processing, and generalized processing. The extended algorithm relies on the conversion of all network forms to a pure processing form. Efficiency improvements to the original algorithm are also presented.     

Minimal forecast horizons in equipment replacement models with multiple technologies and general switching costs

This article considers the problem of equipment replacement in which the replacement decision at a particular time must take into account (i) the state of the existing machine in use, (ii) the available replacement alternatives at the time, (iii) the future advances in the relevant technologies with regard to the equipment under consideration, and (iv) costs of switching between different technologies. A methodology that attains minimal forecast horizons for the problem is developed. A numerical example illustrates the methodology.