JP5043528B2 - Precut material assembling optimization processing method, computer program, and computer-readable recording medium - Google Patents

Description

  In order to cut out a predetermined number of product members of a predetermined length from a plurality of standard length raw materials, the present invention can determine which product member from each raw material and the number of each of the raw materials having a good yield and each of the standard lengths. With regard to the pre-cut material assortment processing method for determining whether to cut out, the Bin Packing Problem (BPP), which is a typical combination problem, was applied as an application, and a genetic algorithm (GA) was applied to this. The present invention relates to an optimization processing method.

  Precut material assembling is a problem that cuts parts products of the length required for residential construction from several types of wood base materials (Cutting Stock Problem), and one-dimensional bin packing problem (Bin Packing Problem : BPP). However, the capacity of the bin is usually constant in BPP, but in the case of pre-cut, the base material of several lengths is targeted.

  As an example of pre-cut materials, in the case of pre-cutting of house structural materials, several types of base materials (3.5m to 6m) are prepared for each specification such as cross-sectional shape, tree species, grade, etc. Cut out the part (product). In the case of a general-sized house, which is called a horizontal member such as a beam, girder, or foundation, an average of 10 pieces from several lengths of base material for each of about 20 types of specifications, a total of about 200 products Is cut out.

  FIG. 1 shows a schematic example of assembling precut materials. The goal of the assortment calculation is to determine how many required products are obtained from the assembling result 103 according to the length of the product group 102, depending on the length of the base material group 101 of several lengths prepared for each product specification. It is to cut with the material (yield maximum). In addition, when the procurement cost and the inventory cost differ depending on the length of the base material, the target is to minimize the necessary base material cost. Usually, the base material cost is determined by the unit price of the material, so it is common to aim for the maximum material yield. Currently, the primary yield in many precut factories is said to be approximately 85% to 90%. For example, Patent Document 1 (Japanese Patent No. 3565262) shows an allocation method by logic using a computer.

  Further, as a combination optimization problem processing method using a genetic algorithm, Patent Document 2 (Japanese Patent Laid-Open No. 10-1111861), Patent Document 3 (Japanese Patent Laid-Open No. 10-15727), and Patent Document as a slab cutting control method. 4 (Japanese Patent Laid-Open No. 9-94646).

Non-patent document 1 (Tetsuya Yagawa, Imai et al., Nobuo Sannomiya: Proposal of genetic algorithm for bin-packing problem, automatic measurement control) Academic papers, Vol.41, No.3, 274-282 (2005)) can be seen.
Furthermore, Non-Patent Document 2 (Hidemi Yamachi, Yasuhiro Tsujimura, Hisashi Yamamoto: Effectiveness and Evaluation of Genetic Algorithm Application to NVP System Design, Journal of Japan Society for Management Engineering, Vol.57, No.2, 113-119 (2006 In)), when applying GA to the fault-tolerant design of software systems, a proposal is made to specify the order in which tasks are combined using genes represented by random numbers. In this method, loci are sorted using genes as keys, and tasks for the loci are assigned in the sort order.
Japanese Patent No. 3565262 JP 10-1111861 A Japanese Patent Laid-Open No. 10-15727 Japanese Patent Laid-Open No. 9-94646 Tetsuya Yagawa, et al., Ima et al., Nobuo Sannomiya: Proposal of genetic algorithm for bin packing problem, Transactions of the Society of Instrument and Control Engineers, Vol.41, No.3, 274-282 (2005) Hidemi Yamaji, Yasuhiro Tsujimura, Hisashi Yamamoto: Effectiveness and Evaluation of Genetic Algorithm Application to NVP System Design, Journal of Japan Society for Management Engineering, Vol.57, No.2, 113-119 (2006)

  In the present invention, as a more general-purpose model of one-dimensional BPP, the application of GA is studied for the assembling problem of pre-cut materials that handle a plurality of base material lengths, and the combination pattern is expressed by two strings of genes. , Omitting the process of searching for a combination pattern, making a model close to a simple GA, and further setting cross control parameters to reflect the results of the assembly calculation, “The group of base materials and products with high yields will be passed on to the next generation. By providing a new elite selection (extended elite selection) function called “trend”, a model with good convergence is provided.

  The first solving means of the present invention (Claim 1) deals with the problem of assembling precut materials when cutting out a product group of a predetermined length from a plurality of standard base material groups (hereinafter abbreviated as base material types). It is assigned to the same base material type as the gene that designates the base material type to which the product is assigned (hereinafter abbreviated as gene B, and expressed as GeneB in the formula). The next step (represented as Step in the formula) is the chromosome of the double gene structure of the gene (hereinafter abbreviated as gene P, expressed as GeneP) that serves as the sort key for specifying the order of assignment in the product group. And calculate with

