Search

Lately, the problem of cell formation (CF) has gained a lot of attention in the industrial engineering literature. Since it was formulated (more than 50 years ago), the problem has incorporated additional industrial factors and constraints while its solution methods have been constantly improving in terms of the solution quality and CPU times. However, despite all the efforts made, the available solution methods (including those for a popular model based on the p-median problem, PMP) are prone to two major types of errors. The first error (the modeling one) occurs when the intended objective function of the CF (as a rule, verbally formulated) is substituted by the objective function of the PMP. The second error (the algorithmic one) occurs as a direct result of applying a heuristic for solving the PMP. In this paper we show that for instances that make sense in practice, the modeling error induced by the PMP is negligible. We exclude the algorithmic error completely by solving the adjusted pseudo-Boolean formulation of the PMP exactly, which takes less than one second on a general-purpose PC and software. Our experimental study shows that the PMP-based model produces high-quality cells and in most cases outperforms several contemporary approaches. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of the sampled version of the fictitious play algorithm, familiar from game theory, for games with identical payoffs, and propose a heuristic based on fictitious play as a solution procedure for discrete optimization problems of the form max {u(y) y = (y1,…yn ∈ y1 x … x yn} i.e., in which the feasible region is a Cartesian product of finite sets y1 i ∈ N = (1, …, n). The contributions of this paper are twofold. In the first part of the paper, we broaden the existing results on convergence properties of the fictitious play algorithm on games with identical payoffs to include an approximate fictitious play algorithm that allows for errors in players 'best replies. Moreover, we introduce sampling-based approximate fictitious play that possesses the above convergence properties, and at the same time provides a computationally efficient method for implementing fictitious play. In the second part of the paper, we motivate the use of algorithms based on sampled fictitious play to solve optimization problems in the above form with particular focus on the problems in which the objective function u(·) comes from a "black box," such as a simulation model, where significant computational effort is required for each function evaluation. [ABSTRACT FROM AUTHOR]

This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all ‘sufficiently large’ values of t], and (2) sensitivity analysis [if a value t0 of ‘time’ is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t ‘sufficiently dose’ to t0 (the first functional form valid for t«t0, the second for t»t0)]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn↗+∞ such that the linear program at tn has this property for all n, then the program has this property for all ‘sufficiently large’ values of t. [ABSTRACT FROM AUTHOR]

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]

One approach to coping with the apparent difficulty of many schedule-optimization problems, such as occur in machine shops and computer processing, is to devise efficient algorithms that find schedules guaranteed to be "near-optimal." This paper presents an introduction to this approach by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible. The paper concludes with a brief survey of what has been accomplished to date in the area of scheduling using this approach. [ABSTRACT FROM AUTHOR]

Sensor systems as critical components of a transportation network provide a variety of real-time traffic surveillance information for traffic management and control. The deployment of sensors significantly affects their overall surveillance effectiveness. This paper proposes a reliable sensor location model to optimize surveillance effectiveness when sensors are subject to site-dependent probabilistic failures, and a general effectiveness measure is proposed to encompass most existing measures needed for engineering practice (e.g., flow volume coverage, vehicle-mile coverage, and squared error reduction). The problem is first formulated into a compact mixed-integer program, and we develop a variety of solution algorithms (including a custom-designed Lagrangian relaxation algorithm) and analyze their properties. We also propose alternative formulations including a continuum approximation model for single corridor problems and reliable fixed-charge sensor location models. Numerical case studies are conducted to test the performance of the proposed algorithms and draw managerial insights on how different parameter settings (e.g., failure probability and spatial heterogeneity) affect overall surveillance effectiveness and the optimal sensor deployment. [ABSTRACT FROM AUTHOR]

