Lecture Notes on
Production and Distribution
Systems Planning

Ömer S. BenliMailto

Department Information Systems
California State University, Long Beach

2002-2.0.1

Contents

LIST OF FIGURES
PREFACE
1  INTRODUCTION TO MODELING AND OPTIMIZATION IN PRODUCTION AND INVENTORY SYSTEMS
    1.1  The Nature of Production-Inventory Processes
    1.2  Continuous vs. Periodic Review Models
    1.3  Form of Cost Functions
    1.4  Certainty and Time Dependence of Parameter Estimates
    1.5  Interaction Among Items: Single vs. Multi Item Models
    1.6  Concluding Remarks
2  BASIC MODELS OF PRODUCTION PLANNING
    2.1  Static Models
    2.2  Dynamic Models
    2.3  Multi Item Models with Demand Interaction
    2.4  Multi Item Models with Resource Interaction
    2.5  Concluding Remarks
3  PRODUCTION SCHEDULING
    3.1  Introduction
    3.2  Sequencing and Scheduling Problems
    3.3  Scheduling Algorithms and Complexity
    3.4  Disjunctive Graph Representation
    3.5  Concluding Remarks
    3.6  Problems on Scheduling and Sequencing
4  LOCATION AND DISTRIBUTION
    4.1  Facility Location Models
    4.2  Discrete Location Problems
    4.3  Vehicle Routing and Scheduling
REFERENCES

List of Figures

    1.1  Inventory-Time Plots
    1.2  A Periodic Review Model
    1.3  Cost Functions
    1.4  Product Structures
    1.5  A Serial Manufacturing Process
    1.6  A Distribution System
    3.1  Reducibility among scheduling problems
    3.2  Disjunctive graph representation of a 3-job (J3 | | oj £ 3 | Cmax).
    3.3  A (feasible) schedule for the 3-job (J3 | | oj £ 3 | Cmax): (a). Digraph and, (b). Gantt Chart representations

Management of production operations comprises planning, coordinating, and executing all activities that create goods and services with the goal of sustaining long-range profitability. Very simply stated, profitability can be expressed as

profit = revenue - cost
= price × output - cost × input
= input × (     price × productivity - cost    )
where productivity is defined as the ratio of output to input. Changing nature of business competitiveness made price and cost nonnegotiable. This implies that the key to higher profitability is lies in productivity improvement. These notes deal with planning of production and distribution systems which are essential for the productive operation of any manufacturing or service enterprise.

Chapter 1
Introduction to Modeling and Optimization in Production and Inventory Systems

1  The Nature of Production-Inventory Processes

Inventory exists as a buffer between customer demand and procurement (production or purchasing) activities. The primary function of a production planning and scheduling system is to decide how this demand is to be met. This is achieved by manipulating the timing and the size of production and purchase orders.

The purpose of procurement is to meet demand. If procurement can be done at the same instant and for the same amount for each demand occurrence, then there is no need for inventories. But this, usually, is not technologically feasible or economical (or, both) for obvious reasons. Therefore, inventories are an unavoidable reality in almost every manufacturing and retail activity.
 

PROCUREMENT Þ
INVENTORY
 Þ DEMAND

Exercise 1 When uncertainty is present, inventories are used as a protection against risk of stockout (i.e., shortage). In an environment that is perfectly predictable, inventory may be needed to take advantage of the economic features of a particular technology, or to regulate the production process to meet the changing trends in demand. Explain and give examples.

A production-inventory process can be described in terms of

Variables1 can be The fundamental relationship among these variables is inventory or material balance which simply states that procurement either goes into meeting demand or goes into inventory, or both; thus ensuring the flow conservation.

 
PROCUREMENT
   =
INVENTORY
 +
DEMAND
  


The other basic relationship is the resource constraints which state that the amount of resources used in the procurement activities cannot exceed the available amount of resources.

 
RESOURCES USED

£
RESOURCES AVAILABLE
 

In order to be more explicit about these relationships, it will be convenient to state the variables as rates.

Demand rate
d(t) = number of items demanded per unit time at time t,
Procurement rate
x(t) = number of items produced or purchased per unit time at time t,
Inventory rate
i(t) = number of items being added to (if positive) or removed from (if negative) inventory per unit time at time t.
Thus, a production-inventory process can be described as a collection of interrelated variables {x(t), d(t), i(t): t Î T } where T is the index set of the process. The index set can be in two forms:
Periodic Review Process
T = {t0, t1, ¼,tT}, a set of discrete time points (discrete process),
Continuous Review Process
T = {0 £ t £ T}, an interval of the real time axis of length T (continuous process).
T is called the planning horizon of the process. The planning horizon is called finite if T < ¥, and infinite otherwise. The values of the variables are presented in the form of tables for the discrete processes and in the form of functions for the continuous processes.

The purpose of modeling a production-inventory process is to optimize an objective function subject to the constraints that describe the physics of the process. In most (single-objective) models, the objective is to maximize profits. This is equivalent to minimizing the costs only when the revenues are constant; that is, when the total revenue is not a function of the decision variables.
max
{PROFITS}
=
max
{REVENUES - COSTS}
=
REVENUES + max
{- COSTS}
=
REVENUES - min
{COSTS}

Example 1 [Product Mix Decisions] In a predominantly make-to-stock environment, there may be a number of end products a company can manufacture and sell in a period. Contribution to profit and overhead from the sale of each end product is likely to be different. The problem is to determine the production plan (the ``product mix'') that maximizes the total contribution to profit and overhead during the planning horizon, subject to constraints imposed by resource limitations and considering customer orders already in hand and potential sales (``forecasts'').

On the other hand, in a make-to-order environment, the demand is exactly known and must be met in its entirety2. In this case the revenues from the sale of end items is constant and the objective is to minimize costs subject to satisfaction of demand and the constraints imposed by the resource limitations.

2  Continuous vs. Periodic Review Models

Let us be more specific about the inventory balance relationship and represent it as the inventory balance equation. Consider the continuous process with an index set T = {0 £ t £ T}. For any two distinct time points, tk, tl Î T, tk < tl, the inventory balance equation is stated as,
ó
õ 		tl

tk 
 [x(t) - d(t) -i(t)] dt = 0.

The following definitions will be needed:

Cumulative Production

X(t) = X(t0) + ó
õ 		t

t0 
 x(t)dt
where X(t0) is the cumulative production up to time t0 which is, without loss of generality, assumed to be equal to zero.
Cumulative Demand

D(t) = D(t0) + ó
õ 		t

t0 
 d(t)dt
where D(t0) is the cumulative demand up to time t0 which is, without loss of generality, assumed to be equal to zero.
Inventory Level

I(t) = I(t0) + ó
õ 		t

t0 
 i(t)dt
where I(t0) is the initial or beginning inventory level.

Example 2 Let the planning horizon, T, be 20 units of time in a continuous review process; and
x(t) = ì
ï
í
ï
î
10   units per unit time,
0 £ t £ 4
0   units per unit time,
4 £ t £ 20
and
d(t) = 3   units per unit time,       0 £ t £ 20.

Figure 1.1 illustrates these functions by plotting x(t), d(t), and i(t) separately, and X(t), D(T), and I(t) on the same graph.


Figure

Figure 1: Inventory-Time Plots

Note that I(t) represents the inventory level at time t. As seen in the above example, this level can be negative. When the inventory level, I(t), reaches zero from above, continuing demand cannot be met from actual inventory. Hence, shortage occurs. There are two extreme possibilities:

Backlogging
If the customer is willing to wait, possibly for some benefit, his demand is backordered, to be met at some future date from the production or purchase to take place at that time.
Lost Sales
If the customer is not willing to wait and will take his business elsewhere, then the benefit to be incurred from meeting that demand is lost.

Between these extremes, other possibilities exist as certain percentage of demand is willing to wait and the remaining will take their business elsewhere.

The fundamental assumption in continuous review models is that procurement decisions can be made at any point during the planning horizon. On the other hand, in the case of discrete processes, the index set is composed of discrete time points. The time points of interest are {t0, t1, ¼, tT}. At all other points the behavior of the process is of no interest. Hence, we want the inventory balance equations to hold only at those points, that is,
ó
õ 		t1

t0 
 [x(t) - d(t) -i(t)] dt = 0,

ó
õ 		t2

t1 
 [x(t) - d(t) -i(t)] dt = 0,

:

ó
õ 		tT

tT-1 
 [x(t) - d(t) -i(t)] dt = 0.

For ease of notation, define,
Xt º X(tt) - X(tt-1),


Dt º D(tt) - D(tt-1),
and

It º I(tt).

With these definitions and recalling that X(t0) º 0, D(t0) º 0, and I(t0) being the initial inventory level, we obtain the following inventory balance equations for the periodic review models:
Xt - Dt - It + It-1 = 0,   t = 1, 2, ¼, T.

It is customary to refer to these time points, t = 1, 2, ¼, T, as periods. If each period is considered as a node, then these equations are the node conservation equations. They simply state that, at each period, the beginning inventory plus the production that takes place during that period, must equal to the demand of that period plus the ending inventory. Schematically, a periodic review model can be shown as in Figure 1.2 .

Figure

Figure 2: A Periodic Review Model

The fundamental assumption in the periodic review models is that the procurement and inventory related costs are accounted only for the state of the process at the points of interest (i.e. at the end of each period). It should be emphasized that periodic review formulations are not necessarily used as simplified approximations of continuous review models. It may be the case that the real life itself may well be operating according to the periodic review assumptions.

3  Form of Cost Functions

In almost every production-inventory model, there are basically two types of costs: procurement related and inventory related. These costs usually expressed as a function of amount produced or purchased and amount stored in inventory, respectively. In general, these functions can take the following forms (See Figure 1.3 ):

Figure

Figure 3: Cost Functions

Let X ³ 0 be the amount produced during a given period and C(X) be the cost of production.

Linear Cost Function

C(X) = cX,   X ³ 0,
where c is the unit cost of production.

Exercise 2 Consider the following production planning model:

min
X,I ³ 0 
 T
å
t=1 
 [ct Xt + ht It]
subject to:
It-1 + Xt - It = Dt,   t = 1, 2, ¼, T.

Note that inventory and procurement variables are related to each other by the balance equations. In other words, if I tell you the values of all procurement variables, you should be able to tell me the unique values of the inventory variables. So why worry about two sets of variables, one set is enough! Show that the following formulation is equivalent to the formulation given above:

min
X ³ 0 
 T
å
t=1 
 æ
è 		ct + T
å
k=t 
 hk ö
ø 		Xt + (constant)
subject to:
t
å
k=1 
 Xk ³ t
å
k=1 
 Dk - I0,   t=1,2,¼,T.

Exercise 3 Consider an inventory system where a product is purchased for resale. In period t, the unit purchase price is ct and the unit selling price is rt. The product purchased in period t cannot be sold until period t+1. Inventory is stored in a warehouse whose capacity is L units. The decision variables in each period are how much to purchase (Xt) and how much to sell (St). The planning period is T periods long. Assume that inventory holding costs are negligible. Formulate the problem as a linear program.

Piecewise Linear Cost Function


C(X) = aj + cj Xj,   bj £ X £ bj+1,   j=0,1,¼,n,
where aj = aj-1 (cj-1 - cj) bj and a0 º 0. b1, ¼, bn are referred to as breakpoints. The function is piecewise linear concave if
c0 > c1 > ¼ > cn
and it is piecewise linear convex if
c0 < c1 < ¼ < cn

Example 3 [Diseconomies of Scale] Diseconomies of scale often arise in production planning. This happens when marginal costs are increasing for a minimization problem (or, marginal returns are decreasing for a maximization problem). The practical significance of such a separable piecewise linear convex objective function is that the problem can still be modeled as a linear program ( See, for example, pp. 14-18 in [68]).

Suppose in a particular shop, during a period, the b1 units can be produced on regular time. An additional b2 - b1 units can be produced on overtime. Clearly, c2 > c1. If during the period, more than b2 units are needed to be procured, then production must be subcontracted to outside suppliers. They are ordered according to increasing unit delivery costs, c3 < c4 < ¼ < cn, and subcontractors' capacities defining the breakpoints, b3 < b4 < ¼ < bn.

