Production Scheduling Model

DETERMINISTIC PERIODIC-REVIEW MODEL

Previously the basic EOQ model and some of its variations were dependent upon the
assumption of a constant demand rate. When this assumption is relaxed, i.e., when the amounts
that need to be withdrawn from inventory are allowed to vary from period to period, the EOQ
formula no longer ensures a minimum-cost solution.
Consider the following periodic-review model. Planning is to be done for the next n periods
regarding how much (if any) to produce or order to replenish inventory at the beginning of each
of the periods. (The order to replenish inventory can involve either purchasing the units or
producing them, but the latter case is far more common with applications of this model, so we
mainly will use the terminology of producing the units.) The demands for the respective periods
are known (but not the same in every period) and are denoted by
ri = demand in period i, for i _ 1, 2, . . . , n.
These demands must be met on time. There is no stock on hand initially, but there is still
time for a delivery at the beginning of period 1.
The costs included in this model are similar to those for the basic EOQ model:
K= setup cost for producing or purchasing any units to replenish inventory at beginning
of period,
c =unit cost for producing or purchasing each unit,
h=holding cost for each unit left in inventory at end of period.
Note that this holding cost h is assessed only on inventory left at the end of a period. There also
are holding costs for units that are in inventory for a portion of the period before being
withdrawn to satisfy demand. However, these are fixed costs that are independent of the
inventory policy and so are not relevant to the analysis. Only the variable costs that are affected
by which inventory policy is chosen, such as the extra holding costs that are incurred by
carrying inventory over from one period to the next, are relevant for selecting the inventory
policy.
By the same reasoning, the unit cost c is an irrelevant fixed cost because, over all the time
periods, all inventory policies produce the same number of units at the same cost. Therefore, c
will be dropped from the analysis hereafter.
The objective is to minimize the total cost over the n periods. This is accomplished by ignoring
the fixed costs and minimizing the total variable cost over the n periods, as illustrated by the
following example.

Example. An airplane manufacturer specializes in producing small airplanes. It has just

received an order from a major corporation for 10 customized executive jet airplanes for the
use of the corporation’s upper management. The order calls for three of the airplanes to be
delivered (and paid for) during the upcoming winter months (period 1), two more to be
delivered during the spring (period 2), three more during the summer (period 3), and the final
two during the fall (period 4).
Setting up the production facilities to meet the corporation’s specifications for these airplanes
requires a setup cost of $2 million. The manufacturer has the capacity to produce all 10
airplanes within a couple of months, when the winter season will be under way. However, this
would necessitate holding seven of the airplanes in inventory, at a cost of $200,000 per airplane
per period, until their scheduled delivery times. To reduce or eliminate these substantial holding
costs, it may be worthwhile to produce a smaller number of these airplanes now and then to
repeat the setup (again incurring the cost of $2 million) in some or all of the subsequent periods
to produce additional small numbers. Management would like to determine the least costly
production schedule for filling this order.
Thus, using the notation of the model, the demands for this particular airplane during the four
upcoming periods (seasons) are
r1 = 3, r2 = 2, r3 = 3, r4 = 2.
Using units of millions of dollars, the relevant costs are
K = 2, h = 0.2.
The problem is to determine how many airplanes to produce (if any) during the beginning
of each of the four periods in order to minimize the total variable cost.
The high setup cost K gives a strong incentive not to produce airplanes every period and
preferably just once. However, the significant holding cost h makes it undesirable to carry a
large inventory by producing the entire demand for all four periods (10 airplanes) at the
beginning. Perhaps the best approach would be an intermediate strategy where airplanes are
produced more than once but less than four times. For example, one such feasible solution (but
not an optimal one) is depicted in Fig. 1, which shows the evolution of the inventory level over
the next year that results from producing three airplanes at the beginning of the first period, six
airplanes at the beginning of the second period, and one airplane at the beginning of the fourth
period. The dots give the inventory levels after any production at the beginning of the four
periods.
How can the optimal production schedule be found? For this model in general, production (or
purchasing) is automatic in period 1, but a decision on whether to produce must be made for
each of the other n - 1 periods. Therefore, one approach to solving this model is to enumerate,
for each of the 2n-1 combinations of production decisions, the possible quantities that can be
produced in each period where production is to occur. This approach is rather cumbersome,
even for moderate-sized n, so a more efficient method is desirable. Such a method is described
next in general terms, and then we will return to finding the optimal production schedule for
the example. Although the general method can be used when either producing or purchasing to
replenish inventory, we now will only use the terminology of producing for definiteness.
An Algorithm
The key to developing an efficient algorithm for finding an optimal inventory policy (or
equivalently, an optimal production schedule) for the above model is the following insight into
the nature of an optimal policy.
An optimal policy (production schedule) produces only when the inventory level is zero. To
illustrate why this result is true, consider the policy shown in Fig. 1 for the example. (Call it
policy A.)
 Fig 1. The inventory level

Policy A violates the above characterization of an optimal policy because production occurs at
the beginning of period 4 when the inventory level is greater than zero (namely, one airplane).
However, this policy can easily be adjusted to satisfy the above characterization by simply
producing one less airplane in period 2 and one more airplane in period 4. This adjusted policy
(call it B) is shown by the dashed line in Fig. 2 wherever B differs from A (the solid line). Now
note that policy B must have less total cost than policy A. The setup costs (and the production
costs) for both policies are the same. However, the holding cost is smaller for B than for A
because B has less inventory than A in periods 2 and 3 (and the same inventory in the other
periods). Therefore, B is better than A, so A cannot be optimal.

