Work-in-process clearing in supply chain operationsplanning.

1. Introduction and literature

Supply Chain Operations Planning (SCOP) is the planning, control and coordination of material release and capacity loading decisions in a supply chain such that predefined customer service levels are met at minimal cost (c.f. De Kok and Fransoo (2003)). Solving

the SCOP problem is a complex task, and mathematical programming (MP) models based on linear aggregate capacity constraints form the basis of most commercially available advanced planning software (see Stadtler and Kilger (2000) for an overview of concepts and a review of software for application to advanced planning systems). These models solve a single static instance of a deterministic capacitated problem setting that arises in a rolling schedule context, with the planning horizon being divided into discrete time buckets. The inherent uncertainty in demand and manufacturing operations is dealt with through a combination of periodic updates of the system state, slack in the capacity and safety stocks. Although the rolling schedule method can result in non-optimal solutions, it is extremely relevant to real-life situations. In this study, a hierarchical planning framework for the SCOP problem is presented with the method of rolling schedules being used to fine-tune the hierarchical levels. We consider a two-level decision hierarchy in which orders and raw materials are released to the production units by the top level, and the released orders are scheduled by the bottom level in terms of both their planned lead times and capacity restrictions.

A model of the production process is embedded in each planning and scheduling model. It is a mathematical representation of the set of technologically feasible operations within the production process. However, only a very narrow range of production models have been considered in the context of SCOP. Traditional MP models assume instantaneous production of orders with a fixed time lag from the moment of release, and avoid considering the effect of Work-In-Process (WIP) levels on shop congestion, throughput and accordingly on the actual flow times (e.g., Billington et al. (1983), Shapiro (1993) and the MRP and MRPII formulations in Voss and Woodruff (2003)). Recently, Spitter, Hurkens, De Kok, Negenman and Lenstra (2005) decomposed the production of orders over multiple periods during a fixed planned lead time, assuming no modeled relation between the throughput and the WIP. From queuing theory (Little's law), it is well known that the flow times and throughput levels depend on the loading of the shop floor. It can therefore be argued that the production model used in SCOP should be based on the actual queuing characteristics of the shop floor. This follows a line of reasoning proposed by Karmarkar (1987) and Hopp and Spearman (2000). These studies are based on long-term relationships assuming stationary conditions, and not on explicitly modeling or recognizing the higher-level order release decisions. In this paper, we are particularly interested in the interaction between the timings and sizes of the release decisions and their operational execution on the shop floor, and the consequences of this interaction on the system performance. We concentrate on the consistency of the generated plans with their actual executions. At a higher-level order release planning model the periodic performance of the production process is anticipated in terms of the interaction between the capacity loading, throughput and flow time. This interaction is defined through the concept of the clearing of WIP during each period.

The idea of clearing was first deployed by Graves (1986), and has been more specifically defined in Karmarkar (1989) (see Karmarkar (1993) for an extended discussion). The clearing function relates the workload of the shop floor to the anticipated flow time of the next job to be released. Examples of clearing functions as they are used in the literature are illustrated in Fig. 1. The clearing function of Graves (1986) indicates that the amount produced is a constant proportion of the WIP, Throughput = tan[alpha] x WIP. It is represented by the "Fixed Lead Time" function in Fig. 1. It assumes an infinite nominal capacity and a fixed lead time that is independent of the WIP level. The fixed planned lead time considered in Graves' model is used in a manner so as to smooth the production output per period. This is different from the way that the planned lead times are used in classical materials requirement planning systems, where the variability in the planned order releases is directly carried onto the manufacturer's planned output process. The "Fixed Capacity" function contains the assumption that the output is independent of the WIP level, and is bounded by a rigid nominal capacity (e.g., Billington et al. (1983), Chung and Krajewski (1984) and Voss and Woodruff (2003)). A typical approach is to combine the fixed lead time and fixed capacity functions, with the output being limited by the available WIP up to a certain level, and beyond that level the output is fixed to the nominal production rate, [mu], implying a finite capacity (e.g., Hackman and Leachman (1989), Spitter, De Kok and Dellaert (2005) and Selcuk et al. (2006)). The "Saturating" function implies the dynamic behavior of the throughput due to the congestion effect of increasing WIP in the system. It was derived initially from steady-state queuing constructs (Karmarkar, 1989). The use of saturating clearing functions has been reported by Zapfel and Missbauer (1993) and Missbauer (2002) in the design of efficient workload control systems, by Asmundsson et al. (2003, 2004) in improving mathematical programming techniques for aggregate production planning, and by Hwang and Uzsoy (2005) in developing efficient lot sizing models with setup times. The non-linear concave shape for the clearing of WIP was approximated by Armbruster et al. (2004) and Asmundsson et al. (2006) by fitting the curve to experimental results obtained from simulations of practical manufacturing settings. Independently, Riano (2002) models the cumulative output of a production process in terms of the sum of weighted transformations of the previous inputs to the production process. The transformation function is linear in nature with the weights computed based on an assumed knowledge over the flow time distribution.

[FIGURE 1 OMITTED]

In this study our objective is two-fold. First, we want to provide a hierarchical planning framework for SCOP problems with the concept of clearing being used to plan and control WIP levels in a way that achieves consistent plans in terms of the actual delivery schedule versus the planned schedule. The framework we apply is in line with the one described in Bertrand and Wijngaard (1985). Our study is different from previous studies on clearing functions because we explicitly consider the planned lead time in the model so that the delivery performance of the production orders and its consequences on the inventory costs can be measured effectively. Accordingly, our framework can be extended to model more complex supply chain situations. Separate production units in a supply chain are coordinated by the release of orders and their planned lead times. The level of consistency between the planning and execution of delivery schedules plays an important role in the performance of these systems. To our knowledge there is no literature on this aspect of consistency; some results based on experimental data have already been presented in Asmundsson et al. (2006) on the level of fit between the approximated clearing function and the actual clearing behavior. However, their study was not conducted on a hierarchical planning system with planned lead times. Second, it is not obvious what type of model should form the basis of the clearing function. We develop an alternative approach in which we define the throughput quantity as a random variable with a probability distribution based on the available WIP during a period and the short-term probabilistic behavior of the shop floor. We test the performance of the established clearing functions and the proposed alternative in various settings using the simulation of a single-stage, single-product supply chain.

The outline of this paper is as follows. In Section 2 we describe the production-distribution situation and the hierarchical coordination within the planning system. We model different clearing functions in Section 3. Section 4 presents the experimental setting (where we explicitly specify the shape of each clearing function), the design of experiments and the results of the simulations. Finally in Section 5, we conclude with further research directions.

2. Problem definition and modeling

We consider a manufacturer with uncertainty in its operations and a downstream warehouse that sees a non-stationary stochastic demand for a single product. Unmet demand is satisfied through backorders. The planning and control of the material flow within the manufacturer and between the manufacturer and the warehouse is done in a centralized approach. In doing so, time is aggregated into periods, and the planned lead time is expressed as an integer number of time periods meaning that an order that is released at the start of a time period is expected to be available in the warehouse after a duration equal to its planned lead time. The orders are released in batches and sent to the warehouse in batches, facilitating the need to keep a finished items inventory by the manufacturer. This inventory is denoted by the term finished WIP to differentiate it both from the unfinished products waiting to be processed in the shop (WIP) and the finished products at the warehouse. The order releases are timed to satisfy the forecasted demand with a time lag equal to the planned lead time. Separately, the capacity loading decision, for a given clearing function, is responsible for planning periodic throughput levels large enough that orders can be delivered on time. It is assumed that there is an ample stock of raw materials available to the manufacturer, and the transportation time between the raw material supply point and the manufacturer's production facilities and between the manufacturer and the finished product warehouse are negligible. Therefore, the flow time of an order consists of the waiting time and the batch processing time that elapse at the manufacturer. Thus, the independent time lags for the introduction of the raw materials before production starts and the transportation time of the finished product after production ends are not considered as being part of the planned lead time in this study. These are the main (and in fact the only) components for the planned lead times considered in Billington et al. (1983) and Hackman and Leachman (1989), and we ignore these aspects to concentrate on the analysis of the clearing functions to model the characteristics of the production process.

The planning is done in a periodic-review setting for a certain planning horizon, and at the start of each time period the rolling horizon method is applied to replan the production taking into account the random deviations due to stochastic production and demand processes. Between each consecutive planning operation the following sequence of events occurs: an order is released and scheduled among the previously released orders, and a planned quantity of work is introduced to the manufacturer as WIP at the start of the time period, the actual demand and the throughput are realized, and the finished orders are sent to the warehouse at the end of the time period. The status information of the manufacturer and the warehouse is updated, and given these inputs, replanning is done starting from the next time period.

The overall planning process consists of two hierarchical levels as illustrated in Fig. 2. At the top level of the hierarchy, a multi-period single-product SCOP problem is solved for a predetermined horizon of time periods (possibly the forecast horizon). The objective is to have a desired customer service (demand fill rate in this case) at the minimum material holding cost. For this purpose, a linear programming formulation is used to determine the optimal capacity loading and order release decisions. Based on the WIP level given to the shop at the start of a time period, SCOP anticipates the expected throughput in that period (see Schneeweiss (1995) for a discussion on anticipation functions in hierarchical planning systems), so that the size and completion time of each order can be determined according to a given planned lead time. At this point, for the sake of clarity, one should note that the manufacturer does not face a continuous arrival of work during each period, instead all the WIP planned for a period is made available at the start of the period. Note that this assumption on the release of raw materials is also utilized in Graves (1986).

As an instruction from the top level the release order of the first time period is given to the bottom level for detailed scheduling together with the currently open orders. At the bottom level of the hierarchy, given the planned lead times and the release dates of the orders, a deliver schedule is planned according to a First-Come First-Serve (FCFS) strategy. We provide a decomposition of planning decisions on material flow and capacity from the execution decisions on finalized orders. The key argument for this hierarchical decomposition is that the base level's actual execution generally differs from the planned outcome, which also motivates us to replan through the rolling horizon method. This aspect is ignored in static models which drives the need to adjust the current delivery schedule in response to infeasible capacity requirements, and feed forward to the top level before the next replanning process.

[FIGURE 2 OMITTED]

The circled numbers in Fig. 2 refer to the sequence of information flow in the planning system. Data set (1) refers to the input to the planning system regarding the status of the manufacturer and the warehouse together with the demand forecasts. The bottom level performs a check on the achievable delivery schedules of the open orders, and updates the current schedule if necessary. The updated schedule (given by data set (2)) is fed forward to the top level. Data set (3) refers to the first period's release order, which is then added to the end of the current delivery sequence by the bottom level using to the FCFS strategy. The delivery schedule including the newly released order and the level of WIP to be added to the shop are finalized decisions, and are given to the execution systems such as enterprise resource planning, and manufacturing execution systems within data set (4).

2.1. SCOP formulation

At the SCOP level, operational planning is done in terms of releasing the orders and planning the throughput levels to satisfy the planned order releases on time in such a way that the forecasted demand is met by holding a minimum amount of material both at the manufacturer and at the warehouse. The non-linear clearing functions are approximated by a piecewise-linear representation, as will be outlined in Section 3. The static exogenous parameters of the SCOP model are defined as follows.

[h.sub.f] = Per unit, per period cost of holding finished product inventory at the warehouse.

[h.sub.w] = Per unit, per period cost of holding WIP at the manufacturer.

[^.h.sub.f] = Per unit, per period cost of holding finished WIP at the manufacturer.

M = Per unit, per period cost of inventory shortage below the safety stock. M is set so high that the system always targets a net inventory level at or above the safety stock.

ss = Safety stock, ss [greater than or equal to] 0.

[mu] = Nominal production rate of the manufacturer. It is the maximum of the average periodic throughput level in the long term.

L = Planned order lead time.

[f.sub.n](dot) = The nth linear part of the piecewise-linear concave clearing function, n = 1, 2,..., N.

T = Planning horizon.

The dynamic exogenous inputs to the SCOP model are updated at every replanning opportunity. These constitute the demand forecasts, the status information about the manufacturer and the warehouse, and a capacity feasible delivery schedule from the bottom-level. They are as follows.

D(t, t + s) = Forecasted demand for period t + s as given at the start of period t, s = 0, 1,..., T - 1. We assume forecasts are not subject to change between replanning epochs, D(t, t + s) = D(t + k, t + s), k [less than or equal to] s.

[^.Q](t, t + s) = Total quantity, among the currently open orders, scheduled for receipt at the start of period t + s as given at the start of period t, s = 1, 2,..., L.

[I.sup.+](t, t) = Current on-hand inventory at the warehouse.

[I.sup.-](t, t) = Current backorder level at the warehouse.

W(t, t) = Current WIP at the manufacturer.

[^.W](t, t) = Current finished WIP at the manufacturer.

The decision variables include system variables such as the net inventory level at the warehouse, WIP and the finished WIP levels at the manufacturer and the anticipated throughput quantities for each planning period. The list of variables that are not executed but used in the plan for evaluation and anticipation purposes, as they are recorded at the start of period t, include the following.

[I.sup.+](t, t + s) = Inventory on hand at the warehouse at the start of period t + s, just before the orders scheduled for period t + s are received, s = 1, 2,..., T.

[I.sup.-](t, t + s) = Backorder level at the warehouse at the start of period t + s, just before the orders scheduled for period t + s are received, s = 1, 2,..., T.

[S.sup.+](t, t + s) = The net inventory level over the safety stock at the warehouse at the end of period t + s, s = 0, 1,..., T - 1.

[S.sup.-](t, t + s) = The net inventory level below the safety stock at the warehouse at the end of period t + s, s = 0, 1,..., T - 1.

W(t, t + s) = WIP level at the manufacturer at the start of period t + s, just before the release of additional WIP into the shop, s = 1, 2,..., T - 1.

[^.W](t, t + s) = Finished WIP at the manufacturer at the start of period t + s, just after the order scheduled for period t + s is sent to the warehouse, s = 1, 2,..., T - 1.

P(t, t + s) = Manufacturer's throughput level in period t + s, s = 0, 1,..., T - 2.

The executable decisions are the order release and the capacity loading decisions, which are denoted as follows.

Q(t, t + s) = The size of the order to be released at the start of period t + s, as decided at the start of period t, s = 0, 1,..., T - L - 1.

R(t, t + s) = Capacity loading decisions. It is the amount of additional WIP released to the shop at the start of period t + s, as decided at the start of period t, s = 0, 1,..., T - 2.

The SCOP problem, at the start of period t, is modeled by the following linear programming formulation. It should be noted that all the constants and the variables in this formulation are non-negative. For L > 1, the order release variables Q(t, t + k) for k < 0 are set to zero, because the decisions at time t are limited to future release orders:

min [T.summation over (s=1)]([h.sub.f] x [I.sup.+](t, t + s)) + [T-1.summation over (s=1)]([h.sub.w] x W(t, t + s)) + [^.h.sub.f] x [^.W](t, t + s)) + [T-1.summation over (s=0)]M x [S.sup.-](t, t + s), (1)

