Solving a Weighted Set Covering Problem for Improving Algorithms for Cutting Stock Problems with Setup Costs by Solution Merging

摘要

Many practical applications of the cutting stock problem (CSP) have additional costs for setting up machine configurations. In this paper we describe a post-processing method which can improve solutions in general, but works especially well if additional setup costs are considered. We formalize a general cutting stock problem and a solution merging problem which can be used as a post-processing step. To solve the solution merging problem we propose an integer linear programming (ILP) model, a greedy approach, a PILOT method and a beam search. We apply the approaches to different real-world problems and compare their results. They show that in up to 50% of the instances the postprocessing could improve the previous best solution.