JP6980983B2 - Material allocation system - Google Patents

Description

The present invention is a member that allocates polygonal products of various dimensions used for construction to several kinds of raw materials to be supplied and calculates how to allocate the products to the raw materials so as to minimize the raw material cost. Regarding the allocation system.

For example, when cutting rectangular products of various dimensions such as wall materials from a given raw material, various calculation methods have been developed to minimize the raw material cost (Patent Document 1).

Japanese Patent No. 5838047

Practical solution to the cutting / stuffing problem (written by Shunji Umetani)

The known conventional techniques have the following problems to be solved.
With the technique shown in Patent Document 1, for example, polygonal products other than rectangles such as trapezoids and triangles cannot be assigned. If the rectangle circumscribing each polygon is regarded as a product and assigned, there is a problem that the yield is lowered.
According to Non-Patent Document 1, the allocation of polygonal products of various dimensions is treated as a strip packing problem. The strip packing problem is the length of the raw material used by allocating polygonal products of various dimensions to be cut out to the raw material with a fixed width and a sufficiently long length, for example, a rolled iron plate. Is a problem to minimize. That is, the number of raw materials is one. On the other hand, the raw materials used to cut out building products are limited in width and length dimensions, and multiple raw materials are used to cut out polygonal products of various shapes and dimensions. It cannot be solved as a strip packing problem as it is. In addition, it is not uncommon to select and use multiple types of raw materials with different dimensions.
The present invention solves the above-mentioned problems by using a rule which is an improved arrangement (allocation) location determination rule for solving a strip packing problem in order to meet the environmental requirement of minimizing industrial waste. The purpose.

The following configurations are means for solving the above-mentioned problems, respectively.
<Structure 1>
When cutting m products with a mixture of rectangles and non-rectangular polygons used for buildings from k types of rectangular raw materials, the number of raw materials required for each type and how to allocate the product to each raw material It seeks to minimize raw material costs,
When k = 1, one raw material shall be taken out, and unallocated products for which the allocation order has been determined shall be taken out in the allocation order.
"A new raw material is taken out, and if the unallocated product taken out can be assigned by the allocation method predetermined to the raw material, the unallocated product is assigned, and the unallocated product is regarded as the assigned product.
If it is not possible to allocate, the operation to restore the unassigned product taken out while maintaining the above allocation order is performed from the first allocation order to the last unallocated product in the allocation order. " Allocate until all products are already allocated.
The first product allocation order allocation means that controls the calculation to obtain the required number of raw materials, how to allocate products to each raw material, and raw material costs.
When k> 1, the price of each raw material is set, one raw material j of the jth type from j = 1 to k is taken out, and the unallocated products for which the allocation order is defined are taken out in the allocation order.
The above-mentioned allocation processing to the extracted raw material is performed for the jth kind of raw material j, and the process is performed.
continuation,
"Now ask for products with assigned to the allocation process the raw materials j went, and the price of the raw materials j, determine the per product area price pj from the sum of the areas of the assigned product" that, the product area per price calculation processing Is executed for all k kinds of raw materials (j = 1 to k).
continuation,
"From the price per product area pj (j = 1 to k) obtained by performing the price calculation process per product area , select the cheapest price per product area pL (1 ≤ L ≤ k), and select the L type. to determine the raw material L and the combination product, the relevant product and allocated Quote, performed per product area prices comparison judgment processing,
A series of processes including the above-mentioned allocation process to the extracted raw materials, the price calculation process per product area, and the price comparison judgment process per product area are performed until all the products are allocated products.
A second product allocation order allocation method that controls the calculation to obtain the required number of raw materials for each type, the method of allocating products to each raw material, and the raw material cost.
A gene that specifies m products in which rectangles and polygons other than rectangles are mixed, and an individual generation means that generates a plurality of chromosomes having loci that arrange the genes in the selected allocation order as individuals.
The generated individual is used as a parent individual, and cross-processing, mutation processing, or selection processing is performed to generate a plurality of child individuals, and the plurality of child individuals are used as the next-generation parent individual, and generational change is repeated. , Equipped with a generational alternation means to generate individuals representing the allocation order of the above products,
When k = 1, arithmetic processing is executed by the above-mentioned first product allocation order allocation means, the individual generation means, and the generation alternation means, and the required number of raw materials and the method of allocating the product to each raw material are determined. When k> 1, the arithmetic processing by the second product allocation order allocation means, the individual generation means, and the generation change means is executed, and the number of raw materials required for each type and each raw material are obtained. A material allocation system characterized by minimizing raw material costs by seeking product allocation methods.

