Search

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

This Note points out a minor error in a technique developed by Soyster and Lev [1] for determining if a linear goal can be substituted for a fractional goal in a goal programming problem. A revised formulation is provided. [ABSTRACT FROM AUTHOR]

The article presents the author's comments about the article "Supply, Shortage, and Service Reliability Decisions by Gas Distribution Utilities: A Chance-Constrained Approach," by Jean-Michel Guildmann. The author focuses on the cost effectiveness associated with Guildmann's mathematical model. It is suggested that management scientists consider the applications of Guildmann's mathematical optimization problem when faced with critical decisions regarding the future of the gas market. The author proposes that the analytical framework proposed by Guildman may be useful when making decisions regarding industrial capacity.

The technique of perturbation analysis has recently been introduced as an efficient way to compute parameter sensitivities for discrete event systems. Thus far, the statistical properties of perturbation analysis have been validated mainly through experiments. This paper considers, for an M/G/1 queueing system, the sensitivity of mean system time of a customer to a parameter of the arrival or service distribution. It shows analytically that (i) the steady state value of the perturbation analysis estimate of this sensitivity is unbiased, and (ii) a perturbation analysis algorithm implemented on a single sample path of the system gives asymptotically unbiased and strongly consistent estimates of this sensitivity. (No previous knowledge of peturbation analysis is assumed, so the paper also serves to introduce this technique to the unfamiliar reader.) Numerical extensions to GI/G/1 queues, and applications to optimization problems, are also illustrated. [ABSTRACT FROM AUTHOR]

One of the important uses of an EOQ item's distribution of lead time demand is to set its reorder point. This paper shows that a realistic model of observed demand patterns can be chosen from the compound Poisson family of distributions. Actual historical data from several U.S. Air Force bases are analyzed using the geometric-Poisson and constant-Poisson distributions. The control discipline is order quantity, reorder point with continuous review. The service level is based on percent of demand supplied during lead time and is consistent with current USAF methodology. The reorder point is based on independent calculations and no attempt is made to jointly optimize the order quantity and reorder point. Lead time is assumed to be known and constant. [ABSTRACT FROM AUTHOR]

This paper presents a new information acquisition problem motivated by business applications where customer data has to be acquired with a specific modeling objective in mind. In the last two decades, there has been substantial work in two different fields—optimal experimental design and machine learning—that has addressed the issue of acquiring data in a selective manner with a specific objective in mind. We show that the problem presented here is different from the classic model-based data acquisition problems considered thus far in the literature in both fields. Building on work in optimal experimental design and in machine learning, we develop a new active learning technique for the information acquisition problem presented in this paper. We demonstrate that the proposed method performs well based on results from applying this method across 20 Web usage and machine learning data sets. [ABSTRACT FROM AUTHOR]

This paper introduces the formal study of process flexibility to the novel domain of sports analytics. In baseball, positional flexibility is the analogous concept to process flexibility from manufacturing. We study the flexibility of players (plants) on a baseball team who produce innings-played at different positions (products). We develop models and metrics to evaluate expected and worst-case performance under injury risk (capacity uncertainty) with continuous player-position capabilities. Using Major League Baseball data, we quantify the impact of flexibility on team and individual performance and explore the player chains that arise when injuries occur. We discover that top teams can attribute at least one to two wins per season to flexibility alone, generally as a result of long subchains in the infield or outfield. The least robust teams to worst-case injury, those whose performance is driven by one or two star players, are over four times as fragile as the most robust teams. We evaluate several aspects of individual flexibility, such as how much value individual players bring to their team in terms of average and worst-case performance. Finally, we demonstrate the generalizability of our framework for player evaluation by quantifying the value of potential free agent additions and uncovering the true "MVP" of a team. Data are available at https://doi.org/10.1287/mnsc.2017.3004. This paper was accepted by Vishal Gaur, operations management. [ABSTRACT FROM AUTHOR]

