A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

Lessons for O.R. from A.I.: A Scheduling Case Study

This paper compares operational research (O.R.) with the currently fashionable topic of artificial intelligence (A.I.) at a detailed level. A.I. concepts, techniques and history are summarized, and O.R. and A.I. approaches compared. A case study-the development of a potential aid to scheduling repair jobs on RAF squadrons—is described. The paper shows where A.I. concepts and techniques were used in the prototype program, known as the Fault Identification & Expediting Repair (FIXER) system. Finally, some lessons for O.R. are drawn.     

How Relevant is Operational Research to Development? The Case of Kenyan Industry

This paper proposes that the debate over O.R.'s role in development can be advanced by looking at a specific industrial environment. The Kenyan example suggests that for O.R. to make a contribution to this developing society it must: first, be defined as broadly as possible so as to include the most basic problem-solving techniques, and second, contribute to the diffusing of these techniques throughout the economy. O.R. should be viewed less as the province of an elite group of specialists— and more as a common resource available to managers at any level of industry. O.R. educators in developing nations can "democratise" quantitative techniques by incorporating them into such traditional business disciplines as accounting, marketing, and production. These courses should stress problem-solving and rely on cases drawn from local experiences. The paper ends by describing a pilot project, the Case Research and Documentation Centre, which is designed to promote more pragmatic management education and research in Kenya.     

Goals and Constraints in Decision-making<Superscript>†</Superscript>

Most problems in management involve multiple goals and two approaches to solving managerial problems have been suggested: optimizing and satisficing. The first covers methods of trade-offs, optimizing in tandem, conversion of goals into constraints and goal programming. The second mainly centres on norm setting and on interval programming. It is argued that cost-benefit analysis essentially belongs to the first group and that, contrary to some suggestions, the differences between the industrial and public sectors (as far as O.R. is concerned) are not related to differences between the optimizing and satisficing philosophies.     

O.R. in the Community

For the past eighteen months the authors have been involved in work with a community group attempting to help the unemployed youth of their small city. This paper discusses some of the key differences and similarities they found between this work in the community and more traditional organizations, particularly in terms of client-consultant expectations and their "organizational" context. The authors were made aware of the inadequacy of traditional O.R. techniques for helping their clients and the paper also describes some of the unconventional methods they were forced to turn to in order to offer realistic and relevant help with this complex "mess" of multiple problems, nested feedback loops and subjective, political beliefs not amenable to quantification.     

A penalty linear programming method using reduced-gradient basis-exchange techniques

We offer a variant of the piecewise-linear penalty-function approach to linear programming which was proposed by Conn [5]. Our variant makes use of computational techniques which are more closely related to those in existing computer codes for linear programming and which can be more readily adapted for large sparse problems that were the techniques described by Conn. An experimental code for small dense problems has been prepared and some experience with it is reported.     

Mathematical programming in subsistence agriculture

This paper examines the use of mathematical programming models in subsistence agriculture as an example of the use of operational research in developing countries. Differences from developed agriculture are described, and five mathematical programming formulations to cater for the major differences are given. Examples of the use of such models in published literature to produce policy oriented conclusions are summarised. This exemplified a more general point that mathematical O.R. formulations are relevant to policy issues in developing countries providing they are modifications of formulations used in developed countries.     

Applications of Mathematical Programming—Before,Now and After

Linear programming and its variants have been used for over 30 years, and during this time there have been technological and theoretical developments which have given the modeller enormous computer power and flexibility. Have these been matched in application—are the models being used?This paper attempts to look at the overall applied nature of linear programming—what has happened, what is happening and what is likely to happen. It draws on evidence from many sources including surveys, the literature and informal comments. The results indicate the growth in real application and power of the latest computer packages. However, there are still some problems remaining, and an attempt is made to highlight barriers to implementation.     

The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results

First, this paper presents the results of experiments with algorithmic techniques for efficiently solving medium and large scale linear and mixed integer programming problems. The techniques presented here are either original or recent.The solution of a great number of problems has shown that efficient problem solving requires automatic adaptation of algorithmic techniques upon problem characteristics. We show when a given technique should be used for a particular problem.The last part of this paper describes an attempt to provide a powerful mathematical programming language, allowing an easy programming of specific studies on medium-size models such as the recursive use of LP or the build-up of algorithms based on the simplex method.All these features have been implemented in the IBM Mathematical Programming System, MPSX/370, and its feature MIP/370. Extensive numerical results and comparisons on real-life problems are provided and commented upon.Presented at the IXth International Symposium on Mathematical Programming in Budapest (1976).     

Quantitative Forecasting—the State of the Art: Econometric Models

