Search

In a recent paper a traffic assignment model has been constructed in which the cost on a link may depend not only on its load, but also on the loads on other links of the network. In this paper it is shown that this model is also capable of handling the case of several classes of users in the same transportation network each of which has an individual cost function and, at the same time, contributes to its own and other classes' cost functions in an individual way. Typical applications arise not only in street networks where vehicles of different types share the same roads (e.g., trucks and passenger cars) but also in other types of transportation networks (e.g., telephone networks). An algorithm is constructed for finding the system-optimizing flow pattern for such a multiclass-user transportation network.

The paper presents a new approach to solving a class of combinatorial economic allocation problems. One member of this class is known as the quadratic assignment problem. Besides presenting an algorithm to solve this problem, we will discuss in general terms the techniques for treating combinatorial problems. A novel feature of the paper is the development of the statistical properties of the criterion function. These statistical properties are used in conjunction with a general enumerative procedure to form the main parts of the algorithm. Using the idea of confidence level enumeration, an extension of the algorithm is proposed which should allow for the effective treatment of large scale combinatorial problems. Finally we present some computational results in order to illustrate the effectiveness of the general approach.

This paper presents an efficient algorithm for finding a minimum-weight generalized matching in a weighted bipartite graph. Computational evidence is given that indicates that the time required to find a least-cost assignment of n jobs to n workers goes roughly as n2 for 10 ≦ n ≦ 50. It is shown that this algorithm can be used to solve effectively the well known transportation problem of integer programming where the objective function is convex-separable. Finally, the paper gives an algorithm that applies the same concept to a graph that is not necessarily bipartite.

Recent papers have developed methods for personnel assignment under risk of failure. In this paper, a two-parameter model is given. It uses both mean and standard deviation in the stochastic model to bring the risk of failure under control.

It is shown in this paper that the pole-assignment problem for a linear time-invariant system of order (n) having (p) number of inputs can be solved by seeking the solution of the same problem for a similar system of order (n−p−r) [where 1≤r≤p] having (r 1) [with r1≤r] number of inputs. This operation can be repeated to simplify the pole-assignment problem in a recursive manner. Another contribution of this paper is that it shows that the asymptotic state-estimator problem for a linear time-invariant system of order (n) having (q) number of outputs can be solved by using the solution to the pole assignment problem of a similar system of order (n−q) having (q1 ) [with q1≤q] number of inputs.

Many problems of the practicing operations analyst do not fit the standard forms of analytic OR procedures and do not lend themselves to precise optimization methods. The voracious appetite of the computer demands numerical algorithms in order to give answers. Very often an optimum is not absolutely essential to management, as long as the answer is efficient or superior to guesswork. So heuristic approaches are adapted to the problem. This paper presents a heuristic approach to a nonstandard, practical assignment problem. It concerns a problem that the analyst had to solve “in the field” at Cape Canaveral (now Cape Kennedy) wherein 74 telemetry channels for 19 missiles had to be assigned to 28 available frequency bands. A conflict for a channel occurs if (a) time for use of the range by the missile channels is demanded and (b) another channel on another missile has the same frequency assignment and also wishes the same time. A conflict means one or more missiles must be denied time on the range, which causes costly delay. It is desirable to assign channels to frequencies (which is done at the time the missile is designed) so as to minimize the total expected amount of conflict (or cost of conflict). This paper shows a general, heuristic (not-necessarily optimum) procedure for handling typical, nonstandard assignment problems and gives details of the Cape Kennedy application. This is an example of what can happen “in the field” when standard mathematical forms are not available.

This paper discusses a problem where jobs of random quality, or importance, arrive at random times and must be done by one of a fixed set of men on hand. The men can all complete any job in an exponential amount of time, with mean l/u, but the men are of different known qualities. Once a man finishes a job he again becomes available to do future jobs. If a man of quality p is assigned to do a job whose value is observed to be x, a reward r(p,x) is received. Also a cost of c(p) is incurred per unit time that a man of quality p is kept idle. The decision maker must observe the values of the incoming jobs and assign them to available men so as to maximize expected reward per unit time. The problem is set into the framework of a G/M/n queue with a possibly limited waiting room, and the optimization is done by techniques of Markov decision analysis.

So far some economists have studied the pattern of traffic assignment theoretically and empirically. But it seems that there are few proper stochastic or statistical models for analyzing the traffic assignment problem on the base of an economic theory. The purpose of this paper is to formulate the economic behavior of traffic assignment and to derive some statistical models which seem useful for empirical study or the prediction of the future course.

