Open Access. Powered by Scholars. Published by Universities.®
Business Administration, Management, and Operations Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Publication Year
Articles 61 - 90 of 145
Full-Text Articles in Business Administration, Management, and Operations
Optimal Design Of Networks With Node Weighted Functions, Shailesh J. Mehta
Optimal Design Of Networks With Node Weighted Functions, Shailesh J. Mehta
Research Reports from the Department of Operations
The design of optimal networks on a set of points is an interesting and important problem. However, the majority of work done so far is in flow problems and on graphs with arc weights. In this dissertation, the problem of constructing optimal networks with node weights is considered. The objective function depends on the weights assigned to the nodes and the degree of the nodes. Special cases of the general design problem of constructing networks or graphs with node weights and arc weights are also treated. The intent of the research was to develop polynomially bounded algorithms. The general design …
Corporate Tax Structures And A Special Class Of Set Partitioning Problems, Chien-Hua Lin
Corporate Tax Structures And A Special Class Of Set Partitioning Problems, Chien-Hua Lin
Research Reports from the Department of Operations
This thesis discusses a special integer program, a complete set partitioning problem in context of a real world situation; namely, that of paying unemployment compensation tax. In the United States, employers are required to pay contribution to a state administered unemployment compensation fund to protect the employees in the event of unemployment. A corporation can often be considered as a composition of subsidiaries, each with their own accounting data. In many states including Ohio, these subsidiaries may be treated individually or in various aggregations, each aggregation becoming a subsidiary, prior to computing the contribution payment. The payment is a function …
Optimal Rearrangement Of Objects, Ashok Kumar Mittal
Optimal Rearrangement Of Objects, Ashok Kumar Mittal
Research Reports from the Department of Operations
This dissertation deals with finding an optimal way of changing a given arrangement to a (specified) new arrangement. Two types of problems are considered. In the first type of problem, there is no extra storage space available for storage of the objects. The rearrangement is done by a sequence of pairwise exchanges. In the second type of problem there is extra storage space available for storage. The rearrangement in this case is done by a vehicle which moves one object at a time. Problems are further classified by type of arrangement as basic cycles, cycles--and general arrangement- and by the …
Critical Path Problem Under Assignment Constraints With The Number Of Men Less Than The Number Of Activities, S. Kumar, D. Wagner, R. Chandrasekaran
Critical Path Problem Under Assignment Constraints With The Number Of Men Less Than The Number Of Activities, S. Kumar, D. Wagner, R. Chandrasekaran
Research Reports from the Department of Operations
The paper concerns the problem of determining the shortest time of project completion under the constraint that the number of men available is less than the number of activities to be performed. Additionally, it is assumed that men differ in skills. In order to solve this problem, two related problems are formulated. The first one does not take into account the constraint that a man cannot perform more than one job at a time. The second one is discrete in time and is used to make a solution of the former problem feasible. An iterative procedure for solving the basic …
Some Algorithms For Solving Extreme Point Mathematical Programming Problems, S. Kumar, D. Wagner
Some Algorithms For Solving Extreme Point Mathematical Programming Problems, S. Kumar, D. Wagner
Research Reports from the Department of Operations
The paper concerns some algorithms for solving extreme point mathematical programming problem formulated in [4]. The algorithms discussed consist in determining lower and upper bounds of the objective function and accomplishing the search for the optimal solution. The direction of search depends upon the choice of the starting point. It can be either lower or upper bound. Algorithms making use of the two possible search direction are discussed in detail. In order to illustrate the application of these algorithms, two numerical examples are solved. Some other algorithms based on different approaches are also briefly discussed.
Design And Testing Of A Generalized Reduced Gradient Code For Nonlinear Optimization, Leon S. Lasdon, Allan D. Waren, Arvind Jain, Margery W. Ratner
Design And Testing Of A Generalized Reduced Gradient Code For Nonlinear Optimization, Leon S. Lasdon, Allan D. Waren, Arvind Jain, Margery W. Ratner
Research Reports from the Department of Operations
Generalized Reduced Gradient (GRG) Methods are algorithms for solving nonlinear programs of general structure. An earlier paper [1] discussed the basic principles of GRG and presented the preliminary design of a GRG computer code. This paper describes a modified version of that initial design, including the experiences that led to the modifications. This paper also is intended to serve as partial system documentation. The code is compared computationally with an interior penalty function code, and anticipated future work on the algorithm is outlined.
Optimal Design Of Water Distribution Pipeline Networks, Wilson Carlos Duarte Delfino
Optimal Design Of Water Distribution Pipeline Networks, Wilson Carlos Duarte Delfino
Research Reports from the Department of Operations
A water distribution pipeline network is a system that transports water from points of supply to points of demand where water must be delivered at a certain rate and pressure head. The system consists of water supply points, water demand points and pumping stations all connected by pipelines according to some network geometry. In this paper we consider the one-period deterministic design problem of a water distribution pipeline network. The design problem in water networks with no loops (tree networks) and in water networks with loops, respectively, is mathematically formulated with pipe costs, pump costs and energy costs being minimized. …
Minimal Spanning Trees With Ratio Criterion, R. Chandrasekaran
Minimal Spanning Trees With Ratio Criterion, R. Chandrasekaran
Research Reports from the Department of Operations
The minimal spanning tree problem is well known, and efficient algorithms exist for solving this problem. One of these algorithms has been called a "greedy" algorithm by Edmonds, who has also described the full potential of such an algorithm. In this paper, we consider a slightly modified objective function. We show that the greedy algorithm does not work for this modified problem, even if it is modified in a suitable way. First we provide a characterization for an optimal tree, which is an extension of a condition found in [2] for the minimal spanning tree problem. This gives us an …
Optimal Selection Of Students For Awarding Financial Aid, R. Chandrasekaran, S. Subba Rao
Optimal Selection Of Students For Awarding Financial Aid, R. Chandrasekaran, S. Subba Rao
Research Reports from the Department of Operations
Most academic departments in universities are faced with the problem of selecting candidates for awarding limited financial aid. In many institutions, there are two levels of aid: (i) graduate assistantships that pay a larger amount and (ii) tuition fellowships which pay only tuition, and hence a lesser amount. The limitation on available aid makes the problem of selecting the right candidates a difficult and interesting one. Even when aid is given, the event that a student joins a department is only probabilistic, due to competition from other schools. However, it seems realistic to assume that the probability that a student …
Nonlinear Optimization Using The Generalized Reduced Gradient Method, Leon S. Lasdon, Richard L. Fox, Margery W. Ratner
Nonlinear Optimization Using The Generalized Reduced Gradient Method, Leon S. Lasdon, Richard L. Fox, Margery W. Ratner
Research Reports from the Department of Operations
Generalized Reduced Gradient methods are algorithms for solving nonlinear programs of general structure. This paper discusses the basic principles of GRG, and constructs a specific GRG algorithm. The logic of a computer program implementing this algorithm is presented by means of flow charts and discussion. A numerical example is given to illustrate the functioning of this program.
Bimatrix Markovian Decision Processes And Stochastic Ratio Games, Vijaykumar V. Aggarwal
Bimatrix Markovian Decision Processes And Stochastic Ratio Games, Vijaykumar V. Aggarwal
Research Reports from the Department of Operations
Markov decision processes and stochastic games have been considered in this dissertation. An infinite planning horizon is assumed. Both discounted and undiscounted cash flows have been treated. In Markov decision process, a two-dimensional reward structure is considered and the objective criterion is to maximize the rate of return. It has been shown that a pure stationary optimal policy exists, whenever the rewards are finite and, in particular, the investment part of cash flow is positive. In the case of discounted cash flows, the optimal policy depends on the initial state the process is in. Finite algorithms have been proposed to …
Computational Experience With An Enumerative Algorithm For The Set Covering Problem With Base Constraints, Harvey M. Salkin, Chien-Hua Lin
Computational Experience With An Enumerative Algorithm For The Set Covering Problem With Base Constraints, Harvey M. Salkin, Chien-Hua Lin
Research Reports from the Department of Operations
An algorithm for the classical set-covering problem with additional "base" constraints is presented. The "base" constrained set covering problem is: Minimize cx, subject to Ex ≥ e, xj = 0 or 1 (j = 1,...,n), and Bx ≤ d. Here E is an m by n matrix of zeros and ones, e is an m column of ones, c and d are nonnegative vectors, and B is a nonnegative array having row diagonal structure. The algorithm is basically a zero-one single branch enumeration with linear programming and other feasibility criteria. A "heuristic" is used which sometimes finds an initial solution …
Row Generalized Linear Programs, R. Chandrasekaran
Row Generalized Linear Programs, R. Chandrasekaran
Research Reports from the Department of Operations
A concept of row generalized linear programs is introduced. Illustrations of potential application for this concept are provided, along with methods for solving the row generalized linear program. The duality between row and column generalized linear programs is discussed.
The Complementarity Problem Of Mathematical Programming, Arie Tamir
The Complementarity Problem Of Mathematical Programming, Arie Tamir
Research Reports from the Department of Operations
We consider the nonlinear complementarity problem: Find x in R^n such that: x ≥ 0 , f(x) ≥ 0 (1) x^T(f(x))=0 (2) where f is a given mapping satisfying f(0) = 0 and q is a vector in R^n. We say that the problem is feasible if (1) has a solution. f is said to be a Q-function if (1)-(2) has a solution for each q in R^n, and it is a P-function if the solution is unique for each q. Classes of functions are defined using properties of the complementarity problem (1)-(2), and sufficient conditions which guarantee that a …
Optimal Flows In Networks With Positive Gains, Klaus Truemper
Optimal Flows In Networks With Positive Gains, Klaus Truemper
Research Reports from the Department of Operations
Simple, yet powerful non-simplex algorithms are developed for max flow and min-cost flow problems in networks with positive gains. It is shown that these algorithms are computationally better than existing non-simplex algorithms. A strong relationship between the min-cost flow problem in pure networks and the max flow problem in networks with positive gains is used to demonstrate how algorithms for one problem can be transformed into ones for the other problem.
One Machine Sequencing To Minimize Mean Flow Time With Minimum Number Tardy, Hamilton Emmons
One Machine Sequencing To Minimize Mean Flow Time With Minimum Number Tardy, Hamilton Emmons
Research Reports from the Department of Operations
The problem of sequencing n jobs on one machine is considered, under the multiple objective of minimizing mean flow time with the minimum number of tardy jobs. A simple procedure is first proposed to schedule for minimum flow time with a specified subset of jobs on time. This is used in conjunction with Moore's Algorithm in a simple heuristic producing good and often optimal schedules. A branch-bound algorithm is presented to produce the optimal schedule efficiently with the help of several theorems which eliminate much branching.
All-Integer Integer Programming Algorithms Applied To Tableaux With Rational Coefficients, Harvey M. Salkin, Shailesh J. Mehta, Pradip H. Shroff
All-Integer Integer Programming Algorithms Applied To Tableaux With Rational Coefficients, Harvey M. Salkin, Shailesh J. Mehta, Pradip H. Shroff
Research Reports from the Department of Operations
It is shown that an initial all integer tableau is not necessary to the convergence of primal all-integer integer programming algorithms. It is well known that an analogous result holds for Gomory's dual all integer method, where only the cost row is required to be integer. We also show that the cost row need not be integer for the convergence of Gomory's dual all integer method.
Service Time Partitioning To Minimize Mean Flow Time, R. Chandrasekaran, Hamilton Emmons, S. Subba Rao
Service Time Partitioning To Minimize Mean Flow Time, R. Chandrasekaran, Hamilton Emmons, S. Subba Rao
Research Reports from the Department of Operations
This study investigates strategies for managing variable patient arrival rates in hospital outpatient clinics, particularly during peak times when waiting rooms overflow. A potential solution, inspired by scheduling theory, is partitioning patients by service time, with a focus on minimizing mean flow time (the total wait and service time). Using a stochastic scheduling model, the study explores a "quick service counter" approach where customers with shorter processing times are served by dedicated servers, preserving seniority to ensure fairness. Service times are assumed observable in advance, as in scenarios like supermarket checkout or preliminary hospital screening. The model simplifies complex queueing …
Order-Preserving Allocation Of Jobs To Two Machines, Shailesh J. Mehta, R. Chandrasekaran, Hamilton Emmons
Order-Preserving Allocation Of Jobs To Two Machines, Shailesh J. Mehta, R. Chandrasekaran, Hamilton Emmons
Research Reports from the Department of Operations
In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.
A Brief Survey Of Algorithms And Recent Results In Integer Programming, Harvey M. Salkin
A Brief Survey Of Algorithms And Recent Results In Integer Programming, Harvey M. Salkin
Research Reports from the Department of Operations
Several recent books and survey articles in integer programming have appeared in the literature. These are listed in the references. This is not another attempt at a detailed survey of a well surveyed field, but rather an outline of the basic techniques, important results, the classical special purpose problems and algorithms, and the available computer programs in integer programming. Hopefully, such a treatment can make the reader aware of the principle (general and special purpose) algorithms, results, and computer programs with a minimal amount of effort. Those interested in the details of a particular technique or result should consult the …
Results On Matroids, Blocking Systems And Convex Sets, Bradley Hull
Results On Matroids, Blocking Systems And Convex Sets, Bradley Hull
Research Reports from the Department of Operations
Two algorithms for matroids are presented, and relations between matroids and blocking systems are explored. A method is presented for removing an element of one of the dual pairs of clutters which comprise a blocking system. The problem of how to "chop off" a vertex from a convex polyhedron without creating new vertices is dealt with. Bounds on the number of cutting planes are determined.
School Bus Routing By Integer Programming, Dynamic Programming, And Composite Algorithms, Harvey M. Salkin, Patrice Breining
School Bus Routing By Integer Programming, Dynamic Programming, And Composite Algorithms, Harvey M. Salkin, Patrice Breining
Research Reports from the Department of Operations
This paper proposes several models, and outlines seemingly efficient techniques for the school bus routing problem. Given the number of schools, buses and their capacities, the number of children, their location and destination, and distances or times between stops, the problem is to design a "best" (several criteria are given) series of bus routes. An integer programming, a dynamic programming, and several composite models and algorithms are proposed. By making reasonable assumptions computer storage problems may be substantially alleviated and implementation is possible in each case. As the problem is usually enormous, emphasis is placed on producing "good" solutions to …
Binding Inequalities In Benders' Partitioning Algorithm, Harvey M. Salkin
Binding Inequalities In Benders' Partitioning Algorithm, Harvey M. Salkin
Research Reports from the Department of Operations
The mixed integer program is transformed to its equivalent integer program which has a vast number of "z inequality" constraints. A brief description of Benders' partitioning algorithm for the mixed integer program, which is suggested by the transformation, is then given. It is shown that unless a bounding constraint is explicitly introduced, a z inequality (hyperplane) that does not intersect an optimal solution to the integer program which appears in the algorithm cannot be dropped. Furthermore, if the bounding constraint is used in place of keeping not binding inequalities, the algorithm may converge at a slower rate. A small plant …
On The Linear Complementarity Problem, Arza K. Rao
On The Linear Complementarity Problem, Arza K. Rao
Research Reports from the Department of Operations
Consider the linear complementarity problem given by system (1): w = Mx + q (1) w ≥ 0, x ≥ 0 (2) } (I) x'w = 0 (3) where w, x and q are vectors of dimension n and M is a matrix of order n x n. Any (x,w) satisfying conditions (1) and (2) is a feasible solution to system (1). Any (x,w) satisfying (1), (2) and (3) is a complementary feasible solution to system (1). The main results derived in this work are given below. 1) Let MZ - class (i.e. off diagonal elements non-positive). Then Lemke's algorithm …
A Solution To A Special Class Of Flow Shop Scheduling Problems, Michael S. Salvador
A Solution To A Special Class Of Flow Shop Scheduling Problems, Michael S. Salvador
Research Reports from the Department of Operations
This research considers the most general type of "network" flow shop in which jobs pass through each of m > 2 stages, where the ith stage is composed of ni ≥ 1 identical processors. Jobs are processed on one processor at each stage in ascending order of stage numbers and the objective is minimization of makespan. The class of shops considered includes those where in-process inventory is prohibited and the sequence of jobs processed on a particular processor is required to be a subsequence of the jobs entering the shop; without these additional constraints, algorithmic solutions are available only for the …
Stockage And Transfer Rules For Multilocation Inventory Control, Chandrasekhar Das
Stockage And Transfer Rules For Multilocation Inventory Control, Chandrasekhar Das
Research Reports from the Department of Operations
A multilocation stochastic inventory problem is dealt with in this dissertation. It is assumed that stock is supplied from a central source and there exists a provision for transfer of stock over the locations. The stockage and transfer decisions are assumed to be centralized. The redistribution is made on the basis of stock review at predetermined points in time between every two consecutive procurement opportunities. Under certain regularity conditions, the optimality of a simple class of transfer rules is established for the two-location system. The optimal stockage rule is also characterized for this system on the supposition that interim transfers …
Algorithms For Discounted Stochastic Games: A Comparison Of Efficiency, Vijaykumar V. Aggarwal
Algorithms For Discounted Stochastic Games: A Comparison Of Efficiency, Vijaykumar V. Aggarwal
Research Reports from the Department of Operations
There are two algorithms for the solution of two person zero sum stochastic games with a finite number of states or positions and where future payoffs are discounted. The first algorithm is on somewhat similar lines as that of Hoffman and Karp for the undiscounted case, and the second one is recently developed by Rao, Chandrasekaran and Nair. This paper presents computer programs for the two algorithms and computational experiments for comparing the efficiency of the algorithms. The results show that the second algorithm requires fewer iterations and moreover, the computation time for each iteration in this is significantly lower. …
Nonserial Dynamic Programming - A Guided Tour, Augustine O. Esogbue, Barry Randall Marks
Nonserial Dynamic Programming - A Guided Tour, Augustine O. Esogbue, Barry Randall Marks
Research Reports from the Department of Operations
Interest in nonserial dynamic programming is deeply rooted in real life applications. Since the initial efforts in the early 60's however, a number of scattered treatment of this interesting field of dynamic programming has emerged. This paper traces the development of nonserial dynamic programming from the basic theory underlying dynamic programming to the latest applications of nonserial dynamic programming. The works of such major contributors as Nemhauser, Wilde, Beightler, Bertele and Brioschi are critically examined and recent relevant computational advances are discussed. The paper is concluded with a few examples of various applications of nonserial dynamic programming together with some …
Algorithms For Discounted Stochastic Games, S. Subba Rao, R. Chandrasekaran, K.P. K. Nair
Algorithms For Discounted Stochastic Games, S. Subba Rao, R. Chandrasekaran, K.P. K. Nair
Research Reports from the Department of Operations
In this paper, a two person zero sum stochastic game with a finite state space is considered. The movement of the game from state to state is jointly controlled by the two players depending on their choice of strategies from a finite number of alternatives available to each player in each of the states. Considering an infinite number of transitions, Hoffman and Karp provided a convergent algorithm for the solution of this game when the future payoffs are not discounted. Subsequently, the authors presented a proof for a faster algorithm available in literature for solving the same problem. This paper …
Reduction Of Dimensionality In Dynamic Programming Of Higher Dimensions: A Comparative Study And Analysis Of Computational Aspects, Augustine O. Esogbue, Amar J. Singh
Reduction Of Dimensionality In Dynamic Programming Of Higher Dimensions: A Comparative Study And Analysis Of Computational Aspects, Augustine O. Esogbue, Amar J. Singh
Research Reports from the Department of Operations
One of the noble aims of dynamic programming at its conception -- namely, that of developing an operational method for the numerical solution of various control problems, is often thwarted for meaningfully scaled systems, by the curse of dimensionality. By far the most important contribution to modern dynamic programming is the development of efficient algorithms capable of being used, with present-day computational devices, to solve problems of a large-scale nature. Consequently, a number of algorithms have appeared in the literature in recent times, each geared towards ameliorating the above curse. The purpose of this paper is to present a didactic …