4.4: Production-Inventory Planning: Multiple Products

ISE 754: Logistics Engineering, Fall 2026

Most things are only weakly connected with most other things.

— Herbert A. Simon’s “empty world hypothesis,” from “The Architecture of Complexity” (1962)1

No new Julia packages used.

No new Logjam functions used.

Companion script

4-net-4.jl, runnable Julia extracted from the lecture’s code blocks.

1. Multiple products

A production-inventory planning model for multiple products differs from modeling multiple single-product systems because shared resources must be managed across products. This requirement introduces additional structure into the formulation through coupling and linking constraints. Table 1 summarizes the four major classes of production-inventory models. The single-product models of Lecture 4.3 illustrate how production-inventory planning can be modeled either as a linear program (LP) when capacity is treated as an external input, and a mixed-integer linear program (MILP) when setup costs are introduced using binary production indicators, allowing the model to determine whether to produce in each period. Secs. 3 and 4 extend this framework to multiple products, focusing on formulations involving linking constraints, where resources must be allocated exclusively to a single product in each period. The second of them introduces switchover decisions, requiring the model to determine not only which product uses a resource but also whether to incur a switchover cost to switch it from one product to another. Models for joint shared resources using coupling constraints come first, in Sec. 2, with an example: the LP of Table 1, and then an MILP in which the shared resource also has a setup cost, as in the single-product MILP.

Table 1: The four major classes of production-inventory models.
LP MILP
Single Product Variable capacity as input to the model Setup cost using production indicators
Multiple Products Joint shared resources using coupling constraints Exclusive shared resources using linking constraints

With several products, the one thing that connects them, so that they have to be considered together in one integrated model, is typically that resources are shared among them. If every product has resources of its own, the products can be planned as separate models, a series of single-product models. What makes a model integrated is a machine that all of the products need to use, or a transportation vehicle, the same truck or the same train, that all of them use. A shared resource is shared in one of two ways. In the first, the total use of the resource by all of the products cannot exceed its total capacity, and the model can then probably still be a linear program. In the second, producing a product requires a switchover to it: the equipment may have to be cleaned, or its tooling changed, and while the resource is set up for one product, no other product can be produced on it.

Multiple-product planning is probably the most industrial-scale material in the course, the closest to what is actually used in industry. Strategic logistics engineering, from a commercial point of view, is an activity that only a really large corporation, such as Walmart, has dedicated personnel for; smaller companies engage consultants to do it, so much of the location material is the focus for someone who wants to become a consultant in the area. Production-inventory planning, by contrast, is purely tactical, the bread and butter of most corporations with complex logistics networks and supply chains. No person could keep track of everything in them and make these decisions, which leaves them reliant on mixed-integer linear programming models of this kind. Most people do not want to deal with a model itself, so it is reached through layers of access, as part of the overall work flow of Lecture 4.3, Sec. 5.

Two facts about math programs make these models easier to build. The first is that adding constraints to a math program can never improve a solution, a basic fact about math programming that is useful to keep in mind because it gives a direction of travel. When a constraint is added to a model that minimizes cost, either the objective does not change, and the constraint is not binding, or the cost increases; if the cost goes down, something has been done wrong somewhere in the modeling.

The second follows from the first: a model can ignore the situations that would make a solution worse, which makes it easier to add the constraints that implement a decision. The switchover constraints of Sec. 4 are the case in point. Switching a production system from one product to another requires changes, retooling, recalibrating and revalidating, and cleaning if the process is continuous, and their costs are incurred once the system is set up to produce the product. Unlike the setup cost of Lecture 4.3, incurred in every period a product is produced, a switchover cost is a one-time cost: as long as the system keeps producing that product and no other, it is not incurred again, and the setup carries over. That is easy to think of conceptually but harder to capture with constraints on binary variables, and what makes it easier than it would otherwise be is that only the situations in which skipping the switchover would lower the cost need to be ruled out. A situation in which a switchover would increase the cost can be ignored, because the model will never select something that increases the cost when nothing requires it, which simplifies how the constraints are implemented.

Otherwise separate single product networks are connected via sharing the combined use of a resource’s capacity (Fig. 1(a)). Continuous variable coupling constraints are used to ensure total output does not exceed available capacity. The model remains an LP if multiple products can be produced at the same time using the same resource, as long as the capacity they share is given rather than determined in the model.

Show the code that draws this figure
# Code block 1: two products' networks, coupled (a) and linked (b)
# Product k's stage i in period j is at P(k, i, j); each arc runs from
# node outline to node outline, and the nodes are drawn over the arcs
ink, datac = colorant"#252525", colorant"#d21f26"
# Each symbol in the font of the lecture's equations, in black, and each
# given value in red, as in Lecture 4.3's network figure; everything
# else in black but the circles and their connectors
mi = Makie.MathTeXEngine.texfont(:italic)
mr = Makie.MathTeXEngine.texfont(:math)
it(s) = rich(s; font = mi)                        # a symbol, in italics
up(s; kw...) = rich(s; font = mr, kw...)          # digits, operators
sym(b, sub, sup = nothing) = sup === nothing ?    # b with subscript sub
    rich(it(b), subscript(up(sub))) :            #   and superscript sup
    rich(it(b), subsup(up(sub), it(sup)))
val(v; op = " = ") = rich(up(op), up("$v"; color = datac))   # a value
# A connector from a circle to its constraint: a curve from p to q,
# drawn toward the control point c
function connector!(ax, p, c, q)
    pts = [Point2f((1 - u)^2 .* p .+ 2u * (1 - u) .* c .+ u^2 .* q)
           for u in range(0, 1; length = 60)]
    return lines!(ax, pts; color = datac, linewidth = 1.6)
end
function twonets!(ax; panel = :coupling, r = 0.16, dx = 1.5, dy = 1.25,
                  gap = 2.9, ls = 15)
    hidedecorations!(ax); hidespines!(ax)
    P(k, i, j) = ((k - 1) * (dx + gap) + (j - 1) * dx, -(i - 1) * dy)
    arc(p, q) = arrows2d!(ax, [p[1]], [p[2]], [q[1] - p[1]],
                          [q[2] - p[2]]; color = ink, shaftwidth = 1.2,
                          tipwidth = 7, tiplength = 7)
    lbl(p, s; al = (:left, :center), c = ink, fs = ls) =
        text!(ax, p[1], p[2]; text = s, color = c, fontsize = fs,
              align = al)
    circ = Dict{Int,Tuple{Float64,Float64}}()    # each product's circle
    for k in 1:2
        for j in 1:2
            x0, y0 = P(k, 1, j)
            arc((x0, y0 + 1.0), (x0, y0 + r))        # supply into stage 1
            for i in 2:3                             # production arcs
                arc(P(k, i - 1, j) .- (0, r), P(k, i, j) .+ (0, r))
            end
            xm, ym = P(k, 3, j)                      # demand from stage 3
            arc((xm, ym - r), (xm, ym - 0.7))
            lbl((xm, ym - 0.78), sym("d", "$j,$k"); al = (:center, :top))
        end
        for i in 1:3                             # inventory arcs
            arc(P(k, i, 1) .- (1.3, 0), P(k, i, 1) .- (r, 0))
            arc(P(k, i, 1) .+ (r, 0), P(k, i, 2) .- (r, 0))
            arc(P(k, i, 2) .+ (r, 0), P(k, i, 2) .+ (0.75, 0))
            y0 = (k == 2 && i == 3) ? 5 : 0          # initial inventory
            lbl(P(k, i, 1) .- (0.73, -0.10),
                rich(sym("y", "$i,1,$k"), val(y0));
                al = (:center, :bottom), fs = ls - 1)
        end
        for i in 1:3, j in 1:2                   # nodes, over the arcs
            poly!(ax, Circle(Point2f(P(k, i, j)...), r); color = :white,
                  strokecolor = ink, strokewidth = 1.5)
        end
        lbl(P(k, 1, 1) .+ (dx / 2, 1.3), "Product $k";
            al = (:center, :bottom))
        lbl(P(k, 1, 1) .+ (dx / 2, 0.10),        # above the arc, so the
            rich(sym("y", "1,2,$k"), up(" ≤ "), up("20"; color = datac));
            al = (:center, :bottom), fs = ls - 1) #   connector clears it
        xc, yc = P(k, 2, 2) .+ (0, (dy - 2r) / 2 + r - 0.02)  # x_{2,2,k}
        poly!(ax, Circle(Point2f(xc, yc), 0.17); color = :transparent,
              strokecolor = datac, strokewidth = 1.6, linestyle = :dash)
        circ[k] = (xc, yc)
    end
    lbl(P(1, 1, 1) .+ (0.08, 0.98), rich(sym("c", "1,1", "p"), val(120)))
    lbl(P(1, 1, 1) .+ (0.08, 0.66),
        rich(sym("x", "1,1,1"), up(" ≤ "), up("26"; color = datac)))
    for i in 2:3                                 # stages with no cost
        lbl(P(1, i, 1) .+ (0.08, (dy - 2r) / 2 + r),
            rich(sym("c", "$i,1", "p"), val(0)))
    end
    xr = P(2, 1, 2)[1] + 1.15                    # the constraints
    (c1x, c1y), (c2x, c2y) = circ[1], circ[2]
    # Product 1's connector passes above product 2's circle, below the
    # arc from its stage 1; product 2's leaves its circle to the right
    if panel == :coupling
        ye = -0.35
        lbl((xr + 1.7, ye + 0.36), "Couples each network";
            al = (:center, :bottom), fs = ls - 1)
        lbl((xr, ye), L"x_{2,2,1} + x_{2,2,2} \;\le\; u_{2,2}";
            fs = ls + 2)
        lbl((xr + 0.95, ye - 0.8), "Continuous\nvariables";
            al = (:center, :top), fs = ls - 1)
        lbl((xr + 2.75, ye - 0.8), "Shared\ncapacity";
            al = (:center, :top), fs = ls - 1)
        connector!(ax, (c1x + 0.15, c1y + 0.08), (4.3, -0.05),
                   (xr - 0.08, ye))
        connector!(ax, (c2x + 0.12, c2y - 0.12), (xr + 0.8, -1.05),
                   (xr + 1.2, ye - 0.26))
    else
        y1, y2, y3 = -0.35, -1.0, -2.05
        lbl((xr, y1), L"x_{2,2,1} \;\le\; u_{2,1}\, z_{2,2,1}";
            fs = ls + 2)
        lbl((xr, y2), L"x_{2,2,2} \;\le\; u_{2,2}\, z_{2,2,2}";
            fs = ls + 2)
        lbl((xr + 1.3, y3 + 0.36), "Links each network";
            al = (:center, :bottom), fs = ls - 1)
        lbl((xr, y3), L"z_{2,2,1} + z_{2,2,2} \;\le\; 1"; fs = ls + 2)
        lbl((xr + 0.8, y3 - 0.42), "Binary\nvariables";
            al = (:center, :top), fs = ls - 1)
        lbl((xr + 2.3, y3 - 0.42), "At most\none";
            al = (:center, :top), fs = ls - 1)
        connector!(ax, (c1x + 0.15, c1y + 0.08), (4.3, -0.05),
                   (xr - 0.08, y1))
        connector!(ax, (c2x + 0.15, c2y - 0.08), (xr - 0.55, y2),
                   (xr - 0.08, y2))
    end
    xlims!(ax, -1.55, xr + 3.75); ylims!(ax, -3.75, 1.72)
    return ax
end
fig = Figure(size = (687, 720))
for (n, (panel, caption)) in enumerate(
        [(:coupling, "(a) Coupled: combined use of a capacity"),
         (:linking, "(b) Linked: exclusive use of a capacity")])
    ax = Axis(fig[2n - 1, 1]; aspect = DataAspect())
    twonets!(ax; panel = panel)
    Label(fig[2n, 1], caption; fontsize = 14, tellwidth = false)
    rowsize!(fig.layout, 2n, Fixed(22))          # the caption below it
end
rowgap!(fig.layout, 4)
fig
Figure 1: Two products’ networks, each with three stages over two periods and the data of Ex. 1: (a) coupled, the production of both products at stage 2 in period 2 sharing that stage’s capacity; (b) linked, stage 2 set up for at most one of the products in period 2. The production arcs each constraint joins are circled in red and connected to it.

There are two ways of connecting multiple products in a math programming model. The first is a coupling constraint, which lets products share a resource’s capacity in combination: a production machine, say, that produces two products at the same time. That does not happen much in discrete production, where a machine usually does one thing or the other. The resource that does combine products is transportation, once a production system is seen more widely: the aggregate shipments of Lectures 3.2 and 3.3 put several products in one trailer and share the truck’s capacity. Trucking is interesting because its capacity is not a single number but a cube capacity and a weight capacity, which makes it a challenge to model as a math program.

With a coupling constraint there are, in effect, two separate math programming models, connected by the continuous variables for the production of each product. Lecture 4.3’s variables had two indices, the stage of production, the rows of its network, and the period, the columns; a third index is now the product. In Fig. 1(a), the two variables are for the same stage and period, stage 2 in period 2, one for each product, and the coupling constraint says that the combined production at that stage in that period can be no more than the stage’s capacity in the period.

A joint shared resource is not exclusive. A kiln in which items are put to dry is an example: it is a production stage, different types of product can be put in it together, and the only limitation is how much it can hold. It is modeled as a joint shared resource whose constraint has no binary variable, only the production quantities, whose sum cannot exceed the shared capacity, and that formulation keeps the model a linear program. Exclusive use is the other case, typically a machine that can produce one product or the other but not both.

Otherwise separate product networks are connected via sharing the exclusive use of a resource’s capacity (Fig. 1(b)). The model becomes an MILP model if each product requires the exclusive use of a resource, where (discrete variable) linking constraints are used to ensure that only one product can use each resource during each period.

Linking constraints are the more typical case for a manufacturing machine, which is doing either one thing or the other, with no way of combining products on it. In Fig. 1(b) there are two capacity constraints, one for each product, much as in Lecture 4.3, where the binary variable z was an off and on switch for a stage’s capacity; here the z variables gate each product’s capacity in the same way. The linking constraint says that both of them cannot be one at the same time, so their sum is at most one: the stage can produce product 1, product 2 or neither, but not both. In logic that condition is an exclusive or, one or the other but not both together, and binary variables can represent all kinds of logical conditions, if-then included, as constraints.

In short, indicator variables require MILP instead of LP, and lumpy resources require indicator variables to include setup and switchover costs. For shared resources, coupling constraints are used to ensure total output does not exceed available capacity, and the model can still be an LP; linking constraints are used to ensure only one activity per period. Sec. 2 takes up coupling constraints, Sec. 3 linking constraints, and Sec. 4 the switchover costs that linking makes possible.

Table 2 summarizes the multiple-product problems of this lecture by what the products share and what solves each, as Table 3 in Lecture 4.3 does for a single product.

Table 2: Multiple-product problems in this lecture: what the products share, the problem, and what solves each.
Resource sharing Problem Solved by
None: each product has its own resources products planned one at a time (Ex. 2 without its linking rows) LP for each product, Lecture 4.3’s Model 1
Combined: products share a resource’s capacity, by coupling constraints shared capacity given, no setup cost LP, Model 1
trucks and trailers shared, a setup cost for each load (Ex. 1) MILP, Model 2, setups an integer count
Exclusive: a resource set up for one product a period, by linking constraints no switchover cost (Ex. 2) MILP, Model 3
switchover cost when a stage changes product (Ex. 3, 4) MILP, Model 4

2. Coupling constraints

Model 1 generalizes Model 1 in Lecture 4.3: each flow carries a product index, and the products at a stage share its capacity in each period, which is given, as Lecture 4.3’s capacities are. Its row (f) is the coupling constraint of Fig. 1(a), and its variables are all continuous, so it is the LP of Table 1.

minimize: total production and inventory cost over the planning horizon

solve for:
(a) production of each product at each stage in each period;
(b) inventory of each product at each stage carried into each period.