subject to

[I.sup.+](t, t + s + 1) - [I.sup.-](t, t + s + 1) = [I.sup.+](t, t + s) - [I.sup.-](t, t + s) + Q(t, t + s - L) + [^.Q](t, t + s) - D(t, t + s), s = 0, 1,..., T - 1, (2)

W(t, t + s + 1) = W(t, t + s) + R(t, t + s) - P(t, t + s), s = 0, 1,..., T - 2, (3)

P(t, t + s) [less than or equal to] [f.sub.n](W(t, t + s) + R(t, t + s)), s = 0, 1,..., T - 2, n = 1, 2,..., N (4)

[^.W](t, t + s + 1) = [^.W](t, t + s) + P(t, t + s) - Q(t, t + s + 1 - L) - [^.Q](t, t + s + 1), s = 0, 1,..., T - 2, (5)

[S.sup.+](t, t + s) - [S.sup.-](t, t + s) = [I.sup.+](t, t + s + 1) - [I.sup.-](t, t + s + 1) - ss, s = 0, 1,..., T - 1. (6)

Constraint set (2) defines the inventory balance at the warehouse between consecutive planning periods using information on the current schedule and assuming that the order released at the start of period k will be available at the warehouse at the start of period k + L. Constraint set (3) determines the WIP balance, with the WIP being increased by the amount of work loaded into the shop and decreased by the throughput. Constraint set (4) provides the throughput and capacity loading relationship according to a piecewise-linear and concave clearing function. The finished WIP balance equations are modeled in constraint set (5), which implies that each order has to be finished and delivered to the warehouse within its planned lead time. Constraint set (6) determines the variables due to the amount of net inventory relative to the safety stock.

