Two-Dimensional Irregular Knapsack Problem with Defects from a Dynamic Textile Environment

The production of clothing, garments, footwear, and other related goods involves cutting fabric and leather rolls. High-quality goods must be free of defects, and the cutting process must be optimized to improve all stages. The problem emerges from a dynamic textile production environment in which a large object is first scanned for defective areas and then cut into smaller irregular items free of defects. The time to define the cutting pattern is short and depends on knowing the defects first. This paper proposes an iterated local search-based heuristic as a solution method to the two-dimensional irregular knapsack problem, which is an NP-hard problem. The algorithm starts by generating an initial random solution, which is then improved using perturbation and local search operators based on swap and insertion moves. Items are positioned in the large object with the bottom-left positioning rule. Experiments are conducted on instances from the literature, evaluating the solution quality for different time limits. The algorithm achieves satisfactory solutions from as early as a 30 s time limit, occupying an average of 75.63% of the object area. The occupied area increases as the time limit increases, reaching 77.78% on average for a time limit of 120 s.