Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 The Combined Cutting Stock and Scheduling Problem

Given their practical relevance and their challenging nature, cutting and packing problems have been a major topic of research since many years. The typology of Wäscher et al. [7] is a good illustration of this fact. Apart from providing a wide classification scheme for these problems, it also identifies a large set of contributions for different variants of the standard problem. These variants cover different characteristics of the items and rolls and different kinds of objective functions, for example. In this paper, we address one possible variant of the problem that considers a scheduling term in the objective function related to the existence of due dates imposed on the delivery of the items. This problem has been addressed recently by Reinertsen and Vossen in [6] and Arbib and Marinelli in [1].

The combined cutting stock and scheduling problem addressed in this paper is defined as follows. We are given a set I of one-dimensional items ( | I |  = n) with sizes denoted by w i and a corresponding demand b i , i ∈ I. These items have to be cut from stock rolls of standard length W whose availability is assumed to be unlimited. For bin-packing instances, the demands b i , i ∈ I, are typically very low (near from 1), while cutting stock instances are characterized by high demands. Since the approaches devised in this paper are independent of the level of demands, we will now on refer only to the more general cutting stock case. The scheduling part of the problem is based on the fact that due dates are imposed on the delivery of each item size. As a consequence, for each item size i ∈ I, there is a corresponding due date which is denoted by d i . From a scheduling standpoint, the item sizes can be seen as jobs whose delivery is expected at most until d i units of time. Deliveries after the due dates are tolerated, but with a penalty in the objective function. Cutting one stock length is assumed to take exactly one unit of time. Hence, the time to complete the job related to an item size i corresponds to the number of stock rolls that have been cut up to the last one on which item i is cut. The objective function of the problem considers two terms: one related to the total wastage and another related to the total tardiness. Here, we will follow the approach of Arbib and Marinelli in [1], and consider that each term has the same weight in the objective function.

A similar problem has been explored by Li in [5] for the two-dimensional case with different stock lengths and jobs with different item sizes. The author considers the existence of both release and due dates, and she proposes linear programming (LP) based heuristics and non LP-based heuristics to find feasible solutions for the problem. As pointed out in [1], the models described in [5] do not ensure that an optimal solution is found for the global problem. The reason lies on the time available for each time period which defines the period length. In [6], the authors address the one-dimensional problem with due dates and no release dates. They describe an integer programming (IP) model which is an extension of the column generation model for cutting stock problems. The variables are associated to patterns indexed by time period. The planning horizon is partitioned into n distinct time periods. Then, the job related to an item size i can only be cut up to the i-th time period. Again, in [1], the authors showed that this approach may lead to sub-optimal solutions whenever an early due date first-based solution is not the optimal solution for the problem. The first exact formulation for this problem has been proposed in [1]. As in [6], the authors consider a formulation in which the variables are related to cutting patterns indexed by time period. Additionally, they use variables representing the inventory level of an item size at a given time period, and they use them in combination with equilibrium equations to identify situations of tardiness. To cope with the size of their model, the authors describe a period-splitting procedure which allows to start with larger period lengths. It consists in solving iteratively the model with shorter period lengths. The computational results provided by the authors illustrate the inherent difficulty of the problem.

In this paper, we explore a compact assignment formulation for the problem that applies to both bin-packing and cutting stock instances. We describe different inequalities to improve the quality of its continuous lower bound (Sect. 2), and we describe in particular an approach based on knapsack-based inequalities derived using dual-feasible functions (Sect. 3). To illustrate the potential of these approaches, we report on computational experiments performed on a set of benchmark instances (Sect. 4).

2 An Assignment Formulation

2.1 The Model

Let T denote the length of the planning horizon. The combined cutting stock and scheduling problem (with due dates) can be formulated with variables \(x_{i}^{t}\), for each item i = 1, …, n, and t = 1, …, T, that represent the number of items of size i that are cut at time period t. The period length is assumed to be equal to 1, and hence, there is a one to one relation between time periods and the stock rolls that are cut. The binary variables z t, t = 1, …, T, determine wether a stock roll is used or not at time period t. The tardiness of an item size i, i = 1, …, n, is measured through the binary variables \(y_{i}^{t}\), \(t = di + 1,\ldots,T\), which is defined only from the due date plus one time period until the end of the planning horizon. Variables \(y_{i}^{t}\) take the value 1 only if the item size i is cut on time period t. Hence, if \(y_{i}^{t} = 1\) for some i = 1, …, n, and \(t = di + 1,\ldots,T\), the item size will be late by at least t − d i units of time. These variables may be related to the \(y_{i}^{k}\) variables used by Arbib and Marinelli in [1]. The assignment formulation states as follows.