This paper develops a methodology to evaluate various aspects of logistics supply support of space bases. It is assumed that there exists at the space base a schedule of operations that reflects the day-to-day living, build-up, and scientific experimental activities that are to be carried on. These activities, in turn, set a series of demands or requirements for products over a time spectrum. The supply system must deliver products so as to meet the amounts and times of the product requirements. Each product or module has an earliest and latest time by which it must be delivered. A mathematical model is developed that plans a series of trips, the dates at which each is to be sent, and the composition of the cargoes on each trip that satisfy the series of requirements over a time spectrum imposed by the activities at the space base. The series of trips are an expression of an efficient plan that simultaneously considers demands for different products at different future times and observes the various constraints of the system (e.g., cargo capacity of spaceships). The mathematical formulation of this scheduling problem is a simple non- linear discrete programming problem. An algorithm has been developed for its solution, and a description thereof is presented. The model is illustrated by showing how it would supply a long-term lunar base. Various uses of the model are described. [ABSTRACT FROM AUTHOR]

Model reference adaptive search (MRAS) for solving global optimization problems works with a parameterized probabilistic model on the solution space and generates at each iteration a group of candidate solutions. These candidate solutions are then used to update the parameters associated with the probabilistic model in such a way that the future search will be biased toward the region containing high-quality solutions. The parameter updating procedure in MRAS is guided by a sequence of implicit probabilistic models we call reference models. We provide a particular algorithm instantiation of the MRAS method, where the sequence of reference models can be viewed as the generalized probability distribution models for estimation of distribution algorithms (EDAs) with proportional selection scheme. In addition, we show that the model reference framework can also be used to describe the recently proposed cross-entropy (CE) method for optimization and to study its properties. Hence, this paper can also be seen as a study on the effectiveness of combining CE and EDAs. We prove global convergence of the proposed algorithm in both continuous and combinatorial domains, and we carry out numerical studies to illustrate the performance of the algorithm. [ABSTRACT FROM AUTHOR]

We study the classical multistage lot sizing problem that arises in distribution and inventory systems. A celebrated result in this area is the 94% and 98% approximation guarantee provided by power-of-two policies. In this paper, we propose a simple randomized rounding algorithm to establish these performance bounds. We use this new technique to extend several results for the capacitated lot sizing problems to the case with submodular ordering cost. For the joint replenishment problem under a fixed base period model, we construct a 95.8% approximation algorithm to the (possibly dynamic) optimal lot sizing policy. The policies constructed are stationary but not necessarily of the power-of-two type. This shows that for the fixed based planning model, the class of stationary policies is within 95.8% of the optimum, improving on the previously best known 94% approximation guarantee. [ABSTRACT FROM AUTHOR]

This paper proposes an optimization model of incorporating competence sets of group decision makers to maximize the total benefit of the whole group. Such an incorporation model is formulated as finding a deduction graph linked from the nodes of existing competencies to the nodes of desired competencies. Compared with other methods treating competence set problems (Yu and Zhang 1991, Li and Yu 1994, and Shi and Yu 1996), the proposed model can solve problems involving multiple decision makers; in addition it allows the network to be cyclic and to contain compound nodes. [ABSTRACT FROM AUTHOR]

This paper discusses technical aspects of the Russell-Yasuda Kasai financial planning model. These include the models for the discrete distribution scenario generation processes for the uncertain parameters of the model, the mathematical approach used to develop the infinite-horizon end-effects part of the model, a comparison of algorithms used in the model's solution, and a comparison of the multistage stochastic linear programming model with the previous technology, static mean-variance analysis. Experience and benefits of the model in Yasuda-Kasai's financial planning process is also discussed. [ABSTRACT FROM AUTHOR]

