JP6540360B2 - Material separation planning device for steel products, method for making steel distribution separation plans, and program - Google Patents

Description

  TECHNICAL FIELD The present invention relates to an apparatus for planning a plan for separating steel products, a method for planning a plan for separating steel products, and a program, and in particular, is suitable for use in creating a plan for separating steel products in a yard.

  In steel processing, which is an example of a metal manufacturing process, for example, when transporting steel materials from a steel making process to a rolling process of the next process, steel materials are temporarily placed in a temporary storage place called a yard, and then It is unloaded from the yard at the processing time. An example of the layout of the yard is shown in FIG. The yard is, as shown in FIG. 5, storage areas 501 to 504 which are sectioned in the vertical and horizontal directions as a buffer area for supplying steel products such as slabs paid out from the upstream process to the downstream process. The vertical divisions are often referred to as "ridges" and the horizontal divisions as "columns". The cranes (1A, 1B, 2A, 2B) are movable in the ridge to transfer steel between different rows in the same ridge. In addition, transfer the steel between the ridges by the transfer table. When creating a transport command, specify "building" and "row" to indicate where to transport the steel material (numbers (11) attached to the storage areas 501 to 504 in Fig. 5 in parentheses, (12), (21), (22)).

  The basic work flow in the yard is shown in FIG. 5 as an example. First, the steel material carried out from the continuous casting machine 510 of the steel making process which is the previous process is carried to the yard by the receiving table X via the piler 511, and the storage area 501 divided by the cranes 1A, 1B, 2A, 2B. It is transported to any one of .about.504 and placed in piles. Then, according to the manufacturing schedule of the rolling process which is the next process, the cranes 1A, 1B, 2A, 2B are placed on the delivery table Z again and transported to the rolling process. In general, in the yard, the steel is placed in the piled state as described above. This is to effectively utilize the limited yard area. On the other hand, when stacking steel products, it is necessary to load steel products from the top in the processing order of the next process in order to be easily supplied to the next process. In addition, it is necessary to prevent steel from being piled in an inverted pyramid shape that is unstable. In this way, dividing steel materials into a plurality of optimum mountains (= out-going mountains: mountains that have become final mountains to be paid out to the next process) is called mountain division.

  Here, in order to reduce the fuel consumption rate of the heating furnace of the rolling process which is the next process, it is required to discharge (insert) steel materials of as high temperature as possible to the heating furnace. For this reason, recently, a heat retention facility has been installed in the yard, and steel materials are piled up and stored in the heat retention facility as described above. Even when heat retaining equipment is used in this manner, as in the case where steel materials are piled up directly in storage areas 501 to 504, in order to make effective use of heat retaining equipment, a disbursed mountain as high as possible in the heat retaining equipment. It is necessary to create In addition, it is necessary to load steel materials from the top in the processing order of the next process and not to load steel materials in an inverted pyramid shape.

  As described above, when drafting a sorting plan in which a plurality of steel products having different sizes and processing orders in the next process are divided into a plurality of piles and drafting is performed, all sorts of piles that can be generated by steels to be drafted Among the candidates, we will solve an optimization problem that minimizes the number of piles and piled loads (handling load of steel products by transport equipment such as cranes). Such problems are large scale problems.

  Therefore, in the patent document 1, all feasible mountains that are subsets that satisfy the stacking constraints are listed for the entire set having steel materials as a plan drafting target as elements, and the number of peaks and the dumping load are minimized. There is disclosed a method of performing an optimal sorting plan by finding an optimal combination of feasible mountains as a set partitioning problem under an objective function.

  Further, in Patent Document 2, there is a method of formulating as a many-to-one assignment problem in which a plurality of transfer lots (groups of steel materials that can be transferred by the transfer device at one time) are allocated to appropriate mountains (optimum mountains = payout mountains). It is disclosed.

Unexamined-Japanese-Patent No. 2007-137612 JP, 2011-105483, A

M. GROTSCHEL, Y. WAKABAYASHI, "A CUTTING PLANE ALGORITHM FOR A CLUDTERING PROBLEM", Mathematical Programming, 45 (1989), p. 59-96

However, the methods described in Patent Documents 1 and 2 have the following problems.
First, in the solution method to which the set division problem shown in Patent Document 1 is applied, the same pile is required because the stacking order requested from the condition of the size (width and length) of an arbitrary steel material pair and the condition of the dispensing order are different. If the number of steel pairs that can not be reduced is relatively small, the number of feasible mountains increases. If this number exceeds several millions, it takes time for both the enumeration of feasible mountains and the calculation of optimum mountains, and the calculation is not completed within the required time (for example, about 3 to 5 minutes) It will be impossible to create a plan. In the case of the sorting problem, if the number of feasible mountains exceeds tens of millions, it becomes difficult to obtain a feasible solution within a practical time (for example, about 10 minutes). In such a case, there may be a case where it can be solved within an acceptable time by the method of formulation as the many-to-one assignment problem shown in Patent Document 2. However, the method shown in Patent Document 2 also has the following problems.

  That is, in the method shown in Patent Document 2, when there are a large number of steel material pairs (reversed pairs) in which the order of arrival at the yard and the stacking order at the yard are reversed, calculation time is required, and calculation is performed within a practical time May not be able to complete.

  Thus, the conventional method may or may not be able to solve within a practical time, depending on the nature of the problem. Therefore, there is a need for a method that can stably solve any problem. Moreover, when the number of feasible mountains exceeds tens of millions, and the ratio division plan of steel material groups having a high ratio of reverse pair is made, it can not be solved within a practical time. Therefore, in the case of a large-scale problem where the number of feasible mountains exceeds 10 million, or when there are many reverse pairs, it is necessary to find a solution in a practical time.

  The present invention has been made in view of the problems as described above, and an object of the present invention is to make it possible to make a plan in a practical time regardless of the nature of the problem to be solved.

The sorting plan drafting apparatus of the present invention piles up a plurality of steel materials carried in to the yard where steel materials are arranged as a storage space between processes in the steel process in the yard such that steel materials having a faster delivery order to the next process are on top A planing apparatus for dividing steel into a plan for preparing a distribution plan for making a plurality of payout piles to be paid out to the next process, wherein the item for evaluating the total number of the piles for delivery and the same delivery pile Objective function setting means for setting an objective function including a term for evaluating the number of reverse pairs in a reverse relationship in which the steel material arriving at the yard at the earlier arrival order is stacked above the later steel material at the yard And Constraint equation setting means for setting a constraint equation representing a constraint when stacking the steel materials, and mathematical programming such that the value of the objective function is maximized or minimized within a range satisfying the constraint by the constraint equation. To Optimal solution deriving means for performing calculation to divide the steel material into the plurality of disbursed peaks by performing the optimization calculation, and the constraint equation is such that the vertex corresponds to the steel material and the branch Undirected graph showing that the two steel members corresponding to the two vertices mutually connected by the two are the two steel members stacked on the same dump pile, a plurality of cliques where the vertices do not overlap each other The objective function setting means includes a term for evaluating the total number of the clique as a term for evaluating the total number of the payout peaks, and a term for evaluating the number of the inverted pairs. Setting the objective function including a term for evaluating the total number of the branches connecting the two vertices corresponding to the two steel members in which the reversal relationship holds, the optimum solution deriving unit may perform the mathematical programming By law During reduction calculation, the total number of the clique, characterized that you evaluate the total number of branches interconnecting two of said vertices corresponding to two of said steel relation of the reverse rotation is established.

According to the sorting plan creation method of the present invention, a plurality of steel materials carried in to the yard where steel materials are arranged as storage spaces between processes in the steel process are stacked in the yard such that steel materials having an earlier delivery order to the next process are on top Method for preparing a classification plan for steel products for drafting a classification plan for making a plurality of payout mountains for payout to the next process, the item for evaluating the total number of the payout mountains and the same payout mountain An objective function setting step of setting an objective function including a term for evaluating the number of reverse pairs in a reverse relationship in which the steel material arriving at the yard at the earlier arrival order is stacked above the later steel material at the yard A constraint equation setting step of setting a constraint equation indicating a constraint when stacking the steel materials, and mathematical programming so as to maximize or minimize the value of the objective function within a range satisfying the constraint by the constraint equation. To Optimization calculation to calculate an optimal solution for dividing the steel material into the plurality of disbursed peaks, and the constraint equation corresponds to the vertex corresponding to the steel material and the branch Undirected graph showing that the two steel members corresponding to the two vertices mutually connected by the two are the two steel members stacked on the same dump pile, a plurality of cliques where the vertices do not overlap each other The objective function setting step includes a term for evaluating the total number of the clique as a term for evaluating the total number of the payout peaks, and a term for evaluating the number of the inverted pair. The objective function is set including a term for evaluating the total number of the branches connecting the two vertices corresponding to the two steel members in which the reversal relationship holds, and the optimal solution deriving step includes the mathematical programming By law During reduction calculation, the total number of the clique, characterized that you evaluate the total number of branches interconnecting two of said vertices corresponding to two of said steel relation of the reverse rotation is established.

  A program according to the present invention is characterized in that a computer is caused to function as each means of the above-described steel product sorting planning device.

  According to the present invention, regardless of the nature of the problem to be solved, it is possible to make a plan in a practical time.

