Stabilized-cycle strategy for a multi-item, capacitated, hierarchical production planning problem in rolling schedules

To analyze the capacitated, multi-item production planning problem and to decompose it into sub-problems, we make use of the supply chain planning matrix presented in Stadtler and Fleischmann (2012). The matrix classifies and decomposes supply chain planning tasks subject to their business functions (e.g., procurement, production, distribution or sales) and according to their planning horizons (e.g., long-, medium- or short-term). Production planning and scheduling tasks are classified in the production section with a medium- and a short-term planning horizon. The aim of these tasks is to find lot sizes and production sequences for machines at the lowest level of data aggregation, so they can be used for shop floor control. Thus, the lot-sizing and machine scheduling problem defines the sub-problem of the base level in our HPPS. However, lot-sizing and machine scheduling decisions depend on available machine capacities, which are defined at the master planning level. Additionally, seasonal demands usually cannot be foreseen at the base level due to the short-term planning horizon. At the top level, decisions regarding available machine capacities and seasonal inventories are made with a medium-term planning horizon. These decisions are provided to the base level.

After sub-problems are defined, planning models and strategies for the sub-problems must be chosen. According to Suerie and Stadtler (2003), planning models are differentiated regarding the characteristics of periods. If the length of a period is chosen so that several setup activities can take place in a single period, the model is characterized as a big-bucket model. The period length of a small-bucket model is rather short, permitting at most one setup per period. Subsequently, periods of a big-bucket (small-bucket) model are named macro-periods (micro-periods). Here, we distinguish between planning strategies for re-planning at the beginning of a macro-period and for re-planning during a macro-period. While the planning strategy for re-planning at the beginning of a macro-period concerns both levels, the planning strategy for re-planning during a macro-period only affects the base level. A rolling schedule strategy is used for re-planning at the beginning of a macro-period and the static–dynamic uncertainty strategy is used for re-planning during a macro-period.

For determining production sequences on a single capacitated machine and defining the production volume per product and micro-period for a short-term planning interval, we propose the proportional lot-sizing and scheduling problem (PLSP)—a small-bucket model—presented in Haase (1994). The PLSP determines the sequence and lot sizes for multi-items on a single, capacitated machine while considering setup and inventory-holding costs.

To define additional capacity on the machine (e.g., overtime and/or additional employees) per macro-period and seasonal inventories for each product at the end of each macro-period, we use the capacitated lot-sizing problem with linked lot sizes (CLSP-L)—a big-bucket model—as presented in Suerie and Stadtler (2003). The CLSP-L determines setup activities, lot sizes and inventories for a single, capacitated machine and allows setup carry-overs from one macro-period to the next.

Using the CLSP-L at the top level, some sequencing decisions of the PLSP at the base level are anticipated. This makes the CLSP-L a predestined model in conjunction with the PLSP in an HPPS. However, using the standard CLSP-L model formulation of Suerie and Stadtler (2003) is insufficient in the context of rolling schedules and demand uncertainty. Hence, we extend it in accordance with the proposals of Meistering and Stadtler (2017) for the CLSP model formulation and add further anticipation functions. Following the implementation of decisions of the PLSP in the object system, these are realized and current data are provided to the planning system by ex-post feedback prior to each re-plan in rolling schedules, see Fig. 1.

To secure that the PLSP (base level) considers instructions (e.g., available capacities and seasonal stocks) of the CLSP-L (top level), the models are linked by appropriate linking constraints. To avoid instructions from the CLSP-L which result in either expensive or, even worse, infeasible solutions of the PLSP, suitable anticipation functions for the CLSP-L are needed. Such functions aim to anticipate the impact of instructions from the CLSP-L to the PLSP. By following a classic top–down signal, direct reactions of the PLSP to the CLSP-L are omitted in the HPPS.

The coordination of models takes into account different levels of data aggregation between planning levels. First, the planning interval length differs among planning models. While the CLSP-L considers a medium-term planning interval of \({\bar{t}}\) macro-periods, the PLSP considers a planning interval of up to \(t^{\mathrm{B}}\) macro-periods split up into \({\bar{s}}\) micro-periods. To distinguish data and variables of the PLSP (base level) from those used in the CLSP-L (top level), these are indicated by superscripts. Here, superscript B stands for “base level” and superscript T represents the “top level”. Data and variables without a superscript are valid for both planning levels. Second, both planning levels are using the same aggregation of data for products: see Table 1. This holds true for setup costs, which come up for setup activities. Third, in contrast to setup costs, inventory-holding costs are aggregated from the base level to the top level. The same applies for the machine capacity, expected demands and variance of demands. Fourth, the aggregation of safety stocks is slightly different. Here, we use expected demands and the variation of demands in the disaggregated form of the base level for calculating safety stocks for each product j, micro period s and each (integer) production cycle length (\(\tau ^{\mathrm{B}}\)). Safety stocks are calculated by the optimization model of Tempelmeier (2011). Subsequently, we aggregate the safety stocks (\(s^{\mathrm{B}}_{j,s,s+\tau ^{\mathrm{B}}}\)) depending on the production cycle length in micro-periods to safety stocks (\(s^{\mathrm{T}}_{j,t,t+\tau ^{\mathrm{T}}}\)) depending on the production cycle length in macro-periods: see Fig. 2. This is done by setting the maximum safety stock of all production cycle lengths in micro-periods (\(\tau ^{\mathrm{B}}\)) belonging to the production cycle length of a macro period (\(\tau ^{\mathrm{T}}\)). This must be done for at least two reasons. First, the safety stock level does not necessarily increase continuously with an increasing production cycle length if the optimization model of Tempelmeier (2011) is used. Second, to offer the PLSP enough freedom for sequencing, the CLSP-L should use the highest safety stock size for a production cycle length in macro-periods (\(\tau ^{\mathrm{T}}\)) as might be needed, by mapping the cycle in micro-periods (\(\tau ^{\mathrm{B}}\)).