Two major decisions are made when scheduling the operations of a fossil-fuel power-generating system over a short time horizon. The "unit commitment" decision indicates what generating units are to be in use at each point in time. The "economic dispatch" decision is the allocation of system demand among the generating units in operation at any point in time. Both these decisions must be considered to achieve a least-cost schedule over the short time horizon. In this paper we present a mixed integer programming model for the short time horizon power-scheduling problem. The objective of the model is to minimize the sum of the unit commitment and economic dispatch costs subject to demand, reserve, and generator capacity and generator schedule constraints. A branch-and-bound algorithm is proposed using a Lagrangian method to decompose the problem into single generator problems. A subgradient method is used to select the Lagrange multipliers that maximize the lower bound produced by the relaxation. We present computational results that indicate the technique is capable of solving large problems to within acceptable error tolerances. [ABSTRACT FROM AUTHOR]

Necessary and sufficient conditions have been given that characterize the data for which a greedy algorithm solves the coin-changing problem. In this paper we study the problem of maximum percentage error when the greedy solution does not work. We also generalize a result of Johnson and Kernighan to the case for which each coin is of different weight. [ABSTRACT FROM AUTHOR]

This paper presents a 'one-pass' algorithm that determines an 'advanced' dual basic feasible solution for a class of capacitated generalized network problems. Special cases in this class of problems include transportation and transshipment problems. We include computational results that show that this new start substantially improves the solution performance of the dual method for transportation and transshipment problems. In fact, a dual code employing this advanced start is found to be faster (in terms of total solution time) than the fastest out-of-kilter code SUPERK on highly rectangular transportation problems. [ABSTRACT FROM AUTHOR]

This paper treats the problem of locating a given number of interrelated physical facilities in a single- or multi-story building as an optimization model such that the weighted sum of the distances along orthogonal directions is minimized, and describes a constructive heuristic algorithm for the one-dimensional model. This linear placement algorithm is then extended to higher dimensions for placing uniform-size equipment modules at homogeneous fixed locations. The algorithm accommodates lower-bound constraints for the linear case efficiently and produces near-optimal solutions. Its significance, as demonstrated by comparison with some existing heuristic procedures, is that it has the capability of handling efficiently problems with large numbers of equal-size facilities whose solutions are computationally intractable using the present optimum-producing methods. [ABSTRACT FROM AUTHOR]

This paper develops a nonlinear bilevel programming model of an aluminium smelter that is capable of representing all the major production processes. The model encompasses all the areas of the smelter which operates in a multilevel way. However, as shown, it can be reduced quite simply to a bilevel programming problem. The problem specification involves nonlinearities with respect to the variables and the presence of ratios among the constraints. The problem is also characterized by a two-way material flow in the production process. A relatively simple solution algorithm that facilitates the attainment of the global optimum is developed. While the problem specification appears daunting, a number of simplifications can be made, due to nature of the problem, allowing its quick solution. While the model developed in this paper together with the solution algorithm appear simple, considerable effort was required to identify the fundamental relationships in the aluminium smelting process, quantify them, and then develop appropriate expressions to represent them. It is believed that the solution of this class of nonlinear bilevel programming problems will have implications for other applications. [ABSTRACT FROM AUTHOR]

This paper considers a stochastic fluid model of a buffer content process {X(t), t ⩾ 0} that depends on a finite-state, continuous- time Markov process {Z(t), t ⩾ 0} as follows: During the time-intervals when Z(t) is in state i, X(t) is a Brownian motion with drift μt, variance parameter τt² and a reflecting boundary at zero. This paper studies the steady-state analysis of the bivariate process {(X(t), Z(t)), t ⩾ 0} in terms of the eigenvalues and eigenvectors of a nonlinear matrix system. Algorithms are developed to compute the steady-state distributions as well as moments. Numerical work is reported to show that the variance parameter has a dramatic effect on the buffer content process. [ABSTRACT FROM AUTHOR]

