Method for resource allocation and scheduling, and system therefor

Claim 2

An analyzing method of resource allocation according to claim 1, whereby said step 1 includes a process to select a next node to be an object for next determination of the weight among the adjacent nodes connected with the earlier processed node by branches.

Claim 3

An analyzing method of resource allocation according to claim 1 or 2, whereby strongly connected components are extracted from said graph, so that all the branches in a graph of a model obtained by removing self-closed loops from said one or a plurality of strongly connected components are weighted.

Claim 4

In an analyzing system for resource allocation which comprises an input device for inputting various information for the resource allocation, an output device for outputting the result of the resource allocation and a processor, said processor executing to a model of a graph consisting of nodes representing the status and branches representing the status transition, and including closed loops: step 1 to select a node from which to start determination of the weight of branches among all the nodes; and step 2 to classify the nodes depending on the determining state of the weight of input branches and output branches of the selected node, and to weight all the input branches x ji and output branches x ij of every classified pattern of nodes i so that y≡Σx ij is as small as possible under a constraint represented by the following equation (1), Σ j x ij - Σ j x ji = 0 x ij ≧ 0   (1) so that all the branches in the graph are weighted by repeating steps 1 and 2.

Claim 5

An analyzing system for resource allocation according to claim 4, wherein said step 1 includes a process to select a next node to be an object for next determination of the weight among the adjacent nodes connected with the earlier processed node by branches.

Claim 6

An analyzing system for resource allocation according to claim 4 or 5, wherein said processor extracts strongly connected components from said graph, thereby to process a model obtained by removing self-closed loops from said one or a plurality of strongly connected components.

Claim 7

An analyzing method of maximum flow of a network to a model of a graph consisting of nodes and branches and including a closed loop, which comprises: step 1 to select a node from which to start determination of the flow rate among all the nodes in the graph; step 2 to classify the nodes depending on the determining state of the flow rate of input branches and output branches of said selected node, and to determine the flow rate of all the input branches x ji and output branches x ij of every classified pattern of nodes i so that y≡Σx ij is as small as possible under a constraint represented by the following equation (1); Σ j x ij - Σ j x ji = 0 x ij ≧0   (1) step 3 to determine the flow rate of all the branches in the graph by repeating steps 1 and 2; and step 4 to detect a branch having the maximum flow rate among all the branches in the graph, thereby to obtain the branch with the maximum flow in the graph and the flow rate.

Claim 8

An analyzing method of maximum flow of a network according to claim 7, wherein said step 1 includes a process to select a node to be an object for next determination of the flow rate among the adjacent nodes connected with the earlier processed node by branches.

Claim 9

An analyzing method of maximum flow of a network according to claim 7 or 8, further comprising: a step to extract a strongly connected component from said graph, thereby to obtain a branch with the maximum flow rate and the flow rate to a model obtained by removing a self-closed loop from said one or a plurality of strongly connected components.

Claim 10

A scheduling method to a model of a graph consisting of nodes representing the status and branches representing the status transition, and including a closed loop, which comprises: step 1 to select a node from which to start determination of the weight of branches among all the nodes in the graph; step 2 to classify nodes depending on the determining state of the weight of input branches and output branches of said selected node, and to weight all the input branches x ji and output branches x ij of every classified pattern of nodes i so that y≡Σx ij is as small as possible under a constraint represented by the following equation (1); Σ j x ij - Σ j x ji = 0 x ij ≧0   (1) step 3 to determine the weight of all the branches in the graph by repeating steps 1 and 2; step 4 to detect a branch with the maximum weight among all the branches in the graph, and step 5 to arrange all the nodes constituting the closed loop in the order by removing the branch with the maximum weight detected in step 4 and cutting the closed loop including the branch.

Claim 11

A scheduling method according to claim 10, wherein said step 1 includes a process to select a node to be an object for next determination of the weight among the adjacent nodes connected with the earlier processed node by branches.

Claim 12

A scheduling method according to claim 10 or 11, further comprising: a step to extract a strongly connected component from said graph, and to remove a branch with the maximum weight from a model obtained by removing a closed loop from said one or a plurality of strongly connected components, so that all the nodes constituting the closed loop including the branch with the maximum weight are arranged in the order.

Claim 13

A scheduling system provided with an input device for inputting various information for the scheduling, an output device for outputting the scheduling result, and a processor, wherein a model of a graph consisting of nodes representing the status and branches representing the status transition and, including a closed loop is processed by said processor in accordance with a flow of procedures set beforehand, said flow of procedures comprising: step 1 to select a node from which to start determination of the weight of branches among all the nodes in said graph; step 2 to classify the nodes depending on the determining state of the weight of input branches and output branches of the selected node, and to weight all the input branches x ji and output branches x ij of every classified pattern of nodes i so that y≡Σx ij is as small as possible under a constraint represented by the following equation (1); Σ j x ij - Σ j x ji = 0 x ij ≧0   (1) step 3 to determine the weight of all the branches in said graph by repeating steps 1 and 2; step 4 to detect a branch with the maximum weight among all the branches in said graph; and step 5 to arrange the nodes constituting the closed loop in the order by removing the branch with the maximum weight which is detected in step 4 and cutting the closed loop including said branch.

Claim 14

A scheduling system according to claim 13, wherein said step 1 includes a process to select a node to be an object for next determination of the weight among the adjacent nodes connected with the earlier processed node by branches.

Claim 15

A scheduling system according to claim 13 or 14, wherein said flow of procedures further comprises a step to extract strongly connected componentd from said graph thereby to process a model obtained by removing closed loops from said one or a plurality of strongly connected components.