If we ignore the finished product inventory holding cost, the shortage cost in the objective function and constraint set (2), the resulting formulation is very similar to the aggregate production planning models presented in Karmarkar (1989), Asmundsson et al. (2003), and Asmundsson et al. (2004), where the term in constraint set (5), Q(t, t + s + 1 - L) + [^.Q](t, t + s + 1), can be considered as an exogenous demand for period t + s, as given at the start of period t.

As the concept of clearing implies, the throughput in a period is a function of the total WIP level at the start of that period. The capacity loading decisions are driven by the desired level of throughput quantities, because, as formulated in constraint set (4), R(t, t + s) determines the range in which P(t, t + s) can be anticipated. It is obvious from the SCOP formulation that the additional WIP introduced into the shop each period increases the total costs. Thus, for a desired throughput level of P(t, t + s) = [min.sub.n=1,2,..., N]{[f.sub.n](W(t, t + s))}, R(t, t + s) is decided such that:

P(t, t + s) = [min.[n=1,2,..., N]]{[f.sub.n](W(t, t + s) + R(t, t + s))}, t = 0, 1,..., T - 2,

and for a desired throughput level of P(t, t + s) [less than or equal to] [min.sub.n=1,2,..., N] {[f.sub.n](W(t, t + s))}, R(t, t + s) = 0. In other words, the SCOP model loads the capacity by the exact quantity that increases the throughput to a desired level, and if the throughput does not need to be increased then no additional WIP is loaded into the shop.

2.2. Scheduling and rescheduling

At the start of the current planning period t, Q(t, t) is released to the scheduling level from the top level. At the scheduling level, decisions regarding the immediate execution of past and current order releases are provided. Thus, the notation changes slightly in this section compared to the notation in the SCOP model. Given the current sequence of open orders {([q.sub.1], [^.dd.sub.1]), ([q.sub.2], [^.dd.sub.2]),..., ([q.sub.k], [^.dd.sub.k])}, as planned by the scheduling level, where the order quantities, the [q.sub.i], are coupled with their planned delivery dates, the [^.dd.sub.i], the newly released order is added to the end of the sequence, ([q.sub.k+1], [^.dd.sub.k+1]) = (Q(t, t), t + L), and the new schedule is sent to the execution systems. In a static framework this is just an implementation of a FCFS dispatching rule. However, in a dynamic framework that includes the plan-execute-(re)plan cycle, due to the stochastic nature of the manufacturing process the actual throughput quantities may deviate from their anticipated values. As a result, there is a need to update the schedules of open orders at each replanning according to the capacity considerations. A feasible delivery schedule has to be input to the top-level SCOP model from the bottom-level scheduling model. A schedule update heuristic is used for this operation.

Given that an arbitrary order is expected to be late, the heuristic finds the earliest period at which the order can be finished and sent to the warehouse. Define the current schedule of the open orders at the warehouse, sent by the execution system to the scheduling level in data set (1) of Fig. 2, by the set [~.X] = {([q.sub.1], [~.dd.sub.1]), ([q.sub.2], [~.dd.sub.2]),..., ([q.sub.k], [~.dd.sub.k])}. Owing to the use the FCFS strategy, [~.dd.sub.1] [less than or equal to] [~.dd.sub.2] [less than or equal to] ... [less than or equal to] [~.dd.sub.k]. For brevity, assign [~.dd.sub.i] = t + 1 if the order ([q.sub.i], [~.dd.sub.i]) is already late at the start of the current period t. An arbitrary order ([q.sub.i], [~.dd.sub.i])[epsilon] [~.X] is expected to be late if and only if

[^.W](t, t) + ([~.dd.sub.i] - t)[mu] - [i-1.summation over (j=1)] [q.sub.j] < [q.sub.i]. (7)

We denote the set of late orders that satisfy condition (7) as [~.X.sub.late]; the new schedule is determined according to the following rule for all ([q.sub.i], [~.dd.sub.i])[member of] [~.X.sub.late]:

[^.dd.sub.i] = [min.[r=0,1,...]]{[~.dd.sub.i] + r : [^.W](t, t) + ([~.dd.sub.i] + r - t)[mu] - [i-1.summation over (j=1)] [q.sub.j] [greater than or equal to] [q.sub.i]}, (8)

where [^.dd.sub.i] is the period at which an order of size [q.sub.i] is scheduled to be received at the warehouse after updating the current schedule. For ([q.sub.i], [~.dd.sub.i])[epsilon] [~.X]\[~.X.sub.late], [^.dd.sub.i] = [~.dd.sub.i]. The new schedule, [^.X] = {([q.sub.1], [^.dd.sub.1]),..., ([q.sub.K], [^.dd.sub.K])}, is then embedded into the SCOP formulation yielding the input:

[^.Q](t, t + s) = [K.summation over (j=1)] 1([^.dd.sub.j] = t + s)[q.sub.j],

where the indicator function 1([^.dd.sub.j] = t + s) has a value of one if [^.dd.sub.j] = t + s, and is zero otherwise. In terms of the fundamental scheduling characteristics, the updated schedule does not conflict with the previous schedule, as outlined in the following proposition:

Proposition 1. The FCFS rule applies for any given pair of consecutive orders in [^.X]. Given ([q.sub.i], [^.dd.sub.i])[epsilon] [^.X] and ([q.sub.i+1], [^.dd.sub.i+1]) [member of] [^.X]:

[^.dd.sub.i] [less than or equal to] [^.dd.sub.i+1],

and the delivery duration does not exceed the planned lead time for any given order in [~.X]. That is, given ([q.sub.i], [^.dd.sub.i]) [epsilon] [~.X] at the start of time period t:

[^.dd.sub.i] [less than or equal to] t + L.

Proof. See the Appendix. [black square]

3. Clearing functions

A clearing function is an abstract representation of the production process at an aggregate level of modeling. Although the underlying modeling assumptions may differ between different clearing functions, it gives the expected level of throughput to be realized during a period of time as a function of the available WIP during that period. In this study, we consider the following four different types of clearing functions that are modeled and examined in terms of their relative effects on the cost and delivery performance.

1. The traditional model with the assumption that the WIP can be cleared using the nominal production rate. We call it the "Traditional Linear" (TL) function, since it is used in the majority of production planning models.

2. The fixed-lead-time fixed-capacity model where the clearing is proportional to the available WIP based on the planned lead time, and is bounded by the nominal production rate. We call it the "Capacitated Fixed Lead Time" (CFL) function.

3. The long-term clearing function based on the steady-state queueing constructs that we call the "Long-Term Non-linear" (LTN) function.

4. The short-term clearing function based on the short-term probabilistic behavior of the shop that we call the "Short-Term Non-linear" (STN) function.

In the following, the mathematical representations of these clearing functions are provided. Although the underlying modeling assumptions may be different, all clearing functions are defined in the discrete time domain. Thus, a common notation is used irrespective of the basis that forms the clearing function. w is defined as the available WIP level during a time period and p = f(w) is the total "expected" throughput quantity during that time period with a nominal average value of [mu] per time period, where f(w) denotes the clearing function. [bar.d] refers to the demand rate per time period, and in the long-run, the throughput rate must be equal to the demand rate. The term time period refers to some fixed duration of time within which the basic input/output parameters of the system are defined such as the demand and the throughput rates, and it is identical for all clearing functions.

The TL and CFL clearing functions are both based on a deterministic view of the production process. TL assumes immediate production of what is available in the shop bounded by the nominal production rate. In other words, a SCOP model without a decomposition of order release decisions from the capacity loading decisions and with TL used to model the production process becomes very similar to the MRP and MRPII formulations of Voss and Woodruff (2003) with the exception that the production output is "partly" smoothed through the nominal production rate. In an environment where the capacity is infinitely large relative to the size of the release orders, such a formulation indicates immediate production of release orders with an independent time lag after the production untill the order becomes ready for demand consumption. The formulation of TL is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

The CFL clearing function is similar to the TL clearing function in that a linear deterministic production rate is assumed that is dependent on the WIP level, and it is bounded by the nominal production rate [mu]. Differently, a smoother production output is considered based on the planned lead time in the same manner as in Graves (1986). The CFL formulation is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

When the formulation is carried over a continuous time domain, for example in deriving LTN, w refers to the average WIP level and p refers to the average throughput level per time period. As also noted in Hackman and Leachman (1989) for a general framework, in a discrete-time production model, each rate-based flow is a step function that is constant in each time period.