<Structure 2>
The orientation of the product taken out is a certain state, a state where this certain state is rotated 90 degrees, a state where it is rotated 180 degrees, a state where it is rotated 270 degrees, and these four types of states are like a mirror. The member allocation system according to configuration 1, wherein a plurality of types of states including any of the inverted states are treated as separate genes.

<Structure 3>
In the predetermined allocation method, when one of the vertices of a rectangular raw material is selected and called a specific vertex, when a new product is allocated on this raw material, the raw material having one end at the specific vertex is used. The product is moved along two directions parallel to the pair of sides of the raw material, and the position of the product is placed as close to the specific vertex as possible to the raw material, and the already assigned product is placed. In some cases, the new product cannot be assigned to the raw material by arranging the new product close to the above-mentioned specific vertex within the range where the assigned product and the new product do not overlap each other. The member allocation system according to any one of configurations 1 and 2, characterized in that the process is repeated in order.

<Structure 4>
The above-mentioned predetermined allocation method is such that the product already allocated on the rectangular raw material and the product to be allocated next share one of the vertices without causing an overlapping part with each other. The member allocation system according to configuration 3, wherein the process of arranging if possible is repeated in order until a new product cannot be allocated to the raw material.

<Structure 5>
The member allocation system according to any one of configurations 1 to 4, wherein the generation change means selects a product allocation order according to the following procedure.
(1) M random initial populations (first generation) are generated.
(2) Two parent individuals are randomly selected from the M population.
(3) M child individuals are produced from two parent individuals by crossover processing.
(4) Mutation treatment is performed on a set number of child individuals out of the obtained M child individuals.
(5) Calculate the required number of raw materials or raw material costs for a total of 2M individuals, including M parent individuals and M child individuals.
(6) Take out M individuals from the required number of raw materials or the one with the lowest raw material cost.
The next generation (second generation) individual population.
(7) Repeat the generation changes from (1) to (6) above, and finish the calculation when the required number of raw materials or the difference in raw material costs reaches the convergence test, or when the set number of generation changes is reached. do.
(8) From the smallest or near-minimum solids, select the product allocation order with reference to those chromosomes.

<Structure 6>
In the above crossing process,
Arbitrary two of the above parent individuals are designated as "parent 1" and "parent 2", and the same number of genes of the child individual that inherits a part of the gene sequence from both of them is generated as the same number as the above parent individual.
In the above mutation treatment,
Any two genes at the locus are exchanged with any of the above offspring to generate new offspring.
In the selection process of the above individual,
From the product allocation order represented by the parent individual and the child individual, the same number as the parent individual is selected from the one with the smaller number of required raw materials or the one with the lower cost of the required raw materials to be the next generation. The member allocation system according to any one of the configurations 1 to 5, wherein the member allocation system is characterized.

<Structure 7>
A computer program that causes a computer to function as the member allocation system according to any one of configurations 1 to 6.
<Structure 8>
A computer-readable recording medium on which the computer program according to configuration 7 is recorded.

When allocating a product with a mixture of rectangles and polygons other than rectangles to raw materials, a specific allocation order is set, and the above allocation order is optimized by the allocation process to the extracted raw materials and the genetic engineering method. Therefore, it is possible to obtain a higher yield than before.

