JP5260262B2 - Product allocation device, product allocation program, recording medium, and product allocation method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a product allocation device capable of allocating efficiently a plurality of kinds of products to a plurality of kinds of mother bodies (materials, containers) with lengths and volumes different from each other. <P>SOLUTION: An individual chromosome data of a parent is defined to array a gene indicating the mother body for allocating the product and an allocation sequence, so as to be evolved to an allocation of high yield by alternation of generations. Gene fitnesses of the same product of a pair of parent individuals are compared in cross control for the alternation of generations, to succeed the gene having the high gene fitness to a child, as a basic rule. On the other hand, the individual yields of the pair of the parents are compared to enhance the succeeding probability as to the gene of the parent having the high individual yield, without according to the basic rule. A local solution is prevented from being led, by this manner. <P>COPYRIGHT: (C)2010,JPO&amp;INPIT

Description

  The present invention relates to a product allocating device, a product allocating program, a recording medium, and a product allocating for achieving an optimal allocation when a plurality of types of products are allocated to a plurality of types of mother bodies having different lengths or volumes. Regarding the method.

In pre-cutting of house structural materials, a plurality of types of products are cut out from a plurality of types of materials having different lengths. There is no limit on the number of materials used. A plurality of materials having the same length can also be used. Assign as much product as possible to one material. At this time, for example, a method of a one-dimensional bin packing problem is adopted in order to optimize the yield of the allocation result. For example, in the Fi rs t Fit Decreasing method, with respect to the longest product at the beginning, from the very long material in order, assigned the only product allocated. When it is full, assign the next product to the next material. Or changing the allocation order to change the material length, comparative evaluation the yield of a plurality of allocation results. At the end of such a trial, an optimal allocation result is obtained. (See Non-Patent Document 2)

In addition, there is a method using genetic engineering to deal with such a material assembling problem. When using genetic engineering, first prepare a large number of individuals with chromosomes showing various allocation results, and evolve the product allocation results through generational changes. Select individuals with chromosome represents an allocation result of the yield, to repeat generation change as better gene is taken over the child. Thereby, an individual having a chromosome showing the optimum allocation result is obtained.

We have previously proposed an Extended Elitism Method (EEM). In this method, a kind of ordered-based model was adopted, in which the product allocation order was included in the genetic information. By performing the crossover control gene level in this model, in a general building material precut plant the yield that is said less than 90%, could be improved to around 95% (see Non-Patent Document 1 .)
Japanese Patent No. 3565262 Toyoda J., Takeyasu K .: Extended Elitism Method for Cutting Stock Problem of Timber Precutting: International Journal of Information Systems for Logistics and Management. 3-1 (2007) 47-59. Toyoda J. and Takeyasu K .: A Revised First Fit Algorithm for Timber Precutting. International Journal of Computational Science 2-1, (2008), pp.92-107. 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, (2005), pp.274-282. Fleszar, K., Hindi, KS: New heuristics for one dimensional bin-packing, Computer & Operations Research 29 (2002) pp.821-839. Scholl A., Klein R. and Jurgens C .: BISON: the fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers and Operations Research, 24-7, (1997), pp.625-645 Schwerin P. and Wischer G .: The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP.International Transactions in Operational Research 4 (1997), pp. 377-389.

In the genetic engineering method as described above, it is necessary to perform control to repeat generational changes so that a good gene is inherited by a child. That is, as is the chromosome indicating the yield good allocation result of occurring earlier, it is desirable to achieve convergence promoted. At the same time, control that does not fall into a local solution is desired. Although the method described in Non-Patent Document 1 is a very excellent method, the convergence may not be good. Therefore, there is a demand for a generational change control method with even better convergence. The same problem occurs when a plurality of types of products are filled in a plurality of types of containers having different volumes as well as lengths.

  It is an object of the present invention to provide a product allocation device, a product allocation program, a recording medium, and a product allocation method that solve the above-described problems. According to the present invention, allocation of a plurality of types of products can be optimized for a plurality of types of mother bodies (materials, containers) having different lengths or volumes using genetic engineering techniques.

In each embodiment of the present invention, the above-described problems are solved by the following configurations.
<Configuration 1>
Any matrix from the length or volume different types of mutually maternal removed any number, these maternal allocates all products of a plurality of types of places constants to calculate the yield of allocation a product allocation apparatus, chromosome structure that displays a gene P to specify the order of allocating the product gene B to specify the type of matrix allocating each product and its parent for all of said products, each one individual An initial setting means for generating and storing in a storage device an initial individual group in which a predetermined number of pieces of individual data having chromosome data of the corresponding structure are collected, and the individual data stored in the storage device Chromosome data is read out, and according to a predetermined assortment calculation rule, for each individual data, the mother body specified by the gene P is assigned in the order of allocation specified by the gene B. The product allocation means for allocating all the products, executing the allocation process, the allocation yield of the entire base used for each individual data as the individual yield, the allocation yield per mother as the material yield, Data derived from a function whose value increases as the individual yield approaches 1 increases, and the degree of increase thereof becomes the individual adaptation rate data. The gene corresponding to the product assigned to the material having the higher material yield is higher. The data derived from the function is used as gene adaptation rate data, the result of the allocation process is acquired, and the allocation result data, the individual adaptation rate data, and the gene adaptation rate data are acquired for each individual data. Then, the adaptation rate calculation means to be stored in the storage device and the individual adaptation rate data of the individual data stored in the storage device are compared, and A pair of individual selection means for selecting a plurality of individuals and storing a new individual population in the storage device, and any individual data included in the new individual population, and included in the pair of chromosome data by comparing the gene of the same products, running for all the products the process of taking over any child one gene as a gene relevant product, the process of generating the individual data of the child, given Crossover control means that repeats until a number of individuals are generated, and new individual data generated by an arbitrary method is added to the individual data of the predetermined number of children to generate an individual population that becomes a new parent The diversification processing means to be stored in the storage device and until the number of generation change processing by the crossover control means reaches a preset upper limit value, or each individual data by the product allocation means Until the result of the allocation process reaches a preset target value, the allocation process by the product allocation unit, the allocation result data by the adaptation rate calculation unit, the individual adaptation rate data, the gene adaptation rate data acquisition process, and selection process of a new population of individuals by the individual selecting means, wherein the crossover control hand stage individual data generation processing of Yoruko, the various processing means of the control to repeatedly execute a process of generating a new population of individuals And the crossover control means compares the gene adaptation rates of the same product of the pair of parents and sets the gene with the higher gene adaptation rate as the gene of the child product. On the other hand, comparing the individual yield of a pair of parents, the parental gene with the higher individual yield is not subject to the basic rule, and Product assignment apparatus characterized in that a reference to increase the probability taken over as a child.