It is a figure which shows an example of an undirected graph. It is a figure which shows an example of a functional structure of the classification planning apparatus of steel materials. It is a flow chart explaining an example of operation of a classification program planning device of steel materials. It is a figure which shows the preparation result of a division plan in a tabular form. It is a figure which shows an example of the layout of a yard.

<Overview of the clique split problem>
As described below, embodiments of the present invention apply the Clique Partitioning Problem to the sorting problem. Although the clique division problem itself is a known technique, in order to clarify differences from the method of the embodiment of the present invention when applying the clique division problem to the classification problem, the embodiment of the present invention will be described before describing it. The outline of the solution method of the general clique division problem is explained.

FIG. 1 is a diagram illustrating an example of an undirected graph.
A clique is a subgraph (complete subgraph) which is a complete graph in an undirected graph G = (V, E) composed of a vertex set V and a branch set E. A complete graph is a graph in which there is a branch between any two vertices belonging to the subset V ′ among the graphs that become the subset V ′ (⊆V) of the vertex set V. A subgraph is a graph consisting of some vertices and some branches of the original graph (however, if there is only one vertex, no branches are included). In the example shown in FIG. 1, a subset of the following vertices is a clique (one {} indicates one clique, and a number in {} indicates a number added beside the vertex shown in FIG. 1 ).
[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 4, 3], [1, 4, 5], [2, 3, 4], [1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [3, 4], [3, 6], [4 , 5], [5, 6], [1], [2], [3], [4], [5], [6]

  The clique partitioning problem is a problem of partitioning a given undirected graph G = (V, E) into cliques (complete subgraphs) so that there is no overlap of vertices, and is used in modeling clustering. Optimization problems on the graph. The standard formulation for the clique partition problem can be formulated as the 0-1 integer programming problem shown in Non-Patent Document 1.

As shown in Non-Patent Document 1, in general, in a completely undirected graph G = (V, E), a subset V ′ of a vertex set V (= {V ₁ , V ₂ ,..., V _p } The branch set A is called a clique division of the undirected graph G when the branch set A⊆E of the) satisfies the following equation (1). That is, the division into a plurality of cliques whose vertices do not overlap with each other for a certain undirected graph is called clique division. Note that {i, j} represents that it is a branch between vertices i and j.

In general, the clique division problem is a problem in which a clique division in which the sum of weights becomes maximum is given when a branch weight r: E → R (real number) regardless of positive or negative is given.
As shown in Non-Patent Document 1, let the vertex set V be V = {1, 2,..., N}, and for the branch set E, a 0-1 variable vector x → = (x _ij ) ₁ ≦ _{i Let j j n n} correspond (→ indicates that x is a vector, and so on). Each component x _ij takes 1 if {i, j} εA and 0 if {i, j} εA. For example, when the undirected graph shown in FIG. 1 is divided into two cliques, a clique consisting of vertices 1, 2, 3 and 4 and a clique consisting of vertices 5 and 6, as an example, 0-1 The variable vector x → is as follows.
x → = (x ₁₂ , x ₁₃ , x ₁₄ , x ₁₅ , x ₁₆ , x ₂₃ , x ₂₄ , x ₂₅ , x ₂₆ , x ₃₄ , x ₃₅ , x ₃₆ , x ₄₅ , x ₄₆ , x ₅₆ ) = (1,1,1,0,0,1,1,0,0,1,0,0,0,0,1)
"A branch set A is a clique division", and for any i, j, k ∈ V, if {i, j} 且 つ A and {j, k} {A, then {i, k} ∈ A In general, the clique division problem can be formulated as the following equations (2) to (6), paying attention to the equivalence with "being".

Where r _ij is the weight of branch {i, j}. Also, the inequality constraints of the equations (3) to (5) are called transitive constraints. In this formulation, the number of variables is n (n-1) / 2 and the number of transitivity constraints is n (n-1) (n-2) / 2 (n is as described above) Is the number of vertices in undirected graphs). The transitivity constraint is a constraint that if the value of the component x _{ij on} two sides of any three vertices (triangles) is 1, the value of the component on the other side must also be 1 .

As described above, in the 0-1 integer programming problem of the general clique division problem, 0-1 which maximizes the equation (2) (that is, the sum of the weights r _ij constituting the clique) within the range satisfying the transitivity constraint Each component x _ij of the variable vector x → is to be obtained. At this time, for example, by multiplying the equation (2) by (-1), the problem of minimizing the equation (2) can be set.

  As described above, the original clique division problem is a problem of finding a clique such that the sum of weights of selected branches is maximized (or minimized). On the other hand, in the classification problem, it is necessary to find a solution in which the tradeoff between minimizing the total number of peaks and minimizing the number of rounds is taken. The rounding number can be formulated in a natural manner by branch weights as described later. On the other hand, the total number of peaks has not been formulated to estimate the number of cliques, not only for the original clique division problem, but also for various problems that have been modified. The optimization problem around cliques is the maximum clique problem, which is "a problem that finds a perfect subgraph of the maximum order (number of vertices) given an undirected graph" and does not connect to the division problem. With respect to such problems, the present inventors have found that the 0-1 integer programming problem of the clique division problem can be applied to the sorting problem as in the embodiment of the present invention described below.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
First Embodiment
First, the first embodiment will be described.
<A structure and process of the steel product division plan planning apparatus 200>
FIG. 2: is a figure which shows an example of a functional structure of the classification division plan planning apparatus 200 of steel materials. FIG. 3 is a flow chart for explaining an example of the operation of the steel product sorting plan drafting apparatus 200. The hardware of the steel sorting planning apparatus 200 is, for example, an information processing apparatus having a CPU, a ROM, a RAM, an HDD, and various interfaces, a programmable logic controller (PLC), an application specific integrated circuit (ASIC), etc. It can be realized by using dedicated hardware. In the following description, the steel product separation plan planning device 200 will be abbreviated as the distribution plan generation device 200 as needed.

[Input unit 201: target slab group list input step S301]
The input unit 201 acquires a sorting target slab group list which is a list of slabs (steel materials) which are targets of planning of the sorting plan. The sorting target slab group list may be acquired at a constant cycle, or may be acquired irregularly triggered by the occurrence of a specific event or the like.
The input unit 201 is realized, for example, by the CPU storing data of the classification target slab group list received from a steel management system computer (not shown) via the communication interface in the HDD or RAM. The steel management system computer is a high-level computer having a database on steel in general arriving at a slab.

  In this embodiment, the case where a plurality of slabs arrive at the same time in a yard in a unit of a plurality of slabs which is the smallest unit which is not divided when transported by a transport device such as a crane is an example I will list and explain. However, a plurality of slabs may not arrive in the yard at the same time. In that case, piles of the plurality of slabs are started after the slab arriving at the yard last among the plurality of slabs arrives at the yard. In the following description, such a plurality of slabs will be referred to as "slab groups" as needed.

In the present embodiment, the classification target slab group list includes, for each slab group, an identification number, an estimated arrival time, a dispensing order, a number of steel members, a maximum width, a minimum width, a maximum length, and a minimum length. Information is included.
The identification number is a number that uniquely identifies each slab group.
The estimated arrival time is the estimated arrival time for each slab group in the yard. In the present embodiment, a sorting plan is created in the case where no slab has been placed in the yard. Therefore, estimated arrival times are given for all slab groups for which the sorting plan is to be made.

The order of delivery is the order of transport to the rolling process of each slab group.
The number of steel members is the number of slabs constituting each slab group.
The maximum width and the minimum width are respectively the maximum width and the minimum width of the slabs constituting each slab group.
The maximum length and the minimum length are respectively the maximum length and the minimum length of the slabs constituting each slab group.

  Here, although the case of acquiring the list for each slab group has been described as an example, the list for each slab may be acquired. In this case, for each slab, the identification number of the slab group to which the slab belongs is included in the list. Also, instead of the maximum width, the minimum width, the maximum width, and the minimum width, for each slab, the width and length of the slab are included in the list.

[Objective function setting unit 202: objective function setting step S302, constraint expression setting unit 203: constraint expression setting step S303]
The objective function setting unit 202 sets an objective variable based on the classification target slab group list input by the input unit 201. Further, the constraint expression setting unit 203 sets a constraint expression based on the classification target slab group list input by the input unit 201. The objective function and the constraint equation formulated in this embodiment will be described below.

[[Definition of undirected graph G and weight r]]
G = (N, E): A set of slab groups N (N = {1, 2,... N}) is a completely undirected graph whose vertices are individual slab groups (G = (N, E)) I assume. One of the vertices shown in FIG. 1 corresponds to one slab group. E is a set of branches e.
In FIG. 1, it is shown that two slab groups {i, j} corresponding to apexes at both ends of the branch can be piled up on the same payout pile, and 2 corresponding to two apexes not interconnected by the branch One slab group indicates that piles can not be piled up on the same pile.

  r: E → {0, 1}: Arrival order to yard when slab group i and slab group j are stacked on the same delivery pile for any two slab groups {i, j} E And the product order in the same payout pile are "1" if they are reversed, otherwise 0-1 variable r ({i, j}) to indicate that it is "0 (zero)" {branch { Let i, j} be a weight. For the two slab groups corresponding to the two vertices shown in FIG. 1, if the product order in the same payout pile as the arrival order to the yard is reversed, the branch weight between the two vertices is “1”. If not inverted, the weight of the branch between the two vertices is "0 (zero)". Here, if the arrival order to the yard and the product order at the same delivery mountain are reversed, the slab group with the higher order will go to the yard rather than the slab group with the lower order. The order of arrival is early. In the following description, a set of two slab groups is referred to as a slab group pair as needed.

[[Decision variable]]
For each branch eεE of the completely undirected graph G, 0-1 variable x (e) is introduced. For simplicity, for the branch e = {i, j} ∈E, the variable x (e) is denoted as x ([i, j]). This variable x ([i, j]) is expressed by the following equation (7).

The equation (7) corresponds to the equation (6) described above. Here, in the 0-1 variable vector x → ∈ {0, 1} ^E , the branch set for the (element) variable x ([i, j]) whose value is “1” is expressed by the following equation (8) It shall be written as

  As described above, in the present embodiment, the variable x ([i, j]) (= x (e)) becomes the decision variable, and the other variables are the variables x ([i, j]) (= x (e) Become a dependent variable of)).

[[Constraint expression]]
The main constraints in sorting planning are the following transitivity constraints, same mountain prohibition constraints, and height constraints. Here, the contents of the transitivity constraint, the same mountain prohibition constraint, and the height constraint will be described. The constraint equation required to convert the optimization problem for minimizing the value of the objective function from the nonlinear programming problem to the mixed integer programming problem will be separately described.

(A) Transitivity constraint (triangular inequality)
The transitivity constraint is, as described above, a branch set in which a branch connecting the first vertex and the second vertex in the undirected graph, and a branch connecting the second vertex and the third vertex constitute the same clique. , And the branch connecting the first vertex and the third vertex must also belong to the branch set constituting the clique.

If an 0-1 variable vector x → ∈ {0, 1} ^E corresponds to a pile, then (incomplete) undirected graph G (V, E (x)) is such that each connected component is a clique (complete graph) It must be a subgraph). Therefore, in order for the 0-1 variable vector x → ∈ {0, 1} ^E to correspond to the accumulation, the 0-1 variable vector x → only needs to satisfy the transitivity constraint. Therefore, the necessary and sufficient condition for each connected component of the undirected graph G (V, E (x)) to be clique is to satisfy the following equations (9) to (11).