In the following section, we extend the CLSP-L model formulation of Suerie and Stadtler (2003) as presented in Meistering and Stadtler (2017). First, we incorporate safety stocks depending on the production cycle length (subsequently called dynamic) to better cope with demand uncertainty. Therefore, safety stocks are determined internally by the model, corresponding to the actual production cycle length, which might vary in the planning interval. Note that safety stocks for different cycle lengths must be provided to the model as data. Thus, they must be determined in advance for every product j, period t and production cycle length \(\tau ^{\mathrm{T}}\). Second, the looking beyond the planning horizon approach of Stadtler (2000) is applied to the model formulation to reduce the truncated horizon effect. Third, soft-capacity constraints are used to ensure feasibility, even if capacity is insufficient. As the complexity of the extended CLSP-L is still high, we split the planning interval to reduce complexity. Only the first part (\(t=1,\ldots ,t^{\mathrm{L}}\)) considers linked lot sizes, while \(t=t^{\mathrm{L}}+1,\ldots ,{\bar{t}}\) neglects them. Thus, the top-level model is a mixture of an extended CLSP-L and an extended CLSP.

Sets

Data

Variables

The objective function (1) minimizes setup and inventory-holding costs, costs for additional capacity units and (negative) bonus payments for production cycles ending beyond the planning horizon, under the assumption of deterministic demands.subject toEquation (2) balance inventories, backlogs and lot sizes while ensuring demand fulfillment for each product j and period t. As situations in which given safety stocks (\({\text{ss}}^{\mathrm{T}}_{j,t,t+\tau }\)) for a production cycle yield negative values might exist, inventory balance constraints have to incorporate authorized backlogs (\({\text{BL}}^{\mathrm{T}}_{j,t}\)). \({\text{BL}}^{\mathrm{T}}_{j,t}\) are restricted by the provided (negative) safety stocks due to constraints (10) and (19). Constraints (3) limit the production time of each period to the regular capacity (\(b^{\mathrm{T}}_{t}\)) and the additional capacity (\(C^{\mathrm{T}}_t\)). The use of \(C^{\mathrm{T}}_t\) is linked to (high) costs (\({\text{pc}}^{\mathrm{T}}_t\)). Thus, the model only uses \(C^{\mathrm{T}}_t\) if \(b^{\mathrm{T}}_t\) is insufficient. Constraints (4) secure that the machine is set up if a production is scheduled for product j in period t. Within the first part of the planning interval, two options exist. First, the setup state of the machine is carried over from period \(t-1\) to period t (\(W^{\mathrm{T}}_{j,t} = 1\)). Second, a setup activity is needed for product j in period t (\(Y^{\mathrm{T}}_{j,t} = 1\)). In the second part of the planning interval (\(t>t^{\mathrm{L}}\)), only the latter exists. Constraints (5)–(8) only apply for linked lot sizes, i.e., for periods \(t=1,\ldots ,t^{\mathrm{L}}\). Equalities (5) ensure that precisely one setup state is carried over from period \(t-1\) to period t. Constraints (6) ensure that for each product j there is at most one setup activity in period t or a setup state carry over from period \(t-1\) to t, or a single-item production of any product other than j. Furthermore, constraints (7) ensure that an exclusive production of product j in period t requires a setup carry-over from \(t-1\) up to period \(t+1\) (\(W^{\mathrm{T}}_{j,t}=W^{\mathrm{T}}_{j,t+1}=1\)). The range of \(QQ^{\mathrm{T}}_{j,t}\) is restricted by constraints (8).

To choose the correct safety stock for a production cycle and to consider the looking beyond the planning horizon approach of Stadtler (2000), we adopt constraints (9)–(15) presented in Meistering and Stadtler (2017). Compared to Meistering and Stadtler (2017), we only added the setup state carry-over variable (\(W^{\mathrm{T}}_{j,t}\)) for periods within the time interval allowing linked lot sizes in Eq. (12). Hence, Eq. (12) ensure that each setup period or setup state carry-over defines the end of a production cycle. All other equations are equal to the ones presented in Meistering and Stadtler (2017).Constraints (16)–(18) define the initial states of \({\text{BL}}^{\mathrm{T}}_{j,t}\), \(I^{\mathrm{T}}_{j,t}\) and \(W^{\mathrm{T}}_{j,t}\). Finally, constraints (19)–(26) set the domains of the decision variables. Note that additional capacities (\(C^{\mathrm{T}}_{t}\)) are limited to the external parameter \(z^{\mathrm{T}}_{\mathrm{max}}\), see (20).To accelerate the solving process of the CLSP-L, we add three kinds of valid inequalities. First, we extend the model formulation by inventory/setup inequalities proposed in Suerie and Stadtler (2003) (here documented in Appendix 1). The second set of valid inequalities used is the capacity/single-item production inequality set presented in Suerie and Stadtler (2003) (Appendix 2). Third, we add further valid inventory inequalities presented in Meistering and Stadtler (2017) (Appendix 3).