In classical inverse linear optimization, one assumes that a given solution is a candidate to be optimal. Real data are imperfect and noisy, so there is no guarantee that this assumption is satisfied. Inspired by regression, this paper presents a unified framework for cost function estimation in linear optimization comprising a general inverse optimization model and a corresponding goodness-of-fit metric. Although our inverse optimization model is nonconvex, we derive a closed-form solution and present the geometric intuition. Our goodness-of-fit metric, ρ, the coefficient of complementarity, has similar properties to R2 from regression and is quasi-convex in the input data, leading to an intuitive geometric interpretation. While ρ is computable in polynomial time, we derive a lower bound that possesses the same properties, is tight for several important model variations, and is even easier to compute. We demonstrate the application of our framework for model estimation and evaluation in production planning and cancer therapy. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

This paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives (e.g., submodular functions) and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications. Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

This paper considers the problem of test design and implementation when testing is imperfect. Items that are classified as conforming may be nonconforming, resulting in a poor outgoing quality level. Items that are classified as nonconforming may be conforming, resulting in excessive scrapping of conforming items. The failed items are commonly retested to reduce the scrapping problem. Alternatively, the accepted items may be retested to improve outgoing quality. In this paper, we examine the question of whether it is better to repetitively test rejected items, or to repetitively test accepted items. We also examine the relationship between the two testing policies, testing equipment accuracy and capacity, incoming quality, and outgoing quality requirements. [ABSTRACT FROM AUTHOR]

This paper develops rolling horizon procedures for solving a multistage inventory problem with facilities-in-series. In such an inventory system, we assume that the raw material is processed successively through several facilities before reaching the customer. The input to a facility comes from one preceding facility (or the raw material) and the output from the facility goes to one succeeding facility (or the customer). The rolling horizon procedures form rolling production schedules by solving a finite horizon multiperiod problem and implementing only the first period's decisions. One period later, the multiperiod problem is updated as better forecasts become available and the process is repeated. The paper considers a simple case when holding costs are linear, production costs on a facility consist of a setup cost and a constant marginal cost of production, and production and holding costs are stationary in time. Demand is allowed to be nonstationary in time. Several rolling horizon procedures are developed for this case and a computational comparison is given. [ABSTRACT FROM AUTHOR]

Banking has been a fertile area for management science applications, as is evident from the review provided in this paper. The relevant management science models are discussed in terms of the areas of bank management for which they were intended. Under dynamic balance sheet management (i.e., internal bank financial planning) we consider forecasting techniques, simulation models and optimization models. Other areas of banking included are bond portfolio management, bank operations, corporate services, bank marketing and management of the loan portfolio. The authors provide an evaluation of the applicability of management science models in practice, discuss the extent to which some have been implemented and consider the philosophy of using management science models in banking. [ABSTRACT FROM AUTHOR]

This paper extends previous work on the use of sequential building heuristics for the design of a collection system, a linear fixed-charge problem that includes the design of a lock-box system as an important subproblem. The heuristic extensions in this paper first present simple methods for eliminating "premature termination" (stopping the heuristics while there are still worthwhile alternatives not included in the collection system) and unprofitable inclusion (including collection alternatives with net benefits less than the fixed cost). Initiation procedures that increase computational efficiency and reduce the likelihood of significant suboptimization are presented. Finally, the simple one-at-a-time building procedure is extended to include joint exclusion-building (a limited switching plus building) and combination switching-building rules that consider combinations of alternatives rather than one-at-a-time evaluation. [ABSTRACT FROM AUTHOR]

This paper combines two rival preference modeling techniques in a new approach to multi-attribute decision making. Currently existing multi-attribute procedures use either global or local preference modeling. In the global modeling technique, a single preference function is constructed in the large; its maximum is the optimal alternative. In the local procedure, sequential approximations of the preference function are constructed in the small. Each approximation generates a trial solution. Under suitable conditions, each trial solution is preferred to its predecessor, so the trial sequence eventually reaches the optimum. Each technique has advantages and disadvantages; this paper combines the desirable features of both techniques in a new improved method. This new method, called the proxy approach, uses the advantages of one technique to overcome the disadvantages of the other. This paper first develops the theoretical aspects of the proxy approach and then compares it to existing procedures. Finally, the proxy algorithm is applied to a curriculum planning problem and numerous insights are gained. [ABSTRACT FROM AUTHOR]