For LTN, the production process is modeled as an M|G|1 queue where orders arrive in batches of size [bar.b] according to exponential inter-arrival times with a mean of 1/[lambda] time periods. Items are processed in exponentially distributed processing times with rate [mu] yielding an Erlang ([bar.b], [mu]) distributed processing time for each batch. It is important to note that the SCOP formulation makes it clear that while the items arrive in batches they are processed individually, and the clearing functions express the throughput WIP relationship in terms of items. Thus, the derivation of LTN in this study shows slight differences from the clearing functions of previous studies that utilize long-term queueing constructs (e.g., Hwang and Uzsoy (2005)). We should also note that the exponential arrival process with fixed batch sizes is an approximation of the real arrival process, where batches of (possibly) different sizes are released according to a process that may (not) show an exponential pattern. Intuitively, the actual release pattern does depend on the specific clearing function used in the SCOP model, which in turn depends on some approximation of the actual release pattern. Analyzing this cyclic structure is a complex task. It is not within the scope of this paper, but remains an interesting direction for future research.

From Little's law we have the fundamental relationship: p = w/[F.sub.item], where [F.sub.item] is the average flow time per item in the batch. Let us define the time it takes to process an item starting from the first in the batch as the batch-item processing time. The batch-item processing time of an item depends on the position of that item in the batch, and, as mentioned in Lambrecht and Vandaele (1996), the average batch-item processing time in a batch of size [bar.b] can be defined as [PT.sub.item] = ([bar.b] + 1)/2[mu]. From the Polaczek-Khinchine mean value formula for M|G|1 systems the average waiting time for each batch is given by

[WT.sub.batch] = [[lambda][bar.b]([bar.b] + 1)]/[2[mu]([mu] - [lambda][bar.b])].

The waiting time of an item in the batch before a batch starts to be processed is equal to the waiting time of the batch itself. Then

[F.sub.item] = [WT.sub.batch] + [PT.sub.item] = [[bar.b] + 1]/[2([mu] - [lambda][bar.b])],

The arrival rate of the batches can be rewritten using [lambda] = p/[bar.b]. Then, from the Little's law:

p = w/[F.sub.item] = [2w([mu] - p)]/[[bar.b] + 1].

Solving this equation for p, and assuming a batch size equal to the demand rate of [bar.d] per time period, the following formulation for the long-term non-linear clearing function can be derived:

LTN:f(w) = [2[mu]w]/[2w + [bar.d] + 1] (11)

This approximation can also be approved by solving an [M.sup.[lambda]]|[M.sup.[mu]]|1 system with bulk arrivals of size [bar.d]. If the batch size is one, d = 1, then LTN becomes identical to the clearing function in Karmarkar (1989). Equation (11) directly implies that, for any given positive [mu] and [bar.d], LTN is increasing and concave for w [greater than or equal to] 0.

The LTN clearing function is insightful in modeling nonlinearity in the production process. However, it generates some conceptual inconsistencies when used in an aggregate production planning problem involving a limited planning horizon, and planning periods that are mainly characterized by the starting and ending status of the production and inventory. The exact continuous-time formulation in Equation (11) is based on long-term averages, and becomes an approximation in a periodic planning environment; the average WIP level may not be equal to the WIP level during a time period. The throughput is a step function in time. Its rate is determined based on the starting WIP level, and is considered as being fixed during a single time period. One may criticize this approximation by stating that LTN yields a throughput level that is greater than the WIP level for some cases such as when w < [mu] - ([bar.d] + 1)/2, and the nominal throughput rate is only achieved with a very high WIP level causing the planning system to load the shop with a large amount of work during the shortage periods. In an environment with extensive material costs, this may not be very efficient. As an alternative to LTN, the clearing function may also be based on a short-term (periodic) probabilistic analysis of the throughput rate of the shop during a time period given the WIP level that is available for that time period.

The STN clearing function refers to such a model of production emphasizing the short-term behavior of the production process between consecutive work release (arrival) opportunities, and it does not consider the average behavior driven by several work releases (arrivals) into the production system. The distribution of throughput probabilities in a time period is dependent on the WIP level at the start of the time period since a throughput quantity greater than the total quantity of items in process is not possible. Given a WIP level of w available during a time period, let us denote the random variable for the throughput level in that time period as [P.sub.w]. Assuming exponential processing times with rate [mu], the probability that all items are cleared in a single time period is

Pr{[P.sub.w] = w} = 1 - [w-1.summation over (k=0)][e.sup.-[mu]] x [[[mu].sup.k]/k!].

Following the previously defined terminology, the expected throughput in a time period with a WIP level of w is

p = [w.summation over (k=1)] kPr{[P.sub.w] = k}. (12)

When w [right arrow] [infinity], [P.sub.w] becomes identical to a Poisson random variable with mean [mu]. Thus, both LTN and STN asymptotically approach the nominal production rate as w [right arrow] [infinity]. However, STN approaches [mu] more quickly then does LTN, and this makes an obvious distinction in the output of the SCOP model. Rewriting Equation (12) yields:

p = w - [w-1.summation over (k=0)](w - k)Pr{[P.sub.w] = k},

and with further simplification through replacing the term 1 - [[summation].sub.j=0.sup.k-1] Pr{[P.sub.w] = j} in the above formulation with Pr{[P.sub.k] = k}, for k = 1, 2,..., w, the STN clearing function is derived as follows:

STN:f(w) = [w.summation over (k=1)]Pr{[P.sub.k] = k}. (13)

The clearing representation in Equation (13) is conceptually robust, since the linear clearing functions can also be modeled by this representation. Consider an uncapacitated situation with the assumption that what is put into the shop can immediately be produced, Pr{[P.sub.w] = w} = 1, then STN yields f(w) = w for all w. In addition, the CFL clearing function can be modeled by setting Pr{[P.sub.w] = w} = 1/L for w [less than or equal to] L[mu] and Pr{[P.sub.w] = w} = 0 for w > L[mu]. From Equation (13), it directly follows that STN is an increasing and concave function for w [greater than or equal to] 0.

In the SCOP formulation, piecewise-linear approximations of the clearing functions are employed. For this purpose, we define "lead time regions" in the domain of the clearing function. An illustration is given in Fig. 3 for an arbitrary non-linear and concave clearing function, which is partitioned by L = l lines that cut the clearing function at points; ([m.sub.l], [[mu].sub.l]), [[mu].sub.l] = [m.sub.l]/l. WIP levels up to [m.sub.1] can be cleared in a single time period, and constitute the L = 1 region. If the WIP level is between [m.sub.l-1] and [m.sub.l] the throughput level ranges between [[mu].sub.l-1] = [m.sub.l-1]/(l - 1) and [[mu].sub.l] = [m.sub.l]/l implying a lead time of l periods. An intuitive approximation for a non-linear clearing function is to assume that the clearing follows a linear line between the lead time shift points, and the slope differs between different lead time regions due to the concavity of the clearing function. For STN and LTN, the nominal production rate, [mu], may never be reached. We assume the clearing function achieves its nominal production rate when the slope of the piecewise-linear approximation falls at or below 0.01. In the following section, the detailed shape of each clearing function is presented together with the other fixed and variable elements of our simulation experiments.

[FIGURE 3 OMITTED]

4. Experiments

4.1. Setting

The manufacturing process was considered to be a single entity with an exponentially distributed processing time per item. It may consist of a single machine or a complex manufacturing center where the transformation time of WIP into finished products is exponentially distributed. The need to aggregate a complex manufacturing center into a single entity stems from the fact that the clearing functions are originally defined based on an aggregate approach to the production process. On the other hand, in a detailed setting, the analysis and results of this study can be generalized to include flow shops with a bottleneck station at the end. The processing rate was set to be 20 units/period, [mu] = 20. The demand forecasts, D(t, t + s), s = 0, 1,..., T - 1, were generated from a gamma distribution with a mean of [bar.d], and a squared coefficient of variation of 0.5, revealing an average utilization level of [rho] = [bar.d]/[mu]. The planning horizon was T = 10 periods. The cost parameters were [h.sub.f] = 1.25, [^.h.sub.f] = 1.20 and [h.sub.w] = 1.00. "Today, direct labor constitutes less than 15% of the cost of most products" (c.f. Hopp and Spearman (2000)), and material costs have the lion's share in this figure. In addition, holding a high WIP level requires a large space on the shop floor, requiring the incorporation of handling and spacing costs in addition into the material costs. Therefore, the WIP holding costs and the finished product holding costs were chosen to be close to each other. Each simulation run started with the initial conditions [I.sup.+] (0, 0) = L[bar.d], [I.sup.-](0, 0) = 0, W(0, 0) = 0 and [^.W](0, 0) = 0. That is, the shop is empty and there are enough items in the inventory for the demand during the lead time.