subject to:
(a) Flow balance: at each stage that feeds the next, for each product, what is produced or carried in is either passed on to the next stage or carried out;
(b) Flow balance: at the last stage, which feeds each product’s demand, what is produced or carried in either meets the period’s demand or is carried out;
(c) Capacity: production of each product at each stage in each period is no more than its capacitythat product’s capacity;
(d) Initial and final inventory: inventory of each product at each stage at the start and at the end of the horizon is given;
(e) Storage: inventory of each product at each stage between periods is no more than its storage capacity;
(f) Coupling: the combined production of all products at a stage in a period is no more than its capacity.

assumptions:
(a) production cost and inventory cost per ton of each product at each stage are constant;
(b) demand for each product in each period is given;
(c) production can pass through every stage within the period it starts in.

Model 1: Coupled products
Model 1 formulation: Coupled products

\begin{array}{rrclll} \mathrlap{\text{Minimize}} & & & & & \\[2pt] \mathrlap{\qquad \displaystyle \sum_{i=1}^{m} \sum_{j=1}^{t} \sum_{k=1}^{g} c_{ik}^p\, x_{ijk} + \sum_{i=1}^{m} \sum_{j=2}^{t+1} \sum_{k=1}^{g} c_{ik}^i\, y_{ijk}} & & & & & \\[16pt] \mathrlap{\text{subject to}} & & & & & \\[8pt] & -x_{ijk} + x_{(i+1)jk} - y_{ijk} + y_{i(j+1)k} & = & 0, & \hphantom{k}\mathllap{i} = 1, \dots, m-1 & (a) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & -x_{mjk} - y_{mjk} + y_{m(j+1)k} & = & -d_{jk}, & \hphantom{k}\mathllap{j} = 1, \dots, t & (b) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & x_{ijk} & \le & u_{ik}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (c) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i1k} & = & y_{ik}^0, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i(t+1)k} & = & y_{ik}^{t+1}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{ijk} & \le & u_{ik}^y, & \hphantom{k}\mathllap{i} = 1, \dots, m & (e) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 2, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & \textcolor{#d21f26}{\small\text{Coupling}}\quad\mathopen{} \smash{\displaystyle \sum_{k=1}^{g}}\, x_{ijk} & \le & u_{ij}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (f) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[8pt] & x_{ijk},\ y_{ijk} & \ge & 0 & & \end{array} \tag{1}

where

x_{ijk}
= production of product k at stage i in period j (ton)
y_{ijk}
= inventory of product k at stage i carried into period j (ton)
c_{ik}^p
= production cost of product k at stage i ($/ton)
c_{ik}^i
= inventory cost of product k at stage i ($/ton-period)
= h\,(c_{1k}^p + c_{2k}^p + \cdots + c_{ik}^p)
d_{jk}
= demand for product k in period j (ton)
u_{ik}
= capacity for product k at stage i (ton)
u_{ij}
= capacity of stage i in period j, shared by the products (ton)
u_{ik}^y
= storage capacity for product k at stage i (ton)
y_{ik}^0
= initial inventory of product k at stage i (ton)
y_{ik}^{t+1}
= final inventory of product k at stage i (ton)
g
= number of products.

The other symbols are those of Eq. 1 in Lecture 4.3. Both lines labeled (d) in Eq. 1 are row (d), as in Lecture 4.3. A stage that shares no capacity has u_{ij} = \infty and no row (f).

Model 1 is not implemented on its own. It is the special case of Model 2, which follows, with no setup cost: then nothing is saved by turning a setup off, the number of setups can be its most, \bar{z}_{ij}, and the row (f) of Model 2 is then the row (f) above with u_{ij} = u_i\,\bar{z}_{ij}, so its implementation solves it.

Model 3 in Lecture 4.3 treats a truck as a setup, its cost incurred for each truck sent and its maximum payload the capacity of the setup (Ex. 6 in Lecture 4.3). A truck shared by several products is a coupling constraint.

A truck that is shared can be represented by the number of trucks, with a constraint making sure that the total amount transported does not exceed the capacity of the trucks. The variable z is then not an indicator variable, 0 or 1, but an integer variable, the number of trucks. Otherwise there are two separate network models, and it is only this constraint, connecting both of them, that requires them to be solved as one integrated model.

Model 2 generalizes Model 1 as Model 3 in Lecture 4.3 generalizes Model 1 in Lecture 4.3: the shared capacity, given in Model 1, is the capacity per setup times the number of setups, determined in the model, each setup at a cost. It is also Model 3 in Lecture 4.3 with a product index.

minimize: total production, inventoryand setup cost over the planning horizon

solve for:
(a) production of each product at each stage in each period;
(b) inventory of each product at each stage carried into each period;
(c) number of setups at each stage in each period.

subject to:
(a) Flow balance: at each stage that feeds the next, for each product, what is produced or carried in is either passed on to the next stage or carried out;
(b) Flow balance: at the last stage, which feeds each product’s demand, what is produced or carried in either meets the period’s demand or is carried out;
(c) Capacity: production of each product at each stage in each period is no more than that product’s capacity;
(d) Initial and final inventory: inventory of each product at each stage at the start and at the end of the horizon is given;
(e) Storage: inventory of each product at each stage between periods is no more than its storage capacity;
(f) Coupling: the combined production of all products at a stage in a period is no more than its capacityper setup times its number of setups.

assumptions:
(a) production cost and inventory cost per ton of each product at each stage are constant;
(b) demand for each product in each period is given;
(c) production can pass through every stage within the period it starts in;
(d) setup cost is incurred for each setup at a stage, whatever the products it then carries;
(e) inventory carries each ton’s share of its setups, taken at a full setup’s capacity, whatever the product.

Model 2: Coupled products with setups
Generalization of Model 1: Coupled products
Model 2 formulation: Coupled products with setups

\begin{array}{rrclll} \mathrlap{\text{Minimize}} & & & & & \\[2pt] \mathrlap{\qquad \displaystyle \sum_{i=1}^{m} \sum_{j=1}^{t} \Bigl( \sum_{k=1}^{g} c_{ik}^p\, x_{ijk} + c_i^s\, z_{ij} \Bigr) + \sum_{i=1}^{m} \sum_{j=2}^{t+1} \sum_{k=1}^{g} c_{ik}^i\, y_{ijk}} & & & & & \\[16pt] \mathrlap{\text{subject to}} & & & & & \\[8pt] & -x_{ijk} + x_{(i+1)jk} - y_{ijk} + y_{i(j+1)k} & = & 0, & \hphantom{k}\mathllap{i} = 1, \dots, m-1 & (a) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & -x_{mjk} - y_{mjk} + y_{m(j+1)k} & = & -d_{jk}, & \hphantom{k}\mathllap{j} = 1, \dots, t & (b) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & x_{ijk} & \le & u_{ik}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (c) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i1k} & = & y_{ik}^0, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i(t+1)k} & = & y_{ik}^{t+1}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{ijk} & \le & u_{ik}^y, & \hphantom{k}\mathllap{i} = 1, \dots, m & (e) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 2, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & \smash{\displaystyle \sum_{k=1}^{g}}\, x_{ijk} & \le & u_i\, z_{ij}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (f) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[8pt] & x_{ijk},\ y_{ijk} & \ge & 0 & & \\[8pt] & z_{ij} & \in & \mathrlap{\{0, 1, \dots, \bar{z}_{ij}\}} & & \end{array} \tag{2}

where

z_{ij}
= number of setups at stage i in period j
c_i^s
= setup cost at stage i ($/setup)
c_{ik}^i
= inventory cost of product k at stage i ($/ton-period)
= h\,\bigl[(c_{1k}^p + c_1^s/u_1) + \cdots + (c_{ik}^p + c_i^s/u_i)\bigr]
u_i
= capacity per setup at stage i, shared by the products (ton/setup)
\bar{z}_{ij}
= most setups at stage i in period j.

The other symbols are those of Eq. 1. A stage that shares no capacity, such as extraction in Ex. 1, has u_i = \infty and no row (f).

Model 2 implementation: Coupled products with setups
# Model: coupled products with setups
using JuMP, HiGHS, Logjam
function prodinv_coupled(cᵖ, cˢ, cⁱ, d, UBˣ, u, z̄, LBʸ, UBʸ)
    m, g = size(cᵖ)
    t = size(d, 1)
    model = Model(HiGHS.Optimizer)
    @variable(model, 0 ≤ x[i=1:m, j=1:t, k=1:g] ≤ UBˣ[i,k])
    @variable(model, LBʸ[i,j,k] ≤ y[i=1:m, j=1:t+1, k=1:g] ≤ UBʸ[i,j,k])
    @variable(model, 0 ≤ z[i=1:m, j=1:t] ≤ z̄[i,j], Int)
    @objective(model, Min,
        sum(cᵖ[i,k]*x[i,j,k] for i=1:m, j=1:t, k=1:g) +
        sum(cˢ[i]*z[i,j] for i=1:m, j=1:t) +
        sum(cⁱ[i,k]*y[i,j,k] for i=1:m, j=2:t+1, k=1:g))
    @constraint(model, flowbal[i=1:m-1, j=1:t, k=1:g],              # (a)
        -x[i,j,k] + x[i+1,j,k] - y[i,j,k] + y[i,j+1,k] == 0)
    @constraint(model, laststage[j=1:t, k=1:g],                     # (b)
        -x[m,j,k] - y[m,j,k] + y[m,j+1,k] == -d[j,k])
    @constraint(model, coupling[i=1:m, j=1:t; isfinite(u[i])],
        sum(x[i,j,k] for k=1:g) ≤ u[i]*z[i,j])                      # (f)

    set_silent(model)
    set_attribute(model, "mip_rel_gap", 0.0)
    optimize!(model)
    if termination_status(model) == JuMP.OPTIMAL
        return (TC = objective_value(model), x = snapvals(value.(x)),
                y = snapvals(value.(y)), z = Int.(snapvals(value.(z))))
    end
    error(termination_status(model))
end
1
Row (c) is the upper bound UBˣ on x, a product’s own capacity at a stage, as Lecture 4.3’s capacity was a bound; rows (d) and (e) are the bounds LBʸ and UBʸ on y, as there.
2
The condition after the semicolon keeps only the stages with a finite capacity per setup: a stage that shares no capacity has no row (f).
3
HiGHS stops by default once its solution is within 0.01% of the best possible, which can leave a cost a few dollars above the optimum; a gap of 0 asks it to prove the optimum.
prodinv_coupled (generic function with 1 method)

A truck trailer shared by two products is modeled much as before. The cost of a trailer going from an origin to a destination, $1,000 say, is a cost common to the products that share it, with no variable cost: the amount shipped does not appear in the objective, because a truckload’s cost, unlike LTL’s, is not proportional to its tons, and what is paid for is the trailer, however much is in it. That is a setup cost in the sense of Lecture 4.3, but there, with a single product, all of it was assigned to the one product. With two or more products sharing the trailer, how is the $1,000 to be assigned to them: half and half, or by how much of the trailer each uses? There is not necessarily a well-defined answer. The company pays the $1,000 regardless, so most of the cost is unaffected; what the allocation does affect is the inventory cost. Each shipment adds value to the products, which are now at a new location, just as production adds value from one stage to the next, and the inventory cost accumulates the value added, stage by stage. The most natural allocation, in proportion to the capacity each product uses, makes the objective function nonlinear, so a linear objective has to approximate it some other way. One way is to weight each product by its maximum payload, which depends on its density. Two extreme products, one like beach balls, which cube out the trailer, and one like gold bars, which weigh it out, are great candidates to share a trailer, and a trailer they share should be charged to them about half and half; their maximum payloads, 25 tons for the gold bars and a hundredth of a ton or less for the beach balls, could serve as weights in a measure that comes out near 50% when both cube and weigh out together. Considerations like these arise in implementing such a problem as a math program: much of the modeling applies directly, but not everything is immediately representable in a formulation.

Assumption (e) of Model 2 takes the simpler course: every ton is charged the same share of a setup, its cost divided by the capacity per setup, whatever the product, as Eq. 4 in Lecture 4.3 charges it.

Example 1: Extraction and staging

A facility that extracts two different raw materials for pharmaceuticals is at a location that requires the extracted material to be sent over rough terrain in a truck to a staging station where it is then loaded onto a tractor trailer for transport to its final destination. A 10-week rolling horizon is used for planning extraction and transportation. The materials’ forecasted demand, in tons, is given in Table 3:

Table 3: Ex. 1’s forecast demand for each material in each week, and its total over the ten weeks (ton).
Week 1 2 3 4 5 6 7 8 9 10 Total
Material 1 13 15 21 14 12 11 45 25 48 14 218
Material 2 11 9 17 15 18 11 6 7 15 20 129

The facility can extract up to 26 and 15 tons per week of each material, respectively, at a cost of $120 and $200 per ton. The annual inventory carrying rate is 0.15. The facility can store up to 20 tons of each material on site, and unlimited amounts of material can be stored at the staging station and the final destination. Currently, five tons of the second material is in inventory at the final destination and this same amount should be in inventory at the end of the planning period. It costs $200 for a truck to make the roundtrip from the facility to the staging station, and it costs $800 for each truckload transported from the station to the final destination. Each truck and tractor trailer can carry up to 10 and 25 tons of material, respectively, and each load can contain both types of material. Determine the amount of each material that should be extracted and when it should be transported in order to minimize total costs over the planning horizon.

With the demand of Table 3, the problem is Model 2 with three stages, the network of Fig. 1, set out without its weeks in Fig. 2: stage 1 is extraction, stage 2 the truck from the facility to the staging station, and stage 3 the tractor trailer from the station to the final destination, where the demand is. The two materials are the products. Extraction has a capacity for each material, 26 and 15 tons a week, row (c), and shares nothing, so it has no setups. Each truck and each trailer is a setup, as in Ex. 6 in Lecture 4.3: its cost, $200 or $800, is incurred for each load, with no cost per ton, and its capacity per setup, 10 or 25 tons, is shared by the two materials, row (f). The 20 tons that can be stored on site are the storage capacity of stage 1, row (e), and the five tons of the second material at the destination are its initial and final inventory at stage 3, row (d).

Show the code that draws this figure
# Code block 2: Ex. 1's two materials through its three stages
red(s) = up(s; color = datac)               # a given value, as in Fig. 1
function ex1net!(ax; r = 0.2, dx = 4.2, dy = 2.2, ls = 15)
    hidedecorations!(ax); hidespines!(ax)
    P(k, i) = ((i - 1) * dx, -(k - 1) * dy)  # material k at stage i
    arc(p, q) = arrows2d!(ax, [p[1]], [p[2]], [q[1] - p[1]],
                          [q[2] - p[2]]; color = ink, shaftwidth = 1.2,
                          tipwidth = 7, tiplength = 7)
    lbl(p, s; al = (:center, :center), fs = ls) =
        text!(ax, p[1], p[2]; text = s, color = ink, fontsize = fs,
              align = al)
    for (i, s) in enumerate(["Extraction", "Staging station",
                             "Final destination"])
        lbl(P(1, i) .+ (0, 0.95), s; al = (:center, :bottom))
    end
    for (k, cap, cost) in ((1, 26, 120), (2, 15, 200))
        lbl(P(k, 1) .- (2.75, 0), "Material $k"; al = (:right, :center))
        arc(P(k, 1) .- (2.55, 0), P(k, 1) .- (r, 0))     # extraction
        lbl(P(k, 1) .- (1.35, -0.14),
            rich(up("≤ "), red("$cap"), up(" ton/week"));
            al = (:center, :bottom), fs = ls - 2)
        lbl(P(k, 1) .- (1.35, -0.51), rich(red("\$$cost"), up("/ton"));
            al = (:center, :bottom), fs = ls - 2)
        lbl(P(k, 1) .+ (-0.15, -r - 0.12),               # stored on site
            rich(up("store ≤ "), red("20"), up(" ton"));
            al = (:center, :top), fs = ls - 2)
        for i in 2:3                                     # truck, trailer
            arc(P(k, i - 1) .+ (r, 0), P(k, i) .- (r, 0))
        end
        arc(P(k, 3) .+ (r, 0), P(k, 3) .+ (1.25, 0))     # demand
        lbl(P(k, 3) .+ (1.35, 0), "demand"; al = (:left, :center),
            fs = ls - 2)
        for i in 1:3
            poly!(ax, Circle(Point2f(P(k, i)...), r); color = :white,
                  strokecolor = ink, strokewidth = 1.5)
        end
    end
    lbl(P(2, 3) .+ (0.6, r + 0.12),                      # at the end too
        rich(red("5"), up(" ton at start and end"));
        al = (:center, :bottom), fs = ls - 2)
    # The truck and the trailer: a box across both materials' arcs, the
    # capacity they share inside it, the cost of a trip below it
    for (i, what, cap, cost, per) in
            ((2, "Truck", 10, "\$200", " a round trip"),
             (3, "Trailer", 25, "\$800", " a load"))
        xm = (P(1, i - 1)[1] + P(1, i)[1]) / 2
        y1, y2 = P(1, i)[2] + 0.38, P(2, i)[2] - 0.38
        w = 2.0
        poly!(ax, Rect(xm - w/2, y2, w, y1 - y2); color = :transparent,
              strokecolor = datac, strokewidth = 1.6)
        lbl((xm, y1 + 0.1), what; al = (:center, :bottom), fs = ls - 1)
        ym = (P(1, i)[2] + P(2, i)[2]) / 2
        lbl((xm, ym + 0.2), rich(up("≤ "), red("$cap"), up(" ton"));
            fs = ls - 2)
        lbl((xm, ym - 0.2), "both materials"; fs = ls - 3)
        lbl((xm, y2 - 0.1), rich(red(cost), up(per));
            al = (:center, :top), fs = ls - 2)
    end
    xlims!(ax, -4.6, 2dx + 2.6); ylims!(ax, -dy - 0.85, 1.45)
    return ax