The motivation for this paper is a problem faced by banks which process large volumes of deposited checks. The checks must be separated by bank number before shipment to the Federal Reserve or other banks. The sorting is usually accomplished using a reader-sorter which reads the magnetic ink characters on the checks and separates them into different "pockets." This paper characterizes the optimal sorting strategy and describes an efficient procedure for finding the optimal solution for problems of the size generally found in practice. The algorithm is based on a two state dynamic programming recursion in which characterization theorems are used to drastically reduce the size of the state space and in which the storage requirements are minimal. The paper includes an analysis of computational experience and describes how the algorithm can be used in a real time environment with deadlines. [ABSTRACT FROM AUTHOR]

This paper extends the Bierman-Hausman credit-granting model by proving that although the distribution on the probability of collection in the case of failure is no longer a conjugate Beta, it remains tractable; the model therefore need no longer be terminated in the case of failure. Further theorems on the structure of optimal policies, which result in a considerable reduction of the dynamic programming state space, are then presented, and the paper concludes with a discussion of extensions and applications. [ABSTRACT FROM AUTHOR]

Many manufacturing firms produce component parts both for assembly into new products and to meet orders for spare parts. An inventory model for this situation would involve two types of demands: probabilistic demand as spares and deterministic (or scheduled) withdrawals as components for assembly. Relevant costs would include a setup cost for replenishment orders, inventory carrying costs, and backorder costs. An analytical model approximating these characteristics is formulated. An optimal dynamic program for the periodic review case is briefly discussed; this policy is extremely costly to implement, however. Two feasible operating policies are considered in the paper: a continuous review (Q, r)-type policy and a simple periodic review scheduling heuristic. The paper concludes with sample economic comparisons of the cost of the (Q, r)-type policy and the heuristic policy for a set of numerical examples. [ABSTRACT FROM AUTHOR]

In an earlier paper [5], we generalized and extended Beckmann's results [1] for a production and inventory problem with proportional smoothing costs and demands being random variables. Our previous results concerned the finite horizon nonstationary case. Here we consider the infinite horizon stationary case. Two curves in the plane determine an optimal policy. They are shown to have slopes between minus one and zero, to be differentiable, and to be bounded by two straight lines with a slope Of minus one. These results are used (a) to accelerate each iteration of a successive approximations algorithm and (b) to formulate a linear programming problem from whose solution an optimal policy can be determined. [ABSTRACT FROM AUTHOR]

The paper presents a method for solving the linear programming problems, which is itself a step towards the generalization of the classical Simlex Method. It replaces two basic variables by two non-basic variables at each iteration. Naturally this will reduce the total number of steps to reach the final solution. The paper also includes the solution of one example to illustrate the applicability of the method. [ABSTRACT FROM AUTHOR]

This paper considers non-linear programming models in which randomized solutions are allowed. That is, we consider the minimization of the expected value of a non-linear function subject to constraints on the expectation of nonlinear functions, where the expectations are taken with respect to randomized decision strategies. Saddle-point and related optimality conditions similar to those given in [10] and [11] for convex functions are obtained with only very mild restrictions on the shape of the optimizing and constraint functions. We also consider when the optimal solution need not be randomized and how the notions of Lagrange multipliers and game theory are related to our results. We offer an economic interpretation of our solution. A few simple examples are given to illustrate the implications of randomized strategies. It is also pointed out how the results of this paper are related to the decomposition methods widely used to solve mathematical programming problems. [ABSTRACT FROM AUTHOR]

This paper introduces an efficient branch and bound algorithm for a special class of mixed integer programming problems called the warehouse location problem. A set of branching decision rules is proposed for selecting warehouses to be constrained open and closed from any node of the branch and bound tree. These rules are tested for their efficiency in reducing computation times and storage requirements to reach optimal solutions. An improved method of solving the linear programming problems at the nodes which substantially reduces the computations is also introduced in this paper. [ABSTRACT FROM AUTHOR]

