An integrated approach for earthwork allocation,sequencing and routing

Planning techniques for large scale earthworks have been considered in this article. To improve these activities a “block theoretic” approach was developed that provides an integrated solution consisting of an allocation of cuts to fills and a sequence of cuts and fills over time. It considers the constantly changing terrain by computing haulage routes dynamically. Consequently more realistic haulage costs are used in the decision making process. A digraph is utilised to describe the terrain surface which has been partitioned into uniform grids. It reflects the true state of the terrain, and is altered after each cut and fill. A shortest path algorithm is successively applied to calculate the cost of each haul, and these costs are summed over the entire sequence, to provide a total cost of haulage. To solve this integrated optimisation problem a variety of solution techniques were applied, including constructive algorithms, meta-heuristics and parallel programming. The extensive numerical investigations have successfully shown the applicability of our approach to real sized earthwork problems.     

Joint optimisation of maintenance and buffer size in a manufacturing system

The objective of this work is to jointly optimise the maintenance of a capacity-constrained resource, its feed machine/operation and inlet buffer size. The maintenance of the capacity-constrained resource is condition-based, whilst that of the inlet machine/operation is time-based. The joint optimisation is achieved by the development of a mixed integer linear programming model. A machining example is used to illustrate the application of the model.     

Application of mathematical programming in planning of human diets

Mathematical programming models have been developed to find utility maximized nutritious diets. The utility maximized diets have been shown to be more practical, more realistic, and less costly than the non-utility maximized diets. In this study we further increase the desirability of diets by gradually softening those nutrients which have been supplied by the foods in the diet at a cost which is above the market price of the respective nutrient. Marginal analysis is used to find marginal costs of the nutrients. The parametric quadratic programming is used to find the optimum diet where the cost of nutrient is equal to the market price of the nutrient supplement. The resulting diet is more desireable and less costly than the previous diets.     

An Investigation of Feedstuffs for Dairy Cattle on Liverton Farm

This paper is based on the winning entry in the Operational Research Competition for Schools 1979. It examines the winter feed costs for dairy cattle on a Devon farm. The present feed is investigated using computer assisted optimisation techniques. The paper then examines whether silage should be introduced; the possible savings and necessary capital costs are calculated. In conclusion it proposes that the present feed be reduced and silage introduced as the main constituent, giving an initial annual saving of £13,000. The proposals are being seriously considered by the farmer and may be implemented in the near future.     

Linear Relaxations and Reduced-Cost Based Propagation of Continuous Variable Subscripts

In hybrid solvers for combinatorial optimisation, combining Constraint (Logic) Programming (CLP) and Mixed Integer Programming (MIP), it is important to have tight connections between the two domains. We extend and generalise previous work on automatic linearisations and propagation of symbolic CLP constraints that cross the boundary between CLP and MIP. We also present how reduced costs from the linear programming relaxation can be used for domain reduction on the CLP side. Computational results comparing our hybrid approach with pure CLP and MIP on a configuration problem show significant speed-ups.     

Ant Colony Optimisation for Machine Layout Problems

Flexible machine layout problems describe the dynamic arrangement of machines to optimise the trade-off between material handling and rearrangement costs under changing and uncertain production environments. A previous study used integer-programming techniques to solve heuristically reduced versions of the problem. As an alternative, this paper introduces an ant colony optimisation (ACO) algorithm to generate good solutions. Experimental results are presented, with ACO obtaining better solutions than the reduction heuristic.     

Modelling and optimisation of electricity,steam and district heating production for a local Swedish utility

