Different box types will share some paper grades, particularly for the fluting and less so for the top/bottom (but there is some sharing even there). For the fluting layer, in terms of surface area, 1 m 2 of box will require ~1.2 m 2 of the middle layer; the precise number is determined by the wavelength of this layer. In effect, there is a bill of materials (BoM) with an entry for each layer of a box sheet. There are so many possible variations in box characteristics (dimensions, BoM, cutouts, folding creases, printing) that in practice boxes are exclusively made-to-order.
The above is a highly simplified description of the process. There are many real-world constraints that impact the analysis; we list some of them later on.
At a corrugator there is an opportunity to combine orders of different dimensions, but with identical BoM. Because the corrugated board cannot be wound into reels (it has to remain flat), it is cut into sheets in-line; most corrugators are double-knife, i.e. can only handle two distinct sheet lengths at any time. This gives rise to a well-understood and solved semi-continuous variant of the CSP (the first published reference we can find is in 1964 [1] ; there are many companies supplying software for solving this problem for the corrugating industry; consequently, there are few academic publications). Figure 2 depicts a small, but otherwise typical, corrugator instance: , sharing a common BoM, are produced on a single corrugator using two paper reel widths (2500 mm & 2200 mm). After producing the first pattern (2 × A + B) from paper 2500 mm wide, the paper width is changed to 2200 mm to produce the second pattern (A + C). A double-knife corrugator, such as the one depicted here, only allows two different sheet lengths to be produced in any one pattern (so, the combination A+B+C would be infeasible).
Other things being equal, it is preferable to run a corrugator at its maximum width. However, this may generate too much waste (consider e.g. producing the second combination with orders A & C out of the bigger reel width) and this is what induces multiple reel widths for the inventory. Industry practice is to hold 8-12 reel widths (for each paper grade / grammage combination) in inventory at the corrugating plant. We call the list of reel widths stocked at the corrugating plants ({2200, 2500} in this example) the inventory policy. is a trade-off between the reel widths that suit the corrugator(s) and those that suit the paper machine(s). So, the fundamental question addressed by this paper is to explore this trade-off and determine a near-optimal policy.
There appears to be very little published work on this problem. The first related reference we could find is from 1983 in [2] :
"The maximum width roll of liner and medium that can be processed by a corrugator at a box plant is a function of the design of the corrugator. In addition to the maximum size roll, most plants stock a number of narrower width rolls. This decision obviously leads to an increase in box plant inventory and a reduction in corrugator productivity. The primary motivation for stocking multiple roll widths is to reduce side trim generated at the corrugator. Because side trim is such an easily measured factor, it generally dominates in the stock size selection process. This can easily lead to a proliferation of stocking sizes. The costs associated with increased inventory and reduced corrugator utilization is more difficult to isolate and measure. This inhibits making an economic tradeoff to determine the number of sizes to stock."
However, this does not consider the trim efficiency at the paper machine(s) and is therefore closer to the classical assortment problem [3] . Several commercial suppliers that offer corrugator CSP software also offer "roll stock analysis", which aims to recommend inventory policies based on historical corrugator demand. However this "analysis" is done, it only looks at the corrugator efficiency, ignoring the impact on the paper machines. The sub-optimality of the resulting solution is made more stark when we consider that the waste generated at the paper machines is often significantly higher than that at the corrugators (more about this later).
In their otherwise comprehensive look at scheduling issues in the paper industry of 2001, [4] do not discuss our problem at all. Similarly, it fails to appear in the 2009 survey [5] and follow-on 2019 survey [6] of supply chain problems in the paper industry.
We speculate that the reason for the paucity of relevant research is the computational intractability of the underlying problem, perhaps coupled with the need to link statistical aspects with combinatorial optimisation ones.
We list below some of the aspects and constraints that may be necessary in any real-world implementation:
It is possible that some of the paper grades used for corrugating boxes are supplied by external suppliers. These do not need to be taken into account at the paper machine CSP. Conversely, it is possible that the paper machines also produce paper for external demand; such demand does not directly impact the corrugating plants, but affects the CSP instances at the paper machines.
The presence of external supply of / demand for paper complicates the notion of percentage waste. This is best illustrated with an example: A paper mill produces 1,000 T, with 3% waste (30 T). Of the 970 T net production, 600 T goes to the open market and the corrugators consume the remaining 370 T. The corrugators also buy, from external suppliers, 130 T. Their input material consumption is therefore 500 T, and they incur 2% waste (10 T) on this. It is hard to defend any specific total percentage waste calculation in the circumstances. We use the convention of adding up the total waste (30 T + 10 T = 40 T) and expressing this as percentage of the total paper machine production, i.e. 4.0% in this case.
Most of the world's corrugators are double-knife, meaning they can cut up to two different sheet lengths at a time, as shown in Figure 2 . For those, industry practice is to keep 8-12 reel widths in inventory. However, triple-knife corrugators exist; these can combine three order lengths at a time. This additional flexibility reduces the number of reel widths in a near-optimal policy down to one or two.
Most corrugated boxes have three layers. However, 5-layer (double-wall) boxes are used for heavier objects. Also, some packaging scenarios call for a 2-layer material (single-facer).
Material substitution is common practice in the industry. For instance, you could substitute a 200 g/m 2 paper for one with 180 g/m 2 , therefore giving the end customer a slightly higher specification. The additional cost may be offset by other factors such as reduced trim waste or inventory / logistics costs.
When an integrated paper company receives an order for a box, it typically has to decide which corrugating plant to assign this to (box orders are almost never split across plants). This is typically decided by transportation cost and production capability considerations. Once the corrugating plant has been determined, there is a further decision as to which specific corrugator will produce this order (orders are almost never split across corrugators).
Almost all paper machines operate a production cycle, e.g. grade Testliner, basis weight 180 g/m 2 is produced every second week, followed by the same grade, basis weight 200 g/m 2 , etc. Although there is evidence that some of these cycles are sub-optimal, it is very difficult to change them, as well as being a difficult-to-solve (non-convex) optimisation problem.
In the general case, there will be multiple paper machines in multiple paper mills. As a result, there is a sourcing decision to be taken. For example, two different paper machines, of differing widths, potentially located in different mills (thus inducing differences in transportation costs) could source the same paper grade.
An integrated paper company will have many corrugating plants, each potentially with multiple corrugators. A uniform policy means that at each plant, the items that are inventoried are a subset of the overall policy. This is dictated by corrugator constraints. For instance, one plant may have a large corrugator, which is 2700 mm wide; another plant's maximum corrugator width may be 2500 mm. There is no point in the second plant holding inventory of items wider than 2500 mm. Even with a uniform policy, the quantities of each of its elements will vary by plant (as shown in Figure 2 ).
However non-uniform policies are also possible: each of the plants may have a policy of specific cardinality, but the policies can vary across corrugating plants. For example, one corrugating plant may specialise in boxes for agriculture, another plant may specialise in boxes for ecommerce. The dimensional characteristics of these could be different and there is no need for the inventory to have any common reel widths.
We present here results for uniform policies alone, but the approach naturally extends to nonuniform ones as well.
At a single corrugating plant one might have thought that in general different paper grades need different policies. However, the fact that boxes are made up of several grades creates a coupling constraint: the three input reels at any given time (for each of the box's layers) must be of the same width. The middle layer in particular (fluting) is common across many different types of boxes. In practice, a common policy across paper grades at a single plant is the industry norm.
Paper is sold by weight, reflecting the underlying material, energy and capital costs. Therefore one talks of cost per tonne for the material. However, different grades / grammages may have different production costs per tonne. This is important in our context because we want to determine the cost of a policy: if the production costs are essentially identical across grades / grammages, then we can just add the weight of the waste. On the other hand, if the production costs vary significantly, we would want to create a financial objective function reflecting the cost of the waste.
When waste is produced at the paper mill, then it is typically recycled on-site and does not incur any transportation cost. However, waste generated at the corrugating plant has to be transported back to a paper mill for recycling. Depending on the distance and the transportation modes, there might be differences between corrugating plants for these costs.
One of the fundamental difficulties in all types of inventory policy is how to adjust them to reflect demand that varies over time. As the underlying problem is combinatorial, the risk arises that an optimal policy for a particular time period is completely different from an optimal policy for another period, even if nothing else changes.
Whilst this is certainly true, we have to face the reality that integrated paper companies lack optimisation-based tools to evaluate, at least periodically, their policy. As a result, companies are often locked into policies that are inherited and sub-optimal.
The fundamental building block of our approach is the policy denoted by P. This consists of a set of reel widths that will be kept in inventory. For example, one such policy consists of {1350, 1770, 1830, 1960, 2040, 2160, 2260, 2435, 2500}. We call | P | the cardinality of P; in this example it is 9. The determination of a cost for P involves three steps:
1. Determining the waste at the corrugators for policy P 2. Determining the waste at the paper machine, using the results from the solutions that were obtained at the previous step
We describe each of these steps below.
Given a policy P and a particular CSP instance for the corrugator, we can determine , the minimum waste when using P to supply the instance by solving the corresponding CSP. For example, for the instance: At the end of this iterative process we will have determined the total corrugator waste = ∑ and the time-phased quantity for each of the policy's elements (e.g. we require 76 T of width 1830 mm of a specific grade in week 23).
On a paper machine that is 6000 mm wide, an optimal solution (allowing a tolerance of -0% / +5% on the quantity) to the corresponding CSP is: We address the more general case, where there are multiple paper machines potentially supplying the same paper grade, by solving a multi-machine CSP. This has similarities with the corrugator CSP, when using a policy with multiple widths. Figure 6 shows the same instance, but with two paper machines, 4300 mm & 6000 mm wide: Figure 6 . Optimal solution to paper machine CSP, with two paper machines, waste = 6754 kg (0.825%). Note how some sizes (e.g. the 2400 mm) are sourced from both paper machines.
By summing the waste across all paper machine CSP instances, we will have determined, for policy P, the total waste at the paper machine, wpm.
The overall cost of the policy is then defined to be z = β wcor + wpm, β > 1. The reason for β > 1 is that waste at the paper machine can be recycled on-site, whereas waste at the corrugator needs to be transported back to the paper mill(s).
It is clearly the case that if we take two CSP instances A & B (for the same master sizes) and we merge them, then the waste of the resulting solution will be no more than the sum of the original instances:
This is because all patterns that are feasible for A and B, are also feasible for A∪B. In practice, we would expect, most of the time, a strict inequality to apply. This non-linearity stops us from assembling a "giant" CSP instance, one for each corrugator. Instead, we have to use a statistical approach, where the corrugator CSP's are as representative as possible of the real ones.
In addition, one might imagine that, because the widths of a policy P are common across all paper grades, we would have to solve only one instance at the paper machine. However, the required quantities are all different and this precludes us from using such a shortcut.
Suppose that we have two policies, 1 , 2 ∶ 1 ⊆ 2 . We can easily see that 1 ≥ 2 because every solution for policy P1 is also valid for P2. For the corrugator, as we increase the cardinality, the optimal waste cannot increase.
However, we cannot draw a similar conclusion for the waste at the paper machine stage. A trivial example would be to compare the policies P1 = {2500} and P2 = {2200,2500} for a paper machine that is 5000 mm wide. Policy P1 incurs no paper machine waste, whereas P2 most definitely does.
It follows that we cannot draw any conclusions regarding z = β wcor + wpm. Somewhat counterintuitively, an optimal policy with cardinality n can be better overall than one with n+k; this phenomenon is observed in practice.
We have outlined above a process for assigning a figure of merit, related to the waste / cost, for an inventory policy P. But how can we search efficiently in the space of P?
Determining the objective function for each P is time-consuming. In a mid-sized real-world study there would be several thousand corrugator CSP instances and a few hundred paper machine CSP instances. In the test-case we report below, it takes ~30 minutes on a modern computer to determine the cost of a policy.
Searching the inventory policy space is problematic, particularly as each policy evaluation is so time-consuming. We started first searching for policies with the same cardinality as an initial, baseline, policy. Can we derive some information to guide the search? One way to do this is to assign a waste to each element of the policy, so that we can distinguish between "good" and "bad" reel widths. This is straightforward for the corrugator waste. It is not so clear for the paper machine case; we use the logic illustrated in Figure 7 : In this manner, we can distribute the total waste to each of the elements of the policy. This is a kind of sensitivity information for each reel width.
We used a tabu local search: starting from an initial policy we perturb it using a variety of "moves", some of them random, others based on the sensitivity information obtained as above.
The end result carries no optimality guarantee of course.
Every analysed policy P is compared against best policy found so far, P*. If the new policy is worse than the best, but "close", it is worth to explore further, by applying more perturbations to it. In order to limit the number of policies we perturb, we determine whether a policy is close enough to the best, by using a threshold ε, initially set to ε = 30%. If the new policy is within ε of the best, then it is close enough and we allow perturbations. This promotes diversification.
In order to favour intensification as the search progresses, we apply a decay factor δ = 0.05 on the threshold as a function of the number of analysed policies N:
If the above inequality holds, P is explored further.
Besides encouraging diversification, the search follows a "depth-first" approach, by perturbing and evaluating the best policies first. For example, if P is evaluated and turns to be the new best, it will be perturbed a number of times and the resulting new policies will be placed first in a prioritised queue of policies to analyse. This logic is applied, analogously, for each evaluated policy, no matter whether it is a new best.
Although evaluating a policy is a time-consuming task, each can be executed independently of the others. So, we can examine in parallel as many policies as the available hardware allows. Taking the number of physical processors (cores) proved to be a good value for the number of policies that can be evaluated simultaneously.
Since the heuristic has no optimality guarantee and a lower bound is very difficult to obtain, we are reduced to using statistical techniques ( [7] , [8] ) for estimating the optimal value / optimality 2500 1700 800
gap. See Figure 8 for a typical distribution of the objective function in one scenario with 436 policy evaluations: We estimate the global minimum as the location parameter of a Weibull distribution fitted to the data. For this scenario, the A* estimator for the location parameter of the Weibull distribution as recommended in [9] is 10.123%, remarkably close to the minimum actually achieved of 10.131%.
We were asked by one of our clients, with one paper mill (with a single paper machine) and three corrugating plants, to examine the following two questions:
a. Is their current inventory policy optimal?
b. If they were to replace one of the 2.5 m wide corrugators, should they buy a wider one at 2.8 m or keep to the existing size?
The data for answering these two questions consists of 5,362 corrugator instances and 124 for the paper machine.
We present results for the unrealistic case of β = 1, i.e. we treat paper machine and corrugator waste as cost-equivalent, as a means of shrouding the commercially sensitive actual results.
For question (a) we started with our client's initial policy, which had cardinality 11. The total waste for their current policy was 11.08%. The policy search identified a policy with total waste of 10.131%, a reduction of around 9%. We were also able to identify a policy with cardinality 9 (two fewer than the baseline) with even lower total waste of 9.95%.
For question (b), the empirical result was that a 2.8 m corrugator is highly advantageous without requiring an increase in the policy cardinality. With the same cardinality of 11, the total waste drops to 8.88%. This is quite surprising because the fact that the new corrugator is wider implies fewer reel widths are available for the existing ones.
The approach we have presented here is promising in identifying policies that improve on the status quo.
However, due to the heuristic nature of the search, we are troubled by the lack of a nonstatistical lower bound and this could be an interesting topic for future research. One step that would facilitate this research is improving the computational efficiency of the process -the more policies we can evaluate in a given period, the more confident we can be of the results.