Let the decision variable be the sum of n+1 auxiliary variables, i.e.,
X = X1 + X2 + ¼+ Xn+1,
where each auxiliary variable is defined over an interval in between the breakpoints, i.e.,
0 £ Xi £ bi - bi-1,   i = 1, 2, ¼, n+1.
In solving the linear program, the algorithm will always set Xi = bi - bi-1, before taking Xi+1 ³ 0.

Exercise 4 [Economies of Scale] Show that the above reformulation does not work for the concave case, i.e. c0 > c1 > ¼ > cn.

Example 4 [General Piecewise Representation] Suppose {ci,  i=1,¼,n}'s are not necessarily increasing. Then, in addition to the auxiliary variables, we need to define n binary variables, Yi,   i = 1, 2, ¼, n,
Yi = ì
í
î
1
if Xi = bi -bi-1, i.e. at its upperbound,
0
otherwise.
And replace the bound constraints on the auxiliary variables by,
(bi -bi-1) ·Yi £ Xi £ (bi -bi-1) ·Yi-1,   i = 1, 2, ¼, n.
where Y0 º 1 and Yn º 0.

Exercise 5 [[16]] Cost of expanding a plant for the first 4,000 units is $5 million per 1,000 units of expansion, for the next 6,000 units it is $1 million per 1,000 units of expansion, and finally it is $3 million per 1,000 units of expansion for the last 5,000 units. It is not possible expand the plant by more than 15,000 units. Ignoring the other constraints, formulate the problem as a mixed integer program.

Exercise 6 [Fixed Charge Model] When a machine is set up to produce a particular item, a setup cost; and when an order is placed, an order cost is incurred. Suppose this fixed cost, k, is independent of the amount procured. If the unit cost of production (or, purchase) is c, the cost of procurement when X units are ordered or produced is given by
C(X) = ì
í
î
k + cX
if X > 0
0
if X=0
Show that C(X) is a piecewise linear concave function of X.

4  Certainty and Time Dependence of Parameter Estimates

Two major attributes of a production-inventory model are the certainty and the time dependence of its parameters' estimates. The parameters in these models can be cost, demand, or technology (e.g. input/output) related. Although, in the following, the demand process will be referred to, the discussion equally applies to the other types of uncontrollable variables.

Demand, being a prediction into the future, is estimated as a result of a forecasting effort. Forecasts result either in the expected values or in the form and parameters of a probability distribution. In the terminology of production and inventory systems,

The process, regardless how it is forecasted, is either stationary or evolutionary. A stationary process is one whose distribution remains the same as time progresses, because the (random) mechanism producing the process is not changing as time progresses. An evolutionary (sometimes called, the nonstationary) process is one which is not stationary. Thus, The concept of stationarity is very important, not only in estimating the demand process, but also in estimating the values of all other parameters of the models, such as costs, technological coefficients, etc.

5  Interaction Among Items: Single vs. Multi Item Models

Practically all production-inventory systems are multi item processes. There hardly exists a manufacturing or a retail establishment that deals with a single item. George E. Kimball stresses the importance of the concept of an item [59]:

In a shoe store, for example, the stock consists of a number of styles of shoes. Within a given style, the shoes come in various sizes. An item here is a pair of shoes of a given style in a given size. The same style in two different sizes makes two different items. Similarly, for an automobile dealer, who carries cars of different models and colors, an item would be a given model in a given color. An oil company processing different crudes must regard each of them as a distinct item.

Items may be distinguished by location alone. If a company carries stock in a number of warehouses, an object must be regarded as an item different from the same object in another warehouse, because moving an object from one location to another requires time and money. In general, two objects are the same item only when they are completely and immediately interchangeable.

It should be remembered that when modeling a production-inventory system as a single item system, the implicit assumption is the nonexistence of any interaction among items in the system. The reasoning behind in analyzing single item models is three-fold:

The interaction among items can broadly be classified into,

  1. Cost Interaction,

  2. Demand Interaction, and

  3. Resource Interaction.

Cost interaction occurs in the objective function, demand interaction appears in the inventory balance equations, and resource interaction is the sole reason of existence of the resource constraints.

5.1  Cost Interaction

If the cost function3 is completely separable, i.e.,
C(X1, X2, ¼, Xn) = C(X1) + C(X2) + ¼+ C(Xn),
then there is no cost interaction. Hence, each item i = 1, 2,¼, n can be treated separately in a single item model, provided that there is no other type of interaction among items.

One type of cost interaction occurs when there exists a discount on the total dollar amount of an order from one supplier regardless of which items are ordered. The other, more common, type of cost interaction is when there exist a ``major'' and a ``minor'' fixed charge (setup or order) cost. Suppose a major setup cost, say Kj, incurred when items in a particular group, j, is to be processes in a machining center, and minor setup costs, kji, incurred for processing each item i in group j. Similar situation may arise in an ordering environment, when items are ordered simultaneously, savings occur in freight, paperwork, and material handling.

Exercise 7 By defining appropriate binary variables, write down a cost function and the related constraints that accounts for both ``major'' and ``minor'' fixed charge costs.

5.2  Resource Interaction

In every production-inventory system in which there are more than one item, they have to share limited resources. These resources may be machine time, capital, labor, warehouse space, etc. Therefore, in every model for such systems, there must be resource constraints. If, in a particular model, a resource constraint does not appear, the implicit assumption must have been that ample resources of that type exist in the system.

Consider a periodic review system with N items that share K resources during a planning horizon of T periods. Then, if the additivity and the linearity assumptions hold, the resource constraints can be written as,
N
å
j=1 
 rkjt Xjt £ Rkt,   k=1,2,¼,K;   t=1,2,¼,T.
where,

rkjt
amount of resource k required in the unit production of item j in period t,
Xjt
amount of item j to be produced in period t,
Rkt
amount of resource k available in period t.

Exercise 8 Show that, under the linearity assumption, in a single item model resource constraints reduce to upper bounds on the procurement amount of the item.

5.3  Demand Interaction

In most production-inventory systems, items are related to each other either in the form of supply-demand relationship (in order to produce one item you need another item as an input), or in the form of input-output relationship (items are stored at different levels, or echelons, such as factory warehouse, wholesaler, retailer, customer; or, when items require different stages of manufacturing)4.

This type of interaction arises as a result of product structures. A number of product structures are shown in Figure 1.4 .

Figure

Figure 4: Product Structures

These product structures can represent a production process describing how a product is formed from raw materials, purchased items, subassemblies, and assemblies (Figure 1.5 ). Product structures can also represent the same item at different geographical locations (Figure 1.6 ).

Figure

Figure 5: A Serial Manufacturing Process

Figure

Figure 6: A Distribution System

The demand interaction is included in the models by means of modifying the inventory balance equations. In periodic review models, the inventory balance equations for multi item processes can be represented as,
Xjt - Ijt + Ij,t-1 = Djt,   j=1,2,¼,N;   t = 1, 2, ¼, T,
where the production, inventory, and demand variables are further subscripted by j referring to item j. Djt is referred to as gross demand and defined as follows,
Djt
=
-
D
 
jt 
+
^
D
 
jt 
=
-
D
 
jt 
+

å
i Î S(j) 
 aji Xi,t+d,
where,

[`D]jt
the external (independent) demand for item j in period t,
[^D]jt
the internal (dependent) demand for item j in period t,
aji
the amount of item j required to produce a unit of item i,
S(j)
the (index) set of items that require item j in their production (the successor set of item j),
d
the procurement lead time.
If S(j) = Æ, for all j, then demand interaction do not exist among items and model reduces to N single item models (provided that no other type of interaction exists among items).

Exercise 9 In the above formulation, suppose the procurement lead time, d, refers to manufacturing lead time. Discuss why, in the presence of resource constraints, and unless there exists technological restrictions to the contrary. manufacturing lead time can always be equal to one period, i.e., d = 1.

6  Concluding Remarks

Based on their analytical structures, production-inventory models can be classified according to the following characteristics:

CONTINUOUS REVIEW


PERIODIC REVIEW

STOCHASTIC

DETERMINISTIC

MULTI ITEM

SINGLE ITEM

DYNAMIC

STATIC

It can be said that periodic review, deterministic, single item, static models are the easiest for analysis and computation. Whereas, continuous review, stochastic, multi item, dynamic models are the hardest. Generally, production planning problems are formulated as periodic review, deterministic, multi item, dynamic models.

The origins of mathematical inventory theory dates back to F. W. Harris, ``How Many Parts to Make at Once'', Factory, The Magazine of Management, Vol.10, No. 2, February 1913, pp. 135-136,152 [49]. A historical and entertaining account of Harris', so called, EOQ model can be found in [37,38].

It is usually claimed that the cornerstones of modern inventory theory are the following articles:

The seminal work of Hadley and Whitin [48] and the model oriented books of Johnson and Montgomery [57] and Hax and Candea [50] are useful references. Practical and heuristic approaches are emphasized in Silver and Peterson [75]. Numerous books on production and operations management treat production-inventory systems. For current state of the art in production-inventory systems see [69] and [47].

Chapter 2
Basic Models of Production Planning

In this chapter, a number of basic lotsizing models will be presented. As mentioned earlier, periodic review models are used in formulating production planning problems. Therefore, emphasis will be on periodic review, deterministic models. But it is always useful to associate these models with their continuous review and stochastic counterparts.

1  Static Models

The model we shall investigate in this section is possibly the simplest model of a production-inventory system. The basic assumptions are the following. Items do not have any interaction, it is a single item model. Furthermore, it is deterministic, that is, all parameters are assumed to be known constants. The parameters are stationary. All of the cost, demand, resource availability, and the technology related (e.g. processing times, input-output coefficients) parameters are assumed to be time independent. Furthermore, we assume that the system will operate indefinitely. Hence, we take the planning horizon to be infinite. Procurement decisions can be made at any period and there is no upper bound imposed on the amount procured. Shortages are not allowed. There is a fixed cost of procurement and linear unit variable procurement cost. Since lost sales are not allowed and parameters are stationary, there is no need to consider the variable procurement costs in the optimization: they are sunk costs.

Under these assumptions, the production-inventory process to be modeled has a regenerative property. Suppose the process starts with zero initial inventory level and suppose we make a specific set of procurement decisions. As a result of these decisions, inventory level will fluctuate. When the inventory level reaches zero level again, a new set of procurement decisions is needed. But, due to the stationarity assumption, none of the parameter values has changed since the last decision, the same set of procurement decisions must again be made. In other words, since nothing has changed, why change the decisions. Hence, the process repeats itself. The times at which inventory level reaches zero from above are called the regeneration points. The portion of the process in between two generation points is called a cycle.

We cannot minimize the total costs over an infinite planning horizon5. Hence, the appropriate objective function is to minimize costs per unit time. Since the process repeats itself identically in every cycle, it is sufficient to compute the costs for one cycle and divide this value by the cycle length in order to obtain the costs per unit time. Our approach, then, to infinite planning horizon models is to compute the costs per unit time as a function of the procurement decision variables and minimize this function with respect to these variables.

Let the parameters of the model be,

D
Amount demanded per period (units per period),
k
Fixed charge cost of procurement ($ per procurement),
h
Unit variable inventory holding (or, carrying) cost ($ per unit per period),
and the (decision) variables6 be,
Xt
Amount to be procured in period t (units),
It
Amount of inventory carried from period t into period t+1, that is, the ending inventory in period t (units), and I0 º 0.

Exercise 1 If the initial inventory. I0 > 0, which model assumption is violated?

Our immediate problem is to determine the procurement quantity at the first period, X1. Since no shortages are allowed, it must be that X1 > D. Furthermore, it has to be a positive integer multiple of the demand per period, D, that is, X1 = nD, n = 1, 2,¼    . To see this, suppose the contrary, say X1 = 1.5 D. Since we have a procurement in period one, we incur the fixed cost k, and since the ending inventory is .5 D, we have an inventory carrying cost of .5 D h. But the beginning inventory is not sufficient to meet the demand in the second period. This necessitates another procurement at period 2, for an amount of at least .5 D, resulting an additional fixed cost of procurement, k. So, the costs incurred in policy {X1 = 1.5 D, X2 ³ .5D,¼} is (2 k + .5 D h + ¼). But we can do better by a policy {X1 = D, X2 ³ D, ...} with a cost (2k+¼) which is (.5 D h) less that the previous policy. This specific example can easily be generalized and we have the following result:

Result 1 At any period, either there is a beginning inventory or procurement can take place, but not both.

The problem reduces to finding a value for n, in other words determination of the cycle length. To this end, let us find the procurement and inventory related costs per period as a function of the cycle length, n. Total costs per period is the sum of the fixed procurement cost per period and the inventory holding cost per period. Recall that variable procurement costs can be ignored for the reasons discussed previously and the shortage costs do not exist due to the assumptions of this model.

Since we are placing one order in every n periods, the contribution of the fixed procurement cost to each period is k/n. Amount of ending inventory in each period of the cycle is,
It = (n - t) ·D,   t = 1, 2, ¼, n.
The total amount of inventory carried in n periods is,
n
å
t=1 
 (n-t) D
=
n-1
å
t=1 
 (n-t)   D
=
D   ( n-1
å
t=1 
 n - n-1
å
t=1 
 t)
=
D   [ n   (n-1) - (1/2)   n   (n-1)]
=
(1/2)   n   (n-1)   D.
Thus, the total costs per period as a function of n, the cycle length, can be stated as,
TC/P(n) = k/n + (1/2)hD(n-1).
If we were to treat n as a continuous variable, it is easy to show that the above function is strictly convex and that the minimum occurs at [^n] = Ö{(2k)/(hD)}. But, this value for cycle length will most likely be fractional, thus, the optimal cycle length is given by,
n* = argmin{TC/P(ë
^
n
 
 û), TC/P(é
^
n
 
 ù)}
And the optimal lotsize is X* = D ·n*.

Exercise 2 [Harris' EOQ Model] Consider a continuous review model with the same set of assumptions as the above model, except that demand is continuous at a constant rate d units per unit time, and that procurement is not restricted to specific time points but can take place at any time. Find the optimal lot size, explicitly defining and indicating the units of each parameter used in the model.

Exercise 3 Our company produces an item at a constant rate of 5,000 units per month. The production cost per unit is estimated to be $ 1. These units are delivered to a manufacturer who is subcontracting our company for the manufacture of these units. The delivery of these units is done by single truck which is owned and operated by our company. The truck has a total shipping capacity of 2,500 units, and it costs $ 25 to make a shipment, irrespective of the quantity shipped. Annual inventory carrying charges are estimated at .50 ($ per $ per year). Describe the inventory system graphically and determine how often the shipments be made to the manufacturer.

Exercise 4 [Capacity Constraints] Consider the model in Exercise 2.2. Suppose there exists an upper bound on the amount of procurement, that is X £ u, where u is the upper bound on the procurement level. Show that the constrained optimal lot size, Xc* = min{X*, u}, where X* is the unconstrained optimal.

Exercise 5 [Continuous Review with Shortages] Consider the model in Exercise 2.2. Suppose shortages are allowed in the form of backorders and assume that there are no lost sales. Let the shortage (backorder) cost be

p
Unit shortage (penalty) cost ($ per unit time per unit short).
Find the optimal lot size and the optimal backorder level.

Exercise 6 [Continuous Review with Lost Sales] Consider the model in Exercise 2.2. Suppose shortages are allowed, but none can be backlogged. All shortages are lost sales. Assume that a loss of [`p] ($ per unit short) is experienced. Show that it is never optimal to inventory the item and permit lost sales.