end
fig = Figure(size = (687, 300))
ex1net!(Axis(fig[1, 1]; aspect = DataAspect()))
fig
Figure 2: Ex. 1’s setup, without its weeks: each material is extracted, trucked to the staging station and carried by tractor trailer to the final destination, the problem’s data in red. The truck and the trailer are each a box across both materials’ arcs holding what the materials share, the vehicle’s capacity; its cost for each trip is set below it.

Example 1(a): Ten-week plan

Determine the ten-week plan and its cost with Model 2, after a lower bound on the cost and the most setups in a week by hand.

Before any model is solved, part of the cost is fixed by flow balance alone. The demand of the ten weeks, 218 tons of the first material and 129 of the second, all has to be extracted, at $120 and $200 a ton, whatever the plan; and since the five tons at the destination at the start are the five wanted at the end, all 347 tons have to be shipped. A load can carry at most its capacity, so shipping them takes at least \lceil 347/10 \rceil = 35 truck trips and \lceil 347/25 \rceil = 14 trailer loads. That is the throughput count of Lecture 1.3, Sec. 5, done in loads rather than machines, and it bounds the cost from below: no plan costs less than extraction plus the fewest loads, the Bounds check of Lecture 1.2.

The same flow balance gives the most setups in a week, \bar{z}_{ij}, that Model 2 needs, by Eq. 5 in Lecture 4.3 with the demand summed over the materials. Through the trucks, stage 2, and the trailers, stage 3, pass the 347 tons of demand, 218 of the first material and 129 of the second, plus the five tons of the second material wanted at the destination at the end less the five there at the start; the site and the station start and end empty. No week can carry more than all of them, so:

\begin{aligned} \bar{z}_{2j} &= \left\lceil \frac{1}{10} \Bigl( (218 + 129) + (5 - 5) \Bigr) \right\rceil = \left\lceil \frac{347}{10} \right\rceil = \lceil 34.7 \rceil = 35 \\ \bar{z}_{3j} &= \left\lceil \frac{1}{25} \Bigl( (218 + 129) + (5 - 5) \Bigr) \right\rceil = \left\lceil \frac{347}{25} \right\rceil = \lceil 13.88 \rceil = 14 \end{aligned}

Extraction, which shares nothing, has no setups. The fewest loads over the ten weeks are the most in any one week, a bound as loose as possible, as it should be; it just has to be finite.

Code block 3 enters the data, Code block 4 computes both bounds, and Code block 5 solves the problem with the implementation of Model 2:

# Code block 3: Ex. 1's data
d = [13 15 21 14 12 11 45 25 48 14      # demand in week j for material k
     11  9 17 15 18 11  6  7 15 20]'    #   (ton)
t = size(d, 1)                          # number of weeks
cᵖ = [120 200; 0 0; 0 0]                # extract, truck, trailer ($/ton)
UBˣ = [26 15; Inf Inf; Inf Inf]         # extraction capacity (ton/week)
cˢ = [0, 200, 800]                      # cost per truck, per trailer ($)
u = [Inf, 10, 25]                       # per truck, per trailer (ton)
m, g = size(cᵖ)                         # stages, materials
h = 0.15/52                             # weekly carrying rate (1/week)
cⁱ = cumsum(cᵖ .+ cˢ./u, dims = 1)*h    # inventory cost ($/ton-week)
y⁰ = [0 0; 0 0; 0 5]                    # initial inventory (ton)
yᵗ⁺¹ = [0 0; 0 0; 0 5]                  # final inventory (ton)
uʸ = [20 20; Inf Inf; Inf Inf]          # storage capacity (ton)
LBʸ = [reshape(y⁰, m, 1, g) zeros(m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)]
UBʸ = hcat(reshape(y⁰, m, 1, g), repeat(reshape(uʸ, m, 1, g), 1, t-1),
           reshape(yᵗ⁺¹, m, 1, g));