Many problems in inventory control, production planning, and capacity planning can be formulated in terms of a simple economic lot size model proposed independently by A. S. Manne (1958) and by H. M. Wagner and T. M. Whitin (1958). The Manne-Wagner-Whitin model and its variants have been studied widely in the operations research and management science communities, and a large number of algorithms have been proposed for solving various problems expressed in terms of this model, most of which assume concave costs and rely on dynamic programming. In this paper, we show that for many of these concave cost economic lot size problems, the dynamic programming formulation of the problem gives rise to a special kind of array. called a Monge array. We then show how the structure of Monge arrays can be exploited to obtain significantly faster algorithms for these economic lot size problems. We focus on uncapacitated problems, i.e., problems without bounds on production, inventory, or backlogging: capacitated problems are considered in a separate paper. [ABSTRACT FROM AUTHOR]

This paper presents a method for finding optimal flows in a dynamic network with random inputs into the system and congestion limits on flow. This model has been used in deterministic settings to represent dynamic traffic assignment and job shop routing. This paper builds on the deterministic results to show that a globally optimal solution in the stochastic problem may be obtained by a sequence of linear optimizations. A decomposition algorithm for this procedure is presented that efficiently solves problems with large-scale deterministic equivalents of up to 66,000 variables. [ABSTRACT FROM AUTHOR]

This paper describes some experiments with two alternative formulations of a nonlinear programming model. One apparently suitable formulation proves to be numerically disastrous for several algorithms. The paper discusses the reasons for this behavior and argues that solution systems need to be strengthened so that they can cope with alternative model formulations. As argued in the paper, it would be desirable to improve the numerical algorithms themselves, or to develop computerized modeling systems that can reformulate models into the form most suitable for a particular existing algorithm. [ABSTRACT FROM AUTHOR]

This paper considers a discrete location-allocation problem for simultaneously determining the location of a given number of capacitated facilities on certain predesignated sites, and the allocation of their products among a fixed number of customers. The objective is to determine the location and (subsequent) allocation that minimizes the total cost of construction (or location), production, and transportation. The formulation of this model is a specially structured, generally nonconvex problem. However, we specify certain sufficient conditions for the solution to two network-structured linear programs to provide an optimal solution to this problem. For other situations, we present an implicit enumeration algorithm within the framework of Benders' decomposition method, which fully exploits the structure of the problem. This method is an improvement over traditional Lagrangian approaches. Computational experience is provided to demonstrate the practicality of this algorithm for reasonable size problems, as well as its superiority over alternative implicit enumeration schemes. This paper also sheds light on the general implementation of Benders' decomposition technique. [ABSTRACT FROM AUTHOR]

This paper considers the problem of determining the policy to be followed by each member of a team so as to optimize some over-all criterion function characterizing the objective of the team. The reasoning of dynamic programming is employed to formulate the optimization problem, and the discussion is couched in the terms of a classical network problem. The paper first formulates a simple bipartite network optimization and then presents a number of generalizations. Finally, it gives two slightly different computational solutions to an example bipartite optimization problem. [ABSTRACT FROM AUTHOR]

We study lot-size policies in a serial, multistage manufacturing/inventory system with two key generalizations, namely (1) random yields at each production stage and (2) an autoregressive demand process. Previous research shows that the optimal policies in models with random yields (even in models with a single installation) lack the familiar order-up-to structure and are not myopic. Thus, dynamic programming algorithms are needed to compute optimal policies, and one encounters the "curse of dimensionality"; this is exacerbated here by the need to expand the size and dimension of the state space to accommodate the autoregressive demand feature. Nevertheless, although our model is more complex, we prove that there is an optimal policy with the order-up-to feature and, more importantly, that the optimal policy is myopic. This avoids the computational burden of dynamic programming. Our results depend on two assumptions concerning the stochastic yield, namely that the expected yield at a work station is proportional to the lot size, and the distribution of the deviation of the yield from its mean does not depend on the lot size. We introduce the concept of echelon-like variables, a generalization of Clark and Scarf's classical concept of echelon variables, to derive the structure of optimal policies. Furthermore, we show that the same kind of policy is optimal for several criteria: infinite-horizon discounted cost, infinite-horizon long-run average cost, and finite-horizon discounted cost (with the appropriate choice of the salvage value function). [ABSTRACT FROM AUTHOR]

