40 results
Search Results
2. The Traffic Assignment Problem for Multiclass-User Transportation Networks
- Author
-
Stella Dafermos
- Subjects
Truck ,Engineering ,Telephone network ,business.industry ,media_common.quotation_subject ,Transportation ,Flow network ,Traffic flow ,Advanced Traffic Management System ,Transport engineering ,Fuzzy transportation ,business ,Function (engineering) ,Assignment problem ,Civil and Structural Engineering ,Computer network ,media_common - Abstract
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.
- Published
- 1972
3. An Algorithm for the Quadratic Assignment Problem
- Author
-
Glenn W. Graves and Andrew B. Whinston
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Optimization problem ,Quadratic assignment problem ,Strategy and Management ,Cross-entropy method ,Management Science and Operations Research ,Assignment problem ,Algorithm ,Generalized assignment problem ,Weapon target assignment problem ,Combinatorial explosion ,Mathematics - Abstract
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.
- Published
- 1970
- Full Text
- View/download PDF
4. A Graph-Theoretic Approach to a Class of Integer-Programming Problems
- Author
-
J. F. Desler and S. L. Hakimi
- Subjects
Discrete mathematics ,3-dimensional matching ,Voltage graph ,Bipartite graph ,Graph (abstract data type) ,Management Science and Operations Research ,Integer programming ,Assignment problem ,Blossom algorithm ,Factor graph ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1969
5. On the personnel assignment problem
- Author
-
Gerhard Mensch
- Subjects
Mathematical optimization ,Information Systems and Management ,Operations research ,Computer science ,Stochastic modelling ,Strategy and Management ,Control (management) ,Management Science and Operations Research ,Assignment problem ,Standard deviation - Abstract
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.
- Published
- 1973
6. Recursive simplification of pole-assignment problem in multi-input systems†
- Author
-
M. R. Chidambara
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Control and Systems Engineering ,Multi input ,Order (ring theory) ,Assignment problem ,Generalized assignment problem ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1972
7. Heuristic Approach to Nonstandard Form Assignment Problems
- Author
-
J. A. Joseph
- Subjects
Range (mathematics) ,Mathematical optimization ,Missile ,Operations research ,Heuristic ,Frequency assignment ,Management Science and Operations Research ,Assignment problem ,Weapon target assignment problem ,Field (computer science) ,Computer Science Applications ,Communication channel ,Mathematics - Abstract
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.
- Published
- 1967
8. A Markov-Decision-Chain Approach to a Stochastic Assignment Problem
- Author
-
S. Christian Albright
- Subjects
Mathematical optimization ,Markov chain ,Operations research ,Computer science ,media_common.quotation_subject ,Management Science and Operations Research ,Computer Science Applications ,Idle ,Value (economics) ,Quality (business) ,Set (psychology) ,Queue ,Assignment problem ,Decision analysis ,media_common - Abstract
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.
- Published
- 1974
9. A treatise on traffic assignment
- Author
-
Komei Sasaki
- Subjects
Empirical research ,Operations research ,Computer science ,General Earth and Planetary Sciences ,Statistical model ,Base (topology) ,Assignment problem ,General Environmental Science - Abstract
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.
- Published
- 1974
10. Evaluation of alternative growth patterns in urban systems
- Author
-
John W. Dickey, John F. Brotchie, P. A. Ahern, and Ron Sharpe
- Subjects
education.field_of_study ,General Computer Science ,Linear programming ,Operations research ,Computer science ,Population ,Management Science and Operations Research ,Set (abstract data type) ,Work (electrical) ,Modeling and Simulation ,Urban system ,education ,Assignment problem ,Simulation - Abstract
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.
- Published
- 1974
11. The Quadratic Assignment Problem
- Author
-
Eugene L. Lawler
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Quadratic assignment problem ,Strategy and Management ,Quartic function ,Quadratic programming ,Management Science and Operations Research ,Assignment problem ,Upper and lower bounds ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
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.
- Published
- 1963
- Full Text
- View/download PDF
12. An Algorithm for Assigning Uses to Sources in a Special Class of Transportation Problems
- Author
-
Gerald L. Thompson and V. Srinivasan
- Subjects
Mathematical optimization ,Fuzzy transportation ,Mathematical model ,Generalization ,Extension (predicate logic) ,Transportation theory ,Management Science and Operations Research ,Special class ,Assignment problem ,Algorithm ,Generalized assignment problem ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1973
13. Asymptotic Optimal Policies for the Stochastic Sequential Assignment Problem
- Author
-
Chris Albright and Cyrus Derman
- Subjects
Mathematical optimization ,Distribution function ,Strategy and Management ,Scheduling (production processes) ,Limiting ,Management Science and Operations Research ,Asymptotic expansion ,Assignment problem ,Random variable ,Generalized assignment problem ,Mathematics - Abstract
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.
- Published
- 1972
14. The truck assignment problem
- Author
-
Wlodzimierz Szwarc
- Subjects
Truck ,Flexibility (engineering) ,Schedule ,Operations research ,Computer science ,Cement factory ,General Engineering ,Factory (object-oriented programming) ,Assignment problem - Abstract
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.
- Published
- 1967
15. Technical Note—Bounds for the Travelling-Salesman Problem
- Author
-
Nicos Christofides
- Subjects
Mathematical optimization ,Computation ,Convergence (routing) ,Technical note ,Sample (statistics) ,Management Science and Operations Research ,Travelling salesman problem ,Assignment problem ,Upper and lower bounds ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1972
16. The minimal cost maximum matching of a graph
- Author
-
Claudio Roveda and Adriano O. De Maio
- Subjects
Factor-critical graph ,Mathematical optimization ,Matching (graph theory) ,General Mathematics ,Maximum cut ,3-dimensional matching ,Management Science and Operations Research ,Strength of a graph ,Assignment problem ,Software ,Edge cover ,Blossom algorithm ,Mathematics - Abstract
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.
- Published
- 1971
17. The Labor Assignment Decision and Application of Work Flow Structure Information
- Author
-
William L. Berry and William K. Holstein
- Subjects
Structure (mathematical logic) ,Work (electrical) ,Operations research ,Computer science ,Job shop ,Strategy and Management ,Aggregate (data warehouse) ,Production (economics) ,Work flow ,Flow shop scheduling ,Management Science and Operations Research ,Assignment problem - Abstract
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.
- Published
- 1972
- Full Text
- View/download PDF
18. The Hungarian method for the assignment problem
- Author
-
Harold W. Kuhn
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Theoretical computer science ,Linear programming ,ComputingMilieux_PERSONALCOMPUTING ,General Engineering ,TheoryofComputation_GENERAL ,Duality (optimization) ,Hungarian algorithm ,Combinatorial optimization ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
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.
- Published
- 1955
19. Optimization of Reduced Dependencies for Synchronous Sequential Machines
- Author
-
Edward J. Smith and Peter Weiner
- Subjects
Sequential logic ,Computer science ,Sense (electronics) ,Theoretical Computer Science ,Set (abstract data type) ,Computational Theory and Mathematics ,Hardware and Architecture ,Figure of merit ,State (computer science) ,Network synthesis filters ,IBM ,Algorithm ,Assignment problem ,Software - Abstract
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.
- Published
- 1967
20. Optimality Properties of a Special Assignment Problem
- Author
-
Roger Wets and S. C. Parikh
- Subjects
Linear bottleneck assignment problem ,Discrete mathematics ,Matrix (mathematics) ,Mathematical optimization ,Linear programming ,Quadratic assignment problem ,Management Science and Operations Research ,Assignment problem ,Matrix similarity ,Generalized assignment problem ,Weapon target assignment problem ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1964
21. A Shuttle Car Assignment Problem in the Mining Industry
- Author
-
Gary H. Reynolds
- Subjects
Computer science ,business.industry ,Strategy and Management ,Industrial production ,Reliability (computer networking) ,ComputerApplications_COMPUTERSINOTHERSYSTEMS ,Management Science and Operations Research ,complex mixtures ,Scheduling (computing) ,Transport engineering ,Mining industry ,Operations management ,Coal ,business ,Assignment problem ,human activities - Abstract
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.
- Published
- 1971
- Full Text
- View/download PDF
22. On some techniques useful for solution of transportation network problems
- Author
-
N. Tomizawa
- Subjects
Reduction (complexity) ,Mathematical optimization ,Computer Networks and Communications ,Hardware and Architecture ,Efficient algorithm ,Flow network ,Upper and lower bounds ,Algorithm ,Assignment problem ,Dijkstra's algorithm ,Software ,Information Systems ,Mathematics - Abstract
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.
- Published
- 1971
23. The Choice Behavior of Transportation Mode
- Author
-
Komei Sasaki
- Subjects
Mathematical optimization ,Empirical research ,Basis (linear algebra) ,Demand curve ,Computer science ,Mode (statistics) ,General Social Sciences ,Operations management ,Statistical model ,Base (topology) ,Assignment problem ,General Environmental Science - Abstract
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.
- Published
- 1972
24. International Capital Mobility and the Assignment Problem
- Author
-
Jay H. Levin
- Subjects
Microeconomics ,Economics and Econometrics ,Labour economics ,International capital ,Economics ,Assignment problem - Published
- 1972
25. On the Connection Assignment Problem of Diagnosable Systems
- Author
-
Gernot Metze, Franco P. Preparata, and Robert T. Chien
- Subjects
Model theory ,Engineering ,business.industry ,Real-time computing ,Logic testing ,System testing ,Hardware_PERFORMANCEANDRELIABILITY ,Application software ,computer.software_genre ,Theoretical Computer Science ,Scheduling (computing) ,Computational Theory and Mathematics ,Hardware and Architecture ,Graphics ,business ,human activities ,Assignment problem ,Automatic testing ,Algorithm ,computer ,Software - Abstract
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.
- Published
- 1967
26. On the State Assignment Problem for Sequential Machines. I
- Author
-
Juris Hartmanis and Richard Edwin Stearns
- Subjects
Mathematical optimization ,Selection (relational algebra) ,Property (programming) ,Substitution (logic) ,Theoretical Computer Science ,Set (abstract data type) ,Variable (computer science) ,Computational Theory and Mathematics ,Hardware and Architecture ,Partition (number theory) ,State (computer science) ,Assignment problem ,Software ,Mathematics - Abstract
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.
- Published
- 1961
27. A further procedure for ordering an input-output matrix: some empirical evidence
- Author
-
Jean-Marie Blin
- Subjects
Linear bottleneck assignment problem ,Economics and Econometrics ,Class (set theory) ,Quadratic assignment problem ,Computation ,Statistics ,Economics ,Applied mathematics ,Empirical evidence ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem - Abstract
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.
- Published
- 1973
28. A Sequential Stochastic Assignment Problem
- Author
-
Sheldon M. Ross, Gerald J. Lieberman, and Cyrus Derman
- Subjects
Combinatorics ,Stochastic process ,Strategy and Management ,Kleene's recursion theorem ,Order (group theory) ,Interval (mathematics) ,Management Science and Operations Research ,Real line ,Random variable ,Assignment problem ,Generalized assignment problem ,Mathematics - Abstract
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).
- Published
- 1972
29. A Target-Assignment Problem
- Author
-
Alan S. Manne
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Nonlinear system ,Cutting stock problem ,Probabilistic logic ,Linear programming formulation ,Management Science and Operations Research ,Assignment problem ,Weapon target assignment problem ,Generalized assignment problem ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1958
30. Two algorithms for a plant-storehouse location problem
- Author
-
C. Roveda and R. Schmid
- Subjects
Mathematical optimization ,Branch and bound ,Quadratic assignment problem ,General Mathematics ,Management Science and Operations Research ,Dynamic programming ,1-center problem ,Decomposition (computer science) ,Algorithm ,Assignment problem ,Software ,Weapon target assignment problem ,Generalized assignment problem ,Mathematics - Abstract
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.
- Published
- 1971
31. On Assembly Line Balancing
- Author
-
Morton Klein
- Subjects
Order of operations ,Mathematical optimization ,Linear programming ,Simple (abstract algebra) ,Cutting stock problem ,Computer science ,Management Science and Operations Research ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,Computer Science Applications ,Scheduling (computing) - Abstract
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.
- Published
- 1963
32. One-Dimensional Space Allocation: An Ordering Algorithm
- Author
-
Donald M. Simmons
- Subjects
Mathematical optimization ,Line segment ,Dimension (vector space) ,Simple (abstract algebra) ,One-dimensional space ,Management Science and Operations Research ,Floor plan ,Type (model theory) ,Linear combination ,Assignment problem ,Algorithm ,Computer Science Applications ,Mathematics - Abstract
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.
- Published
- 1969
33. An extension of the (szwarc) truck assignment problem
- Author
-
David H. Marks, Jon C. Liebman, and M. Bellmore
- Subjects
Mathematical optimization ,business.industry ,Computer science ,Computer data storage ,General Engineering ,Transportation theory ,Routing (electronic design automation) ,business ,Flow network ,Assignment problem ,Computer memory ,Multi-commodity flow problem ,Transshipment - Abstract
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/
- Published
- 1972
34. Assignment Problem Based on Ordinal Preferences
- Author
-
Peter Gärdenfors
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Augmented assignment ,Optimization problem ,Quadratic assignment problem ,Strategy and Management ,Cross-entropy method ,Management Science and Operations Research ,Assignment problem ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
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.
- Published
- 1973
- Full Text
- View/download PDF
35. The Equivalence of Integer Programs to Constrained Recursive Systems
- Author
-
Patanjali S. Nanda
- Subjects
Discrete mathematics ,Strategy and Management ,Computer Science::Programming Languages ,Management Science and Operations Research ,Equivalence (formal languages) ,Extreme point ,Travelling salesman problem ,Assignment problem ,Generalized assignment problem ,Mathematics - Abstract
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.
- Published
- 1973
- Full Text
- View/download PDF
36. The minimal cost maximum matching of a graph (supplementary remarks)
- Author
-
Heiner Müller-Merbach
- Subjects
Linear bottleneck assignment problem ,Mathematical optimization ,Property (philosophy) ,Matching (graph theory) ,General Mathematics ,3-dimensional matching ,Graph (abstract data type) ,Management Science and Operations Research ,Assignment problem ,Software ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
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.
- Published
- 1971
37. A MISSILE TARGETING PROBLEM
- Author
-
M. D. MacLaren and David W Walkup
- Subjects
Mathematical optimization ,Matrix (mathematics) ,Engineering ,Missile ,Operations research ,business.industry ,Monte Carlo method ,Computer programming ,Value (computer science) ,Function (mathematics) ,business ,Assignment problem ,Weapon target assignment problem - Abstract
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.
- Published
- 1964
38. SOLUTION TECHNIQUES FOR THE TRAFFIC ASSIGNMENT PROBLEM
- Author
-
Stephen P Bradley
- Subjects
Matrix (mathematics) ,Mathematical optimization ,Linear programming ,Node (networking) ,Decomposition (computer science) ,Incidence matrix ,Assignment problem ,Generalized assignment problem ,Multi-commodity flow problem ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
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.
- Published
- 1965
39. Describing Industrial Processes with Interference and Approximating Their Steady-State Behaviour
- Author
-
R. A. Cuninghame-Green
- Subjects
Marketing ,Operations research ,Computer science ,Strategy and Management ,Management Science and Operations Research ,Management Information Systems ,Matrix (mathematics) ,Applied mathematics ,Arithmetic function ,Multiplication ,Algebraic number ,Constant (mathematics) ,Assignment problem ,Eigenvalues and eigenvectors - Abstract
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.
- Published
- 1962
40. The Quadratic Assignment Problem: A Note
- Author
-
Dennis Heffley
- Subjects
Linear bottleneck assignment problem ,Economics and Econometrics ,Mathematical optimization ,Augmented assignment ,Linear programming ,Quadratic assignment problem ,Quadratic programming ,Assignment problem ,Mathematical economics ,Generalized assignment problem ,Weapon target assignment problem ,Mathematics - Abstract
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
- Published
- 1972
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.