Elsevier

Omega

Volume 26, Issue 3, 1 June 1998, Pages 355-366
Omega

Stability measures for rolling schedules with applications to capacity expansion planning, master production scheduling, and lot sizing

https://doi.org/10.1016/S0305-0483(97)00056-XGet rights and content

Abstract

This contribution discusses the measurement of (in-)stability of finite horizon production planning when done on a rolling horizon basis. As examples, we review strategic capacity expansion planning, tactical master production scheduling, and operational capacitated lot sizing. An iterative method to dampen the nervousness is presented.

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,…, where is a parameter of the test-bed. Note, this is an approximation, because the result for →∞ 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,…,=(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. Letq̇(i)=defjt=1T−ΔTζjtqj(t+iΔT)for 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 andsmj(i)=def|q̈(i)jq̇(i−1)j|max{q̈(i)j,1}be 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 whereSMmax(i)=defmax{smj(i)|j=1,…,J},andSMmean(i)=def1Jj=1Jsmj(i),

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)

  • S.D. Wu et al.

    One-machine rescheduling heuristics with efficiency and stability as criteria

    Computers & Operations Research

    (1993)
  • A. Nagar et al.

    Multiple and bicriteria scheduling: a literature survey

    European Journal of Operational Research

    (1995)
  • K.R. Baker et al.

    An analytic framework for evaluating rolling schedules

    Management Science

    (1979)
  • J.D. Blackburn et al.

    Alternative approaches to schedule instability: a comparative analysis

    International Journal of Production Research

    (1987)
  • G.M. Campbell

    Master production scheduling under rolling planning horizon with fixed order intervals

    Decision Sciences

    (1992)
  • R.C. Carlson et al.

    Less nervous MRP systems: a dynamic economic lot-sizing-approach

    Management Science

    (1979)
  • R. Hayes et al.

    Explaining observed productivity differentials between plants: implications for operations research

    Decision Sciences

    (1985)
  • D.H. Kropp et al.

    Concepts, theories and techniques—heuristic lot-sizing approaches for dealing with MRP system nervousness

    Decision Sciences

    (1983)
  • H. Mather

    Reschedule the reschedules you just rescheduled—way of life for MRP?

    Production and Inventory Management Journal

    (1977)
  • R. Minifie et al.

    Survey of MRP nervousness issues

    Production and Inventory Management Journal

    (1986)
  • V. Sridharan et al.

    Freezing the master production schedule under rolling planning horizons

    Management Science

    (1987)
  • D.C. Steele

    The nervous MRP system: how to do battle

    Production and Inventory Management Journal

    (1975)
  • H. Tempelmeier et al.

    A lagrangean-based heuristic for dynamic multi-level multi-item constrained lotsizing with setup times

    Management Science

    (1996)
  • S.B. Lee et al.

    Multifacility-type capacity expansion planning: algorithms and complexities

    Operations Research

    (1987)
  • G.D. Eppen et al.

    A scenario approach to capacity planning

    Operations Research

    (1989)
  • C.O. Fong et al.

    The multiregion dynamic capacity expansion problem, part I

    Operations Research

    (1981)
  • C.O. Fong et al.

    The multiregion dynamic capacity expansion problem, part II

    Operations Research

    (1981)
  • R.J. Giglio

    Stochastic capacity models

    Management Science

    (1970)
  • A.J. Kalotay

    Capacity expansion and specialization

    Management Science

    (1973)
  • H. Luss

    Operations research and capacity expansion problems: a survey

    Operations Research

    (1982)
  • H. Luss

    A multifacility capacity expansion model with joint expansion set-up costs

    Naval Research Logistics

    (1983)
  • H. Luss

    A heuristic for capacity planning with multiple facility types

    Naval Research Logistics

    (1986)
  • A.S. Manne

    Capacity expansion and probabilistic growth

    Econometrica

    (1961)
  • V. Verter et al.

    Facility location and capacity acquisition: an integrated approach

    Naval Research Logistics

    (1995)
  • P. Afentakis

    Simultaneous lot sizing and sequencing for multistage production systems

    IIE Transactions

    (1985)
  • H. Gabbay

    Multi-stage production planning

    Management Science

    (1979)
  • A. Zahorik et al.

    Network programming models for production scheduling in multi-stage, multi-item capacitated systems

    Management Science

    (1984)
  • Drexl, A. and Kimms, A., Lot sizing and scheduling—survey and extensions. European Journal of Operational Research,...
  • Cited by (0)

    View full text