# Code block 4: a lower bound on the cost, and the most setups
ship = sum(d) - sum(y⁰) + sum(yᵗ⁺¹)            # tons to ship
@show min_loads = ceil.(Int, ship ./ u[2:3])   # fewest trucks, trailers
max_loads = min_loads                          # the most in any one week
z̄ = [zeros(Int, 1, t); repeat(max_loads, 1, t)] # none to extract
LB = sum(cᵖ[1, :] .* vec(sum(d, dims = 1))) + sum(cˢ[2:3] .* min_loads)
min_loads = ceil.(Int, ship ./ u[2:3]) = [35, 14]
70160
# Code block 5: Ex. 1 solved with prodinv_coupled
TCᵒ, xᵒ, yᵒ, zᵒ = prodinv_coupled(cᵖ, cˢ, cⁱ, d, UBˣ, u, z̄, LBʸ, UBʸ)
@show TCᵒ
TCᵖ = sum(reshape(cᵖ, m, 1, g) .* xᵒ)            # production
TCⁱ = sum(reshape(cⁱ, m, 1, g) .* yᵒ[:, 2:end, :])  # inventory
TCˢ = sum(cˢ .* zᵒ)                               # trucks and trailers
@show TCᵖ
@show TCⁱ
@show TCˢ
prt([zᵒ[2:3, :]; d'];
    rows = ["Trucks", "Trailers", "Demand 1", "Demand 2"],
    cols = string.(1:t), row_title = "Week")
TCᵒ = 70264.66538461528
TCᵖ = 51960.0
TCⁱ = 104.66538461538462
TCˢ = 18200
    Week   1   2   3   4   5   6   7   8   9  10
────────────────────────────────────────────────
  Trucks   3   2   5   3   2   4   4   3   7   2
Trailers   1   1   2   1   1   1   2   1   3   1
Demand 1  13  15  21  14  12  11  45  25  48  14
Demand 2  11   9  17  15  18  11   6   7  15  20

The plan sends 35 trucks and 14 trailer loads over the ten weeks, exactly the fewest that can carry the 347 tons, so its transport cost is the bound’s, and its cost, $70,264.67, is $104.67 above the bound of $70,160, which is its inventory cost.

Total cost $70,264.67: extraction $51,960, inventory $104.67, and 35 trucks and 14 trailers $18,200.

Example 1(b): Cost of a given plan by hand

Using some different data (as noted below, otherwise use the data given in Ex. 1) and only a three-week planning horizon, determine the total production, inventory, and transport cost over the horizon. The forecasted demand for both materials is 20, 10, 45 and 12, 25, 5 tons, respectively. It costs $600 and $400 to extract each ton of material at the facility, and the annual inventory carrying rate is 0.5. The facility can extract up to 30 and 20 tons per week of each material, respectively. Currently, 20 tons of the second material is in inventory at the final destination. A different amount of material can be in inventory at the end of the planning period. For each material, each period, 30, 30, 30 and 16, 17, 17 tons, respectively, are produced; 30, 10, 50 and 0, 20, 30 tons are transported to the staging station; and 22, 8, 60 and 0, 17, 33 tons are transported to the final destination.

Fig. 3 sets the plan out on each material’s network, with both materials’ trucks and trailers each week below them: red is given, and blue has to be determined, here the inventory each node carries out, what came in less what went on, and each week’s loads:

Figure 3: Ex. 1(b)’s plan on each material’s network, a week to a column, in which red is given and blue has to be determined: (a) and (b) the extraction, truck and trailer flows, the demand and the inventory at the start, given, and the inventory each node carries out, determined by flow balance; (c) the two materials’ tons on each week’s trucks and trailers, given, and their sum and the loads that carry it at each vehicle’s capacity, determined.

The plan’s flows are given, so the inventories follow from flow balance, as in Ex. 5(b) in Lecture 4.3: at each stage, the inventory carried out of a week is what came in less what went on. The site has nothing at the start and the staging station nothing; the destination has the 20 tons of the second material. For the first material,

\begin{alignedat}{3} \text{site:}\enspace & 0 + 30 - 30 = 0, &\enspace 0 + 30 - 10 &= 20, &\enspace 20 + 30 - 50 &= 0 \\ \text{station:}\enspace & 0 + 30 - 22 = 8, &\enspace 8 + 10 - 8 &= 10, &\enspace 10 + 50 - 60 &= 0 \\ \text{destination:}\enspace & 0 + 22 - 20 = 2, &\enspace 2 + 8 - 10 &= 0, &\enspace 0 + 60 - 45 &= 15 \end{alignedat}

and for the second,

\begin{alignedat}{3} \text{site:}\enspace & 0 + 16 - 0 = 16, &\enspace 16 + 17 - 20 &= 13, &\enspace 13 + 17 - 30 &= 0 \\ \text{station:}\enspace & 0 + 0 - 0 = 0, &\enspace 0 + 20 - 17 &= 3, &\enspace 3 + 30 - 33 &= 0 \\ \text{destination:}\enspace & 20 + 0 - 12 = 8, &\enspace 8 + 17 - 25 &= 0, &\enspace 0 + 33 - 5 &= 28 \end{alignedat}

The loads come from the combined tons each week. The trucks carry 30 + 0 = 30, 10 + 20 = 30 and 50 + 30 = 80 tons, 3 + 3 + 8 = 14 trucks of 10 tons; the trailers carry 22 + 0 = 22, 8 + 17 = 25 and 60 + 33 = 93 tons, 1 + 1 + 4 = 6 trailers of 25 tons. A week whose tons are an exact multiple of a load’s capacity, as the trucks’ 30 tons are twice, needs exactly that many loads and no more. With the carrying rate of 0.5 a year, h = 0.5/52 a week, and each ton charged its share of each load, assumption (e) of Model 2, the inventory costs are h times 600, 620 and 652 $/ton for the first material at the site, the station and the destination, and 400, 420 and 452 for the second. Then

\begin{aligned} \text{production:}\quad & 600\,(90) + 400\,(50) = 74{,}000 \\ \text{inventory:}\quad & \tfrac{0.5}{52}\bigl[600\,(20) + 620\,(18) + 652\,(17) \\ & \qquad + 400\,(29) + 420\,(3) + 452\,(36)\bigr] = 609.38 \\ \text{transport:}\quad & 200\,(14) + 800\,(6) = 7{,}600 \end{aligned}

The plan’s total cost is 74{,}000 + 609.38 + 7{,}600 = 82{,}209.38 dollars.

Example 1(c): Costs of the plan with code

Compute part (b)’s three costs from the plan with code, and check them against the answers published with the problem.

This part is the one done with code, as in a homework problem; part (b) is the one done by hand, as on an exam. Code block 6 computes the same three costs from the plan and checks them against the answers published with the problem, the Landmark check of Lecture 1.2:

# Code block 6: Ex. 1(b)'s plan, and its costs
X = cat([30 30 30; 30 10 50; 22 8 60],   # x[i,j,k]: stage i, week j,
        [16 17 17; 0 20 30; 0 17 33];    #   material k (ton)
        dims = 3)
Db = [20 12; 10 25; 45 5]                # demand in week j, material k
Y = zeros(3, 4, 2)                       # inventory, by flow balance
Y[3, 1, 2] = 20
for k in 1:2, j in 1:3
    for i in 1:2
        Y[i, j+1, k] = Y[i, j, k] + X[i, j, k] - X[i+1, j, k]
    end
    Y[3, j+1, k] = Y[3, j, k] + X[3, j, k] - Db[j, k]
end
loads = ceil.(Int,
              dropdims(sum(X, dims = 3), dims = 3)[2:3, :] ./ u[2:3])
cᵖb = [600 400; 0 0; 0 0]
cⁱb = cumsum(cᵖb .+ cˢ./u, dims = 1)*0.5/52
PC = sum(reshape(cᵖb, 3, 1, 2) .* X)
IC = sum(reshape(cⁱb, 3, 1, 2) .* Y[:, 2:end, :])
TrC = sum(cˢ[2:3] .* loads)
@assert (PC, round(IC, digits = 2), TrC) == (74000, 609.38, 7600)
@show PC
@show IC
@show TrC
prt(loads; rows = ["Trucks", "Trailers"], cols = string.(1:3),
    row_title = "Week")                  # loads in each week
1
@assert stops the script with an error unless the expression after it is true. A run that gets past this line has confirmed that the three costs computed from the plan, the inventory cost rounded to the cent, are the answers published with the problem, $74,000, $609.38 and $7,600.
PC = 74000
IC = 609.3846153846154
TrC = 7600
    Week  1  2  3
─────────────────
  Trucks  3  3  8
Trailers  1  1  4

The published answer is the one computed here, and the one found by hand in part (b). A key from an earlier offering printed $82,409.38 for the same problem, $200 more: its check had rounded week 2’s 30 tons up to four trucks rather than three, the kind of error a Landmark check exists to catch.

Production $74,000, inventory $609.38, and transport $7,600, for a total of $82,209.38.

If each truck could carry only one type of raw material, it would decouple the problem into two separate problems that can be solved independent of each other since sharing the truck between both types of raw material is the only thing that couples both problems.

3. Linking constraints

In the following model, binary-variable linking constraints are used to ensure products cannot be produced together simultaneously on the same resource. The setup indicator variables, z_{ijk}, do not appear in the objective function and are only used to control shared access to each resource through constraints (c) and (f).

Model 3 generalizes Model 1 in Lecture 4.3: each product has its own network, its capacity at a stage gated by whether the stage is set up for it, and the linking rows join the networks.

minimize: total production and inventory cost over the planning horizon

solve for:
(a) production of each product at each stage in each period;
(b) inventory of each product at each stage carried into each period;
(c) product each stage is set up for in each period.

subject to:
(a) Flow balance: at each stage that feeds the next, for each product, what is produced or carried in is either passed on to the next stage or carried out;
(b) Flow balance: at the last stage, which feeds each product’s demand, what is produced or carried in either meets the period’s demand or is carried out;
(c) Capacity: production of a product at eacha stage in eacha period is no more than its capacity, and zero unless the stage is set up for it;
(d) Initial and final inventory: inventory of each product at each stage at the start and at the end of the horizon is given;
(e) Storage: inventory of each product at each stage between periods is no more than its storage capacity;
(f) Linking: each stage is set up for at most one product in each period.

assumptions:
(a) production cost and inventory cost per ton of each product at each stage are constant;
(b) demand for each product in each period is given;
(c) production can pass through every stage within the period it starts in;
(d) setting a stage up for a product costs nothing and takes none of its capacity.

Model 3: Exclusive shared resources
Model 3 formulation: Exclusive shared resources

\begin{array}{rrclll} \mathrlap{\text{Minimize}} & & & & & \\[2pt] \mathrlap{\qquad \displaystyle \sum_{i=1}^{m} \sum_{j=1}^{t} \sum_{k=1}^{g} c_{ik}^p\, x_{ijk} + \sum_{i=1}^{m} \sum_{j=2}^{t+1} \sum_{k=1}^{g} c_{ik}^i\, y_{ijk}} & & & & & \\[16pt] \mathrlap{\text{subject to}} & & & & & \\[8pt] & -x_{ijk} + x_{(i+1)jk} - y_{ijk} + y_{i(j+1)k} & = & 0, & \hphantom{k}\mathllap{i} = 1, \dots, m-1 & (a) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & -x_{mjk} - y_{mjk} + y_{m(j+1)k} & = & -d_{jk}, & \hphantom{k}\mathllap{j} = 1, \dots, t & (b) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & x_{ijk} & \le & u_{ik}\, z_{ijk}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (c) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i1k} & = & y_{ik}^0, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i(t+1)k} & = & y_{ik}^{t+1}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{ijk} & \le & u_{ik}^y, & \hphantom{k}\mathllap{i} = 1, \dots, m & (e) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 2, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & \textcolor{#d21f26}{\small\text{Linking}}\quad\mathopen{} \smash{\displaystyle \sum_{k=1}^{g}}\, z_{ijk} & \le & 1, & \hphantom{k}\mathllap{i} = 1, \dots, m & (f) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[8pt] & x_{ijk},\ y_{ijk} & \ge & 0 & & \\[8pt] & z_{ijk} & \in & \{0, 1\} & & \end{array} \tag{3}

where

z_{ijk}
= \begin{cases} 1, & \text{if stage } i \text{ is set up for product } k \text{ in period } j \\ 0, & \text{otherwise} \end{cases}
c_{ik}^i
= inventory cost of product k at stage i ($/ton-period)
= h\,(c_{1k}^p + c_{2k}^p + \cdots + c_{ik}^p).

The other symbols are those of Eq. 2. Both lines labeled (d) in Eq. 3 are row (d).

Model 3 implementation: Exclusive shared resources
# Model: exclusive shared resources
function prodinv_excl(cᵖ, cⁱ, d, u, LBʸ, UBʸ)
    m, g = size(u)
    t = size(d, 1)
    model = Model(HiGHS.Optimizer)
    @variable(model, x[i=1:m, j=1:t, k=1:g] ≥ 0)
    @variable(model, LBʸ[i,j,k] ≤ y[i=1:m, j=1:t+1, k=1:g] ≤ UBʸ[i,j,k])
    @variable(model, z[i=1:m, j=1:t, k=1:g], Bin)
    @objective(model, Min,
        sum(cᵖ[i,k]*x[i,j,k] for i=1:m, j=1:t, k=1:g) +
        sum(cⁱ[i,k]*y[i,j,k] for i=1:m, j=2:t+1, k=1:g))
    @constraint(model, flowbal[i=1:m-1, j=1:t, k=1:g],              # (a)
        -x[i,j,k] + x[i+1,j,k] - y[i,j,k] + y[i,j+1,k] == 0)
    @constraint(model, laststage[j=1:t, k=1:g],                     # (b)
        -x[m,j,k] - y[m,j,k] + y[m,j+1,k] == -d[j,k])
    @constraint(model, capacity[i=1:m, j=1:t, k=1:g],               # (c)
        x[i,j,k] ≤ u[i,k]*z[i,j,k])
    @constraint(model, linking[i=1:m, j=1:t],                       # (f)
        sum(z[i,j,k] for k=1:g) ≤ 1)

    set_silent(model)
    set_attribute(model, "mip_rel_gap", 0.0)
    optimize!(model)
    if termination_status(model) == JuMP.OPTIMAL
        return (TC = objective_value(model), x = snapvals(value.(x)),
                y = snapvals(value.(y)), z = Int.(snapvals(value.(z))))
    end
    error(termination_status(model))
end
prodinv_excl (generic function with 1 method)

Constraints (a) and (b) are for flow balance, (c) for production capacity, and (f) are linking constraints that ensure that only one product is produced at each stage during each period. Constraints (a)-(e) all refer to each product separately, and only (f) refer to multiple products together for each stage and period.

With exclusive shared resources, the model can be thought of as two separate math programming models, one for each product. In the constraint matrix of the whole model, Fig. 4, everything outside the two products’ blocks is zero, and the only thing that connects the two math programs is the linking constraints at the bottom; without them, two separate models would be solved. That one simple structure has long been used to decompose such problems: instead of one large integrated model, each product’s model is solved separately, and a master problem combines them, by Lagrangian relaxation and many other decomposition techniques, the subject of literally thousands of papers. Most of that is probably not needed for many problems today. A large enough problem may still need some decomposition, but solvers are good enough on many fairly large problems that they do much of it themselves as part of their presolve, and it is not something a logistics engineer needs to be much concerned about now. In the formulation, the one new row is (f), the linking constraint; otherwise the model is like the setup model of Lecture 4.3, its z variables gating the capacity. Although z is a decision variable, it does not appear in the objective, which has only the production and inventory terms; where Lecture 4.3’s setup model had three terms, the setup cost among them, here z is used only to make the connection.

Example 2: Plant shared by two products

A plant can use a three-stage process to produce two products. A 13-week rolling horizon is used for planning production. The products’ forecasted demand, in tons, is given in Table 4:

Table 4: Ex. 2’s forecast demand in each period, each product, and its total over the 13 weeks (ton).
Week 1 2 3 4 5 6 7 8 9 10 11 12 13 Total
Product 1 6 40 33 24 29 24 16 13 14 17 18 43 25 302
Product 2 17 14 17 4 7 10 12 18 13 23 8 17 3 163

The plant can produce up to 60, 55, and 50 and 50, 45, and 35 tons per week for each stage of each product, respectively; has production costs of $12, $75, and $35 and $20, $130, and $60 per ton for each stage of each product, respectively. The annual inventory carrying rate is 0.3. The first two weeks’ demand for the second product is being held as finished product inventory. The final inventory for all stages of both products is zero. Determine the amount of each product that should be produced to minimize total costs over the planning horizon.

Each stage is shared exclusively by the two products, so the problem is Model 3 with three stages, two products and 13 weeks. Before solving it, a count by hand says whether the weeks are enough. Over the 13 weeks of Table 4 the first product needs 302 tons, and the second 163 less the 31 already held, 132 tons. A week at a stage goes to one product, so at stage 3, which can make 50 tons a week of the first product or 35 of the second, the first needs at least \lceil 302/50 \rceil = 7 weeks and the second \lceil 132/35 \rceil = 4, 11 of the 13; stages 1 and 2 need 9 each. That is Lecture 1.3’s throughput count (its Sec. 5) for a stage shared one product at a time, and it is only a necessary condition, but it commits to an estimate before any model runs: the plan should be feasible, with two weeks to spare at stage 3, the Prior check of Lecture 1.2.

With exclusive shared resources there almost always has to be some inventory on hand at the start. With a single product, as in Lecture 4.3, a plan could start with no initial inventory and work. Here, if the 31 tons of the second product were replaced by zero, the model would be infeasible. In the first week, 6 tons of the first product and 17 of the second are demanded, and with nothing on hand both would have to be produced that week; but a stage can make one product or the other in a week, not both, as it could under a coupling constraint. So some inventory is required, enough to meet the other product’s demand while a stage produces the current one. The model also assumes that all three stages can be done within one period. If a stage took two weeks, the network would have diagonal arcs, from period 1 to period 3, in place of the vertical ones. That is an implicit assumption: nowhere does the problem state it, and it would be stated only if it did not hold, assumption (c) of Model 3, the Assumptions check of Lecture 1.2.

Code block 7 enters the data and the bounds on inventory:

# Code block 7: Ex. 2's data, and the bounds on inventory
# demand in each period, each product (ton)
d = [6 40 33 24 29 24 16 13 14 17 18 43 25
    17 14 17  4  7 10 12 18 13 23  8 17  3]'
t = size(d, 1)                        # number of periods
# capacity of each stage for each product (ton)
u = [60 50; 55 45; 50 35]
m = size(u, 1)                        # number of production stages
g = size(u, 2)                        # number of products
# production cost for each stage, each product ($/ton)
cᵖ = [12 20; 75 130; 35 60]
# weekly inventory carrying rate (1/wk)
@show h = 0.3/(365.25/7)
# inventory cost for each stage, each product ($/ton)
cⁱ = cumsum(cᵖ, dims=1)*h
# initial inventory of each stage, each product (ton)
@show y⁰ = [0 0; 0 0; 0 sum(d[[1 2], 2])]
# final inventory of each stage for each product (ton)
yᵗ⁺¹ = zeros(m, g)
# convert y⁰ and yᵗ⁺¹ from 2D (m x g) to 3D (m x t x g)
LBʸ = [reshape(y⁰, m, 1, g) zeros(m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)]
UBʸ = [reshape(y⁰, m, 1, g) fill(Inf, m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)];
h = 0.3 / (365.25 / 7) = 0.005749486652977412
y⁰ = [0 0; 0 0; 0 sum(d[[1 2], 2])] = [0 0; 0 0; 0 31]

Line 13 is the weekly carrying rate, the annual rate over the number of weeks in a year, a rate per week ($/$-week), the Units check of Lecture 1.2. Line 17 is the initial inventory, the first two weeks’ demand for the second product, 31 tons, held at stage 3. As in Lecture 4.3, the bounds LBʸ and UBʸ fix the inventory into period 1 and out of period t, now three-dimensional, a matrix of stages by periods for each product.

Code block 8 solves the problem with the implementation of Model 3:

# Code block 8: Ex. 2 solved with prodinv_excl
TCᵒ, xᵒ, yᵒ, zᵒ = prodinv_excl(cᵖ, cⁱ, d, u, LBʸ, UBʸ)
@show TCᵒ;
TCᵒ = 64765.105544147846

Code block 9 prints the plan for each product, its production with its demand beneath, its inventory and the stages set up for it, in a loop over the products that titles each table with its product:

# Code block 9: the plan for each product
stages = string.("Stage ", 1:m)                 # the rows of each table
for k in 1:g
    println()                                   # a blank line above each
    prt([xᵒ[:,:,k]; d[:,k]']; rows = [stages; "Demand"],
        cols = string.(1:t), row_title = "Week",
        title = "Product $k: production level and demand")
    println()
    prt(yᵒ[:,:,k]; rows = stages, cols = string.(1:t+1),
        row_title = "Week", title = "Product $k: inventory level")
    println()
    prt(zᵒ[:,:,k]; rows = stages, cols = string.(1:t),
        row_title = "Week", title = "Product $k: set up")
end

Product 1: production level and demand
   Week   1   2   3   4   5   6   7   8   9  10  11  12  13
───────────────────────────────────────────────────────────
Stage 1  29  50   0  27  50   0  29   0  49   0   0  43  25
Stage 2  29  50   0  27  50   0  29   0  49   0   0  43  25
Stage 3  29  50   0  27  50   0  29   0  49   0   0  43  25
 Demand   6  40  33  24  29  24  16  13  14  17  18  43  25

Product 1: inventory level
   Week  1   2   3  4  5   6  7   8  9  10  11  12  13  14
──────────────────────────────────────────────────────────
Stage 1  0   0   0  0  0   0  0   0  0   0   0   0   0   0
Stage 2  0   0   0  0  0   0  0   0  0   0   0   0   0   0
Stage 3  0  23  33  0  3  24  0  13  0  35  18   0   0   0

Product 1: set up
   Week  1  2  3  4  5  6  7  8  9  10  11  12  13
──────────────────────────────────────────────────
Stage 1  1  1  0  1  1  0  1  0  1   0   0   1   1
Stage 2  1  1  0  1  1  0  1  0  1   0   0   1   1
Stage 3  1  1  0  1  1  0  1  0  1   0   0   1   1

Product 2: production level and demand
   Week   1   2   3  4  5   6   7   8   9  10  11  12  13
─────────────────────────────────────────────────────────
Stage 1   0   0  28  0  0  22   0  31   0  23  28   0   0
Stage 2   0   0  28  0  0  22   0  31   0  23  28   0   0
Stage 3   0   0  28  0  0  22   0  31   0  23  28   0   0
 Demand  17  14  17  4  7  10  12  18  13  23   8  17   3

Product 2: inventory level
   Week   1   2  3   4  5  6   7  8   9  10  11  12  13  14
───────────────────────────────────────────────────────────
Stage 1   0   0  0   0  0  0   0  0   0   0   0   0   0   0
Stage 2   0   0  0   0  0  0   0  0   0   0   0   0   0   0
Stage 3  31  14  0  11  7  0  12  0  13   0   0  20   3   0

Product 2: set up
   Week  1  2  3  4  5  6  7  8  9  10  11  12  13
──────────────────────────────────────────────────
Stage 1  0  0  1  0  0  1  0  1  0   1   1   0   0
Stage 2  0  0  1  0  0  1  0  1  0   1   1   0   0
Stage 3  0  0  1  0  0  1  0  1  0   1   1   0   0

Each week every stage is set up for one product, and every stage makes the same amount of it, so the products move through all three stages within the week and all of the inventory is held at stage 3, as finished product. The first product is made in 8 weeks and the second in 5, the 13 weeks between them; the count by hand said at least 7 and 4. The stages are in step because each stage upstream can make at least as much of each product in a week as stage 3, so a plan that repeats stage 3’s schedule at stages 1 and 2 holds no inventory between them, and with nothing charged for a switch, nothing is gained by running a stage ahead; Ex. 3 adds that charge.

Fig. 4 draws the constraint matrix of the model just solved by blocks, its columns grouped by product and its rows by product, the linking row last:

Show the code that draws this figure
# Code block 10: the constraint matrix by blocks, a block per product
# Product k's block spans x in [(k-1)W, kW] and y in [-kH, -(k-1)H];
# its columns are x, y, (v,) z at xc, yc, vc, zc, its rows top down
ink, boxc = colorant"#252525", colorant"#8c8c8c"
dashc = colorant"#969696"
mi = Makie.MathTeXEngine.texfont(:italic)
mr = Makie.MathTeXEngine.texfont(:math)
mb = Makie.MathTeXEngine.texfont(:bold)
it(s) = rich(s; font = mi)                        # a symbol, in italics
up(s) = rich(s; font = mr)                        # digits, operators
csym(p) = rich(it("c"), superscript(it(p)))       # c with superscript p
zsub(k) = rich(it("z"), subscript(up(k)))         # z with subscript k
function blocks!(ax; switch = false, W = 7.0, ls = 13, ms = 15)
    hidedecorations!(ax); hidespines!(ax)
    xc, yc, vc, zc = 1.15, 2.6, 3.65, 5.45        # column centres
    fb, cap, sw = (-0.10, -1.05), (-1.15, -1.95), (-2.05, -2.85)
    H = switch ? 2.95 : 2.05                      # block height
    L = 0.62                                      # linking-row height
    rect(x0, x1, y0, y1; c = boxc, w = 1.0) =
        poly!(ax, Rect(x0, y1, x1 - x0, y0 - y1); color = :transparent,
              strokecolor = c, strokewidth = w)
    dashed(x0, x1, y0, y1) =
        lines!(ax, [x0, x1, x1, x0, x0], [y0, y0, y1, y1, y0];
               color = dashc, linewidth = 1.2, linestyle = :dash)
    lbl(x, y, s; fs = ms, al = (:center, :center), rot = 0.0) =
        text!(ax, x, y; text = s, fontsize = fs, color = ink, align = al,
              rotation = rot)
    top(b) = b[1] - 0.27                          # a box's two lines:
    bot(b) = b[2] + 0.29                          #   name over variables
    dashed(W, 2W, 0, -H); lbl(1.5W, -0.5H, up("0"); fs = ms + 2)
    dashed(0, W, -H, -2H); lbl(0.5W, -1.5H, up("0"); fs = ms + 2)
    for k in 1:2
        ox, oy = (k - 1) * W, -(k - 1) * H        # the block's corner
        rect(ox, ox + W, oy, oy - H; c = ink, w = 1.6)
        lbl(ox + xc, 0.36, csym("p")); lbl(ox + yc, 0.36, csym("i"))
        switch && lbl(ox + vc, 0.36, csym("w"))   # the objective's
        lbl(ox + zc, 0.36, rich("0"; font = mb))  #   coefficients
        lbl(ox - 0.32, oy - H / 2, "Product $k"; fs = ls + 1,
            rot = π / 2)
        b = oy .+ fb                              # rows (a) and (b)
        rect(ox + 0.10, ox + 3.60, b...)
        lbl(ox + 1.85, top(b), "Flow balance (a), (b)"; fs = ls)
        lbl(ox + xc, bot(b), it("x")); lbl(ox + yc, bot(b), it("y"))
        b = oy .+ cap                             # row (c)
        rect(ox + 0.10, ox + 2.20, b...)
        lbl(ox + xc, top(b), "Capacity (c)"; fs = ls)
        lbl(ox + xc, bot(b), it("x"))
        rect(ox + zc - 0.40, ox + zc + 0.40, b...)
        lbl(ox + zc, top(b), rich(up("−"), it("u")))
        lbl(ox + zc, bot(b), it("z"))
        lbl(ox + zc + 0.55, sum(b) / 2, up("≤ 0"); al = (:left, :center))
        if switch                                 # row (g)
            b = oy .+ sw
            rect(ox + 2.40, ox + 4.90, b...)
            lbl(ox + vc, top(b), "Switchover (g)"; fs = ls)
            lbl(ox + vc, bot(b), it("v"))
            rect(ox + zc - 0.40, ox + zc + 0.40, b...)
            lbl(ox + zc, top(b), up("1")); lbl(ox + zc, bot(b), it("z"))
            lbl(ox + zc + 0.55, sum(b) / 2, up("≤ 0");
                al = (:left, :center))
        end
    end
    ly0, ly1 = -2H, -2H - L                       # row (f), across both,
    poly!(ax, Rect(0, ly1, 2W, L); color = :white, strokecolor = datac,
          strokewidth = 1.6)                      #   outlined in red
    ym = (ly0 + ly1) / 2
    lbl(0.15, ym, "Linking (f)"; fs = ls, al = (:left, :center))
    lbl(zc, ym, zsub("1")); lbl(W, ym, up("+"))
    lbl(2W - zc, ym, zsub("2"))
    lbl(2W + 0.12, ym, up("≤ 1"); al = (:left, :center))
    limits!(ax, -0.70, 2W + 0.95, ly1 - 0.12, 0.72)
    return nothing
end
fig = Figure(size = (680, 252), figure_padding = 4)
blocks!(Axis(fig[1, 1]; aspect = DataAspect()))
fig
Figure 4: The constraint matrix of Ex. 2’s model by blocks: each product’s flow balance, rows (a) and (b), and capacity, row (c), in a block of its own over its objective coefficients, zeros outside the two blocks, and the linking row (f) at the bottom, outlined in red, the only row that joins the products.

The two products’ models share nothing but the linking rows, which is the structure the decomposition methods above exploit.

Calculate total production cost and total inventory cost:

size(cᵖ), size(xᵒ)   # Code block 11: cᵖ to reshape to (3, 1, 2) for xᵒ
((3, 2), (3, 13, 2))
# Code block 12: the production and inventory costs
# Reshaped cᵖ broadcast for multiplication with xᵒ
TCᵖ = sum((reshape(cᵖ,m,1,g).*xᵒ)[:])
TCⁱ = sum((reshape(cⁱ,m,1,g).*yᵒ[:,2:end,:])[:])  # First period excluded
TCᵖ, TCⁱ
(64564.0, 201.1055441478439)
TCᵖ + TCⁱ, TCᵒ   # Code block 13: their sum, and the total
(64765.105544147846, 64765.105544147846)

The production cost is the same in every plan that meets the demand, since every ton demanded and not on hand has to pass through all three stages, so what the plan determines is the inventory, $201.11 of the $64,765.11. The two routes to the total agree, the Balance check of Lecture 1.2.

Without the linking constraint, each product is a separate single-product model, which is Model 2 with nothing shared: no stage has a shared capacity (u_i = \infty) and no setups. Code block 14 solves Ex. 2 that way:

# Code block 14: Ex. 2 without linking, each product on its own
TCⁿ = prodinv_coupled(cᵖ, zeros(m), cⁱ, d, u, fill(Inf, m),
                      zeros(Int, m, t), LBʸ, UBʸ).TC
TCⁿ, TCᵒ
(64580.90349075975, 64765.105544147846)

Without linking the plan costs $64,580.9, less than with it: adding a constraint can never improve a solution, the first of the two facts of Sec. 1, and here it costs $184.2, the Bounds check of Lecture 1.2.

Inventory is held only at the third stage, never at the first two, because nothing in this problem makes sharing the resources costly: the only cost of sharing is that the products cannot both use a resource at the same time. An example without a switchover cost is therefore not terribly realistic, since there are few situations in which the only thing connecting products is that they cannot both use a resource; otherwise they are two separate problems. The setup indicators are either all 0 or all 1 across the stages in a week, and nothing very interesting happens. The example is a step toward the switchover model of Sec. 4: it is that model without its switchover constraints, the model to build and solve first, before the switchover constraints are implemented, to make sure it works, even though it is not the problem of interest. Once it works, the problem of interest, with the switchover cost, can be taken up.

Total cost $64,765.11: production $64,564 and inventory $201.11, each week every stage making one product, all of the inventory held at stage 3.

4. Switchover costs

If multiple products are produced using exclusive shared resources, there is often a cost associated with reconfiguring or setting up the resource to produce a product if it was previously producing a different product; examples of such switchover costs would be the material and labor cost associated with re-tooling/re-calibration of machines, cleaning/sterilization of equipment, and the lost production capacity while a resource is not available during set up, the last of which the model below leaves out, its assumption (d).

In the following model, the switchover cost is separate from the production cost in the objective function. There are no setup costs in this model; instead, there are switchover costs. They differ from setup costs in that the switchover cost is incurred only in a period when production switches to a different product at a given stage. As long as the same product continues to be produced in the next period, no additional switchover cost is incurred. This differs from a setup cost, which is incurred every period a stage produces, as in Lecture 4.3.

Switchover costs extend the linking constraints of Sec. 3. A stage is still used exclusively for one product or the other, and what is added is the cost of the switchover each time the stage is switched to a product. Without that cost, a plan would probably switch between the products more frequently; with it, it is often to the plan’s advantage to keep a stage producing the same product a period longer and avoid a switchover, depending on the switchover cost’s relative magnitude. Inventory is what makes that possible: more of a product can be produced while a stage is set up for it, and the inventory then covers its demand over a longer stretch in which it is not produced. That inventory is economic stock, the role Lecture 3.3’s classification (Table 1 in Lecture 3.3) gives to inventory held to make production cheaper. Exactly how to do that is hard to work out, and it is the math programming model that does all of the logic. Its objective now has three terms.

The first such problem was based on a project that two colleagues did for Ford Motor Company, which made glass not only for automobiles but for many commercial buildings, such as skyscrapers. Switching from one color of glass to another required shutting down all of the furnaces, and then weeks and millions of dollars to clear out the molten glass before switching over to produce another color. Ford’s planners were solving linear programs, since that was all they could handle, and determining by hand when capacity would be available for each of the products across its glass facilities in the United States. It was not until later that mixed-integer programming became good enough to model the switchover itself.

Producing complementary products on shared equipment is one way to cope with demand that varies over the year. In the extreme, a winter seasonal product and a summer one that use the same equipment can simply switch over twice a year; other batching is shorter term. Sharing makes sense where the equipment itself is expensive, and it goes with a more flexible production process: the easier a process is to automate, the easier it is to change over. The Toyota Production System, the origin of just-in-time and lean manufacturing, began with exactly this in the 1950s. Japan was devastated after World War II, and visitors from it to Ford’s Rouge River plant in Detroit, a massive, fully integrated facility where raw iron ore came in at one end and cars came out at the other, realized that the country could never hope to build such a plant, since it did not have the demand, and that it could compete only on flexibility:2 one production line able to produce many different models, where Ford had dedicated lines producing thousands of one product at the lowest possible unit cost. Mixing models on a line was then really a nonstarter in the United States. In Detroit, the factories shut down for two weeks each summer to change models, cranes moving the die presses into place, and then produced the same parts for the next year.3 Toyota spent 20 years relentlessly reducing the time required to switch over from one vehicle to another, to a couple of hours on one machine rather than two weeks, and so perfected just-in-time production.4 None of what industrial engineers now learn about it came from the United States, whose massive scale let it dedicate everything; it was the flexibility Japan showed that made it a competitor and ultimately forced everyone down that road.

Model 4 generalizes Model 3 by adding a switchover indicator for each stage, period and product, its cost to the objective, and the rows (g) that set it.5 A switchover is treated as what setup reduction calls an external setup, one done while the stage is still producing, rather than an internal one, done only once the stage has stopped:6 it costs money but takes none of the stage’s capacity, which here is mostly its time. That is the model’s assumption (d), written down as the Model Format Reference asks of every model.

minimize: total production, inventoryand switchover cost over the planning horizon

solve for:
(a) production of each product at each stage in each period;
(b) inventory of each product at each stage carried into each period;
(c) product each stage is set up for in each period;
(d) switchovers of each stage to each product in each period.

subject to:
(a) Flow balance: at each stage that feeds the next, for each product, what is produced or carried in is either passed on to the next stage or carried out;
(b) Flow balance: at the last stage, which feeds each product’s demand, what is produced or carried in either meets the period’s demand or is carried out;
(c) Capacity: production of a product at a stage in a period is no more than its capacity, and zero unless the stage is set up for it;
(d) Initial and final inventory: inventory of each product at each stage at the start and at the end of the horizon is given;
(e) Storage: inventory of each product at each stage between periods is no more than its storage capacity;
(f) Linking: each stage is set up for at most one product in each period;
(g) Switchover: a stage set up for a product in a period that it was not set up for in the period before is switched over to it, the setup before the first period given.

assumptions:
(a) production cost and inventory cost per ton of each product at each stage are constant;
(b) demand for each product in each period is given;
(c) production can pass through every stage within the period it starts in;
(d) setting a stage up for a product costs nothinga switchover to a product costs the same whatever product the stage was set up for before, and takes none of itsthe stage’s capacity;
(e) inventory carries no share of the switchover costs.

Model 4: Switchover costs
Model 4 formulation: Switchover costs

\begin{array}{rrclll} \mathrlap{\text{Minimize}} & & & & & \\[2pt] \mathrlap{\qquad \displaystyle \sum_{i=1}^{m} \sum_{j=1}^{t} \sum_{k=1}^{g} \bigl( c_{ik}^p\, x_{ijk} + c_{ik}^w\, v_{ijk} \bigr) + \sum_{i=1}^{m} \sum_{j=2}^{t+1} \sum_{k=1}^{g} c_{ik}^i\, y_{ijk}} & & & & & \\[16pt] \mathrlap{\text{subject to}} & & & & & \\[8pt] & -x_{ijk} + x_{(i+1)jk} - y_{ijk} + y_{i(j+1)k} & = & 0, & \hphantom{k}\mathllap{i} = 1, \dots, m-1 & (a) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & -x_{mjk} - y_{mjk} + y_{m(j+1)k} & = & -d_{jk}, & \hphantom{k}\mathllap{j} = 1, \dots, t & (b) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & x_{ijk} & \le & u_{ik}\, z_{ijk}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (c) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i1k} & = & y_{ik}^0, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{i(t+1)k} & = & y_{ik}^{t+1}, & \hphantom{k}\mathllap{i} = 1, \dots, m & (d) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & y_{ijk} & \le & u_{ik}^y, & \hphantom{k}\mathllap{i} = 1, \dots, m & (e) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 2, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & \smash{\displaystyle \sum_{k=1}^{g}}\, z_{ijk} & \le & 1, & \hphantom{k}\mathllap{i} = 1, \dots, m & (f) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 1, \dots, t & \\[8pt] & \textcolor{#d21f26}{\small\text{Switchover}}\quad\mathopen{} -v_{i1k} + z_{i1k} & \le & z_{ik}^0, & \hphantom{k}\mathllap{i} = 1, \dots, m & (g) \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & -v_{ijk} + z_{ijk} - z_{i(j-1)k} & \le & 0, & \hphantom{k}\mathllap{i} = 1, \dots, m & (g) \\[-2pt] & & & & \hphantom{k}\mathllap{j} = 2, \dots, t & \\[-2pt] & & & & \hphantom{k}\mathllap{k} = 1, \dots, g & \\[8pt] & x_{ijk},\ y_{ijk} & \ge & 0 & & \\[8pt] & v_{ijk},\ z_{ijk} & \in & \{0, 1\} & & \end{array} \tag{4}

where

v_{ijk}
= \begin{cases} 1, & \text{if stage } i \text{ is switched over to product } k \text{ in period } j \\ 0, & \text{otherwise} \end{cases}
c_{ik}^w
= switchover cost of product k at stage i ($/switchover)
z_{ik}^0
= \begin{cases} 1, & \text{if stage } i \text{ is set up for product } k \text{ before period 1} \\ 0, & \text{otherwise} \end{cases}.

The other symbols are those of Eq. 3. Both lines labeled (g) in Eq. 4 are row (g), the first for period 1 and the second for the periods after it.

Model 4 implementation: Switchover costs
# Model: switchover costs
function prodinv_switch(cᵖ, cʷ, cⁱ, d, u, z⁰, LBʸ, UBʸ)
    m, g = size(u)
    t = size(d, 1)
    model = Model(HiGHS.Optimizer)
    @variable(model, x[i=1:m, j=1:t, k=1:g] ≥ 0)
    @variable(model, LBʸ[i,j,k] ≤ y[i=1:m, j=1:t+1, k=1:g] ≤ UBʸ[i,j,k])
    @variable(model, z[i=1:m, j=1:t, k=1:g], Bin)
    @variable(model, v[i=1:m, j=1:t, k=1:g], Bin)
    @objective(model, Min,
        sum(cᵖ[i,k]*x[i,j,k] for i=1:m, j=1:t, k=1:g) +
        sum(cⁱ[i,k]*y[i,j,k] for i=1:m, j=2:t+1, k=1:g) +
        sum(cʷ[i,k]*v[i,j,k] for i=1:m, j=1:t, k=1:g))
    @constraint(model, flowbal[i=1:m-1, j=1:t, k=1:g],              # (a)
        -x[i,j,k] + x[i+1,j,k] - y[i,j,k] + y[i,j+1,k] == 0)
    @constraint(model, laststage[j=1:t, k=1:g],                     # (b)
        -x[m,j,k] - y[m,j,k] + y[m,j+1,k] == -d[j,k])
    @constraint(model, capacity[i=1:m, j=1:t, k=1:g],               # (c)
        x[i,j,k] ≤ u[i,k]*z[i,j,k])
    @constraint(model, linking[i=1:m, j=1:t],                       # (f)
        sum(z[i,j,k] for k=1:g) ≤ 1)
    @constraint(model, switchfirst[i=1:m, k=1:g],                   # (g)
        -v[i,1,k] + z[i,1,k] ≤ z⁰[i,k])
    @constraint(model, switchover[i=1:m, j=2:t, k=1:g],             # (g)
        -v[i,j,k] + z[i,j,k] - z[i,j-1,k] ≤ 0)

    set_silent(model)
    set_attribute(model, "mip_rel_gap", 0.0)
    optimize!(model)
    if termination_status(model) == JuMP.OPTIMAL
        return (TC = objective_value(model), x = snapvals(value.(x)),
                y = snapvals(value.(y)), z = Int.(snapvals(value.(z))),
                v = Int.(snapvals(value.(v))))
    end
    error(termination_status(model))
end
1
In period 1 there is no period before, so row (g) compares the setup with z⁰, the setup the stage has before the horizon starts.
prodinv_switch (generic function with 1 method)

Constraints (a) and (b) are for flow balance, (c) for production capacity, (g) to force switchovers to occur, and (f) are linking constraints that ensure that only one product is produced at each stage during each period. Constraints (a)-(e) and (g) all refer to each product separately, and only (f) refer to multiple products together for each stage and period.

The tricky part is how to model the switchover constraints. They use the z variables as before, binary, 1 if a stage is set up for a product in a period, with a third index, k, for the product. Table 5 is a profile of them for one stage and two products over seven periods; the same logic applies to every stage. The two products’ indicators cannot both be 1 in the same period, though both can be 0. What is wanted is another indicator, v, the switchover indicator, which is 1 only in the period the stage switches to a product and starts producing it. In the next period, if the stage continues to produce the same product, no switchover cost is incurred. In the table, the stage switches over to product 2 for just one period, period 4, incurring a switchover cost, and then switches back to product 1, incurring another in period 5. The trick is to write constraints that give v that behavior.

Table 5: Setup indicators z_{ijk} and switchover indicators v_{ijk} of one stage i for products k = 1, 2 over seven periods.
Period \boldsymbol{j} \boldsymbol{z_{ij1}} \boldsymbol{z_{ij2}} \boldsymbol{v_{ij1}} \boldsymbol{v_{ij2}}
1 0 0 0 0
2 1 0 1 0
3 1 0 0 0
4 0 1 0 1
5 1 0 1 0
6 1 0 0 0
7 1 0 0 0

In order to ensure that a switchover occurs only the first period that production switched to a different product, the constraint -v_j + z_j - z_{j-1} \le 0, row (g) for one stage and product, can be used. There are eight possible combinations of values that the three binary variables can take. In the table that Code block 15 prints below, the combination [ 0 \; 1 \; 0 = 1 \nleq 0 ] is not feasible (i.e., allowing a product switch without incurring a switchover), and this constraint ensures that this cannot happen. The combination [ 1 \; 1 \; 0 = 0 \leq 0 ] is feasible and will occur; the other three combinations where a switchover is indicated (v_j = 1) are feasible but would never occur because they would only add an additional unnecessary switchover cost and the objective is to minimize cost.

# Code block 15: the truth table of row (g)
# columns: vⱼ, zⱼ, zⱼ₋₁, the row's left side, and whether it is ≤ 0
T = [0 0 0; 0 0 1; 0 1 0; 0 1 1; 1 0 0; 1 0 1; 1 1 0; 1 1 1]
TT(f) = hcat(T, [f(row...) for row in eachrow(T)],
             [f(row...) .<= 0 for row in eachrow(T)])
TT((vⱼ, zⱼ, zⱼ₋₁) -> -vⱼ + zⱼ - zⱼ₋₁)
1
hcat sets the three matrices side by side: the eight combinations, the row’s left side for each, and whether it is at most zero. Written inside [ ] over two lines, the line break would start a new row instead.
8×5 Matrix{Int64}:
 0  0  0   0  1
 0  0  1  -1  1
 0  1  0   1  0
 0  1  1   0  1
 1  0  0  -1  1
 1  0  1  -2  1
 1  1  0   0  1
 1  1  1  -1  1

Table 6 lists each of the eight combinations by what it means for the stage:

Table 6: The eight combinations of row (g) for one stage and product: the paid switch, a switch with its switchover cost, is the one the row must allow; the unpaid switch, a switch with none, is the one it must rule out, its left side 1; and an extra cost, a switchover paid with no switch, is feasible but never at least cost.
\boldsymbol{v_j} \boldsymbol{z_j} \boldsymbol{z_{j-1}} \boldsymbol{-v_j + z_j - z_{j-1}} Case
0 0 0 0 no setup
0 0 1 -1 setup ends
0 1 0 1 unpaid switch
0 1 1 0 setup continues
1 0 0 -1 extra cost
1 0 1 -2 extra cost
1 1 0 0 paid switch
1 1 1 -1 extra cost

Row (g) turns out to be a formulation that gives the logic wanted: the negative of the switchover indicator, plus the setup indicator for period j, less the setup indicator for period j-1, is at most zero. A constraint like this was developed by playing around with the logic until something worked. Two combinations are the ones to check. The one that must be feasible is a stage set up for the product in a period when it was not set up for it the period before, with the switchover indicator 1: -1 + 1 - 0 = 0, which satisfies the constraint. The main one that must not be is the same switch with the switchover indicator 0, a switch with no switchover cost charged: its left side sums to 1, so it is always infeasible.

Of the six other combinations, the only ones of note are the three in which a switchover cost is paid when the stage has not switched to the product, as if an extra switchover cost were paid at random. They satisfy the constraint, its left side at most zero, so row (g) lets them through. The model never selects one, because it only minimizes cost and will not add a positive cost to a solution for no benefit. One could be forced by a constraint setting a switchover indicator to 1 in some period, a switchover made whether it is cost-effective or not, as a stage stops producing for scheduled maintenance. That is the nice thing about math programming: any particular requirement the owner might have can be added as a bespoke constraint, and the model still works, its solution feasible because it satisfies the constraints. If a stage’s storage area is to be used for some other activity in a particular week, for example, a constraint can set the inventory carried at that stage in that week to zero. Like any constraint added to a math program, a bespoke one never improves the solution, so its added cost is the penalty the owner is willing to pay for it. In normal conditions, the combinations need no constraint against them. This is the second of the two facts of Sec. 1: what cannot improve a solution need not be ruled out by constraints. If these situations could lower the cost and had to be avoided, the simple logic of row (g) would not cover them. That is the art of math programming, and there is no logical recipe for it. Four or five documents explaining how to do it have been passed from one math programmer to another for 30 years, so it is part of the black art of math programming.

In Eq. 4, row (f) is the linking constraint, and the switchover cost enters the objective through the switchover indicator. One more thing is needed. Row (g) looks at z_{i(j-1)k}, the setup in the period before, so for the first period the model has to be told what each stage is currently set up for. That makes sense: the current state of a production system is not doing nothing, since a stage may be set up to produce a particular product. The initial setup z_{ik}^0 says, for every product at every stage, whether the stage is set up for it before period 1, and the first line of row (g) uses it; for every period from j = 2 on, the second line is the constraint of the truth table. These two lines are the switchover constraints.

One of the mistakes in math programming is to make a model too complex to begin with. The minimal version comes first, even at the cost of some unrealistic assumptions: here, the model of exclusive resources with only its linking constraint, Ex. 2’s, is made to work before the switchover constraints are added. Building the whole model with everything at once has odds of working that approach zero. It is much better to make a simplifying assumption, even to treat the problem as a linear program, get that to work, and then add features incrementally, verifying at every stage that the model still works. Start small and build up, never with the whole complexity, because a math program that is not feasible typically gives no insight into why, so it is hard to know even where to look for the problem. The work is like orienteering: knowing where one came from, making an incremental improvement and making sure it works before taking the next step, each step building on the last, rather than a big jump that will never work.

Example 3: Shared plant with switchovers

The problem is the same as Ex. 2, except that there is a switchover cost associated with switching the production of one of the products on a resource to the other product. There is no switchover cost in subsequent periods if the same product continues to be produced on the same resource. The costs per switchover for each stage of each product are $400, $90, and $50, and $600, $110, and $70, respectively. The plant is currently set up to produce each stage of the first product. Determine the amount of each product that should be produced to minimize total costs over the planning horizon.

The problem is Model 4 with Ex. 2’s data, the switchover costs c_{ik}^w, and the initial setup z_{ik}^0, 1 for the first product at every stage. Every statement of this problem since 2012 gives the switchover cost of stage 3 for the second product as $60, while every published solution computes with $70; the statement above follows the solutions, and Code block 24 shows what the $60 would change, the Source check of Lecture 1.2.

The example is the same as Ex. 2 but for the switchover requirement and its cost, so everything else is almost identical. The additional information is the initial setup for each product: in period 1, the system is set up to produce product 1 and nothing for product 2. The 31 tons of initial inventory are the first two weeks’ demand for product 2, which covers at least two periods of product 2 and so allows the stages to be set up for product 1 if they are not already; here they already are.

Code block 16 enters the data, Ex. 2’s with the switchover costs, the bounds on inventory and the initial setup:

# Code block 16: Ex. 3's data, the bounds and the initial setup
# demand in each period, each product (ton)
d = [6 40 33 24 29 24 16 13 14 17 18 43 25
    17 14 17  4  7 10 12 18 13 23  8 17  3]'
t = size(d, 1)                        # number of periods
# capacity of each stage for each product (ton)
u = [60 50; 55 45; 50 35]
m = size(u, 1)                        # number of production stages
g = size(u, 2)                        # number of products
# production cost for each stage, each product ($/ton)
cᵖ = [12 20; 75 130; 35 60]
# weekly inventory carrying rate (1/wk)
@show h = 0.3/(365.25/7)
# inventory cost for each stage, each product ($/ton)
cⁱ = cumsum(cᵖ, dims=1)*h
# switchover cost for each stage for each product ($)
cʷ = [400 600; 90 110; 50 70]
# initial inventory of each stage, each product (ton)
@show y⁰ = [0 0; 0 0; 0 sum(d[[1 2], 2])]
# final inventory of each stage for each product (ton)
yᵗ⁺¹ = zeros(m, g)
# initial set up at each stage for each product
z⁰ = [1 0; 1 0; 1 0]
# convert y⁰ and yᵗ⁺¹ from 2D (m x g) to 3D (m x t x g)
LBʸ = [reshape(y⁰, m, 1, g) zeros(m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)]
UBʸ = [reshape(y⁰, m, 1, g) fill(Inf, m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)];
h = 0.3 / (365.25 / 7) = 0.005749486652977412
y⁰ = [0 0; 0 0; 0 sum(d[[1 2], 2])] = [0 0; 0 0; 0 31]

Code block 17 solves the problem with the implementation of Model 4:

# Code block 17: Ex. 3 solved with prodinv_switch
TCᵒ, xᵒ, yᵒ, zᵒ, vᵒ = prodinv_switch(cᵖ, cʷ, cⁱ, d, u, z⁰, LBʸ, UBʸ)
@show TCᵒ;
TCᵒ = 67314.92484599589

Code block 18 prints the plan for each product, its production with its demand beneath, its inventory, the stages set up for it and the switchovers to it, in a loop over the products as Code block 9 does:

# Code block 18: the plan for each product
for k in 1:g
    println()                                   # a blank line above each
    prt([xᵒ[:,:,k]; d[:,k]']; rows = [stages; "Demand"],
        cols = string.(1:t), row_title = "Week",
        title = "Product $k: production level and demand")
    println()
    prt(yᵒ[:,:,k]; rows = stages, cols = string.(1:t+1),
        row_title = "Week", title = "Product $k: inventory level")
    println()
    prt(zᵒ[:,:,k]; rows = stages, cols = string.(1:t),
        row_title = "Week", title = "Product $k: set up")
    println()
    prt(vᵒ[:,:,k]; rows = stages, cols = string.(1:t),
        row_title = "Week", title = "Product $k: switchovers")
end

Product 1: production level and demand
   Week   1   2   3   4   5   6   7   8   9  10  11  12  13
───────────────────────────────────────────────────────────
Stage 1  35  50   0  50  50  57  60   0   0   0   0   0   0
Stage 2  35  50   0  50  50  49   0   0   0   0   0  43  25
Stage 3  35  50   0  50  50   0   0   0  49   0   0  43  25
 Demand   6  40  33  24  29  24  16  13  14  17  18  43  25

Product 1: inventory level
   Week  1   2   3  4   5   6   7   8   9  10  11  12  13  14
─────────────────────────────────────────────────────────────
Stage 1  0   0   0  0   0   0   8  68  68  68  68  68  25   0
Stage 2  0   0   0  0   0   0  49  49  49   0   0   0   0   0
Stage 3  0  29  39  6  32  53  29  13   0  35  18   0   0   0

Product 1: set up
   Week  1  2  3  4  5  6  7  8  9  10  11  12  13
──────────────────────────────────────────────────
Stage 1  1  1  0  1  1  1  1  0  0   0   0   0   0
Stage 2  1  1  0  1  1  1  0  0  0   0   0   1   1
Stage 3  1  1  0  1  1  0  0  0  1   0   0   1   1

Product 1: switchovers
   Week  1  2  3  4  5  6  7  8  9  10  11  12  13
──────────────────────────────────────────────────
Stage 1  0  0  0  1  0  0  0  0  0   0   0   0   0
Stage 2  0  0  0  1  0  0  0  0  0   0   0   1   0
Stage 3  0  0  0  1  0  0  0  0  1   0   0   1   0

Product 2: production level and demand
   Week   1   2   3  4  5   6   7   8   9  10  11  12  13
─────────────────────────────────────────────────────────
Stage 1   0   0  50  0  0   0   0  31   0  23  28   0   0
Stage 2   0   0  38  0  0   0  12  31   0  23  28   0   0
Stage 3   0   0  28  0  0  10  12  31   0  23  28   0   0
 Demand  17  14  17  4  7  10  12  18  13  23   8  17   3

Product 2: inventory level
   Week   1   2  3   4   5   6   7  8   9  10  11  12  13  14
─────────────────────────────────────────────────────────────
Stage 1   0   0  0  12  12  12  12  0   0   0   0   0   0   0
Stage 2   0   0  0  10  10  10   0  0   0   0   0   0   0   0
Stage 3  31  14  0  11   7   0   0  0  13   0   0  20   3   0

Product 2: set up
   Week  1  2  3  4  5  6  7  8  9  10  11  12  13
──────────────────────────────────────────────────
Stage 1  0  0  1  0  0  0  0  1  1   1   1   0   0
Stage 2  0  0  1  0  0  0  1  1  1   1   1   0   0
Stage 3  0  0  1  0  0  1  1  1  0   1   1   0   0

Product 2: switchovers
   Week  1  2  3  4  5  6  7  8  9  10  11  12  13
──────────────────────────────────────────────────
Stage 1  0  0  1  0  0  0  0  1  0   0   0   0   0
Stage 2  0  0  1  0  0  0  1  0  0   0   0   0   0
Stage 3  0  0  1  0  0  1  0  0  0   1   0   0   0
# Code block 19: switchovers at each stage
vec(sum(vᵒ, dims = (2, 3)))
1
Summing over dimensions 2 and 3, the periods and the products, leaves one count for each stage; vec turns the 3 \times 1 \times 1 array that remains into a vector.
3-element Vector{Int64}:
 3
 4
 6

Solved, the plan’s logic is a lot more interesting than Ex. 2’s. Product 1 is produced much as before until week 6, when two of its stages produce it and the third does not, and inventory is now carried at stages 1 and 2. What drives that is that the switchover costs differ by stage. A switchover is a lot more costly at stage 1: for product 1 it costs $400 there, against only $90 at stage 2 and $50 at stage 3, and for product 2 it costs $600 there. Carrying inventory at the first and second stages lets the plan do relatively fewer of the costly switchovers, and as switchovers get cheaper, it does more of them. So the stages cycle at different frequencies, which is the part that would be hard to work out a good way of doing by hand: there are no terribly good heuristics once a problem gets this complicated.

It is useful to look at the setup indicators beside the switchover indicators, the z and the v variables, to make sure that the switchovers are represented as intended. A stage already set up for a product at the start incurs no switchover cost in period 1 for producing it. When production switches over to another product, the switchover indicator for that product is flagged in that period, so the cost is charged then; a product then produced for several periods running is charged only once, before it stops. It is important to read the indicators this way and make sure that the constraints actually work the way they are meant to.

Counted at each stage, they are 3 switchovers at stage 1, 4 at stage 2 and 6 at stage 3, the fewest where they cost the most. Read against the setup indicators, they are where they should be: stage 1, set up for product 1 from the start, is charged nothing in week 1; it switches over to product 2 in week 3, back to product 1 in week 4, which it then makes through week 7 with one switchover, and to product 2 again in week 8.

Fig. 5 sets the two plans one above the other, what each stage is set up for in each week and the tons it makes:

Show the code that draws this figure
# Code block 20: what each stage is set up for, Ex. 2 and Ex. 3
pc = [colorant"#cfe3f5", colorant"#f8dcc2"]    # product 1, product 2
function setups!(ax, x, z, title)
    hidedecorations!(ax); hidespines!(ax)
    m, t, g = size(x)
    for i in 1:m, j in 1:t                    # stage i in week j
        k = findfirst(==(1), z[i, j, :])      # product set up for
        poly!(ax, Rect(j - 1, -i, 1, 1); strokecolor = :white,
              color = isnothing(k) ? :white : pc[k], strokewidth = 2)
        s = sum(x[i, j, :])                   # tons made
        s > 0 && text!(ax, j - 0.5, -i + 0.5; text = "$(round(Int, s))",
                       align = (:center, :center), fontsize = 12,
                       color = ink)
    end
    for i in 1:m
        text!(ax, -0.15, -i + 0.5; text = "Stage $i", fontsize = 13,
              align = (:right, :center), color = ink)
    end
    for j in 1:t
        text!(ax, j - 0.5, 0.1; text = "$j", fontsize = 11,
              align = (:center, :bottom), color = ink)
    end
    text!(ax, t / 2, -m - 0.2; text = title, fontsize = 14,
          align = (:center, :top), color = ink)   # caption, below it
    xlims!(ax, -1.6, t + 0.1); ylims!(ax, -m - 0.75, 0.6)
    return ax
end
r2 = prodinv_excl(cᵖ, cⁱ, d, u, LBʸ, UBʸ)     # Ex. 2's plan, again
fig = Figure(size = (687, 330), figure_padding = 4)
setups!(Axis(fig[1, 1]; aspect = DataAspect()), r2.x, r2.z,
        "(a) Ex. 2: no switchover cost")
setups!(Axis(fig[2, 1]; aspect = DataAspect()), xᵒ, zᵒ,
        "(b) Ex. 3: with switchover costs")
Legend(fig[3, 1], [PolyElement(color = c) for c in pc],
       ["Set up for product 1", "Set up for product 2"];
       orientation = :horizontal, framevisible = false, labelsize = 12)
rowgap!(fig.layout, 2)
fig
Figure 5: What each stage is set up for in each week, and the tons it makes: (a) Ex. 2’s plan, the three stages in step every week; (b) Ex. 3’s, in which stage 1, whose switchovers cost the most, makes product 1 ahead, and the stages are set up for different products in the same week.

Ex. 2’s stages are in step every week. Ex. 3’s switchover costs change that: in weeks 6 and 7 stage 1 is still making product 1 while stage 3 has switched to product 2, and in week 9 stage 3 makes product 1 from inventory built earlier while stages 1 and 2 stay set up for product 2.

Fig. 6 draws the constraint matrix of Ex. 3’s model in the same way:

Show the code that draws this figure
# Code block 21: Ex. 3's constraint matrix by blocks
fig = Figure(size = (680, 330), figure_padding = 4)
blocks!(Axis(fig[1, 1]; aspect = DataAspect()); switch = true)
fig
Figure 6: The constraint matrix of Ex. 3’s model, drawn as Fig. 4 draws Ex. 2’s: each product’s block now has its switchover variables v, their cost c^w and its switchover rows (g) as well, and only the linking row (f) joins the products.

The switchover rows each concern one product, so they fall inside its block, and the two products’ models are still joined by the linking rows alone.

Calculate total production cost, total inventory cost and total switchover cost:

# Code block 22: the three costs, their sum, and the total
# Reshaped cᵖ broadcast for multiplication with xᵒ
@show TCᵖ = sum((reshape(cᵖ,m,1,g).*xᵒ)[:])
# First period excluded
@show TCⁱ = sum((reshape(cⁱ,m,1,g).*yᵒ[:,2:end,:])[:])
@show TCʷ = sum((reshape(cʷ,m,1,g).*vᵒ)[:])
@show TCᵖ + TCⁱ + TCʷ
@show TCᵒ;
TCᵖ = sum((reshape(cᵖ, m, 1, g) .* xᵒ)[:]) = 64564.0
TCⁱ = sum((reshape(cⁱ, m, 1, g) .* yᵒ[:, 2:end, :])[:]) = 390.9248459958931
TCʷ = sum((reshape(cʷ, m, 1, g) .* vᵒ)[:]) = 2360
TCᵖ + TCⁱ + TCʷ = 67314.92484599589
TCᵒ = 67314.92484599589

The production cost is again $64,564, since every ton still passes through all three stages; the plan trades $390.92 of inventory against $2,360 of switchovers. The three components add up to the solver’s total, the Balance check of Lecture 1.2.

What is really important is always to have an orthogonal way of verifying that a model works correctly. Suppose a model that works has its notation changed.

With the cost calculated two different ways, a run of the whole script after the change can give two results that disagree, the total more or less than its components. The production cost is computed directly from the production levels; the inventory cost from the second period on, since either the initial or the final inventory is counted, not both (Lecture 4.3); and the switchover cost from the switchover indicators. If all of that checked out before the variables were changed, the difference is a variable in the model missed in the change, such as an upper bound not yet written the new way, and it can take two or three changes to find them all. That is why the cost is always worth calculating both ways: it checks the model, and otherwise there is only the math program’s result, with no way of knowing whether it is right. The breakdown also gives the components’ relative magnitudes: the production cost is very significant, the inventory cost relatively minor, and the switchover cost somewhat significant.

Code block 23 solves Ex. 3 again with every switchover cost set to zero, and Ex. 2 again beside it:

# Code block 23: switchover costs at zero, against Ex. 2
TC0 = prodinv_switch(cᵖ, zeros(m, g), cⁱ, d, u, z⁰, LBʸ, UBʸ).TC
TC2 = prodinv_excl(cᵖ, cⁱ, d, u, LBʸ, UBʸ).TC
TC0, TC2
1
Ex. 3’s TCᵒ replaced Ex. 2’s, so Ex. 2 is solved again for the comparison; .TC takes the one field of the named tuple that is wanted.
(64765.105544147846, 64765.105544147846)

With nothing charged for a switchover, Model 4 is Model 3, and its cost is Ex. 2’s, $64,765.11, a case already known, the Landmark check of Lecture 1.2.

The first problem, Ex. 2, differs from this one only in having no switchover costs, so with those costs set to zero the model should give the same result, a way of checking that it works correctly. That is the logic of getting the first model working: without switchover costs, it is a baseline known to work, and it too should be checked. Other parts can be checked the same way. With the inventory cost set to zero, the solution should be the same as one that does not include inventory at all, whose cost is just the sum of the demand times the sum of the production costs, with nothing additional. Whatever edge case or extreme result can be thought of to verify a piece of the system gives more confidence as pieces are added to it, and for math programming that is more important than almost anything.

That sum is quick to do by hand. The plan has to make 302 tons of product 1, through stages that cost $12, $75 and $35 a ton, and the 163 tons of product 2 less the 31 held, 132 tons, through stages that cost $20, $130 and $60, so its production cost by hand is:

302\,(12 + 75 + 35) + 132\,(20 + 130 + 60) = 36{,}844 + 27{,}720 = 64{,}564

That is the production cost of both Ex. 2’s plan and this one, by an independent route, the Triangulate check of Lecture 1.2.

Code block 24 solves the problem with the $60 that the statement has always given:

# Code block 24: the statement's $60 at stage 3 for product 2
cʷ60 = [400 600; 90 110; 50 60]
r60 = prodinv_switch(cᵖ, cʷ60, cⁱ, d, u, z⁰, LBʸ, UBʸ)
@show r60.TC
@show round(TCᵒ - r60.TC, digits = 2)
@show r60.x == xᵒ;
r60.TC = 67284.92484599583
round(TCᵒ - r60.TC, digits = 2) = 30.0
r60.x == xᵒ = true

The plan is the same, and the total is $30.0 lower: stage 3 switches over to product 2 3 times, each $10 cheaper. The published total, $67,314.92, is the $70 problem’s, which is why the statement above says $70.

Total cost $67,314.92: production $64,564, inventory $390.92, and switchovers $2,360, with 3, 4 and 6 switchovers at stages 1, 2 and 3.

Example 4: Switchovers in a given plan

A plant makes two products in a three-stage process whose stages are each used by one product at a time, and plans six months of production. The capacity of each stage for each product, in tons a month, and the production cost of each product at each stage, in dollars a ton, are:

u = \begin{bmatrix} 50 & 35 \\ 60 & 45 \\ 70 & 55 \end{bmatrix} \qquad c^p = \begin{bmatrix} 100 & 200 \\ 800 & 1200 \\ 400 & 800 \end{bmatrix}

and the demand for each product in each month, in tons, is Table 7:

Table 7: Ex. 4’s demand for each product in each month, and its total over the six months (ton).
Month 1 2 3 4 5 6 Total
Product 1 20 10 15 20 15 25 105
Product 2 10 15 25 10 5 15 80

The annual inventory carrying rate is 0.3. A switchover costs $2,800, $800 and $400 at stages 1 to 3 for the first product, and $3,200, $600 and $300 for the second. The plant starts with 25 tons of the second product as finished product and every stage set up for the first product, and ends with no inventory. A plan for the six months produces, at stages 1 to 3 in each month, these tons of the first and the second product, x_{ij1} and x_{ij2}:

\begin{bmatrix} 45 & 0 & 0 & 20 & 40 & 0 \\ 20 & 25 & 0 & 20 & 40 & 0 \\ 20 & 25 & 0 & 20 & 40 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 & 20 & 35 & 0 & 0 & 0 \\ 0 & 0 & 40 & 0 & 0 & 15 \\ 0 & 0 & 40 & 0 & 0 & 15 \end{bmatrix}

The stages it sets up for them in each month, z_{ij1} and z_{ij2}, are:

\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}

Determine (a) the switchovers at each stage and their cost, (b) the plan’s total cost, (c) the plan that minimizes the total cost, with the implementation of Model 4, and (d) how the plan given and its cost compare with the model’s.

The problem is Model 4 with three stages, two products and six months, and the plan is given, so its switchovers and cost can be determined by hand; the plan that minimizes the cost is found with the model.

As in Ex. 2, both products have demand in the first period, and a stage can produce only one of them in a period, not both simultaneously, so inventory has to be available: with none at all, the problem would be infeasible, and the inventory has to equal or exceed the demand it covers. The 25 tons of initial inventory satisfy the second product’s first two months of demand, 10 tons and 15, from inventory alone. On a rolling horizon, that was probably a decision made in earlier periods, to produce the first product in these months and meet the second product’s demand from inventory made before.

Example 4(a): Switchovers by hand

Determine the switchovers at each stage, and their cost, from the setup indicators.

Fig. 7 sets out the plan’s setups at each stage, the initial setup first, with the switchovers they make and their costs:

Figure 7: Ex. 4’s setups at each stage, the initial setup first, each month numbered by the product the stage is set up for, in which red is given and blue has to be determined: the setups, given, and the switchovers they make, outlined with their costs, a month set up for a product that the month before was not, and each stage’s total at the right, determined.

A stage switches over to a product in a month in which it is set up for the product and was not the month before, its setup before month 1 the initial setup: v_{ijk} = 1 where z_{ijk} = 1 and z_{i(j-1)k} = 0, the paid switch of row (g). Every stage starts set up for product 1, so month 1 has no switchover. Reading each stage’s two rows of setup indicators across the months:

  • Stage 1 is set up for product 2 in months 2 and 3 and for product 1 from month 4 on, its last month idle but still set up for product 1: switchovers to product 2 in month 2 and to product 1 in month 4.
  • Stage 2 is set up for product 1 in months 1 and 2, product 2 in month 3, product 1 in months 4 and 5, and product 2 in month 6: switchovers in months 3, 4 and 6.
  • Stage 3 follows stage 2, month for month: switchovers in months 3, 4 and 6.

With their costs, the switchovers at each stage are:

\begin{aligned} \text{stage 1:}\quad & 3{,}200 + 2{,}800 = 6{,}000 \\ \text{stage 2:}\quad & 600 + 800 + 600 = 2{,}000 \\ \text{stage 3:}\quad & 300 + 400 + 300 = 1{,}000 \end{aligned}

That is eight switchovers for $9,000. Stage 1, whose switchovers cost the most, switches over the fewest times, as in Ex. 3.

Read stage by stage, the plan is a set of reports with a different focus. Each stage may be a different part of a factory, a different production line or a different facility, and the person running one stage does not much care about the others; instead of a separate report for each product, a separate report for each stage tells it what product it is producing and when it should switch over to produce another.

Example 4(b): Cost of the plan by hand

Determine the plan’s production, inventory and switchover costs, and its total cost, by hand.

Fig. 8 sets the plan out on each product’s network: red is given, and blue has to be determined, here only the inventory each node carries out, what came in less what went on:

Figure 8: Ex. 4’s plan on each product’s network, a month to a column, in which red is given and blue has to be determined: the production at each stage, the demand and the inventory at the start, given, and the inventory each node carries out, determined by flow balance.

The inventories follow from flow balance, as in Ex. 1(b). Stage 2 passes on everything it makes in the month it makes it, so it holds nothing. For the first product, stage 1 carries 45 - 20 = 25 tons out of month 1, and stage 3 carries 25 - 10 = 15 tons out of month 2 and 40 - 15 = 25 out of month 5. For the second product, stage 1 carries 20 tons out of month 2 and 20 + 35 - 40 = 15 out of months 3, 4 and 5, and stage 3 carries 25 - 10 = 15 out of month 1, 40 - 25 = 15 out of month 3 and 15 - 10 = 5 out of month 4. At a monthly carrying rate of 0.3/12 = 0.025, a ton held at stages 1, 2 and 3 costs $2.50, $22.50 and $32.50 a month for the first product, and $5, $35 and $55 for the second. Then, with the 105 tons of the first product and the 80 less 25 held, 55 tons, of the second that pass through all three stages, the costs are:

\begin{aligned} \text{production:}\quad & 105\,(100 + 800 + 400) \\ & \qquad + 55\,(200 + 1{,}200 + 800) = 257{,}500 \\ \text{inventory:}\quad & 2.5\,(25) + 32.5\,(15 + 25) \\ & \qquad + 5\,(20 + 15 + 15 + 15) \\ & \qquad + 55\,(15 + 15 + 5) = 3{,}612.50 \\ \text{switchover:}\quad & 9{,}000 \end{aligned}

The total is $270,112.50.

Example 4(c): Plan solved with the model

Determine the plan that minimizes the total cost, and that cost, with the implementation of Model 4.

This part is the one done with code, as in a homework problem; parts (a) and (b) are the ones done by hand, as on an exam. Code block 25 enters the data, and Code block 26 solves the problem with the implementation of Model 4:

# Code block 25: Ex. 4's data
# capacity of each stage for each product (ton)
u = [50 35; 60 45; 70 55]
d = [20 10 15 20 15 25
     10 15 25 10  5 15]'              # demand (ton)
t = size(d, 1)                        # number of periods
m = size(u, 1)                        # number of production stages
g = size(u, 2)                        # number of products
cᵖ = [100 200; 800 1200; 400 800]     # production cost ($/ton)
cⁱ = cumsum(cᵖ, dims=1)*0.3/12        # inventory cost ($/ton-month)
cʷ = [2800 3200; 800 600; 400 300]    # switchover cost ($)
y⁰ = [0 0; 0 0; 0 25]                 # initial inventory (ton)
yᵗ⁺¹ = zeros(m, g)                    # final inventory (ton)
# initial set up at each stage for each product
z⁰ = [1 0; 1 0; 1 0]
LBʸ = [reshape(y⁰, m, 1, g) zeros(m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)]
UBʸ = [reshape(y⁰, m, 1, g) fill(Inf, m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)];
# Code block 26: Ex. 4 solved with prodinv_switch
r4 = prodinv_switch(cᵖ, cʷ, cⁱ, d, u, z⁰, LBʸ, UBʸ)
@show r4.TC
@show sum(r4.v);
r4.TC = 270112.5
sum(r4.v) = 8

The model’s plan costs $270,112.50, with 8 switchovers.

Example 4(d): Plan given against the model’s

Compare the plan given and its cost, found by hand in parts (a) and (b), with the model’s plan and cost from part (c).

Code block 27 sets the plan given beside the model’s and holds the model’s cost to the one found by hand:

# Code block 27: the plan given against the model's
X = cat([45 0 0 20 40 0; 20 25 0 20 40 0; 20 25 0 20 40 0],
        [0 20 35 0 0 0; 0 0 40 0 0 15; 0 0 40 0 0 15]; dims = 3)
@assert round(r4.TC, digits = 2) == 270112.50
r4.x == X
1
@assert stops the script with an error unless the expression after it is true. A run that gets past this line has confirmed that the model’s total cost, rounded to the cent, is the $270,112.50 found by hand in part (b).
true

The model’s plan is the one given, with its 8 switchovers, and its cost is the $270,112.50 found by hand, two independent routes to one number, the Triangulate check of Lecture 1.2. Its setup indicators differ from the given ones in one place, stage 1’s idle month 6, which the model leaves set up for neither product, at no cost: the given plan comes from a model whose linking rows are written \sum_k z_{ijk} = 1, every stage set up for exactly one product every month, and with the \le 1 of Eq. 4 the plan and its cost are the same.

Production $257,500.00, inventory $3,612.50, and 8 switchovers $9,000.00, for a total of $270,112.50.

Example 5: Twenty-six-week plan and its reports

A plant can use a three-stage process to produce two products. A 26-week rolling horizon is used for planning production. The products’ forecasted demand, in tons, is Table 8:

Table 8: Ex. 5’s forecast demand for each product in each week, weeks 1 to 13 and 14 to 26 side by side, and its total over the 26 weeks (ton).
Week Product 1 Product 2 Week Product 1 Product 2
1 26 4 14 13 11
2 20 7 15 27 8
3 20 24 16 31 14
4 23 19 17 32 11
5 41 13 18 51 14
6 10 12 19 22 9
7 27 9 20 13 9
8 14 12 21 16 4
9 26 5 22 17 5
10 27 39 23 28 6
11 14 7 24 36 18
12 23 11 25 27 22
13 14 22 26 30 23
Total 628 338

The plant can produce up to 60, 55, and 50 and 50, 45, and 35 tons per week for each stage of each product, respectively; has production costs of $12, $75, and $35 and $20, $130, and $60 per ton for each stage of each product, respectively; and has costs of $400, $90, and $50 and $600, $110, and $70 per switchover for each stage of each product, respectively. The annual inventory carrying rate is 0.3. The plant is currently set up to produce each stage of the first product and the first two weeks’ demand of the second product is being held as finished product inventory. The final inventory for all stages of both products is zero. Determine (a) the amount of each product that should be produced in order to minimize total costs over the planning horizon, and report the plan (b) to the person running each stage and (c) to each product’s product manager.

The problem is Ex. 3 over 26 weeks: Model 4 with Ex. 3’s capacities, costs, switchover costs and initial setup, and the first two weeks’ demand for the second product, 11 tons, held at the start. The statement’s $70 is the $70 of Ex. 3, the one every published solution computes with.

Example 5(a): The plan

Determine the plan that minimizes total cost over the 26 weeks, and check it.

Before solving it, a count by hand says whether the weeks are enough, as for Ex. 2. Over the 26 weeks the first product needs 628 tons, and the second 338 less the 11 already held, 327 tons. At stage 3, which can make 50 tons a week of the first product or 35 of the second, the first needs at least \lceil 628/50 \rceil = 13 weeks and the second \lceil 327/35 \rceil = 10, 23 of the 26; stages 1 and 2 need 18 and 20. The plan should be feasible, with three weeks to spare at stage 3, the Prior check of Lecture 1.2.

Code block 28 enters the data, Ex. 3’s with 26 weeks of demand, the bounds on inventory and the initial setup:

# Code block 28: Ex. 5's data, the bounds and the initial setup
# demand in each period, each product (ton): weeks 1-13, then 14-26
d = hcat([26, 20, 20, 23, 41, 10, 27, 14, 26, 27, 14, 23, 14,
          13, 27, 31, 32, 51, 22, 13, 16, 17, 28, 36, 27, 30],
         [ 4,  7, 24, 19, 13, 12,  9, 12,  5, 39,  7, 11, 22,
          11,  8, 14, 11, 14,  9,  9,  4,  5,  6, 18, 22, 23])
t = size(d, 1)                        # number of periods
# capacity of each stage for each product (ton)
u = [60 50; 55 45; 50 35]
m = size(u, 1)                        # number of production stages
g = size(u, 2)                        # number of products
# production cost for each stage, each product ($/ton)
cᵖ = [12 20; 75 130; 35 60]
# weekly inventory carrying rate (1/wk)
@show h = 0.3/(365.25/7)
# inventory cost for each stage, each product ($/ton)
cⁱ = cumsum(cᵖ, dims=1)*h
# switchover cost for each stage for each product ($)
cʷ = [400 600; 90 110; 50 70]
# initial inventory of each stage, each product (ton)
@show y⁰ = [0 0; 0 0; 0 sum(d[[1 2], 2])]
# final inventory of each stage for each product (ton)
yᵗ⁺¹ = zeros(m, g)
# initial set up at each stage for each product
z⁰ = [1 0; 1 0; 1 0]
# convert y⁰ and yᵗ⁺¹ from 2D (m x g) to 3D (m x t x g)
LBʸ = [reshape(y⁰, m, 1, g) zeros(m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)]
UBʸ = [reshape(y⁰, m, 1, g) fill(Inf, m, t-1, g) reshape(yᵗ⁺¹, m, 1, g)];
h = 0.3 / (365.25 / 7) = 0.005749486652977412
y⁰ = [0 0; 0 0; 0 sum(d[[1 2], 2])] = [0 0; 0 0; 0 11]

Code block 28 is Code block 16 with 26 weeks of demand, each product’s weeks set over two lines, 1 to 13 and 14 to 26, as in Table 8. Code block 29 solves the problem with the implementation of Model 4, unchanged, and times the solve:

# Code block 29: Ex. 5 solved with prodinv_switch, and timed
secs = @elapsed r5 = prodinv_switch(cᵖ, cʷ, cⁱ, d, u, z⁰, LBʸ, UBʸ)
@show r5.TC
@show round(Int, secs);
r5.TC = 149745.64188911687
round(Int, secs) = 56

Here the solve takes about a minute, 56 seconds on this page’s render. Code block 30 finds the plan’s production, inventory and switchover costs as Code block 22 does for Ex. 3, and Code block 31 adds them and checks the total against the problem’s published solution:

# Code block 30: the production, inventory and switchover costs
# Reshaped cᵖ broadcast for multiplication with r5.x
@show TCᵖ = sum((reshape(cᵖ,m,1,g).*r5.x)[:])
# First period excluded
@show TCⁱ = sum((reshape(cⁱ,m,1,g).*r5.y[:,2:end,:])[:])
@show TCʷ = sum((reshape(cʷ,m,1,g).*r5.v)[:]);
TCᵖ = sum((reshape(cᵖ, m, 1, g) .* r5.x)[:]) = 145286.0
TCⁱ = sum((reshape(cⁱ, m, 1, g) .* r5.y[:, 2:end, :])[:]) = 1199.641889117043
TCʷ = sum((reshape(cʷ, m, 1, g) .* r5.v)[:]) = 3260
# Code block 31: their sum, and the published total
@assert round(r5.TC, digits = 2) == 149745.64
@show TCᵖ + TCⁱ + TCʷ
@show r5.TC;
1
@assert stops the script with an error unless the expression after it is true. A run that gets past this line has confirmed that the solver’s total cost, rounded to the cent, is the $149,745.64 of the problem’s published solution.
TCᵖ + TCⁱ + TCʷ = 149745.64188911705
r5.TC = 149745.64188911687

The three components add up to the solver’s total, the Balance check of Lecture 1.2. The production cost by hand is, as for Ex. 3:

\begin{aligned} 628\,(12 + 75 + 35) + 327\,(20 + 130 + 60) &= 76{,}616 + 68{,}670 \\ &= 145{,}286 \end{aligned}

That is the solver’s production cost, by an independent route, the Triangulate check of Lecture 1.2. And the total is the $149,745.64 of the problem’s published solution, a case already known, the Landmark check of Lecture 1.2, which Code block 31 asserts.

Total cost $149,745.64: production $145,286, inventory $1,199.64, and switchovers $3,260, with 4, 7 and 9 switchovers at stages 1, 2 and 3.

Modeling setups has only really been feasible for realistically large problems since the late 1990s or early 2000s, and even now a problem like this one can be sensitive. A homework problem with a setup cost may be solved in a minute, yet one number changed, from 100 to 300, leaves it feasible and has it take three hours instead of one minute. The model is highly nonlinear: things are not proportional, and one little tweak can make them blow up, so maintaining feasibility is an important issue. The problems of this course give a flavor of what is done in industry, where software products are essentially front ends to the solver, so a logistics engineer working in the field is typically not interfacing with the math program directly; there are at least one or two layers in between.

The output of a plan can be grouped by product, all of the first product’s together and then all of the second’s, or by stage, since a stage might be at a different location, and from its point of view what matters is which of the products it is producing. How a report is created depends on which decision maker the information is being sent to.

One of the important aspects of using something other than the solver itself is to take the result from the solver and, instead of the raw data, which is usually hard to interpret, report it effectively, which is part of the job of an operations research analyst. The report might be sent to spreadsheets, to web pages, or as email reports to decision makers, each with whatever information is relevant to it. The whole issue of reporting is important.

There is a variety of ways of displaying the flows of a plan, depending on the focus of interest. One is two sets of reports, a separate report for each of the two products, produced in a loop over the products: for each, its demand, how much is produced in each period, the inventory carried, and whether or not a setup is made.

The plan of part (a) is the output in the work flow of Fig. 9 in Lecture 4.3, and the report is the step that turns it into what a reader acts on. The same plan is sliced two ways for two audiences: by stage, for the person running each stage, in part (b), and by product, for each product’s product manager, in part (c). A report goes to a manager, not to the analyst who built the model, so each slice is a DataFrame made from the plan’s arrays and set as a table rather than printed, the three stages’ tables side by side and the two products’, so the 26 weeks take one table’s height.

Example 5(b): A report for each stage

Report the plan to the person running each stage: what the stage makes of each product in each week.

A stage’s report is the reading of a plan stage by stage that follows Ex. 4(a): what the stage makes of each product in each week. Code block 32 makes it a DataFrame of the plan’s production at the stage, and report sets a DataFrame as a table, without the row numbers, types and size that a DataFrame shows by default; Table 9 is the three stages’ reports:

# Code block 32: a report for the person running each stage
using DataFrames
report(df) = HTML("<div class=\"report\">" * sprint(io -> show(io,
    MIME("text/html"), df; eltypes = false, summary = false,
    show_row_number = false)) * "</div>")
for i in 1:m
    display(report(DataFrame("Week" => 1:t,
        "Product 1" => round.(Int, r5.x[i, :, 1]),
        "Product 2" => round.(Int, r5.x[i, :, 2]))))
end
1
sprint runs the function it is given on a string buffer and returns what was written to it, so sprint(io -> show(io, ...)) turns what show prints into a string; HTML hands that string to the page as HTML (HyperText Markup Language, what a web page is written in), inside a <div> whose class, report, gives the table the lecture’s table style.
2
MIME("text/html") asks show for the DataFrame’s HTML form, the table a web page displays, and the three keywords set to false leave out the row of column types, the line giving its size, such as “26×3 DataFrame”, and the row numbers.
3
display puts each stage’s table on the page. Without it nothing in the loop would appear, since only the last value of a cell is shown, and the value of a for loop is nothing.
Table 9: What each stage makes of each product in each week (ton).
(a) Stage 1
Week Product 1 Product 2
1 40 0
2 50 0
3 0 44
4 0 45
5 55 0
6 60 0
7 60 0
8 60 0
9 0 35
10 0 35
11 0 0
12 0 18
13 0 50
14 0 50
15 0 50
16 31 0
17 33 0
18 50 0
19 22 0
20 17 0
21 50 0
22 50 0
23 50 0
24 0 0
25 0 0
26 0 0
(b) Stage 2
Week Product 1 Product 2
1 40 0
2 50 0
3 0 44
4 0 45
5 50 0
6 0 0
7 44 0
8 50 0
9 0 35
10 0 35
11 41 0
12 50 0
13 0 35
14 0 35
15 0 35
16 31 0
17 33 0
18 50 0
19 22 0
20 17 0
21 50 0
22 50 0
23 50 0
24 0 18
25 0 22
26 0 23
(c) Stage 3
Week Product 1 Product 2
1 40 0
2 50 0
3 0 24
4 0 32
5 50 0
6 0 33
7 44 0
8 50 0
9 0 35
10 0 35
11 41 0
12 50 0
13 0 35
14 0 35
15 0 35
16 31 0
17 33 0
18 50 0
19 22 0
20 17 0
21 50 0
22 50 0
23 50 0
24 0 18
25 0 22
26 0 23

Stage 1, where a switchover costs the most, switches over 4 times in the 26 weeks, against 7 and 9 at stages 2 and 3, so it makes each product in long runs, building ahead into inventory held at the stage. In weeks 11, 24, 25, 26 it makes nothing, its work for those weeks already done.

Example 5(c): A report for each product

Report the plan to each product’s product manager: its demand, what is finished each week and the finished inventory on hand.

Code block 33 makes a product’s report a DataFrame of its demand, what stage 3 finishes and the finished inventory at the end of each week, and sets one for each product with Code block 32’s report; Table 10 is the two products’ reports:

# Code block 33: a report for each product's product manager
for k in 1:g
    display(report(DataFrame("Week" => 1:t, "Demand" => d[:, k],
        "Finished" => round.(Int, r5.x[m, :, k]),
        "In stock" => round.(Int, r5.y[m, 2:end, k]))))
end
Table 10: Each product’s demand, the tons finished at stage 3 and the finished inventory at the end of each week (ton).
(a) Product 1
Week Demand Finished In stock
1 26 40 14
2 20 50 44
3 20 0 24
4 23 0 1
5 41 50 10
6 10 0 0
7 27 44 17
8 14 50 53
9 26 0 27
10 27 0 0
11 14 41 27
12 23 50 54
13 14 0 40
14 13 0 27
15 27 0 0
16 31 31 0
17 32 33 1
18 51 50 0
19 22 22 0
20 13 17 4
21 16 50 38
22 17 50 71
23 28 50 93
24 36 0 57
25 27 0 30
26 30 0 0
(b) Product 2
Week Demand Finished In stock
1 4 0 7
2 7 0 0
3 24 24 0
4 19 32 13
5 13 0 0
6 12 33 21
7 9 0 12
8 12 0 0
9 5 35 30
10 39 35 26
11 7 0 19
12 11 0 8
13 22 35 21
14 11 35 45
15 8 35 72
16 14 0 58
17 11 0 47
18 14 0 33
19 9 0 24
20 9 0 15
21 4 0 11
22 5 0 6
23 6 0 0
24 18 18 0
25 22 22 0
26 23 23 0

The two reports slice the same plan for two readers: a stage’s shows what it makes and a product’s what is finished and in stock, so the 63 tons of product 2 that stage 1 holds between weeks appear on neither.

Endnotes

  1. Herbert A. Simon, “The Architecture of Complexity,” Proceedings of the American Philosophical Society 106, no. 6 (1962): 467–482, p. 478, https://www.jstor.org/stable/985254.↩︎

  2. Toyota Motor Corporation, 75 Years of Toyota, Part 1, Ch. 2, Sec. 7, Item 1, “Training at the Ford Motor Company and Observation of American Machinery Manufacturers”: Eiji Toyoda, recalling his training at Ford, put Ford’s daily output at 8,000 units to Toyota’s 40, and the difference between the two companies mainly in the scale of production.↩︎

  3. Associated Press, “U.S. auto factories cutting back on summer downtime,” May 2013: the Detroit automakers traditionally closed their factories for 14 days around July 4, for maintenance and to change the machinery over to the new models.↩︎

  4. A. Smalley, “A Brief History of Set-Up Reduction,” Art of Lean, 2006: in Toyota’s Honsha press shop, a changeover took one to four hours on each machine in the late 1950s, and the average was reduced to 15 minutes in 1962 and to 3 minutes in 1971.↩︎

  5. A setup and a switchover are, in the lot-sizing literature, a set-up and a start-up, with changeover for the switch from one product to another, its cost often depending on the pair: L. A. Wolsey, “Uncapacitated lot-sizing problems with start-up costs,” Operations Research 37(5), 1989, 741-747, whose start-up row is row (g); R. Jans and Z. Degraeve, “Modeling industrial lot sizing problems: a review,” International Journal of Production Research 46(6), 2008, 1619-1643.↩︎

  6. S. Shingo, A Revolution in Manufacturing: The SMED System, Productivity Press, 1985, as summarized by A. C. Moreira and G. C. S. Pais, “Single minute exchange of die: a case study implementation,” Journal of Technology Management & Innovation 6(1), 2011, 129-146, p. 134: the method classifies a setup’s operations as internal, those that can be done only with the machine stopped, or external, those that can be done while it runs, and then converts internal operations into external ones.↩︎