Heterogeneous prestressed precast beams multiperiod production planning problem: modeling and solution methods

Abstract

A prestressed precast beam is a type of beam that is stretched with traction elements. A common task in a factory of prestressed precast beams involves fulfilling, within a time horizon, the demand ordered by clients. A typical order includes beams of different lengths and types, with distinct beams potentially requiring different curing periods. We refer to the problem of planning such production as heterogeneous prestressed precast beams multiperiod production planning (HPPBMPP). We formally define the HPPBMPP, argue its NP-hardness, and introduce four novel integer programming models for its solution and a size reduction heuristic (SRH). We perform computational tests on a set of synthetic instances that are based on data from a real-world scenario and discuss a case study. Our experiments suggest that the models can optimally solve small instances, while the SRH can produce high-quality solutions for most instances.

Appendix 1: Symmetry breaking constraints

As we can see from the solutions of all proposed models, there may be many symmetric solutions. For example, if we change the order of production of the patterns in mold 13 of the solution shown in Fig. 2 we would get the same solution with a different representation. We call this a period-based symmetry. The same occurs when we move the patterns produced in a mold to another one, for example, if we move the produced patterns on mold 14 to mold 15 and vice versa of the solution shown in Fig. 2 we would get the same solution with a different representation. We call this a mold-based symmetry. In order to circumvent this problem and, consequently, improve the running times of the models we define two sets of constraints for breaking both period and mold-based symmetries:

$$\begin{aligned}&\sum _{i \in Q^*(m)} i\;x_i^{m,t} \le \sum _{i \in Q^(m)} i\;x_i^{m,t+1} + r x_0^{m,t+1}, \quad m = 1, \ldots , M, \;t = 1, \ldots , T -1 \end{aligned}$$

(21)

$$\begin{aligned}&\sum _{t = 1}^T \sum _{i \in Q^*(m)} i\;t\;x_i^{m,t} \le \sum _{t = 1}^T \sum _{i \in Q^*(m+1)} i\;t\; x_i^{m+1,t}, \quad m = 1, \ldots , M -1. \end{aligned}$$

(22)

Constraints (21) state that patterns will be fabricated in a crescent order of indexes in the molds. Constraints (22) define that molds will be used for patterns production in a crescent order defined by the value of $\sum _{t = 1}^T \sum _{i \in Q^*(m)} i\;t\;x_i^{m,t}$ for each mold m. Thus, it is easy to see that Proposition 2 is true.

Proposition 2

Addition of symmetry breaking constraints does not modify the optimal solution value of any of the proposed models.

Although considering symmetric solutions increases drastically the problem’s search space and symmetry breaking constraints reduce the number of solutions greatly, we noted, during preliminary computational tests, that the usage of these constraints made the models much bigger and hard to solve. The models required greatly more memory and execution time than before and their insufficient solution performance led us to not consider such constraints in our larger computational tests.