We study periodic-review inventory replenishment problems with fixed ordering costs, and show the optimality of (s, S) inventory replenishment policies. Inventory replenishment is instantaneous, i.e., the lead time is zero. We consider several sales mechanisms, e.g., auction mechanisms, name-your-own-price mechanisms, and multiple heterogeneous sales channels. We prove this result by showing that these models satisfy a recently-established sufficient condition for the optimality of (s, S) policies. Thus, this paper shows that the optimality of (s, S) policies extends well beyond the traditional sales environments studied so far in the inventory literature. [ABSTRACT FROM AUTHOR]

In this paper, we consider the design of a synchronous, unpaced flow line where workers operate at different skill levels and overtime is used, if necessary, to meet a daily production quota. The line is unpaced in the sense that items only move to the next workstation when all workers on the line have completed their respective tasks. The design problem in this case is to assign both workers and tasks to workstations to minimize the expected sum of regular and overtime costs. To solve this problem, we develop an optimization algorithm for smaller problems and a heuristic algorithm for larger problems, which we use to investigate the sensitivity of total expected cost to changes in the price of overtime, hiring practices, worker differences, and the overall amount of work time variability. Based on an extensive computational analysis, we found that (1) planned overtime is frequently beneficial, (2) more workers should be hired as worker variability increases, and (3) increases in overtime costs frequently yield a relatively lower percentage increase in total expected cost. Other managerial implications are discussed in the paper. [ABSTRACT FROM AUTHOR]

We consider joint learning and optimization problems under a general Cascade Click model. Under this model, customers examine the products in a decreasing order of display, from the top to (potentially) the bottom of the list. At each step, customers can decide to either purchase the current product, forego the current product and continue examining the next product, or simply terminate the search without purchasing any product. We first consider the core pricing problem, where the display position (ranking) of each product is fixed and the only decision that the firm needs to make is pricing. We then consider an extension to the problem of joint ranking and pricing in the presence of filtering options, which the customers can use to filter out some undesirable products. For both problems, we develop Upper Confidence Bound (UCB)-based joint learning and optimization algorithms with theoretical performance guarantees. The key challenge here is in constructing a UCB algorithm that exploits the structure of the Cascade Click model while at the same time taking into account all of the historical click and purchase information. Our numerical results yield three key insights. First, naively applying a standard black box UCB algorithm without adapting it to the Cascade structure is very inefficient and results in a huge loss in total revenues during a finite horizon. Second, applying a learning algorithm by assuming a mis-specified model that ignores the Cascade behavior may result in a highly suboptimal solution. Third, jointly optimizing ranking and pricing can significantly improve performance. Thus, although in practice these decisions are sometimes made separately due to organizational structure, our results suggest that a significant benefit can be realized when the two decisions are more closely coordinated. This paper was accepted by J. George Shanthikumar, big data analytics. [ABSTRACT FROM AUTHOR]

Consider the linear complementarity problem given in the system: (1) W = MZ + q (2) W ≥ 0, Z ≥ 0 (I) (3) Z[sup T] W = 0 where, W, Z and q are vectors of dimension n. M is a matrix of order n x n and Z[sup T] is the transpose of Z. Any (Z, W) satisfying (1), (2), and (3) is a complementary feasible solution to system (I). In the literature, a class of matrices is defined such that if M belongs to this class, then existence of a feasible solution to system (I) implies the existence of a complementary feasible solution to system (I) with W = 0. In this paper, a new class of matrices M is developed. It is shown that membership of a matrix M in M is equivalent to the property; for any q existence of a feasible solution to system (I) implies the existence of a complementary feasible solution to system (I) for that q with W = 0. This new class of matrices is not contained in any one of the known classes, namely, copositive plus, positive definite or semidefinite, P-matrices, P-matrices, Z-class, etc. [ABSTRACT FROM AUTHOR]

