639 results
Search Results
52. Some Properties of Generalized Concave Functions.
- Author
-
Thompson Jr., W. A. and Parke, Darrel W.
- Subjects
CONCAVE functions ,REAL variables ,MATHEMATICAL programming ,COMPLEX variables ,ALGORITHMS ,FUNCTIONAL equations ,MATHEMATICAL optimization ,OPERATIONS research - Abstract
This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both ‘generalized concave’ and ‘generalized convex’ is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
53. DISCOUNTED MARKOV PROGRAMMING IN A PERIODIC PROCESS.
- Author
-
Riis, Jens Ove
- Subjects
MARKOV processes ,PROBABILITY theory ,ALGORITHMS ,MATHEMATICAL programming ,ITERATIVE methods (Mathematics) - Abstract
This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of R. A. HOWARD's policy-iteration technique for stationary Markov processes. A numerical example is given in which the developed iteration algorithm is demonstrated. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
54. CHANCE CONSTRAINED PROGRAMMING WITH JOINT CONSTRAINTS.
- Author
-
Miller, Bruce L. and Wagner, Harvey M.
- Subjects
LINEAR programming ,DYNAMIC programming ,MATHEMATICAL programming ,LOGARITHMIC functions ,NONLINEAR programming ,ALGORITHMS ,OPERATIONS research - Abstract
This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-hand side constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the `generalized linear programming' method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
55. DISCOUNTED MARKOV PROGRAMMING IN A PERIODIC PROCESS.
- Author
-
Riis, Jens Ove
- Subjects
MARKOV processes ,ALGORITHMS ,STOCHASTIC processes ,ITERATIVE methods (Mathematics) ,PROBABILITY theory ,OPERATIONS research - Abstract
This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of B. A. HOWARD'S policy-iteration technique for stationary Markov processes, A numerical example is given in which the developed iteration algorithm is demonstrated. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
56. THE MULTI-INDEX PROBLEM.
- Author
-
Haley, K. B.
- Subjects
TRANSPORTATION problems (Programming) ,TRANSPORTATION ,ALGORITHMS ,PROBLEM solving ,LINEAR programming ,MATHEMATICAL inequalities ,SIMPLEXES (Mathematics) ,OPERATIONS research ,EQUATIONS - Abstract
The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]
- Published
- 1963
- Full Text
- View/download PDF
57. A Model for Masking Rotational Latency by Dynamic Disk Allocation.
- Author
-
Gold, D.E., Kuck, D.J., and Weissman, C.
- Subjects
ALGORITHMS ,COMPUTER systems - Abstract
Features the background and algorithms for masking the rotational latency of a disk or drum. Discussion of the anticipatory input and output of data to buffer and primary memories for a monoprogrammed computer system; Presentation of a basic permutation algorithm.
- Published
- 1974
- Full Text
- View/download PDF
58. Efficient Implementation of a Variable Projection Algorithm for Nonlinear Least Squares Problems.
- Author
-
Krogh, Fred T. and Willoughby, R. A.
- Subjects
ALGORITHMS ,LEAST squares ,ESTIMATION theory ,MATHEMATICAL variables ,ANALYSIS of variance ,MATHEMATICAL statistics - Abstract
Nonlinear least squares problems frequently arise for which the variables to be solved for can be separated into a linear and a nonlinear part. A variable projection algorithm has been developed recently which is designed to take advantage of the structure of a problem whose variables separate in this way. This paper gives a slightly more efficient and slightly more general version of this algorithm than has appeared earlier. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
59. The Automatic Integration of Ordinary Differential Equations.
- Author
-
Gear, C. W. and Timlake, W. P.
- Subjects
INITIAL value problems ,DIFFERENTIAL equations ,ALGORITHMS ,SET theory ,BOUNDARY value problems ,AUTOMATION - Abstract
An integration technique for the automatic solution of an initial value problem for a set of ordinary differential equations is described. A criterion for the selection of the order of approximation is proposed. The objective of the criterion is to increase the step size so as to reduce solution time. An option permits the solution of "stiff" differential equations. A program embodying the techniques discussed appears in Algorithm 407. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
60. Conversion of Limited- Entry Decision Tables to Computer Programs--A Proposed Modification to Pollack's Algorithm.
- Author
-
Shwayder, Keith and Morris, R.
- Subjects
ENTROPY (Information theory) ,INFORMATION theory ,COMPUTER programming ,ALGORITHMS ,COMPUTER software - Abstract
Pollack has proposed on algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program. Two modifications a this algorithm are proposed. The first relies on Shannon's noiseless coding theorem and the communications concept of entropy but does not completely test the ELSE Rule. The second modification completely tests the ELSE Rule but results in more executions than the first modification. Both modifications result in lower execution time than Pollack's algorithm. However, neither modification guarantees a globally optimal solution. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
61. An Algorithm for Filon Quadrature.
- Author
-
Chase, Stephen M. and Fosdick, Lloyd D.
- Subjects
ALGORITHMS ,NUMERICAL analysis software ,NUMERICAL integration ,NUMERICAL analysis ,MATHEMATICAL analysis ,COMPUTER programming - Abstract
An algorithm for Filon quadrature is described. Considerable attention has been devoted to an analysis of the round-off and truncation errors. The algorithm includes an automatic error control feature. [ABSTRACT FROM AUTHOR]
- Published
- 1969
- Full Text
- View/download PDF
62. One-Pass Compilation of Arithmetic Expressions for a Parallel Processor.
- Author
-
Stone, Harold S.
- Subjects
PARALLEL processing ,COMPUTER arithmetic & logic units ,COMPILERS (Computer programs) ,ARITHMETIC ,ALGORITHMS ,COMPUTER circuits - Abstract
Under the assumption that a processor may have a multiplicity of arithmetic units, a compiler for such a processor should produce object code to take advantage of possible parallelism of operation. Most of the presently known compilation techniques are inadequate for such a processor because they produce expression structures that must be evaluated serially. A technique is presented here for compiling arithmetic expressions into structures that can be evaluated with a high degree of parallelism. The algorithm is a variant of the so-called "top-down" analysis technique, and requires only one pass of the input text. [ABSTRACT FROM AUTHOR]
- Published
- 1967
- Full Text
- View/download PDF
63. On the Implementation of AMBIT, A Language for Symbol Manipulation.
- Author
-
Christensen, Carlos
- Subjects
PROGRAMMING languages ,COMPUTER algorithms ,ALGORITHMS ,COMPUTER science ,DATA structures ,ELECTRONIC data processing - Abstract
A brief description is given of the implementation technique for the replacement rule of the AMBIT programming language. The algorithm for the "AMBIT scan" and an example of its application are given. The algorithm is applicable to other members of the family of string transformation languages of which AMBIT is a member, and it provides a rationale for the design of the AMBIT language. [ABSTRACT FROM AUTHOR]
- Published
- 1966
- Full Text
- View/download PDF
64. Multi-Tape and Infinite-State Automata--A Survey.
- Author
-
Oettinger, A. G. and Fischer, Patrick C.
- Subjects
TURING machines ,SEQUENTIAL machine theory ,COMPUTATIONAL linguistics ,RECURSION theory ,MACHINE theory ,ALGORITHMS - Abstract
A survey of machines which are more powerful than finite automata and less powerful than general Turing machines is presented. It is felt that the machines in this category are as closely related to digital computers as either the finite automata or the unrestricted Turing machines. Intermediate machines can be created by adjoining an infinite-state memory to a finite-state machine and then performing any or all of the following: (1) restrict the manner in which the unbounded portion of the memory can be accessed, (2) bound the number of steps allowed for a computation by some increasing recursive function of the length of the input, (3) restrict the total amount of memory available in the same manner. Examples from all three classes and their properties are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1965
65. On Overcoming High-Priority Paralysis in Multiprogramming Systems: A Case History.
- Author
-
Stevens, David F. and Randell, B.
- Subjects
MULTIPROGRAMMING (Electronic computers) ,ELECTRONIC data processing ,TIME-sharing computer systems ,MULTIPROCESSORS ,SCHEDULING ,ALGORITHMS - Abstract
High-priority paralysis is the degradation that can occur in multiprogramming systems when scheduling is based primarily on preassigned priorities. It can be alleviated by modifying the scheduling algorithm to maximize the number of programs active at one time. The case history given in this paper indicates two general methods by which simultaneity can be increased. Possible refinements in the scheduling algorithm for future improvements are considered briefly. [ABSTRACT FROM AUTHOR]
- Published
- 1968
- Full Text
- View/download PDF
66. A NOTE ON CORRELATED ERRORS IN REPEATED MEASUREMENTS.
- Author
-
Wiley, James A. and Wiley, Mary Glenn
- Subjects
STATISTICAL correlation ,MEASUREMENT errors ,ALGORITHMS ,ATTENUATION (Physics) ,MATHEMATICAL variables ,ESTIMATION theory - Abstract
This paper considers a test score model in which the true score and the measurement error are autocorrelated. After some preliminary remarks on corrections for attenuation, the paper focuses on the three-wave ease (t = 1, 2, 3), demonstrating identifiability, showing an estimation algorithm, and providing a numerical illustration. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
67. ON THE MAXIMIZATION OF THE GEOMETRIC MEAN WITH LOGNORMAL RETURN DISTRIBUTION.
- Author
-
Elton, Edwin J. and Gruber, Martin J.
- Subjects
LOGNORMAL distribution ,DISTRIBUTION (Probability theory) ,ALGORITHMS ,VARIANCES ,GEOMETRIC programming ,PORTFOLIO management (Investments) ,ECONOMIC equilibrium ,METHODOLOGY ,RATE of return - Abstract
In this paper we discuss the relevancy of the geometric mean as a portfolio selection criteria. A procedure for finding that portfolio with the highest geometric mean when returns on portfolios are lognormally distributed is presented. The development of this algorithm involves a proof that the portfolio with maximum geometric mean lies on the efficient frontier in arithmetic mean variance space. This finding has major implications for the relevancy of much of portfolio and general equilibrium theory. These implications are explored. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
68. APPLICATION OF QUASI-INTEGER PROGRAMMING TO THE SOLUTION OF MENU PLANNING PROBLEMS WITH VARIABLE PORTION SIZE.
- Author
-
Armstrong, Ronald D. and Sinha, Prabhakant
- Subjects
MENU design (Printed ephemera) ,MATHEMATICAL programming ,ALGORITHMS ,INTEGER programming ,CAPITAL budget ,MENUS ,BRANCH & bound algorithms ,FOOD service research ,PLANNING - Abstract
This paper presents the application of a modified mixed-integer programming algorithm to plan menus in which the portion size of the menu items can vary over a specified positive range. Previous mathematical programming formulations of menu planning problems have either required the variables representing menu items to be bivalent, or have formulated the problem with food groups as decision variables and no integer requirements at all. The former gives rise to a zero-one programming problem and the latter to a "feed-mix" problem. In many instances, a more realistic formulation would require that if a menu item is offered, its portion size must be between a specified upper and lower bound. Although this paper addresses itself chiefly to menu planning, it is readily seen that problems in capital budgeting may be tractable with a similar formulation. It is shown how a branch-and-bound algorithm for mixed-integer programming of the type proposed by Beale and Tomlin can be modified to solve the quasi-integer programming problem resulting from a variable portion size formulation of menu planning problems. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
69. DETERMINATION OF OPTIMUM PACKAGING FREQUENCY OF ITEMS JOINTLY REPLENISHED.
- Author
-
Goyal, S. K.
- Subjects
MANUFACTURING processes ,PACKAGING research ,OVERHEAD costs ,VARIABLE costs ,INVENTORY management systems ,MATHEMATICAL models ,ALGORITHMS ,ECONOMIC lot size - Abstract
This paper presents a systematic procedure for obtaining the optimum packaging frequencies for a number of items which are manufactured jointly but packaged individually immediately after manufacture. The method described in the paper is equally applicable to those problems where the optimum purchasing policy is to be obtained for a number of items procured from a single supplier. An example involving twenty jointly replenished items is solved to illustrate the procedure given in the paper. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
70. SOLVING THE "MARKETING MIX" PROBLEM USING GEOMETRIC PROGRAMMING.
- Author
-
Balachandran, V. and Gensch, Dennis H.
- Subjects
MARKETING mix ,GEOMETRIC programming ,BUSINESS planning ,MATHEMATICAL programming ,LINEAR programming ,MARKETING research ,ALGORITHMS ,MATHEMATICAL optimization ,REGRESSION analysis - Abstract
This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
71. Production Planning for a Stochastic Demand Process.
- Author
-
Gonedes, Nicholas J. and Lieber, Zvi
- Subjects
PRODUCTION planning ,ECONOMIC demand ,STOCHASTIC processes ,ALGORITHMS ,PLANNING ,PRODUCTION engineering ,INVENTORY control - Abstract
This paper deals with planning production of a single good over a prescribed finite interval of time [0, T]. The costs considered within the problem are production and holding costs; holding costs are incurred for negative inventory (caused by backlogged sales) and positive inventory (caused by production in excess of demand). The demand for the product is treated as a stochastic process. Problem formulation and optimization use tools from continuous-time stochastic variational calculus and control theory. Among its results, the paper proves the uniqueness of the optimal solution and provides an algorithm for the problem. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
72. The Elementary Redundancy-Optimization Problem: A Case Study in Probabilistic Multiple-Goal Programming.
- Author
-
Hendrix, G. G. and Stedry, A. C.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL programming ,LINEAR programming ,PROBABILITY theory ,ALGORITHMS ,INTEGER programming ,SYSTEM analysis - Abstract
This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
73. The Optimal Location of Nuclear-Power Facilities in the Pacific Northwest.
- Author
-
Dutton, Ron, Hinman, George, and Millham, C. B.
- Subjects
NUCLEAR power plant location ,NUCLEAR power plants ,INDUSTRIAL location ,MATHEMATICAL optimization ,BRANCH & bound algorithms ,TRANSPORTATION ,ALGORITHMS ,GROWTH rate - Abstract
This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
74. A Generated Cut for Primal Integer Programming.
- Author
-
Arnold, Larry R. and Bellmore, Mandell
- Subjects
INTEGER programming ,LINEAR programming ,ALGORITHMS ,MATHEMATICAL optimization ,ITERATIVE methods (Mathematics) ,STOCHASTIC processes - Abstract
This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
75. Coordinating Aggregate and Detailed Scheduling Decisions in the One-Machine Job Shop: Part I. Theory.
- Author
-
Gelders, L. and Kicindorfer, P. R.
- Subjects
PRODUCTION scheduling ,SCHEDULING ,DECISION making ,OVERTIME ,ALGORITHMS ,TARDINESS ,COST ,JOB shops - Abstract
This paper presents a formal model of the one-machine job-shop scheduling problem with variable capacity. Its primary interest focuses on the trade-off between overtime and detailed scheduling costs. The scheduling problem considered is minimizing the sum of weighted tardiness and weighted flow-time costs for a given capacity plan (i.e., a given overtime plan). The paper generalizes sequence-theory results to this case where possible, analyzes various lower-bounding structures for the problem, outlines a preliminary branch-and-bound algorithm, and illustrates several interesting features of the algorithm and bounding structures by an example. Extensions of the results to more complex environments are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
76. A Mathematical Model for Simultaneously Determining the Optimal Brand-Collection and Display-Area Allocation.
- Author
-
Anderson, Evan E. and Amato, Henry N.
- Subjects
ALGORITHMS ,RESOURCE allocation ,BRAND name products ,BUSINESS names ,RETAIL industry ,PROFIT ,CONSUMER preferences - Abstract
This paper addresses a fundamental short-run resource-allocation problem confronting retail distribution: simultaneously finding the specific brands, from many, that should be displayed, and the amount of retail product-display area that should be assigned to these brands, in order to maximize the retail institution's profit. The paper decomposes total market demand according to the various levels of brand preference that could conceivably exist in final markets, and then, employs an algorithm, similar to the one used to solve the fixed-charge problem, to find the optimal brand mix and display-area allocation. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
77. The Optimal Control of Partially Observable Markov Processes over a Finite Horizon.
- Author
-
Smallwood, Richard D. and Sondik, Edward J.
- Subjects
MARKOV processes ,STOCHASTIC processes ,MATHEMATICAL models ,DISCRETE-time systems ,SYSTEM analysis ,MATHEMATICAL functions ,ALGORITHMS - Abstract
This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
78. THE SIMPLEX METHOD IN MIXED INTEGER AND INTEGER PROGRAMMING--A UNIFIED COMPUTATIONAL VIEW.
- Author
-
Shanno, D. F.
- Subjects
INTEGER programming ,ALGORITHMS ,MATHEMATICAL programming ,SIMPLEXES (Mathematics) ,LINEAR programming - Abstract
Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 1973
- Full Text
- View/download PDF
79. FINDING THE K SHORTEST LOOPLESS PATHS IN A NETWORK.
- Author
-
Yen, Jin Y.
- Subjects
ALGORITHMS ,NETWORK analysis (Planning) ,OPERATIONS research ,BRANCH & bound algorithms ,MATHEMATICAL optimization ,MATHEMATICAL models ,LINEAR statistical models ,SYSTEMS engineering ,INDUSTRIAL management - Abstract
This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
80. AN ALGORITHM FOR THE QUADRATIC ASSIGNMENT PROBLEM.
- Author
-
Graves, G. W. and Whinston, A. B.
- Subjects
RESOURCE allocation ,QUADRATIC assignment problem ,ASSIGNMENT problems (Programming) ,ECONOMIC models ,COMBINATORIAL optimization ,COMBINATORICS ,ECONOMIC statistics ,MATHEMATICAL statistics ,MATHEMATICAL models ,ALGORITHMS ,MATHEMATICAL analysis ,PROBLEM solving - 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. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
81. SOLVING PRODUCTION SMOOTHING PROBLEMS.
- Author
-
Galbraith, Jay R.
- Subjects
INVENTORY control ,MATHEMATICAL optimization ,ALGORITHMS ,RESOURCE management ,FOUNDATIONS of arithmetic ,COST analysis ,PRODUCT management ,COST accounting ,ORGANIZATIONAL research ,RESOURCE allocation ,INDUSTRIAL costs ,ORGANIZATIONAL behavior - Abstract
This paper analyzes the problem of balancing resource capacity utilization against the costs of user delay or inventory investment. Instead of formulating algorithms to solve more classical versions of the problem, this paper describes ways that organizations can drop the cost curve prior to applying an optimizing algorithm. This is done by classifying the techniques and giving examples from organizations which have faced serious smoothing problems. Other organizations can improve their coat performance by adopting some of these techniques. [ABSTRACT FROM AUTHOR]
- Published
- 1969
- Full Text
- View/download PDF
82. OPTIMAL PRODUCTION SCHEDULING AND EMPLOYMENT SMOOTHING WITH DETERMINISTIC DEMANDS.
- Author
-
Lippman, Steven A., Rolfe, Alan J., Wagner, Harvey M., and Yuan, John S.C.
- Subjects
PRODUCTION scheduling ,MATHEMATICAL variables ,LABOR supply ,LABOR costs ,INVENTORY control ,PRODUCTION control ,STATISTICAL smoothing ,INVENTORY accounting ,ALGORITHMS ,MATHEMATICAL models ,EDUCATION ,MANAGEMENT - Abstract
In this paper we study a model that minimizes the sum of production, employment smoothing, and inventory costs subject to a schedule of known demand requirements over a finite time horizon. The three instrumental variables are work force producing at regular-time, work force producing on overtime, and the total work force. Overtime is limited to be not more than a fixed multiple of regular time. The idle portion of the work force and the levels of inventory are resultant variables. We postulate the following shape characteristics for the cost functions production costs are convexlike, smoothing costs are V-shaped, and holding costs are increasing, both the production and holding cost functions need not be stationary. In this paper, we provide upper and lower bounds on the cumulative regular-time plus overtime work force for any sequence of demand requirements. We also give the form of an optimal policy when demands are monotone (either increasing or decreasing). Finally, we derive the asymptotic behavior of optimal policies when demands are monotone and the planning horizon becomes arbitrarily long. All of these results, which convey information about the numerical values of optimal policies, given specific demands and an initial level of inventory, depend only on the shape characteristics of the cost functions. Algorithmic techniques are discussed elsewhere. [ABSTRACT FROM AUTHOR]
- Published
- 1967
- Full Text
- View/download PDF
83. DECOMPOSITION OF PROJECT NETWORKS.
- Author
-
Parikh, Shailendra C. and Jewell, William S.
- Subjects
PRODUCTION scheduling ,OPERATIONS research ,CRITICAL path analysis ,MANAGEMENT software ,PROJECT management ,ALGORITHMS ,COMPUTER storage devices ,MATHEMATICAL models ,COMPUTER networks ,SIMULATION methods & models ,MATHEMATICAL models in business ,MANAGEMENT science - Abstract
This paper considers "critical path" networks which are used for the planning and scheduling of projects that consist of well defined sequences of individual activities. When the number of activities is large, it becomes difficult to prepare a network for the project as one unit, and it may also be difficult to store the network in the high speed memory of a digital computer. Also, in the cases where there are two or more independent projects, which are weakly inter-related by common activities, the problem of efficient scheduling of all the projects becomes quite difficult. This paper presents a method to "tear" or "decompose" a project network into several subnetworks, schedule the subnetworks and then to put the subnetworks back together. A computational algorithm is first given for time-only networks; then two computational formulations are given for cost-time network of project subnetworks. The latter essentially generalize the algorithm due to Fulkerson, in order to handle piecewise linear, convex, cost-time curves for some or all of the activities. [ABSTRACT FROM AUTHOR]
- Published
- 1965
- Full Text
- View/download PDF
84. THE GENERALIZED STEPPING STONE METHOD FOR THE MACHINE LOADING MODEL.
- Author
-
Eisemann, Kurt
- Subjects
LINEAR programming ,ALGORITHMS ,MATHEMATICAL programming ,SIMPLEXES (Mathematics) ,MATHEMATICAL models ,MATHEMATICAL models in business ,TOPOLOGY ,NUMERICAL analysis ,BUSINESS mathematics ,MANAGEMENT science ,SIMULATION methods & models - Abstract
This paper gives a detailed description of an algorithm for the solution of a specialized Linear Programming model, to be called the Machine Loading model. It is a generalization of the Transportation Problem, in that weighting factors are applied to the individual elements which form the row and column sums. For the Machine Loading model, the simplex method reduces to a specialized algorithm which generalizes the stepping stone method of the Transportation Problem [2], [3]. With the resulting generalized stepping stone method, it becomes practicable to solve many large-scale problems for which the direct application of the simplex method would be impracticable. The present paper is restricted to a discussion of the following topics: (I) the general characteristics of the model and its topological features; (ii) a detailed solution algorithm, including a consideration of degenerate cases and the use of a computer; (iii) a more restrictive capacitated model and the corresponding modifications to the solution algorithm; and (iv) the complete illustrative solution of a numerical example. The purpose is to aid interested readers in gaining familiarity with the algorithm and facility in the solution of numerical problems. No derivations or proofs will be included. [ABSTRACT FROM AUTHOR]
- Published
- 1964
- Full Text
- View/download PDF
85. ON THE GENERALIZED TRANSPORTATION PROBLEM.
- Author
-
Balas, E. and Ivanescu, P. L.
- Subjects
TRANSPORTATION ,ALGORITHMS ,MATHEMATICAL models of industrial management ,MATHEMATICAL models in business ,MANAGEMENT science ,BUSINESS models ,MATHEMATICAL variables ,BUSINESS mathematics ,EQUATIONS ,ITERATIVE methods (Mathematics) ,PROBLEM solving - Abstract
The purpose of the present paper is to extend the loop-technique of the stepping-stone algorithm to the generalized transportation problem. The main result (Theorem and Corollary of §6) is, that passing from a basic feasible solution to another one may always be carried out by constructing a simple symmetrical or a double loop (as defined in §2) and computing new values for the variables only along this path. The amount of computations needed for this turns out to be substantially reduced as compared to the usual way of solving the system of equations relating the new basis to the old one. [ABSTRACT FROM AUTHOR]
- Published
- 1964
- Full Text
- View/download PDF
86. A HEURISTIC PROGRAM FOR LOCATING WAREHOUSES.
- Author
-
Kuehn, Alfred A. and Hamburger, Michael J.
- Subjects
WAREHOUSES -- Location ,ALGORITHMS ,LINEAR programming ,HEURISTIC programming ,PHYSICAL distribution of goods ,SHIPMENT of goods ,LOCATION analysis ,METHODOLOGY ,INDUSTRIAL applications ,PROBLEM solving research ,FLOW charts ,COMPUTER software - Abstract
The linear programing algorithms available for optimizing the routing of shipments in multi-plant, multi-destination systems cannot, in the current state of knowledge, be applied directly to the more general problem of determining the number and location of regional warehouses in large-scale distribution networks. This paper outlines a heuristic computer program for locating warehouses and compares it with recently published efforts at solving the problem either by means of simulation or as a variant of linear programing. The heuristic approach outlined in this paper appears to offer significant advantages in the solution of this class of problems in that it (1) provides considerable flexibility in the specification (modeling) of the problem to be solved, (2) can be used to study large-scale problems, that is, complexes with several hundred potential warehouse sites and several thousand shipment destinations, and (3) is economical of computer time. The results obtained in applying the program to small scale problems have been equal to or better than those provided by the alternative methods considered. [ABSTRACT FROM AUTHOR]
- Published
- 1963
- Full Text
- View/download PDF
87. IMPROVED COMBINATORIAL PROGRAMMING ALGORITHMS FOR A CLASS OF ALL-ZERO-ONE INTEGER PROGRAMMING PROBLEMS.
- Author
-
Pierce, John F. and Lasky, Jeffery S.
- Subjects
MATHEMATICAL programming ,COMBINATORIAL optimization ,ALGORITHMS ,MODIFICATIONS ,DYNAMIC programming ,NONLINEAR programming ,INTEGER programming ,MANAGEMENT science ,MATHEMATICAL optimization ,PROBLEM solving - Abstract
In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
88. A DYNAMIC MODEL FOR BOND PORTFOLIO MANAGEMENT.
- Author
-
Bradley, Stephen P. and Crane, Dwight B.
- Subjects
BOND funds ,DECISION theory ,DECISION making ,INVESTMENTS ,ECONOMIC indicators ,PORTFOLIO management (Investments) ,ALGORITHMS ,MATHEMATICAL decomposition ,MATHEMATICAL programming ,INVESTMENT analysis ,FINANCIAL management ,MATHEMATICAL models - Abstract
The bond portfolio problem is viewed as a multistage decision problem in which buy, sell, and hold decisions are made at successive (discrete) points in time. Normative models of this decision problem tend to become very large, particularly when its dynamic structure and the uncertainty of future interest rates and cash flows are incorporated in the model. In this paper we present a multiple period bond portfolio model and suggest a new approach for efficiently solving problems which are large enough to make use of as much information as portfolio managers can reasonably provide. The procedure utilizes the decomposition algorithm of mathematical programming and an efficient technique developed for solving subproblems of the overall portfolio model. The key to the procedure is the definition of subproblems which are easily solved via a simple recursive relationship. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
89. The Rearrangement of Items in a Warehouse.
- Author
-
Christofides, Nicos and Colloff, I.
- Subjects
WAREHOUSE management ,WAREHOUSES ,ALGORITHMS ,FACTORIES ,CYCLES ,PLANT layout ,COMMERCIAL buildings ,PHYSICAL distribution of goods - Abstract
This paper is concerned with finding the optimal way of rearranging items in a warehouse from their initial positions to their desired final locations. Such a rearrangement may become necessary because of changes in the relative demand for each item, with the result that what were once fast-moving items at the 'front' end of the warehouse, are now only slow-moving ones that must be moved towards the 'rear.' Although the problem, as treated in this paper, is addressed to the rearrangement of items in a warehouse, many other applications come immediately to mind, such as the reorganization of the layout of open-plan orates and factories. The paper gives a two-stage algorithm that produces the sequence of item movements necessary to achieve the desired rearrangement and incur the minimum cost (or time) spent in the rearranging process; the result is optimal in the restricted case where the rearrangement must be done in a number of cycles each one being of a short time duration (the case, for example, if the warehouse were to remain operative during the rearrangement). [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
90. Maximal, Lexicographic, and Dynamic Network Flows.
- Author
-
Minieka, Edward
- Subjects
ALGORITHMS ,LEXICOGRAPHY ,SCHEDULING ,ENCYCLOPEDIAS & dictionaries ,ALGEBRA ,FOUNDATIONS of arithmetic - Abstract
This paper proves two properties of maximal network flows: (1) If there exist a maximal network flow with a given departure pattern at the sources and a maximal flow with a given arrival pattern at the sinks, then there exists a flow that has both this departure pattern at the sources nd this arrival pattern at the sinks. (2) There exists a maximal dynamic network flow that simultaneously has a latest (earliest) departure schedule at the sources and an earliest (latest) arrival schedule at the sinks. The paper modifies FORD AND FULKERSON'S maximal dynamic flow algorithm to construct a maximal dynamic network flow with a latest departure schedule and an earnest arrival schedule. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
91. The Use of Cuts in Complementary Programming.
- Author
-
Ibaraki, Toshihide
- Subjects
MATHEMATICAL programming ,LINEAR programming ,MATRICES (Mathematics) ,VECTOR analysis ,ALGORITHMS ,FUNCTIONAL equations ,MATHEMATICAL optimization ,OPERATIONS research - Abstract
A complementary programming problem is a linear programming problem with the additional restriction that x
p xq =0 holds for each specified pair (xp , xq ). This paper obtains constraints called C-cuts from the restriction xp xq =0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported. [ABSTRACT FROM AUTHOR]- Published
- 1973
- Full Text
- View/download PDF
92. Solution of the Flowshop-Scheduling Problem with No Intermediate Queues.
- Author
-
Wismer, D. A.
- Subjects
PRODUCTION scheduling ,MANAGEMENT ,OPERATIONS research ,ALGORITHMS ,MANUFACTURING processes ,OCCUPATIONS - Abstract
This paper presents an algorithm that will minimize the total processing time for a particular case of the n-job, m-machine scheduling problem. In many industrial processes, jobs are processed by a given sequence of machines. Often, once the processing of a job commences, the job must proceed immediately from one machine to the next without encountering any delays en route. The machine sequence need not be the same for all jobs. Because of this processing constraint that prohibits intermediate queues, most normal scheduling techniques are not applicable. This paper obtains a solution to this constrained scheduling problem by modeling it as a traveling-salesman problem; known solution techniques can then be employed. The paper solves a sample problem and discusses computational considerations. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
93. Management of Seasonal Style-Goods Inventories.
- Author
-
Ravindran, Arunachalam
- Subjects
INVENTORIES ,PRODUCT management ,CONSUMER goods ,ECONOMIC demand ,SELLING ,ALGORITHMS - Abstract
This paper develops an inventory model in which season length is specifically included as a variable for seasonal style goods under the assumption that the demands exhibit a simple contagion pattern, namely, the influence of past demands on future occurrence of demands. The paper first derives an s-S optimal order policy as a function of the selling season, then determines the optimal duration and timing of the selling season, and, finally includes an algorithm for computing the optimal season length. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
94. AN ALL ZERO-ONE ALGORITHM FOR A CERTAIN CLASS OF TRANSPORTATION PROBLEMS.
- Author
-
De Maio, Adriano and Roveda, Claudio
- Subjects
TRANSPORTATION problems (Programming) ,INDUSTRIES ,LINEAR programming ,ALGORITHMS ,ASSIGNMENT problems (Programming) ,MATHEMATICAL programming - Abstract
This paper considers a special class of transportation problems. There is a set of sources producing the same material with a fixed maximum capacity, and a set of users whose demands for the material are known. A cost is associated with the transportation of the material from each source to each user. Each user is to be supplied by one source only. The problem consists of finding the flow of the material from the sources to the users that satisfies their demands and minimizes the total transportation cost. The formulation of the problem is the same as the well-known Hitchcock problem with the further constraint that all the variables are binary. The paper proposes a search method, roughly resembling Balas's filter method, for the solution of the problem, and discusses it from a computational point of view. Finally, it describes an application of the model to a real industrial problem. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
95. AN ANALYSIS OF THE M/G/1 QUEUE UNDER ROUND-ROBIN SCHEDULING.
- Author
-
Sakata, M., Noguchi, S., and Oizumi, J.
- Subjects
COMPUTER systems ,ELECTRONIC systems ,ALGORITHMS ,QUEUING theory ,MANAGEMENT science ,DISTRIBUTED computing - Abstract
In order to discuss scheduling algorithms for time-sharing computer systems, this paper analyzes the M/G/1 queue under the well known round-robin (RR) discipline. Three models are considered: the constant-quantum RR model, the processor-shared (or zero-quantum RR) model, and the variable-quantum RR model. The paper proposes an effective calculating method for obtaining the expected response time under an arbitrary processing-time distribution with overhead. By the theoretical analysis, one can show how the response time is affected by the scheduling and processing-time distributions, as is demonstrated by some typical examples. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
96. DIVISIBLE AND MOVEABLE ACTIVITIES IN CRITICAL-PATH ANALYSIS.
- Author
-
Jewell, William S.
- Subjects
ALGORITHMS ,ALGEBRA ,FACTOR analysis ,INTEGER programming ,MATHEMATICAL programming ,LINEAR programming - Abstract
Certain jobs in large projects do not have a unique 'location' in the critical-path network; they may be moved into certain slack intervals, for example, or may even be divisible into smaller subtasks, and 'tucked in' at several locations. A previous paper gave an analysis of a model in which a single job can be divided up in any manner among an arbitrary number of locations; the resulting algorithm was of the optimal-network-flow type, which can be simply and efficiently solved using available computer codes. The first part of the present paper extends this model to multiple jobs of divisible type. The general approach is via the decomposition method of linear programming; however, the resulting algorithm is again fairly simple. Optimal cost-time solutions, possibly infinite (or optimal network flow solutions, possibly infeasible) are generated by known algorithms. The resulting schedules or cuts are then combined in a simple, special structure linear program whose dimensionality is equal to the number of divisible groups. Bounds on the nonintegrality of the final allocations can also be determined. When these special jobs can only be moved about the network in their entirety, or in certain indivisible modules, the problem takes on the form of an integer program. The second part of the paper gives a branch-and-bound procedure for the problem of movable activities, together with efficient heuristics for arbitrating and bounding these locations, using only the ordinary critical-path algorithm. Examples are given for both models. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
97. OPTIMIZATION OF SERIES-PARALLEL-SERIES NETWORKS.
- Author
-
Jensen, Paul A.
- Subjects
MATHEMATICAL optimization ,ALGORITHMS ,MATHEMATICAL analysis ,PROBABILITY theory ,ALGEBRA ,MATHEMATICS - Abstract
This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
98. CUTTING-PLANE METHODS WITHOUT NESTED CONSTRAINT SETS.
- Author
-
Topkis, Donald M.
- Subjects
ALGORITHMS ,ALGEBRA ,CALCULATORS ,FOUNDATIONS of arithmetic ,MATHEMATICAL analysis ,MATHEMATICS - Abstract
This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include those of KELLEY, CHENEY AND GOLDSTEIN, and a generalization of the one used by both ZOUTENDIJK and VEXNoTT. For algorithms with nested constraint sets, these conditions reduce to a special case of those of ZANGWILL for such problems and include as special cases the algorithms of Kelley, Cheney and Goldstein, and Veinott. Finally, the paper gives an arithmetic convergence rate. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
99. CONSTRAINED NONLINEAR OPTIMIZATION BY HEURISTIC PROGRAMMING.
- Author
-
Paviani, D. A. and Himmelblau, D. M.
- Subjects
MATHEMATICAL optimization ,NONLINEAR statistical models ,HEURISTIC ,MATHEMATICAL programming ,ALGORITHMS ,PROBLEM solving - Abstract
This paper develops a new algorithm for solving the general nonlinear programming problem that melds the flexible simplex search of NELDER AND MEAD with various additional rules to take care of equality and/or inequality constraints. The set of violated inequalities and equalities is lumped into one inequality constraint loosely satisfied during the early progress of the optimization and more closely satisfied during its final stages. To permit this type of search, the method sets up a special tolerance criterion, a function that does not depend on either the values of the objective function or the values of the constraints. The new algorithm has solved successfully a number of problems that have been proposed in the literature as test problems. Finally, to indicate the algorithm's capabilities, the paper describes an example composed of a linear objective function of twenty-four variables subject to fourteen nonlinear equalities and thirty inequalities. [ABSTRACT FROM AUTHOR]
- Published
- 1969
- Full Text
- View/download PDF
100. ALGORITHMS FOR OPTIMAL PRODUCTION SCHEDULING AND EMPLOYMENT SMOOTHING.
- Author
-
Lippman, Steven A., Roffe, Alan J., Wagner, Harvey M., and Yuan, John S. C.
- Subjects
ALGORITHMS ,PRODUCTION scheduling ,EMPLOYMENT ,STATISTICAL smoothing ,OPERATIONS research ,INDUSTRIAL costs - Abstract
This paper seeks here a minimum cost production plan over a finite number of time periods. There is a known demand requirement (stated in production hours) to be met in each period from current and previous hours of production (stored as inventory). A production policy consists of scheduled amounts of hours, some of which are costed at regular-time wage rates, the remainder costed at overtime rates. Expansion or contraction of the work force (stated in production hours) is charged against the period-to-period variations in regular-time employment. The fluctuations in overtime production do not incur such hiring and firing costs. The amount of overtime used, however, is constrained not to exceed a specified fraction of regular-time utilized in any period. We describe algorithms for finding an optimal policy under the assumption that all costs are described by linear functions and where demands are either monotonic increasing or decreasing in time. In addition to presenting the algorithms, we also examine certain planning horizon results implied by these algorithms. Specifically, we ascertain when optimal first period decisions can be made without knowing the precise values of all future demands and costs. [ABSTRACT FROM AUTHOR]
- Published
- 1967
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.