How using Operations Research in your company can save you millions of dollars

This article gives examples of how Linear Programming Solutions saved companies millions of dollars.

Operations Research is a method of mathematically based analysis of problem-solving and decision-making for providing a quantitative basis for management decisions. The concept of operations research arose during World War II by military planners. After the war, the techniques used in their operations research were applied to addressing problems in business, the government and society. The objective of operations research is optimization, that means “to do things best under the given circumstances and information.” What is so amazing about Operations Research is that it is a general concept that can be applied to a wide variety of fields for example, in agricultural planning, biotechnology, distribution of goods and resources, emergency and rescue operations, engineering systems design, environmental management, financial planning, health care management, inventory control, manpower and resource allocation, manufacturing of goods, military operations, production process control, risk management, sequencing and scheduling of tasks, telecommunications, and traffic control.

There are many very impressive examples on how Operations Research can save you a lot of money.

1. Wastewater Plant Saves $200 million by using existing capacities effectively

The Louisville Metropolitan Sewer District (MSD) was faced with increasingly frequent and intense rainfall that can overwhelm urban wastewater collection and treatment systems and threaten local water environments. MSD partnered with Tetra Tech to implement a real-time control solution using Csoft®, Tetra Tech’s software platform that uses data analytics to optimize the management of sewer networks in real time based on rain forecasts and sensor readings. The solution realized more than $200 million in savings for the local community by reducing the cost of capturing wet weather overflows.

Tetra Tech’s researchers developed Csoft as a cost-effective solution for water utilities to use existing treatment plant storage in lieu of building additional storage facilities. Csoft enables water utilities to respond to rainfall and actual system conditions by maximizing all available storage, conveyance, and treatment capacities. Excess wastewater is diverted and temporarily stored until it can be redirected toward the appropriate treatment plant.

This work has been rewarded with the Franz Edelman Award 2019.

Sources:
(1) https://www.businesswire.com/news/home/20190430006062/en/
(2) https://louisvillemsd.org/edelman-award
(3) https://www.tetratech.com/en/articles/tetra-tech-and-louisville-metropolitan-sewer-district-win-the-2019-informs-franz-edelman-award

2. Hewlett-Packard improves their profit by $500 million through revenue management

HP offers a wide spectrum of innovative products to meet diverse customer needs. While this has helped the company achieve unparalleled market reach, it has come with significant costs and challenges. HP developed two powerful OR-based solutions for product variety management that address the diverse needs of its businesses throughout their products’ lifecycles. The first uses custom-built ROI calculators to evaluate each proposed new product before it is introduced. The second, HP’s Revenue Coverage Optimization (RCO) tool, is used to manage product variety after it has been introduced. By identifying a core portfolio of products most important to order coverage, RCO enables HP businesses to increase operational focus on the most critical products in their offerings. Using these tools, HP achieved over $500M in profit improvements across several business units since 2005. HP also streamlined its product offering, improved execution, achieved faster delivery performance, lowered overhead, and increased customer satisfaction and market share.

This work has been rewarded with the Franz Edelman Award 2009.

Source: https://www.informs.org/Recognizing-Excellence/Award-Recipients/Hewlett-Packard-Co2

3. Billions in Savings through the Application of Mixed-Integer Programming in the Energy Sector

Over the past few years, the Midwest Independent Transmission System Operator, Inc. (MISO) has transformed the electric utility industry in 13 Midwestern US states through the development and implementation of energy and ancillary services markets. MISO uses mixed-integer programming to determine when each power plant should be on or off. Operations research methods set energy output levels and establish the prices at which energy trades. These new markets increased the efficiency of the existing electric infrastructure (power plants and transmission lines) in the Midwest, improved the reliability of the grid, and reduced the need for future infrastructure investments. These advances enabled the MISO region to realize between $2.1 billion and $3.0 billion in cumulative savings from 2007 through 2010. We expect additional savings of $6.1 billion to $8.1 billion through 2020.

Source: https://www.informs.org/Recognizing-Excellence/Award-Recipients/MISO

This article features several Edelman Award winners. For more than 40 years, winners of the Edelman Award have been recognized for transforming how organizations approach some of the world’s most complex problems. First awarded in 1972, the prize is named in honor of Franz Edelman, who founded the Operations Research division within RCA, one of the first corporations to embed research as a business imperative.