This paper presents a branch-and-bound algorithm for solving fixed charge transportation problems where not all cells exist. The algorithm exploits the absence of full problem density in several ways, thus yielding a procedure which is especially applicable to solving real world problems which are normally quite sparse. Additionally, streamlined new procedures for pruning the decision tree and calculating penalties are presented. We present computational experience with both a set of large test problems and a set of dense test problems from the literature. Comparisons with other codes are uniformly favorable to the new method, which runs more than twice as fast as the best alternative. [ABSTRACT FROM AUTHOR]

This paper proposes a new approach and develops an efficient algorithm for solving a class of (simplified) portfolio selection problems. The approach is based on the technique of parametric principal pivoting. The algorithm is particularly suited for problems with special structure and can handle potentially large problems. When specialized to the multiple index model, the algorithm achieves enormous savings in computer storage and computations. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm to compute reliability measures on a stochastic network m which both nodes and links can fad The measures considered are the probability that nodes s and t can communicate for all node pairs s and t, the probability that all operative node pairs can communicate, and the expected number of node pairs communicating It also computes the latter two measures when all communication must proceed through a root node A specialized version of the algorithm is given for networks in which only nodes can fail. [ABSTRACT FROM AUTHOR]

We prove that a necessary and sufficient condition for the primal and dual solution sets of a solvable, finite-dimensional linear programming problem to be stable under small but arbitrary perturbations in the data of the problem is that both of these sets be bounded. The distance from any pair of solutions of the perturbed problem to the solution sets of the original problem is then bounded by a constant multiple of the norm of the perturbations. These results extend earlier work of Williams. [ABSTRACT FROM AUTHOR]

In this note we present some computational evidence to suggest that a version of Bellman's shortest-path algorithm outperforms Treesort-Dijkstra's for a certain class of networks. [ABSTRACT FROM AUTHOR]

A previous research report of the authors presented a formal model of the one-machine job-shop scheduling problem with variable labor capacity. This report presents some computational experience with the algorithm proposed previously and a discussion of the structural aspects of the problem. Extensions and refinements of the algorithm are introduced to deal with nonsimultaneous job arrivals and the production smoothing problem. These results provide insight into the structure of the aggregate-detailed cost trade-off problem and suggest a good heuristic decision rule for problems of realistic size and complexity. [ABSTRACT FROM AUTHOR]

Since it is safer and less expensive to absorb delays on the ground, air traffic control management tries to limit the duration of airborne delays by holding aircraft previous to departure when congestion at the airport of destination is anticipated. The problem of assigning appropriate ground-holds to aircraft is known as the ground-holding problem. Ground-holding decisions must be implemented in real time and for multiple airports; therefore, the speed of solution for algorithms is critical. This paper tests static and dynamic optimal solutions, and a very fast heuristic for the assignment of ground-holds in air traffic control. The optimal solutions are based on stochastic linear programming. The heuristic incorporates elements of stochastic modeling by utilizing information conveyed by a probabilistic forecast of airport landing capacity, while taking into consideration the dynamic nature of the problem. In extensive computational experiments based on data for Logan airport, the heuristic performed significantly better than the optimal static solution, a deterministic solution, and the passive strategy of no-ground-holds; and within 5% of the optimal dynamic solution at a fraction of the computational time. Due to its remarkable efficiency, the stochastic-dynamic heuristic appears to be a promising building block in the development of fast ground-holding algorithms for the complete network of airports. [ABSTRACT FROM AUTHOR]

This paper concerns the throughput rate of multistation reliable production lines with no intermediate buffers. Processing times at the service stations are independent, exponential random variables, possibly with different means. We extend the work started in E. J. Muth (1984) to provide an algorithm that allows for the efficient computation of longer lines and to provide results for the nonidentical server case. A result is presented which provides the distribution function of the holding time at the stations. [ABSTRACT FROM AUTHOR]