This paper first examines the role of ceiling points in solving a pure, general integer linear programming problem (P). Several kinds of ceiling points are defined and analyzed and one kind called "feasible 1-ceiling points" proves to be of special interest. We demonstrate that all optimal solutions for a problem (P) whose feasible region is nonempty and bounded are feasible 1-ceiling points. Consequently, such a problem may be solved by enumerating just its feasible 1-ceiling points. The paper then describes an algorithm called the Heuristic Ceiling Point Algorithm (HCPA) which approximately solves (P) by searching only for feasible 1-ceiling points relatively near the optimal solution for the LP-relaxation; such solutions are apt to have a high (possibly even optimal) objective function value. The results of applying the HCPA to 48 test problems taken from the literature indicate that this approach usually yields a very good solution with a moderate amount of computational effort. [ABSTRACT FROM AUTHOR]

We consider the problem of finding the minimum number of vehicles required to visit once a set of nodes subject to time window constraints, for a homogeneous fleet of vehicles located at a common depot. This problem can be formulated as a network flow problem with additional time constraints. The paper presents an optimal solution approach using the augmented Lagrangian method. Two Lagrangian relaxations are studied. In the first one, the time constraints are relaxed producing network subproblems which are easy to solve, but the bound obtained is weak. In the second relaxation, constraints requiring that each node be visited are relaxed producing shortest path subproblems with time window constraints and integrality conditions. The bound produced is always excellent. Numerical results for several actual school busing problems with up to 223 nodes are discussed. Comparisons with a set partitioning formulation solved by column generation are given. [ABSTRACT FROM AUTHOR]

This note demonstrates that Freeland's (1976) modification of Ruefli's (1971) Generalized Goal Decomposition model can generate nonoptimal solutions and shows how these difficulties can be corrected. In several papers on multi-level planning, it has been suggested that extending the hierarchical levels of the models from two to three or more levels is a straightforward process. This paper shows that this assertion is generally not true. The note points out that in Freeland's (1976) three-level model, the interactions between the two lowest levels of the hierarchy must be strictly controlled before information is passed to the highest level of the organization. [ABSTRACT FROM AUTHOR]

It is well known that all betting systems applied to independent, repeated, and identically distributed trials will result in the same expected gain per average unit wagered as that which applies to a single trial. This paper develops the asymptotic and paradoxical manner in which that constant win rate is maintained for optimal proportional betting according to the Kelly criterion. The appropriateness of using this traditional measure of win rate for proportional betting is contrasted with that of various alternatives. [ABSTRACT FROM AUTHOR]

This paper focuses upon the maximization of labor productivity through selection of the optimal number, duration, and placement of rest breaks. It is demonstrated that resolution of the limited validity associated with previous models leads to a mixed-integer quadratic programming formulation of this problem. Efficient analytic procedures are developed which allow solutions to be obtained in minutes using a hand-held calculator. Then, the characteristics, properties, and potential effectiveness of optimal solutions are examined through an illustration from an existing work environment. Issues relevant to the implementation of the models are presented in a summary of an initial experiment in which one of the models in this paper was used to select rest break policy. The results of this experiment indicated that the output achieved using the model's policy was 13% higher than the output achieved when the subjects used their own rest break policies. Several future research topics are also identified. [ABSTRACT FROM AUTHOR]

In this paper, we describe an integer programming algorithm for assigning tasks on an assembly line to work stations in such a way that the number of work stations is minimal for the rate of production desired. The procedure insures that no task is assigned to a work station before all tasks which technologically must be performed before it have been assigned (precedence restrictions are not violated), and that the total time required at each work station performing the tasks assigned to it does not exceed the time available (cycle time restrictions are not violated). The procedure is based on a systematic evaluation (enumeration) of all possible task assignments to work stations. Significant portions of the enumeration process are performed implicitly, however, by utilizing tests described in the paper which are based on the specific structure of the line balancing problem. An artifice termed a network cut is also developed which eliminates from explicit consideration the assignment of tasks to work stations where such assignments would not lead to improved line balances. Results reported demonstrate that the procedure can obtain optimal balances for assembly lines with between 50 and 100 tasks in a reasonable amount of computation time and with modest computer storage requirements. [ABSTRACT FROM AUTHOR]