The paper describes the formulation of the general planning model, TOPAZ (Technique for the Optimum Placement of Activities into Zones) and its application to evaluating and optimizing alternative growth patterns in urban systems. TOPAZ identifies an urban system as a set of interacting activities to be allocated to a set of zones to maximize an objective of overall benefit less cost of interaction between activities together with the benefit less cost of establishment of the activities, over a set of time periods. The model takes the form of a non-linear assignment problem with linear constraints, and is solved using iterative linear programming. The model is illustrated by application at a macro level to the evaluation of alternative corridor growth patterns for the city of Melbourne (population 2.4 million) over three time periods, 1970–80–90–2000. Two activities are involved, residential and employment activity, and the interactions consist of work, residential, industrial and commercial trips. The city is divided into forty zones.

This paper presents a formulation of the quadratic assignment problem, of which the Koopmans-Beckmann formulation is a special case. Various applications for the formulation are discussed. The equivalence of the problem to a linear assignment problem with certain additional constraints is demonstrated. A method for calculating a lower bound on the cost function is presented, and this forms the basis for an algorithm to determine optimal solutions. Further generalizations to cubic, quartic, N-adic problems are considered.

This paper considers a special class of transportation problems in which the needs of each user are to be supplied entirely by one of the available sources. We first show that an optimum solution to this special transportation problem is a basic feasible solution to a slightly different standard transportation problem. A branch-and-bound solution procedure for finding the desired solution to the latter is then presented and illustrated with an example. We then consider an extension of this problem by allowing the possibility of increasing (at a cost) the source capacities. The problem formulation is shown to provide a generalization to the well known assignment problem. The solution procedure appears to be relatively more efficient when the number of uses greatly exceeds the number of sources.

Certain sets of numbers {ain}, i = 0,…, n, n = 1, 2,…, are known characterize an optimal sequential assignment policy. In this paper the limiting behavior as n → ∞ of the ain's is studied.

Let us consider the following problem: A group of cement factories produces several types of cement, but each factory produces only one type. There is also a group of purchasers and each purchaser may need several types of cement. The amounts supplied and the demands are assumed to be known for each cement factory and each purchaser. Each cement factory has several trucks, but there is only one dispatcher for ail of the trucks from all of the factories. It is assumed that the entire lcad of each truck is for one purchaser only. A truck begins its workday by leaving its base depot loaded and ends its day by returning to it empty. During the day it may be required to transport cement from any of the cement factories. The distances from various factories to individual purchasers are known. The problem to be solved is that of finding a truck schedule such that cement in the needed quantities is delivered daily to the individual purchasers and in such a manner that the total truck-kilometers traveled will be as small as possible. This paper presents the method of solution, though the assumption of an 8-hour workday may not be met. On the other hand, there are methods developed for effecting a variety of cyclic routings which can be used to lend considerable flexibility to the schedules.

This paper concerns finding a tight lower bound to the travelling-salesman problem, with the hope that all the different branch-and-bound algorithms for this problem can benefit from it. The bound is calculated by an iterative procedure with guaranteed convergence and is shown to require a computation time only about 9 per cent greater than the time required to solve an equivalent assignment problem. This new bound was tested on 14 sample problems and, on the average, found to be only 4.7 per cent below the optimum for symmetrical, and 3.8 per cent below the optimum for asymmetrical problems.

This paper deals with the problem of finding the maximum matching of a weighted graph, having the minimum cost. This problem is solved via a branch and bound algorithm, derived directly fromLand andDoig's technique. The linear programming problem associated with each step of the procedure is solved through a primal-dual algorithm.

The movement of workers among machines is a tactic often employed by job shop managers to break bottlenecks and smooth the flow of work. Despite its common occurrence in industrial practice, the problem has only recently received attention in the management science literature. The purposes of this paper are (1) to discuss the nature of the labor assignment problem in job shops, and (2) to suggest a procedure for making labor assignments at the time of actual production. The significant features of the specific rules suggested are that they use aggregate information on work flow patterns in the shop, and that they make fewer labor transfers than other rules which have been suggested.

This paper has always been one of my favorite “children,” combining as it does elements of the duality of linear programming and combinatorial tools from graph theory. It may be of some interest to tell the story of its origin.

The purpose of this paper is to describe an algorithmic ``solution'' to the assignment problem of synchronous sequential machines. The figure of merit used provides a mathematical evaluation of the reduced dependencies that may exist in the set of logic equations. If desired, the algorithm can assign the input, state, and output symbols of a given machine so as to ``minimize'' the total logic, i.e., reduced dependencies of both the state and output logic on state and input variables are optimized. The method is nonenumerative in the sense that the first assignmnent found is optimal. A restricted version of the algorithm has been programmed for an IBM 7094 computer.

