A hierarchical approach for solving an integrated packing and sequence-optimization problem in production of glued lamin
- PDF / 584,953 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 157 Views
A hierarchical approach for solving an integrated packing and sequence-optimization problem in production of glued laminated timber Heiner Ackermann1
· Erik Diessel1
Received: 4 November 2019 / Accepted: 22 June 2020 © The Author(s) 2020
Abstract Integrated packing and sequence-optimization problems appear in many industrial applications. As an example of this type of problem, we consider the production of glued laminated timber (glulam) in sawmills: Wood beams must be packed into a sequence of pressing steps subject to packing constraints of the press and subject to sequencing constraints. In this paper, we present a three-stage approach for solving this hard optimization problem: Firstly, we identify alternative packings for small parts of an instance. Secondly, we choose an optimal subset of these packings by solving a set cover problem. Finally, we apply a sequencing algorithm in order to find an optimal order of the selected subsequences. For every level of the hierarchy, we present tailored algorithms, analyze their performance and illustrate the efficiency of the overall approach by a comprehensive numerical study. Keywords Production planning · Packing problems · Scheduling · Heuristics Mathematics Subject Classification 90B30 · 90B90 · 90C59 · 90B35
1 Introduction Cutting and packing problems arise in many industrial applications, especially in production and logistics. Such problems can be characterized in various ways, for example by their dimension (one, two or three dimensional), by the shape of the items (e.g., rectangular, circular or irregular), by the structure of the packing constraints
B
Erik Diessel [email protected] Heiner Ackermann [email protected]
1
Fraunhofer ITWM, Institute for Industrial Mathematics, Fraunhofer Platz 1, 67663 Kaiserslautern, Germany
123
Ackermann and Diessel
and allowed patterns (e.g., guillotine cuts, orthogonal cuts, …) and by the type of the assortment (e.g., knapsack, bin-packing or cutting stock). For a comprehensive introduction to cutting and packing problems we refer the reader to Dyckhoff (1990). Especially in production however, one additionally needs to consider setup times between the processing of consecutive packings. In general, such sequencing problems can be described as scheduling problems with sequence-dependence setup times (Allahverdi 2015). The simultaneous consideration of both aspects gives rise to integrated packing and sequence-optimization problems. In this paper, we introduce one such problem arising in the production of glued laminated timber (glulam) in sawmills: Wood beams of different height and length shall be packed into a sequence of pressing steps subject to certain packing constraints of the press and subject to requirements on subsequent pressing steps. The packing problem can be described as a two-dimensional packing problem with exact guillotine cuts. The objective is to minimize the amount of material (waste) required in order to fill up the entire press. The sequence-optimization problem
Data Loading...