Due to the complexity of optimum replacement problems over finite time horizons various asymptotic criteria based upon fixed age replacement policies have been employed in the literature and in practice. In this paper the relationships between the optimum policies under three alternative cost criteria are considered. An ordering of the accounting costs under two of these is obtained, and for distributions with Increasing Hazard Rate an ordering of the optimum replacement time is derived. For a finite time horizon the policies are compared to the optimal sequential and fixed-age replacement polices through the example of a gamma distribution previously investigated by Barlow and Proschan (1962, 1965). [ABSTRACT FROM AUTHOR]

Estimating the annual production cost is a crucial component in long range capacity planning for electric utilities. Traditional simulation-based methods are quite expensive in terms of computer resources (space and time), while simpler mathematical programming-based models generally assume a linear variable production cost. This paper presents a method that incorporates quadratic production costs for each unit and uses optimization submodels to develop a system production cost versus output curve. The method is tested using data from a large southeastern utility. Production cost estimates within one percent of the estimates from a large simulation model were obtained with a small fraction of the simulation model's computing time. The concluding section discusses how the new method might be incorporated in procedures for capacity planning. [ABSTRACT FROM AUTHOR]

This paper examines an important scheduling problem resulting from a new process for continuously casting steel. A master slab caster produces slabs which are wider than customer needs, and therefore, these must be ripped longitudinally at least once before they can be processed to a customer-specified width. The purpose of this research is to develop an effective and efficient algorithm for combining customer sizes in order to economically schedule the ripping process. Such a solution procedure could be used to assist decision-makers in selecting master slab widths for production and in designing width limitations for future casters. The method entails more than the minimization of trim loss because other costs are relevant. Mathematical programming is used to arrive at an optimal or near-optimal solution to this production management problem. The results indicate that the procedure described in this paper reduces to total costs dramatically. [ABSTRACT FROM AUTHOR]

New lock box solution techniques have recently been suggested by Stone and Nauss-Markland. This paper briefly discusses these new methodologies and shows how the algorithms can be combined into a third solution procedure which exploits the computational efficiency of the Stone heuristic and retains the optimizing property of the Nauss-Markland algorithm. [ABSTRACT FROM AUTHOR]

The subject of this paper is a classification and discussion of algorithms for solution of nonlinear pure integer programming problems. The survey is organized by characterizing the mathematical form of the nonlinear optimization problems addressed by the various algorithms. If any method can be used without changes to solve mixed integer nonlinear programming problems that fact is mentioned in the description of the algorithm. However algorithms which must be applied only to mixed integer problems are not surveyed. [ABSTRACT FROM AUTHOR]

When several persons organized as a group are to choose one from among several specified alternatives they may make use of majority voting or some other decision-making process. This paper considers the case in which the decision process includes among the alternatives some that are probability mixtures of others. Examples are presented to illustrate the way in which a situation that is transitive under majority voting rule becomes intransitive when mixtures of the same alternatives are permitted. If utility product maximization is used to determine the group choice, as an agreed upon arbitration process when utilities are assigned to the alternatives by each group member but without interpersonal comparability, some examples are presented to illustrate the results of this method. It is reasoned that some such method is often clearly preferable to majority voting in order both to allot more appropriate influence to minorities and to accommodate for differences in importance of alternatives beyond those represented by individual rank orderings. The utility product maximization section includes several numerical examples to illustrate relationships between the findings of this paper and familiar work in game theory by Nash, and by Luce and Raiffa, where this approach has been suggested as a possible method for "arbitration." Other numerical examples utilize inequalities to illustrate intransitivity effects like those discussed previously by Zeckhauser and Shepsle, and also in the context of Arrow's celebrated lmpossibility Theorem. [ABSTRACT FROM AUTHOR]