Exercise 7 Consider the model in Exercise 2.5. Suppose there exist an additional backlogging cost defined as follows:

[^p]
Shortage (penalty) cost per unit short, independent of the duration of shortage ($ per unit short).
Derive the necessary equations to solve explicitly for the optimal lot size and the optimal backorder level.

Let a º Ö{2kh/d}. Assume p = 0, [^p] > 0, discuss in detail the resulting inventory systems for the following three cases:

  1. a < [^p],

  2. a = [^p],

  3. a > [^p],

Exercise 8 [Continuous Review with Finite Procurement Rate] Consider the model in Exercise 2.5. Suppose in addition to planned shortages we allow for a finite procurement rate,

x(t) º x
Number of units procured per unit time.
Find the optimal lot size and the optimal backorder level.

Exercise 9 [Finite Planning Horizon] In infinite planning horizon models, the objective is to minimize total costs per unit time. To this end, total costs per cycle is computed and when this quantity is divided by the cycle length we obtain the total costs per unit time. Beginning points of each cycle constitutes the regeneration points of the process, in the sense that process repeats itself identically at every cycle. Optimization takes place based on the assumption that the process will continue indefinitely. But, if the planning horizon is finite, then this assumption is no longer valid. The optimal values of the decision variables will be the same only if the finite planning horizon is an exact integer multiple of the optimal cycle length computed under the infinite planning horizon assumption-which is highly unlikely to occur. Suggest a scheme that approximates the finite horizon optimal values based on the infinite horizon solutions. How can you measure the performance of this approximation scheme?

2  Dynamic Models

Production planning requires decision making in order to adapt to the evolving conditions. Inherently, therefore, production planning models must admit nonstationary parameters. In this section, single item models will be discussed. Multi item models will be treated in the following two sections. Single item models are applicable in aggregate production planning problems where there is full aggregation of items into a single item. Then there is full aggregation, the single item naturally is the production rate.

2.1  Linear Cost Models

As it was shown in Example 1.3, when the objective function is a separable piecewise linear convex function, the problem can still be formulated as a linear program, provided that all the constraints are linear and variables can be assumed to be continuous. This provides, in addition to efficient computation, extensive analysis capability by post-optimality procedures. Fortunately, it is not very unrealistic to assume piecewise linear convexity in considering most cost functions in aggregate production planning.

2.1.1  Transportation Formulation

Consider a single item, dynamic, periodic review model. In each period, t=1,2,¼,T, the (single) item can be procured from S sources. These sources can be different suppliers, or modes of production, such as regular time, overtime, and subcontracting from a number of subcontractors. It is natural that these sources have finite capacities. Let the capacity of source s=1,2,¼,S be Rst    during period   t=1,2,¼,T,    and other parameters and variables are defined by:

Dt
Amount demanded in period t=1,2,¼,T,
cst
Unit cost of procuring from source s=1,2,¼,S, in period t=1,2,¼,T,
ht
Cost of storing one unit from period t to period t+1,
Xst
Amount to be procured from source s=1,2,¼,S, in period t=1,2,¼,T,
It
Amount of inventory at the end of period t=1,2,¼,T.
Then the problem can be formulated as a linear program:


min
X, I ³ 0 
å
s,t 
 [cst Xst + ht It]
subject to:
Xst
£
Rst,
s=1,...,S;   t=1,¼,T,
It-1 +
å
s 
 Xst - It
=
Dt,
t=1,¼,T,

Exercise 10 [Backorders] In the above formulation, suppose backorders are allowed. That is, let It, t=1,2,¼,T be an unrestricted variable. Its objective function coefficient is ht if it is nonnegative and pt if it is negative, where pt is the cost of having one unit on backorder at the end of period t. By defining appropriate nonnegative variables, revise the above linear programming formulation to account for the backorders.

Exercise 11 [Transportation Problem] Consider the linear programming formulation of problem with backorders. Let

Ystu
be the amount procured from source s = 1,¼,S in period t=1,...,T in order to meet the demand in period u = 1,...,T,
gstu
be the unit cost of procuring from source s = 1,¼,S in period t=1,...,T in order to meet the demand in period u = 1,...,T.
Express gstu in terms of the original cost parameters and formulate the problem as a transportation problem of linear programming. Show the corresponding transportation network.

2.1.2  Renewable Resources

When resource constraints were discussed earlier, it was implied that resources were nonrenewable, that is, resources can be used until they are exhausted and they cannot be renewed during the planning horizon. In the context of periodic review models, though, it is necessary to view resources in two categories:

Nonrenewable Resources
Resources that cannot be renewed during the planning horizon, and
Renewable Resources
Resources that are renewed at each period.
One way to explain the difference is the following. Suppose you can at most allocate ten tons of steel for a particular production during the next four weeks. Your planning horizon consists of 4 one-week periods. Your weekly production capacity is known, say 40 hours. At the beginning of each period you have a ``renewed'' 40 hours of production capacity resource, but have only 10 tons of steel, raw material resource, that can be used during the entire planning horizon of four period. In other words, you cannot use 80 hours of production capacity in the first period and none in the second, whereas, you can use all the steel in the first period and none during the proceeding periods.

Note that the nonrenewable resources can be stored in inventory, while the renewable resources cannot be inventoried. It may be helpful to think about the goods and services analogy. Goods are like nonrenewable resources which can be stored. On the other hand, renewable resources are like services that cannot be kept in inventory. It will be convenient to treat nonrenewable resources as another item that has a demand interaction with the item that requires that resource in its production.

Examples of renewable resources are employment levels and production capacities. From one period to next, it may be possible to change these, at a cost. In the production planning terminology, these costs are referred to as hiring/firing and production capacity change costs, respectively.

Exercise 12 Discuss the intuitive justification of hiring/firing and production capacity change costs being convex (usually, piecewise linear) in most environments.

It will be convenient to incorporate these level and capacity changes in the formulation by means of balance equations. Similar to inventory balance equations, these resource balance equations simply state that in each period, the resource level is equal to the resource level during the previous period plus the increase in resource level in that period minus the decrease in resource level in that period.

Exercise 13 Show that in the (optimal) solution of a linear program that models resource level changes, it is not possible to have both an increase and a decrease in a resource level.

Example 1 [Production Capacity Change] Let

Rt
be the production capacity in period t,
Wt
be the increase in production capacity from period t-1 to period t,
Zt
be the decrease in production capacity from period t-1 to period t,
wt
be the cost to increase in production capacity by one unit from period t-1 to period t,
zt
be the cost to decrease in production capacity by one unit from period t-1 to period t.
Then the production capacity balance equation is
Rt-1 + Wt - Zt - Rt = 0,   t=1,2,¼,T,
where R0 is the given initial production capacity. The objective function needs to be appended by the appropriate cost terms.

Exercise 14 Give a complete formulation for a production planning problem with cost of production capacity change.

Exercise 15 Particularly in process industries, it is common to face with a situation where there are costs associated with production rate changes. These should not be confused with production capacity changes. For example, if a process is being operated at a rate of Xt in period t, unless the Xt = Xt+1, then we incur production rate changeover costs. By defining appropriate variables, formulate this problem.

2.2  Convex Cost Models

For all practical purposes, convex cost functions can be approximated, for any desired level of accuracy, by piecewise linear convex functions. The resulting models can be solved as linear programs. Original work on convex cost models was done by Veinott[78]; details can be found in [80,50,57]. Importance of detailed study of convex cost models lies in their contribution to the planning horizon analysis7. Very simply stated, the planning horizon analysis deals with the issue of determining the shortest horizon to consider such that the current decision remains optimal. These results constitute the core of rolling horizon concept. In order to appreciate the importance of convexity, consider the following exercise.

Exercise 16 Suppose in Exercise 2.11, backlogging is not allowed. Develop a ``one-pass procedure'' for the optimal solution.

Exercise 17 [Where-or-When Production Problem, [80]] This problem has various interpretations. Suppose a company has N plants and must manufacture a total of D units in a given period. Let Xi be the amount produced in plant i=1,¼,N. Furthermore, assume that the cost of production in plant i is given by
Ci(Xi) = (1/ci) ·Xi2,   i=1,¼,N,
where ci > 0 is estimated from historical accounting information. Then the problem is

min
X ³ 0 
 N
å
i=1 
 Ci(Xi)
subject to:
N
å
i=1 
 Xi = D.

Another interpretation is in terms of choosing optimal production levels at a single plant over a number of periods with the requirement that the total production over the planning period is D. Note that only production costs are considered and the inventory holding costs are assumed to be negligible.

  1. Use a dynamic programming formulation to show that given the values Xi,   i = 1, ¼, n-1, the optimal value for Xn = cn (D - åi=1n-1 Xi)/(åi=nN ci).

  2. Find the same optimality condition by applying the Karush-Kuhn-Tucker Optimality Conditions.

