Estimating the Costs of Planned Changes Implied by Freezing Production Plans

Abstract

The use of production planning algorithms on a rolling horizon basis is very common in practice. However, this leads to frequent changes in planned quantities for future periods which may adversely impact support activities such as material preparation, staffing, and setup planning. In this chapter we examine two widely used approaches for this problem, the use of change costs to penalize changes in planned quantities and freezing of the plan by prohibiting any changes in some number of periods in the near future. We use a linear programming model of a single-product single-stage system to develop insights into the conditions when the two approaches are equivalent. Specifically, we derive lower bounds on the values of the change costs which will ensure freezing of the plan in a given planning epoch, and present numerical results to illustrate our findings.

2.1 Introduction

Rolling horizon procedures, where an infinite horizon problem is approximated by the solution to a sequence of finite horizon problems, are common in production planning practice and research. We define the points in time at which a finite horizon model is solved as a planning epoch s, and the interval of time consisting of the T periods $t = s,s + 1,\ldots,s + T - 1$ covered by its planned decisions as the planning window T. Thus at each epoch new values of key decision variables, especially planned release quantities, are calculated, resulting in changes in the planned values of these variables from one epoch to the next. The changes in planned release quantities that occur in each period as new updated demand information becomes available may disrupt supporting activities such as staffing, material procurement, and machine setup that are initiated based on plans developed in earlier periods. This phenomenon, referred to in the literature as schedule nervousness or stability, has been addressed by many researchers over the last several decades (Mather 1977; Carlson et al. 1979; Blackburn et al. 1985, 1986; Sridharan et al. 1988; Narayanan and Robinson 2010).

Several approaches have been proposed to alleviate scheduling nervousness, such as introducing ending conditions in the model solved at each epoch (Eilon 1975; Hung and Leachman 1996; Fisher et al. 2001; Voss and Woodruff 2006), forecasting beyond the current planning horizon (Grinold 1980; Carlson et al. 1982; Grinold 1983; Kropp et al. 1983; Blackburn et al. 1985, 1986), holding safety stock (Kropp et al. 1983; Blackburn et al. 1985, 1986; Yano and Carlson 1987; Sridharan and LaForge 1989; Metters and Vargas 1999; Bai et al. 2002; Sahin et al. 2013), freezing the schedule by prohibiting changes in certain periods (Blackburn et al. 1985, 1986; Sridharan et al. 1987, 1988; Sridharan and Berry 1990; Zhao and Lee 1993; Zhao and Xie 1998; Zhao and Lam 1997; Xie et al. 2003), and introducing change costs (Carlson et al. 1979; Kropp et al. 1983; Voss and Woodruff 2006) and chance constraints (Johnson and Montgomery 1974; Bookbinder and Tan 1988; Tarim and Kingsman 2004; Ravindran and Uzsoy 2011; Aouam and Uzsoy 2014). In this chapter we focus on the link between two prominent methods: freezing the schedule by prohibiting planned changes for some subset of the periods in the current planning window, and introducing change costs in the objective function that penalize planned changes, in a single-stage single-product system with fixed lead time and limited capacity. We assume the planning problem solved at each epoch of the rolling horizon procedure takes the form of a linear program, and analyze the structure of optimal solutions to develop lower bounds on the values of change costs that will guarantee zero planned changes in a given period of the current epoch, i.e., freezing the schedule, at optimality. We thus demonstrate the equivalence between freezing the schedule and penalizing planned changes in the objective function.

In the next Sect. 2.2, we will briefly discuss the methods of freezing schedules and introducing change costs. In Sect. 2.3, we present the primal and dual formulations for a single-stage single-product production system. In Sect. 2.4, we analyze the behavior of release changes for a single-product model. Detailed analysis of unit release change costs to guarantee freezing is provided in Sect. 2.5. A computational study illustrates the implications of our findings in Sect. 2.6. Section 2.7 summarizes our conclusions and discusses future research directions.

2.2 Literature Review

In this section, we briefly introduce the rolling horizon approach used in this chapter, and then discuss the methods of freezing the schedule and introducing change costs.

2.2.1 Rolling Horizon Approach

In the most common application of the rolling horizon approach, time is considered in discrete periods $t = 1,\ldots,\infty$. At the start of each planning epoch s, all relevant information on the state of the production system and estimated future demand is collected and a production plan developed for the next T periods s, s + 1, …, $s + T - 1$ using a finite horizon planning model whose nature may vary with the application domain. The specific decisions usually involve planned material release quantities R _t (s) and production quantities X _t (s) for each period as well as lot sizes in problems involving setup times. The decisions for the current period s are implemented, and time advances to the beginning of period s + 1, when the process of information collection and planning recommences. We shall refer to each period s at which a finite horizon plan is developed as a planning epoch, the set of periods s, s + 1, …, $s + T - 1$, as the current planning window, and the number of periods T considered in the finite horizon model as the planning window length. We shall denote the set of all information available for planning purposes at the start of period s as Ω(s) and the solution obtained by the planning model solved at the start of period s as $\mathbf{R(s)} = \left [R_{s}(s),R_{s+1}(s),\ldots,R_{s+T-1}(s)\right ]$ where R _t (s), $\forall t = 1,\ldots,K$ denotes the values of the decision variables R _t (s) computed for period t at planning epoch s, $s \leq t \leq s + T - 1$. K is the final period of the entire planning horizon.

A natural consequence of this process is that the decision variables R _t (s) associated with a given period t, t ≤ s and $0 \leq s - t \leq T - 1$, are revised T − 1 times before actually being implemented in period t = s. The changes arise from the fact that the finite horizon planning models used to develop plans at successive planning epochs use different sets of information, i.e., $\varOmega (s) \subset \varOmega (s + 1)$. A given period t, t ≤ s and $0 \leq s - t \leq T - 1$, will first be considered at planning epoch $s = t - T + 1$, yielding decision variable $R_{t}(t - T + 1)$. The next planning epoch will yield a new set of decision variables $R_{t}(t - T + 2)$ for period t. Eventually, after new decisions $R_{t}(t - T + 1)$, $R_{t}(t - T + 2)$, …, R _t (t − 1) have been calculated at planning epochs $s = t - T + 1,\ldots,t - 1$, the decision variable R _t (s) will be implemented at epoch s = t. The basic rolling horizon procedure we study is thus described as follows:

2.2.2 Algorithm RH

Step 1::

Set s = 0, given the initial WIP level W ₀(s) and finished goods inventory (FGI) levels I ₀(s).

Step 2::

Increment s by 1.

Step 3::

Solve the finite horizon problem with planning window length T involving periods s to $s + T - 1$.

Step 4::

Implement the releases R _s (s) and production X _s (s) as the realized plan. Record the WIP W _s (s) and FGI I _s (s) at the end of period s as initial values of WIP $W_{s}(s) = W_{s}(s + 1)$ and FGI $I_{s}(s) = I_{s}(s + 1)$ for the next window from periods s + 1 to s + T.

Step 5::

Update the demand forecasts for periods s + 1 to s + T.

Step 6::

Return to Step 2 and repeat until epoch $s = K - T + 1$.

This repeated revision of the planning decisions for each period can cause problems in practice. One of the purposes of production planning is to provide visibility into future requirements for ancillary functions that support production, such as staffing, maintenance, and purchasing. Frequent changes in planned release and production quantities can lead to significant disruptions in these support activities, often rendering the execution of the production plans infeasible and leading to much wasted effort due to redundant updates. In the notation above, the change in the planned release quantities R _t (s) and R _t (s + 1) from epoch s to epoch s + 1 is given by:

$$\displaystyle{ \bigtriangleup R_{t}(s,s + 1) = R_{t}(s + 1) - R_{t}(s). }$$

We shall refer to these changes as planned changes in the production plan from epoch s to the next epoch s + 1. In this study, we focus on planned changes in only one set of decision variables, the release variables R _t (s), because these decisions affect both production planning and its supporting activities.

2.2.3 Freezing the Schedule Within the Planning Horizon

In many production environments it is important to maintain a stable production plan where decisions for a given time period are not changed dramatically from epoch to epoch. Frequent, large changes in previously announced plans will cause the users of those plans to question their reliability; if they feel plans are unreliable, users will tend to ignore any planned releases and production that they think are likely to change in the future. Supporting activities such as staffing, machine preparation, and materials procurement need time to respond to changes in planned releases, which may cause longer cycle times for the entire production system. Therefore, a stable plan is preferable.

Freezing the schedule fixes the production plans for the next several periods, permitting no changes even when there are changes in demand. This has the advantage of eliminating planned changes in the frozen periods, but also limits the system’s ability to respond to demand changes. When demand forecasts are revised upwards, freezing may result in unmet demand and reduced customer service levels. When demand forecasts are revised down in the face of reduced demand, excess inventories may accumulate. Plans associated with periods further in the future are allowed to change.

Freezing the schedule was proposed with the aim of controlling schedule nervousness (Sahin et al. 2013). This strategy aims to divide a single planning window into two parts as shown in Fig. 2.1: frozen periods and a free interval. The frozen periods, in turn, consist of two parts: lead time and additional freezing periods. In a rolling horizon environment, the output for the first L periods is determined by releases implemented in periods prior to the current planning window and cannot be changed. Freezing a period implies a decision not to change the planned release quantities even when demand has changed. We can only change releases in periods in the free interval in response to demand changes.

Fig. 2.1

Concept of freezing the schedule

Many researchers (Blackburn et al. 1985, 1986; Sridharan et al. 1987, 1988; Sridharan and Berry 1990; Zhao and Lee 1993; Zhao and Xie 1998; Zhao and Lam 1997; Xie et al. 2003) have proposed freezing schedules to provide more stable production plans. There are two general freezing approaches, order-based and period-based freezing (Sridharan et al. 1987; Zhao and Lee 1993). Under order-based freezing we freeze specific orders, while period-based freezing freezes all orders in the schedule for specified periods. In this chapter we consider the latter approach. In terms of schedule stability, Zhao and Lee (1993) found that period-based freezing with longer freezing periods outperforms order-based freezing in terms of schedule changes, but with lower service level and higher costs. Sridharan et al. (1987) found that in an uncapacitated system freezing up to 50 % of the planning window increases production changeover and inventory carrying costs only slightly. Zhao and Lee (1993) further found that under deterministic demand, longer freezing periods affect cost performance, production instability, and service level only slightly. Sridharan and LaForge (1994a) also found that freezing part of the schedule reduces the service level slightly. However, under stochastic demand, longer freezing periods degrade all performance measures. They suggested balancing schedule stability and service level by choosing an appropriate length of the freezing period when demand is stochastic.

In order to increase the service level in the presence of frozen schedules, Yano and Carlson (1987) and Sridharan and LaForge (1989) suggested holding safety stock. In the presence of safety stock, Sridharan and LaForge (1989, 1994a,b) found that freezing a part of the schedule may reduce the service level only slightly. By specifying safety stock levels, Sridharan and Berry (1990) claimed that freezing the schedules can reduce schedule instability under both deterministic and stochastic demand. Blackburn et al. (1985, 1986) presented a comprehensive comparison of four different production strategies to improve schedule stability: lot for lot, freezing the schedule, introducing change costs, and extending the planning window by forecasting using the Wagner-Whitin algorithm and Silver-Meal heuristic. They suggested that under most conditions, freezing the schedule and implementing change costs yield better cost and schedule stability than the other planning strategies. They also pointed out that when demand is uncertain with fixed capacity and lead time, freezing the schedule only helps schedule stability. The question of how to select proper values for freezing window length and change costs is left open. Thus, there is a tradeoff between schedule stability, on the one hand, and other performance measures such as service level and total cost, on the other.

2.2.4 Introducing Change Costs

The method of introducing change costs also aims to control schedule nervousness by penalizing both positive and negative planned changes from one planning epoch to the next (Voss and Woodruff 2006). Change costs represent a unit cost imposed on any planned change from the planned quantity computed in the previous planning epoch. Carlson et al. (1979) and Kropp et al. (1983) also proposed incorporating schedule change costs into material requirement planning (MRP) using the Wagner-Whitin (1958) algorithm in a rolling horizon environment with setup costs. They did not consider unit change costs but focused instead on the introduction of additional setups, without cancelling an existing setup. They suggested that with schedule change costs an optimization model will choose the most economical solution, but did not discuss how to set appropriate values for change costs. Kropp and Carlson (1984) introduced change costs for adding or cancelling a setup and suggested, following Carlson et al. (1979) and Kropp et al. (1983), that schedule change costs can help to control the tradeoff between holding and setup costs in order to minimize total overall costs. Based on the contributions of Carlson et al. (1979), Kropp et al. (1983) and Kropp and Carlson (1984), Blackburn et al. (1985, 1986) further modified the change costs to encourage new setups and discourage cancellation of an already planned setup. They compared the change cost method to other strategies such as lot sizing, freezing schedules, and holding safety stocks in a rolling horizon environment, finding that adding change costs and freezing the schedule provide better results. However, the problem of specifying appropriate values of the change costs is critical to the effective use of this approach. Setting change costs too high may result in increased costs due to excess inventories or backorders, while setting them too low may permit unnecessary changes in planned quantities.

Braun and Schwartz (2012) examine three different methods to reduce schedule nervousness in master production scheduling: (1) Freezing the schedule, (2) Move suppression, and (3) Schedule change suppression. The frozen horizon approach involves freezing the schedule for a certain number of periods in each planning window. Move suppression introduces a penalty cost on the changes from period t − 1 to the next period t in the same planning epoch. Schedule change suppression introduces unit change costs on any change made in any planned quantity from one epoch to the next. Both move suppression and schedule change suppression are controlled by a penalty factor trying to minimize the level of schedule nervousness, defined as the maximum amount of change from period to period. Under this objective, move suppression performs the best, followed by schedule change suppression. The frozen horizon approach creates the most nervousness because it needs to react to fulfill demand. The penalty cost plays a critical role in controlling both the timing and magnitude of schedule changes. However, determining a specific value for the penalty cost requires considerable trial and error. In addition, the three approaches do not consider capacity and holding cost, yielding no clues as to the impact of the policies on backlogs and inventory costs.

Cost structure is also a critical factor that affects the performance of planning systems. Several researchers (Sridharan et al. 1987; Sridharan and Berry 1990; Zhao and Lee 1993; Kadipasaoglu and Sridharan 1995) have found that the ratio of setup and FGI holding costs influences schedule stability, service level, and total cost performance in MRP. A large setup to holding cost ratio produces fewer setups, generating lower total cost and more stable plans. However, these findings assume unlimited capacity and no backlogging. Voss and Woodruff (2006) impose a common nonnegative change cost on both positive or negative changes. They also suggest that a quadratic penalty function is more realistic and simpler, removing the need to distinguish between positive and negative changes. However, this results in a nonlinear objective and does not consider the different causes of positive or negative changes. Thus we still lack clear insight into how to set change costs when planning in a rolling horizon environment with capacity constraints.