This characterization of optimal policies can be used to identify policies that are not optimal.
In addition, because it implies that the only choices for the amount produced at the beginning
of the ith period are 0, ri, ri + ri+1, . . . , or ri+ri+1 +….+ rn, it can be exploited to obtain an
efficient algorithm that is related to the deterministic dynamic programming approach.

Fig.2 Comparison of two inventory policies A and B

In particular, define
Ci= total variable cost of an optimal policy for periods i, i+ 1, . . . , n when period i starts with
zero inventory (before producing), for i= 1, 2, . . . , n.
By using the dynamic programming approach of solving backward period by period, these
Ci values can be found by first finding Cn, then finding Cn+1, and so on. Thus, after Cn, Cn-1, .
. . , Ci-1 are found, then Ci can be found from the recursive relationship
Ci = minimum j=i, i+1, …., n{Cj+1 +K+ h[ri+1 + 2ri+2 +3ri+3 +…+( j-i)rj]},
where j can be viewed as an index that denotes the (end of the) period when the inventory
reaches a zero level for the first time after production at the beginning of period i. In the time
interval from period i through period j, the term with coefficient h represents the total holding
cost over this interval. When j =n, the term Cn+1 =0. The minimizing value of j indicates that if
the inventory level does indeed drop to zero upon entering period i, then the production in
period i should cover all demand from period i through this period j.
The algorithm for solving the model consists basically of solving for Cn, Cn-1, . . . , C1 in turn.
For i = 1, the minimizing value of j then indicates that the production in period 1 should cover
the demand through period j, so the second production will be in period j +1. For i = j +1, the
new minimizing value of j identifies the time interval covered by the second production, and
so forth to the end. We will illustrate this approach with the example.

Application of the Algorithm to the Example

Returning to the airplane example, first we consider the case of finding C4, the cost of the
optimal policy from the beginning of period 4 to the end of the planning horizon:
C4= C5+2 =0+2=2.
To find C3, we must consider two cases, namely, the first time after period 3 when the inventory
reaches a zero level occurs at (1) the end of the third period or (2) the end of the fourth period.
In the recursive relationship for C 3, these two cases correspond to (1) j = 3 and (2) j = 4.
Denote the corresponding costs (the right-hand side of the recursive relationship with this j) by
C3(3) and C3(4) respectively. The policy associated with C3(3) calls for producing only for period
3 and then following the optimal policy for period 4, whereas the policy associated with C3(4)
calls for producing for periods 3 and 4. The cost C3 is then the minimum of C3(3) and C3(4).
C3(3) =C4+2=2+2=4
C3(4)=C5+2+0.2(2)=0+2+0.4=2.4
C3 = min{4, 2.4} =2.4.
Therefore, if the inventory level drops to zero upon entering period 3 (so production should
occur then), the production in period 3 should cover the demand for both periods 3 and 4. To
find C2, we must consider three cases, namely, the first time after period 2 when the inventory
reaches a zero level occurs at (1) the end of the second period, (2) the end of the third period,
or (3) the end of the fourth period. In the recursive relationship for C2, these cases correspond
to (1) j =2, (2) j = 3, and (3) j = 4, where the corresponding costs are
C2(2)= C3+2=2.4+2=4.4
C2(3)=C4+2+0.2(3)=2+2+0.6=4.6
C2(4)= C5+2+ 0.2[3+2(2)] = 0 +2 + 1.4 =3.4.
C2= min {4.4, 4.6, 3.4} =3.4.
this production should cover the demand for all the remaining periods.
Finally, to find C1, we must consider four cases, namely, the first time after period 1when the
inventory reaches zero occurs at the end of (1) the first period, (2) the second period, (3) the
third period, or (4) the fourth period. These cases correspond to j=1, 2, 3, 4 and to the costs
C1(1), C1(2), C1(3), C1(4), respectively. The cost C1 is then the minimum of C1(1), C1(2), C1(3), C1(4).
C1(1) = C2 +2 = 3.4 +2 = 5.4.
C1(2) = C3 +2 + 0.2(2) = 2.4 +2 +0.4 =4.8.
C1(3) =C4 +2 +0.2[2 +2(3)] =2 +2 + 1.6 =5.6.
C1(4) =C5 +2 +0.2[2 +2(3) +3(2)] =0 +2 +2.8 =4.8.
C1 =min {5.4, 4.8, 5.6, 4.8} =4.8.
Note that C1(2) and C1(4) tie as the minimum, giving C1. This means that the policies
corresponding to C1(2) and C1(4) tie as being the optimal policies. The C1(4) policy says to
produce enough in period 1 to cover the demand for all four periods. The C1(2) policy covers
only the demand through period 2. Since the latter policy has the inventory level drop to zero
at the end of period 2, the C3 result is used next, namely, produce enough in period 3 to cover
the demand for periods 3 and 4. The resulting production schedules are summarized below.
Optimal Production Schedules.
1. Produce 10 airplanes in period 1.
Total variable cost _ $4.8 million.
2. Produce 5 airplanes in period 1 and 5 airplanes in period 3.
Total variable cost _ $4.8 million