P1: JDW
Smith WL040/Bidgolio-Vol I WL040-Sample.cls June 20, 2003 13:19 Char Count= 0
OPTIMIZATIONAPPROACHES 393Table 2Cost of Producing Products A, B, and C at
Plants 1 and 2ABC
Plant 1 $40 $32 $81
Plant 2 $45 $29 $75A company with two manufacturing plants has orders
for three products that can be produced at either plant.
The costs of producing the products at each plant are
shown in Table 2.
Plant 1 can produce 200 products per day and Plant
2 180 products per day. If orders are due at the end of
the week (5 working days) for 700 units of product A, 800
units of product B, and 300 units of product C, how should
the plants be scheduled to produce the required products
at minimum cost?
The linear programming approach to this problem
would start by establishing variables and defining an ob-
jective function. Then constraints would be identified, to
which the feasible solution must adhere. In this problem
those would be expressed in the following mathematical
terms:Variables:x1,x2,x3 represent the amount of each prod-
uct (A, B, and C, respectively) that Plant 1 will produce;
x4,x5,x6 represent the amount of each product that
Plant 2 will produce
The Objective:minimize (Cost) = 40x 1 + 32 x 2 + 81 x 3 +
45 x 4 + 29 x 5 + 75 x 6
Constraints:
x 1 +x 2 +x 3 <=1000 (the capacity of Plant 1)
x 4 +x 5 +x 6 <=900 (the capacity of Plant 2)
x 1 +x 4 =700 (orders for product A)
x 2 +x 5 =800 (orders for product B)
x 3 +x 6 =300 (orders for product C)The LP solution to this problem produces an optimum
production plan with a minimized cost of $74,300, by
scheduling production as shown in Table 3.
This solution was obtained by using a linear program-
ming application based on the Simplex algorithm located
on the Internet (Hochbaum & Goldschmidt, 1998). You
can also find a linear programming solver in Microsoft’s
Excel spreadsheet program.
To describe a typical supply chain accurately to an op-
timizer, one would have to include, among other things,
the following variables to define objectives, constraints,
and relationships: resource utilization percentages, pro-Table 3Optimal Production Plan for Plants 1 and 2UNITS OF PRODUCT
ABC
Plant 1 700 200 0
Plant 2 0 600 300duction capacity, customer demand, inventory storage ca-
pacity, minimum inventory requirements, transportation
costs, throughput capacity, and product yields.Integer and Mixed Integer Programming
These programming solutions are similar to linear pro-
gramming problems, except that an integer-programming
problem is one in which the decision variables are con-
strained to integer values, and a mixed-integer problem
is one that contains both integer and noninteger decision
variables. In a problem similar to the one described ear-
lier, the linear programming model might have given a
production rate of 700.4 units of Product A in Plant 1.
Most people would round that to 700 and move on. Sup-
pose, however, that we were using the linear programming
technique to decide how many warehouses we should
build and the result was 0.4 warehouse at one location
and 0.6 warehouse at another. In this case, we would want
the results in integer values.Heuristic Solutions
Heuristic solutions for addressing SCM planning are
based on various models, rules of thumb, and the con-
cept of intelligent trial and error to improve the solu-
tion results. Beginning with a known feasible solution
to the problem, the heuristic approach follows rules to
incrementally modify the variables in the problem and
then analyze the results (feedback). If the objective im-
proves, the process is repeated. This continues until the
objective no longer gets better. This approach will produce
an optimized solution, but not necessarily the optimal so-
lution.
There are a number of heuristic methods used in sup-
ply chain planning software products based on both pro-
prietary and published approaches. One popular method
is the theory of constraints by Eli Goldratt. This method
focuses on the most constrained variables, or critical bot-
tlenecks, in addressing the planning function. The master
plan (solution) is developed around these bottlenecks.Genetic Algorithms
Genetic algorithms work well on mixed (continuous and
discrete) problems. The process looks for optimized so-
lutions from a large set of possible solutions. These are
crossbred or mutated to form new sets of solutions. This
continues from one generation to the next until a reason-
ably optimized solution is developed. Processing genetic
algorithms can be computation intensive, but they gener-
ally work better than other approaches for certain types
of optimization problems.
To use a genetic algorithm, one must define an ob-
jective function, the genetic representation, and genetic
operators (Wall, 2002). The algorithm then creates a set of
solutions and applies genetic operators such as mutation
and crossover to evolve the solutions to find an optimized
one.Tabu Search
This process for finding optimized solutions is described
as a meta-heuristic superimposed on another heuristic
and uses methods to forbid searches that take the solution