Next, we extend the PLSP model formulation of Haase (1994) by dynamic safety stocks and soft capacity constraints.

Sets

Data

Variables

The objective function (27) minimizes inventory-holding, setup, and penalty costs for additional capacity units assuming deterministic demands. Inventory-holding costs are only taken into account at the end of each \({\text{sf}}^{\mathrm{Dth}}\) micro-period. Aiming to schedule production as early as possible within the first macro period t, we renounce holding costs for the first macro-period and offer an incentive for early production by adding small values (multiples of \(\epsilon\)) for inventory-holding in the first macro period.subject toConstraints (28)–(32) are the well-known PLSP constraints (Haase 1994). Equation (28) represents inventory balance constraints extended by the authorized backlogs. Authorized backlogs are restricted to the absolute negative safety stocks determined by constraints (38) and (48). Constraints (29) ensure that the sum of the regular capacity and the additional capacity is not exceeded by the capacity requirements of the production volume. Since additional capacity units are linked to high penalty cost coefficient (\({\text{pc}}^{\mathrm{B}}_s\)), the model only chooses them if the regular capacity (\(b^{\mathrm{B}}_{s}\)) results in an infeasible solution. Constraints (30) ensure that product j can only be produced in period s if the resource is set up for it. Furthermore, constraints (31) link the setup activity variables (\(Y^{\mathrm{B}}_{j,s}\)) to the setup state variables (\(W^{\mathrm{B}}_{j,s}\)). The special aspect of the PLSP is that precisely one setup state carry-over of product j from period s to \(s+1\) (Eq. (32)) exists and that, at most, one setup activity is allowed per period s (Haase 1994). Note that lot sizes can be produced over one period or several consecutive periods. Consequently, the number of products produced in a period s is limited to two. With two products per period maximum, the production sequence for the shop floor control is set as follows: the product j with the setup state carry-over from \(s-1\) to s (\(W^{\mathrm{B}}_{j,s-1}=1\)) is scheduled first and the product j with the setup activity in period s (\(Y^{\mathrm{B}}_{j,s}=1\)) is scheduled second.Furthermore, we extend the PLSP model formulation by equations (33)–(40) to ensure that the PLSP chooses the correct safety stock for every production cycle. The functionality of Eqs. (33)–(38) is similar to the functionality of Eqs. (9), (10), and (12)–(15) of the CLSP-L (see also Meistering and Stadtler 2017). The only difference is that we neglect the looking beyond the planning horizon approach of Stadtler (2000) in the PLSP model formulation as final inventories/backlogs are set by Eqs. (39) and (40) to externally given parameters provided by the CLSP-L. Equation (35) ensures that the last production cycle of each product ends in the last period of the planning interval. Due to externally given initial and final inventories as well as the limited capacity and limited setup activities per micro period s, the PLSP might result in infeasible solutions. To counteract such situations, the minimum inventory and maximum backlog constraints (37) and (38) are only considered for micro-periods s that do not belong to the first macro-period. However, relaxing constraints (37) and (38) enable the PLSP to have both positive inventories and backlogs of product j in micro-periods of the first macro period. In combination with the objective function (27), which offers an incentive for positive inventories during the first macro-period, the model formulation results in an unbounded solution. To prevent this, we extended the PLSP model formulation by inequalities (41) and (42). Due to binary variables \(N^{\mathrm{B}}_{j,s}\), backlogs are bounded by \(m^{\mathrm{BL}}_{j,s}\) and either backlogs or a positive inventory will exist at the end of a micro-period s in the first macro-period.withFinally, constraints (45)–(47) set initial states of \({\text{BL}}^{\mathrm{B}}_{j,s}\), \(I^{\mathrm{B}}_{j,s}\), and \(W^{\mathrm{B}}_{j,s}\) and constraints (48)–(55) define domains of decision variables. Note that additional capacities (\(C^{\mathrm{B}}_{s}\)) are limited to the externally given integer value \(z^{\mathrm{B}}_{\mathrm{max}}\), see (49).We add valid inventory inequalities (56) to set lower bounds for end-of-period inventories of each setup period by adding up period demands beyond the setup period and the safety stocks belonging to the production cycle. Here, inventories for product j are bounded by the safety stocks required, if the preceding lot size is started before the planning interval (first term of right hand side), or the safety stocks plus demand covering \(\tau ^{S}\) micro periods, if a lot size is started in period \(s-1\) (second term of right hand side).

The main coordination problem between the planning levels of the HPPS addressed here is converting the products’ lot sizes into a feasible production sequence with minimal costs. While the PLSP takes the production sequence into account, the CLSP-L—except for the first and the last scheduled products—neglects the production sequence within a macro-period. The first and the last scheduled products are determined by the setup state carry-over variables. All other products that are planned to be produced in a macro-period are scheduled without any specific sequence.

As usual, the CLSP-L assumes that demand is due at the end of a macro-period. Hence, the production sequence during a macro-period has no impact on demand fulfillment. However, the PLSP assumes that demand will be due at the end of a micro-period. Thus, the production sequence is important for demand fulfillment. Therefore, the aim of coordination is that CLSP-L instructions provide the PLSP a sufficient degree of freedom for production sequencing. With a high degree of freedom, expected demands during a macro period can be fulfilled without multiple setup activities of one product in a macro-period and/or without the need of additional capacity.

