METHOD AND SYSTEM FOR RESOURCE ALLOCATION

Abstract

To provide a more efficient resource allocation method and system using a genetic algorithm (GA).

The present technology includes a method for allocating resources to a production process including a plurality of processes, the method including allocating priorities to the plurality of processes, selecting processes executable at a first time among the plurality of processes and capable of allocating necessary resources, allocating the necessary resources to the selected processes in descending order of priorities, selecting processes executable at a second time that is later than the first time among the plurality of processes and capable of allocating necessary resources, and allocating the necessary resources to the selected processes in descending order of priorities. The present technology also includes, as a method of expressing genes of GA, not having direct allocation information for genes but having information (priority) for determining an order for allocation.

Claims

1. A method for allocating resources to a production process having a plurality of processes by a computer, the method comprising: allocating priorities which are randomly selected to the plurality of processes; selecting processes executable at a first time among the plurality of processes and capable of allocating necessary resources; allocating necessary resources to the selected processes in descending order of priorities; selecting processes executable at a second time that is later than the first time among the plurality of processes and capable of allocating necessary resources; and allocating necessary resources to the selected processes in descending order of priorities.

2. The method according to claim 1, wherein each of the priorities allocated to the plurality of processes is unique.

3. The method according to claim 1, wherein the priorities are arbitrarily selected.

4. (canceled)

5. The method according to claim 1, wherein the priorities are represented by a real number.

6. The method according to claim 1, wherein the executable processes are unexecuted processes and has no unexecuted preceding processes.

7. The method according to claim 1, wherein the processes capable of allocating necessary resources are processes in which all of the necessary resources are available.

8. The method according to claim 1, wherein the allocating necessary resources to the selected processes in descending order of priorities includes allocating resources until there are no more processes available for allocation.

9. The method according to claim 1, wherein the second time is the earliest time among end times of the processes to which the resources are allocated.

10. The method according to claim 1, further comprising repeating the selecting processes and allocating the necessary resources until all of the plurality of processes are completed.

11. The method according to claim 10, further comprising: setting a time at which all of the plurality of processes are completed as a third time; setting a time at which all of the plurality of processes are completed when priorities different from the priorities are allocated to the plurality of processes as a fourth time; and selecting the priority corresponding to the third time or the fourth time which is not later.

12. The method according to claim 11, further comprising: calculating end times for different priorities until a predetermined number of times or a predetermined amount of time has elapsed; and selecting a priority corresponding to an end time that is not later than any other.

13. A system in which a computer allocates resources to a production process having a plurality of processes, configured to: allocate priorities which are randomly selected to the plurality of processes; select processes executable at a first time among the plurality of processes and capable of allocating necessary resources; allocate necessary resources to the selected processes in descending order of priorities; select processes executable at a second time that is later than the first time among the plurality of processes and capable of allocating necessary resources; and allocate necessary resources to the selected processes in descending order of priorities.

14. A computer-readable medium for allocating resources to a production process having a plurality of processes comprising instructions which, when executed by a computer, cause the computer to carry out: allocating priorities which are randomly selected to the plurality of processes; selecting processes executable at a first time among the plurality of processes and capable of allocating necessary resources; allocating necessary resources to the selected processes in descending order of priorities; selecting processes executable at a second time that is later than the first time among the plurality of processes and capable of allocating necessary resources; and allocating necessary resources to the selected processes in descending order of priorities.

15-18. (canceled)

Description

BRIEF DESCRIPTION OF DRAWINGS

[0019] FIG. 1 is a diagram showing an execution order of each process in a production process including a plurality of processes according to an embodiment of the present technology.

[0020] FIG. 2 illustrates a system in which a computer allocates resources to a production process having a plurality of processes, in accordance with an embodiment of the present technology.

[0021] FIG. 3 is a flow chart illustrating a method for allocating resources to a production process in accordance with an embodiment of the present technology.

DESCRIPTION OF EMBODIMENTS

[0022] FIG. 2 illustrates a system for a computer to allocate resources to a production process having a plurality of processes in accordance with an embodiment of the present technology.

[0023] The system 200 for allocating resources includes a network 210, a server 220, and a client 230.

[0024] The network 210 communicably connects a plurality of devices such as the server 220 and the client 230. The network 210 may be the Internet, a local area network (LAN), or a wide area network (WAN). In addition, the network 210 may be configured in a wired or wireless manner, or a combination thereof.

[0025] The server 220 is a computer having a processor (not shown), a memory (not shown) storing a program, and a communication function (not shown). The server 220 executes a program stored in the memory in response to a request from the client 230, and returns the result to the client 230. In the present application, a “memory” includes not only a main storage device such as a random access memory (RAM) and a read only memory (ROM) but also an auxiliary storage device such as a hard disk drive (HDD) and a solid state drive (SSD).