This paper considers optimization problems with a nonlinear-additive objective function and a single linear constraint. Such models have numerous direct applications and serve as subproblems in procedures for more complex problems. Some important portfolio selection problems can be expressed in this form, and the problem also arises in economic theory. Several authors have noticed independently that special cases and variants of the problem can be solved exactly by surprisingly simple, finite algorithms. The major purpose of this paper is to present these results in a unified framework, which then permits substantial generalizations and extensions. The results lend themselves to an appealing managerial interpretation, similar to the rate-of-return cutoff rules of capital budgeting. [ABSTRACT FROM AUTHOR]

The increased focus on heuristics for the approximate solution of integer programs has led to more sophisticated analysis methods for studying their performance. This paper is concerned with the worst-case approach to the analysis of heuristic performance. A worst-case study establishes the maximum deviation from optimality that can occur when a specified heuristic is applied within a given problem class. This is an important piece of information that can be combined with empirical testing and other analyses to provide a more complete evaluation of a heuristic. In this paper the basic ground rules of worst-case analysis of heuristics are reviewed, and a large variety of the existing types of worst-case results are described in terms of the knapsack problem. A selected sample of results for four other problems is given. The paper concludes with a discussion of possibilities for further research. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of scheduling "n" independent tasks on "m" parallel processors. Each job consists of a single operation with a specific processing time and due date. The processors are identical and the operation of the system is non-preemptive. The objective is to schedule the jobs in such a way that the total tardiness of the n jobs is as small as possible. For the case of a single processor with n jobs, there exists algorithms which provide optimal solutions. On the other hand currently available optimal scheduling algorithms for multiple processors can handle only small problems. Therefore, practitioners are forced to use heuristic methods to schedule their jobs on multiple processors. This raises questions of the following nature: "Are we scheduling our jobs reasonably well? Are there other schedules with which our total tardiness can be lowered substantially? How far off might the heuristic solution be, from the optimal solution?" The study reported in this paper focuses on a heuristic which can handle reasonably large problems, and yet can be simply and economically implemented. Experiments are conducted by establishing lower bounds for the optimal total tardiness of randomly generated scheduling problems. These lower bounds are then compared with the total tardiness obtained from the heuristic. It is found that the heuristic under study provides solutions which are quite close to the optimal ones. The experiments include 560 randomly generated problems that range from "loose" to "tight" in due dates, with varying numbers of jobs and processors. A nonparametric statistical analysis is presented to generalize the results. [ABSTRACT FROM AUTHOR]

A heuristic algorithm employing dynamic programming is presented for solving the two-dimensional cutting stock problem where all the small rectangles are of the same dimensions, but without the usual restriction that the cutting be done with "guillotine" cuts, i.e., cut which must be made in stages from one edge to the opposite edge of the large rectangle being cut. The objective of the algorithm is to determine a cutting or layout pattern for which the ratio of the unused area to the total area of the large rectangle tends to be small. To demonstrate the method, the common problem of establishing standardized loading patterns for rectangular items on pallets is examined in detail. The algorithm is described with a minimum of mathematics through the use of several pictorial displays and a simple example. The efficiency of the heuristic is then evaluated by comparing computer generated loading patterns for 182 different size items to the loading patterns recommended by the U.S. Navy, and shown to be 10.4 percent more efficient for 64 out of 182 cases when the number of items per layer were not identical. The algorithm is also shown to be an effective aid to management both in establishing standardized loading patterns and procedures, and in communicating these loading standards to production personnel via computer generated "shop paper." This type of computer design flexibility and control is a valuable management tool not only for standardizing pallet arrangements, but for carton design and consolidation, warehouse design and layout, bin and shelf stocking, designing tapes for numerically controlled gas cutting machines, and numerous other industrial problems involved with the efficient layout of rectangular objects. [ABSTRACT FROM AUTHOR]

