Parça yerleştirme algoritmalarının postal oluşturma problemine uygulanması

Abstract

Bu tezde, endüstride geniş uygulama alanları bulunan parça yerleştirme problemi ele alınmıştır. Özel olarak tekstil sektöründeki "Otomatik Pastal Hazırlama" işlemine uygulanması ele alınmıştır. Problem iki ana kısımda incelenmiştir, dikdörtgen parçaların ya da çokgenlerin kapsayan dikdörtgenlerinin yerleştirilmesi ve doğrudan çokgen yerleştirme. Çalışmada algoritmik geometri yöntemleri ile sezgisel yaklaşımların kaynaştırılması yoluna gidilmiştir. Birinci kısım, dikdörtgen yerleştirme, iki ana adımdan oluşur: Hangi parçanın yerleştirileceği karan ve seçilen parça için uygun bir konum bulunması. Parçaların hangi sıra ile yerleşeceğine, genetik algoritmalar kullanılarak karar verilir. Verilen sıradaki parçaların yerleştirilmesi için ise sezgisel bir yaklaşım; alt-sol yaklaşımı kullanılır. Alt-sol sezgisel yaklaşımı kullanılarak, her parça sıralamasına tek bir yerleşim karşı düşürülür. Her sıralamaya yerleşim veriminin bir fonksiyonu olan uygunluk değeri atanır. Genetik operatörler kullanılarak bu uygunluk değeri, dolayısıyla da yerleşke verimi arttınlmaya çalışılır. Çokgen yerleştirmede, çokgenlerin birbirleri ile örtüşmeden yerleştirilmeleri problemi, minkowki çokgen işlemleri kullanılarak çözülür. Yerleştirilen herbir çokgen için, daha önce yerleştirilmiş çokgenlerle örtüşmeyeceği alan bulunur. Bu alan içinde kalınarak, en alt, en sol konum ya da kapsayan dikdörtgeni minimum yapan konum saptanır, parça yerleştirilir, yapı güncellenir. Tezin ikinci bölümünde yerleştirme problemlerinin genel tanıtımı ve sınıflandırılması yapılır. Üçüncü bölümde dikdörtgen parçaların yerleştirilmesi, dördüncü bölümde çokgen yerleştirilmesi incelenir.