<Configuration 2>
In product assignment apparatus according to Structure 1, wherein the assortment calculation rule, the products and gene B and gene P as one set of data, the gene P to the gene B and the first key product in ascending order as a second key When the sorted product is taken out, the products are taken out, the taken out products are assigned to the mother body indicated by the gene B, and the gene B of the next taken out product displays another mother body, the other mother body When the product is assigned to the next and the gene B of the next extracted product displays the same parent body, it is determined whether the product can be assigned to the currently assigned parent body. A product allocating apparatus characterized in that the product is allocated to the base of the product, and if the allocation is impossible, the product is allocated to a new same base.

<Configuration 3>
In product assignment apparatus according to Structure 2, the gene P specifying the order of allocating the product to the matrix is a function of the material yield, gene P of products allocated to the same matrix will both equal Product allocating device characterized by being set as follows.

<Configuration 4>
In product assignment apparatus according to any of the first to 3, the individual adaptive rate data, said individual yield is smaller at a lower range than the average value of the individual yield of individuals included in the population of individuals, and A product allocating device, wherein the product allocating device is derived by calculating a function that greatly changes in a range from the average value to the maximum value.

<Configuration 5>
In the product allocating device according to any one of Configurations 1 to 4, the temperature of the parent individual is represented by a function indicating a lower value as the individual yield is higher, and the probability that the gene of each product of each individual is inherited by the child individual is expressed. , and one of the temperature of the pair of parents is lower than the other temperature, and can the one gene adaptation rate is higher than the other gene adaptation rate, one of the genes is carried over to the individual child, a pair When the temperature of one of the parent individuals is higher than the other and the gene adaptation rate is lower than the other gene adaptation rate, the other gene is inherited by the offspring individual, otherwise Is a function of a temperature difference and a gene adaptation rate, and the product allocation device is characterized in that the probability that one of the genes is inherited is determined by a monotonic increase or monotonic decrease function.

<Configuration 6>
A product allocation program for causing a computer of a product allocation apparatus to function as each means described in Configuration 1.

<Configuration 7>
A computer-readable recording medium recording a product allocation program that causes a computer of a product allocation apparatus to function as each means described in Configuration 1.

<Configuration 8>
A product allocating method including a step of executing a corresponding process by each means using the product allocating device according to Configuration 1.

<Effect of Configuration 1>
Which product information as to allocate and in what order to any material displayed in the gene, individuals with and Ru evolved to a large number of individuals to generation change with that gene, the allocation result of optimum yield as genetic information Is generated. The crossover control means sets rules for gene transfer so that it can evolve appropriately and early and not fall into a local solution. Chromosome genes with high individual yields are passed on to offspring, even if the gene adaptation rate is low, to prevent falling into a local solution. In addition, the generation of a new individual group by the diversification processing means also prevents falling into a local solution.
<Effect of Configuration 2>
Utilizing the information to be displayed in the genes, and the allocation result of each individual, it is possible to automatically calculate the yield or the like.
<Effect of Configuration 3>
Gene P when sorted in ascending order as a second key, high material yield base with is used in the allocation to the first, the combination of mother and products with a high material yield is more likely to be taken over to the next generation Become.
<Effect of Configuration 4>
The individual adaptation rate was set so that diversity of parent individuals was maintained and excellent individuals were preferentially selected.
<Effect of Configuration 5>
Even and if yield as a whole individuals even large genetic adaptation rate is low, if the yield is good as a whole individuals even low genetic adaptation rate is stochastically over to the child either gene I tried to make it.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings. The contents shown in the drawings and the following description are merely examples, and it goes without saying that the present invention is not limited to these. The computer program used for the product allocation apparatus of the present invention can be recorded on a computer-readable recording medium such as a CD-ROM and installed in any information processing apparatus for use. Furthermore, it can be used and distributed through a network.

(Device structure)
FIG. 1 is a functional block diagram showing an embodiment of the product allocation device of the present invention.
The apparatus of the present invention is realized by a personal computer having a known structure. The product allocation apparatus 10 shown in the figure includes a display 2, a main body control unit 3, a keyboard 4, and a mouse 5. A printer 11 is connected to the main body control unit 3. The keyboard 4 and the mouse 5 are input means for inputting calculation processing conditions. The display 2 and the printer 11 are output means for outputting the results of arithmetic processing.

As shown in the figure, computer programs such as initial setting means 21, product allocation means 22, adaptation rate calculation means 23, individual selection means 24, crossover control means 25, diversification processing means 26, and repeat control means 27 are installed. . These computer programs cooperate to execute arithmetic processing. The storage device 30, as shown in the figure, the initial population of individuals 31, material data 32, the product data 33, assortment calculation rules 34, generation change the upper limit value 35, yield target value 36, the parent of the individual group 37, an individual child Data such as the group 38, the best allocation 39, the best individual yield 40, and the like are stored. The functions and data structures of these programs will be described in detail later.

FIG. 2 is an internal block diagram of the main body control unit of the product allocation device.
A CPU (Central Processing Unit) 111, a ROM (Read Only Memory) 112, a RAM (Random Access Memory) 113, an HDD (Hard Disk) 114, and an input / output interface 115 are connected to the internal bus 110 of the computer. Yes. A display 2, a keyboard 4, a mouse 5, and a printer 11 are connected to the input / output interface 115.

The storage device 30 illustrated in FIG. 1 includes a ROM 112, a RAM 113, and an HDD 114. The arithmetic processing unit 20 includes a CPU 111, a ROM 112, a RAM 113, and the like. Data necessary for the arithmetic processing is mainly stored and saved in the HDD 114. A computer program executed by the CPU 111 is stored in the ROM 112 or loaded into the RAM 113 as appropriate.