The approach of introducing release change costs in the objective function is equivalent to period-based freezing (Carlson et al. 1979; Kropp et al. 1983; Kropp and Carlson 1984; Blackburn et al. 1985, 1986; Lin et al. 1994; Voss and Woodruff 2006; Braun and Schwartz 2012) by setting the change costs to infinity for the frozen periods, and zero for the periods in the future where changes are permitted. However, this limiting case does not assist us in setting appropriate values for change costs. The costs of planned changes are hard to determine in practice, since they are driven by the changes to planned activities that must be made due to changes in production plans. Lin et al. (1994) set arbitrary unit change costs and found that the length of the frozen periods increases as the unit change cost increases. Hence it is useful to identify the minimum value of the change cost in a particular period that will ensure that the schedule will be frozen in that period. If an accurate estimate of this value could be computed, management could compare this estimate with their knowledge of the system and the potential impacts of planned changes to assess whether the decision to freeze the plan is justified.

In the next Sect. 2.3, we will begin our analysis of the release change cost LP model with fixed lead time to provide comprehensive analysis of how to set unit release change costs to guarantee freezing the schedule in the current epoch.

2.3 Release Change Cost Model with Fixed Capacity

In this section, we present the mathematical model of a single-product single-stage production system with a finite planning window.

2.3.1 Single-Product Model

In this section, we consider a single-stage single-item production system with a deterministic production lead time of L periods and a capacity of C units per planning period. We introduce unit release change costs to the model motivated by Voss and Woodruff (2006) using the following notation:

Indices:

s::

planning epoch $s = 1,\ldots,K - T + 1$; also indicates the first period of a planning epoch.

t::

a planned period within the planning window from s to $s + T - 1$.

Parameters:

T::

planning window length, the number of periods considered in a planning epoch consisting of periods s to $s + T - 1$.

K::

number of planning periods in the entire horizon.

C::

maximum number of units the system can produce in a planning period.

L::

lead time-material released to the system in period t becomes available as finished product in period $t + L - 1$.

D _t (s)::

demand forecast made at the start of epoch s for period t, $s \leq t \leq s + T - 1$.

ω _t ::

unit WIP holding cost.

$\varphi _{t}$::

unit FGI holding cost.

π _t ::

unit backlog cost.

γ _t ::

unit release change cost.