Furthermore, it has the following control process,
Control 1: High Yield Base Material-Increase the order of allocation of products belonging to the product group so that the group is not destroyed by preceding allocation. Control 2: High Yield Base Material-of products belonging to the product group The gene is controlled so that it is maintained as much as possible even after the crossing operation, and a precut material combination optimization processing method is provided.

Further, according to a second solution of the present invention, in claim 1, a set of products is defined as l = {i | i = 1,. . . , The length of the n} product i l _i, the matrix species preform to allocate this product as a t _i, whereas the base material species t (t = 1,2, .., m) of the preform Each set of genes at the locus of the product i is defined as follows, where B _i is a set, a base material belonging to B _i is K ^(t) (= 1, 2,..., M) and length is b _t. ,

The pre-cut material arrangement optimization processing method according to claim 1 is provided.

Furthermore, in claim 1,
The remaining material ratio r _{k (t)} (0 ≦ r _{k (t)} ≦ 1) is defined by the following equation for the remaining material after cutting the product from the base material K ^(t).

The last term in equation (5) indicates the yield of the base material K ^(t) ,
Here, in order to realize the control 1, GeneP of (3) is defined as follows by introducing a number α that is sufficiently small (for example, 0.0001),

GeneP consists of the base material-product group remaining material rate and base material number that are recalculated by equation (5) for each assortment calculation, and is the same value for the same base material-product group, and a small value for high yields. Will have
To further implement the control 2, cross control parameter (Crossover Control Parameter: CCP) introducing p _i, a genetic cross probabilities at intersections,

CCP functions F _p provides a pre-cut material assortment optimization processing method according to claim 1, characterized in that the increasing function with respect to remainder rate r _{k (t).}

The combination of precut materials according to claim 3, further comprising: calculating a remaining material ratio from equation (5) based on a combination result of products assigned to the base material, and updating GeneP according to the definition of equation (6). This is an optimization processing method.
Furthermore, these can be used as a computer program and a computer-readable recording medium convenient for carrying.

As an example of one-dimensional BPP, the present invention examines the application of GA for the problem of assembling pre-cut materials. In the case of pre-cut, unlike a general one-dimensional BPP, there are a plurality of base material lengths, so a double structure is used. Establishing a model with good convergence by making a kind of elite selection that protects the dominant constituent group (elite group) in individuals by setting gene structure by character string and setting cross control parameters in cooperation with genes, A precut material assembling process with a good yield is performed.
In addition, the present invention is not limited to assembling precut materials. For example, when there are a plurality of trucks having different loadable amounts with respect to cargo to be transported, the present invention can be applied to exploring efficient cargo assembling. .

As mentioned above, pre-cut material assortment is a cutting stock problem and can be modeled as a one-dimensional BPP. Normally, BPP handles one kind of capacity bin, but in the case of this pre-cut, as mentioned above There are several types of base material lengths, which are more general in the sense of assuming multiple capacity bins. A one-dimensional multi-BPP that handles multiple types of bins is defined below.
m kind of volume _{b t (t = 1, ..} , m) bottle is in enough, this volume _{l i (i = 1, ...} , n) When you put all of the items of, of the volume b _t bottle If the usage cost of a bin of type t is ct and the bin type of bin k (k = 1, 2,...) Is t _k , the one-dimensional multi-BPP is

It can be expressed. (9) is that the total volume of items to be placed in the bin is less than or equal to the capacity of the bin, (10) is to place all items in one of the bins, and (11) is for multiple items at the same time Indicates that the bottle does not enter.
In contrast to the above, the bin is replaced with a pre-cut base material, the set of bins according to capacity is replaced with a set of base materials according to length (hereinafter referred to as base material type), and the volume of the product is cut out. If it is read as length, it becomes a precut material assembling problem. In general, the pre-cut is generally aimed at the maximum yield. Yield y is expressed by the following equation:

Here, since the total product length of the numerator is given, the usage cost c _t is replaced by the base material length b _t in equation (1).
And it is sufficient. In pre-cutting, the “nose cutting” that adjusts both ends of the base material (cutting off both ends to adjust the shape of both ends of the base material) and the “saw allowance” when cutting the product (the thickness of the saw when cutting) This is not an essential problem.

  When applying GA to BPP, there is a method in which the allocation patterns to bins are listed by some method, each pattern is used as a gene, and the pattern genes are arranged into chromosomes so that all items to be included in the bin are included. For example, Yachikawa et al. (2005) uses a set of items that are contained in one bin as one gene, and arranges genes corresponding to each bin into individuals. However, this method requires exploration and evaluation of the combination of items entering the bin, and cannot be easily applied when handling a plurality of types of bins as in the present invention.

  FIG. 2 is a schematic example of the 0-1 character string representation of the assembling problem in which the number of base materials in the FF (first fit) method is set in advance. In this way, the following model can be considered as an idea using 0-1 character strings used in simple GA as genes. All the products are provisionally allocated to the base material of each length in advance by, for example, the FF (first fit) method, and a sufficient number of base materials to be prepared is calculated. A product is assigned to any base material with a length equal to or greater than the product length. This is expressed as a 0-1 character string and used as a gene code.

  However, in this case, even if the number of base materials for each base material type can be reduced to half of the number of products, if the number of products is n and the number of base material types is m, the maximum 0-1 character string of the chromosome is n × m / 2 Xn bit length, and the above-mentioned example of the horizontal member of a general house handles a huge exploration space of 1,000 to 3,000 bits, and there is a concern about exploration efficiency and convergence problems. Therefore, the following model was examined in the present invention.

In the present invention, chromosomes are represented by the order of products to be assigned (Order based representation), and the order of assignment in the product group assigned to the same base material type as gene B that specifies the base material type to which the product is assigned is specified. Consider a chromosome having a double gene structure of gene P, which is the sort key to be used.
Let the set of products be l = {i | i = 1,2. . . , N}, the length of the product i is l _i , and the base material type of the base material to which the product is assigned is t _i . On the other hand, the base material species t (t = 1,2, ..., m) a set of the base material of the B _t, the base material k ^(t) belonging to the B _t (1,2, ..), length each gene product locus defined as follows as b _t a is (see Table 1 gene structure).

Using these two genes, the assembling calculation is performed according to the following rules. Note that “nose clip” and “saw allowance” can be easily incorporated by adjusting the base material length and product length, so they are ignored here for simplicity of expression.
<Assortment calculation rules>

However, in the above assembly rules based on the gene structure, the combination of the base material and the product within the same base material type is determined by the relative size relationship of GeneP, which is the sort key, so the combination reacts sensitively to changes in GeneP, so the schema It is assumed that the concept does not hold and evolution to a stable optimal solution cannot be expected. Therefore, in order to avoid this, it is considered that the “base material with high yield—product group tends to be handed over to the next generation”. In particular,
Control 1: High yield base material—Promote the allocation order of products belonging to the product group so that the group is not destroyed by the preceding allocation.
Control 2: High yield base material-The gene of the product belonging to the product group should be maintained as much as possible even after crossing operation.
Control that. In contrast to the normal elite selection based on the individual unit adaptation rate, this control is a broader elite selection that preserves a group with a high adaptation rate (yield) in the base material and product group units that make up the individual. This is called extended elite selection.
The remaining material ratio r _{k (t)} (0 ≦ r _{k (t)} ≦ 1) is defined by the following equation for the remaining material after the product is cut from the base material k ^(t) .

Note that the last term of the equation is the yield of the base material k ^(t) .
Here, in order to realize the control 1 described above, GeneP of (3) is defined as follows by introducing a sufficiently small number α (for example, 0.0001).

GeneP consists of the base material-product group remaining material rate and base material number that are recalculated by equation (5) for each assortment calculation, and is the same value for the same base material-product group, and a small value for high yields. Will have.
To further implement the control 2, cross control parameter (Crossover Control Parameter: CCP) introducing p _i, and genetic crossing probability at intersections.

The function F _p of CCP is an increasing function with respect to the remaining material rate rk _(t) . Details of CCP and its functions will be described in the next section on examination of intersection.

