Stability measures for rolling schedules with applications to capacity expansion planning, master production scheduling, and lot sizing
Introduction
Planning methods with a finite horizon are, by definition, tailored to construct a plan for T periods. Consider, for instance, capacity expansion planning which is a long-term production planning problem. Since the lifetime of a firm is supposed to last beyond the planning horizon, capacity expansion planning is not a single event. A quick and dirty approach to meet that situation would be to plan for the T periods 1,…,T, to implement that plan, to plan for the next T periods T+1,…,2 T, afterwards, and so on. This would make long-term production planning a process running a solution method every T periods. Beside the fact that the final state of one production plan defines the initial state for the next, these runs would be independent.
In a real-world situation, however, this working principle would not be appropriate for several reasons. The capacity demand, for instance, appears to be non-deterministic. A more accurate estimate for capacity demand refines early forecast as time goes by, and (unexpected) events such as the invention of new technologies, process innovations, and competition issues make expansion plans obsolete.
So, what usually happens is that planning overlaps. This is to say that, starting with a plan for the periods 1,…,T, the plan for the first, say Δ T≥1, periods is implemented and a new plan is then generated for the periods Δ T+1,…,Δ T+T which coins the name rolling horizon. In other words, the production in the periods Δ T+1,…,T is rescheduled. Note, if Δ T<T/2 some periods are revised more than once.
This point of view reveals the capacity expansion planning problem with T periods being a subproblem in a rolling horizon implementation. While the first Δ T periods of the current plan are implemented, new expansion sizes may differ markedly from a former expansion plan in later periods due to rescheduling. This phenomenon is known as nervousness1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Since many proceedings, such as financial planning and subcontracting, do heavily interact with the expansion process and the supply chain management is also affected by capacity expansion, nervous plans cause high transaction costs. It is unlikely to find methods which take all relevant aspects into account. Hence, the performance of capacity expansion planning methods should not only be evaluated by run-time and objective function values for a fixed horizon, but by cost and (in-)stability measures for the performance on a rolling horizon basis, too. This not only holds for the capacity expansion example, but for many other production planning problems, too.
To emphasize the relevance of this work, Section 2discusses several production planning problems for which decisions are to be made on a rolling horizon basis. These examples range from capacity expansion planning which is a strategic (long-term) decision, to master production scheduling which is a tactical (medium-term) decision, to lot sizing which is an operational (short-term) decision. In Section 3we review some more literature for planning in rolling horizon implementations. Stability measures are then suggested in Section 4. Section 5is devoted to discuss the implications of robust planning to solution methods. Section 6presents an iterative method to reduce the nervousness and illustrates the ideas by means of an example. Concluding remarks in Section 7finish the paper.
Section snippets
Capacity expansion planning
The problem of capacity expansion planning is to acquire extra capacity for a facility in order to meet a monotonically growing capacity demand. The finite planning horizon (which is typically several years) is subdivided into a number of discrete time periods (such as months). Capacity which is acquired before it is used incurs holding costs for carrying excess capacity. Expanding the capacity of a facility causes expansion costs. Furthermore, capacity that is available at one facility may be
Literature review
The question of how to measure the performance of a planning method when applied on a rolling horizon basis is discussed and studied by several authors. There are two main streams. Some authors consider cost oriented measures while others suggest stability oriented performance measures. If computational studies are done, a plan is generated for the periods 1,…,T,…,T̂ where T̂ is a parameter of the test-bed. Note, this is an approximation, because the result for T̂→∞ would be of interest.
In[46]
Stability measures
To measure the performance of a production planning method when used with a rolling planning horizon, assume that a T-period subproblem is solved n>0 times. As a result we get a production plan for the periods 1,…,T,…,T̂=(n−1)Δ T+T. Following the lines above, in each run i=1,…,n−1 the plan for the periods (i−1)Δ T+1,…,iΔT is implemented while the plan for the periods iΔT+1,…,(i−1)Δ T+T is of a preliminary nature. Letfor i=1,…,n−1 denote the weighted production
Implications for planning methods
The question that arises is how to take the stability of a plan into account when solving a production planning problem. Let i≥2 be the number of the run that is performed andbe an item-specific instability measure that is derived from , , respectively, taking into account what run i can affect. Furthermore, let SM(i)∈{SMmax(i),SMmean(i)} be the overall (in-)stability measure under concern whereand
An iterative method
To show how the above ideas may affect planning, an iterative method will now be presented and will be examined by solving a small example. Assume that lot sizing is the problem to be solved.
Consider the following data: J=3 items are to be scheduled in T=8 periods. In each period t we have Ct=100 capacity (=time) units available. Producing one unit of an item j requires pj=1 of these capacity units. Setting the machine up takes st1=10, st2=20, and st3=30 time units, respectively, depending on
Conclusion
We have discussed stability measures for dynamic production planning with rolling schedules. As examples we have given the long-term capacity expansion planning problem, the medium-term master production scheduling problem, and the short-term capacitated lot sizing problem. The (in-)stability measures that we propose take into account changes in all those periods which are rescheduled. The amount of change is also considered. An iterative method is presented to reduce the nervousness of
Acknowledgements
This work was done with partial support from the DFG-project Dr 170/4-1. We are indebted to Andreas Drexl for the fruitful discussions.
References (77)
An analysis of terminal conditions in rolling schedules
European Journal of Operational Research
(1981)- et al.
An integrated evaluation of facility location capacity acquisition and technology selection for designing global manufacturing strategies
European Journal of Operational Research
(1992) - et al.
A facilities in series capacity constrained dynamic lot-size model
European Journal of Operational Research
(1978) - et al.
A new heuristic approach for the multi-item dynamic lot sizing problem
European Journal of Operational Research
(1994) - et al.
Proportional lotsizing and scheduling
International Journal of Production Economics
(1995) The discrete lot-sizing and scheduling problem
European Journal of Operational Research
(1990)The discrete lot-sizing and scheduling problem with sequence-dependent setup costs
European Journal of Operational Research
(1994)Multi-level, single-machine lot sizing and scheduling (with initial inventory)
European Journal of Operational Research
(1996)Simulation ordering rules for single level material requirements planning with a rolling horizon and no forecast error
Computers & Industrial Engineering
(1990)- et al.
Minimizing the error bound for the dynamic lot size model
Operations Research Letters
(1995)