$R_{t}^{'}(s - 1)$::

release quantity planned for period t in planning epoch s − 1, which is outside the current planning epoch s. These values correspond to planned quantities from the previous decision epoch s − 1, and hence are known with certainty at the start of the current planning epoch s.

$\overline{R_{t}(s)}$::

release quantity already implemented for period $t = s - L + 1,\ldots,s - 1$. These are deterministic parameters that must be considered due to the presence of the fixed lead time L.

U::

estimated demand for all periods outside the current planning window, corresponding to the estimated mean of future demand.

Primal Decision Variables:

R _t (s)::

release quantity planned in epoch s for period t, $s \leq t \leq s + T - 1$.

W _t (s)::

WIP level planned in epoch s for period t, $s \leq t \leq s + T - 1$.

X _t (s)::

production quantity planned in epoch s for period t, $s \leq t \leq s + T - 1$.

I _t (s)::

FGI planned in epoch s for period t, $s \leq t \leq s + T - 1$.

B _t (s)::

backlog planned in epoch s for period t, $s \leq t \leq s + T - 1$.

△R _t (s − 1, s)::

planned release change for period t between the consecutive epochs s − 1 and s, $\bigtriangleup R_{t}(s - 1,s) = R_{t}(s) - R_{t}^{'}(s - 1)$.

Using this notation we can formulate the single-product planning model solved at each epoch of the rolling horizon procedure as follows:

2.3.2 Mathematical Model

Objective:

$$\displaystyle{ \text{ Minimize} = \left \{\sum _{t=s}^{s+T-1}\left [\omega _{ t}W_{t}(s) +\varphi _{t}I_{t}(s) +\pi _{t}B_{t}(s)\right ] +\sum _{ t=s}^{s+T-2}\gamma _{ t}\left \vert \bigtriangleup R_{t}(s - 1,s)\right \vert \right \}. }$$

Constraints:

$$\displaystyle\begin{array}{rcl} & & R_{s+T-\tau }(s) \geq U,\,\forall \,\tau \in (1,L). {}\\ & & W_{t}(s) =\sum _{ \tau =0}^{L-1}R_{ t-\tau }(s),\,\forall \,t \in (s,s + T - 1). {}\\ & & I_{t}(s) - B_{t}(s) = I_{t-1}(s) - B_{t-1}(s) + X_{t}(s) - D_{t}(s),\,\forall \,t \in (s,s + T - 1). {}\\ & & X_{t}(s) \leq C,\,\forall \,t \in (s,s + T - 1). {}\\ & & X_{t}(s) = R_{t-L}(s),\,\forall \,t \in (s,s + T - 1). {}\\ & & \bigtriangleup R_{t}(s - 1,s) = R_{t}(s) - R_{t}^{'}(s - 1),\,\forall \,t \in (s,s + T - 1). {}\\ & & X_{t}(s),\,W_{t}(s),\,R_{t}(s),\,I_{t}(s),\,B_{t}(s) \geq 0,\,\forall \,t \in (s,s + T - 1). {}\\ \end{array}$$

While the WIP costs are usually omitted in planning models with fixed lead times (Missbauer and Uzsoy 2011), we include them in this model because of the role of WIP holding costs in determining release change costs which will emerge from our analysis. In order to analyze the structure of optimal solutions for this model, we first rewrite the release change variable △R _t (s − 1, s), which is free in sign, as the difference of two nonnegative decision variables representing the positive and negative release changes:

$$\displaystyle\begin{array}{rcl} \bigtriangleup R_{t}(s - 1,s)& =& R_{t}(s) - R_{t}^{'}(s - 1) {}\\ & =& \bigtriangleup R_{t}^{+}(s - 1,s) -\bigtriangleup R_{ t}^{-}(s - 1,s). {}\\ \end{array}$$

A positive release change $\bigtriangleup R_{t}^{+}(s - 1,s) = \max \left [R_{t}(s) - R_{t}^{'}(s - 1),0\right ] > 0$ means that the period t release planned in epoch s exceeds that planned in epoch s − 1, so it is necessary to increase the planned release quantity to account for this change. On the other hand, $\bigtriangleup R_{t}^{-}(s - 1,s) =\max \left [R_{t}^{'}(s - 1) - R_{t}(s),0\right ] > 0$ means it was previously planned to release more material in epoch s − 1 than is now needed in epoch s. We assign positive and negative release changes unit costs of $\gamma _{t}^{+}$ and $\gamma _{t}^{-}$, respectively, and rewrite variables X _t (s), I _t (s), and R _t (s), in terms of $\bigtriangleup R_{t}^{+}(s - 1,s)$ and $\bigtriangleup R_{t}^{-}(s - 1,s)$. This straightforward but tedious substitution yields the following primal formulation:

2.3.3 Primal Model

$$\displaystyle\begin{array}{rcl} \text{ Minimize}& =& \sum _{t=s}^{s+T-1}\left [\left (\varphi _{ t} +\pi _{t}\right )B_{t}(s)\right ] +\omega _{s+T-1}W_{s+T-1}(s) {}\\ & & +\sum _{t=s}^{s+T-2}\left \{\bigtriangleup R_{ t}^{+}(s - 1,s)\left [\gamma _{ t}^{+} +\sum _{ \tau =t}^{t+L-1}\omega _{ t} +\sum _{ \tau =t}^{s+T-1}\varphi _{ t}\right ]\right \} {}\\ & & +\sum _{t=s}^{s+T-2}\left \{\bigtriangleup R_{ t}^{-}(s - 1,s)\left [\gamma _{ t}^{-}-\sum _{\tau =t}^{t+L-1}\omega _{ t} -\sum _{\tau =t}^{s+T-1}\varphi _{ t}\right ]\right \} {}\\ \end{array}$$

Primal Constraints:

$$\displaystyle{ R_{s+T-1}(s) \geq U,\,\,\,\,\,\,\,\,\left [\alpha _{s+T-1}(s)\right ]. }$$

(2.1)

$$\displaystyle\begin{array}{rcl} & & \bigtriangleup R_{s+T-t}^{+}(s - 1,s) -\bigtriangleup R_{ s+T-t}^{-}(s - 1,s) \geq U - R_{ s+T-t}^{'}(s - 1) \\ & & \phantom{aaaaaaaa}\forall \,t \in (2,L),\,s \geq 2,\,L \geq 1,\,\,\,\,\,\,\,\,\left [\alpha _{s+T-t}(s)\right ]. {}\end{array}$$

(2.2)

$$\displaystyle\begin{array}{rcl} & & \sum _{\tau =s+L}^{t}\left [\bigtriangleup R_{ s+T-t}^{+}(s - 1,s) -\bigtriangleup R_{ s+T-t}^{-}(s - 1,s)\right ] + B_{ t}(s) \geq V _{t}(s), \\ & & \phantom{aaaaaaa}\forall \,t \in (s,s + T - 1),\,\,\,\,\,\,\,\,\left [\beta _{t}(s)\right ]. {}\end{array}$$

(2.3)

$$\displaystyle\begin{array}{rcl} & & -\bigtriangleup R_{s+T-t}^{+}(s - 1,s) + \bigtriangleup R_{ s+T-t}^{-}(s - 1,s) \geq -C + R_{ t}^{'}(s - 1), \\ & & \qquad \quad \forall \,t \in (s,s + T - 1 - L),\,\,\,\,\,\,\,\,\left [\sigma _{t}(s)\right ]. {}\end{array}$$

(2.4)

$$\displaystyle\begin{array}{rcl} \bigtriangleup R_{s+T-t}^{+}(s - 1,s) -\bigtriangleup R_{ s+T-t}^{-}(s - 1,s)& \geq & -R_{ s+T-t}^{'}(s - 1), \\ & \forall & \,t \in (s,s + T - 2),\,\,\,\,\,\,\,\,\left [\eta _{t}(s)\right ].{}\end{array}$$

(2.5)

$$\displaystyle{ B_{t}(s)\geqslant 0. }$$

(2.6)

$$\displaystyle{ R_{s+T-t}^{+}(s - 1,s),\,R_{ s+T-t}^{-}(s - 1,s) \geq 0,\,\forall \,t \in (s,s + T - 2). }$$

(2.7)

where for brevity of notation we define the constants:

$$\displaystyle{ V _{t}(s) = -I_{s-1}(s) + B_{s-1}(s) +\sum _{ \tau =s}^{t}D_{\tau }(s) -\sum _{\tau =s+L}^{t}R_{\tau -L}^{'}(s) -\sum _{\tau =s}^{s+L-1}R_{\tau -L}(s). }$$

(2.8)

Constraint set (2.4) implies that release changes must be feasible with respect to the residual capacity given by $R_{t}^{'}(s - 1) - C$ in each period t. The dual variables associated with each constraint set are denoted by the Greek letters in square brackets to the right of the constraints.

2.3.4 Dual Model

The dual of this model is as follows:

$$\displaystyle\begin{array}{rcl} \text{ Maximize}& =& U\alpha _{s+T-1}(s) +\sum _{ t=2}^{L}\alpha _{ s+T-t}(s)\left [U - R_{s+T-t}^{'}(s - 1)\right ] {}\\ & & +\sum _{t=s}^{s+L-1}\left \{\beta _{ t}(s)\left [-I_{s-1}(s) + B_{s-1}(s) +\sum _{ \tau =s}^{t}D_{\tau }(s) +\sum _{ \tau =s}^{t}R_{\tau -L}(s)\right ]\right \} {}\\ & & +\sum _{t=s}^{s+T-1}V _{ t}(s)\beta _{t}(s) +\sum _{ t=s}^{s+T-1-L}\sigma _{ t}(s)\left [-C + R_{t}^{'}(s - 1)\right ] {}\\ & & \quad \! -\sum _{t=s}^{s+T-2}R_{ t}^{'}(s - 1)\eta _{ t}(s). {}\\ \end{array}$$

Dual Constraints:

$$\displaystyle{ \alpha _{s+T-1}(s) \leq \omega _{s+T-1},\,\forall \,t \in (s,s + T - 1),\,\,\,\,\,\,\,\,\left [R_{s+T-1}(s)\right ]. }$$

(2.9)

$$\displaystyle{ \beta _{t}(s) \leq \varphi _{t} +\pi _{t},\,\forall \,t \in (s,s + T - 1 - L),\,\,\,\,\,\,\,\,\left [B_{t}(s)\right ]. }$$

(2.10)

$$\displaystyle\begin{array}{rcl} -\sigma _{t}(s) +\eta _{t}(s)& +& \sum _{\tau =t+L}^{s+T-1}\beta _{ \tau }(s) \leq Q_{t}^{+}(s), \\ & & \forall \,t \in (s + T - 1,s + T - 2),\,\,\,\,\,\,\,\,\left [\bigtriangleup R_{s+T-t}^{+}(s - 1,s)\right ].{}\end{array}$$

(2.11)

$$\displaystyle\begin{array}{rcl} \eta _{t}(s) +\alpha _{t}(s)& \leq & \gamma _{t}^{+} +\sum _{ \tau =t}^{t+L-1}\omega _{ \tau }, \\ & \forall & \,t \in (s,s + T - 1 - L),\,\,\,\,\,\,\,\,\left [\bigtriangleup R_{s+T-t}^{+}(s - 1,s)\right ].{}\end{array}$$

(2.12)

$$\displaystyle\begin{array}{rcl} \sigma _{t}(s) -\eta _{t}(s)& -& \sum _{\tau =t+L}^{s+T-1}\beta _{ \tau }(s) \leq Q_{t}^{-}(s), \\ & & \,\forall \,t \in (s + T - 1,s + T - 2),\,\,\,\,\,\,\,\,\left [\bigtriangleup R_{s+T-t}^{-}(s - 1,s)\right ].{}\end{array}$$

(2.13)

$$\displaystyle\begin{array}{rcl} -\eta _{t}(s) -\alpha _{t}(s)& \leq & \gamma _{t}^{-}-\sum _{\tau =t}^{t+L-1}\omega _{ \tau }, \\ & \forall & \,t \in (s,s + T - 1 - L),\,\,\,\,\,\,\,\,\left [\bigtriangleup R_{s+T-t}^{-}(s - 1,s)\right ].{}\end{array}$$

(2.14)

$$\displaystyle{ \alpha _{t}(s),\,\beta _{t}(s) \geq 0,\,\forall \,t \in (s,s + T - 1). }$$

(2.15)

$$\displaystyle{ \sigma _{t}(s),\,\eta _{t}(s) \geq 0,\,\forall \,t \in (s,s + T - 2). }$$

(2.16)

For constraint sets (2.12) and (2.14), we define the constants:

$$\displaystyle{ Q_{t}^{+}(s) =\gamma _{ t}^{-} +\sum _{ \tau =t}^{t+L-1}\omega _{ \tau } +\sum _{ \tau =t}^{t+L-1}\varphi _{ \tau },\,\forall \,t \in (s,s + T - 1 - L). }$$

and

$$\displaystyle{ Q_{t}^{-}(s) =\gamma _{ t}^{-}-\sum _{\tau =t}^{t+L-1}\omega _{ \tau } -\sum _{\tau =t}^{t+L-1}\varphi _{ \tau },\,\forall \,t \in (s,s + T - 1 - L) }$$

Before we start to analyze release changes, we will briefly discuss some of the primal and dual constraints. Let us begin from constraint (2.3). When

$$\displaystyle{ I_{t}(s) = B_{t}(s) +\sum _{ \tau =s+L}^{t}\left [\bigtriangleup R_{ t}^{+}(s - 1,s) -\bigtriangleup R_{ t}^{-}(s - 1,s)\right ] - V _{ t}(s) > 0. }$$

the system has positive FGI, implying β _t (s) = 0. In addition, at most one of $\bigtriangleup R_{t}^{+}(s - 1,s)$ and $\bigtriangleup R_{t}^{-}(s - 1,s)$ can be positive in a given period since their associated columns in the constraint matrix are linearly dependent. In the capacity constraint (2.4) $-\bigtriangleup R_{t}^{+}(s - 1,s) + \bigtriangleup R_{t}^{-}(s - 1,s) > -C + R_{t}^{'}(s - 1)$ implies that the planned release changes are not constrained by capacity, and hence the associated dual variable $\sigma _{t}(s) = 0$. When $\bigtriangleup R_{t}^{+}(s - 1,s) > 0$, we must have $\bigtriangleup R_{t}^{+}(s - 1,s) > -R_{t}^{'}(s - 1)$ implying η _t (s) = 0 from (2.5). For negative changes, we cannot reduce the planned release quantity by more than $R_{t}^{'}(s - 1)$ units due to the nonnegativity of release changes. Hence, $\bigtriangleup R_{t}^{-}(s - 1,s) < R_{t}^{'}(s - 1)$ also implies η _t (s) = 0, unless demand is zero. $\bigtriangleup R_{t}^{+}(s - 1,s) > 0$ also indicates $-\sigma _{t}(s) +\eta _{(}s) +\sum _{ \tau =t+L}^{s+T-1}\beta _{\tau }(s) = Q_{t}^{+}(s)$ by constraint (2.11). $\bigtriangleup R_{t}^{-}(s - 1,s) > 0$ implies $\sigma _{t}(s) -\eta _{(}s) -\sum _{\tau =t+L}^{s+T-1}\beta _{\tau }(s) = Q_{t}^{-}(s)$ by constraint (2.13). If the backlog variable B _t (s) > 0, then $\beta _{t}(s) =\varphi _{t} +\pi _{t}$ by constraint (2.10). These relationships will be used in the following sections to develop bounds on the values of the change costs that will guarantee freezing of schedules by eliminating planned release changes in a given period. Specifically, we seek the values of the unit change costs for each period that result in optimal values of zero for the planned release changes in that period.

In the next Sect. 2.3.5, we describe our implementation of freezing the schedule in the rolling horizon environment. In Sect. 2.4, we examine the behavior of release changes in a planning epoch followed by some insights into the effects of unit release change costs on the behavior of release changes from one epoch to the next. We then derive the change costs that can freeze the schedule in Sect. 2.5.

2.3.5 Examples of Freezing the Schedules

Freezing the schedule in a particular planning epoch s for a specific number of periods T such that $t = s,\ldots,s + T - 1$ means eliminating all planned release changes in these periods, causing all release change variables for those periods to take a value of zero. We seek the values of the unit change costs for each period that will result in optimal values of zero for the planned release changes in each period. We shall assume that if a given period s + k is frozen, all periods $s,s + 1,\ldots,s + k - 1$ prior to it in the planning window must also be frozen.

Figure 2.2 shows an example of freezing the schedule of release plans for the third period s + 2 in epoch s in a T = 7 period planning window with a fixed lead time of L = 1 period. With a lead time of one period, we must release work in period s + 2 to meet demand in period s + 3. The orange colored cells labelled (L) indicate the period with fixed pre-release based on future demand outside the planning window. This period cannot be frozen because its releases must be planned based on demand information outside the current planning window. The red cells labelled (F) indicate the periods we decide to freeze. For example, as Fig. 2.2a shows, when we freeze the release plan in period s + 2 in epoch s, we also need to freeze periods s and s + 1 prior to it which are labelled (E). In the next epoch s + 1 as shown in Fig. 2.2b, we will freeze period s + 3 and all periods prior to it in the current planning epoch.

Fig. 2.2

Example of freezing the schedule

2.4 Behavior of Positive and Negative Release Changes

In this section, we analyze the causes of release changes and how they affect the production system. We begin our analysis by assuming that the only source of variability from one planning epoch s to the next epoch s + 1 is the newly revealed demand information in the last period $s + T - 1$ of each epoch. This assumption implies that once the demand in a period is observed, it does not change. While this assumption is often not realistic—demand forecasts for a future period can usually be updated until the demand is realized—this simplified approach allows us to gain insight from the study of a simpler problem. Later in this section we relax this assumption, allowing demand changes at all periods within the current planning window.

It is intuitive that a sufficiently high unit release change cost should completely eliminate all release changes; a release cost of infinity corresponds to a constraint setting all planned release changes to zero. Setting the unit cost of positive release changes higher than the backlog cost will drive the primal model presented in Sect. 2.3 to hold backlogs instead of modifying releases. Negative release changes, on the other hand, may be eliminated by adjusting the associated change costs relative to the unit FGI and WIP holding costs, causing the model to hold inventory instead of reducing releases. Thus, positive release change costs should take backlog cost into consideration, while negative release costs ought to be driven by the cost of holding FGI. Both positive and negative change costs should be related to the lead time and the timing of changes.

When producing with a lead time of L periods in a rolling horizon environment, we need to impose an ending condition on releases for future demand outside the current planning window in order to prevent the model from setting releases to zero and eliminating all production in periods beyond the current window. For there to be no release changes at all, the newly revealed demand $D_{s+T-1}(s)$ must be satisfied by the release quantities planned in the previous epoch. Thus, two general causes, excess demand and excess pre-release, lead to release changes as discussed in the subsequent sub-sections.

2.4.1 Excess Demand

If $D_{s+T-1} > R_{s+T-1-L}^{'}(s - 1)$ a positive release change is necessary for the new demand to be met without backlogging, increasing the total amount of material released in the planning window over that already planned for that period in the previous epoch s − 1. In this case we have the following three scenarios based on constraint (2.4) with residual capacity:

• $D_{s+T-1}(s) - R_{s+T-1-L}^{'}(s - 1) \leq \sum _{t=s}^{s+T-1-L}\left [C - R_{t}^{'}(s - 1)\right ]$

In this case the excess demand is less than the cumulative residual capacity, so the positive release change required to meet the excess demand is feasible and given by:

$$\displaystyle{ \sum _{t=s}^{s+T-1-L}\bigtriangleup R_{ t}^{+}(s - 1,s) = D_{ s+T-1}(s) - R_{s+T-1-L}^{'}(s - 1). }$$

(2.17)

Equation (2.17) implies, as expected, that excess demand in period $s + T - 1$ may require positive planned release changes in period s to $s + T - 1 - L$ to satisfy the excess demand. This is because the excess capacity in period $s + T - 1$ may not be sufficient for the necessary release changes, requiring us to release material earlier and hold it in FGI until period $s + T - 1$.

• $D_{s+T-1}(s) - R_{s+T-1-L}^{'}(s - 1) >\sum _{ t=s}^{s+T-1-L}\left [C - R_{t}^{'}(s - 1)\right ] = 0$

In this case, there is no residual capacity available to produce any of the additional demand, all of which must be backlogged, yielding:

$$\displaystyle{ B_{s+T-1}(s) = D_{s+T-1}(s) - R_{s+T-1-L}^{'}(s - 1). }$$

(2.18)

• $D_{s+T-1}(s) - R_{s+T-1-L}^{'}(s - 1) >\sum _{ t=s}^{s+T-1-L}\left [C - R_{t}^{'}(s - 1)\right ] > 0$

In this situation, the maximum amount of the incremental demand that can be accommodated with positive release changes is:

$$\displaystyle{ \sum _{t=s}^{s+T-1-L}\bigtriangleup R_{ t}^{+}(s - 1,s) =\sum _{ t=s}^{s+T-1-L}\left [C - R_{ t}^{'}(s - 1)\right ], }$$

(2.19)

and the remainder must be backlogged. However, the entire amount given by (2.19) need not necessarily be released; the model may decide to backlog some of this material if the cost of positive release changes is sufficiently high. In this case the backlogs will be at least:

$$\displaystyle{ B_{s+T-1}(s) \geq D_{s+T-1}(s) - R_{s+T-1-L}^{'}(s) -\sum _{ t=s}^{s+T-1-L}\left [C - R_{ t}^{'}(s - 1)\right ]. }$$

(2.20)

2.4.2 Excess Pre-release

$D_{s+T-1}(s) < R_{s+T-1-L}^{'}(s)$ implies that we planned to release more material in the previous planning epoch than the new demand requires; our initial estimate U of the demand in period $s + T - 1$ has been revised down to a lower number. The optimal plan for epoch s will potentially have a negative release change in order not to carry unnecessary WIP and hold extra FGI. With an appropriately specified negative release change cost, the model will reduce releases only in period $s + T - 1 - L$ by the amount:

$$\displaystyle{ \bigtriangleup R_{t}^{-}(s - 1,s) = \max \left [R_{ s+T-1-L}^{'} - D_{ s+T-1}(s),0\right ] > 0. }$$

(2.21)

In conclusion, the causes of positive and negative changes are different. Without positive release changes to satisfy excess demand, we will have backlogs, while without negative release changes to eliminate unnecessary material from the system, we will need to hold unnecessary inventory at additional cost. Thus, we should treat positive and negative changes in different ways, suggesting that they need to be assigned different unit change costs. When the only source of demand variability is the new demand information in the final period $s + T - 1$ of the current epoch, we will only have negative changes in period $s + T - 1 - L$,since demand is not updated in periods earlier than period $s + T - 1$. However, a high demand observation in the final period $s + T - 1$ may cause positive release changes throughout the current planning window.

However, it is still not clear how to set change costs to guarantee freezing of the schedule in specific periods. In addition, planning in a rolling horizon environment complicates the cost settings: any decision in one epoch affects not just the current epoch, but potentially also those in later epochs. Hence we seek a lower bound on the values of change costs that guarantee freezing of the schedule in the current epoch. However, these results are valid only for decisions made in the current epoch. It remains possible that new demand information in some future epoch will call for positive or negative release changes, even with the costs we specify. We will begin with an analysis of negative release change costs, and then examine positive release change costs.

From this point onward, we relax the assumption that the only source of potential release changes is the new demand information in the end of each epoch; we will allow updated demand forecasts for each period in each epoch.

2.5 Release Change Costs for a Single Product

In this section, we present the analysis for positive and negative release changes from the last period $s + T - 1 - L$ of epoch s backward to its first period s.

2.5.1 Negative Release Change Costs

• Freezing Period s+T-1-L When Excess Pre-release occurs in Epoch s

When there is excess pre-release in period $s + T - 1$, we will only have negative release changes in period $s + T - 1 - L$. A high enough negative release change cost that makes negative release changes unattractive results in $\bigtriangleup R_{s+T-1-L}^{-}(s - 1,s) = 0$ so that constraint (2.13) takes the form:

$$\displaystyle{ \sigma _{s+T-1-L}(s) -\eta _{s+T-1-L}(s) -\beta _{s+T-1-L}(s) \leq \gamma _{s+T-1-L}^{-}- L\omega -\varphi. }$$

(2.22)

Since we are considering a negative release change in a single-product model, the capacity constraint (2.4) in period $s + T - 1 - L$ is not binding, so $\sigma _{s+T-1-L}(s) = 0$. In order to derive a lower bound on the negative change cost that will result in zero negative changes at optimality, we note that the maximum value of $-\eta _{s+T-1-L}(s)$ is zero. $\bigtriangleup R_{s+T-1-L}^{-}(s - 1,s) = 0$ in an optimal solution means carrying the excess pre-release as FGI, implying $I_{s+T-1-L}(s) > 0$. The complementary slackness condition applied to constraint (2.3) gives $\beta _{s+T-1-L}(s) = 0$. Thus the negative release change cost to guarantee freezing period $s + T - 1 - L$ in epoch s must satisfy:

$$\displaystyle{ \gamma _{s+T-1-L}^{-}\geq L\omega +\varphi. }$$

(2.23)

Note, however, that freezing the schedule in period $s + T - 1 - L$ in epoch s will create an excess pre-release in period $s + T - 1$ in epoch s + 1, impacting decisions in the next epoch s + 1.

We now consider the negative change costs required to freeze the schedule in period $s + T - 2 - L$ in epoch s, given updated demand information in period $s + T - 2$ only.

• Freezing Period s+T-2-L When Excess Pre-release occurs in Epoch s

In order to eliminate negative changes in period $s + T - 2 - L$ due to excess pre-release in period $s + T - 2$ in epoch s, the worst case situation is to carry all the excess pre-release as FGI for both periods $s + T - 2$ and $s + T - 1$. When $\bigtriangleup R_{s+T-2-L}^{-}$ $(s - 1,s) = 0$ at optimality the complementary slackness condition for (2.13) yields:

$$\displaystyle\begin{array}{rcl} & & \sigma _{s+T-2-L}(s) -\eta _{s+T-2-L}(s) -\sum _{\tau =s+T-2}^{s+T-1}\beta _{ \tau }(s) \\ & & \quad \leq \gamma _{s+T-2-L}^{-}- L\omega -\sum _{\tau =s+T-2}^{s+T-1}\varphi. {}\end{array}$$

(2.24)

Since the capacity constraints are not binding in period $s + T - 2 - L$ and we wish to have zero negative release change in the optimal solution, we must have $\sigma _{s+T-2-L}(s) = 0$ by constraint (2.4). We set $-\eta _{s+T-2-L}(s) = 0$ to obtain a lower bound on the negative change cost. Freezing excess pre-releases results in positive FGI $I_{s+T-2}(s) > 0$, implying $\beta _{s+T-2}(s) = 0$ by (2.3) and thus:

$$\displaystyle{ \gamma _{s+T-2-L}^{-}\geq L\omega + 2\varphi -\beta _{ s+T-1}(s). }$$

(2.25)

Freezing excess pre-releases in period $s + T - 2 - L$ may affect the decision in period $s + T - 1 - L$ under the following two conditions:

• 1. $I_{s+T-1}(s) = 0$: $\beta _{s+T-1}(s) = L\omega +\varphi$

• 2. $I_{s+T-1}(s) > 0$: $\beta _{s+T-1}(s) = 0$

If eliminating negative release changes in period $s + T - 2 - L$ will not require holding FGI in period $s + T - 1 - L$ from (2.25) we obtain:

$$\displaystyle{ \gamma _{s+T-2-L}^{-}\geq \varphi. }$$

(2.26)

On the other hand, if the freezing period $s + T - 2 - L$ requires holding FGI in period $s + T - 1$, we need higher negative change costs to freeze the schedule in period $s + T - 2 - L$, since the change cost must offset the additional cost of carrying the excess material for an additional period in period $s + T - 1 - L$, yielding:

$$\displaystyle{ \gamma _{s+T-2-L}^{-}\geq L\omega + 2\varphi. }$$

(2.27)

This is a lower bound on the negative release change cost required to guarantee freezing of the schedule under all circumstances. The approach can be applied to periods $s + T - 3 - L,\ldots,s$. We summarize the minimum unit negative release change costs required to freeze the schedule in each period of an epoch s in Table 2.1. In Table 2.1 “Worst-Case Periods” indicates the maximum number of periods for which FGI must be carried if negative release changes are eliminated in this period.

Table 2.1 Negative release change costs required to freeze the schedule

We emphasize once again that to guarantee elimination of negative changes in the current epoch under all circumstances, we need to set the change cost to at least the lower bound specified in Table 2.2. Recall also that these lower bounds only guarantee the freezing of the schedule in the current epoch, not that there will be no release changes in the specified period in any future epoch.

Table 2.2 Negative release change costs guaranteeing freezing of plan

2.5.2 Positive Release Change Costs

When updated demand forecast information reveals increased demand, we need to use available residual capacity within the current planning window consisting of periods $s,\ldots,s + T - 1 - L$ to satisfy unmet demand and reduce backlogging. In a T period planning window with a lead time of L periods, it is quite possible to have positive changes in all T − L periods because of unmet excess demand. We will begin the analysis from period $s + T - 1$ with excess demand in epoch s first. We will then extend the analysis to the rest of the periods in epoch s.

• Freezing Period s+T-1-L When Excess Demand Occurs in Period s+T-1

When there is excess demand in period $s + T - 1$, we may have positive release changes in all periods from period s to period $s + T - 1 - L$ depending on the availability of residual capacity in these periods. If there is no capacity available in period $s + T - 1 - L$, there will never be a positive release change for that period in an optimal solution. If there is residual capacity in that period, freezing period $s + T - 1 - L$ in epoch s implies $\bigtriangleup R_{s+T-1-L}^{+}(s - 1,s) = 0$ and $B_{s+T-1}(s) > 0$, which in turn implies $\beta _{s+T-1}(s) =\pi +\varphi$ by (2.10). Applying the complementary slackness condition to constraint (2.12), we obtain:

$$\displaystyle{ -\sigma _{s+T-1-L}(s) +\eta _{s+T-1-L}(s) +\beta _{s+T-1}(s) \leq \gamma _{s+T-1-L}^{+} + L\omega +\varphi. }$$

(2.28)

Since we freeze the positive changes for period $s + T - 1 - L$, the capacity constraint (2.4) is not binding, implying $\sigma _{s+T-1-L}(s) = 0$. Freezing the positive changes also makes constraint (2.5) not binding so that $\eta _{s+T-1-L}(s) = 0$ since $0 > -R_{s+T-1-L}^{'}(s)$. Based on these, we obtain a lower bound on the positive release change cost required to freeze positive changes in period $s + T - 1 - L$ as:

$$\displaystyle{ \gamma _{s+T-1-L}^{+} \geq \pi -L\omega. }$$

(2.29)

• Freezing Period s+T-2-L When Excess Demand Occurs in Period s+T-2

A positive release change in period $s + T - 2 - L$ may stem from excess demand in period $s + T - 1$, in period $s + T - 2$, or both. When we decide to eliminate positive release changes in period $s + T - 2 - L$, in the worst case we will cause two periods of backlogging in periods $s + T - 2$ and $s + T - 1$. Since freezing period $s + T - 2 - L$ in epoch s assumes there is residual capacity in that period, we have $\bigtriangleup R_{s+T-2-L}^{+}(s - 1,s) = 0$ and $B_{s+T-2}(s) > 0$, which implies:

$$\displaystyle\begin{array}{rcl} & & -\sigma _{s+T-2-L}(s) +\eta _{s+T-2-L}(s) +\beta _{s+T-2}(s) +\beta _{s+T-1}(s) \\ & & \quad \leq \gamma _{s+T-2-L}^{+} + L\omega + 2\varphi {}\end{array}$$

(2.30)

and $\beta _{s+T-2}(s) =\pi +\varphi$ by constraints (2.12) and (2.10). When freezing the schedule causes constraints (2.4) and (2.5) not to be binding, $\sigma _{s+T-2-L}(s) =\eta _{s+T-2-L}(s) = 0$. The positive release change cost to freeze period $s + T - 2 - L$ due to excess demand in period $s + T - 2$ in epoch s is obtained as:

$$\displaystyle{ \gamma _{s+T-2-L}^{+} \geq \pi -L\omega -\varphi +\beta _{ s+T-1}(s). }$$

(2.31)

If freezing changes in period $s + T - 2 - L$ causes backlogging in period $s + T - 1$, then $\beta _{s+T-1}(s) =\pi +\varphi$ by (2.10) so that:

$$\displaystyle{ \gamma _{s+T-2-L}^{+} \geq 2\pi - L\omega. }$$

(2.32)

If freezing changes in period $s + T - 2 - L$ does not cause backlogging and FGI in period $s + T - 1$, then $\beta _{s+T-1}(s) = L\omega +\varphi$ yielding:

$$\displaystyle{ \gamma _{s+T-2-L}^{+} \geq \pi. }$$

(2.33)

If we want to guarantee freezing period $s + T - 2 - L$ in an epoch s, we need to set the positive change cost to at least 2π − L ω. The results of the same procedure applied to the rest of the analysis to eliminate positive release changes are summarized in Table 2.3. The “Worse-Case Periods” in Table 2.3 represents the maximum number of periods for which backlogs must be carried. For example, if we decide to freeze period s in epoch s, it may cause backlogging in up to T − L periods. From Table 2.3, we observe that setting positive release change cost to eliminate positive release change in period t in epoch s must consider how freezing affects the future periods within the current planning epoch. The costs to guarantee elimination of positive changes for each period are summarized in Table 2.4. However, recall also that these lower bounds on the positive release change cost only guarantee the freezing of the schedule in the current epoch, and do not guarantee that there will be no release changes in a specified period in future epochs.

Table 2.3 Positive release change costs to freeze the schedule

Table 2.4 Positive release change costs guaranteeing to freeze the schedule

2.5.3 Freezing Costs Inside an Epoch or Across Epochs

In the previous two sub-sections, we have shown how to set positive and negative release change costs to guarantee freezing the schedule for a given period in a specific planning epoch s. For example, if we choose to freeze the schedule in period s + 2 with T = 6 planning periods in epoch s as Fig. 2.3a shown, we not only need to freeze period s + 2 but also all periods preceding it in the epoch s. This means we need to freeze the three periods from period s to s + 2 in each epoch s.

Fig. 2.3

An example of freezing the schedule across epochs

If we decide to freeze period s + 2 in epoch s in an environment with lead time of L = 1 period, we can use Tables 2.2 and 2.4 to set the change costs for period s + 2 in epoch s as:

$$\displaystyle{ \gamma _{s+2}^{+}(s) \geq 3\pi -\omega }$$

(2.34)

and

$$\displaystyle{ \gamma _{s+2}^{-}(s) \geq 3\varphi +\omega. }$$

(2.35)

In the next epoch s + 1 as shown in Fig. 2.3b, we also need to freeze the three periods s + 1, s + 2, and s + 3. How can we set the change cost for period s + 2 in epoch s + 1? Based on Tables 2.2 and 2.4, we need to set the change cost for period s + 2 in epoch s + 1 as:

$$\displaystyle{ \gamma _{s+2}^{+}(s + 1) \geq 4\pi -\omega }$$

(2.36)

and

$$\displaystyle{ \gamma _{s+2}^{-}(s + 1) \geq 4\varphi +\omega. }$$

(2.37)

From (2.36) and (2.37), the associated positive and negative changes costs for period s + 2 in epoch s + 1 are higher than (2.34) and (2.35). This is because in a rolling horizon environment, we truncate the planning problem by considering information only within the current planning window of T periods. Thus, we will obtain lower change costs to guarantee freezing period s + 2 in epoch s since we ignore the impact of release changes in the current epoch on periods outside the current planning window. If we extend the planning window length to T = 7 periods with L = 1 period in an epoch as shown in Fig. 2.3c, we still can use Tables 2.2 and 2.4 to set the change costs to freeze period s + 2 in epoch s. Since we have one more period s + 6 in epoch s, the associated change costs to freeze period s + 2 are now:

$$\displaystyle{ \gamma _{s+2}^{+}(s) \geq 4\pi -\omega }$$

(2.38)

and

$$\displaystyle{ \gamma _{s+2}^{-}(s) \geq 4\varphi +\omega. }$$

(2.39)

The change costs to freeze period s + 2 in this condition are equal to those in a six period example in epoch s + 1. In summary, the freezing decision affects not only planning periods in the current epoch but also future periods as yet outside the current planning window. However, we cannot assess the impact of freezing decisions on periods currently outside the planning window until we know their demand information.

2.6 Numerical Examples

In this section, we present numerical examples for the single-product model with fixed lead time and capacity analyzed in the previous sections.

2.6.1 Settings and Assumptions

We assume that the length of the planning window in a planning epoch is T = 6 periods. The overall planning period is 400 periods, giving 395 planning epochs. The overall capacity for each period is 70 units. For each planning epoch, we allow updated demand forecast for all periods. We also assume the demand is normally distributed with mean of 60 units and standard deviation of 27 units, implying an average capacity utilization of 0.86. We generate the demand by using Arena Input Analyzer without allowing negative values. The lead time is L = 2 periods and producing one unit of output requires one unit of capacity. The associated cost values are shown in Table 2.5.

Table 2.5 Costs of single-product model

In this section we want to confirm that the derived lower bounds on the release change costs can guarantee freezing of the schedule under all circumstances. In our example in any epoch s, periods s, …, s + 3 may have release changes so that we can define the overall positive changes in any period s as:

$$\displaystyle{ \bigtriangleup R_{}^{+}(s) =\sum _{ s}\bigtriangleup R_{s}^{+}(s - 1,s),\forall s \in (1,K - T + 1). }$$

(2.40)

If we want to measure all positive release changes in any period s + 3 in any epoch s, the latest period in which release changes can take place, we can define as:

$$\displaystyle{ \bigtriangleup R_{}^{+}(s + 3) =\sum _{ s}\bigtriangleup R_{s+3}^{+}(s - 1,s),\forall s \in (1,K - T + 1). }$$

(2.41)

Similar expressions can be defined to compute the analogous quantities for negative release changes.

2.6.2 Examples of Setting Release Change Costs

Since we have a common lead time of L = 2 periods, we may have release changes in periods s through s + 3 in epoch s. Thus, from Tables 2.4 and 2.2 we can set the release change costs as shown in Table 2.6. From Table 2.6, positive change cost is significantly higher than negative change cost in each period and freezing earlier periods in an epoch requires higher change costs. For example, if we want to freeze period s + 1 in epoch s, we must set positive and negative change costs to $318 and $48, respectively. In the next epoch s + 1, can we still set the release change costs for period s + 1 in this manner to guarantee freezing? The answer is “No.”

Table 2.6 Release change cost in epoch s

From the analysis in Sect. 2.5.3, we must increase the associated release change costs to guarantee freezing of the schedule in epoch s + 1. Table 2.7 clearly shows how to set the release change costs from epoch s to epoch s + 1. For example, we need to increase both change costs in period s + 1 to $428 and $60, respectively, in contrast to $318 and $48 for this period under the previous planning epoch s. This is because we truncate the infinite horizon planning problem into a sequence of finite horizon problems. In epoch s, period s + 1 does not need to consider the effect of freezing on period s + 4; however, in epoch s + 1, we need to consider the period s + 4 that causes the increase in costs. We also see a similar trend in release change costs on other periods in different planning epochs.

Table 2.7 Release change cost in epoch s + 1

When we extend the planning window length from T = 6 to T = 7 periods, in epoch s, we also need to increase the associated release change costs for periods s to s + 3. Table 2.8 shows the cost settings for planning window lengths of T = 6 to T = 7 periods based on the analysis in Sect. 2.5.3. When we have one more period in an planning epoch, we need to increase the positive and negative release change costs, for example in period s, from $428 and $60 to $538 and $72, respectively.

Table 2.8 Release change cost when T = 7 periods in epoch s

By setting the release change costs slightly higher than the derived release change costs to prevent multiple optimal solutions, we can guarantee elimination of either positive or negative release changes. Figure 2.4 presents the results of release changes when we apply different change costs to freeze different periods in any epoch. Blue bars represent the results of positive release changes and red bars represent the results of negative release changes.

Fig. 2.4

Results of freezing single product

Figure 2.4a shows that when there are no change costs we observe release changes in all periods. When we set the change costs using the derived lower bounds, we can eliminate all release changes in period s, which is shown in Fig. 2.4b. When we want to freeze periods s and s + 1, the derived lower bound for period s + 1 also holds. We find zero release change in period s + 1 as shown in Fig. 2.4c. We also find the same results for guaranteeing elimination of release changes when we set the change costs equal to the derived lower bounds to freeze period s + 2 and s + 3 in Fig. 2.4d, e. Thus, the numerical results confirm that we can freeze the schedule by setting the release change costs to the derived lower bound.

2.7 Conclusion

In this chapter we have analyzed the relation between two different approaches for improving schedule stability, the use of change costs to penalize planned changes and the freezing of the plan in certain periods by prohibiting any planned changes. We formulate the planning problem to be solved at each epoch as a linear program, and analyze the structure of the optimal solutions to derive lower bounds on the values of the unit change costs that will ensure zero release changes. We find that the unit change costs required to ensure freezing in a given period is lower for later periods in the epoch. This is intuitive since any excess inventory and backlogs associated with earlier periods in the epoch will be held longer. We also find that freezing positive release changes require higher unit change costs than freezing negative changes, since the former are driven by backlog costs and the latter by inventory holding costs.

Although the production system we have considered is very simple compared to practical industrial systems, we believe this work provides useful insights. First of all, it allows a rough-cut analysis of the change costs required to ensure schedule freezing, allowing management to assess at least qualitatively, whether they believe the impact of the planned changes will indeed result in costs of this magnitude. The formulation of the planning problem at each epoch in terms of planned changes rather than gross release quantities also provides a basis for further analysis of the problem. Of particular interest is the extension of the analysis in this chapter to systems with multiple products. In this case we conjecture that the unit costs derived in this paper will not be sufficient to eliminate all planned changes, since the change costs must also offset the benefit obtained by reallocating capacity between products as demand information is updated. The analysis applied in this paper is based on the optimality conditions for linear programs, which cannot be applied to problems with setup times that require mixed-integer programming formulations. Nevertheless, the ideas from this work could be applied numerically to obtain estimates of change costs that would freeze schedules in this environment also. Finally, the extension of this approach to multiple stage production systems involving different capacitated resources is also of interest.