As there is often no further information on the demand pattern within a micro-period, we assume that demand in a macro-period is evenly spread over its micro-periods. This is an approximate anticipation function representing a compromise between the exactness of modeling the base level and the difficulty of modeling and solving the resultant model (along the lines of Schneeweiss 2003).

A high degree of freedom for production sequencing in the PLSP would be achieved by setting the minimal inventory for each product at the end of each macro-period t such that it is sufficient to cover expected demands during the macro-period \(t+1\). This leads to an identical number of setup activities in the CLSP-L and the PLSP. However, inventory-holding costs and fill rates are unnecessarily high. Thus, a compromise between inventories and degree of freedom for production sequencing is needed to coordinate the CLSP-L and the PLSP. We propose to add functions to the extended CLSP-L model formulation for anticipating the (expected) minimal inventory for each product at the end of each macro-period (\(t \le t^{\mathrm{L}}\)).

The first anticipation function affects the minimal inventory of product j at the end of macro-period \(t-2\) if it is the last scheduled product in macro-period \(t-1\) (\(W^{\mathrm{T}}_{j,t}=1\)). By adding inequalities (57) to the CLSP-L, the inventory of product j at the end of macro-period \(t-2\) covers at least all expected demands, plus the corresponding safety stock up to the moment at which the last production in macro-period \(t-1\) begins at the latest. Note that we assume that demand can be fulfilled from production immediately and that the production rate is no less than the demand rate. The expected demand until the start of production is calculated by subtracting the expected demands during the production time (\(XD_{j,t}\)) from the expected weekly demand. Due to constraints (58), variables \(XD_{j,t}\) are forced to 0 if product j is not the last product scheduled in period t and is limited to the expected demand during the production time by constraints (59).The second function anticipates minimal inventory at the end of macro-period \(t-1\) for all products j that are neither the first (\(W^{\mathrm{T}}_{j,t}=0\)) nor the last scheduled ones (\(W^{\mathrm{T}}_{j,t+1}=0\)) in macro-period t. Since the deterministic CLSP-L will be applied in a stochastic demand setting, we expect that run-out times of those products will vary around the middle of a macro-period. Hence, inequalities (60) ensure that the inventory of each product j at the end of macro-period \(t-1\) (if \(W^{\mathrm{T}}_{j,t}=W^{\mathrm{T}}_{j,t+1}=0\)) covers at least half of the expected demands during the average production time of a macro-period t, plus the corresponding safety stock. The average utilization rate (util) must be provided externally to the CLSP-L.By adding inequalities (57)–(60) to the extended CLSP-L model formulation, the solution of the CLSP-L provides a suitable degree of freedom for sequencing decisions in the PLSP, while requiring less inventory than for the scenario, in which the minimal inventory covers at least the macro period’s demands.

If the stabilized-cycle strategy is used, we add another fill-rate based anticipation function to the CLSP-L model formulation. This should help to avoid multiple setup activities for product j within a macro-period in the production plan of the PLSP. We observed that the CLSP-L tends to link the product with the highest ratio of inventory-holding costs to setup costs from period t to \(t+1\). This indicates that linked lot-size decisions are completely cost-driven and ignore demand coverage in macro-periods \(t+1\). This might lead to high backlogs or to high costs in the PLSP. Hence, it is beneficial using the minimal fill-rate parameter (\(\beta ^{\mathrm{min}}_{j,t}\)) to determine linked lot sizes, if the stabilized-cycle strategy is used. The \(\beta ^{\mathrm{min}}_{j,1}\) parameter represents the minimal fill rate of product j that is required at the end of the first macro-period in order not to violate the target fill rate (\(\beta ^{\mathrm{tar}}_j\)) at the end of the reporting period. More details regarding \(\beta ^{\mathrm{min}}_{j,t}\) are provided in Meistering and Stadtler (2017) and in Sect. 4.5. Here, we use \(\beta ^{\mathrm{min}}_{j,1}\) to determine an expected artificial inventory (\(ai_j\)) for each product j at the end of the first macro-period, if a setup activity of product j is planned in macro-period \(t=1\). The artificial inventory is calculated by adding allowed backlogs of the first macro-period (\((1-\beta ^{\mathrm{min}}_{j,1})\cdot d^{{\rm T}}_{j,1}\)) to the initial inventory and subtracting the expected demands of the first macro-period: see equations (62). Therefore, a product j with a high \(ai_{j}\) (e.g., a product has a high initial inventory and/or a high degree of freedom of backlogs (small \(\beta ^{\mathrm{min}}_{j,1}\))) represents a high chance of ending the first macro-period without additional setups or penalized backlogs. Thus, by adding equalities (61)–(63) to the CLSP-L model formulation, the product \({\hat{j}}\) with the highest \(ai_{j}\) at the end of the first macro-period is linked to the second macro-period.with

According to the general functionality of an HPPS, the base level must consider instructions from the top level. For the HPPS presented in this article, the PLSP has to reach a given final inventory level for each product j by the end of the short-term planning interval. Furthermore, additional capacities are limited. Both, the final inventory level (\({\bar{i}}^{\mathrm{T}}_{j,t^{\mathrm{B}}}\)) and the maximum additional capacity per macro-period t (\({\bar{c}}^{\mathrm{T}}_{t}\)) are provided to the PLSP by the solution of the CLSP-L: see Fig. 3.

