Tree-search algorithms for quadratic assignment problems

Problems having the mathematical structure of a quadratic assignment problem are found in a diversity of contexts: by the economist in assigning a number of plants or indivisible operations to a number of different geographical locations; by the architect or indusatrial engineer in laying out activities, offices, or departments in a building; by the human engineer in arranging the indicators and controls in an operators control room; by the electronics engineer in laying out components on a backboard; by the computer systems engineer in arranging information in drum and disc storage; by the production scheduler in sequencing work through a production facility; and so on. In this paper we discuss several types of algorithms for solving such problems, presenting a unifying framework for some of the existing algorithms, and dcscribing some new algorithms. All of the algorithms discussed proceed first to a feasible solution and then to better and better feasible solutions, until ultimately one is discovered which is shown to be optimal.     

Markov chain analysis of a situation where cannibalization is the only repair activity

This paper considers a group of S identical aircraft, each of which is partitioned into K parts which fail exponentially. The only way in which a failed aircraft can be repaired is by cannibalizing its out-of-commission parts from other failed aircraft. The evolution of the number of good aircraft over time is governed by the transient behavior of an absorbing Markov chain. We can therefore study this behavior by matrix multiplication although the computational problem grows large for K ≥ 3. Some numerical results and some approximations are also provided.     

More ado about economic order quantities (EOQ)

This paper is concerned with the determination of explicit expressions for economic order quantities and reorder levels, such that the cost of ordering and holding inventory is minimized for specific backorder constraints. Holding costs are applied either to inventory position or on-hand inventory, and the backorder constraint is considered in terms of the total number of backorders per year or the average number of backorders at any point in time. Through the substitution of a new probability density function in place of the normal p.d.f., explicit expressions are determined for the economic order quantities and the reorder points. The resulting economic order quantities are independent of all backorder constraints. It is also concluded that under certain conditions, the minimization of ordering costs and inventory holding costs (applied to inventory position), subject to a backorder constraint, is equivalent in terms of reorder levels to minimization of the safety level dollar investment subject to the same backorder constraint.     

The many-product cargo loading problem

An algorithm, based upon dynamic programming, is developed for a class of fixed-cost cargo loading problems. The problems can be formulated as integer programming problems, but cannot be efficiently solved as such because of computational difficulties. The algorithm developed has proved to be very efficient in an actual operations research study involving over 500 different cargo items, more than 40 possible stops and several types of transportation vehicles. A numerical illustration is provided.     

The Argentine dilemma: The Southern cone vis-à-vis the “contradictory duality of world reality”

The world has been faced with a contradiction since the end of the Cold War. On the one hand, there are factors that have led to complex multi-interdepen-dency; on the other, there is a process of global disintegration caused by those very same factors. It is in this context that the Southern Cone of South America has revealed a remarkable inequality in its balance of military power. If Argentina is taken as the center of gravity of both the sub-regions in the area, the Mercado Comun del Sur (Mercosur) and the Austral Cone, it is difficult to find a solution to this imbalance because the regional structure is experiencing the same contradictions as the world itself. What is clear is that the solution depends much more on the policies adopted by Argentina than those of Chile or Brazil. To solve this dilemma, Argentina needs credibility - something that requires fundamental internal change and substantial external support.     

Economic impact and the notion of compensated procurement

The paper consists essentially of two parts. In the first part a linear economic impact model is presented whose structure is based on subcontracting flows. The structural coefficients are defined in terms of flows per area. The model is derived from two identities that are analogous to the income and expenditure identities of national income accounting. The parameters are prime contracts and when one or several of the prime contracts are changed, the model determines the impacts of such changes on the various regions that have been selected. The impacts can be combined with regional multipliers to derive changes in regional income and regional employment. Fragmentary data for this kind of model have been collected on a one-time basis by DOD in 1965 and some results based on the data are presented. The second part of the paper is concerned with normative economics. A scheme is suggested, called compensated procurement, that outlines how the Department of Defense might employ the impact model in a macroeconomic setting. The basic idea is that a stabilization fund be established to finance an array of potential projects which are contracted for to balance sudden shifts in defense demand. Only short-run stabilization is advocated.     

Reliability of a single unit with k spares in case of the hyper-exponential and the erlang failure distribution

In this paper formulas are derived for the reliability of a single unit to which identical spares in standby are allocated, with all of these units having a hyper-exponential or Erlang distributed lifetime. Two advantages are obtained by using these distributions. First, the general procedure for calculating the effect of redundancy is applicable, in contrast with most of the common life distributions, such as Weibull. Moreover, both distributions are suitable for matching to observed curves and practical data by varying the values of the parameters, covering together most of the cases of practical interest.     

A note on splitting the bump in an elimination factorization

This exposition presents a method for incorporating a technique known as “splitting the bump” within an elimination form reinversion algorithm. This procedure is designed to reduce fill-in during reinversion and should improve the efficiency of linear programming systems which already use the superior elimination form of the inverse.     

Optimal betting strategies for favorable games

We examine the problem of a gambler interested in maximizing the expected value of a convex utility function of his fortune after n plays of a game. We allow any probability distribution to rule the outcome of each play, and this distribution may change from play to play according to a Markov process. We present results regarding the existence of an optimal policy and its structural dependence on the gambler's fortune. The well-known results of Bellman and Kalaba for exponential and logarithmic utility functions and coin-tossing games are generalized. We also examine the situation of general stale spaces and show that the same structural results hold.