Analysis of the Stochastic Skiving Stock Problem

Abstract

This study addresses the stochastic version of the one-dimensional skiving stock problem (SSP), a rather recent combinatorial optimization challenge. The tradi tional SSP aims to determine the optimal structure that skives (combines) small items of various sizes side-by-side to form as many large items (products) as possible that satisfy a target width. This study considers a single-product and multi-product cases for the stochastic SSP. First, two-stage stochastic programming model is pre sented to minimize the total cost for the single product stochastic SSP which is under random demand. Integration of the Column Generation, Progressive Hedging Al gorithm, and Branch and Bound is proposed where Progressive Hedging Algorithm is embedded in each node of the search tree to obtain the optimal integer solution. Next, the single product stochastic model is extended to the multi-product, multi random variable model with the additional costs as a large size complex model. To examine this large-sized stochastic N P-hard problem, a two-stage stochastic programming approach is implemented. Moreover, as a solution methodology, this problem is handled in two phases. In the first phase, the Dragonfly Algorithm constructs minimal patterns as an input for the next phase. The second phase executes a Sample Average Approximation method that provides solutions for the stochastic production problem with large size scenarios. Results indicate that the two-phase heuristic approach provides good feasible solutions under numerous sce narios without requiring excessive execution time. Finally, a multi-objective case for the deterministic SSP is analyzed where the objectives are minimization of the trim loss (waste), number of items in each product by considering the quality aspect, and number of pattern changes as the set-up. Lexicographic method is preferred for the multi-objective approach where preferences are ranked according to their importance. Column generation and Integer programming are further used to solve the multi-objective problem. In addition, a heuristic is proposed for the same multi objective problem.