FIG. 3 is an explanatory diagram of a data structure used in the product allocation device of the present invention. FIG. 4 is an explanatory diagram showing the schematic operation.
The outline of the function of each unit shown in FIG. 1 will be described with reference to FIGS. This apparatus first selects and takes out an arbitrary number of arbitrary mother bodies from a plurality of types of mother bodies having different lengths or volumes. Then, a plurality of types of all products of a predetermined number are assigned to these mother bodies. After that, the yield of the allocation is calculated. An example of the material data 32 is shown in the upper left of FIG. An example of product data 33 is shown in the upper right of FIG. The unit of material length and product length is mm. For example, there are 3 types of materials and 10 types of products. The initial setting means 21 has a function of generating an initial individual group 31 using the material data 32 and the product data 33 and storing it in the storage device 30. The material data 32 and the product data 33 are input in advance by the above input means.

In this invention, in order to employ a genetic engineering technique, chromosome data constituted by arranging various genes is defined. Individuals have chromosomes, and the properties of the chromosomes are inherited genetically by the next generation individuals. Each locus initial individual data shown in FIG. 3, the identification data of all the products are allocated et al are displayed in sequence. The product at each locus has a gene B and a gene P, respectively. The gene B displays information specifying the type of mother body to which the product is assigned. The gene P displays information that serves as a sort key for designating the order in which products are assigned to the mother body during the assortment calculation. In the initial individual data illustrated in FIG. 3, the product P1 at the locus 1 is assigned to the parent of the material type data M1 because the gene B is M1. At the same time, gene P is 0.1. The smaller this value is, the earlier it is assigned to one of the mother bodies. The gene P is a real number between 0 and 1, for example. Since the main part of the individual data is chromosome data, only the individual data will be described in the following description. The individual data includes individual yield as attribute data in addition to the chromosome data, as shown in the lowermost part of FIG.

  The product allocation unit 22 has a function of reading chromosome data of each initial individual data included in the initial individual population 31 stored in the storage device 30 and executing an allocation process. This allocation process is executed according to the assortment calculation rule 34 stored in the storage device 30. In the allocation process, for each individual data, calculation is performed in which all products are allocated to the mother body specified by the gene B in the allocation order specified by the gene P. When this calculation is performed, as shown in the middle part of FIG. 3, the initial individual data is sorted using the gene B as the first key and the gene P as the second key. Using the material assembling calculation data thus obtained, a calculation is performed in which the products P1, P3, and P6 are allocated in this order to the base body of M1.

Next, the adaptation rate calculation means 23 has a function of acquiring the individual yield, the material yield, the individual adaptation rate data, and the gene adaptation rate data and storing them in the storage device 30. Individuals yield is determined from the assignment result of the entire individual data is cut assignment step of the whole matrix used. Material yield is distillate allocation step of every mother. In the individual data shown in the bottom table of FIG. 3, examples of individual yield and material yield are shown. The allocation result data indicates which product is allocated to which matrix. The individual adaptation rate data is derived from a function of individual yield, as will be described later. The gene fitness data is derived from a function of material yield, as will be explained later.

  With the above processing, as shown in FIG. 4, preparation for obtaining the parent individual group 37 from the initial individual group 31 (FIG. 1) was completed. The comparison process in the upper right of FIG. 4 is a process for determining termination. In the initial state, the end determination process is skipped, and the individual selection means 24 (FIG. 1) executes the middle selection process in FIG. The individual selection means 24 compares the individual adaptation rate data of each individual data stored in the storage device 30 and selects a plurality of individuals with good adaptation rates as parent individual groups 37, which are stored in the storage device 30. Remember. This is to change generations leaving only parents with good individual yield.

  The crossover control means 25 has a function of reading one pair of individual data included in the parent individual group 37 and generating individual child data in order. A child individual group 38 is generated from the individual data of a predetermined number of children. The crossover control means 25 compares genes of the same product (locus matching) included in the chromosome data of the pair of individual data. Then, the process of taking over one of the genes as the gene of the corresponding product to the child is executed for all products. Thus, individual data of one child is generated. This process is repeated until a predetermined number of individuals are generated. In the present invention, an annealing method is employed particularly in this crossover process. Specific processing will be described later.

  The diversification processing means 26 is a gene for any of several loci for an individual selected from a predetermined number of children generated by the crossover control means 25 with a predetermined probability (mutation probability). A function of generating a new individual population 41 and storing it in the storage device is performed by performing a mutation operation that changes the number of the selected individuals or replacing the selected individual with new individual data generated by an arbitrary method. Thereafter, the assortment calculation by the product allocation means 22 is executed again. Then, the allocation process by the product allocation unit 22, the acquisition process of the adaptation rate by the adaptation rate calculation unit 23, the individual selection process by the individual selection unit 24, the individual data generation process of the child by the crossover control unit 25, and the diversification The process of generating a new individual group by the processing means 26 is repeated.

The iterative control means 27 repeats this iterative control until the number of generation change processes by the crossover control means 25 reaches the generation change upper limit 35. Also, alternatively, the result of the allocation process for each individual data by the product assignment unit 22, as compared to the yield target value 36 are repeated until a target value. Finally, data indicating the best allocation 39 and the best individual yield 40 is obtained and output to the display 2 and the printer 11 to complete the processing.

In the EEM (Extended Elite Selection Method) described in Non-Patent Document 1 above, a crossover control parameter (CCP) which is a function of a remaining material ratio (= 1−material yield) of a material to which a product is assigned. Defined. This CCP was used as a parameter for each gene constituting the chromosome to be passed on to the next generation. That is, child 1 is generated from parent 1 and parent 2 according to the following rule. Further, a child 2 is generated by replacing the relationship between the parent 1 and the parent 2 of this rule.
If CCPi (Parent 1) ≥ Rnd, i-th gene of child 1 = i-th gene of parent 1
If CCPi (parent 1) <Rnd, the i-th gene of child 1 = i-th gene of parent 2, where CCPi (parent 1) is the CCP of the i-th gene of parent 1, Rnd is (0,1 ) Random number

  In this way, if the CCP function is defined so that a “good gene” with a low residual material rate is inherited, individuals with better chromosomes are born as a result of the generation change, and convergence can be ensured. However, in this EEM, the child will inherit the “good gene” from only one parent. On the other hand, in the present invention, a “good gene” having a high yield can be inherited from each parent, so that even better convergence can be expected. Moreover, the risk of falling into a local solution was avoided by using a probability function based on the annealing method for the crossover rule. Therefore, according to the product allocation device of the present invention, it is possible to efficiently allocate a plurality of types of products to a plurality of types of mother bodies (materials and containers) having different lengths or volumes by genetic engineering techniques. The allocation result can be acquired.

