Chapter 4 Operations
4.1 Transportation Problems
Acme would like to minimize it’s delivery costs. Suppose Acme has two orgins \(a\) and \(b\) and three destinations 1,2,3. The following table provides the cost \(c_{ij}\) of transporting one unit from the origin \(i\) to destination \(j\), and the maximum capacity of the origins and the required demand to the destinations. Acme needs to know how it must cover the demand to the destinations at a minimal cost.
## Warning: package 'dplyr' was built under R version 3.4.2##
## Attaching package: 'dplyr'## The following objects are masked from 'package:stats':
##
## filter, lag## The following objects are masked from 'package:base':
##
## intersect, setdiff, setequal, union## Warning: package 'kableExtra' was built under R version 3.4.4| orig_dest | 1 | 2 | 3 | capacity |
| a | 8 | 6 | 3 | 70 |
| b | 2 | 4 | 9 | 40 |
| demand | 40 | 35 | 25 |
This can be modeled with a LP with the following elements:
Decision variables in the form \(x_{ij}\), representing units transported from origin \(i\) to destination \(j\).
An objective function with cost coefficients equal to \(c_{ij}\).
Two sets of constraints: a less or equal set of constraints for each origin, limiting the units to be transported, and a greater of equal set of constraints representing the demand of each destination must be covered.
The resulting LP is:
\[MIN z = 8x_{a1} + 6x_{a2} + 3x_{a3} + 2x_{b1} + 4x_{b2} + 9x_{b3}\] subject to:
ca. \(x_{a1} + x_{a2} + x_{a3} \leq 70\) cb. \(x_{b1} + x_{b2} + x_{b3} \leq 40\) d1. \(x_{a1} + x_{b1} \geq 40\) d2. \(x_{a2} + x_{b2} \geq 35\) d3. \(x_{a3} + x_{b3} \geq 25\) \(x_{ij} \geq 0\)
Let’s now use R to solve Acme’s transportation problem:
library(lpSolve)
obj.fun <- c(8,6,3,2,4,9)
m <- 2
n <- 3
constr <- matrix(0, n+m, n*m)
for(i in 1:m){
for(j in 1:n){
constr[i, n*(i-1)+j] <- 1
constr[m+j, n*(i-1)+j] <- 1
}
}
constr.dir <- c(rep("<=", m), rep(">=", n))
rhs <- c(70,40,40,35,25)
####Solving the LP Model
prod.trans <- lp("min", obj.fun, constr, constr.dir, rhs, compute.sens = TRUE)
####LP Solution
prod.trans$obj.val
sol <- matrix(prod.trans$solution, m, n, byrow=TRUE)
prod.trans$duals
####Sensitivity Analysis of LP
prod.trans$duals.from
prod.trans$duals.to
prod.trans$sens.coef.from
prod.trans$sens.coef.to4.2 Economic Order Quantity
Description The EOQ function finds the optimal order policy in the classical Economic Order Quantity (EOQ) model and the EOQ model with planned shortages.
Usage
EOQ(d, k, h, b = 0)
Where
- d is Demand per unit time.
- k is Ordering or fixed cost per order.
- h is Holding cost per unit of product.
- b is Shortage penalty cost per unit (default:0)
Details
The EOQ model, also called Lot-Sizing model, considers that demand is uniform and deterministic. Lead time, the time between the placement of an order and its receipt, is equal to zero. The optimal order policy in the classical EOQ model minimizes the total cost associated with the ordering and holding costs while meeting all demand (without shortage). When shortages are allowed (b > 0) we have the EOQ model with backorders or planned shortages.
Value A list containing:
- T Time between orders (cycle length)
- S Maximum backorders in units. Displayed when b > 0
- TVC Total variable cost.
Let’s walk through a couple of examples. The first is a classical EOQ model, and the second an EOQ model with planned outages.
Acme has a given demand for its Invisible Paint of 8000 units per year, with a set-up cost of 12000 and a holding cost of 0.3 per unit.
library(SCperf)## Warning: package 'SCperf' was built under R version 3.4.3EOQ(8000,12000,0.3) Q T TVC 25298.2 3.2 7589.5
We find that the optimal solution is to order 25,298 units every 3.2 months with a total variable cost of 7,859.5 USD.
Now consider that backorders are allowed for Acme’s Invisible Paint at a cost of 1.1 per unit per year.
EOQ(8000,12000,0.3,1.1) Q T S TVC 28540.2 3.6 6115.8 6727.3
With this condition, the optimal solution is to order 28540 units every 3.6 months with a total variable cost of $6727.3 and the maximum shortage is 6116 units.
4.3 Economic Production Quantity
The Economic Production Quantity (EPQ) model is an extension of the EOQ model. It considers finite production rate, that is, the inventory is replenished gradually as the order is produced. Note that this assumption requires the production rate to be greater than the demand rate (p>d) otherwise there would be no inventory at any time.
The model considers that a new order is produced incrementally when the inventory reaches zero. During the time that production run, t = Q/p, inventory is accumulated at rate p???d, which implies that when the production of the batch Q is finished the inventory will reach its maximum level I.
Usage EPQ(d, p, k, h, b = 0)
Where
d is Deterministic demand per time unit
p is Production rate
k is Ordering or fixed cost per order
h is Holding cost per unit of product
b is Shortage penalty cost per unit (default:0)
EPQ() returns a list containing:
Q Order quantity
t Time required to produce the batch quantity
T Time between orders (cycle length or time)
I Maximum inventory level
TC Total cost
Acme has a fixed demand for its Super Speed Vitamins of 200 units per period at a fixed cost per unit of 100 USD, a holding cost of 5 USD per unit. Acme’s production rate for Super Seed Vitamins is 1000.
EPQ(d=200,p=1000,k=100,h=5)q t T I TC 100.0 0.1 0.5 80.0 400.0
We find the production run at t=0.1, the optimal order interval is T = 0.5, the optimal order quantity is Q = 100, the maximum inventory level is I=80 and the total cost is TC = $400.
4.4 News Vendor Model
When the demand is a random variable with normal distribution, the optimal stocking quantity that minimize the expected cost is: Q = m + z ??? sd, where z is known as the safety factor and Q ??? m = z ??? sd is known as the safety stock. Referred to as the newsboy problem, it is not formulated in terms of per unit holding cost h = c ??? s and penalty cost b = p ??? c.
Usage
Newsboy(m, sd, p, c, s = 0)
Where
m is Mean demand during the period
sd is Standard deviation of demand during the period
p is the selling price, where p > c
c is the unit cost
s is the salvage value (default:0), where s < c
The Model output is a list containing:
Q Optimal order-up-to quantity
SS Safety stock
ExpC Expected cost
ExpP Expected profit
CV Coefficient of variation of the demand
FR Fill rate, the fraction of demand served from stock
z Safety factor
Acme’s demand for glue is normally distributed with a mean of 100 and a standard deviation of 30. The selling price is 4 USD and the unit cost is 1 USD.
Newsboy(100,30,4,1)Then CR is 0.75 and Q is 120.23. Note that the order is for 20.23 units (safety stock) more than the mean. Note also that ExpC(120.23) = 38.13 and ExpP(120.23)=261.87, with FR=0.96.
Suppose now that demand is normal with mean 100 and standard deviation 20. The unit cost is 5, the holding and penalty cost are 1 and 3 respectively. From the definition of the holding and penalty cost we find that p=4.
Newsboy(100,20,4,1)Then CR = 0.75 and Q = 113.49. Notice that the order is for 13.49 units (safety stock) more than the mean, ExpC(113.49) = 25.42 and ExpP(113.49) = 274.58, with fill rate of 97 percent.
4.5 Production Scheduling
Acme produces jet bike kits. It has just received an order from Warner Bros. for 10 customized executive jet bike kits for the use of the corporation’s upper management. The order calls for three of the jet bike kits to be delivered (and paid for) during the upcoming winter months (period 1), two more to be delivered during the spring (period 2), three more during the summer (period 3), and the final two during the fall (period 4). Setting up the production facilities to meet the corporation’s specifications for these jet bikes requires a setup cost of 2 million usd. Acme has the capacity to produce all 10 jet bike kits within a couple of months, when the winter season will be under way. However, this would necessitate holding seven of the jet bike kits in inventory, at a cost of $200,000 per kit per period, until their scheduled delivery times. Management would like to determine the least costly production schedule for filling this order.
To solve this problem, we will use the Wagner-Whitin (WW) algorithm included in te R package SCperf. Considering time-varying demand, the algorithm builds production plans that minimizes the total setup and holding costs in a finite horizon of time, assuming zero starting inventory and no backlogging
Usage
WW(x, a, h, method = c(“backward”, “forward”))
Where
x is a numeric vector containing the demand per unit time
a is a numeric number for the set-up cost per unit and period
h is a numeric number for the holding cost per unit and period
method is a character string specifing which algorithm to use: “backward” (default) or “forward”
library(SCperf)
x <- c(3,2,3,2)
a <- 2
h <- 0.2
WW(x,a,h,method="backward")Call: WW.default(x, a, h, method = “backward”)
TVC: [1] 4.8
Solution: [,1] [,2] [,3] [,4] [1,] 5.4 4.8 5.6 4.8 [2,] NA 4.4 4.6 3.4 [3,] NA NA 4.0 2.4 [4,] NA NA NA 2.0
Jt: [1] “2 or 4” “4” “4” “4”
The total variable cost is $4.8 million (minimum value in the first raw). Since we have two minimun values in the first raw (positions 2 and 4), we have the following solutions:
Solution 1: Produce to cover demand until period 2, 5 kits. In period 3, new decision, minimun value 2.4 in period 4 (third raw). Then in period 3 produce to cover demand until period 4, 5 kits.
Solution 2: Produce to cover demand until period 4, 10 kits.
WW(x,a,h,method="forward")Call: WW.default(x, a, h, method = “forward”)
TVC: [1] 4.8
Solution: [,1] [,2] [,3] [,4] [1,] 2.0 NA NA NA [2,] 2.4 4.0 NA NA [3,] 3.6 4.6 4.4 NA [4,] 4.8 5.4 4.8 5.6
Jt: [1] “1” “1” “1” “1 or 3”
The total variable cost is $4.8 million (minimum value in the last raw). Since we have two minimun values in columns 1 and 3, the solutions are:
Solution 1: Produce in period 1 to cover demand until period 4, 10 kits.
Solution 2: Produce in period 3 to cover demand until period 4, 5 kits. In period 2, new decision, minimun value 2.4 in raw 3. Then in period 1 produce to cover demand until period 2, 5 kits.