In this paper we study the nonlinear resource allocation problem, defined as the minimization of a convex function over one convex constraint and bounded integer variables. This problem is encountered in a variety of applications, including capacity planning in manufacturing and computer networks, production planning, capital budgeting, and stratified sampling. Despite its importance to these and other applications, the nonlinear resource allocation problem has received little attention in the literature. Therefore, we develop a branch-and-bound algorithm to solve this class of problems. First we present a general framework for solving the continuous-variable problem. Then we use this framework as the basis for our branch-and-bound method. We also develop reoptimization procedures and a heuristic that significantly improve the performance of the branch-and-bound algorithm. In addition, we show how the algorithm can be modified to solve nonconvex problems so that a concave objective function can be handled. The general algorithm is specialized for the applications mentioned above and computational results are reported for problems with up to 200 integer variables. A computational comparison with a 0, 1 linearization approach is also provided. [ABSTRACT FROM AUTHOR]

This paper considers a specially structured uncapacitated facility location problem. We show that several problems, including certain tool selection problems, substitutable inventory problems, supplier sourcing problems, discrete lot sizing problems, and capacity expansion problems, can be formulated as instances of the problem. We also show that the problem with m facilities and n customers can be solved in O(mn), as a shortest path problem on a directed graph. [ABSTRACT FROM AUTHOR]

We consider a production/distribution system represented by a general directed acyclic network. Each node is associated with a specific "product" at a given location and/or production stage. An arc (i, j) indicates that item i is used to "produce" item j. External demands may occur at any of the network's nodes. These demands occur continuously at item-specific constant rates. Components may be assembled in any given proportions. The cost structure consists of inventory carrying, variable, and fixed production/distribution costs. The latter depend, at any given replenishment epoch, on the specific set of items being replenished, according to an arbitrary set function merely assumed to be monotone and submodular. It has been shown that a simply structured, so-called power-of-two policy is guaranteed to come within 2% of a lower bound for the minimum cost. In this paper, we derive efficient algorithms for the computation of an optimal power-of-two policy, possibly in combination with this lower bound. These consist of a limited number of polymatroidal maximum flow calculations in networks closely associated with the original production/distribution network. [ABSTRACT FROM AUTHOR]

This is the second half of a two-part survey on arc routing problems. The first part appeared in the March-April 1995 issue of this journal. Here, the rural postman problem (RPP) is reviewed. The paper is organized as follows: applications, the undirected RPP, the directed RPP, the stacker crane problem, and the capacitated arc routing problem. [ABSTRACT FROM AUTHOR]

This paper discusses the distributional Little's law and examines its applications in a variety of queueing systems. The distributional law relates the steady-state distributions of the number in the system (or in the queue) and the time spent in the system (or in the queue) in a queueing system under FIFO. We provide a new proof of the distributional law and in the process we generalize a well known theorem of Burke on the equality of pre-arrival and postdeparture probabilities. More importantly, we demonstrate that the distributional law has important algorithmic and structural applications and can be used to derive various performance characteristics of several queueing systems which admit distributional laws. As a result, we believe that the distributional law is a powerful tool for the derivation of performance measures in queueing systems and can lead to a certain unification of queueing theory. [ABSTRACT FROM AUTHOR]

We show that an O(n³ log n) algorithm can find optimal power-of-two lot size policies for finite production rate assembly systems. This improves an O(n5) algorithm proposed in D. Atkins, M. Queyranne and D. Sun's 1992 paper. [ABSTRACT FROM AUTHOR]