The equations (9) to (11) correspond to the equations (3) to (5) described above, respectively. In the following description, a branch set satisfying the transitivity constraint expressions of the equations (9) to (11) is denoted as Ω.
(B) The same mountain prohibition constraint The same mountain prohibition constraint specifies a slab group that can not be piled up on the same delivery mountain. In this embodiment, it is assumed that slab groups that do not satisfy the following width and length conditions should not be piled up on the same delivery pile.
(B-1) Width condition Unconditionally, if the maximum width of a certain slab group is narrower than the minimum width of the slab group located under the certain slab group, the certain slab group is considered below the concerned It can be placed on top of a located slab group. When the maximum width of a certain slab group is wider than the minimum width of the slab group located below the certain slab group, the difference between the two widths is a reference value (for example, 300 [mm]) determined by the operation constraints. If it is less than that, the certain slab group can be placed on the underlying slab group, but it can not be placed beyond it.

  That is, when the width condition is satisfied, the maximum width of a certain slab group is narrower than the minimum width of the slab group located below the certain slab group, and the maximum width of a certain slab group is the relevant one. And the difference between the widths of the two is less than a reference value (e.g., 300 [mm]).

(B-2) Length condition If the maximum length of a certain slab group is shorter than the minimum length of the slab group located under the certain slab group, the certain slab group is unconditionally It can be placed on a slab group located in When the maximum length of a certain slab group is longer than the minimum length of the slab group located below the certain slab group, the difference between the two lengths is determined by the reference value (for example, 3000 mm) determined by the operation constraints. If it is less than that, the certain slab group can be placed on the slab group located immediately below it, but it can not be placed beyond it.

  That is, when the length condition is satisfied, the maximum length of a certain slab group is shorter than the minimum length of a slab group located below the certain slab group, and the maximum length of a certain slab group is the relevant one. In this case, the length is longer than the minimum length of a slab group located below a certain slab group, and the difference between the lengths is less than a reference value (e.g., 3000 [mm]).

  In the present embodiment, as shown in the following equation (13), a slab group which does not satisfy at least one of the above width condition and length condition (that is, it should not be piled up on the same delivery pile) Introduce a set F of pairs (branches).

In equation (13), i and j indicate slab groups that do not satisfy at least one of the width condition and the length condition.
Then, for a set F (⊆ E) of slab group pairs (branches) that can not be piled up on the same mountain, the following equation (14) is expressed as the same mountain prohibition constraint equation.

(C) Mountain height constraint The mountain height constraint is a constraint that the height of one delivery mountain is equal to or less than a reference value.
In the present embodiment, it is assumed that all slabs have the same thickness. Therefore, the condition that the number of slabs stacked on one payout pile is equal to or less than the reference number (for example, 12 [sheets]) is taken as the height constraint. Here, the upper limit of the number of slabs stacked in one payout pile is denoted as h (h ∈ Z ₊ (natural number)).

  Then, for vertex (slab group) i) N, the following equation (16) is expressed as a peak height constraint equation.

The first term (w (i)) on the left side of the equation (16) is the number of slabs (w (i): N → Z ₊ (natural number)) of the slab group i (∀i∈N). w (i) is, for example, a natural number of 1 or more and 6 or less (1 ≦ w (i) ≦ 6).

Further, the second term (a term of 左) of the left side of the equation (16) represents the total number of slabs of the slab group j other than the slab group i of the mountain (creek mountain) including the slab group i (∈N).
In equation (16), Σ of the second term of the left side of equation (16) is the sum of vertices (slab groups) j other than vertices (slab groups) i in the vertex set (slab group set) V (This is the same in the following formulas)