It is a functional block diagram of the system of this invention. It is explanatory drawing which illustrates the raw material data used for Example 1. FIG. It is explanatory drawing which illustrates the product data used for Example 1. FIG. It is a calculation processing operation flowchart of the system of this invention. It is a flowchart of the calculation process example of the first product allocation order allocation means. It is a calculation processing example flowchart of the second product allocation order allocation means. It is a flowchart of the calculation process example of the allocation order setting method by the BL method. It is a calculation processing example flowchart of the allocation order setting method focusing on the vertices of a polygon. It is explanatory drawing of the A state of a product, the state which rotated or inverted this state, and the gene structure. It is explanatory drawing which illustrated the allocation order setting method of FIG. It is explanatory drawing which illustrated the allocation order setting method of FIG.

To minimize the raw material cost according to the present invention, the renewal of the allocation order of products by the genetic algorithm (generational change) and the calculation of the raw material cost obtained by allocating the product to the raw material by a predetermined method are alternately repeated. It is something to do. That is, first, the allocation order (first generation individual) of the product in which the rectangle and the polygon other than the rectangle are mixed is obtained, then the raw material cost (evaluation value) when the allocation order is adopted is obtained, and then. It repeats the process of finding an evolved allocation order so that an excellent allocation order remains. Hereinafter, embodiments of the present invention will be described in order.

(System configuration)
FIG. 1 is an explanatory diagram of a functional block constructed on a computer in order to realize the system of the present invention.
In this computer storage device, raw material data 12 showing information such as raw material dimensions, product data 14 showing information such as product dimensions, and the required number of raw materials (for each type) obtained as a result of arithmetic processing. 18, how to allocate products to each raw material 20, raw material cost 22, etc. are stored.

Further, for the arithmetic processing, a first product allocation order allocation means 24, a second product allocation order allocation means 28, an individual generation means 36, a generation change means 38, and the like are provided. In the middle of this arithmetic processing, the individual data 40 indicating the allocation order is repeatedly generated. The individual data 40 is data in which the order of allocation is arranged at the locus, and is data that evolves by alternation of generations.

The individual generation means 36 generates a certain number of first-generation individuals by the individual generation process. The generation alternation means 38 has a function of generating a certain number of next-generation individuals by crossover processing, mutation processing, and selection processing.

