EURO 2024 Copenhagen
Abstract Submission

771. Hybrid Biased Random Key Genetic Algorithm For The Capacited Multi-Period Cutting Stock Problem with Setups

Invited abstract in session MB-49: Integrated lot-sizing problems, stream Lot Sizing, Lot Scheduling and Production Planning.

Monday, 10:30-12:00
Room: M1 (building: 101)

Authors (first author is the speaker)

1. Eduardo Silva
ICT, UNIFESP
2. Silvio Alexandre de Araujo
Departamento de Matemática, Universidade Estadual Paulista-UNESP
3. Antonio Chaves
UNIFESP
4. Raf Jans
Department of Logistics and Operations Management , HEC Montreal

Abstract

The Multi-Period Cutting Stock Problem (MPCSP) involves cutting large stock objects into small items to satisfy demands for each period while allowing for inventory. The MPCSP is a variation that integrates the well-known Cutting Stock Problem (CSP) and the Lot-Sizing Problem. Practical applications are found in the furniture and paper industries.

In CSP, the primary goal is to minimize material costs. However, real production involves auxiliary costs, like switching between cutting patterns, causing interruptions and setup costs. A desirable cutting plan has fewer patterns. Literature on pattern setups in MPCSP is limited, and when capacity constraints are considered, the problem becomes even more challenging.

Pattern-based models and column generation are common approaches for MPCSP along with another heuristics. A large number of columns in practical problems is a challenge for pattern-based models, making techniques like evolutionary algorithms an alternative approach.

This work proposes a Biased Random Key Genetic Algorithm (BRKGA) optimized by Q-Learning (BRKGA-QL) to solve MPCSP with capacity constraints and pattern setups.

The BRKGA-QL is compared with a hybrid column generation approach from the literature using benchmark instances. Results show BRKGA-QL consistently outperforms in terms of integer values across all instances.

Keywords

Status: accepted

Back to the list of papers