In this paper, it is shown that if the cost matrix of an assignment problem has the following property cij = |j − i| then any basic feasible solution is optimal if and only if its unit components belong to two well-defined symmetric regions. The matrix with above mentioned property is called the “reordering matrix,” because it arose for the first time in the reordering of nodes of a critical path and other acyclic network problems. One deals with similar matrices in some problems related to order statistics.

Shuttle cars form a part of the standard equipment employed by the mining industry in the transportation of coal when using the room-and-piller method for extracting coal from underground seams. These cars are subject to frequent failure, so the problem of assigning shuttle cars to sections of the mine is considered in this paper, with the objective of maximizing expected output. A particularly simple solution is found that could be used readily by any mine foreman.

This paper presents an efficient algorithm for solving transportation problems. The improvement over the existing algorithms of the “primal-dual” type [3], [5] consists in modifying the “potential-raising” stages of the solution process in such a way that negative-cost arcs are removed so that the Dijkstra's algorithm may be applied. Especially, the algorithm requires at most n3 additions and comparisons when applied to an n-by-n assignment problem, as compared with the theoretical upper bound proportional to n4 for the number of such operations required by currently available methods. Furthermore, auxiliary techniques of simplifying the original network by means of “reduction” and “induction” are also introduced as useful tools to treat large-scale problems and specially-structured problems with.

So far some economists have studied the pattern of traffic assignment theoretically and empirically. But it seems that there are few proper stochastic or statistical models for analyzing the traffic assignment problem on the base of an economic theory. The purpose of this paper is to formulate the economic behavior of traffic assignment and to derive some statistical models which seem useful for empirical study or the prediction of the future course.Three diffirent models for traffic assignment were developed. The first is similar to Quandt-Baumol model (1966) by which they analyzed the social traffic demand in California. In that model it is suggested that individual will choose the transportation modes so as to minimize his loss prescribed by traffic time and cost of each mode. However in deriving the social demand function from individual's one, we have had no consistent procedure concerning aggregation.The second model was developed by a stochastic approach to overcome the difficulty in the aspect of aggregation of the first model. The traffic time and cost are main factors to assign the modes in that model too.The thrid model was proposed for prediction in the future course so that model always satisfys the condition that the sum of predicted values of each assignment ratio be strictly unity.Finally some empirical applications on the basis of the second and thrid model were attempted. It seems that such applcations were rather succesful.

This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u 1 , u 2 , . . . , u n , where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of a given arrangement of testing links (connection assignment) each unit of the system tests a subset of units, and a proper diagnosis can be arrived at for any diagnosable fault pattern. Methods for optimal assignments are given for instantaneous and sequential diagnosis procedures.

In this paper, the problem of determining economical state assignments for finite-state sequential machines is studied. The fundamental idea in this study is to find methods for selection of these assignments in which each binary variable describing the new state depends on as few variables of the old state as possible. In general, these variable assignments in which the dependence is reduced yield more economical implementation for the sequential machine than the assignments in which the dependence is not reduced. The main tool used in this study is the partition with the substitution property on the set of states of a sequential machine. It is shown that for a sequential machine the existence of assignments with reduced dependence is very closely connected with the existence of partitions with the substitution property on the set of states of the machine. It is shown how to determine these partitions for a given sequential machine and how they can be used to obtain assignments with reduced dependence.

In a recent paper Ghosh and Sarkar [5] have developed a model of input-output systems as spatial configurations. Roy has proposed a more efficient solution method; but computation time still increases factorially which rules out its use for large matrices. [15] This note shows that the problem they have formulated belongs to a class of discrete programming problems known as placement or assignment problems. Several natural extensions are briefly discussed. More importantly, an efficient algorithm for the quadratic assignment problem is used to compute the optimal ordering of five comparable input-output matrices (US, Norway, Japan, Italy, India). These preliminary empirical results do show rather stable assignment patterns for the industries; and certain clusters of industries are shown to emerge as hypothesized by Ghosh and Sarkar.

