Two-phase heuristics for solving two-dimensional skiving and cutting stock problem

A two-dimensional skiving and cutting stock problem (2D-SCSP) presents a significant challenge in various industries, requiring advanced optimization techniques. Addressing this intricate problem holds the potential to optimize material utilization and operational efficiency, crucial for modern manufacturing processes. The exist- ing column and row generation method (C&R), introduced by Wang et al., provides a mathematical foundation but encounters challenges, particularly in the non-linear row- generating sub-problem. To overcome these challenges, we propose a two-phase heuris- tic method for 2D-SCSP. The first phase involves clustering techniques, utilizing a fre- quency distribution table (FDT) and agglomerative hierarchical cluster (AC) to generate suitable coil groups. The second phase employs two mathematical models, PGM1 and PGM2, along with corresponding heuristics, HPGM1 and HPGM2, for pattern gener- ation. Performance testing indicates that the combination of AC and PGM2 outper- forms C&R, while FDT and HPGM1, as well as AC and HPGM1, yield comparable results with significantly faster execution. Despite its speed, the combination of AC and HPGM2 falls short of achieving satisfactory objective values.