Method for allocating resources to jobs using network flow algorithms
AssigneeSiemens Aktiengesellschaft
InventorsChristoph Moll, Thomas Nüssler
Life of this patent
Estimating the term…
Abstract
A resource allocation system is described in which resources and jobs are arranged as a network flow graph. In the system, resources are allocated to jobs using a network flow algorithm applied to the graph. The algorithm is applied from a graph source to a graph sink by finding a solution progressively for each time interval.
Claims9
A method for determining an allocation of m resources Rm to fixed time k jobs Jk equipped with respective suitabilities/capabilities for fulfilling jobs, which are to be executed in k time windows in each case, comprising:
- arranging, by a computer, resource time breaks that can be shifted in time, the m resources and the fixed time k jobs as a time layered network flow graph;
- and
- determining, by the computer a set allocations of the m resources to k jobs based on the network flow graph by computing a time discretization with n time intervals and by applying a network flow algorithm to the network flow for each interval, with an ith (1≦i≦n) assignment of the m resources to the k jobs being retained for the ith application of the network flow algorithm to the network flow graph for the ith to nth time interval of the k jobs, with, in the ith application of the network flow algorithm to the network flow graph, the assignments to the time intervals belonging to the first to ith jobs which were retained in previously executed first to ith applications of the network flow algorithm to the network flow graph, being kept constant for the ith application of the network flow algorithm, and with, in the ith application of the network flow algorithm to the network flow graph, at least one connector of the network flow graph being given a definable cost factor in accordance with at least one definable rule without considering any resource travel time and without considering any job priority;
- and
- displaying the flow graph on a display.
A non-transitory computer readable storage for controlling a computer with commands stored thereon for executing a method for determining an allocation of m resources Rm to fixed time k jobs Jk equipped with respective suitabilities/capabilities for fulfilling jobs, which are to be executed in k time windows in each case, comprising:
- arranging resource time breaks that can be shifted in time, the m resources and the fixed time k jobs as a time layered network flow graph;
- and
- determining, by the computer a set allocations of the m resources to k jobs based on the network flow graph by computing a time discretization with n time intervals and by applying a network flow algorithm to the network flow for each interval, with an ith (1≦i≦n) assignment of the m resources to the k jobs being retained for the ith application of the network flow algorithm to the network flow graph for the ith to nth time interval of the k jobs, with, in the ith application of the network flow algorithm to the network flow graph, the assignments to the time intervals belonging to the first to ith jobs which were retained in previously executed first to ith applications of the network flow algorithm to the network flow graph, being kept constant for the ith application of the network flow algorithm, and with, in the ith application of the network flow algorithm to the network flow graph, at least one connector of the network flow graph being given a definable cost factor in accordance with at least one definable rule without considering any resource travel time and without considering any job priority;
- and
- displaying the flow graph on a display.
Dependencies are inferred from the claim text.