2.3  Concave Cost Models

The problem is a single item, periodic review model with nonstationary parameters but no bounds on variables other than the nonnegativity restrictions. Assume that the procurement and inventory costs are concave. The arguments will equally apply when backlogging is permitted, but for ease of presentation let us assume that the shortages are not allowed. Then the model can be formulated as the following mathematical program:
ì
í
î
min
X,I ³ 0 
 é
ë
å
t 
 Ct(Xt) + Ht(It) ù
û 		|It-1 + Xt - It = Dt,   t=1,¼,T, ü
ý
þ
where, the Ct(·) and Ht(·) are concave functions of procurement and inventory amounts in period t, respectively.

Consider the following results,

Result 2 Minimum of a concave function subject to linear constraints will occur at one of the extreme points of the feasible region defined by the linear constraints.

Result 3 Every basic feasible solution to a set of linear constraints corresponds to an extreme point of the feasible region defined by those constraints.

Therefore, it is sufficient to search for the optimal solution only among the basic feasible solutions to the system of equations
{It-1 + Xt - It = Dt,   t=1,¼,T}.
Any basic feasible solution to this set of linear equations can have at most T positive variables from the set
{Xt, It,   t=1,¼,T}.
Based on these, the following result follows:

Result 4 In a basic feasible solution to the above problem, there is either inventory carried into a period or procurement takes place at that period, but not both. That is,
It-1 ·Xt = 0,  t=1.¼,T.

For example, in a four period problem, let X1, X2, I1 > 0. Since there can be at most four positive variables in a basic feasible solution, there is no way of satisfying the demands of periods 3 and 4, D3, D4, by choosing only one more positive variable out of I2, I3, X4. In other words, if a period ``uses'' two positive variables (i.e. one more than it deserves), then there must be a period into which there is no inventory being carried and no procurement taking place-thus making it impossible to meet its demand.

An immediate consequence of this result is that the procurement occurs only when inventory reaches zero (as is the case in its continuous review counterpart). These points are referred to as regeneration points and periods in between two regeneration points constitute a cycle. This is similar to the static case, except that, since parameters are nonstationary, the cycle lengths are not necessarily the same.

An efficient dynamic programming formulation of this problem is based on the following result:

Result 5 If there is a procurement to take place in any period, t=1,¼,T, it is equal to {Dt} or {Dt + Dt+1} or ¼ or {Dt +Dt+1 + ¼+ DT}.

Wagner-Whitin's[81] original dynamic programming formulation assumes fixed charge procurement and linear inventory holding costs with no backlogging, though numerous extensions and generalizations of the approach has been made since then (see [47] for an overview). The significance of Wagner-Whitin's work lies as much in developing a planning horizon theorem as providing an efficient solution to the above problem8.

The functional equation for periods, t=1,¼,T, can be defined as follows:

ft(It-1) = the minimum cost of satisfying demand from period t to T,
given the initial inventory, It-1.
= minXt { Ct(Xt) + Ht(It) + ft+1(It)}
= minXt { Ct(Xt) + Ht(It-1 +Xt - Dt) + ft+1(It-1 +Xt - Dt)}

where I0 and IT are given and fT+1 º 0.

Exercise 18 Suppose there are capacity constraints on procurement. Is the above dynamic programming formulation still applicable? Why or why not?