Econometric model building for forecasting has developed substantially over the past 15 years. Nevertheless, operational researchers have neglected these new developments. This paper defines nine stages the forecaster must go through when developing an econometric model. Each stage is discussed with reference to the most recent research. The complexity of econometric model building requires the forecaster to adopt a modelling strategy. Two have been proposed in the literature; one moves from a specific model to a more general version, the second goes from the general to the specific. Five recent O.R. studies using econometric methodology are then evaluated, highlighting the common areas of weakness. They are those areas that econometricians have paid most attention to in their recent research. The paper then surveys the effectiveness of econometric models compared to alternative approaches, concluding with some recommendations to the O.R. worker in forecasting. In particular, it recommends that more attempts are made to develop econometric models for O.R. applications.     

Anthropology and O.R.: The Place of Observation in Management Science Process

This paper is an argument to combine the methods of observation with O.R. techniques to form the basis of a management science process. The paper begins by defining a typology showing where observation methods seem to be most appropriate in O.R. interventions. This is followed by a section outlining some of the techniques and problems of observation as seen from the field of anthropology. Using this theory, combined with personal experience, an observation process is developed. An example of using the process is then given.     

A global optimization approach for the linear two-level program

Linear two-level programming deals with optimization problems in which the constraint region is implicity determined by another optimization problem. Mathematical programs of this type arise in connection with policy problems to which the Stackelberg leader-follower game is applicable. In this paper, the linear two-level programming problem is restated as a global optimization problem and a new solution method based on this approach is developed. The most important feature of this new method is that it attempts to take full advantage of the structure in the constraints using some recent global optimization techniques. A small example is solved in order to illustrate the approach.The paper was completed while this author was visiting the Department of Mathematics of Linköping University.     

Crop planning optimization model: the validation and verification processes

Each optimization problem in the area of natural resources claims for a specific validation and verification (V&V) procedures which, for overwhelming majority of the models, have not been developed so far. In this paper we develop V&V procedures for the crop planning optimization models in agriculture when the randomness of harvests is considered and complex crop rotation restrictions must hold. We list the criteria for developing V&V processes in this particular case, discuss the restrictions given by the data availability and suggest the V&V procedures. To show its relevance, they are applied to recently constructed stochastic programming model aiming to serve as a decision support tool for crop plan optimization in South Moravian farm. We find that the model is verified and valid and if applied in practice—it thus offers a plausible alternative to standard decision making routine on farms which often leads to breaking the crop rotation rules.     

Application of the boundary-value technique to singular perturbation problems at high Reynolds numbers

The boundary-value technique, advanced by Roberts for the solution of singular pertubation problems of ordinary differential equations where the small parameter multiples the highest derivative, is extended to the solution of the Navier-Stokes equation at high Reynolds numbers. Three standard flows—uniform flow past a plate, flow with a linearly adverse external velocity, and shear flow past a flat plate—have been chosen as test problems with a view to evaluating some of the features of the boundary-value technique, particularly in comparison with coefficient matching techniques as examplified by the method of matcher asymptotic expansions.     

A Simultaneous Enumeration Approach to the Traveling Salesman Problem

The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.     

A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

The E.E.C. and the development of O.R.

The growth of the E.E.C. has brought about a change in the scale of many organizational problems and a change in the ways that they can be tackled. Accordingly it is plausible that the techniques of O.R. should develop in response to these changes. This paper examines some desirable developments and suggests ways in which they might be achieved by adapting methods devised in other fields for similar problems.     

Implementation of a primal–dual method for SDP on a shared memory parallel architecture

Primal–dual interior point methods and the HKM method in particular have been implemented in a number of software packages for semidefinite programming. These methods have performed well in practice on small to medium sized SDPs. However, primal–dual codes have had some trouble in solving larger problems because of the storage requirements and required computational effort. In this paper we describe a parallel implementation of the primal–dual method on a shared memory system. Computational results are presented, including the solution of some large scale problems with over 50,000 constraints.     

Efficient Solution of a Class of Quantified Constraints with Quantifier Prefix Exists-Forall

In various applications the search for certificates for certain properties (e.g., stability of dynamical systems, program termination) can be formulated as a quantified constraint solving problem with quantifier prefix exists-forall. In this paper, we present an algorithm for solving a certain class of such problems based on interval techniques in combination with conservative linear programming approximation. In comparison with previous work, the method is more general—allowing general Boolean structure in the input constraint, and more efficient—using splitting heuristics that learn from the success of previous linear programming approximations.     

An Efficient Algorithm for Non-Point Source Pollution Management Problems

A dynamic programming (DP) algorithm is proposed for a class of non-point source pollution control problems. The formulation deals with the selection of a spatial distribution of management practices in such a way as to meet a control agency's sediment pollution target. The inherently combinatorial nature of these problems — stemming from the discrete nature of the decision variables, which are production, conservation and mechanical control practices — gives them a special integer programming structure. This paper focuses on the DP formulation and the computer implementation of this algorithm. The approach is shown to be informative, robust and relatively efficient. Furthermore, the paper demonstrates that dynamic programming can be used to generate sensitivity analysis information for multiple-choice knapsack problems.