Suppose there are n men available to perform n jobs. The n jobs occur in sequential order with the value of each job being a random variable X. Associated with each man is a probability p. If a “p” man is assigned to an “X = x” job, the (expected) reward is assumed to be given by px. After a man is assigned to a job, he is unavailable for future assignments. The paper is concerned with the optimal assignment of the n men to the n jobs, so as to maximize the total expected reward. The optimal policy is characterized, and a recursive equation is presented for obtaining the necessary constants of this optimal policy. In particular, if p1 ≦ p2 ≦ ⋯ ≦ pn the optimal choice in the initial stage of an n stage assignment problem is to use pi if x falls into an ith nonoverlapping interval comprising the real line. These intervals depend on n and the CDF of X, but are independent of the p's. The optimal policy is also presented for the generalized assignment problem, i.e., the assignment problem where the (expected) reward if a “p” man is assigned to an “x” job is given by a function r(p, x).

This paper is concerned with a target assignment model of a probabilistic and nonlinear nature, but nevertheless one which is closely related to the “personnel-assignment” problem. It is shown here that, despite the apparent nonlinearities, it is possible to devise a linear programming formulation that will ordinarily provide a close approximation to the original problem.

This paper considers the following assignment problem. There are some groups of plants, each group producing a different commodity. There are some consumption areas, each containing a number of storehouses and wanting a certain amount of all the commodities. The problem consists of finding the assignment of storehouses to plants which minimizes the overall cost, consisting of fixed charges associated to all storehouses and plants, and of transportation costs. For the solution of this problem, which can be called a plant-storehouse location problem, two algorithms are presented. The first algorithm makes use of a branch and bound technique; the second is based on a decomposition technique, which follows directly from the Dynamic Programming.

This paper gives a simple method for finding an optimal assignment of operations to work stations when the order of operations is specified. It is shown that the problem with a specific ordering can be formulated as an assignment problem or as a shortest-route problem for which an inspection-type solution is available. The more general problem, when it is possible to enumerate all feasible orderings of operations, can then be handled by repeating the required calculations for all such orderings.

The space-allocation problem arises when an architect tries to arrange rooms of fixed area but unspecified shape on a floor plan in such a way as to minimize a given linear combination of the distances between all pairs of rooms. In one dimension, this is the problem of ordering line segments along a simple axis or rooms along one side of a corridor. This paper devises an efficient branch-and-bound algorithm for finding the optimal ordering, and shows that the algorithm can solve one special type of facilities-to-locations assignment problem. Space allocation in two dimensions is also discussed briefly.

IN THIS JOURNAL IN 1967, SZWARE PRESENTED AN ALGORITHM FOR THE OPTIMAL ROUTING OF A COMMON VEHICLE FLEET BETWEEN M SOURCES AND N SINKS WITH P DIFFERENT TYPES OF COMMODITIES. THE MAIN PREMISE OF THE FORMULATION IS THAT A TRUCK MAY CARRY ONLY ONE COMMODITY AT A TIME AND MUST DELIVER THE ENTIRE LOAD TO ONE DEMAND AREA. THIS ELIMINATES THE PROBLEM OF ROUTING VEHICLES BETWEEN SOURCES OR BETWEEN SINKS AND LIMITS THE PROBLEM TO THE ROUTING OF LOADED TRUCKS BETWEEN SOURCES AND SINKS AND EMPTY TRUCKS MAKING THE RETURN TRIP. SZWARE CONSIDERED ONLY THE TRANSPORTATION ASPECT OF THE PROBLEM (I.E., NO INTERMEDIATE POINTS) AND PRESENTED A VERY EFFICIENT ALGORITHM FOR SOLUTION OF THE CASE HE DESCRIBED. IF THE TOTAL SUPPLY IS GREATER THAN THE TOTAL DEMAND, SZWARE SHOWS THAT THE PROBLEM IS EQUIVALENT TO A (MP + N) BY (NP + M) HITCHCOCK TRANSPORTATION PROBLEM. DIGITAL COMPUTER CODES FOR THIS ALGORITHM REQUIRE RAPID ACCESS STORAGE FOR A MATRIX OF SIZE (MP + N) BY (NP + M); THERFORE, COMPUTER STORAGE REQUIRED GROWS PROPORTIONALLY TO P SQUARED. THIS PAPER OFFERS AN EXTENSION OF HIS WORK TO A MORE GENERAL FORM: A TRANSSHIPMENT NETWORK WITH CAPACITY CONSTRAINTS ON ALL ARCS AND FACILITIES. THE PROBLEM IS SHOWN TO BE SOLVABLE DIRECTLY BY FULKERSON'S OUT-OF-KILTER ALGORITHM. DIGITAL COMPUTER CODES FOR THIS FORMULATION REQUIRE RAPID ACCESS STORAGE PROPORTIONAL TO P INSTEAD OF P SQUARED. COMPUTATIONAL RESULTS INDICATE THAT, IN ADDITION TO HANDLING THE EXTENSIONS, THE OUT-OF-KILTER ALGORITHM IS MORE EFFICIENT IN THE SOLUTION OF THE ORIGINAL PROBLEM WHEN THERE IS A MODERATE NUMBER OF COMMODITIES AND A COMPUTER OF LIMITED STORAGE CAPACITY. /AUTHOR/