[[Indicator]]
Next, the evaluation index in the objective function will be described.
In this embodiment, a weighted linear sum of the total number of peaks (peak height) and the number of rounds is used as an objective function. The weighted linear sum refers to the sum of the number of peaks (peak height) and the value of the number of peaks obtained by multiplying the weighting factor for the total number of peaks (peak height) and the weighting factor for the peak number. . The weighting factor for the total number of peaks (peak height) is a coefficient representing the balance between the evaluation for the total number of peaks (peak height) and the evaluation for the peak number. The weighting factor for the heading number is a factor that represents the balance between the evaluation for the heading number and the evaluation for the total number of peaks (peak height).

  Using the total number of mountains (mountain height) as an evaluation index is that mountain division in the yard has limited capacity for heat insulation equipment, limited storage space for slabs, and places slabs directly in storage spaces In this case, it is required to raise the peak height as much as possible and reduce the total number of peaks as much as possible because the cooling of the uppermost and lowermost slabs is larger than that of the other slabs. It is.

  The reason for using the number of rounds as the evaluation index is as follows. First of all, when dividing the area, it is required that the number of the transfer work for stacking be as small as possible, in consideration of the problem of the work space and the ability of the transfer equipment such as the crane performing the work. In the case of division, it is ideal if the slabs can be stacked in the order of arrival at the yard. On the other hand, in order to eliminate the rolling at the time of dispensing and to perform the dispensing operation quickly, it is the basic principle in the dispensing pile that the ones with the earlier dispensing to the lower process be piled up. Therefore, in reality, the order of arrival at the yard may differ from the order of arrival at the delivery pile. That is, it may be necessary to load the slabs with the earlier arrival order to the yard on the same upper tier of the delivery pile than the later slabs. In that case, the slabs that arrived in the yard will be temporarily placed temporarily in the temporary storage until the slabs in the lower row reach the yard, and the slabs in the lower row will arrive in the yard and pile up After that, it is necessary to load the slabs for temporary storage on the slabs. Therefore, it is desirable to divide the work so as to minimize such work. The number of occurrences of such temporary placement is mathematically expressed as a reverse number. The number of reversals is the total number of slab group pairs in which a relation in which the order of arrival at the yard and the order of arrival at the same payout pile are reversed is established. Thus, the number of rounds is represented by a reverse number.

[[Formulation of total mountain number]]
As described above, the general clique division problem is a problem of maximizing or minimizing the sum of the weights r (e) of the branches e (= {i, j}). Therefore, the problem setting is not such that the evaluation on the total number of peaks (total number of cliques) to be considered most in the sorting problem can be considered. . Therefore, to apply the clique division problem to the categorization problem, the formulation of the total number of mountains becomes an issue.

  In order to solve such problems, the present inventors calculate the total number of cliques regardless of the number of vertexes constituting each clique, regardless of the configuration of cliques (in this case "1"). I thought it was necessary to find such an "amount". Then, as the “quantity” such that the number of vertices constituting such a clique is at least the same value at the same time, the value for each vertex is smaller as the number of vertices constituting the clique is larger I got the idea that it would be better to use such an amount. Under such an idea, in this embodiment, “1 / p” (p is the number of branches connected to one vertex in the clique + 1) is adopted as a weight to be defined for each vertex. The denominator p (the number of branches connected to one vertex in the clique + 1) represents the total number of vertices constituting the clique. Therefore, taking the sum of the values of all the vertices of the clique, 1 / p which is its reciprocal, gives 1 (= p (total number of vertices constituting the clique) x 1 / p (= the clique) Weight of each vertex)). Therefore, the sum of cliques, that is, the total number of peaks, can be obtained by summing the values at all the vertices.

The undirected graph shown in FIG. 1 is divided into two cliques, a clique consisting of vertices 1, 2, 3 and 4 and a clique consisting of vertices 5 and 6, as an example, and the above-mentioned method is used Thus, it is explained that the total number of creeks and the total number of mountains match.
First, in a clique consisting of vertices 1, 2, 3 and 4, the number of branches connected to vertex 1 is 3, so the weight for vertex 1 is 1/4 (= 1 / (3 + 1)). Similarly, in a clique consisting of vertices 1, 2, 3 and 4, since the number of branches connected to vertices 2, 3, and 4 is also 3, respectively, the weights for vertices 2, 3, and 4 are each 1/4 (= 1 / (3 + 1)).

Next, in the clique consisting of the vertices 5 and 6, since the number of branches connected to the vertices 5 and 6 is 1, respectively, the weight for the vertices 5 and 6 is 1/2 (= 1 / (1 + 1)).
Therefore, the total number of peaks, which is the sum of them, is 2 (= 1/4 + 1/4 + 1/4 + 1/4 + 1/2 + 1/2), which corresponds to the total number of cliques.

  Based on the above thinking, the total number of peaks (number of cliques) for an arbitrary 0-1 variable vector x → ∈ Ω is expressed by the following equation (17). Note that, as described above, Ω is a branch set satisfying the transitivity constraint, and the 0-1 variable vector x → is a vector having the variable x ([i, j]) as an element.

[[Formula of objective function]]
Assuming that the weighting factor for the total number of peaks (peak height) is k ₁ and the weighting factor for the number of inversions (= counting number) is k ₂ , as described above, the objective function is “k ₁ × total number of peaks + k ₂ × inversion It becomes number.
The inversion number of each payout peak for any x∈Ω is represented by _{∈ e} ∈E r (e) x (e). Further, the total number of peaks is expressed by equation (17). Therefore, the objective function is expressed by the following equation (18).

[[Convert nonlinear programming problems to mixed integer programming problems]]
The objective function of equation (18) is the sum of rational functions (nonlinear functions) having a polynomial in the denominator. Therefore, we considered linearizing the non-linear function to reduce the computational load.