$$\displaystyle\begin{array}{rcl} & \mathrm{min.\ }& \sum _{t=1}^{T}z^{t} +\sum _{ i=1}^{n}\sum _{ t=d_{i}+1}^{T}y_{ i}^{t}{}\end{array}$$
(1)
$$\displaystyle\begin{array}{rcl} & \mathrm{s.t.\ }& \sum _{t=1}^{T}x_{ i}^{t} = b_{ i},\quad i = 1,\ldots,n,{}\end{array}$$
(2)
$$\displaystyle\begin{array}{rcl} & & \sum _{i=1}^{n}w_{ i}x_{i}^{t} \leq Wz^{t},\quad i = 1,\ldots,n,\ t = 1,\ldots,T,{}\end{array}$$
(3)
$$\displaystyle\begin{array}{rcl} & & x_{i}^{t} + y_{ i}^{t+1} \leq L_{ i}^{min}y_{ i}^{t},\quad i = 1,\ldots,n,\ t = d_{ i} + 1,\ldots,T,{}\end{array}$$
(4)
$$\displaystyle\begin{array}{rcl} & & z^{t} \in \{ 0,1\},\quad t = 1,\ldots,T,{}\end{array}$$
(5)
$$\displaystyle\begin{array}{rcl} & & x_{i}^{t} \geq 0\mathrm{\ and\ integer},\quad i = 1,\ldots,n,\ t = 1,\ldots,T,{}\end{array}$$
(6)
$$\displaystyle\begin{array}{rcl} & & y_{i}^{t} \in \{ 0,1\},\ i = 1,\ldots,n,\quad t = d_{ i} + 1,\ldots,T.{}\end{array}$$
(7)

As mentioned above, the objective function (1) is composed by a term related to the total wastage and another related to the total tardiness. Constraints (2) ensure the satisfaction of the demand. Constraints (3) forbid any cutting pattern that exceeds the stock length, while constraints (4) support the definition of the \(y_{i}^{t}\) variables. The values \(L_{i}^{min}\) for i = 1, …, n, may be defined as follows:

$$\displaystyle\begin{array}{rcl} & & L_{i}^{min} =\min \left \{b_{ i},\left \lfloor \frac{W} {w_{i}}\right \rfloor + 1\right \}. {}\\ \end{array}$$

2.2 Strengthening the Assignment Formulation

The LP relaxation of (1)–(7) can be strengthened by considering the following inequalities. Since a feasible solution will never use less than the stock rolls required to cut all the items, we may enforce the inequality

$$\displaystyle\begin{array}{rcl} & & \sum _{t=1}^{T}z^{t} \geq K^{min},{}\end{array}$$
(8)

where K min is a lower bound on the number of stock rolls computed for example using dual-feasible functions [3]. Assigning an item to a roll (or time period) implies that a stock roll is used at this time period, and hence, we have

$$\displaystyle\begin{array}{rcl} & & z^{t} \geq y_{ i}^{t},\quad i = 1,\ldots,n,\ t = d_{ i} + 1,\ldots,T.{}\end{array}$$
(9)

Using a stock roll at time period t + 1, \(t = 1,\ldots,T - 1\) implies that a roll has been used at time period t, and hence

$$\displaystyle\begin{array}{rcl} & & z^{t} \geq z^{t+1},\quad t = 1,\ldots,T.{}\end{array}$$
(10)

Similar constraints apply to the \(y_{i}^{t}\) variables, which translate into the following inequalities

$$\displaystyle\begin{array}{rcl} & & y_{i}^{t} \geq y_{ i}^{t+1},\quad t = d_{ i} + 1,\ldots,T.{}\end{array}$$
(11)

3 Knapsack-Based Inequalities Derived from Dual-Feasible Functions

3.1 Dual-Feasible Functions and Valid Inequalities

A function f: [0, 1] → [0, 1] is a dual-feasible function (DFF), if for any finite set \(\left \{x_{i} \in \mathbb{R}_{+}: i \in J\right \}\) of nonnegative real numbers, the following holds

$$\displaystyle\begin{array}{rcl} & & \sum _{i\in J}x_{i} \leq 1\Longrightarrow\sum _{i\in J}f(x_{i}) \leq 1. {}\\ \end{array}$$

Dual-feasible functions have been used essentially to derive lower bounds for standard cutting and packing problems. In [3], the authors showed that these functions can also be used to derive valid inequalities for IP models with knapsack constraints.

To strengthen the formulation (1)–(7), we applied the DFF mentioned below to the knapsack constraints (3). Let f be a DFF. The following inequalities derived from (3) by applying f are valid inequalities for the integer polytope of (1)–(7):

$$\displaystyle\begin{array}{rcl} & & \sum _{i=1}^{n}f\left (\frac{w_{i}} {W}\right )x_{i}^{t} \leq 1,\quad i = 1,\ldots,n,\ t = 1,\ldots,T.{}\end{array}$$
(12)