(Explanation of symbols used)
Next, the above process will be described in a more specific embodiment. In the following description, the symbols shown in Table 1 are used. The material length type was expressed as “material length type”.

ただし、（２）式は、材料に割り付けられた製品の長さの合計が、材料の長さ以下であることを示す。（３）式はすべての製品はどれかの材料に割り付けられることを示す。（４）式は１つの製品が同時に複数の材料に割り付けられないことを示す。 ( Yield target)
This example introduces the calculation of the optimal allocation method when cutting a precut product from a material. The optimum allocation is determined by whether the material yield is maximum as described below.
Now, there are enough materials of m lengths b _t (t = 1,..., M), and when cutting out all products of length l _i (i = 1,..., N), When the material cost of using the wood length species t and _{c t, CSP (Cutting Stock Problems} ) can be expressed by equation (1) below.

However, equation (2) indicates that the total length of the products assigned to the material is equal to or less than the length of the material. Equation (3) indicates that all products are assigned to any material. Equation (4) indicates that one product cannot be assigned to multiple materials at the same time.

ここで分子の製品長累計は所与であるので、(1)式で使用コストｃ_ｔを材長ｂ_ｔに置き換えて（６）式のようにすればよい。

なお、実際のＣＳＰでは材料の両端を整える「鼻切」および製品を切り出す際の「鋸代」を考慮する必要があるが、本質的な問題ではない。
以上の内容において、ｍ＝１とすれば通常の一次元ビンパッキング問題（Bin Packing Problem: BPP）となることは言うまでも無い。
既存の計算方法を使用して、予め最良と思われる個体歩留を計算しておき、図１に示す最良個体歩留４０を記憶しておくとよい。他の計算方法よりも良い歩留が得られたらそれを採用するというように、本発明の装置を利用するとよい。 In CSP, it is common to aim for the maximum yield. The yield y is expressed by the following equation (5).

Here, since the product length cumulative molecules are given, it is sufficient (1) as in replacing the use cost c _t to Zaicho b _t (6) formula in formula.

In an actual CSP, it is necessary to consider “nose cutting” for adjusting both ends of a material and “saw allowance” for cutting a product, but this is not an essential problem.
In the above contents, it goes without saying that if m = 1, it becomes a normal one-dimensional bin packing problem (BPP).
An individual yield that seems to be the best is calculated in advance using an existing calculation method, and the best individual yield 40 shown in FIG. 1 may be stored. As to adopt it Once good yield is obtained than other calculation methods, it may utilize the apparatus of the present invention.

(Initial population and generational change)
In the present invention, an individual structure having a chromosome with good convergence is defined. Each individual's chromosome has information indicating the result of assignment, in which all products are assigned to any one of the materials. In the initial population, those with good and bad allocation results are mixed. Such a predetermined number of individuals are generated, and generational changes are made so that good genes are inherited until the objective is achieved. Each of the generational change, to evaluate each individual of the yield by applying will be described later (assortment calculation rules).

(Definition of individual structure)
The chromosome of the individual used has gene B and gene P as shown in Table 2. There are as many gene loci as there are products to be assigned, and there is a one-to-one correspondence with the assigned products. Gene B (labeled “GeneB” in Table 2) designates the material length type to which the product is assigned. Gene P (indicated as “GeneP” in Table 2) designates the order of allocation in the group of products allocated to the same material length type.

(Assortment calculation rules)
By defining the individual structure as described above, it is possible to control the evolution of individuals by generational change. The assortment calculation rule is used for evaluation of individual yield and calculation of parameters for controlling generation change. Each individual has a double gene structure chromosome having gene B and gene P at each locus. For this chromosome, assortment calculation is performed according to the following rules. Note that “nose clip” and “saw allowance” can be incorporated by adjusting the material length and product length, so they are ignored here for simplicity.
First, sort the products in ascending order with GeneB as the first key and GeneP as the second key, take out the products in the sorted order, and repeat the following steps (Step 1 and Step 2) until all products are assigned.
Step1. If GeneB changes, assign it to a new material with a new material length
Step2. If GeneB does not change, assign the product to the currently assigned material if the product can be assigned, and assign it to a new material of the same material type if it is not possible.

(Gene structure to ensure convergence)
In the above assembling rules, the allocation order is determined by the relative size relationship of GeneP. As a result, the material-product group changes sensitively due to a slight change in GeneP, so it is not possible to expect an evolution to a stable optimal solution by a method such as ordinary uniform crossover. Therefore, in order to avoid this, a material-product group having a high material yield is apt to be handed over to the next generation. Specifically, the following two controls are performed. It is necessary to design a gene structure capable of this control.
Control 1: Material with a high material yield—Products belonging to a product group are preferentially assigned earlier so that the group is not destroyed by the combination of the preceding materials.
Control 2: Material with high material yield-Ensure that the genes of products belonging to the product group are inherited as much as possible to the next generation through crossover operations.

(Control 1)
For control 1, “individual yield” and “material yield” are used as parameters. Furthermore, gene P is defined as follows. Made to correspond to the product i to i-th locus of wood length species assigned to t _i, the assignment order and s _i, the length of the product i and l _i. Assume that a set of materials of the material type t is B _t , a length is b _t , and a material belonging to B _t is k ^(t) (= 1, 2,...) Let I _{k (t)} . At this time, the yield y _{k (t)} of the material k ^(t) is defined by the following equation (7). This yield is a yield in material units with respect to the yield of the whole individual of the formula (5). Equation (5) is “individual yield” and equation (7) is “material yield”.