To ensure that the provided additional capacity per macro-period is not exceeded in the PLSP, constraints (64) are added to the PLSP model formulation. These constraints limit the sum of additional capacity units (\(C^{\mathrm{B}}_s\)) of all micro-periods s belonging to macro-period t (\(s=1+(t-1) \cdot {\text{sf}}^{\mathrm{T}},\ldots ,t \cdot {\text{sf}}^{\mathrm{T}}\)) to the provided additional capacity (\({\bar{c}}^{\mathrm{T}}_{t}\)).To ensure that the PLSP considers the final inventory provided by the CLSP-L solution for each product j by the end of the planning interval (\({\bar{s}}\)), constraints (65) and (66) are added to the PLSP model formulation.To accelerate the solution process, we reduce the solution space by fixing some binary decision variables of the PLSP with respect to the CLSP-L solution. Thus, we use constraints (67) to set all setup variables \(Y^{\mathrm{B}}_{j,s}\) of product j belonging to macro-period t and the setup state carry-over variable (\(W^{\mathrm{B}}_{j,(t-1)\cdot {\text{sf}}^{\mathrm{T}}}\)) to 0, if no link into macro-period t (\({\bar{w}}^{\mathrm{T}}_{j,t} = 0\)) and no setup activity (\({\bar{y}}^{\mathrm{T}}_{j,t} = 0\)) exist for macro-period t in the solution of the CLSP-L.

For re-plans during a macro-period, we make use of the static–dynamic uncertainty strategy. Thus, in a re-plan during a macro-period the PLSP adjusts lot sizes, while setup variables (\(Y^{\mathrm{B}}_{j,s}\)) are fixed to the production and machine scheduling plan from the beginning of the macro-period. Due to fixed setup decisions, limited machine capacity and uncertain demands, re-plans during a macro-period might result in infeasible solutions. To counteract this, we extend the PLSP model formulation for re-plans during a macro-period by further backlog variables \({\text{BL}}^{\mathrm{FEA}}_{j,s}\). Those backlogs are added to the inventory balance constraints (28), resulting in constraints (69). To ensure that \({\text{BL}}^{\mathrm{FEA}}_{j,s}\) are only used once capacity is exhausted, these are penalized within the modified objective function (68).To secure that each re-plan of the base level considers the same instructions, we propose variable planning intervals for re-plans during the macro-period (Stadtler 1988). Meaning that the last micro-period \({\bar{s}}\) of the planning interval is the same for all re-plans during a macro-period, whereas the first period of the planning interval is rolled forward with every re-plan. Thus, the length of the planning intervals varies between \(s=1,\ldots ,{\bar{s}}\) and \(s={\text{sf}}^{\mathrm{T}}-{\text{rp}},\ldots ,{\bar{s}}\), with rp as the length of the re-planning interval of the base level. For re-plans at the beginning of a macro-period, we use rolling schedule strategies for the top level and the base level. Thus, some constraints of the CLSP-L and the PLSP model formulation must be modified to ensure that setup and lot-size decisions within the frozen horizon are not revised by a re-plan. Hence, we introduce a new parameter \({\text{fh}}^{\mathrm{T}}_{j}\), which indicates the last macro-period t of the frozen part of the planning interval for product j. Here, the range of constraints (9) and (10) of the CLSP-L model formulation is adjusted to \(t= {\text{fh}}^{\mathrm{T}}_j+2,\ldots ,{\bar{t}}+1\), and the range of constraints (84), (85) and (90) is updated to \(t= {\text{fh}}^{\mathrm{T}}_j+1,\ldots ,{\bar{t}}+1\). For the PLSP model formulation, the range of constraints (37), (38) and (56) is modified to \(s = {\text{fh}}^{\mathrm{T}} + {\text{sf}}^{\mathrm{T}}+1,\ldots ,{\bar{s}}\). Additionally the range of constraints (41) and (42) is set to \(s=1,.., {\text{fh}}^{\mathrm{T}}+{\text{sf}}^{\mathrm{T}}\). Note that the major difference between the rolling schedule strategies (e.g., period-based, order-based and stabilized-cycle strategy) is the determination of frozen horizons. Thus, the determination of \({\text{fh}}^{\mathrm{T}}_{j}\) is treated differently among the strategies.

In the period-based strategy, the frozen horizon is set to a specific number of periods (Sridharan and Berry 1990). To gain high planning flexibility, the frozen horizon is usually set to the shortest possible number of periods for all products. According to Xie et al. (2003), it is beneficial to set the number of periods of the re-planning interval equal to the number of frozen periods to reduce planning nervousness. With a re-planning interval equal to the frozen horizon, \({\text{fh}}^{\mathrm{T}}_{j}\) has to be set to 0 for all products and re-plans.

In the order-based strategy, the frozen horizon of product j is set to a number of production cycles (Sridharan and Berry 1990). Thus, for a multi-item lot-sizing problem, the length of frozen horizons can differ between products. To enable re-planning for each product in each re-plan, a re-planning interval of one period is required. Hence, \({\text{fh}}^{\mathrm{T}}_{j}\) is defined as the last period of the \(X^{\mathrm{th}}\) production cycle if started in the first period, and is reduced by the number of periods of the re-planning interval before every re-plan.