Among all the DFF, the maximal functions are those that produce non-dominated results. In our experiments, we used the following functions that were shown to be maximal in [3]:f FS, 1 (described in [4]), with \(k \in \mathbb{N}\setminus \left \{0\right \}\), and f CCM, 1 (described in [2]), with \(C \in \mathbb{R}\) and C ≥ 1.

  • \(f_{FS,1}(x;k) = \left \{\begin{array}{ll} x, &\mbox{ if }(k + 1) {\ast} x \in \mathbb{N},\\ \left \lfloor (k + 1)x \right \rfloor /k, &\mbox{ otherwise.} \end{array} \right.\)

  • \(f_{CCM,1}(x;C) = \left \{\begin{array}{cl} \left \lfloor Cx\right \rfloor /\left \lfloor C\right \rfloor, &\mbox{ if }x < 1/2, \\ 1/2, &\mbox{ if }x = 1/2, \\ 1 - f_{CCM,1}(1 - x),&\mbox{ if }x > 1/2.\end{array} \right.\)

3.2 A Cutting Plane Procedure

From the definitions given above, we define the following general cutting plane procedure for (1)–(7).

  • Cutting plane procedure

  • Solve the LP relaxation of (1)–(7) (let (z ∗, x ∗, y ∗) be the optimal solution);

  • do

    • Let f k be a DFF with parameter γ;

    • for (a given range of γ, and a given set of knapsack constraints (3)) do

      • if (inequality (12) is violated for f γ , x ∗ and the current constraint (3) )

      • then (add this inequality (12) to the LP relaxation of (1)–(7) )

    • end for.

    • Re-Solve the LP relaxation of (1)–(7) (let (z ∗, x ∗, y ∗) be the optimal solution);

  • while (stopping criteria are not satisfied).

To control the number of inequalities that are generated, we may limit the range of the DFF parameters and the number of knapsack constraints (3) from which the inequalities are derived. Furthermore, the stopping criteria may include for example the number of inequalities added to the LP relaxation or the maximum number of iterations without a significant improvement of the value of the objective function (based on a pre-defined value).

4 Computational Experiments

To evaluate the performance of the approaches devised in this paper, and in particular, the cutting plane procedure described in Sect. 3, we performed a set of computational experiments on benchmark instances. We used a set of instances taken from the same set of cutting stock instances as in [1] and for which due dates were generated, and we used values of T (the planning horizon) equal to those reported by these authors. A set of 40 instances divided in two groups of 20 instances were generated in that way. The tests were run on a PC with an i7 CPU with 3.5 GHz and 32 GB of RAM. For the optimization subroutines, we resorted to CPLEX 12.5.

In Table 1, we report on the values of the continuous lower bounds provided by the LP relaxation of (1)–(7) under the following scenarios:

  • A:  LP relaxation (1)–(7) without any cut;

  • B:  LP relaxation (1)–(7) with cut (8);

  • C:  same as B plus the cuts obtained with the cutting plane procedure of Sect. 3;

  • D:  same as C plus the cuts (9)–(11).

Table 1 Computational results
Full size table

Columns D1 to D4 extend the previous results for different parameters of the cutting plane procedure discussed in Sect. 3. Let δ, max cuts , and it denote respectively the smallest value of the violation of an inequality (12) that triggers its insertion on the model in the cutting plane procedure, the maximum number of cuts added between two consecutive resolutions of the LP relaxation, and the maximum number of iterations that we allow without an improvement of the solution value of the LP relaxation greater than 0.001. For the aforementioned scenarios C and D, the values for (δ, max cuts , it) that were used are (0. 1, 20, 20). Columns D1 to D4 in Table 1 correspond to the previous scenario D with the following pairs of values for (δ, max cuts , it):

  • D1:  (δ, max cuts , it) = (0. 1, 20, 50);

  • D2:  (δ, max cuts , it) = (0. 1, 50, 50);

  • D3:  (δ, max cuts , it) = (0. 01, 20, 20);

  • D4:  (δ, max cuts , it) = (0. 25, 20, 20).

Columns z RL and t RL in Table 1 stand respectively for the value of the optimal solution and the computing time required in the corresponding scenario. Note that we used the two dual-feasible functions described in Sect. 3 without any restriction on the domain of their parameters. Instead, we used the parameters (δ, max cuts , it) to control the number of cuts that are added to the LP relaxation.

While inequality (8) leads to a small improvement in the value of the lower bound provided by the LP relaxation of (1)–(7), the impact of the cutting plane procedure described in Sect. 3 is much more significant. On average, the value of the lower bound increased by almost 4.7 % for the first set of instances, and by 11.1 % for the second set (scenario A against scenario C). Inequalities (9)–(11) have no impact on the first set of instances, but when combined with the cutting plane procedure, the average improvement of the lower bound raises to 15 %. That can be explained by the fact that the DFF based cutting planes focus on the knapsack constraints of the model and particularly on the \(x_{i}^{t}\) variables, while inequalities (9)–(11) focus on the remaining variables of the model, thus complementing the cutting plane procedure. Considering the parameters (δ, max cuts , it), the best results in terms of the quality of the continuous lower bounds are achieved with scenario D2 for both sets of instances. The corresponding average improvement in the value of the lower bound is respectively 8.9 % and 19.2 % for the first and second set of instances. The maximum improvement in the first set of instances goes up to 30.9 %, and up to 38.1 % for the second set.

Additionally, we solved the first set of instances up to integrality with a time limit of 3600 s for branch-and-bound in a way that is similar to the approach followed in [1]. For this purpose, we used the cutting plane procedure with the definitions of scenario D. After the time limit, the value of the best lower bound was better than the bound at the root node by 13.3 %, while the average integrality gap was equal to 20.4 %, a value that is in line with the overall gaps reported in [1] while obtained using a compact formulation.