The first product allocation order allocation means 24 functions when the number of raw material types is 1, and executes allocation processing to the extracted raw materials and raw material cost calculation processing from the given allocation order ( The required number of raw materials 18 (for each type), the method of allocating products to each raw material 20, and the raw material cost 22 are calculated.

The second product allocation order allocation means 28 functions when the number of raw material types exceeds 1, and includes allocation processing to the extracted raw materials, price calculation processing per product area, and price comparison determination processing per product area. , The raw material cost calculation process is executed, and the required number of raw materials 18 (for each type), the method of allocating the product to each raw material 20, and the raw material cost 22 are obtained from the given allocation order. The method of allocating a product to each raw material 20 is used when actually cutting out a product with a processing machine.

That is, the computer of this system receives the raw material data 12 and the product data 14, and uses the individual generation means 36, the generation change means 38, the first product allocation order allocation means 24, or the second product allocation order allocation means 28. It is repeatedly operated, arithmetic processing is performed, and the minimization search process of the raw material cost 22 is executed.

(Usage data)
FIG. 2A shows an example of raw material data used in Example 1, showing a rectangle having a width of 910 mm and a height of 1820 mm, and showing that there is only one type of raw material. Therefore, the first product allocation order allocation means 24 described above operates. The output of the arithmetic processing is the required number of raw materials 18 (for each type), the method of allocating the product to each raw material 20, and the raw material cost 22. As shown in FIG. 2B, for example, when two types of raw materials, a rectangle f1 having a width of 910 mm and a height of 1820 mm and a square f2 having a width and a height of 910 mm, are used, the first It can be calculated by operating the second product allocation order allocation means 28.

FIG. 3A shows an example of the product data 14 used in the first embodiment. Product numbers 1 to 5 indicate the type of product shape, and the quantity for each type is shown. For example, product number 2 has 4 sheets and product number 5 has 30 sheets. The total number of products (m) is 38.

The shape of each product is indicated by the number of vertices and the xy coordinates of the vertices. In the example of this figure, the maximum number of vertices is 4. For example, the product of product number 1 is a quadrangle (rectangle) having side lengths of 200 mm and 300 mm, and the number thereof is two. The product of product number 2 is a triangle. The absence of vertices is indicated by *. As shown in FIG. 3B, the products include a square g1, a rectangle g2, a trapezoid g3, and a triangle g4, an L-shaped g5 having 6 vertices, and a U-shaped g6 having 8 vertices. There are some, and these can be calculated in the same way.

(Flowchart and layout)
4 to 8 are flowcharts of arithmetic processing of the system of the present invention. FIG. 4 is a main routine, and the processing of step S4 is shown in FIGS. 5 and 6. Further, FIGS. 7 and 8 show examples of a predetermined allocation method of each product to raw materials.

FIG. 5 is an operation example of the first product allocation order allocation means 24. Further, FIG. 6 is an operation example of the second product allocation order allocation means 28. FIG. 7 is the "simplest" BL method shown in Non-Patent Document 1, and FIG. 8 shows an example of a devised BL method. This allocation method is an example, and other methods can be selected.

In the first embodiment, as shown in FIG. 2, since there is only one type of raw material, the first product allocation order allocation means 24 shown in FIG. 5 is used in step S4 of FIG. 4, and the first product allocation order allocation means 24 shown in FIG. 5 is used. In step S107, the simplest BL method shown in FIG. 7 was selected, and arithmetic processing was executed according to the flowchart shown in FIG.

(Alternation of generations and genes)
The required number of raw materials 18 (for each type) obtained as a result of the arithmetic processing, or the raw material cost 22 thereof, largely depends on the order of allocation of the products to the raw materials. A genetic algorithm is applied to optimize this allocation order. The parameters used for the arithmetic processing of the genetic algorithm were set to the number of individuals M = 500, the number of mutations = 10, and the number of generational changes = 100 from the practical arithmetic processing time considered from the rule of thumb.

When the order of allocation of products is brought closer to the optimum by the genetic algorithm, the evaluation value starts to converge at a certain point. The evaluation value is the raw material cost 22 obtained each time as a result of the arithmetic processing. From experience, when the number of products is about 20 or more, it seems that the state is temporarily converged when the generation change is repeated, but when the generation change is continued, the evaluation value may become smaller again. many. Therefore, in the first embodiment, since the number of products is 38, the convergence test is not used as the end condition, and the end condition is set as the upper limit of the number of generation changes.

That is, after 100 generations of alternation of generations, the evaluation values are compared, and the allocation method in which the chromosomes provided by the individual having the minimum evaluation value are in the order of allocation is output as a result. According to this calculation method, the processing waiting time is almost constant. When the number of products is less than about 20, it is advisable to use the upper limit values of both the convergence test and the number of generation changes as the termination condition.

(Specific processing procedure)
In step S1 of FIG. 4, the individual generation means 36 randomly generated 500 first-generation individuals from the product data 14 of FIG. This means that 500 types of allocation order have been set. After that, for example, as shown in FIG. 9A, the triangular product labeled A in the figure is moved on the raw material as described in FIGS. 10 and 11 to select the allocation location. do.

As shown in FIGS. 9A and 9B, the state of this product at the time of allocation is, in addition to the A state, the B state rotated 90 degrees, the C state rotated 180 degrees, and the D state rotated 270 degrees. There are a total of eight types of states, an E state, an F state, a G state, and an H state, in which each of these states is inverted with respect to the x-axis or the y-axis.

Even for the same product, if the condition is different, the allocation method will be different. Naturally, it affects the evolution of the individual. When the product number of any product is P, eight types of states are expressed as PA, PB, PC, PD, PE, PF, PG, PH. As shown in FIG. 9 (c), there are eight types of products having product numbers 1 to 5 shown in the example of FIG. Treat these conditions as if they were separate products, and generate an allocation order for 38 products.

In particular, if a polygonal product has one or more internal angles equal to a right angle, arrange the sides sandwiching the right angle so that they are parallel to the x-axis and y-axis, and set that orientation as the basic orientation of the product. good. Further, when the calculation processing time becomes long, not eight types including rotation and inversion may be used, but four types excluding the inverted one may be used.

As a matter of course, those that cannot be reversed (there is a distinction between the front and back) cannot be considered for inversion, and those that do not change the state of the product even if they are inverted or those that do not change the state of the product even if they are rotated are types. May be reduced. It is possible to consider other angles, but there is a high possibility that the number of types will be excessive and the arithmetic processing time will be unrealistic, and it is not necessary to consider with exceptions.

In the above procedure, 500 individuals having the chromosome as shown in FIG. 9D were randomly generated. The gene sequence is used in the order of product allocation and at the same time determines the orientation of the product. At this time, the numbers of genes with the same product number and different codes such as 1A, 1B, 1C, 1D, 1E, 1F, 1G, 1H contained in 500 first-generation individuals should be equal. It is convenient. That is, the sum of the numbers of 1A = the sum of the numbers of 1B = ... = the sum of the numbers of 1H.

Next, in step S2 of FIG. 4, the generation alternation means 38 uses the above 500 individuals as parent individuals, randomly selects two parent individuals, and generates two child individuals by crossover processing. This process was performed until 500 offspring were produced. Then, 10 were randomly selected from 500 offspring and subjected to mutation treatment.

In the above crossing process, any two of the parent individuals are designated as "parent 1" and "parent 2", and two child individuals having a chromosome inheriting a part of the gene sequence are generated from both of them. In the above mutation treatment, any two genes at the locus are exchanged for 10 randomly selected offspring.

Next, in steps S3, S4, and S5 of FIG. 4, since the number of types of raw materials = 1 in Example 1, the first product allocation order allocation means 24 is executed until it is applied to all individuals. If the number of types of raw materials> 1, the second product allocation order means 28 operates. The operation of the first product allocation order allocation means 24 is repeated for all 500 parent individuals and 500 child individuals, and the evaluation values of 1000 individuals and the allocation method 20 for each raw material are obtained.

When there are no unapplied individuals, the number of generational changes is determined in step S6. When the set number of generation changes = 100 is reached, in step S8, 1000 evaluation values by 500 parent individuals and 500 child individuals, that is, the raw material cost 22, are compared. The individual having the minimum value is selected, the required number of raw materials 18 (for each type), the allocation method 20 to each raw material, and the raw material cost 22 are generated, and the processing is completed.

When it is determined in step S6 that the set number of generation changes has not been reached, the generation change means 38 executes the individual selection process in step S7. In step S7, 500 pieces are selected from the smaller evaluation value of the 1000 pieces, and the process returns to step S2 as 500 pieces of the next-generation parent individual. In this Example 1, the flow from step S2 to step S7 was repeated up to the 100th generation.

The arithmetic processing of the first product allocation order allocation means 24 executed in step S4 will be described with reference to FIG. As described with reference to FIG. 4, 500 child individuals are given to the first product allocation order allocation means 24 one by one. Only the first generation is given 500 parent individuals one by one.

Therefore, first, in step S101, the order of allocation of products is determined according to the given individual. Next, in step S102, all the products are unallocated, and the required number of raw materials 18 (for each type) is initialized to (a = 0).

Next, in step S103, it is determined whether or not all the products have been allocated. When the allocation has been completed, the required number of raw materials 18 (for each type), the allocation method 20 for each raw material, and the raw material cost 22 are output, and step S4 in FIG. 4 is completed. If the allocation has not been completed, the process proceeds to step S104. In step S104, the required number of raw materials 18 (for each type) is added by one (a = a + 1), and the process proceeds to step S105. In step S105, i indicating the locus is initialized to 1, and the process proceeds to step S106.

In step S106, it is determined whether the i-th product is unallocated or allocated. If the allocation has been completed, the process proceeds to step S110. If not, proceed to step S107, execute a predetermined allocation method, that is, the method shown in FIG. 7 in Example 1, and in step S108, whether the i-th product can be allocated to the raw material 42 in the process of allocation. Is determined.

If it is determined in step S108 that allocation is not possible, the process proceeds to step S110. When the allocation is possible, in step S109, the i-th product is allocated to the raw material 42 in the middle of allocation, the i-th product is assigned, and the process proceeds to step S110. In step S110, i is incremented by 1 in order to process the i-th next product, and the process proceeds to step S111.

In step S111, it is determined whether or not all the products have been assigned. That is, if i> m (m is the number of products), the process returns to step S106 for determination of the next product in the allocation order, and the procedure from step S106 to step S111 is repeated. If i> m, all the products have been assigned, and the process proceeds to step S112. In step S112, the method of allocating the raw material 42 just taken out and the product allocated is determined and stored in the storage device. After that, the process returns to step S103.

In step S103, it is determined whether or not all the product allocation methods have been determined. If there is an unprocessed product, a new raw material is taken out in step S104, and the processes from step S105 to step S112 are repeated. On the other hand, when it is determined in step S103 that the allocation method of all products has been determined, the processing of this flowchart is terminated. That is, the process of step S4 in FIG. 4 is completed.

The allocation method used in step S107 of FIG. 5 will be described with reference to FIGS. 7 and 10. The methods shown in FIGS. 7 and 10 utilize the simplest BL method and are described in Non-Patent Document 1. In step S301 of FIG. 7, it is determined whether or not the unallocated product given in step S107 of FIG. 5 can be allocated on the raw material.

FIG. 10A shows a plan view of the raw material 42. In this allocation method, when the product is moved from the upper right to the left on the raw material 42 and cannot move, it is moved to a place where it can move downward to determine the allocation location.

It is assumed that two products 43 and 44 have already been assigned to the raw material 42 shown in FIG. 10 (b). Here, the product 45 is newly placed in the upper right corner of the raw material 42. At this time, it is determined whether or not the raw material 42 can be allocated so as not to overlap with the already allocated products 43 and 44.

If the allocation is not possible, the process proceeds from step S301 in FIG. 7 to step S303, and if allocation is not possible, control is returned to step S108 in FIG. 5 and the process proceeds to step S110 in FIG. If the allocation is possible, the process proceeds to step S302 in FIG. In step S302, the unassigned product 45 is moved to the left until it protrudes from the raw material or is blocked by the already assigned products 43 and 44, and then moves downward. After the allocation is completed as shown in FIG. 10B, the allocation method is stored in the storage device, the control is returned to step S108 of FIG. 5, and the process proceeds to step S109.

As described above, in the example of FIG. 10B, the quadrangular product 43 and the triangular product 44 have already been assigned to the raw material 42. The square product 45 in the following allocation order can be allocated so as not to overlap the allocated products 43 and 44 in the upper right corner of the raw material 42. Then, the product 45 is moved to the left and further downward to determine the allocation at the position where it cannot move.

In the example of FIG. 10 (c), the square product 46 has already been assigned to the raw material 42. The triangular product 47 in the following allocation order also moves to the left first and then moves downward in the same manner as described above, and the allocation is confirmed at the position where it cannot move.

Then, a new product is placed, moved in the same way so as not to overlap with the allocated product, and the allocation is confirmed at the position where it cannot move. You may adopt the method of moving downward first and then moving to the left. Since the dimensions of the raw material 42 are limited, it may not be possible to allocate the product anywhere from the beginning. At this time, the process of allocating the product to a new raw material is restarted.

FIG. 8 is a flowchart of the BL method for trying a method of allocating the leftmost vertex of the newly allocated product so as to overlap the vertex of the allocated product. FIG. 11 is an explanatory diagram of the allocation example. As shown in FIG. 11, a quadrangle (trapezoid) 48 has already been assigned to the raw material 42.

There are three vertices of the rectangular product 48 on which the leftmost and bottom vertices of the triangular unassigned product 49 can be overlapped. Therefore, there are three new methods for allocating the triangular unallocated product 49, as shown in (a) to (c). Of these, (b), which has the smallest height from the lower side of the raw material 42 of the unallocated product 49, is selected.

FIG. 6 is an operation flowchart when there are two or more types of raw materials. In this step S201, the allocation order of the products is determined in the same manner as in step S101 of FIG. Next, in step S202, all the products are unallocated and the number of raw materials is initialized in the same manner as in step S102 of FIG.

That is, the number of k types of raw materials j is set to (aj = 0), and the price of k types of raw materials j (j = 1 to k) is set to Cj (j = 1 to k). Then, in step S203, it is determined whether or not all the products have been allocated. If there is an unallocated product, the process proceeds to step S204, and the processing from step S204 to step S206 is set to repeat processing between j = 1 to k and i = 1 to m.

In step S205, an allocation trial of m products is executed. Step S205 in this figure is the same as the process from step S106 to step S112 in FIG. In the second embodiment, since there are a plurality of types of products, the total product area allocated to the price pj = price Cj / raw material j per product area is calculated for each raw material.

When the allocation of all the products in the given allocation order is completed, the process of step S206 is performed. In step S206, the prices per product area are compared, the cheapest product price per area pL (1 ≦ L ≦ k) is selected, and the combination and allocation of the L-type raw material L and the product assigned to the raw material L are assigned. Remember the one. This process is executed in step S4 of FIG. Other processes are the same as in Example 1.

By the above processing, even if the product contains a mixture of rectangles and polygons other than rectangles, the optimum allocation order is obtained by the genetic algorithm (individual generation means, generation change means) and the first or second product allocation order allocation means. By obtaining the optimum allocation result, it is possible to reduce the manufacturing cost. Moreover, the optimization becomes possible with a practical calculation processing time.

The explanation about the influence of the thickness of the cutting tool on the allocation is omitted.

12 Raw material data 14 Product data 18 Required number of raw materials (for each type) 20 How to allocate products to each raw material 22 Raw material costs 24 First product allocation order allocation means 28 Second product allocation order allocation means 36 Individual generation means 38 Generational Alternate Means 40 Individual Data 42 Raw Materials 43 Products 44 Products 45 Products 46 Products 47 Products

Claims (8)

When cutting m products with a mixture of rectangles and non-rectangular polygons used for buildings from k types of rectangular raw materials, the number of raw materials required for each type and how to allocate the product to each raw material It seeks to minimize raw material costs,
When k = 1, one raw material shall be taken out, and unallocated products for which the allocation order has been determined shall be taken out in the allocation order.
"A new raw material is taken out, and if the unallocated product taken out can be assigned by the allocation method predetermined to the raw material, the unallocated product is assigned, and the unallocated product is regarded as the assigned product.
If it is not possible to allocate, the operation to restore the unassigned product taken out while maintaining the above allocation order is performed from the first allocation order to the last unallocated product in the allocation order. " Allocate until all products are already allocated.
The first product allocation order allocation means that controls the calculation to obtain the required number of raw materials, how to allocate products to each raw material, and raw material costs.
When k> 1, the price of each raw material is set, one raw material j of the jth type from j = 1 to k is taken out, and the unallocated products for which the allocation order is defined are taken out in the allocation order.
The above-mentioned allocation processing to the extracted raw material is performed for the jth kind of raw material j, and the process is performed.
continuation,
"Now ask for products with assigned to the allocation process the raw materials j went, and the price of the raw materials j, determine the per product area price pj from the sum of the areas of the assigned product" that, the product area per price calculation processing Is executed for all k kinds of raw materials (j = 1 to k).
continuation,
"From the price per product area pj (j = 1 to k) obtained by performing the price calculation process per product area , select the cheapest price per product area pL (1 ≤ L ≤ k), and select the L type. to determine the raw material L and the combination product, the relevant product and allocated Quote, performed per product area prices comparison judgment processing,
A series of processes including the above-mentioned allocation process to the extracted raw materials, the price calculation process per product area, and the price comparison judgment process per product area are performed until all the products are allocated products.
A second product allocation order allocation method that controls the calculation to obtain the required number of raw materials for each type, the method of allocating products to each raw material, and the raw material cost.
A gene that specifies m products in which rectangles and polygons other than rectangles are mixed, and an individual generation means that generates a plurality of chromosomes having loci that arrange the genes in the selected allocation order as individuals.
The generated individual is used as a parent individual, and cross-processing, mutation processing, or selection processing is performed to generate a plurality of child individuals, and the plurality of child individuals are used as the next-generation parent individual, and generational change is repeated. , Equipped with a generational alternation means to generate individuals representing the allocation order of the above products,
When k = 1, arithmetic processing is executed by the above-mentioned first product allocation order allocation means, the individual generation means, and the generation alternation means, and the required number of raw materials and the method of allocating the product to each raw material are determined. When k> 1, the arithmetic processing by the second product allocation order allocation means, the individual generation means, and the generation change means is executed, and the number of raw materials required for each type and each raw material are obtained. A material allocation system characterized by minimizing raw material costs by seeking product allocation methods. The orientation of the product taken out is a certain state, a state where this certain state is rotated 90 degrees, a state where it is rotated 180 degrees, a state where it is rotated 270 degrees, and these four types of states are like a mirror. The member allocation system according to claim 1, wherein a plurality of types of states including any of the inverted states are treated as separate genes. In the predetermined allocation method, when one of the vertices of a rectangular raw material is selected and called a specific vertex, when a new product is allocated on this raw material, the raw material having one end at the specific vertex is used. The product is moved along two directions parallel to the pair of sides of the raw material, and the position of the product is placed as close to the specific vertex as possible to the raw material, and the already assigned product is placed. In some cases, the new product cannot be assigned to the raw material by arranging the new product close to the above-mentioned specific vertex within the range where the assigned product and the new product do not overlap each other. The member allocation system according to any one of claims 1 and 2, characterized in that the process is repeated in order. The above-mentioned predetermined allocation method is such that the product already allocated on the rectangular raw material and the product to be allocated next share one of the vertices without causing an overlapping part with each other. The member allocation system according to claim 3, wherein the process of arranging, if possible, is repeated in order until a new product cannot be allocated to the raw material. The member allocation system according to any one of claims 1 to 4, wherein the generation change means selects a product allocation order according to the following procedure.
(1) M random initial populations (first generation) are generated.
(2) Two parent individuals are randomly selected from the M population.
(3) M child individuals are produced from two parent individuals by crossover processing.
(4) Mutation treatment is performed on a set number of child individuals out of the obtained M child individuals.
(5) Calculate the required number of raw materials or raw material costs for a total of 2M individuals, including M parent individuals and M child individuals.
(6) Take out M individuals from the required number of raw materials or the one with the lowest raw material cost.
The next generation (second generation) individual population.
(7) Repeat the generation changes from (1) to (6) above, and finish the calculation when the required number of raw materials or the difference in raw material costs reaches the convergence test, or when the set number of generation changes is reached. do.
(8) From the smallest or near-minimum solids, select the product allocation order with reference to those chromosomes. In the above crossing process,
Arbitrary two of the above parent individuals are designated as "parent 1" and "parent 2", and the same number of genes of the child individual that inherits a part of the gene sequence from both of them is generated as the same number as the above parent individual.
In the above mutation treatment,
Any two genes at the locus are exchanged with any of the above offspring to generate new offspring.
In the selection process of the above individual,
From the product allocation order represented by the parent individual and the child individual, the same number as the parent individual is selected from the one with the smaller number of required raw materials or the one with the lower cost of the required raw materials to be the next generation. The member allocation system according to any one of claims 1 to 5. A computer program that causes a computer to function as the member allocation system according to any one of claims 1 to 6. A computer-readable recording medium on which the computer program according to claim 7 is recorded.

Images