Here, the rational function of the first term of the objective function of equation (18) is linearized by representing it as a linear piecewise function. Therefore, a new continuous variable α _i is introduced for each vertex (slab group) i, which represents the upper limit of the rational function of the first term of the objective function of equation (18). That is, the continuous variable α _i is defined as a variable to satisfy the following equation (19).

  Here, if the 0-1 variable vector x → having variable x ([i, j]) as an element is an acceptable solution of the problem of minimizing the value of the objective function of equation (18), (19) The value of the polynomial of the denominator on the left side of the equation is a value corresponding to the total number of vertices (slab groups) constituting the clique including the vertex (slab group) i. Therefore, the value of the polynomial of the denominator on the left side of equation (19) must be an integer of 1 or more and h or less.

  From the above, the inequality of the equation (19) may be established only when the value of the polynomial of the denominator on the left side of the equation (19) is an integer. That is, for simplicity, if the left side of the inequality in equation (19) is expressed as 1 / (1 + X), the left side is 1 / (only at integer points (X = 0, 1,..., H-1) It can be replaced by a piecewise linear convex function that matches the value of 1 + X).

  Specifically, X of the nonlinear function (1 / (1 + X)) takes only integer values of X = 0, 1,..., H-1. Therefore, first, it divides into the section of [0, 1], [1, 2], ..., [h'-1, h '], ..., [h-2, h-1]. Then, in each section, the non-linear function (1 / (1 + X)) is approximated with a linear function that matches the value of the non-linear function (1 / (1 + X)) only when X is an integer point. For example, in the [0, 1] section, the nonlinear function (1 / (1 + X)) is a straight line connecting (X, 1 / (1 + X)) = (0, 1) and (1, 1/2) It is approximated to (Y = (-1/2) X + 1). Also, in the [h′−1, h ′] section, the nonlinear function (1 / (1 + X)) is (X, 1 / (1 + X)) = (h′−1, 1 / h ′) and It is approximated to a straight line (Y = (2h'-X) / {h '(h' + 1)}) connecting h 'and 1 / (1 + h'). Here, although the expression “approximation” is used, as described above, the polynomial (= 1 + X) of the denominator on the left side of the equation (11) takes only integer values, and hence the feasible solution space (x (e) At ∈ {0, 1}), the values of the non-linear function (1 / (1 + X)) and the piecewise linear bump function will match exactly.

  From the above, the equation (19) can be expressed using h-1 inequalities shown in the following equation (20).

  By doing as described above, only the integer value of the value of the following equation (22) which is the sum of all the vertices (slab groups) i of the value of the following equation (21) which is a term of the non-linear function You can make it impossible. This feature can be used to formulate a nonlinear programming problem that minimizes the value of the objective function of equation (18) as a mixed integer programming problem.

[[Formula of objective function and constraint expression as mixed integer programming problem]]
Since the value of equation (22) can only be an integer, an integer variable z (z∈Z ₊ (natural number)) is defined. From the above, the equation (18) is converted into the following equations (23) to (27).

The reason why the integer variable z is used without using _{∈ i 用 い N} α _i as the objective function in the equation (23) is that the branch and bound method may end early. Specifically, as described above, α _i is a continuous variable, but if the inequality of inequality (24) is satisfied, the sum of all vertices (slab groups) i of continuous variable α _i A certain _{∈ i ∈ N} α _i (= z) corresponds to the total number of cliques (the total number of peaks), so it is an integer. Therefore, when the integer variable z is used, it is implicitly requested that the equal sign be established in the equation (24). That is, if the 0-1 variable vector x → (which has variables x (e) (x ([i, j])) as the element) is the optimal solution, then _{∈ i ∈ N} α _i is an integer. If Σ _{i ∈ N} α _i is not an integer, the 0-1 variable vector x → is not an optimal value. Therefore, using the integer variable z, it can be expected to limit the search range of the 0-1 variable vector x →.

[[Objective function and constraint expression]]
From the above, in this embodiment, the variable x (e) (x) minimizes the value of the objective function of the equation (23) within the range satisfying the constraints of the following equations (24) to (33). We will derive ([i, j]).

The equations (28) to (30) respectively correspond to the transitivity constraint equation shown in the equations (9) to (11), and e, f and g in the equations (28) to (30) are respectively , {I, j}, {j, k}, {i, k}. It is the same mountain prohibition constraint equation shown in the equations (31) and (14). Equation (33) is the hill height constraint equation shown in equation (16). Γ ₃ indicates an undirected graph (G = (N, E)).

Therefore, the objective function setting unit 202 sets the objective function of equation (23). Specifically, the objective function setting unit 202 sets, for example, a weighting factor k ₁ for the total number of peaks (peak height) and a weighting factor k ₂ for the number of inversions. The weighting factors k ₁ and k ₂ may be acquired by, for example, the input unit 201 from the steel material management system computer, or may be acquired by an operation by the operator on the user interface of the classification planning device 200. Further, the objective function setting unit 202 sets possible values as e (= i, j) of the variables x (e) (x ([i, j])) based on the classification target slab group list, and A possible value is set as the weight r (e).

  Further, the constraint expression setting unit 203 sets constraint expressions of Equations (24) to (33). Specifically, the constraint expression setting unit 203 sets, for example, a set of slab group pairs (branches) that should not be piled up on the same mountain based on the target slab group list for classification and the reference value in the width condition and the length condition. Derive F; The reference value in the width condition and the length condition may be acquired by, for example, the input unit 201 from the steel material management system computer, or may be acquired by an operation by the operator on the user interface of the classification planning device 200. In addition, in the equations (28) to (33), the constraint equation setting unit 203 sets e (= i, j) of the variable x (e) (= x ([i, j])), variable x (f) Possible values are set as f (= j, k) of (= x (j, k)) and g (= i, k) of variable x (g) (= x (i, k)). Further, the constraint expression setting unit 203 sets the upper limit h of the number of slabs to be stacked on one payout pile in the equations (24) and (33). For example, the upper limit h of the number of slabs to be stacked on one payout pile may be acquired by the input unit 201 from the steel material management system computer, or by the operation by the operator on the user interface of the classification planning device 200 Good.

[Optimum Solution Deriving Unit 204: Optimal Solution Deriving Step S304]
The optimum solution deriving unit 204 performs the optimization calculation by the mixed integer programming to obtain the value of the objective function of the equation (23) within the range satisfying the constraints of the constraints of the equations (24) to (33). A variable x (e) (x ([i, j]) to be minimized (ie, an optimal solution of the variable x (e) (x ([i, j])) is derived.

In this embodiment, optimization calculation is performed under the following assumptions.
(A) When delivering slabs to the next process, the order of delivery to the next process of the slab group having a relatively higher order is the same so that the slab groups above the dump mountain can be delivered sequentially. Each slab is piled up earlier than the delivery order to the next process of the slab group whose order is relatively lower.

(B) In the case where there is freedom in the order of delivery of the slab group to the next process, the earlier the arrival order to the yard is the slab group, the lower the pile of delivery. For example, with respect to slab groups of the same lot number, there is no restriction on the order of delivery of slab groups to the next process. The lot represents a process of the next process (for example, a hot rolling process), and the lot number represents the order of processes in the next process of the process.
(C) The order of arrival at the yard shall be unique, and there shall be no overlap between different slab groups.
With such an assumption, the stacking order is determined uniquely for any subset N′εN of the slab group.
In addition, since the optimization calculation by mixed integer programming is implement | achieved by using a well-known technique, the detailed description is abbreviate | omitted here.

[Output Unit 205: Output Step S305]
The output unit 205 outputs information based on the optimal solution of the variable x (e) (x ([i, j])) derived by the optimal solution derivation unit 204. For example, the output unit 205 can output the optimal solution of the variable x (e) (x ([i, j])) derived by the optimal solution deriving unit 204. In this case, from the optimum solution of the variable x (e) (x ([i, j])], the operator determines the payout group to which the slab group belongs and the corresponding slab group for each of the slab groups included in the classification target slab group list. It is possible to create information that includes the shipping order in the delivery pile. Further, the output unit 205 can derive such information from the optimal solution of the variable x (e) (x ([i, j])) derived by the optimal solution derivation unit 204 and can output the information. In addition, the output unit 205 determines which slab group at which timing and which slab group at which timing on which timing based on the sorting target slab group list and the optimal solution of the variable x (e) (x ([i, j])). It is possible to specify whether or not to carry out the operation, and to issue an operation command to the conveyance device based on the specified contents. In this case, the optimal solution of the variable x (e) (x ([i, j])) may or may not be output.

<Summary>
As described above, in the present embodiment, the total number of piles is reduced, and the number of piles (slab groups with the earlier arrival order to the yard in the same delivery mountain are stacked above the later slab groups). The optimization problem that minimizes the value of the objective function with the goal of reducing the number of roundings required for the solution is solved by performing optimization calculations using mathematical programming. At this time, vertices are made to correspond to slab groups, and two slab groups corresponding to two vertices mutually connected by branches are represented as candidates for two slab groups stacked on the same payout pile. Then, the total number of cliques is represented as the total number of peaks, and the total number (reversal number) of branches between two vertices corresponding to two slab groups in which the inverse relationship is established is represented as the total number.

  Therefore, the classification problem can be applied to the clique division problem. By doing this, when there are many slab groups that the laying load becomes large when piled up on the same delivery pile among the slab groups for which the sorting plan is to be drafted, or if the slab groups for which the sorting plan is to be drafted Even if the number is large, it is possible to create a yarding plan within a practical time. That is, regardless of the nature of the problem to be solved, it is possible to create a yarding plan within a practical time.

For example, in the present embodiment, it is not necessary to enumerate executable peaks as in the set division problem and prepare variables for the number. Since the number of subsets in the set division problem shown in Patent Document 1 is 2 ⁿ , ^where n is the number of elements of the set, it is an exponential time algorithm. On the other hand, in the present embodiment, the problem can be formulated by variables of the order of n ² polynomials. Thus, it is possible to construct an algorithm that is not influenced by the number of feasible peaks (subsets). Further, in the method of Patent Document 2, it is possible to formulate the evaluation of the number of rounds which could not be formulated, that is, the evaluation of the reverse pair in a natural manner. This allows real-time problems to be completed in real time.

  Further, in the present embodiment, the sum of all vertices of the inverse number of branch number + 1 connected to one vertex (slab group) is represented as the total number of peaks (see equations (17) and (18)). . Therefore, the total number of peaks can be formulated in the clique division problem.

Further, in the present embodiment, for the value of the nonlinear function represented by the inverse number of the branch number + 1 connected to one vertex (slab group) in the clique (one mountain), the branch connected to one vertex in the clique Express the sum (Σ _{i ∈ N} α _i ) for all vertices (slab groups) of continuous variables α _i that define the upper limit of the piecewise linear function that matches only with the value of the number for each slab group as the total number of peaks (See Equations (20), (23), (25), etc.). Thus, non-linear programming problems can be replaced by mixed integer programming problems. Therefore, optimization calculation by mixed integer programming can be performed, and the time for optimization calculation can be further shortened.

Further, in the present embodiment, the sum of all the vertices (slab groups) of the continuous variable α _i is represented by the integer variable z, and the integer variable z is represented by the total number of peaks (equations (23), (25), etc. See). Therefore, the search range of the optimal solution can be limited, and the time for optimization calculation can be further shortened.

<Modification>
[Modification 1]
In the present embodiment, the objective function aiming to minimize the weighted linear sum of the total number of peaks (peak height) and the number of vertical turns (number of inversions) has been described as an example. However, the objective function is not limited to a weighted linear sum of the total number of peaks (height) and the number of inversions (number of inversions). For example, the sum of all the delivered mountains, the total number of mountains (mountain height), and the number of piles (reversed) of the time until one finished delivery mountain is completed (the working time of the transport equipment for creating one mountain). A weighted linear sum with a number) may be used as an objective function. In addition, the time taken to pay out the slab to be paid out last from the slab to be paid out first to the next process in one dump mountain (from the payout time of the first slab in one dump mountain to the payout time of the last slab A weighted linear sum of the sum of all the delivery peaks, the total number of peaks (peak height), and the number of turns (reverse number) of time) may be used as the objective function. With regard to the former, if the time until one delivery pile is completed is short, for example, it is possible to shorten the time for keeping the heat retention facility for receiving the slab, and it is possible to suppress the decrease in the temperature of the slab. Regarding the latter, if the time taken to pay out the slab to be paid out last from the slab for the first step in one dumping mountain is short, the time during which the heat retaining equipment is open for the withdrawal from the heat retaining equipment It is possible to reduce the temperature of the slab and to reduce the temperature of the slab.

[Modification 2]
In the present embodiment, the optimization problem for minimizing the value of the objective function has been described using mathematical programming as an example. However, for example, by multiplying each term of equation (23) by (-1), it may be an optimization problem that maximizes the value of the objective function.

[Modification 3]
In the present embodiment, the case where the thickness of all the slabs is the same has been described as an example. However, the thickness of the slabs may not be the same. In this case, w (i) may be the sum of the thicknesses of the slabs included in the slab group i.

[Modification 4]
In the present embodiment, the case where the nonlinear function is transformed into a linear piecewise convex function and the nonlinear programming problem is formulated into a mixed integer programming problem has been described as an example. As described above, this is preferable because the time for optimization calculation can be shortened. However, optimization calculation by non-linear programming may be performed.

[Modification 5]
In the present embodiment, the sum ( _{総 和 i ∈ N} α _i ) of all continuous variables α _i for all vertices (slab groups) is taken as the integer variable z, and the integer variable z is expressed as the total number of peaks as an example. Explained. As described above, this is preferable because the search range of the optimum solution can be narrowed. However, instead of using the integer variable z, the total (Σ _{i ∈N} α _i ) of all the continuous variables α _i for all the vertices (slab groups) may be formulated as it is as the total number of peaks.

[Modification 6]
In the present embodiment, the case of creating the sorting plan in units of slab groups has been described as an example. However, the sorting plan may be prepared in units of one slab. In that case, the “slab group” in the above description is read as “slab”, and the number of steel members is one (therefore, for example, the number of slabs in slab group i, j w (i), w (j)) The value of x becomes “1)), and the maximum width and the minimum width become the same value in the width of the slab. Likewise, the maximum length and the minimum length have the same value for the length of the slab.

Second Embodiment
Next, a second embodiment will be described. In the first embodiment, the equation (17) is described by taking, as an example, the case where the sum of all vertices of the inverse number of branch number + 1 connected to one vertex (slab group) is represented as the total number of peaks. See equation (18)). On the other hand, in the present embodiment, the number of slabs included in one vertex (slab group) is divided by the total number of slabs included in all the vertices (slab groups) forming a clique (mountain) including the vertex. The sum of all the values for all vertices is expressed as the total number of peaks. As described above, the present embodiment and the first embodiment mainly differ in the expression of the total number of peaks. Therefore, in the description of the present embodiment, the same parts as those in the first embodiment are denoted by the same reference numerals as those in FIGS. 1 to 3, and the detailed description will be omitted.

[[Formulation of total mountain number]]
The undirected graph shown in FIG. 1 is divided into two cliques of a clique consisting of vertices 1, 2, 3 and 4 and a clique consisting of vertices 5 and 6 as an example, as in this embodiment. It is explained that the total number of cliques and the total number of peaks match even if the total number of mountains is expressed in Here, it is assumed that the number of slabs of the slab group corresponding to the vertices 1, 2, 3, 4, 5, and 6 is 3, 2, 1, 4, 2, 2, 2, respectively.

  The number of slabs of vertex 1 (slab group) (= 3), the total number of slabs of all vertices 1, 2, 3 and 4 (slab groups) constituting the clique including vertex 1 (= 10 (= 3 + 2 + 4 + 4)) The value divided by is 3/10. Similarly, the number of slabs of vertices 2, 3, and 4 (= 2, 1, 4) is the total number of slabs of all vertices 1, 2, 3, 4 (slab groups) constituting a clique including vertex 1 (slab groups) The values divided by 10) are 2/10, 1/10, and 4/10, respectively. Furthermore, the number of slabs (= 2, 2) for vertices 5 and 6 (slab groups) is the total number of slabs for all vertices 5 and 6 (slab groups) that make up the clique including vertex 1 (= 4 (2 + 2) The values divided by) are 1/2 and 1/2, respectively. The total number of peaks, which is the sum of these, is 2 (3/10 + 2 + 10 + 1/10 + 4/10 + 1/2 + 1/2), which corresponds to the total number of cliques.

  Based on the above thinking, the total number of peaks (number of cliques) for an arbitrary 0-1 variable vector x → ∈ Ω is expressed by the following equation (34).

The equation (34) is an alternative to the equation (17) described in the first embodiment.
[[Formula of objective function]]
As described in the first embodiment, assuming that the weighting factor for the total number of peaks (peak height) is k ₁ and the weighting factor k ₂ for the number of inversions, the objective function is “k ₁ × total number of peaks as described above. It becomes + k ₂ × reverse number.
The inversion number of each mountain for any x _∈ Ω is represented by _∈ e _{∈ E} r (e) x (e). Further, the total number of mountains is expressed by equation (34). Therefore, the objective function is expressed by the following equation (35).

The equation (35) is an equation to replace the equation (18) described in the first embodiment.
[[Convert nonlinear programming problems to mixed integer programming problems]]
The objective function of the equation (35) is, like the equation (18), the sum of rational functions (nonlinear functions) having a polynomial in the denominator. Therefore, in the present embodiment, as in the first embodiment, the non-linear function is linearized.

That is, the rational function of the first term of the objective function of the equation (35) is linearized by expressing it by a linear piecewise function. Therefore, a new continuous variable β _i is introduced for each vertex (slab group) i, which represents the upper limit of the rational function of the first term of the objective function of the equation (35). That is, the continuous variable β _i is defined as a variable to satisfy the following equation (36).

The equation (36) is an alternative to the equation (19) described in the first embodiment.
In the same way as described in the first embodiment, the 0-1 variable vector x → having the variable x ([i, j]) as the element minimizes the value of the objective function of the equation (35). If it is an allowable solution, the value of the polynomial of the denominator on the left side of equation (36) is a value corresponding to the total number of vertices (slab groups) that constitute the clique to which the vertex (slab group) i belongs. Therefore, the value of the polynomial of the denominator on the left side of the equation (36) must be an integer of 1 or more and h or less. Therefore, the inequality of the equation (36) may be established only when the value of the polynomial of the denominator on the left side of the equation (36) is an integer.

  From the above, if the left side of the inequality in equation (36) is regarded as w (i) / (w (i) + X) for simplicity, the left side is an integer point (X = 0, 1,... Only h-1) can be replaced by a piecewise linear convex function that matches the value of w (i) / (w (i) + X).

  For example, in the [h′−1, h ′] section, the nonlinear function (w (i) / (w (i) + X)) is (h′−1, w (i) / (w (i)) It is represented by the equation of the following equation (37) which connects + h′−1) and (h ′, w (i) / (w (i) + h ′)).

  From the above, the equation (36) can be expressed by using h-1 inequalities shown in the following equation (38).

The equation (38) is an alternative equation to the equation (20) described in the first embodiment.
By doing as above, only the integer value of the value of the following equation (40) which is the sum of all the values of the following equation (39) which is the term of the nonlinear function at all vertices (slab groups) i You can make it impossible. This feature can be used to formulate a nonlinear programming problem that minimizes the value of the objective function of equation (35) as a mixed integer programming problem.

The equations (39) and (40) become equations in place of the equations (21) and (22) described in the first embodiment, respectively.
[[Formula of objective function and constraint expression as mixed integer programming problem]]
Since the value of the equation (39) can only take integers, an integer variable z (z∈Z ₊ (natural number)) is defined. From the above, the equation (35) is converted into the following equations (41) to (45).

The reason why the integer variable z is used without using 41 _{i ず N} β _i as the objective function in the equation (41) is that the branch and bound method may end early, as described in the first embodiment. It is because there is.
The equations (41) to (45) are alternatives to the equations (23) to (27) described in the first embodiment, respectively.
[[Objective function and constraint expression]]
From the above, in the present embodiment, the value of the objective function of the equation (23) can be obtained within the range satisfying the constraints of the following equations (27) to (33) and (41) to (43). The variable x (e) (x ([i, j])) to be minimized will be derived.

  As shown in equation (23), the objective function is the same as in the first embodiment. The equations (28) to (30) are transitivity constraint equations described in the first embodiment. Formula (31) is the same mountain prohibition constraint formula described in the first embodiment. The equation (33) is the hill height constraint equation described in the first embodiment. Expression (27) is a constraint expression that indicates that the integer variable z is a natural number, as in the first embodiment.

  Therefore, the objective function setting unit 202 sets the objective function of equation (23). Further, the constraint equation setting unit 203 sets constraint equations of Equations (27) to (33) and Equations (41) to (43). The setting of the objective function and the constraint equation is performed, for example, in the same manner as described in the first embodiment.

  As described above, the sum of the value obtained by dividing the number of slabs of one vertex (slab group) by the total number of slabs of all slab groups constituting the clique (mountain) including the vertex is obtained for all the vertices. Even if expressed as the total number of peaks, the same effect as the first embodiment can be obtained.

The notation of the total number of mountains described in the first and second embodiments is an example, and as described in the section of [formulation of the total number of mountains] in the first embodiment, Set the weights for each of the vertices so that the sum of the weights for the vertices that make up one clique is 1, and for all of the vertices that make up the undirected graph, the weights set for each of the vertices As long as the total number of peaks is expressed by the sum of the above, the function representing the total number of peaks is not limited to those described in the first and second embodiments.
Also in the present embodiment, various modifications described in the first embodiment can be adopted.

Third Embodiment
Next, a third embodiment will be described. The present embodiment is the sum ( _{総 和 i ∈ N} α _i ) of all the continuous variables α _i described in the first embodiment for all vertices (slab groups), and the continuous variable β described in the second embodiment of _i, both the all vertices sum of (slab _group) (Σ i∈N β _i) was formulated as a common integer variable z, both constraints of the first embodiment and the second embodiment Use Thus, this embodiment is a combination of the constraint equations according to the first and second embodiments. Therefore, in the description of the present embodiment, the same parts as those in the first and second embodiments are denoted by the same reference numerals as those in FIGS. 1 to 3, and the detailed description will be omitted.

[[Objective function and constraint expression]]
In the present embodiment, the value of the objective function of the equation (23) is minimized within the range satisfying the constraints of the following equations (24) to (33) and the equations (41) to (43). The variable x (e) (x ([i, j])) will be derived.

  Therefore, the objective function setting unit 202 sets the objective function of equation (23). Further, the constraint equation setting unit 203 sets constraint equations of Equations (24) to (33) and Equations (41) to (43). The setting of the objective function and the constraint equation is performed, for example, in the same manner as described in the first embodiment.

As described above, the sum (Σ _{i ∈ N} α _i ) of all continuous variables α _i for all the vertices (slab groups) and the total (Σ _i for all the vertices (slab groups) of the continuous variable β _{i If} both of _{整数 N} β _i ) are formulated as a common integer variable z, the search range of the optimum solution can be further narrowed.
The various modifications described in the first embodiment can be adopted also in this embodiment.

(Example)
Next, an example will be described.
In this embodiment, a plan division plan is created by each of the solution method according to the third embodiment (invention example), the solution method according to patent document 1 (comparative example 1), and the solution method according to patent document 2 (comparative example 2) The time required to solve the solution was compared. However, in the case where the calculation time is 3 minutes (180 seconds) or more, it is evaluated by dual gap representing the accuracy of the solution obtained at that time.
The dual gap is expressed by the following equation (44).
Dual gap = {(upper limit value-lower limit value) / upper limit value} × 100 (44)

  In the equation (44), the upper limit value is the value of the objective function of the best solution among the solutions that can realize the sorting plan, obtained three minutes after the start of the calculation. The lower limit value is the value of the largest (worst) objective function among the optimum solutions for solving the relaxation problem, obtained three minutes after the start of calculation. When the upper limit value and the lower limit value match, the solution at that time is the optimal solution. The relaxation problem is a problem in which the condition of the 0-1 variable of the optimization problem is relaxed (the 0-1 variable is allowed to take values between 0 and 1 other than 0 and 1).

Also, in any solution method, the total number of slab groups is 50, and a sorting plan is created for the same slab group (that is, the same sorting target slab group list is used).
Also, in any solution method, k ₁ × total number of peaks + k ₂ × number of inversions is used as an objective function. Here, the weighting factor k ₁ for the total number of peaks (peak height) is 5.0 (k ₁ = 5.0), and the weighting factor k ₂ for the reverse number is 1.0 (k ₂ = 1.0). .
FIG. 4 is a table showing the creation results of the sorting plan by these solutions.

  In FIG. 4, “prohibited%” is a percentage of the ratio of the number of slab groups to the number of branches (branches) that should not be piled up on the same dump pile, with respect to the total number of slab group pairs. “% Reverse” is a slab in which the order of arrival at the yard and the order of arrival at the delivery mountain are reversed with respect to the total number of slab group pairs minus the number of slab group pairs that can not be piled up on the same delivery mountain. The ratio of the number of group pairs is expressed as a percentage. "F. Mt" is the number of feasible mountains (in millions). “Opt. V” is the value of the objective function when the optimal solution is obtained, or the upper limit value. The “number of mountains” is the number of mountains of payout obtained as a result of the optimization calculation. The "inverted" is the number of slab group pairs whose order of arrival at the yard and the order of arrival at the delivery pile is reversed as a result of the optimization calculation.

  Coloring in FIG. 4 is the one with the best solution among the three solutions. As shown in FIG. 4, when the number of feasible peaks reaches tens of millions, the solution of Comparative Example 1 (Patent Document 1) can not obtain a solution that can realize peak division within 3 minutes of calculation time. . In addition, even with the solution of Comparative Example 2 (Patent Document 2), there are many cases where an optimum solution can not be obtained within 3 minutes of calculation time as compared with the solution of the invention example (the above-described embodiment). Bad (ie, the value of Opt. V is large). On the other hand, according to the solution of the invention example (the embodiment described above), stable solution results can be obtained regardless of the size of the problem. In the solution method of the invention example (the embodiment described above), when the data ID is "03", "05", "15", "21", the calculation does not converge within 3 minutes of calculation time, and 3 The best solution among the two solutions has not been obtained. Among these, “03”, “15”, “21”, Opt. Since the value of V is the same as the value of Comparative Example 1 (Patent Document 1), an optimum solution is obtained as a result. Even when the data ID is "05", Opt. The value of V is almost the same as the value of the optimum solution obtained in Comparative Example 1 (Patent Document 1). Therefore, in all the cases of this embodiment, the solution of the invention example (the embodiment described above) is the best solution among the three solutions, or, even if it is not the best solution, Opt substantially equal to the best solution. . It can be seen that the value of V was obtained.

(Other modifications)
The embodiment of the present invention described above can be realized by a computer executing a program. In addition, a computer readable recording medium recording the program and a computer program product such as the program can be applied as an embodiment of the present invention. As the recording medium, for example, a flexible disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a magnetic tape, a non-volatile memory card, a ROM or the like can be used.
In addition, any of the embodiments of the present invention described above is merely an example of implementation for carrying out the present invention, and the technical scope of the present invention should not be interpreted limitedly by these. It is a thing. That is, the present invention can be implemented in various forms without departing from the technical idea or the main features thereof.

(Relationship with claim)
An example of the relationship between the claims and the embodiments is shown below. The relationship between the claims and the embodiments is not limited to the following relationship, as described in the modification and the like.
<Claims 1, 2, 11>
The objective function setting unit is realized, for example, by using the objective function setting unit 202.
The term for evaluating the total number of payout peaks is realized, for example, by using the first term of the equations (18), (23), and (35).
The term for evaluating the rounding number is realized, for example, by using the second term of the equations (18), (23), and (35).
The constraint expression setting means is realized, for example, by using the constraint expression setting unit 203.
The optimal solution deriving means is realized, for example, by using the optimal solution deriving unit 204.
The total number of payout peaks is realized, for example, by using equation (17).
Mountain carrying number, for example, be achieved by using a portion except for the k ₂ of the second term of equation (23).
<Claim 3>
The total number of payout peaks is realized, for example, by using the integer variable z of the first term of the equation (23) defined by the equations (17), (34), or the equations (25) and (42) Be done.
<Claim 4>
The total number of payout peaks is realized, for example, by using equation (34).
<Claim 5>
The total number of payout peaks is realized, for example, by using the integer variable z of the first term of the equation (23) defined by the equations (25) and (42) (see also the fifth modification).
Claims 6 and 7
The continuous variable is realized, for example, by using the continuous variables α _i and β _i (see also the fifth modification). An integer variable is realized by using an integer variable z.
<Claim 8>
The peak height constraint equation is realized, for example, by using equation (16).
<Claim 9>
The same mountain prohibition constraint equation is realized by using, for example, equations (14) and (15).
<Claim 10>
The steel material group corresponds to, for example, a slab group.
<Claim 12>
The transitivity constraint equation is realized by using, for example, equations (9) to (11).
The first vertex, the second vertex, and the third vertex are realized by, for example, vertices corresponding to slab groups i, j, and k shown in equations (9) to (11).

  200: Classification planning device for steel material, 201: input unit, 202: objective function setting unit, 203: constraint equation setting unit, 204: optimal solution derivation unit, 205: output unit

Claims (14)

A plurality of steel products carried into the yard where steel materials are arranged as storage spaces between processes in the steel process are piled up in the yard so that steel materials having an earlier delivery order to the next process are above, and delivered to the next process It is a steel sorting plan drafting device for drafting a grading plan for producing a plurality of dumping mountains,
The term for evaluating the total number of the piles and the number of reverse pairs in which the steel material having the earlier arrival order to the yard is stacked above the steel material of the later one at the same pile. Objective function setting means for setting an objective function including a term for evaluating
Constraint equation setting means for setting a constraint equation representing a constraint when piling up the steel material;
Calculation for dividing the steel material into the plurality of disbursed peaks by performing optimization calculation by mathematical programming so as to maximize or minimize the value of the objective function within the range satisfying the constraint by the constraint equation. Optimum solution deriving means for
The constraint equation is that the two steel members corresponding to the steel members at the top and the two steel members corresponding to the two vertices connected with each other by branches are the two steel members stacked on the same delivery pile. Including a constraint expression that specifies that the undirected graph to be represented is divided into a plurality of cliques in which the vertices do not overlap each other,
The objective function setting means includes a term for evaluating the total number of cliques as a term for evaluating the total number of the payout piles, and two steel members for which the relationship of the reverse is established as a term for evaluating the number of the reverse pairs. Setting the objective function including a term for evaluating the total number of the branches connecting two corresponding vertices with each other;
The optimum solution deriving means connects the two vertexes corresponding to the two steel members for which the relation of the total number of cliques and the reversal is established in the optimization calculation by the mathematical programming. steel Whack planning apparatus characterized that you assess the total number of. Weights are set for each of the vertices such that the sum of the weights for the vertices of one clique is one;
The steel product according to claim 1, wherein the total number of the payout piles is defined as a sum of weights set for each of the vertices for all of the vertices forming the undirected graph. Classification planning device.   The total number of the disbursed peaks is a non-linear function of a non-linear function which is the inverse of a value obtained by adding one to the number of the branches mutually interconnecting the vertex and the other vertexes constituting the clique including the vertex. The steel product separation planning device according to claim 2, characterized in that it is defined as a sum of all of the vertices forming the directional graph.   The total number of the disbursed peaks is a non-linear function of a non-linear function which is a value obtained by dividing the number of steel members corresponding to the vertexes by the total number of steel members corresponding to all the vertices constituting the clique including the vertex. The steel product separation planning device according to claim 2, characterized in that it is defined as a sum of all of the vertices forming the directional graph.   The total number of the disbursed peaks is a non-linear function of a non-linear function which is the inverse of a value obtained by adding one to the number of the branches mutually interconnecting the vertex and the other vertexes constituting the clique including the vertex. The sum of all of the vertices constituting the directional graph, and the number of steel members corresponding to the vertices divided by the total number of steel members corresponding to all the vertices constituting the clique including the vertex The steel distribution planning device according to claim 2, characterized in that two non-linear functions are defined as the sum of all the vertices of the undirected graph.   The total number of the payout piles is a continuous variable set for each of the vertices, and all of the vertices of the undirected graph of the continuous variable representing the upper limit value for the piecewise linear function converted from the non-linear function The steel material sorting plan drafting device according to any one of claims 3 to 5, which is defined as a sum of.   7. A method according to claim 6, wherein a summation of all the vertices constituting the undirected graph of the continuous variable is an integer variable, and the integer variable is defined as a total number of the piles for dispensing. Planning device.   The constraint equation includes a peak height constraint equation indicating that the steel material corresponding to the vertex and the number of steel materials corresponding to the other vertices constituting the clique including the vertex are equal to or less than an upper limit value. The steel product sorting planning device according to any one of claims 1 to 7, characterized in that The constraint equation setting means derives, based on the size of the steel material, a set of two steel materials which can not be stacked on the same delivery pile;
The restriction equation is characterized by including a same mountain prohibition restriction equation indicating that the accumulation of two steel material sets that can not be stacked on the same pile is prohibited from being piled on the same pile. The sorting apparatus according to any one of claims 1 to 8, wherein the separation of the steels is planned.   The steel distribution plan planning apparatus according to any one of claims 1 to 9, wherein the steel material corresponding to the top is a steel material group made of a plurality of steel materials. 1 is set as a weight for the branch connecting the two vertices corresponding to the two steel members in which the reverse relationship holds, and 0 (zero) is set as a weight for the other branch.
11. The steel product sorting plan drafting device according to any one of claims 1 to 10, wherein the number of reverse pairs is expressed as a total number of weight values set for the branches.   In the constraint equation, the steel material corresponding to the first vertex, the first vertex, the second vertex, and the third vertex, which are the three vertices of the three vertices of the clique, The steel material corresponding to the top of 2 is stacked on the same delivery pile, and the steel material corresponding to the second top and the steel material corresponding to the third apex are on the same delivery mountain If loaded, including a transitivity constraint equation indicating that the steel corresponding to the first vertex and the steel corresponding to the third vertex must also be stacked on the same delivery pile. The sorting apparatus according to any one of claims 1 to 11, characterized in that it comprises: A plurality of steel products carried into the yard where steel materials are arranged as storage spaces between processes in the steel process are piled up in the yard so that steel materials having an earlier delivery order to the next process are above, and delivered to the next process It is a method of planning a plan for dividing steel into a plan for planning a plan for forming a plurality of dumped mountains,
The term for evaluating the total number of the piles and the number of reverse pairs in which the steel material having the earlier arrival order to the yard is stacked above the steel material of the later one at the same pile. Objective function setting step of setting an objective function including a term for evaluating
A constraint equation setting step of setting a constraint equation indicating a constraint when stacking the steel materials in a pile;
Calculation for dividing the steel material into the plurality of disbursed peaks by performing optimization calculation by mathematical programming so as to maximize or minimize the value of the objective function within the range satisfying the constraint by the constraint equation. Optimum solution derivation process to
The constraint equation is that the two steel members corresponding to the steel members at the top and the two steel members corresponding to the two vertices connected with each other by branches are the two steel members stacked on the same delivery pile. Including a constraint expression that specifies that the undirected graph to be represented is divided into a plurality of cliques in which the vertices do not overlap each other,
The objective function setting step includes a term for evaluating the total number of cliques as a term for evaluating the total number of the piles, and the two steels for which the reverse relationship holds as the term for evaluating the number of the reverse pairs. Setting the objective function including a term for evaluating the total number of the branches connecting two corresponding vertices with each other;
In the optimal solution deriving step, the branch connecting the two vertices corresponding to the two steel members in which the relation of the total number of the cliques and the reversal is established in the optimization calculation by the mathematical programming. Whack planning method of steel to the total number of the evaluation to feature the Rukoto a.   A program that causes a computer to function as each means of the steelmaking separation planning unit according to any one of claims 1 to 12.

Images