Part Nesting Algorithms for Nonconvex Polygons with Application to Automatic Marker Making An essential step in the manufacture of clothing is the generation of cutting plan or marker. The marker determines how the parts that make up an article of clothing are cut from a bolt of cloth. For any marker making task, the set of parts is determined by the range of sizes and styles required for a particular cutting. The job of the marker maker is to pack the parts in a rectangle of smallest length whose width is determined by width of the bolt of cloth. Some parts may be rotated by 180 degrees or flipped. Some parts may also may be rotated a small amount, no more than 3 degrees. Parts can not be rotated by arbitrary angles because cloth has a direction called nap. The pieces are cut out of layers of cloth on a long cutting table. To improve cloth utilization, the parts for many articles are included in the same marker. The efficiency of a marker is the ratio of the sum of all parts area to the total area. Cutting process itself can have severe impacts on the company's profit, especially when material of high value is involved. A poor way of cutting may result in a large amount of trim loss which means that material and production resources have been wasted. Unfortunately generating an optimal marker (shortest marker of a given width containing a given set of parts) is NP- complete. Using a CAD system, well trained people can generate near-optimal markers manually, but this is a time consuming job. Current software for automatic makers doesn't reach human performance so they are used with human intervention. Automatic generation of markers would better enable manufacturers to keep up with customer demands for different styles and sizes. The problem of automatic marker making is a derivative of a problem known in the literature under different names such as : cutting stock, trim loss, bin packing, dual bin packing, strip packing, knapsack, loading, assortment, depletion, dividing, layout, nesting, partitioning or even capital budgeting, change making, assembly balancing, memory allocation, multiprocessor scheduling etc. These topics interest different disciplines such as Information and Computer Sciences, Management Science, Engineering Sciences, Mathematics, Operational Research. All of them have the common logical structure that there is on one hand stock of large objects and on the other hand a list of small items; and geometric combinations of small items are assigned to large objects. The problem of automatic marker is the problem of two dimensional non- convex polygon nesting. The methods for the solution of nesting problems cover a wide range of methods. These can be classified in three main groups : analytical vui methods, heuristic approaches, and others. Analytical methods are mostly used in the nesting of rectangular elements. They are too slow even for moderate sized problems because of the huge number of states that must be considered. For convex and non- convex part nesting AI approaches such as heuristic search, knowledge-based systems, case-based reasoning, neural networks etc. or improvement strategies based on ' meta-heuristics' such as simulated annealing, genetic algorithms, tabu search or other techniques like database/substitution, greedy heuristics, Monte Carlo placement, lattice packing, clustering methods are used. This work covers two dimensional translational non-convex polygon nesting. As stated in the first paragraph rotation is not allowed because of the properties of the application: cloth has a direction called nap,no rotation other than up to 3 degrees are allowed but pieces can flip about x or y axis. In this work the problem is treated in two main part: 1. Placement of rectangular pieces ( 2-D Bin packing) 2. Placement of nonconvex polygonal pieces (nesting) In the first part the pieces to be nested are approximated to rectangles, by substitution to their bounding boxes and the problem is treated like 2D bin packing problem. 2D bin packing place some rectangular boxes ( our bounding boxes) in an open ended bin ( bolt of cloth) without overlapping with each other. As 2D rectangle packing is NP-complete in order to obtain near optimal solution in reasonable time an approach based on heuristic is taken and Bottom-Left Heuristic is chosen as placement strategy. Bottom-Left Heuristic is a bottom-left stability preserving heuristic. If a rectangle is placed in a bottom-left stable position it can no more move downwards or slide to left. At any stage of the heuristic the bin contains a set of empty spaces (holes). There is always at least one hole which is the unbounded area over the placed boxes. To place a rectangle each hole is examined to find whether this rectangle fits in, some candidate places are found. The process of finding candidate places for a rectangle can be viewed as sliding a mechanical device composed from a pair of bar of length equal to the length of the rectangle, and a spring pulling them outwards. At any time the height of the bars is equal to the local maximum of the bottom subtracted from local minimum of the top, in the interval determined by the rectangle width. Whenever the height of the bars is equal or greater than the height of the rectangle to be placed, the position is marked as a candidate. After traversing each hole and extracting the candidates, the candidate that preserve bottom-left stability is taken. Then the rectangle is placed and data structure is updated to represent new configurations of the holes. For each rectangle to be packed same process is applied in the given order of the rectangles. For poorly ordered list of rectangles the algorithm can lead to bad packing but even a simple ordering of decreasing width applied to the parts to be packed leads to satisfactory results. At this point instead of using a simple ordering to improve the result, a job scheduling algorithm based on genetic algorithms is used whose output (order) is used to decide the order of rectangles to be packed in the placement stage. IX Genetic Algorithms is first described as a methodology for studying natural adaptive systems and designing artificial adaptive systems in 1975 by J.Holland. It is now frequently used as an optimization method, based on analogy to the process of natural selection in biology where from one generation to the next weak elements are eliminated and those with the best performance in the current environment (fittest) survive. GAs are widely recognized as an effective search paradigm in job scheduling. GA maintains a population of strings ( chromosomes) that encode candidate solutions to a problem. These strings are the analog of chromosomes in natural evolution. A fitness function defines the quality of the solution. In this work GA is used to improve result of BL heuristic by finding efficient ordering of rectangles to be packed. Genotype is a string of integer coding the order of rectangles. Phenotype is the arrangement obtained after packing the rectangles following the order coded in the genotype, the process has five step: 1. Initialization 2. Reproduction 3. Evaluation 4. Selection 5. Termination In the first stage a population is initialized randomly. Order based coding is used that is if N is the number of rectangle to be packed, genotype consists of an array of N integer and genotype is initialized by assigning N distinct number in the range 0-(N-l) to each element of the array. For a genotype g, i is the order of the rectangle no g[i]. A number of genotype is created to initiate the population. For each genotype correspond a fitness value, which is a function of the efficiency of the layout obtained using the order coded in the genotype. Reproduction is made simulating roulette wheel selection. To each genotype from the population is assigned a portion in the wheel proportional to its fitness function. By means of this, good genotypes have more chance to be selected. A pairs of genotypes are selected and the crossover operator is applied to them. As a the crossover operator, order base crossover is used : A cut point is randomly found, part of the genotype from start to cut point is taken from one parent and directly copied to the child, remaining part of the parent is copied to child following the order in the second parent. Child constructed with this method inherit important information from both parent but mainly from first parent. Using the crossover operator stated above a pool of child is formed. At the evaluation stage for each child its phenotype is constructed decoding the genotype and a fitness value is calculated. parentl : 1 - 2 | 3 - 4 - 5 parent2 : 5 - 4 j 3 - 2 - 1 child : 1 - 2 - 5 - 4 - 3 An example of order based crossover Selection process replace some individuals from previous population by the individuals from the child pool. Many threshold values have been tried to decide which individual to discard from previous population and which children to include. Change in the population does not always occur in a regular way in order to prevent to get stuck on a local minimum mutation operator is used. Two kind of mutation operator is defined for this application. First randomly select two integer in the genotype string and swap their place. Second operator again randomly select a rectangle and rotate it 90 degrees. Not to destroy regular conversion to a better population mutation operator is applied to the population with a low probability. Mutation operator change directly an individual in the population no selection process needed. These processes are applied to an initial population iteratively. Termination condition is a predetermined number of iteration. If in a certain stage of the iteration population got hung up to a local minimum some part of the population is replaced with randomly generated individuals. Genetic algorithms is used for its following properties: 1. GAs work with a coding of the parameter set, not the parameter themselves. 2. Gas search a population of points, not from a single point. 3. Gas use objective function information, not derivatives or other auxiliary knowledge. 4. Gas use probabilistic transition rules, not deterministic rules. It has been seen from the solutions obtained that use of genetic algorithms to schedule rectangles to be packed with BL heuristic, improve considerably solution of BL placement. Second part of the work: placement of small pieces covers a somewhat different area of research. The first part solve 2D bin packing problem. It deals mainly on the scheduling of rectangles, geometric properties of the pieces have not been taking into account. In the second part it is worked mainly on computational geometry. There are mainly three steps in the program:. Determination of all non-overlapping positions of a polygon relative to all previously placed polygons.. Selection of one of these positions, according to a selection criteria. Placement of the polygon and rearrangement of the data structure For the first step, " Minkowski Polygon Operations" is used. Outside of the resulting polygon from minkowski sum A©(-B), define all the positions, where the reference point of polygon B can be placed, without overlapping polygon A. Minkowski sum has been calculated by using ail algorithm based on sweeping. XI As selection criteria, two heuristic methods is used; Selection of the position that results in minimum bounding box of the placed polygons and selection of the bottom-left position. Minimum bounding box selection favors filling the holes, but sometimes results in dense but narrow arrangements that doesn't use all the width of the cloth, left place is too narrow to be filled and become waste. A combination of these two heuristics results in a better layout. As rearrangement of data structure; each time a new polygon is added to the layout, polygon union of the previously placed polygons with the new polygon is calculated. At each step all previously placed polygons are threaten like a unique polygon, this diminish considerably calculations. In brief this work combine computational geometry methods generally discarded by layout and packing communities, with their traditional optimization methods.