(Control 2)
Using this material yield, gene B and gene P at the locus of product i are expressed as follows.

  Here, gene B displays a value specifying any material from 1 to m. Gene P is a numerical value between 0 and 1 and serves as a sort key. ε is a constant that is adjusted to ensure that the gene P of the product group assigned to the same material has the same value, and is a sufficiently small value for the material yield. When the gene P is defined as shown in the equation (9), the gene P of the product assigned to the material having a higher material yield becomes a small value, and when sorted, the gene P is arranged at the head side and the order of the assembling calculation is accelerated. Therefore, allocation is performed preferentially. For this reason, it is suppressed that a material-product group with a high material yield is destroyed by a product with a low material yield, and convergence is improved. The initial value of gene P can be determined using a random number.

  The method for generating the initial individual is not particularly limited, and may be generated by a method according to a predetermined rule. Individuals may be generated by a method using random numbers. The method according to a predetermined rule is a method of assigning a product to a material according to a predetermined rule and setting the gene B and the gene P based on the result. Examples of this method include the Revised First Fit Descending (RFFD) method described in Non-Patent Document 2 by the present inventors, and the Revised First Fit (RFF) method in which the same algorithm is applied without particular conditions for products. However, it is not limited to these.

  In general, when an initial individual is generated by a method according to a predetermined rule, since the individual is relatively excellent from the beginning, it converges quickly, but it tends to drop into a local solution. On the other hand, when an initial individual is generated by a method using random numbers, it is difficult for a drop to a local solution to occur, but it takes time to converge. Therefore, some individuals are generated by a method according to a predetermined rule, and an initial population is generated by generating the remaining individuals by a method using random numbers. As a result, convergence can be accelerated while suppressing a drop in the local solution. The proportion of individuals generated by a method according to a predetermined rule is, for example, 10 to 90%. The results vary depending on the combination of material type and product. A good result may be obtained if an individual is generated only by a method according to a predetermined rule. In addition, a good result may be obtained when an individual is generated only by a method using random numbers. However, the combination of both is likely to give a better result.

(Generation of initial population)
The initial setting means 21 generates an initial individual population 31 by generating a plurality of individuals defined as described above. Hereinafter, an example of a method for generating the initial individual population 31 will be described.
In this example, the RFFD is applied to one individual, and the products are generated by applying the RFF to the remaining individuals by rearranging the products a required number of times at random. However, in order to ensure the diversity of the initial individuals, not all of them are generated by RFFD and RFF, but the number of individuals corresponding to a predetermined RFF generation ratio α, and the rest are generated by random numbers. Specifically, it is performed as follows.

  Here, β is a parameter that does not protrude from the range of the value of the gene P obtained by equation (9), and is set to a value that is approximately the lower limit by looking at the distribution of the remaining material ratio through a prior experiment.

(Calculation of adaptation rate)
As described with reference to FIG. 4, after the initial setting unit 21 generates the initial individual population 31, the product allocation unit 22 performs the material combination calculation, and then the adaptation rate calculation unit 23 performs the individual adaptation rate and the gene adaptation rate. Calculate When the gene P is calculated based on the material yield, the gene P is updated using the equation (9).

(1) Gene adaptation rate The gene adaptation rate is an index indicating the superiority or inferiority of the allocation of each product in each individual. The expression method is not particularly limited. In one example, the gene fitness ratio GFR (Gene Fitness Ratio) can be expressed using the material yield as shown in the following equation (13). According to (13), the higher the gene gene adaptation rate that corresponds to the product of the material yield is allocated to high material, such genes are carried over to the next generation of the individual to be generated by the crossover operation Cheap.

(2) Individual adaptation rate The expression method of the individual adaptation rate is not particularly limited as long as it is an index indicating the superiority or inferiority of each individual. In one example, the individual adaptation rate is calculated based on a function in which the degree of increase in value increases as the individual yield expressed by equation (5) approaches 1. By setting in this way, an individual with a high individual yield is selected by the individual selecting means 24 and becomes a parent individual, and convergence is improved.
For example, the individual adaptation rate a is obtained by scaling the individual yield y (0 ≦ y ≦ 1) of the equation (5) by the function F, and can be expressed as the equation (14).

Since this individual adaptation rate becomes a selection criterion for selecting a parent individual, the survival distribution of the individual depends on this function and consequently affects the convergence. The balance between individual diversity and excellence is important for the convergence to the optimal value. Therefore, the average value of individual yields of all individuals is obtained, and the individual adaptation rate is small when the individual yield y is lower than the average value, and is scaled by a function that varies greatly from the average value to the maximum value. Is reasonable. An example of such a function, F (y) ⁼ a ^{y 10.}

(Individual selection)
The individual selection means 23 selects an individual to be a parent when changing generations from a given individual group. For example, select one third of the population and leave it, discarding the others. The ratio to be selected varies depending on the case. For example, any ratio of 10 to 90% may be adopted. This will leave the parents with good genes preferentially and make the following adjustments. For example, first, all individuals are sorted in the order of individual adaptation rates, and a predetermined number of individuals with high individual adaptation rates are selected. This is the elite selection method. Next, a predetermined number of individuals are selected from the remaining individuals by the roulette selection method. The selection probability of each individual may be proportional to the individual adaptation rate. In addition, various selection methods using the individual adaptation rate may be combined.

  Diversity is lost only by the elite selection method and it tends to fall into a local solution. Convergence is not good only by the roulette selection method. Therefore, it is preferable to combine the elite selection method and the roulette selection method. For example, 5% of the individuals to be selected are selected by the elite selection method. The rest is selected by the roulette selection method or other selection methods. In addition to the roulette selection method, the ratio of using the elite selection method and other selection methods is suitably about 3% to 30%. It is good to adopt what is suitable for each case.

(Crossover process)
FIG. 5 is a diagram for explaining the operation of the crossover control means.
The crossover control means 25 takes out individual data included in the parent individual population 37 after selection as a parent individual one by one and generates child individual data by crossover control. These will be the next generation child population. In the crossover control, the gene adaptation rate of each gene at the same locus of the pair of parent individuals taken out is compared individually. In the figure, a pair of parents is indicated as parent 1 and parent 2. Also, to help communicate the crossover control, each locus describing the timber length species product is allocated (A, B, C, D ··) and GFR only.

  As a rule, the gene adaptation rates are compared, and the gene of the parent individual with the higher gene adaptation rate is inherited to the child. The inherited genes are GeneB and GeneP, respectively.

このような交叉方法を以下、対戦交叉法（Tournament Crossover Operation Method: TCOM）」と呼ぶ。