If the stabilized-cycle strategy is used, no fixed frozen horizons need to be determined in advance (Meistering and Stadtler 2017). The parameter \({\text{fh}}^{\mathrm{T}}_{j}\) is set as in the order-based strategy, but might be revised if the expected fill rate (\(\beta ^{\mathrm{exp}}_{j,1}\)) of product j at the end of the first macro-period is smaller than the minimal fill rate (\(\beta ^{\mathrm{min}}_{j,1}\)) of product j that has to be reached by the end of the first macro-period. Thus, there is a great chance that the target fill rate (\(\beta ^{\mathrm{tar}}_j\)) is not violated. While \(\beta ^{\mathrm{tar}}_j\) is externally given, the fill-rate parameters \(\beta ^{\mathrm{min}}_{j,t}\) and \(\beta ^{\mathrm{exp}}_{j,t}\) are calculated by Eqs. (71) and (72). More details regarding the stabilized-cycle strategy and fill-rate parameters are provided in Meistering and Stadtler (2017).Those fill-rate parameters can also be used within the PLSP model. This is of particular relevance concerning the “unbounded” backlogs \({\text{BL}}^{\mathrm{B}}_{j,s}\) of micro-periods s belonging to the first macro-period. On the one hand, feasible and cost-minimizing solutions are reached by relaxing bounds for \({\text{BL}}^{\mathrm{B}}_{j,s}\). On the other hand, all expected demands during the first macro-period are allowed to be backordered until the last micro-period of the first macro-period. This might result in high downside deviations of actual fill rates from those given. Using \(\beta ^{\mathrm{min}}_{j,t}\), we can calculate “allowed” backlogs of product j in the current first macro-period, so that \(\beta ^{\mathrm{tar}}_{j}\) is met at the end of the reporting period (first term of the right-hand side of constraints (76)).

We further introduce new variables \({\text{BL}}^{\mathrm{PEN}}_{j,s}\) and \({\text{BO}}^{\mathrm{B}}_{j,s}\). Variables \({\text{BL}}^{\mathrm{PEN}}_{j,s}\) represent backlogs of product j in micro-period s in the first macro-period greater than the “allowed” backlogs (\((1-\beta ^{\mathrm{min}}_{j,1}) \cdot \sum _{s=1}^{{\text{sf}}^{\mathrm{T}}} d^{\mathrm{B}}_{j,s}\)). Variables \({\text{BO}}^{\mathrm{B}}_{j,s}\) indicate backorders of product j in period s. Constraints (75) set the lower bound of \({\text{BO}}^{\mathrm{B}}_{j,s}\) for each product j and period s to the difference of \({\text{BL}}^{\mathrm{B}}_{j,s}\) and \({\text{BL}}^{\mathrm{B}}_{j,s-1}\). The value of \({\text{BL}}^{\mathrm{PEN}}_{j,s}\) is determined by constraints (76). For each \({\text{BL}}^{\mathrm{PEN}}_{j}\), penalty costs (\({\text{blc}}^{\mathrm{B}}_{j}\)) are added to the objective function of the PLSP resulting in modified objective functions for re-plans at the beginning of (during) a macro-period (73) respectively (74) if the stabilized-cycle strategy is used.

In the computational study, we use some of the instances presented in Meistering and Stadtler (2017). These instances have been designed for big-bucket, lot-sizing problems. Thus, we use the data of an instance at the top level, while data for the base level are disaggregated. Each instance consists of six products, one capacitated machine and a reporting period of one year, divided into 48 macro-periods, respectively weeks (\({\bar{p}}=48\)). The planning interval at the top level is set to twelve weeks (\({\bar{t}}=12\)), including a linked-lot-size interval of eight weeks (\(t^{\mathrm{L}} = 8\)). The planning interval at the base level is set to 4 weeks (\(t^{\mathrm{B}}=4\)). Each week consists of five working days (\({\text{sf}}^{\mathrm{D}} = 5\)), which in turn consist of three shifts of 7 h each. Thus, the number of shifts belonging to a week is 15 (\({\text{sf}}^{\mathrm{T}} = 15\)), which is sufficiently large enough to schedule all products (\({\bar{j}}=6\)) within a week. The planning interval length is a compromise between finding nearby optimal solutions of the models in adequate computing times with a standard MIP solver, and covering at least two complete production cycles in the planning interval at the top level. Assuming a 24-h day, one additional working hour maximum can be used per shift (\(z^{\mathrm{B}}_{\mathrm{max}} = 1\)). This automatically results in a maximum of 15 additional working hours per week (\(z^{\mathrm{T}}_{\mathrm{max}}=15\)). The penalty costs for an additional working hour (\({\text{pc}}^{\mathrm{T}}_t = {\text{pc}}^{\mathrm{B}}_s = {\bar{t}} \cdot {\bar{j}} \cdot {\text{sc}}_j +1\)) are set to constant high values for each week/shift. Table 2 presents an overview of further parameters of the 16 instances.

The mean demand per week t over a reporting period is set to \(\mu ^{\mathrm{T}}_{j} = 1000\) for all products and instances. Here, instances with and without seasonal demand are studied. Given the seasonal factors (\({\text{sd}}^{\mathrm{T}}_{j,t}\)), the mean demand of product j in week t is \(d^{\mathrm{T}}_{j,t} = \mu ^{\mathrm{T}}_{j} \cdot {\text{sd}}^{\mathrm{T}}_{j,t}\), which is also the demand forecast for week t. At the base level, we assume that demand occurs at the end of each day. By assuming five days per week, we set the demand forecast of the last shift of a day to a fifth of \(d^{\mathrm{T}}_{j,w}\). All other shifts of a day presume a mean demand of zero. No bias and no updates of forecasts are considered. A forecast error only appears in the first period of a rolling schedule after lot-sizing and sequencing decisions have been made (Meistering and Stadtler 2017). Given the coefficient of variation (cv), the daily standard deviation of the demand is \(\sigma ^{\mathrm{B}}_{j,s} = \sqrt{(d^{\mathrm{T}}_{j,w} \cdot {\text{cv}})^{2}/{\text{sf}}^{\mathrm{D}}}\). The realized demand \(d^{\mathrm{obs}}_{j,s}\) for product j at the end of the last shift of a day is calculated by a truncated normal distribution (\(\max \{0, {\text{NV}}(d^{\mathrm{B}}_{j,s}, \sigma ^{\mathrm{B}}_{j,s})\}\)).

