Solution approaches for the bi-objective Skiving Stock Problem

Abstract

The Skiving Stock Problem (SSP) aims to determine an optimal plan for producing as many large objects as possible by combining small items. The skiving process may need different considerations depending on the production environment and the product characteristics. In this study, we address bi-objective 1D-SSP with two conflicting objectives. One common objective is to minimize the trim loss remaining after skiving, as removing the excess width is an extra procedure. When welding is an element of the skiving process, increasing the number of items for each product indicates compromised quality. Therefore, minimizing the number of small items for each product becomes a primary objective in such cases. To solve this bi-objective version of the NP-hard problem, we implement a Lexicographic Method (LM) in which the importance of the objectives imposes their preference orders. We propose two methodologies within the LM framework. The first methodology integrates Column Generation (CG) and Branch & Bound (B&B) to search for an exact solution. Given the excessive computational time an exact solver may require for tight or large-sized problems, we propose a heuristic method integrating the Dragonfly Algorithm (DA) and a Constructive Heuristic (CH). Real-world application results validate the exact solver and demonstrate comparable results for the heuristic solver in terms of solution quality and computational time. The efficiency of the solution methodologies for a preemptive multi-objective SSP aims to support decision-makers with make-or-buy decisions.