Such a crossover method is hereinafter referred to as “Tournament Crossover Operation Method (TCOM)”.

  This TCOM respects the group of products assigned to the material, regardless of the gene structure whose chromosome is the product sequence, by the above two controls, and for each gene without expanding exploration space due to wasteful redundancy. Compared to GFR, it is characterized by increasing the adaptation rate of individuals as a whole of genes by passing on a gene with a high adaptation rate to the next generation.

  However, since the gene to be inherited is determined by the rule of the formula (15) in this method, for example, the gene of the product assigned to the material having a very high material yield is “always” inherited to the next generation. However, even if some material yields are high, the individual yield as the sum of the material yields is not always high. In some cases, lowering the yield of one material can improve the yield of other materials and increase the overall yield. However, if the crossover method based on the rule of equation (15) is fixedly handled, For example, a set of material yield genes that is almost as close to 1 is surely inherited by the next generation, and there is almost no possibility that the material yield will be lowered. In this case, there is a risk of entering a dead end and falling into a local solution.

  Individuals generated by RFF, in particular, have a high yield combination due to good combination preemption, which is a feature of the FF method, while the yield of the material assigned at the end is low and the overall yield is not high. There is a case. In fact, as described later, in the previous TCOM proposal (Toyota, 2008), when the initial individual generation rate by RFF was set to α = 1 and α = 0.5 in the BPP benchmark evaluation I know it will be worse.

  In order to solve this, in the present invention, a stochastic element is incorporated into the crossover rule of the equation (15). Therefore, we will adopt the concept of simulated annealing. In the annealing method, the internal temperature is defined following the phenomenon in which atoms move from the initial high energy state to the energy minimum state as the internal temperature slowly cools. This is a technique to gradually converge the exploration range as the temperature decreases. This idea is incorporated into the crossover rule as follows.

(Crossover rule)
The “temperature” T ^(p) of the parent individual P (P = 1, 2) is defined as a function of the parent individual yield as follows. Thus, the higher the individual yield, the lower the temperature.
T ^(p) = (1- y ^(p) ) × γ P = 1,2 (16)
Here, y ^(p) is the individual yield of the parent individual P, γ is an adjustment parameter, and γ = 0.1 in this discussion. The probability that the child's i-th gene is inherited from parent 1 is defined as Pr ⁽¹⁾ , and this is defined as a function of the parents' GFR and temperature as follows.

FIG. 6 is an explanatory diagram in which the probability function of equation (17) is graphed.
The probability that a gene is inherited from parent 1 is Pr ⁽¹⁾ . The probability that the gene is inherited from parent 2 is Pr ⁽²⁾ = 1−Pr ⁽¹⁾ . Using the probability function of equation (17), the crossover rule of equation (15) is changed to the following equation. FIG. 6 shows a probability curve (when T = 0.01) of inheriting the gene of parent 1.

  According to this rule, an individual with a low individual yield has a high internal energy, so even if a gene of this individual has a high gene adaptation rate, it will lose the survival competition with the gene of an individual with a relatively low internal energy. It means that there are cases. Therefore, even if the gene of a product assigned to a material with an extremely high material yield is used, if the individual's yield is lower than the partner's individual yield, the child may not be inherited. become. This is expected to reduce the risk of falling into a local solution.

That is, the temperature of the parent individual is expressed by an arbitrary function that shows a lower value as the individual yield is higher . Then, the probability that the gene of each product of each individual is inherited by the child individual is made to depend on this temperature. When one temperature of a pair of parent individuals is lower than the other temperature and one gene adaptation rate is higher than the other gene adaptation rate, one gene is inherited by a child individual. When one temperature of the pair of parent individuals is higher than the other temperature and one gene adaptation rate is lower than the other gene adaptation rate, the other gene is inherited by the offspring individual. In other cases, the probability that one of the genes will be inherited is determined by a function of the temperature difference and the gene adaptation rate. The exp curve in the graph of FIG. 6 indicates that the probability is obtained by a monotonically increasing function or a monotonically decreasing function. Even and if yield as a whole individuals even large genetic adaptation rate is low, if the yield is good as a whole individuals even low genetic adaptation rate is stochastically over to the child either gene To prevent falling into a local solution.

(Diversification processing)
The diversification processing means 26 replaces a part of the individual population with a newly generated individual or causes a mutation in a part before the next generation process. By this processing, it is possible to suppress a drop in the local solution. The selection of individuals to be diversified may be performed by a random method or by a method other than the random method. For example, individuals with a low individual adaptation rate may be preferentially selected and replaced. In this embodiment, the diversification process is performed after the crossover process. The ratio of individuals to be diversified is not particularly limited, but is about 5 to 40%, for example. The timing for performing the diversification process is not particularly limited. It may be performed before crossover processing or before individual selection.

  Mutation involves mutating selected genes in selected individuals. The gene may be selected by a random method, but may be selected by a method other than a completely random method, for example, a gene having a low gene adaptation rate is preferentially selected. The method for mutating the gene is not particularly limited, but in one example, the gene can be mutated by resetting the gene in accordance with the setting rules of the gene B and the gene P in the expression (12). The number of mutant loci is not particularly limited, but is 3 to 30% of the total number of loci, for example. Mutation may occur in only one of gene B and gene P, or in both. When gene B is mutated, it is reasonable and preferable to update gene P based on the content after the mutation. On the other hand, in the case of gene P, it is preferable to change it alone.

(Repeated control)
The repetition control unit 27 performs control so that the above generation change is repeated until the end criterion is satisfied. The termination criterion is not particularly limited. For example, (1) the individual adaptation rate with the highest individual adaptation rate among individuals belonging to the population exceeds the target value, (2) the number of generations of the population exceeds the reference value, and the like. Can be mentioned. Only (2) may be used as the end criterion. It may not be efficient to continue processing after the target individual adaptation rate is exceeded. Therefore, it is preferable to determine that the termination criterion is satisfied when the criteria (1) and (2) are satisfied by using the criteria (1) and (2) together.

  After completion, an individual belonging to the group having the maximum individual yield is taken out. Then, using the chromosome B and the chromosome P, products can be assigned to materials according to the above-described product assignment rules, and the assignment result can be output.

(Schematic operation of the device)
7 and 8 are operation flowcharts of the above-described apparatus.
The computer program of the above apparatus operates in the following procedure, for example. First, in step S11, the initial setting means 21 generates an initial individual population. That is, a sufficient number of individuals having a chromosome having a predetermined structure are generated. Individual data including the chromosome structure data is stored in a storage device. The product allocation means 22 reads individual data from the storage device one by one from the initial individual population 31 thus obtained, and executes the processing from step S12 to step S20 for all the individuals.