Sequence-independent setup costs (\({\text{sc}}_{j}\)) are set to $1000 for all products and no setup times are assumed. As proposed in Meistering and Stadtler (2017), the inventory-holding costs per product j and week t are determined by equation (79) and disaggregated to inventory-holding costs per product j and day by Eq. (80).Initial inventories are uniformly distributed in the interval [0, \({\text{EOQ}}_j\)] for all products j. The last setup \(l_j^{\mathrm{T}}\) of product j prior to the reporting period is defined subject to its initial inventory and its expected mean demand. Here, we only consider instances with mixed envisaged \({\text{TBO}}_j\). Meaning that each pair of products are assigned to the same envisaged \({\text{TBO}}_j\) of either two, three or five weeks. We execute the study either with a low (70%) or a high (85%) machine utilization rate. The target fill rate \(\beta ^{\mathrm{tar}}_j\) is set to either 95% or 98% for all products in an instance.

Each instance is repeated 30 times (\({\bar{r}}=30\)). This is equivalent to a simulation of 30 years. Since every single year is taken as a sample (with identical initial inventories and setup states), we have 30 independent samples per instance. This should be large enough for statistical analysis (Sheskin 2011).

As proposed in Meistering and Stadtler (2017), we analyze the performance of the HPPS by comparing the results of three rolling schedule strategies: the period-based, order-based, and the stabilized-cycle strategy. An overview of settings used within each strategy in re-plans at the beginning of a week is presented in Tables 3 and 4.

As mentioned in Sect. 4.5, the strategies differ in the way of freezing decisions at the top level and in minor details of their model formulations. To gain a better overview, Table 5 shows the specific model formulations used to determine lot sizes and machine schedules at different planning levels and different planning times.

The top level provides instructions to the base level for the first four weeks. Instructions generated by the CLSP-L contain the available additional capacity per week, the target inventory for each product j at the end of the fourth week and allowed setup activities per week. For re-plans during a week, the static–dynamic uncertainty strategy is used in all strategies. Penalty costs for using a ’feasibility’ backlog (\({\text{BL}}^{\mathrm{FEA}}_{j,s}\)) in re-plans during a week are set to high costs (e.g., \({\text{pen}}^{\mathrm{FEA}}_j = {\text{pc}}^{\mathrm{B}}_s+1\)). This ensures that \({\text{BL}}^{\mathrm{FEA}}_{j,s}\) are only chosen by the model if there are no other means.

First, we study the rolling schedule strategy with period-based frozen horizons. As can be seen from Table 3, only the first week’s decisions of the top-level planning interval are fixed, while decisions for all other weeks are subject to revision. The re-planning interval is set to the first week. In a re-plan at the base level at the beginning of a week, production volume and setup decisions are made for the upcoming 60 shifts. While all setup decisions within the first week are realized, the production volume might be revised by the daily re-plan. Note that setup activities are only allowed at the base level if they were planned by the top level.

Second, the order-based rolling schedule strategy is considered. Here, product-specific, order-based frozen horizons are used for freezing decisions at the top level. Therefore, a product’s frozen horizon is equal to the first production cycle length, if it started in the first period of the planning interval. Using the same re-planning interval as the period-based strategy, only decisions beyond a product’s frozen horizon may be revised in re-plans at the top level. The re-planning strategy at the base level is similar to the one described in the period-based strategy.

Third, the stabilized-cycle strategy is used for production planning and scheduling. As in the period-/order-based strategy, the re-planning interval is set to the first week at the top level. No fixed frozen horizons are defined, but decisions within the re-planning interval are fixed. As in Meistering and Stadtler (2017), the worst-case demand scenario is set to \(d^{\mathrm{ext}}_{j,t}=d_{j,t} + 3 \cdot \sigma _{j,t}\) and the estimated fill-rate \(\beta ^{\mathrm{est}}_{j}\) is determined by the same preparatory simulation procedure with data from the top level. Again, the re-planning strategy for a re-plan during a week is similar to the one described in the period-based strategy. However, the model formulation of the PLSP used within the stabilized-cycle strategy is slightly different: see Table 5. Thus, penalty costs (\({\text{blc}}^{\mathrm{B}}_{j}\)) for a backlog that is higher than the “authorized” backlog (\({\text{bl}}^{\mathrm{allowed}}_{j}\)) must be calculated by Eq. (81). Here, penalty costs are determined subject to setup costs, target fill rate and mean demand, using data from the top level.Note that fill-rate parameters \(\beta ^{\mathrm{exp}}_{j,t}\) and \(\beta ^{\mathrm{min}}_{j,t}\) are updated before every re-plan of the top level by considering current inventories, actual fulfilled demand and expected parameters for the remaining days of the first week of the current planning interval.