District heating may help reduce environmental impact and energy costs, but policy instruments and waste management may influence operations. The energy system optimisation model MODEST has been used for 50 towns, regions and a nation. Investments and operation that satisfy energy demand at minimum cost are found through linear programming. This paper describes the application of MODEST to a municipal utility, which uses several fuels and cogeneration plants. The model reflects diurnal and monthly demand fluctuations.Several studies of the Linköping utility are reviewed. These indicate that the marginal heat cost is lower in summer; a new waste or wood fired cogeneration plant is more profitable than a natural-gas-fired combined cycle; material recycling of paper and hard plastics is preferable to waste incineration from an energy-efficiency viewpoint; and considering external costs enhances wood fuel use. Here, an emission limit is used to show how fossil-fuel cogeneration displaces CO₂ from coal-condensing plants.     

An Adaptive Neural Network Model for Nonlinear Programming Problems

In this paper a canonical neural network with adaptively changing synaptic weights and activation function parameters is presented to solve general nonlinear programming problems. The basic part of the model is a sub-network used to find a solution of quadratic programming problems with simple upper and lower bounds. By sequentially activating the sub-network under the control of an external computer or a special analog or digital processor that adjusts the weights and parameters, one then solves general nonlinear programming problems. Convergence proof and numerical results are given.     

Coordinated control of distribution supply chains in the presence of fuzzy customer demand

This paper considers a single product inventory control in a Distribution Supply Chain (DSC). The DSC operates in the presence of uncertainty in customer demands. The demands are described by imprecise linguistic expressions that are modelled by discrete fuzzy sets. Inventories at each facility within the DSC are replenished by applying periodic review policies with optimal order up-to-quantities. Fuzzy customer demands imply fuzziness in inventory positions at the end of review intervals and in incurred relevant costs per unit time interval. The determination of the minimum of defuzzified total cost of the DSC is a complex problem which is solved by applying decomposition; the original problem is decomposed into a number of simpler independent optimisation subproblems, where each retailer and the warehouse determine their optimum periodic reviews and order up-to-quantities. An iterative coordination mechanism is proposed for changing the review periods and order up-to-quantities for each retailer and the warehouse in such a way that all parties within the DSC are satisfied with respect to total incurred costs per unit time interval. Coordination is performed by introducing fuzzy constraints on review periods and fuzzy tolerances on retailers and warehouse costs in local optimisation subproblems.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

A mixed integer linear programming model for reliability optimisation in the component deployment problem

Component deployment is a combinatorial optimisation problem in software engineering that aims at finding the best allocation of software components to hardware resources in order to optimise quality attributes, such as reliability. The problem is often constrained because of the limited hardware resources, and the communication network, which may connect only certain resources. Owing to the non-linear nature of the reliability function, current optimisation methods have focused mainly on heuristic or metaheuristic algorithms. These are approximate methods, which find near-optimal solutions in a reasonable amount of time. In this paper, we present a mixed integer linear programming (MILP) formulation of the component deployment problem. We design a set of experiments where we compare the MILP solver to methods previously used to solve this problem. Results show that the MILP solver is efficient in finding feasible solutions even where other methods fail, or prove infeasibility where feasible solutions do not exist.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Solution of goal programming models using a basic taboo search algorithm

Goal programming is a very powerful technique for solving multiple objective optimisation problems. It has been successfully applied to numerous diverse real life problems. In this paper a Taboo search based method is developed to solve preemptive goal programming problems. The method can easily be applied to any kind of preemptive goal programming problems.     

A Dynamic Programming Model for Pig Production

The feeding policy of a pig production unit affects both the cost of production and the weight and carcase composition of the pigs produced. Since the market value of the pigs produced is determined by the weight and composition of the carcase, feeding policy has a major influence on the economic performance of the unit. In order to evaluate possible feeding policies, the effect of feed intake on both the weight and the body composition of the growing pig must be known, and since an optimal policy will involve using least cost rations, it must be possible to determine the least cost rations to produce liveweight gains of specified body composition. A dynamic programming model to determine the optimal feeding policy to produce pigs of specified weight and carcase composition is developed using a published pig growth model which allows the formulation of the required least cost rations, and the use of this dynamic programming model is illustrated.     

A faster exact method for solving the robust multi-mode resource-constrained project scheduling problem