Exercise 19 Suppose you are faced with the demands D = {5, 7,11, 3 } for the next four periods. You have to choose two alternative ways of meeting this demand: in-house production or outside purchase (once you decide on an alternative, all four periods' demand should be met that way). Shortages are not allowed and holding cost is $1.00 per unit per period for both alternatives.

In-house production data:

Period, Setup Cost, Production
i $ki Cost, $ci
per setup per unit
1 5 1
2 7 1
3 9 2
4 7 2

Outside Purchase data (The order cost is zero):

Range, Unit Cost
in number of $ci
units ordered in period
1234
1 to 3 1 2 2 3
4 to 11 1 4 5 4

Which alternative would you choose and why?

These dynamic lotsizing models discussed in this section often occur as subproblems of Material Requirements Planning (MRP) Systems. See [7,19] for an overview of these issues.

3  Multi Item Models with Demand Interaction

The concepts of an item and product structures were introduced in Section 1.5.3. The models to be discussed in this section arise due to these product structures. In the MRP literature, they are commonly known as infinite loading models. No resource constraints are included (unless one treats a nonrenewable resource as an another item) in these models. Since these models primarily model production environments with input/output relationship among items, other than the end items, it does not make sense to permit shortages. For example, an assembly is not physically complete without an item it must contain. Shortage of a single unit may shut down the entire production line.

Basically, these models minimize the sum of production and inventory holding costs subject to inventory balance equations where demands per period reflect both internal and external demands.

The general form of the model is given below:



min
X,I ³ 0 
 é
ë
å
j,t 
 Cjt(Xjt) + Hjt(Ijt) ù
û
subject to:
Xjt - Ijt + Ij,t-1 -
å
i Î S(j) 
 ajiXi,t+dj =
-
D
 
jt 
 ,   j=1,2,¼,N;   t = 1, 2,¼, T.

The definitions of variables are repeated for convenience:

Xjt
amount of item j=1,¼, n to be produced in period t=1,¼,T,
Ijt
amount of inventory of item j=1,¼,n at the end of period t=1,¼,T,
[`D]jt
the external (independent) demand for item j in period t,
aji
the amount of item j required to produce a unit of item i,
S(j)
the (index) set of items that require item j in their production (the successor set of item j),
dj
the production lead time of item j=1,¼,n.

Even when the cost functions are assumed to be linear, dimension of such models make their routine application either infeasible or very expensive with conventional LP software [53]. For example, for a ten-period problem, with 100 products, each having 100 predecessor parts, the resulting linear program will have on the order of 100,000 constraints and 200,000 variables. It is computationally prohibitive to consider the fixed charge production costs, as they are required in MRP environments. For problems of practical size, use of heuristic multilevel lotsizing procedures are unavoidable. The reader is referred to [7] for an overview of heuristics.

Exercise 20 Because of the production lead times, certain variables defined above may be eliminated from the model. Explicitly define those variables to be set to zero, for specific product structures.

Exercise 21 [[19]] In systems like infinite-loading MRP, the production lead times are used as a means of handling the finite production capacities. But lead times and lotsizes are intimately related. Lead times are a consequence a particular lotsizing decision and cannot be used a priori to generate accurate lotsizes. Discuss.

Exercise 22 Show how a nonrenewable resources can be treated as an item in a demand interaction model. Assume there are no other resource constraints. Give a detailed formulation for a small example.

4  Multi Item Models with Resource Interaction

A single period case of a multi item model with resource constraints was discussed in Example 1.1. When there are multi periods, clearly, one must incorporate the inventory balance equations. If we assume that there does not exist any demand interaction, i.e. S(j) = Æ, "j, these would be similar in structure to single item balance equations where variables are appended with subscripts identifying the item they refer to.

The general form of the model is given below:



min
X,I ³ 0 
 é
ë
å
j,t 
 Cjt(Xjt) +Hjt(Ijt) ù
û
subject to the inventory balance equations:
Xjt - Ijt + Ij,t-1 = Djt,   j=1,2,¼,N;   t = 1, 2, ¼, T,
and, the resource constraints,
N
å
j=1 
 rkjt Xjt £ Rkt,   k=1,2,¼,K;   t=1,2,¼,T.
where, the definitions are repeated for convenience,

Xjt
amount of item j=1,¼, n to be produced in period t=1,¼,T,
Ijt
amount of inventory of item j=1,¼,n at the end of period t=1,¼,T,
Djt
the demand for item j=1,¼,n in period t=1,¼,T,
rkjt
amount of resource k required in the unit production of item j in period t,
Rkt
amount of resource k=1,2,¼,K available in period t=1,2,¼,T.

Exercise 23 [Multi Period Product Mix Problem] Formulate a profit maximization version of the above problem. Define the necessary parameters.

5  Concluding Remarks

The key elements of a production system are customers, material, and capacity. Such a system requires, in the least, the following objectives:

An effective production planning and control system aims to resolve these conflicting (``incompatible'') objectives. In order to achieve this, one can use multi criteria optimization. For example, simultaneously taking into account the following objective functions: The dimensions and complexities of most production planning problems make their analysis by means of multi criteria optimization either impossible or computationally prohibitive. Practical considerations make it necessary to utilize satisficing9 approach. Ackoff [1] describes the satisficing procedure as follows:
The most important objective (judged in some qualitative way) is selected as the basis for the measure of performance of a course of action. Minimal levels of acceptable performance (subjectively determined) are imposed as restrictions on an acceptable solution. Such a level may, for example, be the level of performance attained in the past.

Consider a case in which a decision maker wants to reduce costs and improve service. [...] The decision maker may be willing to settle for this criterion of performance: to minimize costs subject to the condition that the quality of service does not deteriorate below the current level. If service is improved, fine; this is a bonus. But it will not be permitted to get worse.

Such a procedure combines the principles of optimization and satisficing; optimization with respect to costs, satisficing with respect to service. If alternative optima relative to costs are found, that action which does best relative to service is selected.

Exercise 24 According to [52], the eminent management scientist and Nobel Laureate in Economics, Herbert Simon, has introduced the concept that the goal of an operations research study should be to ``satisfice'' rather than optimize. Discuss.

This approach results in the classical formulation of production planning problems: minimization of production and inventory related costs subject to satisfying the demand without violating the resource constraints. Considering a planning horizon of, probably, years and each eight-hour shift as a period, with thousands, if not ten thousands of interacting items, such a formulation turns out to be a large scale mathematical program. The problem with this monolithic approach, in addition to prohibitive computational burden, is massive detailed data requirements.

In order to resolve this dilemma, hierarchical approaches based on aggregation are suggested (see, for example, [64]). Basically, production planning decision hierarchy is designed to be composed of echelons such as

Each higher level in the hierarchy imposes constraints on the lower level and each lower level sends feedback information to the higher level. One major problem is how to treat the interactions among these hierarchical levels. On one extreme, this can be as loose as in Manufacturing Resources Planning (MRPII) or, on the other extreme, as mathematically structured as in the price- or resource-directive decomposition approaches of mathematical programming. Another major problem is how to treat the aggregation and disaggregation issues. Levels of aggregation is required for both items and production resources. Although there is considerable amount of ongoing research in this area, the theory is far from complete [77].

Exercise 25 Consider a multi item, periodic review model with resource and demand interaction. Suppose periods are of different lengths. For example, the planning horizon consists of ten periods of length one-day, followed by five periods of length one-week, and so on. Suggest a way of handling inventory balance equations.

Exercise 26 [[57]]

The company you work for produces a number of products. You are responsible for the planning the production of only two of these products: let us say Product A and Product B. Each of these two products require two operations. For both products, the first operation is done in Department 1 and the second operation in Department 2. Your are pretty sure that the production rates are:

Production Rate in Units per Hour
Product Operation 1 Operation 2
A 2 4
B 1 5

It is a terribly competitive business you are in: no matter how much you force the Sales Department, the best you can get out of them is their guesstimate of the demand for the next three months. They say, to the best of their abilities, the demand for A will 100, 200, and 150 units, and for B, 180, 220, and 100 units. But they threaten you with your job if you allow for shortages!

Then you fight with Production Department for capacity allotments. After hours of negotiations all you can get from the production people is the following:

Capacity in Machine Hours
Department 1Department 2
Month Regular Time Overtime Regular Time Overtime
1 250 50 100 20
2 250 50 50 20
3 200 50 50 20
But you have a feeling that, with a little help from your boss, you can make small changes in these allotments...

Your company operates in a free zone , the labor rates are highly volatile, the same can be said about inventory carrying charges. But the cost people did their best and come out with the following cost data. You are left with the problem of distributing the unit cost figure over operations one and two.

Unit Cost($)Unit Inventory Cost
Product Regular Time Overtime per Period ($)
A 30 31 2
B 28 32 3

Last time you checked the finished goods inventory, you noticed that there were 10 units of Product A and 20 units of Product B.

You are up for promotion and you really want to show off your expertise in modeling and solving production planning problems, making extensive use of the powers of post optimality analysis of linear programming. Your company has all the necessary software and support personnel and 24-hour open computing facilities. Although you have a very important engagement for the coming weekend, you have to submit the report in a week!

Chapter 3
Production Scheduling

1  Introduction

The domain of scheduling is material flow systems. ``Material'' in these systems may be

Our primary concern is production scheduling and, therefore, manufacturing terminology and examples will be used. It is common to define scheduling as ``the art of assigning production resources to production activities in order to insure the termination of activities in a reasonable amount of time''. The aim of scheduling theory is to devise solution procedures for allocation over time of the production resources in the form machines to production activities referred to as jobs, subject to constraints on machines and jobs. The major constraints are limits on the capacity of resources and technological restrictions on the order in which jobs can be performed. Usually, these constraints are too complicated to be stated explicitly in lot sizing models. Therefore, in analytical models of production planning surrogate or aggregate constraints are used, which are simplified versions of true resource constraints. The exact capabilities of production resources can only be determined as the result of production scheduling process.

Typically, the number of feasible allocations or schedules will be finite, but very large. If all the relevant information on jobs, machines, and optimality criterion are known in advance, the scheduling problem becomes a combinatorial optimization problem. Most of these problems are notoriously difficult problems.

Sequencing simply is the ordering of a collection of jobs to be performed, whereas scheduling is concerned with the assignment of times for each job that tells when it is to be performed. If the criterion of a scheduling problem is a regular measure of performance, that is, when the criterion cannot be improved by inserting idle times on the machines, and thus, jobs can be started on machines as soon as possible, then a sequence determines a schedule, and vice versa.

In deterministic scheduling, all job characteristics (number of jobs, routing of jobs, etc.) and all shop characteristics (number of machines, their availabilities, etc.) are fixed and known in advance. In stochastic scheduling those characteristics vary randomly. Based on the assumption on the availability of information on the future requirements, the scheduling environment can be static or dynamic. In a static environment, the scheduling problem is defined with respect to a finite set of fully specified requirements; no additional requirements will be added to this set, nor will any of the specifications be altered. In dynamic environment, the scheduling problem is defined not only for the known requirements, but also with respect to the anticipations for additional requirements and specifications generated over the planning horizon.

A good schedule is the one which utilizes the resources efficiently, responds to demands rapidly, and conforms to prescribed due dates closely. Ideally, as any production plan, the schedules should be evaluated based on their costs, such as,

But, in a detailed production scheduling environment, it is difficult, if not impossible, to assign such costs to each schedule alternative. Hence, it is customary to evaluate schedules based of their performances on job and shop related variables. Examples of schedule performance measures are

2  Sequencing and Scheduling Problems

Deterministic, static scheduling problems may arise whenever n jobs Jj     (j=1,...,n) have to be processed on s stages Sl     (l = 1,... ,s) each of which may have ml parallel machines Mkl     (k=1,... ,ml). We assume that

Given such an instance, a scheduling problem can be modeled as determining the schedule S that minimizes fmax or åfj such that in S

  1. fmax = max  1 £ j £ n { fj(Cj) } and åfj = åfj(Cj),

  2. prescribed { O1j,... ,Ooj,j } for each job Jj is preserved,

  3. each of msij parallel machines in stage sij processes one operation Oij at a time,

  4. each operation Oij requiring the stage sij are processed on one and only one of msij parallel machines at a time,

  5. possibly some other constraints on each job and/or shop are satisfied.

The large variety of sequencing and scheduling problems makes it necessary to introduce a systematic notation that classifies these problems. The small differences in the problem assumptions makes significant difference in the solvability of these problems. Therefore, a detailed specification of each problem essential. The scheme that is presented below is based on [61], which was first suggested in [45] and also appears in [13,12]. The version given here is adapted from [4]. In this classification, each scheduling problem is represented by a 4-tuple a | b | g | d:

2.1  Examples

1|P||Cmax: refers to a class of single stage scheduling problems in which n jobs are scheduled on m identical parallel machines so as to minimize makespan.

1|Pc||Cmax: refers to a class of 1|P||Cmax problems in which the number of machines is a constant c.

1|Q||Cmax: refers to a class of single stage scheduling problems in which n jobs are scheduled on m uniform parallel machines so as to minimize makespan.

1|P|rj,[`(dj)]|Cmax: refers to a class of single stage scheduling problems in which n jobs are to be scheduled on m identical parallel machines so as to minimize makespan. In a feasible schedule no job can start before its ready time rj and each job must be completed by its deadline [`(dj)].

J|||Cmax: refers to a class of job shop scheduling problems in which the aim is to minimize makespan. It is assumed that in the job shop there is a single machine at each stage.

3  Scheduling Algorithms and Complexity

Given a scheduling problem, we need an algorithm to solve it. How do we know that the algorithm is a ``good'' one? A useful measure of performance would be ``the rate of growth of the time or space required to solve larger and larger instances of a problem'' [2]. Therefore, we need a number to measure the size of a problem. One convenient measure is the size of the input data. For example, the size of a scheduling problem might be the number of jobs to sequence, n. More precisely, it is the number of digits in the data of the problem instance when it is encoded in binary form. The time complexity or the running time of the algorithm is the time needed by the algorithm (e.g., number of elementary operations such as additions and comparisons) expressed as a function of the problem size. The space complexity is similarly defined.

If a scheduling algorithm solves, in the worst case, a problem with an input size of n in time cn2 for some constant c that is independent of the size and the data of the problem instance, then we say the time complexity of (or, the computational effort required by) the algorithm is O(n2), read ``order n2''. In general, an algorithm may have the complexity of O(p(n)). If p(·) is a fixed polynomial function in the size of the problem, then that algorithm is said to be polynomially bounded or, in the words of Edmonds [34], it is a ``good'' algorithm and the problem is ``well solved''.

In order to appreciate the importance of polynomial boundedness, consider the following example adapted from [2]. Suppose we have a single stage scheduling problem with two identical parallel machines with the objective of minimizing schedule length, i.e., 1|P2||Cmax. Consider two algorithms: A1 and A2. The first one, A1, lists the n processing times in the nonincreasing order and assigns the jobs according to this list to the machine with the least amount of work, breaking the ties arbitrarily. It may not find the optimal solution, but it is a good heuristic algorithm with a time complexity of O(n logn). A2, on the other hand, explicitly enumerates all possible solutions, with a time complexity of O(2n). Assume that one unit of time on our computer is equal to one millisecond. The limits on the problem size as determined by the growth rate are shown below:

Time Maximum Problem Size
Algorithm Complexity 1 sec 1 min 1 hour
A1 n logn 140 4893 2.0 ×105
A2 2n 9 15 21

Suppose that we replace our computer with another one, which is ten times faster than the current one. The increase in the size of the problem that we can solve due to tenfold speed-up is shown below:

Maximum Maximum
Time Problem SizeProblem Size
Algorithm Complexity Before Speed-up After Speed-up
A1 n logn s1 » 10 s1
A2 2n s2 s2 + 3.3

Note that with algorithm A2, the size of the problem that can be solved after tenfold speed-up only increases by three, whereas with algorithm A1, the size increases almost tenfold. Instead of an increase in speed, consider the effect of using more efficient algorithm. Suppose you have only one minute to solve the problem. Using the faster algorithm, you can solve a problem more than 325 times larger than the one you can solve with the slower algorithm.

At present, roughly 10% of the scheduling problems are ``well solved''. It is also known that for 80% of the problems it is highly unlikely that polynomially bounded algorithms can be developed. The remaining 10% are open. This means that if we require optimal solutions, for roughly 90% of the problem types in scheduling, we have to resort to enumerative methods, such as branch & bound or dynamic programming, which may require exponential time in the worst case. If, in practice, this turns out to be computationally prohibitive, then one has to use a heuristic algorithm.

In order to be more concrete about these solvability issues, we need some definitions from the theory of NP-completeness. This theory deals with so-called recognition problems. These problems are also referred to as feasibility or decision problems. Given an optimization problem, corresponding feasibility problems, requiring a yes/no answer, can be constructed in the following manner. Say, we have a minimization problem, minx Î Xf(x), then the feasibility problem is asking for the existence of a feasible x Î X such that f(x) £ z for some threshold value z.

Suppose we have an ``oracle'' that returns a ``yes'' or a ``no'' answer to our feasibility problem, then we can solve any ``reasonable'' minimization problem by consulting the oracle polynomial number of times. It is reasonable to expect that we have a finite lower bound, a, and a finite upper bound, b, for the optimum value of the objective function. That is, the oracle answers with a ``no'' to the feasibility problem with z=a and ``yes'' to the feasibility problem with z=b. Let u=b-a be the initial interval of uncertainty. It is also reasonable to be content with an integer interval of uncertainty and the nearest integer for the optimal objective function value. Apply a bisection search to the interval of uncertainty, by asking the oracle the feasibility of z=a+u/2. Depending on the yes/no answer, the new interval of uncertainty is either [a, a+u/2] or [a+u/2, b]. Thus, the interval of uncertainty is reduced by a factor of 2. After performing l bisections, the interval of uncertainty is reduced by a factor of 2l. If we want the final interval of uncertainty to be of length 1, then we have to perform l bisections:
 u
2l
 = 1,
or
l = logu,
Thus, we can obtain the optimal solution after logu number of calls to the oracle.

Therefore, for the purposes of computational complexity, it is sufficient to be concerned with the feasibility problems. Consider the following definitions.

Class P
A feasibility problem belongs to class P if, for any instance of the problem, a ``yes'' or a ``no'' answer can be determined by a polynomial algorithm.
Class NP
A feasibility problem belongs to class NP, if the feasibility of a given structure can be checked in polynomial time.

For example, the feasibility version of the problem 1|P2||Cmax is a member of NP. If you give me a structure, that is list of jobs assigned to each machine, and a z, I can, in polynomial time, ``check'' if maximum of the sums of processing times in each machine is less than or equal to z. But, suppose the problem is a variant of the above problem: all possible assignments of jobs to two identical machines such that the makespan is less than or equal to z. Then, if you give me, say, two sets of assignments, and claim that they constitute all the assignments whose makespan is less than or equal to z, I can check if those two are feasible, but cannot be sure if they are the all possible assignments, without computing all possible assignments myself, and I don't have a way of doing the latter in polynomial time.

It follows from the definitions that P Í NP.

A problem P1 is reducible to another problem P2 if for any instance of P1, an instance of P2 can be constructed in polynomial time such that solving the instance of P2 will solve the instance of P1 as well. The reducibility of P1 to P2 implies that P1 can be considered as a special case of P2.

A summary of reducibility among scheduling problems are illustrated in Figure 3.1 .


Picture Omitted
Figure 1: Reducibility among scheduling problems

In this figure each graph Gi represents a different characteristic of a scheduling problem and a 5-tuple (v1,¼,v5), where vi is a vertex of graph Gi, represents a particular scheduling problem. In Gi, the directed path from P¢ to P shows the reducibility in terms of the characteristic vi. Note that graph G3 indicates that there is no reducibility relation between pmtn and °.

Now the final two definitions in our discussion of computational complexity,

NP-hard
A problem P is called NP-hard if every problem, P¢, in class NP can be reduced to P.
NP-complete
A problem P is called NP-complete if it is NP- hard and belongs to class NP.

All of the above implies the following: if a polynomial time algorithm can be found for any NP-complete problem, then every problem in class NP can be solved in polynomial time, and thus proving P = NP. But this is very unlikely, NP contains some very difficult combinatorial problems, such as, integer programming and many other problems in graphs theory, network design, sets and partitions, automata and languages, etc. which received considerable amount of research without finding any polynomial algorithm for these problems[43]. We know P Í NP, the major unresolved problem is whether P Ì NP or P = NP.

In order to show the NP-completeness of a problem in NP, one has to reduce it to a known NP-complete problem (for an illustration as to how this is done see, e.g. [39]). The practical significance of showing the feasibility version of an optimization problem to be NP-complete is that one should not pursue the search for a good optimizing algorithm for such a problem and be content with finding a good approximating (i.e. heuristic) algorithm.

4  Disjunctive Graph Representation

Gantt Charts are very useful visual tools for representing schedules. Another graphical representation of scheduling problems is by means of disjunctive graphs due to [72]. It is widely used in representing single machine multi stage makespan minimization scheduling problems. In the following, this scheme is presented in the context of the basic job shop scheduling problem, (Js |   |   | Cmax). Clearly, in this configuration sij can equivalently be referred as the machine required by the operation Oij. If we let

then the scheduling problem can be restated as
min
t*
s.t.
tl-ti ³ pi
"    (i,l) Î A;
ti ³ 0
"    i Î N;
tl-ti ³ pi Úti-tl ³ pl
"    (i,l) Î Ek, k Î M.
Any feasible solution of this problem is called a schedule. In the above formulation the first inequality preserves the precedence constraints and the last inequality (disjunctive constraint) guarantees that each machine processes one job and each job is processed by a single machine at a time. This formulation suggests that the job shop scheduling problem can be represented via a disjunctive graph G = (N,A,E) with node set N, ordinary (conjunctive) arc set A and, disjunctive arc set E = È  k Î M Ek. Figure 1

Figure

Figure 2: Disjunctive graph representation of a 3-job (J3 |   | oj £ 3 | Cmax).

illustrates disjunctive graph representation of a 3-job (J3 |   | oj £ 3 | Cmax). The nodes of G correspond to operations, the directed arcs in A correspond to precedence relations among operations of a job and the disjunctive arcs in Ek correspond to precedence relations among operations performed on machine k. The number on the node i is the processing time of the operation i. Let

With the above notation, (Js |   |   | Cmax) can be restated as determining an acyclic S Ì E that minimizes the length of a longest path in the digraph DS.

5  Concluding Remarks

The seminal work on the theory of machine scheduling is [26]. The classic texts are [6] and [42], both of them seem to be currently out of print. A recent book by Baker, [8], does provide a very readable introduction to the basic results in the area. Other book containing most of recent results and having extensive discussions on computational complexity and analysis of heuristics is [12]. [50] has an introductory chapter on scheduling. Heuristic methods are thoroughly covered in [66]. A recent survey of the area, together with classification, complexity results and open problems can be found in [61]. Complexity results of static scheduling problems can also be found in [51].

The advances in manufacturing automation and the changing nature of business competitiveness created demand for viable production scheduling systems. In order to achieve this one needs to integrate production planning (e.g. lot sizing) with production scheduling and sequencing in structurally sound manner with acceptable computational burden.

Origins of lot sizing dates back to [49] and that of scheduling to the early work of H. L. Gantt who developed the Gantt Charts during the World War I to handle scheduling problems associated with loading cargo to Allied ships. Not much done until 1950's, when there were rigorous mathematical analyses in both areas; such as the work of Arrow and his colleagues [5] and Dvoretzky and his colleagues [31,32] in inventory theory and Johnson [58] and Smith [76] in scheduling theory. Although there were few isolated studies, such as [33] and [60], which more or less attacked the lotsizing and sequencing problems jointly, the two areas developed quite independent of each other. Holstein [55] probably was the first to argue explicitly for the necessity of integrating these two areas.

After the publication of the critical articles on the state-of-the-art in these areas by the eminent researchers such as Wagner [79], Silver [74], and Graves [46], 1980's has witnessed the resurgence of research in integrating systems. In North America, the Hierarchical Production Planning was developed by a group at MIT (see [11] for an overview), a group at Cornell proposed a framework [63], developed COSMOS [67], and the resulting by-products such as XCELL+ [25] and PRS [20]. In Europe, GRAI Method was developed at the Automation Laboratory of University of Bordeaux 1 [30]. Also during this decade, the emerging production management paradigms, such as MRPII, OPT, and JIT, received considerable attention by both practitioners and researchers in the area (see [19] for an overview).

Some of the recent work concerning the integration issues are [28], [29], [70], [71], [23].

The central role played by mixed integer programming in production planning and scheduling models is stressed in [73]. As stated in [9], the successful solution of large-scale mixed integer programs requires formulations whose LP-relaxations give a good approximation to the convex hull of feasible solutions. Stronger mixed integer programming formulations have led to computational breakthroughs in number of large-scale problems; see, for example, [54] and [56]. The recent methodologies of branch-and-cut and branch-and-price, by themselves may not be sufficient in solving the huge mixed integer programming problems resulting from integrated production planning models. Coarse grained parallel computing may offer the needed additional computational capability [73,18].

6  Problems on Scheduling and Sequencing

  1. Suppose that 12 jobs must be processed in an open shop with six stages having a single machine in each. How many different sequences are there? If your computer could evaluate 100 schedules every second, how much time would be required in order to evaluate all feasible sequences.

  2. For each of the problems below, indicate precisely what or who would correspond to jobs and who or what would correspond to machines. In each case discuss what objectives might be appropriate and special priorities that might exist.
    • Treating patients in a hospital emergency room.

    • Unloading cargo from ships at port.

    • Serving users on a time-shared computer system.

    • Transferring long-distance phone calls from one city to another.

  3. Seven jobs are to be processed through a single machine. The processing times and the due dates are given below:
    Job 1 2 3 4 5 6 7
    Processing Time 3 6 8 421 7
    Due Date 4 8 12 15 11 25 21

    Determine the sequence that minimizes

      a Mean flow time,
      b number of tardy jobs,
      c Maximum lateness,
      d Makespan.

  4. Consider F3|||Cmax problem with the following processing time data:
    Machine
    Job A BC
    1426
    2237
    3656
    4348
    What is the makespan? Draw a Gantt chart for your solution.

  5. Suppose you own a auto paint shop. You have currently five cars waiting to be painted. You can only paint one car at a time. The time it takes to paint these cars and your expected profit from each car are:
    Car Painting time (hr.s) Profit ($100)
    A6 2
    B21
    C54
    D41
    E32
    In which order would you paint the cars? Why?

  6. Solve a F3|||Cmax problem with the following processing times
    Machine
    Job A BC
    112513
    261013
    391118
    417164

  7. Consider an F3|||Cmax problem:
    MachineDue
    Job A BC Date
    17535
    269812
    3136516
    424720

      a Draw a Gantt Chart for the permutation sequence {4-2-3-1}.
      b Determine the makespan, the mean flow time, maximum lateness, and maximum tardiness for the sequence in (a).
      c Instead of a single machine in the first stage, suppose you have four identical parallel machines (in stages two and three, you still have a single machine each). That is, the problem is F3|P4,1,1||Cmax. What is the improvement on the makespan?
      d What is the improvement if you have four machines in every stage? i.e. F3|P4||Cmax.

  8. We know that mean lateness and mean tardiness are not necessarily equal, are maximum tardiness and maximum lateness always equal? Explain.

  9. A manufacturer of charm bracelets has five jobs to schedule for a leading customer. Each job requires a stamping operation followed by a finishing operation, which can begin on an item immediately after its stamping is complete. The table below shows operation times per item (in minutes) for each job in the order. In addition, preparations for each job at the stamping facility require a setup before processing begins, as shown in the table below. Find a schedule that completes all five jobs as soon as possible.
    Job Items (min/item) Setup
    in Lot Stamp. Finish. Times
    1 20 2 8 100
    2 25 2 5 250
    3 100 1 2 60
    4 50 4 2.5 60
    5 40 3 6 80

  10. Consider the following F3|||Cmax problem
    Jobs123456
    pj,16124362
    pj,272611814
    pj,333871012
    Given that the Cmax of the sequence {3-5-6-4-2-1} is 57, find an optimal sequence.

  11. Consider the following three job problem with all ready times equal to zero:
    Job 1 2 3
    Processing Time 8 6 4
    Weight 2 1 2
    Due Date 10 10 10

    Assume that preemption is not allowed.

      (a) Sequence the jobs such that weighted mean flow time is minimized.
      (b) Evaluate your schedule by each of the following objectives:
      1. makespan,

      2. weighted flow time,

      3. weighted lateness,

      4. weighted tardiness,

      5. maximum flow time,

      6. maximum lateness,

      7. maximum tardiness, and

      8. weighted number of tardy jobs.

  12. Solve the following F3|||Cmax problem by branch & bound.
    Jobs123
    pj,1123
    pj,2321
    pj,3211

    1. State in words exactly what the problem (J3 |   | oj £ 3 | Cmax) is.

    2. Given that (J3 |   | oj £ 3 | Cmax) is NP-hard, based only on the reducibility graphs, Figure (3.1 ), what can you say about,
      • (F3 |   | oj £ 3 | Cmax)?

      • (J3 |   | oj £ 3 | Lmax)?

      • (J3 |   | oj £ 3, pmtn | Cmax)?

    3. (J3 |   | oj £ 3 | Cmax) is an optimization problem, state its corresponding decision (or, feasibility, or, recognition) problem.

Chapter 4
Location and Distribution

Location and distribution problems are intimately related. In location problems we wish to locate a number of facilities at certain points in order to optimize a given measure of performance. The facilities to be located can be plants, warehouses, distribution centers, machines on shop floor, transistors on a chip, etc. Whatever the system is, these facilities have some form of interaction among themselves and possibly with other facilities whose locations are fixed. For example, a number of items produced at certain plants are to be shipped to warehouses at a number of locations which in turn ship these items to regional distribution centers that serve individual customers at various final destinations. Distribution problems, on the other hand, determine how this flow of material should take place so that a given performance measure is optimized.

The simplest distribution problem is the transportation problem of linear programming. We wish to determine the amounts to be shipped from supply points at fixed locations with known amounts of available material, to demand points at fixed locations with known amounts of demand so as to minimize the total transportation costs. In this problem, since the locations of the facilities (i.e., the supply and demand points) are fixed, the distances among facilities are given parameters of the problem. The decision variables in the problem are the amount of interaction (i.e., the number of units shipped) among facilities. In the quadratic assignment problem, on the other hand, locations are the unknowns of the problem and the amount of interactions among facilities are the givens.

We can think of locations of the facilities implying a measure of proximity among facilities and the amounts of interaction between two facilities the facilities implying a measure of intensity between these facilities. Measures of proximity can be the distance or the time required to travel or the unit cost of shipment between facilities. Measures of intensity among facilities can be amount of material shipped per unit time or amount of communication required between a pair of facilities or some weight denoting the relative importance of one facility to the other.

1  Facility Location Models

Let F be the index set of facilities whose locations are the decision variables in the problem. In general, the cardinality of F can also be decision variable of the problem. Define G to the index set of facilities whose locations are known in advance and hence are the parameters of the problem. If we denote the level of proximity between any two facilities, i and j, by dij and the level of intensity by wij, then their joint contribution to the objective function can be expressed by (dijwij).

Depending upon the ``geographical'' restrictions on where the facilities are to be located, the location problems can be considered in three broad classes:

Planar Location
Facilities can be located at any point on the plane. Number of possible locations are infinite.
Network Location
Facilities can be located at any point on a given network. All the nodes and every point on the arcs of the network are possible candidate points, again resulting in infinite number of possible locations.
Discrete Location
Facility locations can be chosen among a finite set of given candidate points.

In planar location problems, the measure of proximity, dij, is the planar distance, lp. Let (xi, yi) denote the coordinates of a point, i, on the plane. Given any two points, i and j, on the plane, the lp distance between them is given by
[|xi - xj|p + |yi - yj|p]1/p,   for   p ³ 1,
where,

p=1,
gives the rectilinear distance value, and
p=2,
is the Euclidean distance; when
1 < p < 2,
the value of the distance lies between the rectilinear and Euclidean distance values, and for
p > 2,
the distance value lies below the Euclidean and continues to decrease as p increases. Finally, as
p ® ¥,
it takes the limiting value of so called Tchebychev distance,
max
  {|xi - xj|, |yi - yj|},
which is a convenient measure, for example, in modeling location problems involving the location of items moved in and out of an automated storage and retrieval systems [40].
In network location problems distance is measured as the shortest distance in the network; and in discrete location problems, it is part of the given data set.

In location problems there are two primary measures of performance:

Minimax
which minimizes the maximum contribution among all pairs of facilities; also referred to as p-centers problem,
min
  
max
(i,j) 
   {dijwij},   i,j Î F ÈG,
Minisum
which minimizes the sum of contributions of all facility pairs ; also referred to as p-medians problem,
min
  
å
(i,j) 
 {dijwij},   i,j Î F ÈG.

Exercise 1 Which measure of performance would you choose in locating

Exercise 2 Formal mathematical models of location problems go at least as back as Pierre de Fermat (1601-1665) who proposed a basic form of the Euclidean distance minisum problem by issuing the challenge [82]:

... let he who does not approve of my method, attempt the solution of the following problem: given three points in the plane, find the fourth point such that the sum of its distances to the three given points is a minimum.
Formulate the Fermat's problem using the notation introduced in this chapter and a suggest a solution approach.

The standard textbook on location problems is [41]. An excellent review of field by the same authors can be found in the article [40]. More advanced books on location problems are [62] and [65]. Discrete location models are reviewed in [3]. An overview of representative problems in location research is given in [17]. Algorithms and solution results for network location problems are comprehensively covered in [21,22].

In most of the location problems, it is desirable to be close to the facilities to be located. However, some facilities are ``undesirable'' or ``semi-desirable'', such as nuclear reactors, military installations, and polluting plants. It may be meaningful to use maximin and maxisum objective in locating such facilities. A comprehensive review of related research can be found in [36].

2  Discrete Location Problems

Let m denote the number of candidate facility locations, indexed by i=1,¼,m. Suppose there are n demand centers, indexed by j=1,¼,n, where the services or the products of the facilities are required. Let the amount demanded at demand center j be dj which is in units of quantity per period, such as tons per month, boxes per day, etc. A candidate facility location may have a limited capacity for production of goods or services, denote this capacity by ki, in same units as those for dj.

There are two sets of decision required: selection of locations for the facilities, and how much each open facility will ship to each demand center. Define the following decision variables, for i=1,¼,m, and j=1,¼,n:
yi = ì
í
î
1
if a facility is located at i,
0
otherwise.

xij = amount to be transported from i to j, per unittime.

The objective function is minimization of the total costs of fixed costs of locating facilities and the variable costs of transportation from these supply points to demand centers. Let fi be the fixed cost corresponding the candidate location i. The parameters fi's are in units of costs per unit time, where unit time is same as the unit used in dj; such as dollars per year. These costs may include amortized capital costs, annualized lease costs, insurance, taxes, and other overhead costs whose total is not directly related to the facility throughput [40]. Finally, the variable costs of transporting one unit from i to j is denoted by cij.

Then, the discrete facility location problem can be modeled as the following mixed integer linear programming problem:
min
å
i 
 fi yi +
å
i,j 
 cij xij
subject to:

å
i 
 xij
³
dj,   j=1,¼,n,

å
j 
 xij
£
ki yi,   i=1,¼,m.
where x ³ 0 and y=0,1.

Note that when we choose the locations by fixing the values of yi's, i.e. projecting the problem onto the space of y-variables, the resulting is a transportation problem. We can use a solution strategy in which we fix each yi to 0 or 1, and then solve the resulting transportation problem. We then can fix another set of y's and solve the transportation problem, etc. If we were to solve for all sets of y, the solution giving the minimum objective function value would be the optimum solution. However, if we can use the transportation problem to help us calculate a new set of y's which leads to a lower value of the adjective function, then we can converge to the optimal solution without having to check explicitly all possible sets of y. This is exactly what Benders' Decomposition does when applied to location and distribution problems.

Exercise 3 [Dual of the Transportation Problem [68]] Suppose ore is available at m mines and is required at n plants. Let bj   ( > 0) denote the minimum amount of ore required at plant j=1,¼,n, and let ai   ( > 0) denote the maximum amount of ore that can be shipped from mine i=1,¼,m. Let cij be the cost of shipping one unit of ore from the ith mine to the jth plant. The problem is to determine how much ore to ship from each mine to each plant (xij) in order to meet the requirements at the plants with minimum transportation cost.

Then a trucking company offers to take all the available ore at the mines and deliver the required amounts ore at the plants. Let ui be the price they agree to pay for one unit of ore at the ith mine and let vj be the price they agree to sell one unit of ore at the jth plant. Discuss an economic interpretation of the dual problem as that of maximizing the net revenue of the trucking company.

2.1  Benders' Decomposition

Benders' Decomposition [10] is a resource directive decomposition for solving large scale linear (mixed-integer) programming problems with coupling (or, complicating) variables. Whereas, Dantzig-Wolfe Decomposition [27] is a price directive decomposition for solving large scale mathematical programming problems with coupling (or, complicating) constraints. Therefore, it is natural to view these as duals of one another.

Decomposition algorithms, an addition to being computational techniques, can also be interpreted as descriptive theoretical models of planning. In a multi-divisional firm or in a multi-sector economy, the master problem can represent the actions of the coordinating center, while the subproblems correspond to the divisions or sectors. This interpretation can also be viewed as the simulation of decentralized planning procedures subject to central resource constraints and centrally defined objectives. It is important to point out that the decomposition algorithm, in this context, is the descriptive model of the preparation of the planning decisions, not the model of the everyday operation and of everyday control of the economic system.

A brief outline of Benders' Decomposition as applied to the discrete location problems is given below. Rewrite the location problem of the previous section in matrix notation as,

min
x ³ 0,y=0,1 
   {cx + dy | Ax +Dy ³ b }.
Define Y = {y=0,1   |  $  x ³ 0,   Ax ³ b - Dy}. Projecting onto the y-variables,

min
y Î Y 
   { dy +
min
x ³ 0 
 [  cx  |  Ax ³ b-Dy] }.
The inner minimization in the above problem is balanced transportation problem that is always feasible and has finite optimum. [Why? ]. Therefore we can replace it with its dual,

min
y Î Y 
   { dy +
max
u ³ 0 
 [u(b-Dy) | uA £ c]}
where u is the dual vector corresponding to the constraints {Ax ³ b - Dy}. Let {up,  p=1,¼,P} be the extreme points of {u ³ 0 | uA £ c}, then

min
y Î Y 
 { dy +
max
1 £ p £ P 
 [up(b-Dy)]},or


min
y Î Y,w 
 { dy + w   |   w ³ up (b-Dy),   p=1,¼,P }.
This problem which is equivalent to the original problem, has P constraints which can be a huge number. But it is likely that at optimality only a small subset of these constraints will be active. A natural solution strategy to apply for such problems is relaxation. Basically this solution strategy starts solving the problem with a small subset of the constraints, other constraints being ``relaxed''. The optimal solution thus obtained is checked if it satisfies the ``relaxed'' constraints. If it does, then we are done, otherwise, the most violated constraint is appended to the subset. [We may also discard some of the amply satisfied constraints (i.e. ones with the greatest slacks), when and if it is desirable to keep the size of the problem reasonable.] And the program is solved with the updated set of constraints. Thus, in this approach, instead of solving a large problem once, a number of smaller problems are solved many times.

The relaxed original problem is referred to as the master problem and the problem of determining the most violated constraint is called the subproblem . Let S Í {up,  k=1,¼,P}. Then the master problem is:

min
y Î Y,w 
 { dy + w | w ³ up (b-Dy),   up Î S}.
Let its optimal solution be (y°, w°). And the subproblem is given by:

max
u ³ 0 
   {u(b-D y°) | u A £ c },
and its dual is the transportation problem,

min
x ³ 0 
   {cx | Ax ³ b - d y°}.
Let their optimal solutions, respectively, be u° and x°. Finally, if w° ³ u°(b-Dy°), then (y°,x°) is optimal, otherwise S ¬ S +{u°}, and resolve the master problem. For a detailed analysis of the use of Benders Decomposition in distribution systems design see Geoffrion and Graves [44].

Exercise 4 Write down a pseudocode for Benders' Decomposition of the discrete location problem discussed in the previous section.

2.2  An Institutional Interpretation

It will be illustrative to discuss the master and sub-problems in terms of the following institutional interpretation. Consider two involved parties: The Producer and The Transporter. The Producer's concern is to determine at which sites the plants are to be constructed so as the total (fixed and variable) costs are minimized.

After determining the initial location vector, i.e. sites at which plants are to be constructed, The Producer subcontracts the remainder of the work, namely the production levels and transportation flows, to The Transporter. The Transporter's concern, after receiving the ``statement of work'' is to determine the production levels at the sites where plants are to be constructed and the transportation flows of commodities from the plants to the customers so as to minimize the transportation costs. This is accomplished by The Transporter by solving a transportation problem. After solving this problem, a ``bid'' is sent by The Transporter to the Producer stating how much the transportation will cost. In addition, The Transporter also sends a ``proposal'' which contains information about how the bid would be affected for certain changes in the statement of work.

The Producer, based on the proposal (and the bid) received from The Transporter, and other restrictions such as the configurational constraints on the opening of plants, checks whether the locations that were specified in the statement of work to The Transporter are optimal levels. If they are not yet optimal, a new statement of work is drafted and send to The Transporter. This iterative process continues until the location vector is optimal (or satisfactorily close to optimal), then the problem is solved, which is the termination of the overall solution procedure.

Exercise 5 Suppose we have the following warehouse location problem. There are three customers, j=1,2,3, with daily demands of 400, 200, and 300 units,respectively. There are three candidate sites, i=1,2,3, for leasing warehouses. Warehouse fixed costs would be $1,000 per day at each location for a capacity of 1,000 units or less. The unit transportation costs from each candidate site to each customer location are given below,

$/unitCustomer
Site 1 2 3
1145
2413
3641
Solve the problem and identify explicitly the information flow between the master and the subproblems in every major iteration.

3  Vehicle Routing and Scheduling

Design of a distribution system resulting in the number, locations, and sizes of facilities, and assignment of facilities to demand zones is basically a strategic issue. Routing and scheduling of vehicles on such a system is crucial from tactical and operational viewpoint. A system that is optimal in the strategic sense may not be the best choice when tactical and operational aspects are considered [15]. Given a transportation network and demands for service at various points in the network, ``spatial'' configuration of vehicle movements are the concern of routing problems; when ``temporal'' decisions are also important, that is, if explicit consideration is given to the times at which various locations are visited, we are faced with a vehicle scheduling problem [14].

The basic problem can be stated as follows [35]: A set of customers, each with a known location and a known requirement for some commodity, is to be supplied from a single facility by vehicles of known capacity. The problem is to design the minimum cost routes of these vehicles, subject to:

  1. The requirements of all the customers must be met.

  2. The total load allocated to each vehicle may not exceed its capacity.

  3. The total time (or, distance) for each vehicle to complete its route may not exceed some predetermined value.

  4. There is an earliest and a latest time within which a customer can accept a delivery.

When the last three constraints are relaxed, the problem reduces to traveling salesman problem, which is known to be strongly NP-Hard. The additional constraints can only make the solution even more difficult. If the last two constraints are relaxed, the problem is to determine the minimum number of vehicles, which is closely related to the classical knapsack problem. See [24] for various formulations and extensive bibliography in this area.

References

[1]
Russel L. Ackoff. Scientific Method: Optimizing Applied Research Decisions. Wiley, 1962.

[2]
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

[3]
C. H. Aikens. Facility location models for distribution planning. European J. Operational Research, 22:263-279, 1985.

[4]
H. Cemal Akyel. Minimizing Schedule Length on Identical Parallel Machines: An Exact Algorithm. PhD thesis, The Institute of Engineering and Science, Bilkent University, 1991.

[5]
K. A. Arrow, T. E. Harris, and J. Marschak. Optimal inventory policy. Econometrica, 19:250-272, 1951.

[6]
K. R. Baker. Introduction to Sequencing and Scheduling. Wiley, 1974.

[7]
K. R. Baker. Requirements planning. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, chapter 9, pages 571-628. North-Holland, 1993.

[8]
K. R. Baker. Elements of Sequencing and Scheduling. The Amos School of Business Administration, Dartmouth College, Hanover, N.H., 1994.

[9]
C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance. Branch-and-Price: Column generation for solving huge integer programs. In J. R. Birge and K. G. Murty, editors, Mathematical Programming: State of the Art 1994, pages 186-207. MPS, The University of Michigan, 1994.

[10]
J. F. Benders. Partioning procedures for solving mixed variables problems. Numer. Math., 4:238-252, 1962.

[11]
G. R. Bitran and D. Tirupati. Hierarchical production planning. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, chapter 9, pages 523-568. North-Holland, 1993.

[12]
J. Blazewicz, K. Ecker, G. Schmidt, and J. Weglarz. Scheduling in Computer and Manufacturing Systems. Springer-Verlag, 1993.

[13]
J. Blazewicz, J. K. Lenstra, and A. H. G. Rinnooy Kan. Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math., 5:11-24, 1983.

[14]
L. Bodin, B. Golden, A.Assad, and M. Ball. Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, 10:63-211, 1983.

[15]
J. H. Bookbinder and K. E. Reece. Vehicle routing considerations in distribution system design. European J. Operational Research, 37:204-213, 1988.

[16]
S. P. Bradley, A. C. Hax, and T. L. Magnanti. Applied Mathematical Programming. Addison-Wesley, 1977.

[17]
M. L. Brandeau and S. S. Chiu. An overview of representative problems in location research. Mgmt Sci., 35:645-674, 1989.

[18]
R. W Brown, J. F. Shapiro, and P. J. Waterman. Parallel computing for production scheduling. Manuf. Syst., 6:56-64, 1988.

[19]
Jimmie Browne, John Harhen, and James Shivnan. Production Management Systems: A CIM Perspective. Addison-Wesley, 1988.

[20]
C-WAY, 2359 N. Triphammer Road, Ithaca, New York 14850, USA. A Guided Tour of PRS: The Production Reservation System, 1990.

[21]
B. Ç. Tansel, R. L. Francis, and T. J. Lowe. Location on networks: A survey-part i. the p-center and p-median problems. Mgmt Sci., 29:482-497, 1983.

[22]
B. Ç. Tansel, R. L. Francis, and T. J. Lowe. Location on networks: A survey-part ii. exploiting the tree network structure. Mgmt Sci., 29:498-511, 1983.

[23]
Shi-Chung Chang and Fu-Shiung Hsieh. Integrated order and production scheduling for flow shops. In G. Dougmeingts, J. Browne, and M. Tomljanovich, editors, Computer Applications in Production and Engineering: Integration Aspects, pages 621-628. IFIP, Elsevier Science Publishers B. V. (North-Holland), 1991.

[24]
N. Christofides. Vehicle routing. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, editors, The Traveling Saleman Problem, chapter 12. Wiley, 1985.

[25]
R. Conway, W. L. Maxwell, J. O. McClain, and S. L. Worona. User's Guide to XCELL+: Factory Modeling System. The Scientific Press, third edition, 1990.

[26]
Richard W. Conway, William L. Maxwell, and Louis W. Miller. Theory of Scheduling. Addison-Wesley, 1967.

[27]
G. B. Dantzig and A. Wolfe. The decomposition algorithm for linear programming. Econometrica, 29:767-778, 1961.

[28]
Stephane Dauzere-Peres and Jean B. Lasserre. An Integrated Approach in Production Planning and Scheduling, volume 411 of Lectures Notes in Economics and Mathematical Systems. Springer-Verlag, 1994.

[29]
Stephane Dauzere-Peres and Jean-Bernard Lasserre. Integration of lotsizing and scheduling decisions in a job-shop. European J. Operational Research, 75:413-426, 1994.

[30]
G. Dougmeingts, L. Pun, M. Mondain, and D. Breuil. Decision making system for production control, planning, and scheduling. Int. J. Prodn Res., 16:137-152, 1978.

[31]
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. The inventory problem: I. case of known distributions of demand. Econometrica, 20:187-222, 1952.

[32]
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. The inventory problem: II. case of unknown distributions of demand. Econometrica, 20:450-466, 1952.

[33]
B. P. Dzielinski and R. E. Gomory. Optimal programming of lot lot sizes, inventory, and labor allocations. Mgmt Sci., 11:874-890, 1965.

[34]
J. Edmonds. Paths, trees, and flowers. Canad. J. Math., 17:449-467, 1965.

[35]
S. Eilon, C. D. T. Watson-Gandy, and N. Christofides. Distribution Management: Mathematical Modelling and Practical Analysis. Hafner, 1971.

[36]
E. Erkut and S. Neuman. A survey of analytical models for locating undesirable facilities. European J. Operational Research, 40:275-291, 1989.

[37]
Donald Erlenkotter. An early classic misplaced: Ford W. Harris's economic order quantity model of 1915. Mgmt Sci., 35:898-900, 1989.

[38]
Donald Erlenkotter. Ford Whitman Harris and the economic order quantity model. Ops Res., 38:937-946, 1990.

[39]
M. Florian, J. K. Lenstra, and A. H. G. Rinnooy Kan. Deterministic production planning: Algorithms and complexity. Mgmt Sci., 26:669-679, 1980.

[40]
R. L. Francis, L. F. McGinnes, and J. A. White. Locational analysis. European J. Operational Research, 12:220-252, 1983.

[41]
R. L. Francis, L. F. McGinnes, and J. A. White. Facility Layout and Location. Prentice-Hall, second edition, 1992.

[42]
Simon French. Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Series in Mathematics and Its Applications. John Wiley & Sons, 1982.

[43]
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.

[44]
A. M. Geoffrion and G. W. Graves. Multicommodity distribution system design by benders decomposition. Mgmt Sci., 20:822-844, 1974.

[45]
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling theory: A survey. Annals of Discrete Mathematics, 5:287-326, 1979.

[46]
S. C. Graves. A review of production scheduling. Ops Res., 29:646-675, 1981.

[47]
S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors. Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science. Elsevier Science, 1993.

[48]
G. Hadley and T. M. Whitin. Analysis of Inventory Systems. Prentice-Hall, 1963.

[49]
Ford W. Harris. How many parts to make at once. Factory, The Magazine of Management, 10:135-136,152, 1913. Reprinted in Ops Res., 38:947-950, 1990.

[50]
A. C. Hax and D. Candea. Production and Inventory Management. Prentice-Hall, 1984.

[51]
Jeffrey W. Herrmann, Chung-Yee Lee, and Jane L. Snowdon. A classification of static scheduling problems. In Panos M. Pardalos, editor, Complexity in Numerical Optimization, pages 203-253. World Scientific Publishing Co., P.O.Box 128, Farrer Road, Singapore 9128, 1993.

[52]
Frederick S. Hillier and Gerald J. Lieberman. Introduction to Operations Research. Holden-Day, fourth edition, 1986.

[53]
James K. Ho and William A. McKenney. Triangularity of the basis in linear programs for material requirements planning. Opns. Res. Lett., 7:273-278, 1988.

[54]
K. Hoffman and M. Padberg. LP-based combinatorial problem solving. Annals of Operations Research, 4:145-194, 1985.

[55]
W. K. Holstein. Production planning and control integrated. Harvard Business Review, May-June 1968.

[56]
Ellis L. Johnson. Modeling and strong linear programs for mixed integer programming. In Stein W. Wallace, editor, Algorithms and Model Formulations in Mathematical Programming, pages 1-43, Berlin Heidelberg, 1989. NATO ASI Series, Vol. F51, Springer-Verlag.

[57]
Lynwood A. Johnson and Douglas C. Montgomery. Operations Research in Production Planning, Scheduling, and Inventory Control. Wiley, 1974.

[58]
S. M. Johnson. Optimal two and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1:61-68, 1954.

[59]
George E. Kimball. General principles of inventory management. J. of Manufacturing and Opns. Mgmt., 1:119-130, 1988.

[60]
L. S. Lasdon and R. C. Terjung. An efficient algorithm for multi-item scheduling. Ops Res., 19:946-969, 1971.

[61]
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, chapter 9, pages 445-522. North-Holland, 1993.

[62]
R. F. Love, J. G. Morris, and G. O. Wesolowsky. Facilities Location: Models & Methods. North-Holland, 1988.

[63]
W. Maxwell, J. Muckstadt, L. J. Thomas, and J. Vander Eecken. A modeling framework for planning and control of production in discrete parts manufacturing and assembly systems. Interfaces, 13:92-104, 1983.

[64]
Harlan C. Meal. Putting production decisions where they belong. Harvard Business Review, 62:102-111, 1984.

[65]
P. B. Mirchandani and R. L. Francis, editors. Discrete Location Theory. Wiley, 1990.

[66]
T. E. Morton and D. W. Pentico. Heuristic Scheduling Systems with Applications to Production Systems and Project Management. Wiley, 1993.

[67]
J. A. Muckstadt, P. L. Jackson, W. T. Martin, S. Bellantoni, and R. Ferstenberg. Cornell simulator of manufacturing operations (COSMOS). Technical Report 684, SORIE, Cornell University, 1986.

[68]
Katta G. Murty. Linear Programming. Wiley, 1983.

[69]
Evan L. Porteus. Stochastic inventory theory. In D. P. Heyman and M. J. Sobel, editors, Stochastic Models, volume 2 of Handbooks in Operations Research and Management Science, chapter 12, pages 605-652. North-Holland, 1990.

[70]
C. N. Potts and L. van Wassenhove. Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. Journal of Operational Research Society, 48:395-406, 1992.

[71]
D. B. Pressmar. LP-models in production planning and control. In G. Fandel, Thomas Gulledge, and Albert Jones, editors, New Directions for Operations Research in Manufacturing, pages 91-100, Berlin - Heidelberg, 1992. Springer-Verlag. Proceedings of a Joint US/German Conference, Gaithersburg, Maryland, USA, July 30-31, 1991.

[72]
B. Roy and B. Sussmann. Les problémes d'ordonnancement avec contraintes disjonctives. Note DS no. 9 bis, SEMA, Montrouge, 1964.

[73]
J. F. Shapiro. Mathematical programming models and methods for production planning and scheduling. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, chapter 9, pages 371-444. North-Holland, 1993.

[74]
E. A. Silver. Operations research in inventory management: A review and critique. Ops Res., 29:628-645, 1981.

[75]
Edward A. Silver and Rein Peterson. Decision Systems for Inventory Management and Production Planning. Wiley, second edition, 1985.

[76]
W. E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3:59-66, 1956.

[77]
L. J. Thomas and J. O. McClain. An overview of production planning. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, chapter 9, pages 333-370. North-Holland, 1993.

[78]
Arthur F. Veinott, Jr. Production planning with convex costs: A parametric study. Mgmt Sci., 10:441-460, 1964.

[79]
H. M. Wagner. Research portfolio for inventory management and production planning systems. Ops Res., 28:445-475, 1980.

[80]
Harvey M. Wagner. Principles of Operations Research. Prentice-Hall, 1969.

[81]
Harvey M. Wagner and Thomson M. Whitin. Dynamic version of the economic lot size model. Mgmt Sci., 5:89-96, 1958.

[82]
G. O. Wesolowsky. The Weber problem: History and perspectives. Location Science, 1:5-23, 1993.

Footnotes:

1It is customary to refer to uncontrollable variables as parameters and to controllable variables as decision variables or, simply, as variables.

2Even in the case of shortages this applies. Backorders are met at a later date causing additional costs. Planned lost sales are not really applicable in a make-to-order environment.

3This function implies both procurement and inventory related costs.

4A different kind of demand interaction occurs when there exists correlated demand (when the demand of one item is correlated with another), as occuring in marketing phenomena of substitution or reinforcement.

5To be precise, this is true only in the absence of discounting. Throughout this discussions, discounting of the future costs are not treated.

6Notice that, because of the inventory balance equations, it is sufficient to specify either inventory levels or the procurement amounts.

7The planning horizon analysis is also an equally challenging problem in concave and linear cost functions.

8In the words of [77] `` The Wagner-Whitin Legacy ... started a small industry.''

9satisfying + sufficing

File translated from TEX by TTH, version 3.13.
On 3 Oct 2002, 06:25.