The computational study has been executed on an Intel(R) Core(TM) i7 processor with a clock speed of 3.4 GHz, 16.0 GB RAM and 4 threads, using Windows 7 Professional and the same simulation environment as Meistering and Stadtler (2017). Models are implemented in Xpress-IVE (Version 1.24.12) and solved by the Xpress Optimizer (Version 29.01.10). The maximum computational time per re-plan and planning level is set to 100 s. While we observed that some re-plans at the beginning of a week do not yield optimal solutions within the computational time limit, all re-plans during a week reach optimal solutions. For the sake of completeness, mean optimality gaps per planning level for re-plans at the beginning of a week are presented in Tables 6, 7, 8 (i.e., CLSP-L Gap and PLSP Gap). The optimization model of Tempelmeier (2011) is used in combination with the binary search heuristic of Manna and Waldinger (1987) to determine safety stocks.

The performance of each strategy is analyzed by two indicators: mean downside deviation (\({\text{DD}}_{{\bar{r}}}\)) of the actual fill rates (\(\beta _{j,r}\)) of products j at the end of reporting periods in repetition r from the target fill rate (\(\beta ^{\mathrm{tar}}_j\))(see Eq. 82), and actual mean costs (\(\overline{c_{r}}\)) based on inventory-holding and setup costs of realized decisions in repetition r (see equation 83).Beside mean downside deviations and mean costs, Tables 6, 7, 8 contain the mean proportion of the prematurely aborted cycles (\(\overline{\text{ac}}\)) for each strategy. This provides insights into the planning nervousness of the strategies. Note that all strategies are unable to solve the HPPS for the same two repetitions in two instances with seasonal demand and a cv of 0.3. Thus, only 28 repetitions are used for validating the performance for these instances, which are marked by asteriks in Tables 6, 7, 8.

As shown in Tables 6, 7, 8, the stabilized-cycle strategy is the best strategy subject to \({\text{DD}}_{{\bar{r}}}\) for all instances. The order-based strategy is the best strategy regarding \(c_{{\bar{r}}}\) for all instances. Both, the period-based (\(\triangle \overline{c_{{\bar{r}}}} = 14.70\%\)) and the stabilized-cycle strategy (\(\triangle \overline{c_{{\bar{r}}}} = 7.38\%\)) result in higher costs compared to the order-based strategy. However, the order-based strategy does not ensure that the target fill rate is at least reached on average over all 30 repetitions and products. This results in rather high \({\text{DD}}_{{\bar{r}}}\). The stabilized-cycle strategy leads to lower \(c_{{\bar{r}}}\) and less \({\text{DD}}_{{\bar{r}}}\) than the period-based strategy for all instances. Thus, the stabilized-cycle strategy is superior to the period-based strategy. However, the evaluation of strategies is bi-criteria meaning that it is impossible to trade off an increase of \(c_{{\bar{r}}}\) and a decrease of \({\text{DD}}_{{\bar{r}}}\). Hence, no clear conclusion regarding the stabilized-cycle and the order-based strategy can be drawn without preference information of the decision-maker.

Further insights are possible, if we take a closer look at the specific instances. As can be seen in Tables 7 and 8, the order-based strategy result in greater costs in four instances (\(\beta ^{\mathrm{tar}}_{j} = 0.98\) and \({\text{cv}}=0.3\)) than the stabilized-cycle strategy for the same instance with \(\beta ^{\mathrm{tar}}_{j} = 0.95\), see Table 9. Because the corresponding \({\text{DD}}_{{\bar{r}}}\) of the stabilized-cycle strategy are lower than those of the order-based strategy—if calculated for a \(\beta ^{\mathrm{tar}}_j = 0.95\)—the stabilized-cycle strategy is superior to the order-based strategy for these instances. For other instances, the stabilized-cycle strategy at least provides solutions with a clearly smaller \({\text{DD}}_{{\bar{r}}}\) and only a minor increase in costs compared to the order-based strategy. Thus, the stabilized-cycle strategy weakly dominates the order-based strategy.

For a better understanding of the numerical results (Tables 6, 7, 8), Fig. 4 shows the costs per reporting period and the fill rates per product and reporting period for the instance \(95\%/70\%/0.3\) with constant demands. Evidently, mean costs per reporting period are lowest (\(c_{{\bar{r}}} = 185{,}473.66{\$}\)) for the order-based strategy. However, there is not even one reporting period in which all products reach at least the target fill rate of 0.95. This leads to a rather high mean downside deviation (\(DD_{{\bar{r}}} = 3.03\%.\)). If the period-based strategy is used, the mean costs (\(c_{{\bar{r}}} = 209{,}367.67{\$}\)) and the mean fill rates (\(\beta ^{{\bar{p}}}_{{\bar{j}}} = 98.01\)) are the highest among the studied strategies. However, there are still reporting periods in which some products do not reach the target fill rate. This results in a mean downside deviation of 0.84 percentage points.

If the stabilized-cycle strategy is used, almost all products reach the target fill rate at the end of each reporting period. In only seven out of the 30 years, one product out of six misses the target fill rate by only a narrow margin. This results in the lowest mean downside deviations (\({\text{DD}}_{{\bar{r}}} = 0.03\%\)) among the three strategies. While the stabilized-cycle strategy results in lower mean costs than the period-based strategy (\(\triangle c_{{\bar{r}}} = -\,5.69\%\)), it leads to higher mean costs than the order-based strategy (\(\triangle c_{{\bar{r}}} = 6.46\%\)) for the instance \(95\%/70\%/0.3\) with constant demand.