The optimal rules for the allocation of advertising expenditure when that expenditure affects the demand function facing the firm have been derived for a variety of processes and are relatively well known. The purpose of this paper is to extend the analysis of advertising to include recruitment advertising. We study the optimal rules for the cases where recruitment advertising acts as a current or capital input and finally in a diffusion model where advertising influences the rate at which potential recruits become aware of the firm. [ABSTRACT FROM AUTHOR]

Lumpy or sporadic demand patterns with highly skewed distributions are common in parts and supplies types of stockholdings, and much of available inventory control methodology is not appropriate for such items. This paper presents a simple, easily used regression model to calculate order points for lumpy items from knowledge of demand parameters and the desired service level. It is derived from the particular compound Poisson distribution commonly called 'stuttering Poisson.' Results are derived and presented in the following framework, though application is not limited to these conditions. The control discipline is the order quantity, order point (Q, R) approach with continuous review. Lead time is assumed to be known and constant. An assigned service level is assumed based on fraction of demand supplied without backorder. Joint optimization of Q and R is not addressed, but rather order point is based on an independently calculated order quantity. Forecasting methods are not addressed, but the mean and variance of lead time demand forecasts are assumed available. [ABSTRACT FROM AUTHOR]

This paper examines the problem of deriving the tangent (or market) portfolio from a given set of risky assets and a specified risk-free borrowing and lending rate. Deriving the tangent portfolio involves solving a mathematical programming problem which can be specified as the minimization of a quadratic objective function with linear constraints. The complementary pivot algorithm has previously been shown to be capable of deriving the optimal solution to certain quadratic programming problems, subject to a nonnegativity constraint. This paper demonstrates that the algorithm can be used to derive the tangent portfolio and that the nonnegativity constraint does not pose any serious handicap. Furthermore, it is shown that the algorithm can efficiently solve large-scale problems of this nature. [ABSTRACT FROM AUTHOR]

This paper proposes and analyzes a model for maximizing the profit of a product sold under warranty. The decision variables assumed in the model are the price of the product and the length of the period throughout which the manufacturer is responsible for service. The paper focuses on the dependence of optimal profit on price and protection period for a realistic and general description of a warrantied product. Failures are stochastic and repairs are of constant cost. Demand depends exponentially on price and warranty duration. After an introduction and literature review, the basic model is presented and assumptions are made about the particular probability law governing product failures. The optimization procedure is then illustrated for certain values of input parameters. Finally, an extensive economic analysis of the sensitivity of the optimal solution to variations in input parameters is provided. [ABSTRACT FROM AUTHOR]

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]

Most marketing planning models have carry-over effects in which one period's decisions influence the results obtained in future periods. In this paper it is shown that failure to allow for the carry-over effect beyond the planning horizon can result in underallocation of resources and in biases in the timing pattern of resource expenditure. For a wide class of market planning models, a procedure is developed to take into account this long-term effect. The distortion and the procedure are illustrated in an example. [ABSTRACT FROM AUTHOR]

Goal programming has now become an important tool in areas such as public management science. There is therefore a need for examining ways of securing improved computational efficiency, as is done in this paper, instead of resting only on the linear programming equivalences that were set forth when the original goal programming article was published in Vol. 1, No. 2 of Management Science. Based on lemmata which permit reduction of various important classes of convex goal programming models to problems of full row rank-interval programming type, explicit solutions to convex goal programming problems are exhibited. Some of the equivalences herein established are also useful in their own right and for other classes of problems--e.g., interval programming--as well as advanced start procedures and other such computational matters. [ABSTRACT FROM AUTHOR]

Stochastic dominance (SD) theory is concerned with orderings of random variables by classes of utility functions characterized solely in terms of general properties. This paper discusses a type of stochastic dominance, called DSD, which is defined by the utility functions having decreasing absolute risk-aversion. Necessary and sufficient conditions for DSD are presented for discrete random variables which, after the possible addition of points of zero probability, are concentrated on finitely many equally-spaced points. The problem is cast as a nonlinear program, which is solved through an efficient dynamic programming routine. Examples are presented to illustrate the increased effectiveness of DSD relative to previous types of stochastic dominance. [ABSTRACT FROM AUTHOR]

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]