Blending Problem in the Metal Industry

This article describes a simplified Blending Problem in the Oil Industry by way of an example and shows how to solve it using the Excel solver. We look at which percentages of the available alloys to use to obtain the desired blend at minimal cost.

Introduction

Blending problems in general deal with the question of which percentages of different materials should be blended together to obtain a blend with certain minimum number of ingredients. Each input material has different compositions of these ingredients and different prices. The objective is to minimize cost while obtaining the a blend with the desired ingredient levels. Blending problems occur in food manufacturing (for example Whiskas Cat Food) as the Diet Problem, in the oil industry and, as described here, in the metal industry.

Input data

There are several different alloys, named A through I, that have certain percentages of lead, zinc, and tin., see table below. Each alloy has a certain cost per pound as given in the table as well. The last column states the percentages of each ingredient in the desired blend. The question is which alloys should be used and in which fractions to obtain the desired blend at minimal costs.

Alloy A B C D E F G H I Desired blend
% Lead 10 10 40 60 30 30 30 50 20 30
% Zinc 10 30 50 30 30 40 20 40 30 30
% Tin 80 60 10 10 40 30 50 10 50 40
Costs/lb 4.1 4.3 5.8 6 7.6 7.5 7.3 6.9 7.3

Connecting the input data with the results through formulas

