Solving an apparel trim placement problem using a maximum cover problem approach

A trim placement problem from the apparel industry is presented and solved. The problem is related to cutting and packing problems, which have received attention in the literature for close to 40 years. The problem is motivated by a pants layout problem involving irregularly-shaped pieces. A two-stage strategy is commonly employed, with large pieces, or panels, arranged first, followed by smaller pieces, or trim. This paper assumes the panels have been arranged, and presents an approach for placing the trim pieces into unused ‘containers’ of the stock material. Groups of trim pieces are first generated using existing polygon containment algorithms. Then, groups are assigned to containers to maximize a weighted function of the trim pieces. The mathematical programming formulation is developed, which is a generalization of the Maximum Cover Problem, a well-known problem in the location literature. Due to wide variability in branch and bound solution times, a Lagrangian Heuristic incorporating an improvement heuristic is developed. Computational experience demonstrates the effectiveness of the Lagrangian Heuristic on real pants markers. The optimal solution is found for all, and solution times are less than branch and bound in 10 out of 12 problem instances (considerably less in three), and only slightly more in the other two. Times are also less variable than branch and bound, an important characteristic with an interactive layout system.