The TL and CFL clearing functions were modeled as defined in Equations (9) and (10). The piecewise-linear approximation of the STN clearing function was based on Equation (13), and was modeled as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

In STN, 100% productivity was disturbed starting from a workload level of nine items, and the nominal throughput rate, 20 items/period, was reached when there were 34 items in the process. For LTN we used [bar.d] = 17 in Equation (11). It assumes higher (or equal) productivity than does STN for low levels of workload, w [less than or equal to] 16, and the productivity quickly degrade as the shop congestion increases. The nominal throughput rate achieved by LTN, 18.71 items/period, is less than that of STN. The piecewise-linear approximation of the LTN clearing function was as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

The SCOP formulation together with the specific shape of the clearing function used in the formulation implies that the WIP is bounded by the level [W.sub.max] = min{w : f(w) = [mu]'}, since, increasing the WIP further does not add to the planned throughput quantities but instead increases the cost. Here, [mu]' is the nominal throughput rate indicated by the clearing function, which may be less than the theoretical maximum. For TL, [W.sub.max] = 20, for CFL, [W.sub.max] = 20L, for LTN, [W.sub.max] = 131 and for STN, [W.sub.max] = 34. One would expect that the higher the [W.sub.max] level, the higher the WIP costs, but at the same time the lower the [W.sub.max] level, the more likely is the shop to become idle during a period thereby increasing the possibility for late deliveries in subsequent periods.

4.2. Design

In addition to the type of clearing function used in the SCOP model, we considered environmental factors such as the demand uncertainty and the utilization in the design of experiments. Demand uncertainty was modeled in terms of a per cent deviation from the forecasted demand. If the forecasted demand for a period was [^.d], the actual demand, for the same period, with a 40% deviation was generated from a Uniform (0.60 [^.d], 1.40 [^.d]) distribution, and with a 80% deviation it was generated from a Uniform (0.20[^.d], 1.80[^.d]) distribution. A deterministic demand setting was represented by a 0% deviation from the forecasted values. The utilization was changed by changing the demand levels. Given a fixed value of [mu] = 20, a 80% utilization was achieved by setting [bar.d] = 16, and a 90% utilization was achieved by setting [bar.d] = 18. Different planned lead times were also considered. The planned lead time could be either short, L = 3 periods, or long, L = 5 periods. These values were generated by rounding the mean flow time found from the Polaczek-Khinchine mean value formula for an M|G|1 system with batch processing under utilization levels of 0.80 and 0.90 respectively. Table 1 provides the design of experiments.

In total there were 48 different treatments, and for each of them we used a simulation run length of 5460 periods. The first 260 periods were used as the warm up period. Welch's procedure (see Law and Kelton (2000) for a complete description) was applied to approximate the warm-up period for the output analysis of each simulation. Each simulation with a given choice of treatments was replicated 15 times using a different random number stream at each replication. Between different sets of replications the same set of random number streams were implemented. The experiments were performed using QUINTIQ 3.1.0.10 (see Quintiq (2007) for further details) to simulate the warehouse and the manufacturer, and CPLEX to solve the SCOP formulation.

4.3. Results

We are interested in two significant performance measures: (i) the average periodic cost given that a target level of demand fill rate is satisfied; and (ii) the consistency of the planned schedule with the actual delivery of the orders. The target fill rate is 98%. For each simulation, an initial run was performed with the safety stock set equal to zero. Then, the safety stock was adjusted according to the procedure described in Kohler-Gudum and De Kok (2001), so as to satisfy the target fill rate, and the simulation was repeated with the new safety stock value. Tables 2 and 3 provide results related to the total average cost, respectively with planned lead times of L = 3 and L = 5 periods. The total average cost per period is abbreviated to TC, and the specific cost components are also provided such as: the average on-hand inventory at the warehouse ([I.sup.+]); the average finished WIP at the production unit (FW); and the average WIP level (W), in order to clarify the factors that generate the difference in TC. In addition, the safety stock level (SS) indicates the variability in the back-order level of the warehouse. The total cost is calculated as follows:

TC = [h.sub.f][I.sup.+] + [^.h.sub.f]FW + [h.sub.w]W.

These cost terms are more meaningful when considered together with the actual delivery performance of the order releases. This is because the sizes and the timings of the order releases are mainly driven by the periodic demand forecasts during the planned lead time and the deviations from these demand forecasts. Thus, one finds it difficult to explain differences between the clearing functions if the delivery performance is ignored in the analysis. The results for the delivery performance under different clearing functions are provided in Tables 4 and 5 with planned lead times of L = 3 and L = 5 periods respectively. AF denotes the average actual order flow time, CVF is the coefficient of variation in the flow times, [DELTA]L is the mean squared deviation of actual flow times from the planned lead time and [pi] denotes the percentage of tardy orders.

In accordance with our objective in this study, the simulation results are interpreted by looking at the relative performance of different clearing functions. The lowest value of each performance criterion among the different clearing functions is in bold typeface, and pairwise comparisons were performed between different clearing functions keeping all other experimental factors fixed. The "[dagger]" sign in the tables refers to the absence of a statistical difference between the results of different clearing functions with a 95% confidence level.

The clearing function has a significant effect on the performance of the SCOP model. About a 55% improvement in the total periodic cost is possible by using different clearing functions in the SCOP model, and the consistency of the planned schedule can be improved significantly. Recall from the previous sections that orders are released to the manufacturer and received by the warehouse in batches of various sizes, and the demand is moderately variable. Thus, one would expect that both [DELTA]L and [PI] have significant impacts on TC.

The effect of TL especially on [PI], and therefore on SS, is very adverse. TL supports late production because it assumes that a high level of WIP can be quickly cleared. When the operational execution in the shop is not in line with this assumption, the number of tardy orders increases significantly, and the system has to hold a high SS to compensate for large backorders. As a result, we see a very high [I.sup.+], and consequently a high total cost. The effects are bigger under a high utilization. The average WIP level has its lowest value under TL, because capacity loading is kept low due to the assumption of high productivity. We see this is an unrealistic assumption because it causes loss of capacity, and the system suffers from high backorders leading to very high SS levels. Consequently, TL generates the longest average flow time in all cases and it is greater than the planned lead time. Under TL, the deviation from the planned schedule in terms of [DELTA]L is smaller than those of CFL and LTN. However, this does not generate a better cost performance due to the high number of late order deliveries. Under a high utilization, over 60% of the orders are delivered late. Thus, the level of consistency should be considered as a joint effect of [DELTA]L and [PI].

From that point of view, we can see a clear distinction between STN and TL, in that both [DELTA]L and [PI] of STN are smaller than those of TL. As a result, STN outperforms TL with an improvement from 33 to 62% in TC. STN assumes a lower productivity than does TL, and loads the capacity earlier, resulting in decreased flow times. Having the flow times closer to the planned lead times and significantly decreased [PI], STN provides a better coordination of the material flow between the manufacturer and the warehouse than does TL.

CFL assumes a lower productivity than does STN, and provides a lower [PI]. However, earlier than planned delivery of the production orders increases [DELTA]L. In addition, the variation in the flow times is higher than that of STN. An appealing result is that the differences between the [I.sup.+] of CFL and the [I.sup.+] of STN are insignificant in almost all cases. Although STN has a higher SS and [PI], improved consistency and reliability in the planned lead times provide better planning of the finished product stock at the warehouse. WIP levels can be decreased drastically without causing loss of capacity, and a lower TC is achieved with STN in all cases.

Similar to CFL, LTN can be mainly characterized by the early delivery of the orders. Since the utilization is kept at moderately high values (above 80%) LTN loads the shop early and in large quantities in order to achieve a certain planned throughput level. If the actual processing capability is more productive than what is assumed by LTN, early delivery of orders occurs. As a consequence, in most of the cases LTN provides the smallest AF and the lowest [PI]. This results in the lowest SS and [I.sup.+] with LTN in almost all cases. However, with drastically decreased WIP levels STN provides the lowest cost solution. Under low utilization and low variability LTN does not perform worse than STN where an increased W and FW can be compensated by a decreased [I.sup.+]. This is due to the fact that the congestion effect of LTN is weak in these cases, due to low planned WIP levels.

The performance of LTN is more sensitive to the environmental factors. Increased uncertainty and high utilization cause LTN to have a deteriorating performance. LTN overreacts to increased uncertainty and utilization causing an increased TC. Under [rho] = 0.80, (Tables 2 and 3), [I.sup.+] of LTN triples, and W of LTN increases by about 70% when the demand uncertainty increases from 0 to 80%. Under the same conditions, [I.sup.+] of STN doubles, and W of STN increases by about 20%. Similarly, when the utilization is increased from 0.80 to 0.90 under the deterministic demand conditions, [I.sup.+] of LTN increases by about 250%, and W of LTN increases by about 125%, while [I.sup.+] of STN increases by about 100%, and W of STN increases by about 60%. This relatively robust behavior of STN under changing environmental factors is due to the fact that CVF and [DELTA]L of STN are always less than those of LTN. That is, both the variability and the unpredictability of the delivery schedules are less severe under STN, which makes the planning system less vulnerable to environmental uncertainties. Except for the cases with [rho] = 0.80 and [U.sub.D] = 0%, STN provides a better TC performance than does LTN. Under [rho] = 0.90 and [U.sub.D] = 80%, both STN and LTN satisfy the same fill rate with insignificantly different [I.sup.+] levels, where, with its much lower WIP level, STN outperforms LTN. To sum up, STN achieves a high level of consistency between the planned schedule and the executed schedule, where the effect of a rolling horizon on the suboptimality is less significant. STN ensures a better coordination between the capacity loading and the order release decisions, which results in an improved cost performance especially under high demand uncertainty, and high utilization levels.

As can be seen from the results, the choice of the planned lead time does not have a significant impact on the cost performance of the LTN, STN and TL clearing functions. Since the structure of CFL depends on the planned lead time, its performance differs significantly between L = 3 and L = 5. Thus, it is crucial to choose the right planned lead time when CFL is deployed in the SCOP model. CFL with L = 5 provides [I.sup.+] and FW values close to those of CFL with L = 3, but it causes a much higher average WIP level. It generates an unnecessary build up of WIP, which suggests that we should model the production process using more opportunistic clearing functions, i.e., CFL with L = 3 outperforms CFL with L = 5. However, very optimistic models such as TL (CFL with L = 1) also perform badly. We see that the STN clearing function provides a good reference point between the optimistic and the pessimistic production models. This can be also seen when one looks at the average order flow times: the AF of STN is always larger than the AF of CFL and smaller than the AF of TL, and is closer to the planned lead time. Since the throughput quantities per period are determined at the SCOP level according to the planned lead time, an increase in the planned lead time yields an increase in the actual order flow times. In addition, Tables 4 and 5 provide the interesting result that as the planned lead time increases the production of the release orders are spread across a bigger number of periods. Thus, the coefficient of variation in the actual order flow times decreases due to the rolling horizon method used at each replanning opportunity. In relation to the decrease in CVF, more orders are delivered early for a clearing function with a pessimistic approach such as CFL and LTN, and more orders are delivered late for a clearing function with an optimistic approach such as TL. In that respect, STN provides a relatively robust behavior such that [DELTA]L and [PI] change very slightly under different planned lead times.

5. Conclusions and future research

In this paper, we have provided a planning framework for SCOP with the capacity loading decisions being decomposed from the order release so that the throughput during the planned lead time can be determined to meet the planned delivery schedule. The throughput performance of the system was planned by modeling an anticipation of the dynamic performance of the shop floor through clearing functions. Our research question has been, "what is the appropriate form of such a clearing function for the best performance of the SCOP model?" We have shown that the shape of the clearing function plays an important role in the completion time of the orders. There is a tradeoff between loading the shop early with high WIP levels and forcing the system to deliver orders earlier than planned, and keeping low WIP levels in the shop but experiencing increased number of late deliveries. In addition the consistency of the actual production schedule to the planned schedule improves the cost performance of the system. Finally deploying a production model based on the short-term probabilistic performance of the shop provides the best performance in terms of the average periodic cost and the robustness by achieving coordinated flow of material both within the manufacturer and between the manufacturer and the warehouse.

We see that, with STN, the squared deviation of the actual flow times from the planned lead times has its lowest value and keeps the number of orders that are tardy at a reasonable level. Therefore, we may also expect to see an improved performance especially for multi-stage, multi-item production-distribution situations due to better coordination of material flow between successive stages of the supply chain. The structure of the supply chain plays an important role. The performance evaluation for more complex structures is therefore an interesting subject for future research. The complexity can be further increased by considering more realistic shop structures such as multi-resource flow shops and job shops.

In addition to the performance-related issue, especially through STN, more detailed discussion on modeling the clearing behavior can be performed. For example, instead of a mean value approach, the approximated distribution characteristics of the throughput depending on the WIP level can be incorporated into the clearing function. In that respect, the STN clearing function can be elaborated in such a way that it relates the WIP level to a throughput level with a certain probability of occurrence.

References

Armbruster, D., Ringhofer, C. and Jo, T.C. (2004) Continuous models for production flows, in Proceedings of the 2004 American Control Conference, Boston, MA, pp. 4589-4594.

Asmundsson, J.M., Rardin, R.L. and Uzsoy, R. (2003) Tractable nonlinear capacity models for production planning part I: modeling and formulations. Research report, Laboratory for Extended Enterprises at Purdue, School of Industrial Engineering, Purdue University, West Lafayette, IN.

Asmundsson, J.M., Rardin, R.L. and Uzsoy, R. (2004) Tractable nonlinear capacity models for production planning part II: implementation and computational experiments. Research report, Laboratory for Extended Enterprises at Purdue, School of Industrial Engineering, Purdue University, West Lafayette, IN.

Asmundsson, J.M., Rardin, R.L. and Uzsoy, R. (2006) Tractable nonlinear production planning models for semiconductor wafer fabrication facilities. IEEE Transactions on Semiconductor Maufacturing, 19(1), 95-111.

Bertrand, J.W.M. and Wijngaard, J. (1985) The structuring of production control systems. International Journal of Operations and Production Management, 6(2), 5-20.

Billington, P.J., McClain, J.O. and Thomas, L.J. (1983) Mathematical programming approaches to capacity constrained MRP systems: review, formulation and problem reduction. Management Science, 29, 1126-1141.

Chung, C.H. and Krajewski, L.J. (1984) Planning horizons for master production scheduling. Journal of Operations Management, 4(4), 389-406.

De Kok, A.G. and Fransoo, J.C. (2003) Planning supply chain operations: definition and comparison of planning concepts, in Handbook in Operations Research and Management Science, Volume 11: Design and Analysis of Supply Chains, De Kok, A.G. and Graves, S.C. (eds), Elsevier, Amsterdam, The Netherlands, pp. 597-675.

Graves, S.C. (1986) A tactical planning model for a job shop. Operations Research, 34(4), 522-533.

Hackman, S.T. and Leachman, R.C. (1989) A general framework for modeling production. Management Science, 35(4), 478-495.

Hopp, W.J. and Spearman, M.L. (2000) Factory Physics: Foundations of Manufacturing Management, second edn., McGraw-Hill, New York, NY.

Hwang, S. and Uzsoy, R. (2005) A single stage multi-product dynamic lot sizing model with work in process and congestion. Research report, Laboratory for Extended Enterprises at Purdue, School of Industrial Engineering, Purdue University, West Lafayette, IN.

Karmarkar, U.S. (1987) Lot sizes, lead times and in-process inventories. Management Science, 33(3), 409-418.

Karmarkar, U.S. (1989) Capacity loading and release planning with work-in-progress (WIP) and leadtimes. Journal of Manufacturing Operations Management, 2, 105-123.

Karmarkar, U.S. (1993). Manufacturing lead times, order release and capacity 5loading, in Handbook in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory, Graves, S.C., Rinnooy Kan, A.H.G. and Zipkin, P.H. (eds), Elsevier, Amsterdam, The Netherlands, pp. 287-329.

Kohler-Gudum, C.K. and De Kok, A.G. (2001) A safety stock adjustment procedure to enable target service levels in simulation of generic inventory systems. BETAWorking Paper 71, Technische Universiteit Eindhoven, The Netherlands.

Lambrecht, M.R. and Vandaele, N.J. (1996) A general approximation for the single product lot sizing model with queueing delays. European Journal of Operational Research, 95, 73-88.

Law, A.M. and Kelton, W.D. (2000) Simulation Modelling and Analysis, third edn., McGraw-Hill, New York, NY.

Missbauer, H. (2002) Aggregate order release planning for time-varying demand. International Journal of Production Research, 40(3), 699-718.

Quintiq (2007) http://www.quintiq.com (accessed on March 4, 2007).

Riano, G. (2002) Transient behavior of stochastic networks: application to production planning with load dependent lead times. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA.

Schneeweiss, C. (1995) Hierarchical structures in organizations: a conceptual framework. European Journal of Operational Research, 86, 4-31.

Selcuk, B., Fransoo, J.C. and De Kok, A.G. (2006) The effect of updating lead times on the performance of hierarchical planning systems. International Journal of Production Economics, 104(2), 427-440.

Shapiro, J.F. (1993) Mathematical programming models and methods for production planning and scheduling, in Handbook Operations Research and Management Science, Volume 4: Logistics of Production and Inventory, Graves, S.C., Rinnooy Kan, A.H.G. and Zipkin, P.H. (eds), Elsevier, Amsterdam, The Netherlands, pp. 371-443.

Spitter, J.M., De Kok, A.G. and Dellaert, N.P. (2005). Timing production in LP models in a rolling schedule. International Journal of Production Economics, 93-94, 319-329.

Spitter, J.M., Hurkens, C.A.J., De Kok, A.G., Negenman, E.G. and Lenstra, J.K. (2005) Linear programming models with planned lead times. European Journal of Operational Research, 163, 706-720.

Stadtler, H. and Kilger, C. (2000) Supply Chain Management and Advanced Planning: Concepts, Models, Software and Case Studies, Springer-Verlag, Heidelberg, Germany.

Voss, S. and Woodruff, D.L. (2003) Introduction to Computational Optimization Models for Production Planning in a Supply Chain, Springer-Verlag, Heidelberg, Germany.

Zapfel, G. and Missbauer, H. (1993) New concepts for production planning and control. European Journal of Operational Research, 67, 297-320.

Appendix

Proof of Proposition 1. Define [^.W]*(t, [~.dd.sub.i]) = [^.W](t, t) + ([~.dd.sub.i] - t)[mu] - [[summation].sub.j=1.sup.i-1] [q.sub.j]. The schedule update heuristic partitions the set [~.X] into two disjoint subsets; the subset of orders that are rescheduled, [~.X.sub.late], and the subset of orders that are not rescheduled, [~.X]\[~.X.sub.late]. We consider the following two cases:

Case 1. ([q.sub.i], [~.dd.sub.i]) [epsilon] [~.X.sub.late] and ([q.sub.i+1], [~.dd.sub.i+1]) [epsilon] [~.X]\[~.X.sub.late].

From the definition of the subset [~.X.sub.late] the following conditions are determined [^.W]*(t, [~.dd.sub.i]) < [q.sub.i], and [^.W]*(t, [~.dd.sub.i+1]) [greater than or equal to] [q.sub.i+1]. Accordingly

[^.W]*(t, [~.dd.sub.i+1]) = [^.W]*(t, [~.dd.sub.i])+([~.dd.sub.i+1] - [~.dd.sub.i])[mu] - [q.sub.i] [greater than or equal to] [q.sub.i+1],

which directly implies that:

[^.W]*(t, [~.dd.sub.i]) + ([~.dd.sub.i+1] - [~.dd.sub.i])[mu] [greater than or equal to] [q.sub.i].

Then, the following relationship holds true due to Equation (8):

[^.dd.sub.i] [less than or equal to] [^.dd.sub.i+1]. (A1)

Case 2. ([q.sub.i], [~.dd.sub.i]) [epsilon] [~.X.sub.late] and ([q.sub.i+1], [~.dd.sub.i+1]) [epsilon] [~.X.sub.late].

By the definition of the subset [~.X.sub.late], [^.W]*(t, [~.dd.sub.i]) < [q.sub.i]. From Equation (8):

[^.W](t, t) + ([^.dd.sub.i+1] - t)[mu] - [i.summation over (j=1)] [q.sub.j] [greater than or equal to] [q.sub.i+1],

which implies that:

[^.W]*(t, [~.dd.sub.i]) + ([^.dd.sub.i+1] - [~.dd.sub.i])[mu] - [q.sub.i] [greater than or equal to] [q.sub.i+1].

From Equation (8), this automatically satisfies the fact that:

[^.dd.sub.i] [less than or equal to] [^.dd.sub.i+1]. (A2)

For the case with ([q.sub.i], [~.dd.sub.i]) [epsilon] [~.X]\[~.X.sub.late] and ([q.sub.i+1], [~.dd.sub.i+1]) [epsilon] [~.X.sub.late], and the case with ([q.sub.i], [~.dd.sub.i]) [epsilon] [~.X]\[~.X.sub.late] and ([q.sub.i+1], [~.dd.sub.i+1]) [epsilon] [~.X]\[~.X.sub.late], Proposition 1 is satisfied directly from the definitions of [~.X] and [~.X.sub.late].

The proof on order crossings is done by induction. From constraint sets (4) and (5) it is obvious that [[summation].sub.s=1.sup.L] [^.Q](t, t + s) [less than or equal to] [^.W](t, t) + L[mu]. Given that [~.X.sub.late] = [null];, this directly implies that:

[k.summation over (j=1)][q.sub.j] [less than or equal to] [^.W](t, t) + L[mu]. (A3)

During the current period the worst-case throughput is zero, which causes, in the next replanning, some of the orders to become late. However, Equation (A3) still holds, and from Equation (8), it is directly given that:

[^.dd.sub.k] [less than or equal to] t + L. (A4)

The production unit is assumed to be initially empty, yielding [~.X.sub.late] = [null] at the start of the simulation. Therefore, condition (A4) holds true during the rest of the simulation. Together with Equations (Al) and (A2), this completes the proof of Proposition 1. [black square]

Biographies

Baris Selcuk has been a research assistant at the Technische Universiteit Eindhoven, The Netherlands since 2003. He holds an MSc degree in Industrial Engineering from Bilkent University in Turkey. His areas of interest include hierarchical planning, adaptive decision support systems, lead time management and queueing systems.

Jan Fransoo is a Professor of Operations Management and Logistics at the Technische Universiteit Eindhoven, The Netherlands. He holds an MSc in Industrial Engineering and a PhD in Operations Management and Logistics from the Technische Universiteit Eindhoven. Following the completion of his PhD thesis, he was awarded a fellowship by the Royal Netherlands Academy of Sciences. He specializes in operations planning and supply chain management in the process and FMCG industries, and is part of the Eindhoven Retail operations group. He also serves as Research Director of the European Supply Chain Forum, a collaborative effort with about 20 large multi-national companies. He has hold various visiting appointments at US universities, including Clemson University, Stanford University and the University of California at Los Angeles. He serves as a Senior Editor of the Production and Operations Management, an Associate Editor of Journal of Operations Management, and has published over 30 papers in academic journals such as IIE Transactions, Production and Operations Management, Journal of Operations Management, International Journal of Operations and Production Management and European Journal of Operational Research.

Ton G. de Kok has a MSc in Mathematics from Rijksuniversiteit Leiden, The Netherlands and a PhD in Mathematics from the Free University, Amsterdam, The Netherlands. He worked at Philips Electronics from 1985 until 1992. Since 1992 he has been a Full Professor at the Technische Universiteit Eindhoven. He published over 75 articles in international scientific journals. He is a Director of the European Supply Chain Forum (eSCF). He is a Scientific Director of the research school Beta. His main research areas are in supply chain management and concurrent engineering with an emphasis on quantitative analysis.

B. SELCUK*, J. C. FRANSOO and A. G. DE KOK

Department of Technology Management, Technische Universiteit Eindhoven. The Netherlands

E-mail: {b.selcuk, j.c.fransoo, a.g.d.kok}@tm.tue.nl

Received December 2005 and accepted December 2006

*Corresponding author

Table 1. Experimental design

                                                     Number of
Factors                        Treatments            treatments

Clearing function              CFL, LTN, STN, TL     4
Demand uncertainty, [U.sub.D]  0, 40, 80%            3
Utilization, [rho]             0.80, 0.90            2
Planned lead time, L           3 periods, 5 periods  2

Table 2. Cost performance of the clearing functions, L = 3 periods

                     Demand uncertainty, [U.sub.D]
                         0% Clearing function
[rho]        CFL               LTN               STN

0.80
  SS          29.3               9.8              35.1
  [I.sup.+]   33.8 ([dagger])   19.7              35.0 ([dagger])
  FW           9.9              10.2               8.3
  W           13.8              19.3               4.8
  TC          67.9              56.1 ([dagger])   58.5 ([dagger])
0.90
  SS          78.7              65.1              83.4
  [I.sup.+]   77.5              72.8 ([dagger])   72.2 ([dagger])
  FW          11.0              11.8               9.9 ([dagger])
  W           20.9              42.6               7.3
  TC         131.0             147.8             115.7

                     Demand uncertainty, [U.sub.D]
             0% Clearing function  40% Clearing function
[rho]        TL                    CFL               LTN

0.80
  SS          77.1                  41.0              25.1
  [I.sup.+]   65.6                  44.5 ([dagger])   34.6
  FW           7.8                  10.3              10.7
  W            0.9                  15.1              23.5
  TC          92.2                  83.0              79.5
0.90
  SS         309.7                  97.3              83.0
  [I.sup.+]  234.6                  92.9 ([dagger])   88.04
  FW           9.8 ([dagger])       11.2              12.2
  W            1.2                  22.4              47.6
  TC         306.2                 152.0             172.3

                     Demand uncertainty, [U.sub.D]
             4% Clearing function                80% Clearing function
[rho]        STN               TL                CFL

0.80
  SS          46.7              94.1              70.7
  [I.sup.+]   45.4 ([dagger])   79.5              71.5 ([dagger])
  FW           8.6               8.0              11.0
  W            5.3               0.9              17.4
  TC          72.3             109.8             120.0
0.90
  SS         103.0             348.6             155.1
  [I.sup.+]   93.5 ([dagger])  261.6             142.0 ([dagger])
  FW          10.0 ([dagger])    9.9 ([dagger])   11.6
  W            7.8               1.2              24.5
  TC         136.6             340.0             215.9

                     Demand uncertainty, [U.sub.D]
                        80% Clearing function
[rho]        LTN               STN               TL

0.80
  SS          55.6              76.7             142.8
  [I.sup.+]   63.6              72.4 ([dagger])  120.0
  FW          12.0               9.0               8.4
  W           33.3               5.9               0.9
  TC         127.3             107.2             161.0
0.90
  SS         143.1             163.3             453.3
  [I.sup.+]  140.5 ([dagger])  144.7 ([dagger])  327.9
  FW          13.3              10.2              10.1
  W           56.8               8.4               1.2
  TC         248.3             201.5             423.2

Table 3. Cost performance of the clearing functions, L = 5 periods

                     Demand uncertainty, [U.sub.D]
                         0% Clearing function
[rho]        CFL               LTN               STN

0.80
  SS          26.0              11.7              36.6
  [I.sup.+]   35.4 ([dagger])   21.8              36.1 ([dagger])
  FW          10.2               9.8               8.4
  W           28.4              18.6               4.6
  TC          84.8              57.5 ([dagger])   59.8 ([dagger])
0.90
  SS          77.8              64.1              82.6
  [I.sup.+]   80.5              71.9              76.2
  FW          11.3 ([dagger])   11.2 ([dagger])    9.9
  W           42.1 ([dagger])   41.7 ([dagger])    7.0
  TC         156.3             145.1             114.2

                     Demand uncertainty, [U.sub.D]
             0% Clearing function  40% Clearing function
[rho]        TL                    CFL               LTN

0.80
  SS          79.7                  37.9              25.3
  [I.sup.+]   67.0                  46.8 ([dagger])   35.2
  FW           7.9                  10.7              10.1
  W            0.9                  30.1              21.6
  TC          94.2                 101.5              77.7
0.90
  SS         311.2                  95.7              85.6
  [I.sup.+]  234.6                  96.3 ([dagger])   90.9
  FW          10.1                  11.6              11.5
  W            1.2                  44.2 ([dagger])   45.6 ([dagger])
  TC         306.6                 178.5             173.1

                     Demand uncertainty, [U.sub.D]
             40% Clearing function    80% Clearing function
[rho]        STN               TL     CFL

0.80
  SS          47.7              94.6   67.3
  [I.sup.+]   46.5 ([dagger])   79.4   75.3 ([dagger])
  FW           8.7               8.2   11.7
  W            4.9               0.9   33.8
  TC          73.5             109.9  142.0
0.90
  SS         104.1             348.6  152.0
  [I.sup.+]   94.7 ([dagger])  260.7  146.0 ([dagger])
  FW          10.1              10.2   12.3
  W            7.4               1.2   47.8
  TC         137.9             339.3  245.1 ([dagger])

                     Demand uncertainty, [U.sub.D]
                        80% Clearing function
[rho]        LTN               STN               TL

0.80
  SS          57.1              76.7             143.1
  [I.sup.+]   66.0              73.6 ([dagger])  120.6
  FW          10.9               9.3               8.7
  W           29.0               5.5               0.9
  TC         124.6             108.6             162.2
0.90
  SS         144.1             163.5             453.0
  [I.sup.+]  142.7 ([dagger])  146.2 ([dagger])  328.3
  FW          12.0              10.5 ([dagger])   10.5 ([dagger])
  W           53.5               7.9               1.2
  TC         246.3 ([dagger])  203.3             424.1

Table 4. Delivery performance of the clearing functions, L = 3 periods

                     Demand uncertainty, [U.sub.D]
            0% Clearing function        40% Clearing function
[rho]       CFL   LTN   STN    TL     CFL    LTN   STN    TL

0.80
  AF        2.49  2.29   2.86   3.25   2.52  2.29   2.88   3.30
  CVF       0.29  0.34   0.20   0.18   0.30  0.34   0.20   0.18
  [DELTA]L  0.78  1.09   0.35   0.40   0.80  1.12   0.35   0.44
  [PI]      3.67  0.81   7.71  31.33   4.87  1.17   9.16  35.72
0.90
  AF        2.59  2.24   2.88   3.54   2.64  2.28   2.92   3.57
  CVF       0.30  0.37   0.22   0.17   0.30  0.37   0.22   0.16
  [DELTA]L  0.75  1.25   0.43   0.63   0.74  1.23   0.43   0.66
  [PI]      8.03  2.68  11.95  57.65  10.06  3.48  14.01  60.41

            Demand uncertainty, [U.sub.D]
              80% Clearing function
[rho]       CFL    LTN   STN    TL

0.80
  AF         2.58  2.28   2.93   3.39
  CVF        0.31  0.36   0.21   0.18
  [DELTA]L   0.80  1.20   0.37   0.51
  [PI]       7.62  2.38  12.18  43.09
0.90
  AF         2.76  2.35   2.98   3.62
  CVF        0.30  0.37   0.22   0.15
  [DELTA]L   0.73  1.19   0.43   0.69
  [PI]      14.64  5.24  17.42  64.50

Table 5. Delivery performance of the clearing functions, L = 5 periods

                     Demand uncertainty, [U.sub.D]
              0% Clearing function      40% Clearing function
[rho]       CFL   LTN   STN    TL     CFL   LTN   STN    TL

0.80
  AF        4.12  4.27   4.87   5.33  4.11  4.26   4.88   5.37
  CVF       0.24  0.20   0.12   0.12  0.26  0.20   0.12   0.12
  [DELTA]L  1.75  1.24   0.37   0.50  1.88  1.29   0.38   0.54
  [PI]      2.80  0.89   8.62  37.53  3.53  1.00   9.48  41.59
0.90
  AF        4.33  4.20   4.88   5.67  4.35  4.23   4.90   5.71
  CVF       0.22  0.21   0.13   0.10  0.24  0.21   0.14   0.10
  [DELTA]L  1.38  1.43   0.44   0.79  1.47  1.42   0.46   0.82
  [PI]      6.82  2.23  12.24  69.44  8.32  2.74  13.98  72.11

            Demand uncertainty, [U.sub.D]
               80% Clearing function
[rho]       CFL    LTN   STN    TL

0.80
  AF         4.10  4.24   4.89   5.47
  CVF        0.29  0.22   0.13   0.12
  [DELTA]L   2.18  1.42   0.43   0.65
  [PI]       5.30  1.75  11.71  49.81
0.90
  AF         4.38  4.27   4.94   5.76
  CVF        0.26  0.23   0.14   0.09
  [DELTA]L   1.65  1.48   0.49   0.87
  [PI]      10.52  3.94  16.44  76.76