In the first step, the input data are connected with the results through several formulas, see screenshot below. The line “Percentages” highlighted in yellow is left blank (or may be filled with any values) and presents the decision variable. The sum of these must equal to 1 (it’s actually in fractions between 0 and 1.

The cost for each alloy used will be the cost/lb multiplied with its percentage. The sum over all alloys will be the total cost and represents the objective value (to be minimized).

In the lines below we compute the resulting amounts of each ingredient for each alloy given fraction of each alloy in the decision variables. The sum over each ingredient computes the amount of each ingredient for the actual blend (in column K). Now, these values can be used to enter the formulas in the Excel solver.

Dantzig Blending Problem Metal_Formula screenshot

Entering the information into the Excel solver

First, the objective value, here in K9, the total amount of cost is entered as objective and Min is selected as this is a minimization problem.

The decision variables are entered into the line “Changing Variable Cells”. The constraints are that (1) the actual blend amounts are as least as great as the given desired blend and (2) the sum over all fractions equals to 1.

Dantzig Blending Problem Metal_Solver screenshot

The solution

Hitting solve presents the following results:

Percentage 0 0.6 0 0.4 0 0 0 0 0 1
Costs 0 2.58 0 2.4 0 0 0 0 0 4.98
% Lead 0 6 0 24 0 0 0 0 0 30
% Zinc 0 18 0 12 0 0 0 0 0 30
% Tin 0 36 0 4 0 0 0 0 0 40

Extensions and Remarks

 

 

Source: Dantzig, G B, Chapter 3.4. In Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.

Resource Allocation Problem

This article describes the Resource Allocation Problem by way of an example and shows how to solve it using the Excel solver. Here we look at how many products to make of each kind when the products can be made on different machines which have limited availability.

Introduction

In the Resource Allocation Problem, there are multiple machine types with a given amount of operation time and several products to produce. The products can be manufactured on the different machines, however the amount of time to make these products differs from machine to machine. Each product has a certain profit and the objective is to decide over production quantities and assign machines for the production such that the profit is maximized.

Input data

The input data are given in the table below. There is the number of machines per machine type, the hours of operation per machine (let’s assume per week, but any other planning time frame may be chosen), resulting in weekly machine availability. In addition, each machine takes a certain time to produce these products, for example for Product 1, Machine 1 takes 1 hour, the other machines take 2 hours each. The profit per unit  is given in the last line of the table for each product.

Time to produce one unit of product..
Number of Machines Hours of Operation Machine availability Product 1 Product 2 Product 3 Product 4
Machine 1 4 40 160 1 4 5 3
Machine 2 3 40 120 2 3 4 2
Machine 3 2 40 80 2 2 5 3
Machine 4 3 40 120 2 1 3 2
Profit per product 30 25 60 20

Connecting the input data with the results through formulas

The screenshot below shows the formulas (and input in the first lines) used for this problem. The area highlighted in yellow marks the decision variables which are initially empty. In the line below, the quantities are summed up over all machines, for each product. This will be needed later (here in line 26) to compute the profit per product.

The table highlighted in blue multiplies the hours per product and machine with the amounts made, resulting in the total production hours per product and machine. This is for bookkeeping purposes: In column I, these hours are added up for each machine to obtain the total used machine hours per machine type. This number will be needed in the next step for the constraints.

Lastly, the total profit is obtained by summing up the profit per product. That value is the objective value which is to be maximized.

Resource Allocation Problem Formula Screenshot

Entering the information into the Excel solver

As mentioned above, the objective value is the total profit, given in cell I26 and is to be maximized. The decision variables (here “Changing Variable Cells”) are the table marked in yellow, in the example from E12 to H15.

The only constraint in this model is that the used machine hours may not exceed the available machine hours.

Resource Allocation Problem_Solver_Screenshot

The solution

Hitting solve gives the optimal number of products to be made, see table below. Machine 1 only produces Product 1, Machine 2 does Product 3, Machine 3 also makes Product 1 and Machine 4 produces Product 2. Product 4 is not manufactured in this example (as it takes a relatively large amount of time to make, with profits being the lowest.

Product 1 Product 2 Product 3 Product 4
Machine 1 160 0 0 0
Machine 2 0 0 30 0
Machine 3 40 0 0 0
Machine 4 0 120 0 0
total 200 120 30 0

 

The resulting hours on each machine per product and profits per product are as follows. The formulas for the profit per product have been put in prior to solving (see above). The total profit in this example amounts to $10,800.

Product 1 Product 2 Product 3 Product 4 Machine hours used
Machine 1 160 0 0 0 160
Machine 2 0 0 120 0 120
Machine 3 80 0 0 0 80
Machine 4 0 120 0 0 120
Total profit
Profit per product $6,000 $3,000 $1,800 $0 $10,800

 

Extensions and Remarks

This model is a generalization of the Production Mix Problem as the Resource Allocation Problem allows for multiple machines of each kind (whereas in the Production Mix Problem there is only one machine per type).

The restrictions of this model are the following: The model is not taking any given demand into account and also it assumes that any number of items can be sold. Furthermore, costs of production are not taking into consideration. Also it models only one time period. All these things are addressed in the more complex Extended Resource Allocation Problem.

Production Mix Problem (with Multiple Machines)

This article describes the Production Mix Problem by way of an example and shows how to solve it using the Excel solver. Here we look at how many products to make of each kind when the products can be made on different machines which have limited availability.

Introduction

Many manufacturers produce multiple products and have several, different machines that can all produce these products. In this case the Production Mix Problem occurs. This is a problem that can be formulated as linear program (LP) and solved to optimality. In this post we will give a minimal example in terms of the product and machine number as well as the complexity of the problem.

The objective in the Production Mix Problem is to maximize the total profit over all products. The decision to be made is how much to produce of each product to achieve this.  The constraint is to not exceed the amount of production capacity that is available for each machine.

Input data

The input data needed to solve this problem are the hours (or minutes or any other time unit) needed for each product on each machine, the production capacity of each machine, and the profit per unit of each product. An example for the input data can be found in the table below.

In this example, the production of 1 unit of Product 1 requires 2 hours when using Machine 1, 1 hour when using Machine 2 and 1 hour when using Machine 3 (Machine 4 is not suitable for Product 1). Selling one unit of product 1 will earn a profit of $20. There are 200 hours available on Machine 1, 150 hours on Machine 2 and so on.

Product
Machines Product 1 Product 2 Product 3 Product 4 Production capacity
Machine 1 2 0 2 1 200
Machine 2 1 0 1 2 150
Machine 3 1 6 0 2 250
Machine 4 0 3 1 0 100
Profit per product 20 40 25 30

Connecting the input data with the results through formulas

In the next step, a few formulas have to be entered into the spread sheet, see the screenshot below. This provides the Excel solver with important information about the problem. In the column UNITS USED, we compute the inventory for each component that remains after production of all planned units. Beforehand, when there is no entry for the decision variable yet, this will simply be zero, but will be updated as the solution is obtained. The INVENTORY AFTER is the difference between the inventory before and the units used. The PROFIT PER PRODUCT equals the product of profit per product and the quantity made for each product. In the cell for the total profit, these are added up over all products.

Production_Mix_Machines_Formula screenshot

After these formulas are entered, the optimization problem can be solved using the following objective function and constraints. The objective function is the total profit which is the sum over all products of the quantity products per product multiplied by the profit for that product.

The constraints are that (1) the decision variable which is the number of products produced per product is integer and non-negative and (2) that the machine hours needed to produce those quantities d not exceed the given capacity for each machine.

Entering the information into the Excel solver

The solver dialogue looks like shown in the graph below. The “Set Objective” (here $H$22) is the cell computing the total profit. The “Variable Cells” are the cells with the decision variables. In our case this is the number of products to be produced. Furthermore, there are constraints. The decision variable has to be integer and non-negative which is expressed in the first two lines of the “Constraints”. The last line ensures that the used production time must not exceed the maximum production capacity for each machine.

Production_Mix_Solver_Screenshot

The solution

Pressing solve in the above menu will give the following results using the Excel solver:

The capacity used and the remaining capacity can be found in the table below.

CAPACITY USED REMAINING CAPACITY
Component 1 198 2
Component 2 150 0
Component 3 248 2
Component 4 100 0

The results for the decision variables (no. of products made) and the profits are given below:

 

Product 1 Product 2 Product 3 Product 4
NO. OF PRODUCTS MADE 48 22 34 34 TOTAL PROFIT:
PROFIT PER PRODUCT $960 $880 $850 $1,020 $3,710

The solution states that 48 units of Product 1, 22 units of Product 2, 34 units of Product 3, and 34 units of Product 4 should be produced to maximize the total profit which amounts to $3,710 (sum over all products) in this example.

Extensions and Remarks

The presented problem can be extended by several other constraints, for example by a minimum or maximum for the number of products made, or different profits depending on the quantity produced. Also alternate methods to produce a product (needing different amounts of components) is a possible extension of this problem.

A slightly different problem that has the exact same architecture arises when considering different machines instead of components. In that case there are several products that share machines. Each product takes a certain amount of time on each machine (can also be zero). The machine has limited capacity (before: inventory of the components) which is measured in time. Again, the objective is to find the profit maximizing production quantities for each product.

The mathematically identical problem, however with a somewhat different context occurs in the Production Mix Problem with Multiple Components. The difference is that instead of sharing the same machines, these products use the same components. And instead of production capacity measured in time units, we now have inventory of components measured in pieces. You can read about it here. In that post, we used the exact same numerical example to highlight the similarities and differences.

Also, the Production Mix Problem (with Multiple Machines)  is a special case of the Resource Allocation Problem. In the Resource Allocation Problem, there are several machines of each kind (whereas in the Production Mix Problem there may only be one machine of each kind).

If you would like this or a similar problem to be solved by us, please contact us.

Production Mix Problem (with Multiple Components)

This article describes the Production Mix Problem by way of an example and shows how to solve it using the Excel solver. Here we look at how many products to make of each kind when the products use some of the same components of limited availability.

Introduction

Many manufacturers produce multiple products that are somewhat related and share some of the same components. In this case the Production Mix Problem occurs. This is a problem that can be formulated as linear program (LP) and solved to optimality. In this post we will give a minimal example in terms of the product and component number as well as the complexity of the problem.

The objective in the Production Mix Problem is to maximize the total profit over all products. The decision to be made is how much to produce of each product to achieve this.  The constraint is to not exceed the amount of inventory for each of the needed components.

Input data

The input data needed to solve this problem are the quantities needed of each component for each product, the inventory of each component, and the profit per unit of each product. An example for the input data can be found in the table below.

In this example, the production of 1 unit of Product 1 requires 2 units of Component 1, 1 unit of Component 2 and 1 unit of Component 3 (none of Component 4). Selling one unit of product 1 will earn a profit of $20. There are 200 units of Component 1 in stock, 150 of Component 2 and so on.

Product
Components Product 1 Product 2 Product 3 Product 4 Inventory
Component 1 2 0 2 1 200
Component 2 1 0 1 2 150
Component 3 1 6 0 2 250
Component 4 0 3 1 0 100
Profit per product 20 40 25 30

Connecting the input data with the results through formulas

In the next step, a few formulas have to be entered into the spread sheet, see the screenshot below. This provides the Excel solver with important information about the problem. In the column UNITS USED, we compute the inventory for each component that remains after production of all planned units. Beforehand, when there is no entry for the decision variable yet, this will simply be zero, but will be updated as the solution is obtained. The INVENTORY AFTER is the difference between the inventory before and the units used. The PROFIT PER PRODUCT equals the product of profit per product and the quantity made for each product. In the cell for the total profit, these are added up over all products.

Production_Mix_Formula screenshot

After these formulas are entered, the optimization problem can be solved using the following objective function and constraints. The objective function is the total profit which is the sum over all products of the quantity products per product multiplied by the profit for that product.

The constraints are that (1) the decision variable which is the number of products produced per product is integer and non-negative and (2) that the inventory needed to produce those quantities does not exceed the given inventory.

Entering the information into the Excel solver

The solver dialogue looks like shown in the graph below. The “Set Objective” (here $H$22) is the cell computing the total profit. The “Variable Cells” are the cells with the decision variables. In our case this is the number of products to be produced. Furthermore, there are constraints. The decision variable has to be both integer and non-negative which is expressed in the first two lines of the “Constraints”. The last line expresses that the used inventory must not exceed the inventory at hand.

Production_Mix_Solver_Screenshot

The solution

Pressing solve in the above menu will give the following results using the Excel solver:

UNITS USED INVENTORY AFTER
Component 1 198 2
Component 2 150 0
Component 3 248 2
Component 4 100 0
Product 1 Product 2 Product 3 Product 4
NO. OF PRODUCTS MADE 48 22 34 34 TOTAL PROFIT:
PROFIT PER PRODUCT $960 $880 $850 $1,020 $3,710

The solution states that 48 units of Product 1, 22 units of Product 2, 34 units of Product 3, and 34 units of Product 4 should be produced to maximize the total profit which amounts to $3,710 in this example. The units used and the inventory after can be found in the column above as well.

Extensions and Remarks

The presented problem can be extended by several other constraints, for example by a minimum or maximum for the number of products made, or different profits depending on the quantity produced. Also alternate methods to produce a product (needing different amounts of components) is a possible extension of this problem.

A slightly different problem that has the exact same architecture arises when considering different machines instead of components. In that case there are several products that share machines. Each product takes a certain amount of time on each machine (can also be zero). The machine has limited capacity (before: inventory of the components) which is measured in time. Again, the objective is to find the profit maximizing production quantities for each product.

The mathematically identical problem, however with a somewhat different context occurs in the Production Mix Problem with Multiple Machines. The difference is that instead of products using the same components, these products share the same machines. And instead of inventory of components measured in pieces, we now have production capacity measured in time units (for example hours). You can read about it here. In that post, we used the exact same numerical example to highlight the similarities and differences.

If you would like this or a similar problem to be solved by us, please contact us.

Production Scheduling Software “Pro S”

We have  developed a Production Scheduling Software, Pro S.

The software will schedule jobs in a multi-machine setting, featuring

  • job assignment to certain machine types
  • job assignment to certain machines
  • due dates
  • order release dates
  • job priorities
  • set up times
  • sequence-dependent set up times
  • delayed start for a seamless continuation of the former production schedule.

Contact us for a free trial now!

 

This is an example of the input (in Excel):

Input_Excel

The output will come both as a table in Excel and visualized in a Gantt chart:

Results_Excel

Gantt_chart

 

This is the Gantt chart solution for a slightly modified input (in this example, machine ready times are Machine 1: 11 am, Machine 2: 8 am, Machine 3: 10 am, and Machine 4: 12:30pm). This feature assures a seamless continuation of the prior production schedule.

Gantt-chart-with-delayed-start.png

Let us know how we can help you today!

How to Join Maximization and Minimization Objectives in One Objective Function

What do you do if you have both a maximization objective for one measure, e.g. a quality measure, and a minimization objective, let’s say transportation cost, for another measure?

Apart from having opposing goals, the measures most likely also have different measuring units as well as different ranges of values.

In order to tackle the problem, we account for those obstacles and follow these steps:

  1. We scale both values to take up the same range, e.g. from 0 to 10.
  2. We set up the objective function to go in one optimization direction, say minimization, keep the sign for the values that we would like to minimize and change the sign for the values that would like to maximize.
  3. In addition, we can weigh these values with factor weights that sum up to one. The higher the weight for one measure, the more this measure will be taken into account in the optimization compared to the other measure(s).

Note that you can do this in the same manner with more than two measures in the objective function.