First, in step S12, target individual data is selected. In step S13, sort processing is performed using GeneB and GeneP. After that, in step S14, assortment calculation (described in the “Assortment calculation rule” section) is executed. In step S15, the individual yield of the individual data is calculated. Further, the material yield of each material used in step S16 is calculated. In step S17, GeneP as a sort key is calculated using equation (9) and rewritten. In step S18, GFR (gene adaptation rate) is calculated. In step S19, the individual adaptation rate is calculated.

  In step S20, it is determined whether calculation has been completed for all individuals. If the result of this determination is no, the process returns to step S12. If yes, the process ends and the process proceeds to the process of FIG. In the flowchart of FIG. 8, steps S <b> 31 to 33 are processing of the repetition control unit 27. Step S34 is a process of the individual selection means 24. Steps S35 to 37 are processing of the crossover control means 25. Step S38 is processing of the diversification processing means 26.

In step S 3 1, the individual data with the maximum individual yield is read from the target individual data. For example, in step S15, a process for selecting an individual with a high individual yield may be performed simultaneously with the calculation of the individual yield. In step S 3 2, it is determined whether or not the maximum yield is the target value. If it is the target value, the process is terminated. In step S 3 3, the decision of whether you run the generation change until the maximum number of generations. If the result of this determination is yes, the process is terminated.

When both the determination results of step S32 and step S33 are no, the process proceeds to step S34 and subsequent steps. That is, the next generation change is executed. In step S 3 4, using the result of the sorting, a good individual individuality adaptation rate for example, to select only one-half of the total. This becomes the parent individual group 37. In step S 3 5, selects a pair of parent from among the population of individuals. Then, already in the manner described, the crossover control at Step S 3 6. In step S 3 7, the determination whether the generated number required child individual data. If the result of this determination is yes, the process proceeds to step S38, and if no, the process returns to step S35. In step S 3 8, the diversification process. Then, the material assembling process after step S12 in FIG. 7 is repeated again.

(Evaluation based on BBP benchmark problem)
In material assembling calculation, it is preferable to compare the calculation results obtained by various calculation methods and adopt the best allocation result. This is because the optimal calculation method often differs depending on the combination of materials and products. Accordingly, a long calculation processing time by the computer hinders work efficiency. Therefore, the following benchmark test is performed to demonstrate the high practicality of the apparatus of the present invention.

In the above TCOM model, the material length type m = 1, depending on the BPP benchmark problem: comparison with the Extended Elitism Method (EEM) GA model (Toyoda, et al., 2007) and the RFF of the TCOM model Comparison was made when the initial individual production rate α was 1, 0.5, and 0. Benchmarks used was item size for the bins capacity 100000 are uniformly distributed in the range of (20000,35000). There are 10 problems that are considered very hard (very difficult to get the minimum solution) with 3 to 5 items in the bin. This shows the minimum number of bins currently known.

As a result, the superiority over EEM was confirmed, and the difference according to the ratio of initial individual generation by RFF was as follows. When the initial individual ratio α = 0.5, the minimum bin solution is obtained by 8 out of 10 questions. When α = 0, although the convergence speed is slow, the obtained solution is the same as when α = 0.5. there were. However, the case of generating all the initial individual in RFF and RFFD as alpha = 1, was obtained with minimal solution of 10 questions are only 5 questions, TCOM danger of falling into a local solution depending on the configuration of the initial individual body Confirmed that there is.

Therefore, a new TCOM model incorporating a stochastic element according to the present invention is applied to the same benchmark problem, and its effect is confirmed. In the present invention, new individuals are not introduced in the mutation performed to maintain diversity in the previous model, but priority is given to shortening the calculation time over diversity. Other conditions are the same as in the previous model, the number of individuals is 100, the maximum number of generations is 1000 generations, and various parameters are set as equation (18), and the best results are adopted in 10 trials. Benchmark issue, use 10 example of problems that are the same V ery Hard before, environment is the same as the previous shown in Table 3 Run.

  The execution results are shown in Table 4. NewTCOM is the new model after this improvement. “All RFF” indicates that α = 100%, “50% RFF” indicates α = 50%, and “All RN” indicates that α = 0% and all are generated by random numbers. "Hits" is the number of the problems with the optimum value out of 10 problems, "Av.Rel." Is the relative deviation average of each problem, "Max.Rel." Is the maximum relative deviation, and "Av.Abs" "" Is the absolute deviation average, and "Max.Abs." Is the maximum absolute deviation. The relative deviation is calculated as 100 × (running value−minimum solution) / minimum solution, and the absolute deviation is calculated as (running value−minimum solution). "Av.Time" is the average calculation time and the unit is second. As can be seen from Table 4, in this improved model, even when α = 100%, 8 questions were the minimum solution, and the average calculation time was the earliest 3 seconds due to the excellent initial individual effect.

(Evaluation based on housing pre-cut material data)
Evaluate the improvement model with the same residential pre-cut data as applied to the previous model. The residential pre-cut CSP is a problem of cutting a member (product) having a length required for residential construction from a wood base material having several types of lengths. Here, it was applied to the horizontal members of two standard detached houses ( Table 6 ). These horizontal members are divided into 16 and 18 lots that can be cut from the same base material such as cross-sectional shape (Shape), tree species (Spec.), Grade (Grade), etc., and the number of products cut out for each lot (Num.) And the base material group (Kinds of Material) used are also different. In addition, since the cross-sectional shape differs for every lot, the yield of the whole house is compared by the volume yield by volume.
As in the previous case, the parameters are set to λ = 0.2 in equation (18) and the number of individuals is 100. The maximum number of generations is set by equation (19), which is a setting rule when considering practical use in the previous report. Also, the number of trials is the same as the previous 10 times. The results are shown in Table 5 for House 1 and Table 6 for House 2.

  In Tables 5 and 6, “Num. Of Prd.” And “Num. Of Mtr.” Are the number of products and the length type of each lot, respectively. “Max. Gen.” is the maximum number of generations based on the rule of equation (19). "Yield Rate" in the old and new TCOM column is the maximum yield obtained in 10 trials, "Num." Is the number of times the maximum yield was obtained in 10 trials, and "Time" is the calculation time in seconds. did. Here, the data of the old TCOM is from the previous report. Note that Time is slightly smaller because it was a single significant digit last time, and this time and the previous time are virtually the same. As a result of the above, in the evaluation with precut data, the result was almost the same as the previous model. This is because it is assumed that the yield is almost the optimum value in any residence, and the maximum number of products is 40 or less, and it can be estimated that there is no significant difference in yield and time.

