Algorithms Based On The Scan Line For The Two-dimensional Irregular Strip Pakcing Problem

Nesting problems widely exist in traditional manufacturing industries,such as shipbuilding industry,leather industry,textile industry and furniture industry.In different industries,the nesting problem has different constraints.Based on the cutting and blanking scene of parts in the textile industry,this thesis solves the Two-Dimensional Irregular Strip Packing Problem（2DIRSP）in this scene,which is a core problem of the layout problem.Also known as the Nesting Problem.This scenario requires cutting irregular parts that need to be cut on a rectangular fabric with a fixed width and unlimited length,and converts the original maximized fabric utilization into a minimized fabric usage length.The improvement of the layout utilization rate can significantly and effectively enhance the economic benefits of the enterprise.Therefore,it is of great significance to study the layout of two-dimensional irregular belts.In order to better adapt to the fact that there are voids in parts and a large number of parts in the actual layout process,this thesis adopts the scanning line method as the solution of overlapping collision technology.Based on the scanline method,this thesis needs to solve two key issues of placement rules and placement order.In terms of placement rules,this thesis proposes an evaluation function based on the scanning line method;in terms of placement rules,this thesis proposes a layout algorithm framework Fast Compress Local Search Algorithm（FCLSA）based on evaluation functions.FCLSA can be divided into three main parts: first,sorting the parts according to their geometric features to obtain the initial sequence,and executing the fast solution generation algorithm to obtain the initial layout plan;second,on the basis of the initial plan,executing the compression algorithm,Obtain the limit usage length of the initial sequence;thirdly,perform a local search algorithm on the basis of the solution obtained in the second step to further compress the usage length of the rectangular fabric.After the placement order is adjusted,try to execute the decoding algorithm to obtain a valid arrangement.When the time limit is reached,the iteration is stopped,and the final layout plan is obtained.The core of FCLSA is the frequently called decoding algorithm in the compression algorithm and the local search algorithm,which is based on the evaluation function of the adaptive scanline method.By evaluating the compactness of multiple placement positions on the rectangular fabric,the decoding algorithm selects the optimal placement position for each part according to the placement order of the parts,and finally generates a layout plan.At the same time,according to the characteristics of the placement rule of the decoding algorithm,in order to improve the adjustment efficiency of the placement order,this thesis introduces a variety of adjustment operators for the local search algorithm to improve the search efficiency of the algorithm and balance the global search ability and local search ability.This thesis tests the algorithm on the European classic nesting test case.Through the comparative analysis with several other optimal algorithms,it is found that FCLSA has achieved relatively good results,and at the same time,it can better adapt to instances with irregular parts with holes and large-scale instances with layout,and has strong competitiveness.