A reconfigurable network is a circuit-switched network where the effective topology and capacities can be dynamically adapted to changes in the traffic requirements or to changes in the structure of the network due to failures. The application of reconfigurable networks considered in this paper is data communications. We formulated the joint topology, capacity and routing problem in a reconfigurable network as a nonlinear, mixed integer programming problem. To solve this problem, we present a partial branch-and-bound algorithm. The reduced gradient method is used to solve the problem with the integrality constraints relaxed. Lagrangian relaxation is applied to obtain lower bounds. In the computational experiments, the algorithm found good solutions in a few minutes of CPU time. In addition, the reduction in the minimal delay due to the reconfiguration capability can be as large as 62%. [ABSTRACT FROM AUTHOR]

In this paper, we study a single-item continuous-review inventory system with Poisson demand. In addition to the standard cost structure of a fixed setup cost and a quasiconvex expected inventory holding and shortage cost, special opportunities for placing orders at a discounted setup cost occur according to a Poisson process that is independent of the demand process. This model has been studied as a subproblem of multi-item/location inventory systems where there are economies-of-scale in joint replenishment. For the single-item model, the literature proposes the (s, c, S) policy, under which an order is placed to increase the inventory position to S either when the inventory position drops to s, or when the inventory position is at or below c and a discount opportunity occurs. We prove that the (s, c, S) policy is optimal for the model, develop an efficient algorithm for computing optimal control parameters s*, c*, S* and carry out a parametric analysis showing the effects of changes in problem parameters on the optimal control parameters and the minimum cost. [ABSTRACT FROM AUTHOR]

Maximum average weight ideal problems in ordered sets arise from modeling variants of the investment problem and, in particular, learning problems in the context of concepts with tree-structured attributes in artificial intelligence. Similarly, trying to construct tests with high reliability leads to a nontrivial maximum average weight ideal problem. This paper investigates the computational complexity and shows that the general problem is NP-complete. Important special cases (e.g., finding rooted subtrees of maximal average weight), however, can be handled with efficient algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present two algorithms for a machine allocation problem occurring in manufacturing systems. For the two algorithms presented we prove worst-case performance ratios of 2 and 3/2, respectively. The machine allocation problem we consider is a general convex resource allocation problem, which makes the algorithms applicable to a variety of resource allocation problems. Numerical results are presented for two real-life manufacturing systems. [ABSTRACT FROM AUTHOR]

Given a complete directed graph G = (V, A), the delivery man problem (DMP) consists of determining a Hamiltonian circuit minimizing the sum of distances (along the circuit) from a given vertex v1, to every vertex of V, including v1 itself. There exists a number of applications of the DMP in the fields of distribution and machine scheduling. The DMP is NP-hard. The objective of this paper is to develop new theoretical results and an exact algorithm for the problem. A new, integer linear programming formulation is provided, and results on the matroidal structure of a class of combinatorial problems are developed. These are used to derive lower bounds for the DMP. These bounds are embedded into an enumerative algorithm. The largest problems solved to optimality with the proposed algorithm involve 60 vertices. This compares favorably with previously published methods. [ABSTRACT FROM AUTHOR]

This paper investigates the application of a new class of neighborhood search algorithms--cyclic transfers--to multivehicle routing and scheduling problems. These algorithms exploit the two-faceted decision structure inherent to this problem class: First, assigning demands to vehicles and, second, routing each vehicle through its assigned demand stops. We describe the application of cyclic transfers to vehicle routing and scheduling problems. Then we determine the worst-case performance of these algorithms for several classes of vehicle routing and scheduling problems. Next, we develop computationally efficient methods for finding negative cost cyclic transfers. Finally, we present computational results for three diverse vehicle routing and scheduling problems, which collectively incorporate a variety of constraint and objective function structures. Our results show that cyclic transfer methods are either comparable to or better than the best published heuristic algorithms for several complex and important vehicle routing and scheduling problems. Most importantly, they represent a novel approach to solution improvement which holds promise in many vehicle routing and scheduling problem domains. [ABSTRACT FROM AUTHOR]