(Summary)
For the one-dimensional Multiple Stock Length CSP that handles multiple material lengths, the previously reported GA model using TCOM has a risk of falling into a local solution because the gene to be inherited is definitely determined by TCOM crossover. It pointed out. As a breakthrough, we proposed a new TCOM that incorporates the element of probability by considering the parent individual's (1-yield) as “temperature” and incorporating the concept of annealing in the gene exchange decision process. We applied this to the same BPP benchmark data and pre-cut data as before, and compared the old and new TCOM. As a result, in the benchmark data, when the initial individuality formation by RFF was 100%, the old model had a minimum of 5 questions out of 10, while the new TCOM had a minimum of 8 questions in a shorter time. I was able to get it. In addition, it was confirmed that the performance was equivalent to the precut data.

It is a functional block diagram which shows the Example of the product allocation apparatus of this invention. It is an internal block diagram of the main body control part of said product allocation apparatus. It is explanatory drawing of the data structure used with the product allocation apparatus of this invention. It is explanatory drawing which shows schematic operation | movement of the product allocation apparatus of this invention. It is explanatory drawing which shows the operation example of crossing control. It is explanatory drawing of the probability curve by an annealing method. It is an operation | movement flowchart (the first half) of the apparatus of this invention. It is an operation | movement flowchart (second half) of the apparatus of this invention.

DESCRIPTION OF SYMBOLS 10 Product allocation apparatus 11 Printer 20 Arithmetic processing apparatus 21 Initial setting means 22 Product allocation means 23 Adaptation rate calculation means 24 Individual selection means 25 Crossover control means 26 Diversification processing means 27 Repetition control means 30 Storage device 31 Initial individual population 32 Material data 33 product data 34 assortment calculation rule 35 generation change the upper limit value 36 step populations 39 best allocation of distillate target value 37 parent population of individuals 38 children 40 best individual yield

Claims (8)

Take an arbitrary number of matrixes from multiple types of matrixes of different lengths or volumes, assign multiple types of all the products of a predetermined number to these matrices, and calculate the allocation yield A product allocation device,
Each individual has a chromosome having a structure for displaying the gene B for designating the type of mother body to which each product is assigned and the gene P for designating the order in which products are assigned to the mother for each product. Initial setting means for generating an initial individual group in which a predetermined number of pieces of individual data having chromosome data are collected and stored in a storage device;
The chromosome data of each individual data stored in the storage device is read out, and in accordance with a predetermined assortment calculation rule, for each individual data, the matrix specified by the gene P is assigned in the order specified by the gene B. Product allocating means for allocating all the products and executing an allocation process;
The allocation yield of the whole mother used for each individual data is the individual yield, the allocation yield for each mother is the material yield, and the value increases as the individual yield approaches 1, and the degree of increase is large. The data derived from the function is used as the individual adaptation rate data, the data derived from the function that is higher for the gene corresponding to the product assigned to the material having a higher material yield as the gene adaptation rate data, and the allocation process An adaptation rate calculation means for acquiring allocation result data, the individual adaptation rate data, and the gene adaptation rate data for each individual data to be stored in the storage device;
Individual selection means for comparing individual adaptation rate data of each individual data stored in the storage device, selecting a plurality of individuals having a high individual adaptation rate, and storing a new individual population in the storage device;
A pair of individual data included in the new individual population is read out, the genes of the same product included in the pair of chromosome data are compared, and either gene is used as a gene of the corresponding product as a child. A crossover control means for executing the process of taking over for all products and generating the child individual data until a predetermined number of individuals are generated;
Diversification processing means for adding new individual data generated by an arbitrary method to the predetermined number of child individual data, and generating a new parent individual group and storing it in a storage device;
Allocation by the product allocation means until the number of generation change processes by the crossover control means reaches a preset upper limit value or until the result of the allocation process of each individual data by the product allocation means reaches a preset target value Processing, acquisition processing of the allocation result data, the individual adaptation rate data, and the gene adaptation rate data by the adaptation rate calculation means, selection processing of a new individual population by the individual selection means, and a child by the crossover control means Repetitive control means for performing control so as to repeatedly execute the individual data generation process and the new individual population generation process by the diversification processing means,
The crossover control means compares the gene adaptation rate of the same product of the pair of parents with the basic rule that the gene with the higher gene adaptation rate is the gene of the child product. Compared with the individual yield of the parent of the parent, for the gene of the parent with the higher individual yield, there is provided a standard for increasing the probability of being inherited as a child gene without following the basic rule. Product allocation device. In the product allocation device according to claim 1,
The assortment calculation rule is that the product, gene B, and gene P are a set of data, the gene B is the first key, the gene P is the second key, the products are sorted in ascending order, and the products are taken out in the sorted order. The assigned product is assigned to the mother body indicated by gene B. When gene B of the next removed product indicates another mother body, the product is assigned to the other mother body and then taken out. When the gene B of the product displays the same matrix, it is determined whether the product can be allocated to the currently allocated matrix, and if it can be allocated, the product is allocated to the currently allocated matrix and allocated. If it is impossible, the product allocating apparatus is characterized in that the product is allocated to a new same base material. In the product allocation device according to claim 2,
Gene P to specify the order of allocating the product to the matrix is a function of the material yield, gene P of products allocated to the same matrix is characterized in that it is set to be the same value both Product allocation device. In the product allocating device according to any one of claims 1 to 3,
The individual adaptation rate data, said individual yield is smaller at a lower range than the average value of the individual yield of individuals included in the population of individuals, and a function that varies greatly in the range of the maximum value from the average value Product allocating device characterized by being derived by calculation. The product allocation device according to any one of claims 1 to 4,
The temperature of the parent individual is expressed as a function that shows a lower value as the individual yield is higher , and the probability that the gene of each product of each individual is inherited by the child individual is determined. If one gene adaptation rate is higher than the other gene adaptation rate, one gene is inherited by the offspring individual, and the temperature of one of the pair of parent individuals is higher than the other temperature. When one gene adaptation rate is lower than the other gene adaptation rate, the other gene is inherited by the offspring individual, otherwise it is a function of temperature difference and gene adaptation rate , A product allocating apparatus characterized in that a probability that any gene is inherited is determined by an increase or monotonic decrease function .   A product allocation program for causing a computer of a product allocation device to function as each means according to claim 1.   A computer-readable recording medium having recorded thereon a product allocation program that causes a computer of the product allocation apparatus to function as each means according to claim 1.   A product allocating method including a step in which each means executes a corresponding process using the product allocating device according to claim 1.

Images