The assignment problem, a well-known variant of which is the problem of optimal staff distribution, has formerly been treated as a problem of linear optimization starting with numerical evaluations of the assignments. In this paper the assignment problem is regarded as a problem of social choice, where preference orders are used as the sole initial information. A formal definition of an assignment function is given and various conditions for such functions are suggested. Some conditions are found to be incompatible. Several reasonable assignment functions are examined with respect to which conditions they fulfil. Finally, some problems, related to the assignment problem, are informally discussed.

It has been established that integer programs with integral, recursive constraint matrices have integral extreme points for integral, nonnegative requirement vectors. In this paper, it is first shown that the assignment problem can be transformed to such a program, but with upper bounds on some variables. This equivalent program leads to additional results for solving the assignment problem. Algorithms are then delineated to transform matching, covering and travelling salesman problems to equivalent recursive programs of the aforementioned type, but with bounds on some variables. These results are extended to programs with special structure in their constraint matrices.

In addition to the preceding paper, it will be shown that (1) the matching problem is closely related to the linear assignment problem and how (2) this property can be taken advantage of for solving the matching problem.

The following missile assignment problem is considered. Missiles are to be assigned to targets in two distinct steps. First, each missile is programmed so that it can be fired at any one of a small number of targets, the number of targets being the missile capability. The programming of the missiles is represented by a qualification matrix Q. Second, if battle occurs, all missiles are to be assigned to targets and launched. Each missile must be assigned to a target for which it is programmed. It is assumed that only a random subset X of the missiles will actually be available for battle, and so the assignment must be made for a reduced qualification matrix Q(X). The questions considered are 'what is an optimal assignment given the reduced qualification matrix Q(X).,' and 'what can be expected from this assignment.' Use of a damage function is proposed. An optimal assignment is one which maximizes the value of the damage function. The damage function may be chosen to represent a wide variety of optimization requirements. The main part of the paper describes Monte Carlo procedures for estimating the expected damage and the probability that the damage will be at least c for any number c.

The paper investigates the application of some large scale solution techniques to the so called traffic assignment problem, or multicommodity flow problem. As this is a network problem, there are two equivalent formulations. The first is based on the node-arc incidence matrix and is the usual approach. The second is based on an arc-chain matrix and the formulation is an extension of Ford and Fulkerson's multi-commodity work. Decomposition techniques are applied to the first formulation and a minimum chain network approach applied to the second. Then an extension of the arc-chain formulation shows it is equivalent to decomposition theory being applied to a slightly different node- arc formulation.

One very natural way of describing industrial processes with interference gives rise to particularly unwieldy mathematical expressions; but by a change of language, these expressions can be simply handled by the familiar notation of matrix algebra-where, however, addition and multiplication do not have their usual arithmetical meanings. This line of attack promises to produce a useful machinery for the analysis of systems of interacting processes, but first all the usual algebraic questions must be answered-e.g. the question of evaluating the eigenvalues and eigenvectors of a matrix in the new notation. This problem is equivalent to that of determining the steady states of a system of interacting processes, assuming constant activity times. This paper shows that the eigenvalue of a general matrix A can be determined explicitly in terms of A, as can the eigenvector in a particular set of cases. The general eigenvector and eigenvalue computation problem can be simplified into a dual form closely analogous to a formulation of the Assignment Problem by H. W. Kuhn.

Results of the Koopmans-Beckmann (K-B) analysis of the quadratic assignment problem [3] have perplexed many location theorists. K-B hold that indivisibilities of plant, in the presence of minimal interaction between spatially separated plants (namely, the shipment of intermediate goods at positive transportation rates), preclude the existence of a system of rents which will sustain an integral assignment, optimal or otherwise [3, p. 69]. Earlier in their paper K-B show that a sustaining price system does exist when the transportation of intermediate products is excluded; however, it is the presence of such interaction that leads to the more interesting quadratic assignment problem and the pessimistic conclusion reported above. The authors first present the quadratic assignment problem in a "permutation search" format, and then construct an equivalent linear programming problem which allows fractional assignments to be optimal without forfeiting any integral (one whole plant to each location) solutions that might exist