A flow (flowchart) of the entire algorithm of the present invention is shown in FIG.
A. Initial setting (S301)
For each individual, geneBt _i at the locus (product: i = 1, 2,..., N) is a random number 1 ≦ t _i ≦ m, and GenePs _i is a random number 0 ≦ s _i ≦ 1. Set. However, let's set in advance to satisfy equation (6) and avoid lethal genes.
Individuals are generated by the initial number of individuals determined as described above.
B. Assortment calculation (S302)
Perform allocation according to the rules for assortment calculation in the previous section, and use the result to perform the following processing.
B-1. Calculation of Adaptation Rate Adaptation rate a scales individual yield y (0 ≦ y ≦ 1) of equation (5) with function F _a .

Yields are found to be 70% to 90% on average in preliminary experiments, the minimum is 50% to 60%, and the goal is 90% or higher. In view of this, the adaptation rate a is almost 0 when y <0.5, and the function F _a (y) should be set so that y varies greatly between 0.6 and 1.0.
B-2. Calculation of residual material rate and update of GeneP Calculate the residual material rate from Equation (5) based on the combination result of the products assigned to the base material, and update GeneP according to the definition of Equation (6).

C. Selection (S303)
Selection combines normal elite selection with roulette selection. According to the calculated adaptation rate, up to the number determined by the specified selection rate, first select the elite number specified in descending order of the individual adaptation rate, and select the rest by roulette selection proportional to the adaptation rate. Hesitate.
D. Intersection (S304)
Individuals selected by selection are propagated to the initial population by this crossing.
Usually, crossing generates two offspring individuals from the genes of two parent individuals according to the rules of one-point intersection or uniform intersection. However, the present invention adopts an extended elite selection method in which two children are generated by exchanging genes of each parent gene according to the cross probability CCP. Assuming that Gene B of the i-th locus (i = 1, 2,..., N) of individual A is t _i (A), GeneP is s _i (A), and CCP is p _i (A), Generating a child's gene with simple rules.

However, Rnd is a random number p _i of (0, 1), and p _i is given by equation (7) according to the remaining material ratio of the base material defined by equation (5). In preliminary experiments, it is known that individuals with a yield of 90% or more have a remaining material ratio of the base material that is almost 0.1% or more. It is necessary to aim at a material rate of 0.05% or less. Therefore, the function F _p of the equation (7) that gives p _i is close to 0 near the origin with respect to the remaining material ratio r of the base material, changes greatly near r = 0.05, and when r> 0.1. It can be estimated that it is effective to set so that gene exchange is performed with a certain probability.

E. Mutation (S305)
Since the model of the present invention deals with two types of genes, mutation probabilities are set for each gene, and the target individual is selected with the set probabilities to perform the mutation operation. For an individual to be mutated, a gene at a randomly selected locus is reset with a random number in the manner of initial setting. The number of loci to be mutated is specified in advance.
In the case of GeneB mutation, GeneP is also reset at the same time, and the conditions of formulas (4) and (9) are applied to avoid the generation of lethal genes. If GeneP is mutated, GeneB is not changed.