This paper presents a mixed-integer linear programming formulation for the multi-mode resource-constrained project scheduling problem with uncertain activity durations. We consider a two-stage robust optimisation approach and find solutions that minimise the worst-case project makespan, whilst assuming that activity durations lie in a budgeted uncertainty set. Computational experiments show that this easy-to-implement formulation is many times faster than the current state-of-the-art solution approach for this problem, whilst solving over 40% more instances to optimality over the same benchmarking set.     

An Interactive Planning Model for the New Zealand Dairy Industry

A long-term planning model for a large New Zealand dairy company is described. The model presents an integrated view of the company's operation, including transportation and processing. The model used is based on a network formulation, NETPLAN, developed by the authors to carry out the optimisation. NETPLAN is highly flexible, interactive and provides graphical output of the results. The optimisation maximises net revenue based on product prices, variable process costs and variable transport costs subject to factory capacity, product demand and raw material supply constraints.     

An objective space cut and bound algorithm for convex multiplicative programmes

Multiplicative programming problems are global optimisation problems known to be NP-hard. In this paper we propose an objective space cut and bound algorithm for approximately solving convex multiplicative programming problems. This method is based on an objective space approximation algorithm for convex multi-objective programming problems. We show that this multi-objective optimisation algorithm can be changed into a cut and bound algorithm to solve convex multiplicative programming problems. We use an illustrative example to demonstrate the working of the algorithm. Computational experiments illustrate the superior performance of our algorithm compared to other methods from the literature.     

An architecture for solving sequencing and resource allocation problems using approximation methods

In the search for better optimisation techniques, new methods that mix artificial intelligence and operations research have emerged. Search heuristics are integrated with optimisation algorithms. Approximation methods, like Hill Climbing, Simulated Annealing, and Tabu Search, that have been used with success in combinatorial optimisation problems, are one of such research lines. This paper presents the key elements of approximation methods and combines them in a tool appropriate for solving sequencing and resource allocation problems. The system permits a clear division between problem specification and problem solving, allowing a declarative representation and therefore minimising developing costs. The key issues discussed in this work are a model for representing this class of problems in a standard form, a set of strategies for applying the approximation methodology, and an expert system that dynamically manipulates the strategies' parameters.     

Developments in linear and integer programming

In this review we describe recent developments in linear and integer (linear) programming. For over 50 years Operational Research practitioners have made use of linear optimisation models to aid decision making and over this period the size of problems that can be solved has increased dramatically, the time required to solve problems has decreased substantially and the flexibility of modelling and solving systems has increased steadily. Large models are no longer confined to large computers, and the flexibility of optimisation systems embedded in other decision support tools has made on-line decision making using linear programming a reality (and using integer programming a possibility). The review focuses on recent developments in algorithms, software and applications and investigates some connections between linear optimisation and other technologies.     

A new lot sizing and scheduling heuristic for multi-site biopharmaceutical production

Biopharmaceutical manufacturing requires high investments and long-term production planning. For large biopharmaceutical companies, planning typically involves multiple products and several production facilities. Production is usually done in batches with a substantial set-up cost and time for switching between products. The goal is to satisfy demand while minimising manufacturing, set-up and inventory costs. The resulting production planning problem is thus a variant of the capacitated lot-sizing and scheduling problem, and a complex combinatorial optimisation problem. Inspired by genetic algorithm approaches to job shop scheduling, this paper proposes a tailored construction heuristic that schedules demands of multiple products sequentially across several facilities to build a multi-year production plan (solution). The sequence in which the construction heuristic schedules the different demands is optimised by a genetic algorithm. We demonstrate the effectiveness of the approach on a biopharmaceutical lot sizing problem and compare it with a mathematical programming model from the literature. We show that the genetic algorithm can outperform the mathematical programming model for certain scenarios because the discretisation of time in mathematical programming artificially restricts the solution space.