[0026] The client 230 is a computer, a tablet terminal, a smartphone, or the like having a function of communicating with the server 220 and other devices via the network 210. The number of clients 230 may be one or more.

[0027] FIG. 3 illustrates a flowchart of a method for allocating resources to a production process in accordance with an embodiment of the present technology.

[0028] The resource allocation method 300 according to the present technology begins at step 310, and at step 320, the server 220 prioritizes each process in the production process. The priority given to each process may be unique or may be arbitrarily selected. In addition, the priority may be randomly selected and/or expressed as a real number.

[0029] Next, in step 330, the server 220 selects processes that can be executed and to which the necessary resources can be allocated. An executable process may be a process that has not been executed and has no preceding process that has not been executed. The process to which the necessary resources can be allocated may be a process in which all the necessary resources are available.

[0030] Next, in step 340, the server 220 allocates the necessary resources to each of the selected processes in descending order of priority. Allocating the necessary resources to the selected processes in descending order of priority may be allocating resources until there are no more processes to which resources can be allocated.

[0031] Next, in step 350, the server 220 determines whether any of the processes has been completed. If it is determined that any of the processes has been completed, the process proceeds to step 360. If it is determined that none of the processes has been completed, the process returns to step 350, and is repeated until it is determined that any of the processes has been completed.

[0032] When any of the processes is completed in step 350, the server 220 determines whether all processes are completed in step 360. If it is determined that all the processes have been completed, the process proceeds to step 370. When it is determined that any of the processes has not been completed, the process returns to step 330, and the server 220 selects a process which can be executed at that time and to which necessary resources can be allocated. The time may be the earliest time among the end times of a plurality of processes to which resources are allocated.

[0033] When all the processes are completed in step 360, it is determined in step 370 whether or not a termination condition is satisfied, such as calculation for a predetermined number of generations or only the same solution for a certain period of time. If the termination condition is not satisfied, the array of priorities and the end times or required times of all the processes are stored as one solution, and the process returns to step 320. If the termination condition is satisfied, then the previous solutions are compared and, for example, the one whose end time is not later than any other is taken as the optimal solution, and the resource allocation method 300 terminates at step 380. The comparison of the solutions may be sequentially compared with the previous solution every time all the processes are completed in step 360 with respect to one array of the priority, and a solution whose end time is not later may be set as a new solution. When the end time is the same, the previous solution may be maintained as it is.

[0034] A more detailed embodiment of the present technology will now be described with reference to FIGS. 1 and 3.

[0035] In Table 5, processes A through E in FIG. 1 are prioritized according to step 320 in FIG. 3. In this example, the priority order is represented by a real number in a range of 0 to 1, and a larger value is a higher priority order, that is, to be allocated first. The priority value may be a sufficiently large integer value that is unlikely to overlap. An exclusive integer may be used, but when two individuals are crossed, values may be overlapped, and another means for eliminating the overlap is required. Even when the priority is expressed by a real number, there is a possibility of being overlapped mathematically, but it is extremely rare that a problem may occur when there is a conflict. In this case, it is considered to be sufficient for practical use if, for example, the one appearing earlier is selected.

[0036] When the example of Table 5 is expressed by a program such as C#, for example, like “double[ ] g=new double[ ]{0.5, 0.1, 0.4, 0.2, 0.6};”, the genes of the individuals in the GA can be expressed as array data including priority information for determining the order in which the computer allocates solutions. Since the gene of the individual includes the priority information, it is not necessary to include the information itself of the solution allocated to the gene of the individual.

TABLE-US-00005 TABLE 5 Process A B C D E Array Subscript 0 1 2 3 4 Value(Priority) 0.5 0.1 0.4 0.2 0.6

[0037] Next, according to step 330, a process that can be executed and to which necessary resources can be allocated is selected. At the process start time, processes A and B can be allocated from the order of the processes. In accordance with step 340, since the priority of process A is greater when comparing the priorities of processes A and B, the necessary resource X is allocated to process A as shown in Table 6.

TABLE-US-00006 TABLE 6 ResourceX A ResourceY ResourceZ

[0038] Since the resource X among the necessary resources is already allocated to process A and cannot be used for process B that can be executed at the same time, none of the resources is allocated to process B. Since process A and process B, which are the preceding processes of process C, are not completed, no resource is allocated to process C. Since process B, which is the preceding process of process D, has not been completed, no resource is allocated to process D.