F. Target achievement determination (S306)
It is determined whether a predetermined target yield is achieved or whether the maximum number of generations set by overlapping generations has been reached.
If not, the process returns to the downstream of S301 and repeats the determination according to the same procedure.
G. STOP (end of processing)
When a predetermined target yield is achieved or the maximum number of generations set by overlapping generations is reached, the process is terminated.

  As shown in Attached Table 1 in the list of horizontal member precuts in FIG. 8, the GA of the present invention model was applied to 199 horizontal members of a standard single-family house that was ordered by a housing manufacturer. These horizontal members can be divided into groups of 18 lots that can be cut out from the same base material such as cross-sectional size, tree species, grade, etc., and the number of products to be cut out and the base material group used for each lot are different ( (See Table 2: Base material group and product group, and implementation results). For example, Lot No. 8 and Lot No. 9 have 1 target product, Lot No. 6 has 2 products, Lot Nos. 12 and 16 have 3 products. You can expect to get it. Therefore, the number of individuals to be generated and the maximum number of generations were appropriately set according to the number of combinations of base material types and products. Other parameters were set as follows based on the results of preliminary experiments. The nose clip is 0 mm and the saw blade is 5 mm.

For each function, the adaptation rate function F _{a in} equation (15) is a linear function, and the CCP function F _{p in} equation (7) is similar to a sigmoid function (FIG. 4 adaptation rate function (left) and CCP function ( (See right)).

Table 3 shows the combined execution results of the adaptation rate function and the CCP function. The specifications of the personal computer used are as shown in FIG. The results in Table 2 show the maximum value, average value, minimum value, and standard deviation of the yields that can be executed 50 times with the same parameters for each lot (examples of execution results are shown in Tables 2 and 10 of FIG. 9). Is shown in Appendix 3). For lots with 5 or less products, the results of all 50 runs are the same and are estimated to be optimal. The standard deviation was within 0.5%. Exceptions are Lot No. 12 and No. 14, but in Lot No. 12, 80% of 50 trials occurred twice and the remaining was 96.22%.
As a result, if the combination of the maximum yields of 50 trials is adopted, the 199 required horizontal members of this house can be pre-cut with an overall volume yield of 95.21%.

Table 3 evaluates the adaptation rate function Fa and the CCP function Fp for lot No. 1 with a large number of products and a relatively large standard deviation. Table 3 shows a comparison of the adaptation rate function and CCP function for each case. Other parameters are not changed except Case7. FIG. 6 shows a graph of each function.
Cases 1 and 2 are cases where only the adaptation rate function is changed, Cases 3 to 5 are cases where only the CCP function is changed, and Cases 6 and 7 are cases where crossing control by CCP is not performed.
Table 4 shows the execution results of 50 times by case (in the case of lot No. 1).

  Cases 1 and 2 are cases in which only the adaptation rate function is changed. Comparing Original with Case 1 and Case 2, it can be seen that the adaptation rate function has little influence on the convergence. On the other hand, Cases 3 to 5 are cases in which only the CCP function is changed, and the CCP function affects the convergence and can provide a good convergence by giving an appropriate function form. In other words, gene crossover control at the time of crossing by CCP is greatly related to convergence, and it is speculated that extended elite selection has more influence on selection than normal selection by adaptation rate.

  In order to confirm this further, we compared the difference in the presence or absence of crossover control by CCP in terms of yield generation. Fig. 7 shows the change in yield of individual bodies (left: Case 6 right: Original). When the maximum yield was obtained for both the original model (Original: CCP crossing control) and Case 6 (uniform crossing method). The maximum, average, and minimum values of the generation-specific body yields were shown. This shows that convergence is unstable when CCP is not reflected in the intersection. That is, it can be confirmed that the above-mentioned assumption that “the concept of schema is not established and evolution to a stable optimal solution cannot be expected” is made. In this case, the addition of elite selection (Case 7) shows a slight improvement in yield (Table 4), but the convergence is significantly worse than the original model, and the effectiveness of extended elite selection by CCP has been demonstrated.

  In comparing the GA of the present invention with other algorithms, there is no application example of GA to precut material assortment. A general FFD (First Fit Descending) method was improved so that it could be applied to this model, and the results were compared.

  The algorithm of Patent Document 1 lists combinations of base materials having a plurality of base material lengths that are equal to or greater than the total length of all product lengths, and adds the base material lengths using the listed base material combinations. The method comprises the steps of determining whether all products are allocated in ascending order, and searching for a combination of base materials that further reduces the total base material length for a combination of the minimum base material lengths that can be assigned. is there.

The FFD (First Fit Descending) method is a general solution for the bin packing problem. However, this model cannot be used as it is because there are multiple types of base material length (bin capacity). Therefore, the FFD method was improved as follows and applied to the precut assembling problem.
The product sequence sorted in descending order of product length is i = 1, 2,. . , N, and assign the product to the base material according to the following rules.

The assignment result to the base material k ^(t) is adopted, and the set of assigned products l _{k (t)} is determined.
Step 5: Completed when assignment is completed for all products i (i = 1,..., N). If there are unallocated products, go to Step 1.
In this multi-FFD method, products are assigned in descending order of product length according to the FFD rule to each base material of each base material type, and the base material of the base material type that has the highest yield and the result of the allocation are used. This is a method of executing the process until all products have been assigned.

  Table 5 compares the numerical values (Table 3) of the GA of the present invention with the results of applying the method of Patent Document 1 and multi-FFD (detailed example is Attached Table 3). As a result, the model of this paper has a yield advantage of 0.6% over the patent method and 1.7% over the FFD model. In particular, the superiority of lot No. 1 and lot No. 7 with many combination patterns can be confirmed. In general, it can be said that the GA model of the present invention is extremely useful considering that the yield in a pre-cut factory is 90% or less. This is a result of the extended elite selection by cross control of CCP promoting the evolution to the optimal solution effectively and stably.

  In the present invention, not only pre-cut material assembling in the pre-cut industry, but in the field generally referred to as a stacking problem, for example, in the transportation industry, when there are a plurality of trucks having different loadable capacity for cargo to be transported, It can also be applied to exploring cargo stacks. This can also be applied to the stacking and shipping of railway containers of different sizes in the case of rail transport.

  Even in the field studied as Cutting Stock Problem (CPS), it can be applied to the process of manufacturing a base material and cutting a product from it, for example, rolling and sawing schedule of H-shaped steel in steel industry and cutting schedule of pipe steel. An example is the cutting of paper rolls in the paper industry.

A schematic example of assembling precut materials is shown. It is a schematic example of 0-1 character string expression of the assembling problem in which the number of base materials in the FF method is set in advance. It is a flow (flowchart) figure of the whole algorithm of this invention. It is a graph of the adaptation rate function (left) and CCP function (right) in the present invention. It is the specification (program environment) of the personal computer used for implementation of this invention. It is an adaptation rate function (left) and a CCP function (right) according to an embodiment of the present invention. It is a transition (left: Case 6, right: Original) of the generation separate body by the Example of this invention. It is a horizontal member pre-cut list (Appendix 1). It is an iterative execution result table (Appendix Table 2) used in the first embodiment of the present invention. It is the execution result (Appendix Table 3) of GA and FFD in the present invention.

Explanation of symbols

101 Base Material Group 102 Product Group 103 Assortment Result S301 Initial Setting S302 Assortment Calculation S303 Selection S304 Crossing S305 Mutation S306 Target Yield Determination S307 STOP

Claims (6)

The product i (i = 1, 2,..., N) is the mother of the pre-cut material assembling problem when a product group of a predetermined length is cut out from a plurality of types of standard base material groups (hereinafter abbreviated as base material types ). It is assumed that the base material belonging to each base material type t is k ^(t) (k ^(t) = 1,...) If the total number of grades m, the length l _i of each product i, the length b _t of the base material k ^(t) is given as data,
Computer
N products each having a length of l _i are allocated to a base material of length b _t according to the base material type ,
The base material species to assign the product i and t _i, and the data of gene B _i to specify the base material species t _i (GeneB In the formula _i), the product of the allocation order that assigned to the base material species t _i The gene P _i to be specified (GeneP _{i in the} formula) is used as the gene for each product i, and the chromosome consisting of n loci corresponding to the allocation of n products to each base material is stored as one individual. Store in the department,
Applying selection processing, crossover processing and mutation processing related to genetic algorithm to a group consisting of a plurality of individuals, and performing the process of determining the allocation of each product of that generation every time a generation passes from parent to child,
In the crossing process, two child individuals “child 1” and “child 2” are generated from two parent individuals “parent 1” and “parent 2”, and the i-th (i = 1, 1) of each child individual is generated. 2,..., N) is a process of inheriting genes from the “parent 1” and “parent 2” loci respectively, and is high based on the product allocation yield indicated by the chromosome of each parent individual. A precut material assembling optimization processing method, characterized in that it is determined so that a gene of a parent individual showing a yield is taken over with a high probability . The yield is the base material k ^(t) The base material of the remaining material after cutting the product from ^(t) The following formula showing the ratio to
It is expressed using the remaining material ratio by
The intersection processing is expressed by the following equation based on the yield:
The following rules using the intersection control parameters by:
The method according to claim 1, wherein the gene of the offspring parent is inherited according to   The process of assigning each product to the base material is the gene B representing the base material type of the assignment of the product i in each chromosome. _i And the same gene B _i The product of P is a gene P that represents the order of allocation _i Is the process of assigning to the base material of each base material type in ascending order of
The gene gene P _i Is calculated by a predetermined calculation procedure using a value related to the yield, and the calculation procedure is the gene P when the yield is high. _i When P is small and yield is low, gene P _i The method according to claim 1 or 2, which is a procedure predetermined so as to take a large value. The process of assigning each product to the base material is as follows:
Steps 1 to 4 below,
Is processing by
Gene P _i Is the base material k ^(t) The base material of the remaining material after cutting the product from ^(t) The following formula showing the ratio to
Using the remaining material ratio by
The method according to claim 3, calculated by:   A computer program that causes a computer to execute the method according to claim 1.   A computer-readable recording medium on which the program according to claim 5 is recorded.