One of the most important functions of air traffic management systems is the assignment of ground-holding times to flights, i.e., the determination of whether and by how much the take-off of a particular aircraft headed for a congested part of the ATC system should be postponed to reduce the likelihood and extent of airborne delays. In this paper, we will present an analysis of the fundamental case in which flights from many origins must be scheduled for arrival at a single, congested airport. We will describe a set of approaches for addressing a deterministic and a stochastic version of the problem. A minimum cost flow algorithm can be used for the deterministic problem. Under a particular natural assumption regarding the functional form of delay costs, a very efficient, simple algorithm is also available. For the stochastic version, an exact dynamic programming formulation turns out to be impractical for typical instances of the problem and we present a number of heuristic approaches to it. The models and numerical results suggest the potential usefulness of formal decision support tools in developing effective ground-holding strategies. Many methodological and implementation issues, however, still require resolution. [ABSTRACT FROM AUTHOR]

In this paper, we develop a stochastic, multiclass network equilibrium model of airline passenger transportation. The model explicitly incorporates the behavior of the passengers in regard to the decision whether or not to travel, and route selection, and formalizes the passenger's decision as an abstract network. The equilibrium between the realized demand for the routes of travel and the supply of the seats is shown to satisfy a system of nonlinear equations. A Gauss-Seidel algorithm is then proposed for the computation of the equilibrium and conditions for convergence are established. Finally, the algorithm is applied to compute the solution to the national Air Canada airline passenger network, and the output is compared to the actual observed flows. [ABSTRACT FROM AUTHOR]

In this paper, we present a new strongly polynomial time algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(n log n) shortest path problems on networks with n nodes and m arcs and runs in O(n log n (m + n log n)) time. Using a standard transformation, this approach yields an O(m log n (m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial time algorithm, due to Z. Galil and E. Tardos, by a factor of n²/m. Our algorithm for the capacitated minimum cost flow problem is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. In this case, the running time of the algorithm is O((m' + n)log n(m + n log n)). [ABSTRACT FROM AUTHOR]

Partitioning methods lend themselves very well to implementation on parallel computers. In recent years, branch-and-bound algorithms have been tested on various types of architectures. In this paper, we develop a queueing network model for the analysis of a class of branch-and-bound algorithms on a master-slave architecture. The analysis is based on a fluid flow approximation. Numerical examples illustrate the concepts developed. Finally, related branch-and-bound algorithms are studied using a machine repair queueing model. [ABSTRACT FROM AUTHOR]

Frequency domain methodology has been applied to discrete-event simulations to identify terms m a polynomial model of the simulation output. In this paper, the problem of optimally selecting input frequencies is studied. A fast algorithm is presented that closely approximates the optimal solution. The results obtained from the algorithm are compared to known optimal solutions. Tables of input frequencies for various experiments are presented in an appendix. [ABSTRACT FROM AUTHOR]

T = (V, E) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex v[sub 1]. The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q; a linear combination of the number of vehicles and of the total distance traveled by these vehicles is minimized. The TCVRP is shown to be NP-hard. This paper presents lower bounds for the TCVRP based on the solutions of associated bin packing problems. We develop a linear time heuristic (upper bound) procedure and present a bound on its worst case performance. These lower and upper bounds are then embedded in an enumerative algorithm. Numerical results follow. [ABSTRACT FROM AUTHOR]

We consider problems on networks that are captured by two performance measures. One performance measure is any general cost function of a solution; the other is a bottleneck measure that describes the worst (maximum cost) component of the solution. The paper contains algorithms to solve three problems. In one problem, we minimize the bottleneck subject to a constraint on the generalized cost. In the second problem, we minimize the generalized cost subject to a constraint on the bottleneck. In the third problem, we consider the two criteria simultaneously and find all the Pareto optimum solutions. The major result is that the introduction of the bottleneck measure changes the complexity of the original (general cost) problem by a factor which is at most linear in the number of links. [ABSTRACT FROM AUTHOR]