[0039] When process A is completed in step 350, the production process proceeds to step 360, and the production process returns to step 330 because all the processes have not been completed yet at this time. In step 330, a process that can be executed and to which necessary resources can be allocated is selected. At the end time of process A, it is only process B that can be allocated from the order relationship of the process. It is shown in Table 7 that after the end of process A, the necessary resources X and Y are allocated to process B.

TABLE-US-00007 TABLE 7 ResourceX A B ResourceY B ResourceZ

[0040] Since process A and process B, which are the preceding processes of process C, are not completed, no resource is allocated to process C. Since process B, which is the preceding process of process D, has not been completed, no resource is allocated to process D.

[0041] When process B is completed, a process which can be executed and to which necessary resources can be allocated is selected according to step 330 again in the same manner as described above. At the end time of process B, processes C and D can be allocated based on the order relationship of the processes. Comparing the priorities of processes C and D according to step 340, since the priority of process C is greater, the necessary resources Y and Z are allocated to process C as shown in Table 8.

TABLE-US-00008 TABLE 8 ResourceX A B ResourceY B C ResourceZ C

[0042] For process D that can be executed at the same time, since the resource Y among the necessary resources has already been allocated to process C and cannot be used, none of the resources is allocated to process D.

[0043] When process C is completed, a process which can be executed and to which necessary resources can be allocated is selected in accordance with step 330 again in the same manner as described above. At the end time of process C, processes D and E can be allocated based on the order relationship of the processes. When the priorities of processes D and E are compared in accordance with step 340, since the priority of process E is greater, the necessary resource Z is allocated to process E as shown in Table 9.

TABLE-US-00009 TABLE 9 ResourceX A B ResourceY B C ResourceZ C E

[0044] For process D that can be executed at the same time, since both of the necessary resources X and Y are not allocated and available, the necessary resources X and Y are allocated to process D as shown in Table 10.

TABLE-US-00010 TABLE 10 ResourceX A B D ResourceY B C D ResourceZ C E

[0045] Upon completion of processes D and E, according to step 360, it is determined whether a termination condition is satisfied, and if not, the solution is stored and the process returns to step 320, and if the termination condition is satisfied, an optimal solution among the previously stored solutions is determined, and the resource allocation method 300 ends at step 380.

[0046] In the above example, when the time required for each process is one hour, a schedule as shown in Table 11 can be created.

TABLE-US-00011 TABLE 11 9:00 10:00 11:00 12:00 13:00 14:00 15:00 X A B D Y C Z E

[0047] Further, in the case where the respective processes have different required times (not necessarily in units of one hour), a schedule as shown in Table 12 can be created. In Table 12, the start time and the end time of each process can be recursively obtained based on the end time of the process executed before that, for example, start time of process C=end time of process B, (end time of process B=start time of process B+required time of process B, start time of process B= . . . ). If process F using the resources Y and Z is finally present, the start time of process F is the end time of processes D and E, whichever is not earlier (MAX). For simplicity, the end time of a process and the start time of the next process are the same, but a certain time interval may be provided between processes, or the time required for preparation or transition of processes may be included in the required time of the process or the next process.

TABLE-US-00012 TABLE 12 9:00 10:00 11.00 12:00 13:00 14:00 15:00 X [00001] [00002] [00003] Y [00004] Z [00005]

[0048] Returning to step 320, Tables 13 and 14 show examples in which different priorities are allocated and the results of expansion thereof. In this case, genes of individuals can be expressed as array data as in an actual program (for example, in C#, double[ ] g=new double[ ]{0.5, 0.7, 0.4, 0.8, 0.6}).

TABLE-US-00013 TABLE 13 Process A B C D E Array Subscript 0 1 2 3 4 Value(Priority) 0.5 0.7 0.4 0.8 0.6

TABLE-US-00014 TABLE 14 9:00 10:00 11:00 12:00 13:00 14:00 15:00 X [00006] [00007] [00008] Y [00009] Z [00010]

[0049] When Table 12 and Table 14 are compared, it can be said that the allocation result of Table 12 is a better individual, i.e., a more suitable solution, in that the entire process is completed earlier.

INDUSTRIAL APPLICABILITY

[0050] According to the present technology, the resources are sequentially allocated in accordance with the execution order of the processes, and the priority can be used as a method of solving selection in a case where there is a conflict (there are a plurality of choices). Therefore, all individuals (solution candidates) are always feasible solutions, and a more suitable solution can be searched more efficiently than the conventional method in which a feasible solution rarely appears.

REFERENCE SIGNS LIST

[0051] 210 network [0052] 220 Server [0053] 230 Client