KR101617689B1 - A method and system for fast resource allocation planning using plan retrieval and repair - Google Patents

Abstract

The present invention relates to a resource allocation planning method and system, and more particularly, it relates to a resource allocation planning method and system, and more particularly to a resource allocation planning method and system using a plan database generated in advance for various situations, The present invention relates to a method and a system for high-speed resource allocation planning using a plan search and correction technique capable of generating a plan in a short time by deriving a plan for a situation.
(A) generating a problem situation feature vector for a given problem situation; (b) searching a plan database, detecting a similar situation feature vector for the problem situation feature vector and a plan already created for the similar situation feature vector; And (c) calculating a plan for the problem situation by modifying a preliminary plan for the similar situation feature vector. According to the present invention, there is provided a method for planning a resource allocation, In calculating the plan for the resource allocation problem, a similar situation with respect to the problem situation is detected in the previously generated plan database, and a plan for the problem situation is derived by modifying the similar plan accordingly, There is an effect of providing a resource allocation planning method and system capable of calculating an efficient resource allocation plan in real time or within a short time.

Description

Technical Field [0001] The present invention relates to a method and system for fast resource allocation using a plan search and correction technique,

The present invention relates to a resource allocation planning method and system, and more particularly, it relates to a resource allocation planning method and system, and more particularly to a resource allocation planning method and system using a plan database generated in advance for various situations, The present invention relates to a method and a system for high-speed resource allocation planning using a plan search and correction technique capable of generating a plan in a short time by deriving a plan for a situation.

The problem of resource allocation planning is the problem of allocating resources to activities so that the desired performance is given when limited resources and activities that require them are given. Here, resources and activities are abstract concepts. Activities such as tasks to be performed normally, manufacturing processes in factories, delivery of goods, and the like are the activities, and the personnel, machinery, facilities These are resources.

The way in which the activities are performed can be variously specified. In some cases, one activity may be composed of several sub-activities, and the sub-activities may be performed in a sequential manner. In some cases, these activities may be performed in parallel. Some of these activities may be performed sequentially, while others may be performed in parallel.

In addition, the resource requirements required to perform one sub-activity can be variously defined in terms of the resource type and the number of sub-activities. One sub-activity requires one or more resources belonging to one resource type Or may require more than one resource from each of the multiple resource types, and for one sub-activity, there may be multiple such resource requirements as one or more alternatives.

That is, one activity type is defined by specifying the order of execution of the detailed activities described above and the resource requirements of each detailed activity, and one resource allocation planning problem is defined by one or more activity types and each activity type The type of resource, and the number of resources available for each resource type. The definition of activity types and resource types includes constraints ( constraint.

The performance of the resource allocation plan problem typically involves maximizing the utilization rate of the resource or minimizing the cost by performing all the activities to be performed during a given planning period, maximizing the due date required for the activities, There are various types of performance objectives, such as minimizing the amount of time it takes to perform all of the activities, and this is called the objective function of the resource plan assignment problem.

For example, in the case of supply chain management, the master planning problem is the total cost of production, cost of inventory, shipping costs, costs due to delivery delays, and order fulfillment when given weekly forecast demand Weekly production from each factory, weekly transportation from each factory to each distribution center, and weekly transportation from each distribution center to the customer are determined to minimize the costs incurred by the customer. There are corresponding activities in the factory, production work and transportation between factories, distribution centers, and customers to deal with the demand. There are factories with limited production capacity and various transportation vehicles with limited transportation capacity. do.

As another example, among the distribution problems, the problem of the display of each store is to determine which products are displayed on the display shelves of the retail store. It is a matter of maximizing the daily space utilization and maximizing product sales. The problem is to create. In the case of this problem, a finite number of merchandise display positions correspond to the resources, and the display of each merchandise corresponds to an activity that requires the merchandise display position of the store where the merchandise is the resource.

More specifically, in order to explain the resource allocation planning problem, the present invention explains the scheduling problem as an example.

Scheduling problems have been extensively applied in situations where process management in conventional computer systems, efficient management of limited resources such as process management, logistics systems, and hospitals in manufacturing systems is required, and various techniques exist for this.

This scheduling problem refers to the problem of determining when and how to handle a given resource when there are jobs to be processed, and the solution is called a schedule. That is, the task in the scheduling problem corresponds to the activity in the resource allocation planning problem.

Specifically, a scheduling problem consists of one or more types of resource types and one or more task types, and each task is defined as one or more operations to be processed. An operation may require more than one resource type, and each resource type may require more than one resource. In addition, there can be several alternative resources in one operation. There may be precedence constraints expressing possible work routes among tasks belonging to one task, where the posterior relations may be serial or parallel, and there may be one or more alternative work orders It is possible.

For example, considering the problem of creating a schedule for a semiconductor line A, there are 1 R1, 2 R2, and 3 R3 units used in a semiconductor line, and the products produced in the line are J1 and J2 Let's say that we can have an alternative work order of O11 → O12, or O11 → O13 for production of J1 product, and a work order of <O21, O22> → O23 for J2. Where <O21, O22> indicates that two jobs can be performed simultaneously. The resources required to perform each task are O11 = {R1, R2}, O12 = {2R2}, O13 = {R1,2R3}, O21 = {R3}, O22 = {2R2}, O23 = {R1} And can be represented in a multi-set form. For example, task O13 indicates that one resource of R1 type and two resources of R3 type are required.

As an example of the schedule generation, a case may be considered in which a schedule for maximizing the total production amount of J1 and J2 for a given planning period is created for the above case. In addition, various objective functions can be used for the scheduling problem. For example, maximization of resource utilization rate, minimization of total task completion time, and maximization of delivery deadline for task are examples of objective functions. In addition, instead of using only one objective function, a method of optimizing and combining several objective functions by weighting is often used.

However, it is true that the above scheduling work has many difficulties. For example, in the case of semiconductor packaging lines, there are various kinds of substitute equipment that can perform the tasks and the operations required in accordance with the package to be produced. In addition, when one equipment performs one operation and then performs another operation, depending on the situation, it may take time to perform a setup change of the equipment. Therefore, in order to optimize the defined objective function while considering the above-mentioned constraints, if a schedule for all the equipments in the production line is to be generated for a given package, It is necessary to generate a schedule in consideration of the condition, which requires a considerable amount of time and effort.

Furthermore, in the case of the large-scale equipment industry such as the above-mentioned semiconductor packaging line, it is necessary to perform a quick re-scheduling operation due to a sudden failure of a specific equipment, etc. However, when a long time is required for scheduling, The loss can be very large. In addition, a request for a rapid resource allocation plan can not be overlooked even when the efficient allocation of resources can be directly linked to the competitiveness of the company, such as the resource allocation planning problems in the above-described supply chain management or distribution. Thus, there is a demand for a method and a system capable of realizing a resource allocation plan task according to a specific problem situation in real time or in a short time. However, existing methods require much time to generate a plan with high performance, In order to generate the plan, the performance of the resulting plan is unsatisfactory. However, the appropriate solution is not yet presented.

It is an object of the present invention to provide a resource allocation planning method and system capable of realizing efficient resource allocation plan creation in real time or in a short time according to a specific problem situation do.

According to one aspect of the present invention, there is provided a resource allocation planning method comprising the steps of: (a) generating a problem situation feature vector for a given problem situation; (b) searching a plan database, detecting a similar situation feature vector for the problem situation feature vector and a pre-established plan for the same; And (c) calculating a plan for the problem situation by modifying the preliminary plan for the similar situation feature vector, wherein the plan database stores a plurality of situation feature vectors and pre-generated plans thereon And is managed.

Prior to the step (a), (p), in order to generate and store plans for a plurality of context feature vectors in advance, various context feature vectors are input and a plan is generated using a separate planner Thereby creating the plan database.

  Here, in the step (p), when the plurality of problem situations exist in generating the plan database, the capacity of the plan database is calculated by using representative values of one or more problem situations using the predetermined rule Can be reduced.

Here, in the step (p), a plan database for a case where the problem situation is changed significantly can be generated in advance.

Here, the step (b) may include: using a similar situation feature vector recommender, a modified plan calculated from the plan for the situation feature vectors stored in the plan database via the plan corrector, Detecting similarity feature vectors and their plans for which the performance values of a given item are predicted to be the most similar when comparing a plan that a situation feature vector is calculated through a plan generator, Can be stored and managed.

Here, the step (b) may be a step of detecting one or more situation feature vectors most similar to the problem situation feature vector in the plan database, using a similar situation feature vector recommender.

Here, prior to step (b), the method may further include generating the similar situation feature vector recommender by applying a machine learning technique to (q) a plurality of context feature vectors and plans therefor have.

Here, the machine learning technique may include a support vector machine or a k-Nearest Neighbor (k-NN) technique.

The step (b) may include filtering the context feature vector of the plan database in advance so as to detect only some context feature vectors of the plan database and detect the similar situation feature vector.

Herein, the plan database stores and manages all of the plurality of situation feature vectors and the plan generated in advance by using the plan generator, or a part of the plan major information, and in the step (b) The similarity feature vector for the problem situation feature vector and all or part of the information about the similarity feature vector are recommended from the similarity feature vector recommender, and in the step (c), the similarity feature vector The plan in the problem situation can be generated by modifying all or part of the information about the plan.

In the step (b), the similarity situation feature vector and the plan for the problem situation feature vector are searched using the situation feature vector and the derivation situation feature vector of the plan database, And the plan database may store and manage a plurality of derivation feature vectors and a plan thereof together with a plurality of context feature vectors and a plan thereof.

Here, the step (c) may include inputting the similar situation feature vector, a plan previously generated by using the plan generator, and the problem situation feature vector, using the plan corrector, It can be a step of calculating the plan.

Here, when the similar situation feature vector recommender recommends one or more similar situation feature vectors, the plan modifier may calculate a plan having the best plan performance value by modifying the plan according to each similarity feature vector.

Here, the plan modifier may include a plan that is obtained by modifying a plan generated beforehand for the similar situation feature vector so as to fit the problem situation feature vector, and a resource allocation plan using the plan generator by inputting the problem situation feature vector The plan is modified in accordance with a scheme capable of minimizing the performance difference from the plan derived when it is assumed that the similarity condition is directly generated, It may be to modify the generated plan.

Here, the plan corrector may be configured to apply machine learning to simulate the existing plan generator of the planner by using plans generated using an existing plan generator for a plurality of context feature vectors as learning data It may be generated.

Here, the machine learning technique may include an on-line learning, a support vector machine, and a reinforcement learning technique.

Here, when a plan corrector is used to generate a plan for the plurality of derivative feature vectors, the plan database also records the number of plan corrections required for correcting the plan of the similar situation feature vector by the plan corrector And the plan correction frequency information can be used later in the plan correction work by the plan corrector.

Here, the problem situation feature vector may include at least one of a type of available resources, a number of types of available resources, a type of activity, a number of types of activities, a pre-relationship between sub-activities in each type of activity, A cost information and a time information related to the activity and the detailed activity, the calculated plan information, the plan performance value, and the objective function.

When the likelihood feature vector recommender detects a similar situation feature vector, if the probability of error calculated by a predetermined method exceeds a specific threshold value, Can be calculated directly.

According to another aspect of the present invention, a resource allocation planning system includes a plan database for storing and managing plan and plan performance values generated using a plurality of context feature vectors and a plan generator separately for the plurality of context feature vectors; Searching the plan database to detect a situation feature vector most similar to the problem situation feature vector, or, from a plan for the context feature vectors stored in the plan database, A similar situation feature vector recommender for deriving a similar situation feature vector predicted to have the most similar performance value of a given item and a previously generated plan when comparing the plan calculated through the plan generator with the problem situation feature vector; And a plan corrector for calculating a plan for the given problem situation by modifying the plan for the one or more similar situation feature vectors.

Here, the similarity feature vector recommender applies a machine learning technique such as a support vector machine or a k-nearest neighbor (k-NN) to a plurality of context feature vectors and a plan thereof Lt; / RTI &gt;

Here, the plan corrector inputs the modified plan according to the modification of the plan and the problem situation feature vector in consideration of the problem situation feature vector, the similar situation feature vector for the same, and the plan for the similar situation feature vector The plan may be modified according to a scheme that minimizes the difference in the performance value from the derived plan when it is assumed that the resource allocation plan is directly generated using the plan generator.

Here, the plan modifier may use plans generated using an existing plan generator for a plurality of context feature vectors as learning data, so that when an arbitrary problem situation feature vector is given, May be generated by applying machine learning to simulate the plan generated by the plan generator of FIG.

Here, the plan database may be generated by reducing the capacity of the plan database by using representative values of one or more problem situations using a predetermined rule, when the plurality of problem situations exist.

Here, the plan database may have previously generated a plan database for a case where a problem situation is significantly changed in generating the plan database.

Here, the similarity feature vector recommender may filter the context feature vector of the plan database in advance to search only some of the context feature vectors of the plan database to detect the similar situation feature vector.

Herein, the plan database stores and manages all of the plurality of situation feature vectors and the plan information generated beforehand by using the plan generator, or a part of the plan major information, and the similar situation feature vector recommender includes: Extracts all or part of the similarity feature vector and its plan for the problem situation feature vector by searching for the feature vector, and the plan modifier corrects all or part of the plan for the similarity feature vector Thereby generating a plan in the above-described problem situation.

Here, the similarity condition feature vector recommender searches for a situation feature vector and a derivation condition feature vector of the plan database, detects a similar situation feature vector for the problem situation feature vector and a plan therefor, and the plan database stores a plurality of In addition to a situation feature vector and a plan for it, a plurality of derivation feature vectors and a plan for them may be stored and managed together.

Here, when generating a plan for the plurality of derivative feature vectors, when using a planner, the planner also records the number of plan corrections required for the planner to modify the plan of the similarity feature vector And the plan modification frequency information can be used later in the plan modification work by the plan modifier.

Here, the problem situation feature vector may include at least one of a type of available resources, a number of types of available resources, a type of activity, a number of types of activities, a pre-relationship between sub-activities in each type of activity, A cost information and a time information related to the activity and the detailed activity, the calculated plan information, the plan performance value, and the objective function.

Here, when the similarity feature vector recommender detects the similarity feature vector, if the error probability calculated by the predetermined method exceeds a certain threshold value, the plan condition generator is not used, Can be calculated directly.

According to the present invention, in calculating a plan for a given resource allocation problem situation, a similar situation for the problem situation is detected in a previously generated plan database, and a plan for the problem situation is derived by correcting the similar plan accordingly Thereby, it is possible to provide a resource allocation planning method and system capable of calculating an efficient resource allocation plan according to a specific problem situation in real time or in a short time.

BRIEF DESCRIPTION OF THE DRAWINGS The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of the specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention.
1 is a flowchart of a resource allocation planning method using a plan search and correction technique according to an embodiment of the present invention;
FIG. 2 is a data flow diagram when a plan database is created according to an embodiment of the present invention; FIG.
3 is a data flow diagram at the time of generating a plan database including a derivation feature vector according to an embodiment of the present invention.
FIG. 4 is a data flow diagram when a similar situation feature vector recommender is generated according to an embodiment of the present invention. FIG.
5 is a data flow diagram at the time of calculating a plan for a problem situation according to an embodiment of the present invention.
FIG. 6 is a block diagram of a resource allocation planning system using a plan search and modification technique according to an embodiment of the present invention; FIG.

BRIEF DESCRIPTION OF THE DRAWINGS The present invention is capable of various modifications and various embodiments, and specific embodiments will be described in detail below with reference to the accompanying drawings.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, the present invention will be described in detail with reference to the accompanying drawings.

The terms first, second, etc. may be used to describe various components, but the components are not limited by the terms, and the terms are used only for the purpose of distinguishing one component from another Is used.

According to the present invention, when calculating a resource allocation plan for a complex problem situation constituted by various activities and resources such as a semiconductor production process, it can take a lot of time and thus cause a considerable loss. A similar situation feature vector most similar to the problem situation feature vector is generated in the previously generated plan database 610, and a pre-existing plan feature database The present invention provides a resource allocation planning method and system capable of performing a planning task for a specific problem situation in real time or in a short time by deriving a plan for the problem situation by correcting the detected plan, do.

Here, the term "problem context" refers to data defining a resource allocation plan problem to be solved, and includes all the data necessary for defining a resource allocation problem. For example, the objective function of a resource allocation problem, the type of available resources, the number of available resources by type of each resource, the type of activity and the number of each activity type to be dealt with, Path, priority among activities, completion request date for each activity, constraints on changing resource settings, resource setting status, cost and time information related to activities and detailed activities, and the like.

For example, consider the case of creating a schedule to produce two J1 products and three J2 products in order to look more closely at the example of the semiconductor line A above. The types and numbers of the above tasks are 2J1, 3J2, O11 → O12, or O11 → O13, and <O21, O22> → O23, and the time required for each operation as the type and the number of 1R1, 2R2, 3R3, And thus constitutes the above-described problem situation.

In addition, the Context Feature Vector is a vector including data having a variable attribute among the data of the problematic situation. Hereinafter, the calculation of the similar situation feature vector and the configuration of various context feature vectors Can be used.

In the above example, the number of tasks having a variable attribute in a single semiconductor line, except for items with low possibility of fluctuation in terms of the time-based resource allocation plan such as the post-relationship of each task, The number of each operation, the type and number of equipment, and the like. Therefore, in terms of time-sched- uled scheduling, the type and number of tasks that are highly likely to fluctuate and the number and types of input equipment, including two J1s and three J2s, R1s R1s, R2s R2s, R3 R3s (2J1, 3J2, 1R1 2R2, 3R3) may be problematic feature vectors.

However, the variable attribute is relative to the definition of the planning period and the period of the scheduling. If the scheduling is performed not every hour but every week, it is assumed that it does not change in the time scheduling such as the time required for the task. It may be treated as a variable and included in the problem situation feature vector.

In addition, the plan database 610 may include a plurality of context feature vectors and performance values of a plan and a plan for the context feature vectors, And the vector for various virtual situations generated by

In order to explain this easily, a method of returning to the previous example and appropriately varying the values of each item based on the problem situation feature vector will be described. Therefore, when the equipment R1 is 1, 2, 4, and R2 is 2, 3, and 4, when J1 is 1, 2, and 5, and J2 is 2, 3, and 6 And the like, and by combining them, it is possible to construct various situation feature vectors such as cases where J1 is reduced (1J1, 3J2, 1R1 2R2, 3R3) in the problem situation feature vector. In addition, each situation feature vector and its performance values are obtained through the resource allocation plan generator, and then stored and managed in the plan database 610.

Also, the similarity feature vector may include a plurality of context feature vectors, which are most similar to the problem context feature vector among the plurality of context feature vectors stored in the schedule database 610, When a modification is made using the plan corrector 630, the feature vector is estimated to have the smallest performance difference.

Again, in the previous example, if the problem situation feature vector is changed so that R1 is 1, R2 is 2, R3 is 3, J1 is 1, while J2 is 5 (1J1, 6J2, 1R1 2R2, 3R3), and this value can be a similar situation feature vector.

The similarity feature vector and the plan for the similarity feature vector thus detected are stored in the plan database 610 in consideration of the difference between the problem situation feature vector and the similar situation feature vector, 630) to be used as a resource allocation plan for the problem situation.

Here, the stored plan is a plan derived by using a separate plan generator 220 for a given situation. By modifying the stored plan using the plan preparation unit 630 below, A plan with a performance value that is very close to or greater than the saved plan can be derived.

FIG. 1 is a flowchart illustrating a resource allocation planning method using a plan search and correction technique according to an embodiment of the present invention. 1, a resource allocation planning method using a plan search and correction technique according to an embodiment of the present invention includes generating a plan database 610 (S110), a similar situation feature vector recommender 620 S120), receiving a problem situation (S130), calculating a problem situation feature vector (S140), detecting a similar situation feature vector (S150), modifying a plan for the similar situation feature vector And deriving a plan for the situation (S160).

First, a step S110 of creating the plan database 610 will be described. In generating the plan database 610, it is important to select an appropriate problem situation first. By creating the plan database 610 based on a problematic situation that is likely to occur in an actual situation, it is possible to shorten the calculation time by reducing the amount of the database, and to obtain a plan with higher performance.

As a method for appropriately selecting a problem situation, there is a method of collecting and using data on various problem situations that existed for the problem in the past. If the number of such problems is too large, the amount of the plan database 610 is adjusted by applying a predetermined rule to the data of the problem situation, clustering and using the representative value of the problem situation or the data of the problem situation The calculation time can be shortened. As an example of the above, a method of using a median for a plurality of problem situation data, a method of finding a problem situation based on the occurrence frequency of the problem situation, and the like can be given.

In addition, in selecting the problem situation, a plan database 610 including a problem situation for a case where a problem situation is expected to be significantly changed in future, apart from a problem situation for a situation existing in the problem, It is also possible to generate it in advance.

When the problem situation is given, a problem situation feature vector is calculated, and a plurality of situation feature vectors are constructed while slightly changing the values, and then the plans are derived using the conventional plan generator 220. The problem condition feature vector may be configured to include items that can be varied among the items of the problem situation. In addition, the problem condition feature vector may be calculated based on various situations existing in the existing problems, . The conventional plan generator 220 can be used without any restriction, irrespective of the type, even if the generation of the optimal solution is not guaranteed if an appropriate plan can be derived.

At this time, the problem situation feature vector covers all the data necessary for defining the resource allocation problem, including the type of available resources, the number of available resources by type, the type of activity, the number of types of activity, Cost and time information related to the activity and detailed activities, the calculated plan, and the time and cost of the resource. Information such as information, plan performance value, objective function, and the like.

In addition, when a problem situation is given and a similar situation feature vector is detected in the plan database 610 after the problem situation feature vector is calculated, a plan for the similar situation feature vector is transmitted to the planner 630, It is appropriate to detect a similar situation feature vector that is the closest to the expected plan performance value when it is assumed that the plan performance value at the time of modification through the input of the problem situation feature vector is performed by the plan generator 220. Therefore, The plan database 610 preferably also includes a plan performance value for the situation feature vector along with the plan.

In this case, the plan performance refers to a performance value for an objective function of a resource allocation planning problem. For example, if the equipment operation rate maximization is set as an objective function of a resource allocation planning problem, the equipment operation rate becomes a plan performance value, If the minimization of the production time as the objective function of the planning problem is taken as the scheduling objective function, the production time value is the planned performance value.

FIG. 2 shows a data flow at the time of generating the plan database 610 according to an embodiment of the present invention. As shown in FIG. 2, when the problem situation generator 210 selects an appropriate selected problem situation and a problem situation feature vector for the problem condition is selected, the values are transmitted to the plan generator 220 so that the planning and planning performance Values are derived. In addition, as described above with respect to the problem situation feature vector, a plurality of situation feature vectors are constructed while changing the values slightly in consideration of the variability and the variation value based on various situations existing in the existing problem, The plan and plan performance values can be derived, so that the plan database 610 can be configured.

The plan database 610 may be configured to include the context feature vector and the plan for the context feature vector through the series of processes described above. In addition to the items included in the context feature vector, It is preferable that the plan database 610 includes the above-described problem situation.

In addition, although it is possible to create and use the plan database 610 as described above, the person in charge of resource allocation planning does not necessarily have to directly create the plan database 610. The plan database 610 may be produced separately and transferred to a person in charge or, in some cases, may be manufactured as a standard product, and partially modified in accordance with the environment.

After constructing the plan database 610 through the above-described series of processes, the planetary database 610 may be configured to calculate the derivative values of the contextual feature vector, generate a plan of the derived values, and include it in the plan database 610, It is also possible to configure the plan database 610 more finely.

When the context feature vector is generated as described above, it is also possible to use a context feature vector transformer 310 to calculate a derivative context feature vector. In generating the derivation condition feature vector, it is preferable to generate the derivation condition feature vector by considering the possibility of calculating a good plan with a minimum modification when calculating the plan through the plan corrector 630. For example, in the case of the production process, it is necessary to create a plan that slightly exceeds the production requirement threshold, and to revise the plan in the direction of reducing it. It can be advantageous to export. In this case, the situation feature vector dequantizer 310 preferably operates in a manner of deriving a production plan that slightly exceeds a reference value in calculating the derivative feature vector.

A plan for the derivative feature vector thus calculated may be generated and included in the plan database 610. At this time, the conventional plan generator 220 may be used, but in this case, the plan generation time may be too long Therefore, it is also possible to calculate a plan for the derivation feature vector by using the plan corrector 630 to be discussed below.

FIG. 3 shows a data flow when generating the plan database 610 including the derivation feature vector according to an embodiment of the present invention. As shown in FIG. 3, when the context feature vector is transferred to the context feature vector derivator 310, a derivation context feature vector for the context feature vector is derived, which is sent to the plan creator 630 along with the plan for the context feature vector To derive planning and planning performance values for the derivation context feature vector.

Next, a description will be given of the similar situation feature vector recommender 620 generation step (S120). Here, the similarity condition feature vector recommender 620 refers to the plan when the similarity condition feature vector in the plan database 610 is modified through the planner 630 so as to match the problem situation feature vector according to the problem situation From the plan database 610, a similarity feature vector closest to the expected plan performance value when the performance value assumes that the plan generator 220 is to be executed by inputting the problem situation feature vector.

The similarity condition feature vector recommender 620 can be realized by a conventional known machine learning technique such as a support vector machine or a k-nearest neighbor (k-NN), and specifically, The recommender 620 can be generated by using the pair of the situation feature vector and the derivation feature vector as independent variables, and using the performance value of each plan as a dependent variable, and using them as learning data. In addition, as discussed above, the context feature vector and its derivative context feature vector may be computed using the context feature vector generator 310, and the performance values of each plan for the context feature vector may be computed using a conventional plan generator It is possible to derive the similarity condition feature vector recommender 620 by using the fitness function generator 220 and the derivation feature vector by using the plan corrector 630. [

FIG. 4 illustrates a data flow when generating a similar situation feature vector recommender 620 according to an embodiment of the present invention. As can be seen from FIG. 4, by applying the machine learning technique to the situation feature vector and the derivative feature vector pair as independent variables, and using each plan performance value as a dependent variable, The recommender 620 can be generated.

Next, a description will be given of a step of receiving a problem situation (S130) and a step of calculating a problem situation feature vector (S140). According to an embodiment of the present invention, after receiving the problem situation from the resource allocation plan user, the problem situation feature vector is calculated by considering the characteristics of the problem situation with respect to the items having variable attributes from the problem situation.

At this time, the problem situation feature vector covers all the data necessary for defining the resource allocation problem, including the type of available resources, the number of available resources by type, the type of activity, the number of types of activity, Cost and time information related to the activity and detailed activities, the calculated plan, and the time and cost of the resource. Information such as information, plan performance value, objective function, and the like.

In particular, if the setting state of the resource among the items of the problem situation feature vector is examined, each resource may require a certain setting task for proper operation, and thus it may take a certain time to set and operate the resource. Therefore, depending on the setting state of the resource, the resource allocation task should be performed in consideration of the time delay in the case where the setting task must be preceded before being input to the specific sub-activity. Similarly, in the case of the restriction on the resource setting change, artificial or mechanical restriction may be applied to a specific setting task depending on a specific resource, so that it may be necessary to consider this in a resource allocation planning task.

Next, in the step of detecting the similar situation feature vector (S150), for the purpose of generating the plan for the problem situation feature vector, the detection of the similar situation feature vector for the plan to be used as the input of the plan creator 630 Assuming that the plan performance value when the plan of the situation feature vector in the plan database 610 is modified through the plan creator 630 is that the resource allocation plan generator 220 performs the problem situation feature vector input The similarity condition characteristic vector closest to the predicted plan performance value is detected by the schedule database 610. At this time, it is also possible to calculate the similar performance feature vector by using the saliency similar performance feature vector recommender 620.

In some cases, it is possible to search only a part of the context feature vectors included in the plan database 610 to detect the similar context feature vectors. For example, when the capacity of the plan database 610 is so large that it is inefficient to search all areas of the database, or when a correction operation is considered, only when the specific item is larger or smaller based on the problem situation feature vector, Or when it is appropriate to retrieve the data. For example, if the objective function is the maximization of the utilization rate in a given article production process, and if a production schedule for 100 tasks is to be derived, one is produced in a schedule for 101 tasks If it is easier to modify the schedule, and if the objective function is in compliance with the deadline, if you want to derive a production schedule using 100 machines, you can add a machine in the production schedule for 99 machines It is desirable to modify it. In this case, the scope of the search operation can be limited through a pre-filtering operation on the plan database 610. It is also possible to limit only the context feature vector to the search range in the plan database 610, excluding the derivation context feature vector.

In addition, when the likelihood feature vector is detected, if the probability of error calculated by a predetermined method exceeds a certain threshold value, the existing plan generator 220 may be used to detect the problem situation It is also possible to prevent the occurrence of errors by directly calculating the plan for

Finally, in step S160 of deriving a plan for the problem situation by modifying the plan for the similarity feature vector, the problem situation feature vector is considered together with the similarity feature vector and the plan for the similarity feature vector, The plan for the problem situation is derived by modifying the existing plan for the performance feature vector. At this time, the plan corrector 630 may be used to modify the plan for the similar performance feature vector.

The plan modifier 630 modifies the plan according to a method of minimizing the difference in plan performance from the existing plan due to the modification of the plan or maximizing the modified plan performance.

Similar to the case of the saliency similar situation feature vector recommender 620, by using the plans generated using the existing plan generator 220 for a plurality of context feature vectors as learning data, When a feature vector is given, an on-line learning, a support vector machine, and a support vector machine are generated so that the modification result of the plan creator 630 is similar to the plan generated by the existing plan generator 220. [ It is also possible to construct the plan corrector 630 by applying machine learning such as reinforcement learning. In addition, it is also possible that the plan corrector 630 calculates the planned performance value for the plan in addition to the corrected plan.

In addition, in the correction work of the plan, the plan correction work may be performed in consideration of only a part of the plan information to be used as the input, not the whole. For example, in the case of a scheduling problem, it is possible to configure the schedule modification operation to take into consideration only the operation sequence without considering the operation time. In this case, the plan database 610 may include only the work order information among the plan information.

In addition, when calculating a plan for a derivation condition feature vector derived from an arbitrary condition specifying vector by using the plan corrector 630, the plan database 610 may be provided with a plan It is also possible to record the number of corrections together and to detect the similar situation feature vector by referring to the number of plan corrections during the plan modification work by the plan corrector 630. [

FIG. 5 schematically shows a data flow at the time of plan calculation for a problem situation according to an embodiment of the present invention. 5, when the problem situation feature vector according to the problem situation is transferred to the similar situation feature vector recommender 620, the similar situation feature vector recommender 620 searches the plan database 610 , And the performance value after the plan correction operation using the correction generator 630 is the closest to the performance value of the plan derived from the case where it is assumed that the problem situation feature vector is input and the resource plan is directly generated using the plan generator And the likelihood feature vector corresponding to the plan are transmitted to the plan creator 630. The plan creator 630 together with the plan predictor 630 calculates the problem situation vector The plan will be calculated.

FIG. 6 shows a block diagram of a resource allocation planning system 600 using a plan search and modification technique in accordance with an embodiment of the present invention. 6, the planning system 600 using the schedule search and modification technique according to an embodiment of the present invention includes a plan database 610, a similar situation feature vector recommender 620, and a plan modifier 630 ). &Lt; / RTI &gt;

First, the plan database 610 according to an embodiment of the present invention calculates the problem situation feature vector for the appropriately selected problem situation and changes the values of the configuration items slightly, ) And the performance values of each plan and plan for the generated context feature vector. In addition to this, it is possible to manage the derivation feature vector made from the context feature vector and the performance values of the plan and the plan together.

Next, the similarity condition feature vector recommender 620, as described above, also obtains the performance closest to the performance value of the plan when the planner generator 220 is directly generated for the problem situation feature vector according to the given problem situation A similarity condition characteristic vector having a plan that can be calculated through the plan creator 630 is detected in the plan database 610 or a plan having the highest performance value is determined through the plan creator 630 A similar situation feature vector having a plan that can be calculated is detected in the plan database 610.

Then, the plan corrector 630 also revises the plan for the similar situation feature vector to derive a plan for the problem situation, as described above.

The foregoing description is merely illustrative of the technical idea of the present invention, and various changes and modifications may be made by those skilled in the art without departing from the essential characteristics of the present invention. Therefore, the embodiments described in the present invention are not intended to limit the technical spirit of the present invention but to illustrate the present invention. The scope of protection of the present invention should be construed according to the following claims, and all technical ideas within the scope of equivalents thereof should be construed as being included in the scope of the present invention.

210: Problem Situation Generator
220: Plan Generator
310: Situation Characteristic Vector Derivator
600: Resource allocation planning system using plan search and modification
610: Planning database
620: Similar situation feature vector recommender
630: Planner

Claims (31)

(a) generating a problem situation feature vector for a given problem situation;
(b) searching the planning database,
Detecting a similar situation feature vector for the problem situation feature vector and an already generated plan for the problem situation feature vector; And
(c) calculating a plan as a solution to the problem situation by modifying a preliminary plan for the similar situation feature vector,
Wherein a plurality of context feature vectors and pre-generated plans are stored and managed in the plan database. The method according to claim 1,
Prior to step (a)
(p) In order to generate and store plans for a plurality of context feature vectors in advance, various context feature vectors are input and a plan is generated using a separate planner,
Further comprising the step of generating the plan database. 3. The method of claim 2,
In the step (p)
In creating the plan database,
Characterized by using a representative value representative of the plurality of problem situations or clustering data of the plurality of problem situations to reduce the capacity of the plan database when a plurality of problem situations exist Planning method. 3. The method of claim 2,
In the step (p)
Wherein the planning database is generated in advance including a problem situation in which a problem situation changed from a previously existing problem situation to a predetermined reference value or more. The method according to claim 1,
The step (b)
Using a similar situation feature vector recommender,
Among the plans for the context feature vectors stored in the plan database,
A modified plan in which the plan is calculated through a plan modifier,
When the problem situation feature vector is compared through a plan generator,
Detecting similarity situation feature vectors that are expected to have the smallest difference in performance value for a given item and plans for them,
Wherein the performance value of the plan for the context feature vector is also stored and managed in the plan database. 6. The method of claim 5,
The step (b)
Using a similar situation feature vector recommender,
And detecting one or more context feature vectors most similar to the problem context feature vector in the plan database. The method according to claim 6,
Prior to step (b)
(q) For a plurality of context feature vectors and their plans,
And generating the similar situation feature vector recommender by applying a machine learning technique. The method of claim 7, wherein
Wherein the machine learning technique comprises a support vector machine or k-Nearest Neighbor (k-NN) technique. The method according to claim 1,
The step (b)
And to detect the similar situation feature vector by searching only some of the situation feature vectors in the plan database,
And filtering the context feature vectors of the plan database in advance. The method according to claim 1,
Wherein the plan database stores a plurality of context feature vectors and all of the plans previously generated using the plan generator with respect to the plurality of context feature vectors,
In the step (b)
Retrieves the context feature vector of the plan database,
All or some of the similar situation feature vectors for the problem situation feature vector and a plan for the similar situation feature vector are recommended from the similar situation feature vector recommender,
In the step (c)
Wherein the plan in the problem situation is generated by modifying all or part of the plan for the similar situation feature vector. The method according to claim 1,
The step (b)
The context feature vector and derivative feature vector of the plan database are retrieved,
Detecting a similar situation feature vector for the problem situation feature vector and a plan therefor using a similar situation feature vector recommender,
In addition to the plurality of context feature vectors and their plans,
A plurality of derivation feature vectors and a plan for the plurality of derivation feature vectors are stored and managed together. The method according to claim 1,
The step (c)
Using a planner,
A similarity situation feature vector, a plan previously generated using the similarity feature vector, and a problem situation feature vector,
And calculating a plan for the problem situation feature vector. 13. The method of claim 12,
The plan modifier comprises:
When the similar situation feature vector recommender recommends one or more similar situation feature vectors,
And a plan corresponding to each similar situation feature vector is modified to calculate a plan having the best plan performance value. 14. The method of claim 13,
The plan modifier comprises:
A plan that is obtained by modifying a plan generated beforehand for the similar situation feature vector so as to fit the problem situation feature vector and a case where it is assumed that a resource allocation plan is directly generated using the plan generator by inputting the problem situation feature vector Modifying the plan in a way that minimizes the performance gap with the plan,
Wherein the pre-generated plan is modified for the similar situation feature vector so that optimal performance can be achieved for the problem situation feature vector. 14. The method of claim 13,
The plan modifier comprises:
By using the plans generated by using the existing plan generator for a plurality of context feature vectors as learning data,
To simulate the existing plan generator of the planner,
Wherein the resource allocation is generated by applying machine learning. 16. The method of claim 15,
Wherein the machine learning techniques include on-line learning, support vector machines, and reinforcement learning techniques. 16. The method of claim 15,
When a plan modifier is used to generate a plan for the plurality of derivative feature vectors,
The planner database records and manages the number of plan corrections required when the planner modifies the plan of the similar situation feature vector,
And the plan correction frequency information is used later at the time of plan correction work by the plan corrector. The method according to claim 1,
The problem situation feature vector may include:
The type of resources available, the number of resources available, the type of activity, the number of activities by type, the pre-relationship between sub-activities in each activity type, the alternate resource, the alternate path, the priority between activities, Wherein the resource allocation information includes at least one of a constraint upon change, a setting state of resources, cost and time information related to activities and detailed activities, calculated plan information, plan performance value, and objective function. The method according to claim 6,
When the similar situation feature vector recommender detects the similar situation feature vector,
If the probability of error of the detected similarity feature vector exceeds a certain threshold value,
Wherein a plan for the problem situation is directly calculated using a separate plan generator without using a plan corrector. A plan database storing and managing plan and plan performance values generated using a plurality of situation feature vectors and a separate plan generator therefor;
After generating a problem situation feature vector from a given problem situation,
Searching the plan database to detect a situation feature vector most similar to the problem situation feature vector, or, from a plan for the context feature vectors stored in the plan database, And a similarity feature vector for deriving a similarity condition feature vector that is expected to have the smallest difference in performance value for a given item and the already generated plan for the given item when comparing the plan calculated through the plan generator, Recommendation period; And
And a plan modifier for modifying a plan for the one or more similar situation feature vectors to produce a plan as a solution to the given problem situation. 21. The method of claim 20,
The similarity condition feature vector recommender includes:
For a plurality of context feature vectors and their plans,
Wherein the resource allocation is generated by applying a machine learning technique. 21. The method of claim 20,
The plan modifier comprises:
Taking into account the problem situation feature vector, the similarity situation feature vector for it, and the plan for the similarity situation feature vector,
According to a method capable of minimizing the difference in the performance value from the plan derived when the modified plan according to the modification of the plan and the problem situation feature vector are input and the resource plan is directly generated using the plan generator Wherein the plan is modified. 23. The method of claim 22,
The plan modifier comprises:
By using the plans generated by using the existing plan generator for a plurality of context feature vectors as learning data,
Given an arbitrary problem situation feature vector,
In order for the modification result of the plan corrector to simulate the plan generated by the existing plan generator,
Wherein the resource allocation is generated by applying machine learning. 21. The method of claim 20,
Wherein the plan database comprises:
Wherein a plurality of problem situations are generated by using a representative value representative of the plurality of problem situations or by reducing the capacity of the plan database by clustering and using data of the plurality of problem situations Resource allocation planning system. 21. The method of claim 20,
Wherein the plan database comprises:
And a problem situation which is changed from a previously existing problem situation to a predetermined reference value or more. 21. The method of claim 20,
The similarity condition feature vector recommender includes:
And to detect the similar situation feature vector by searching only some of the situation feature vectors in the plan database,
Wherein the system is configured to filter the context feature vector of the plan database in advance. 21. The method of claim 20,
In the plan database, a plurality of context feature vectors and all or part of the plan information previously generated using the plan generator are stored and managed,
The similarity condition feature vector recommender includes:
Retrieves the context feature vector of the plan database,
Extracts all or a part of the similar situation feature vector for the problem situation feature vector and a plan for the similar situation feature vector,
The plan modifier comprises:
And generates a plan in the problem situation by modifying all or part of the plan for the similar situation feature vector. 21. The method of claim 20,
The similarity condition feature vector recommender includes:
The context feature vector and derivative feature vector of the plan database are retrieved,
Detecting a similar situation feature vector for the problem situation feature vector and a plan therefor,
In addition to the plurality of context feature vectors and their plans,
Wherein a plurality of derivation feature vectors and a plan thereof are stored together and managed. 29. The method of claim 28,
When a plan modifier is used to generate a plan for the plurality of derivative feature vectors,
The planning database also records and manages the number of plan modification times required when the plan modifier modifies the plan of the similar situation feature vector,
And the plan modification frequency information is used later in the plan modification work by the plan modification unit. 21. The method of claim 20,
The problem situation feature vector may include:
The type of resources available, the number of resources available, the type of activity, the number of activities by type, the pre-relationship between sub-activities in each activity type, the alternate resource, the alternate path, the priority between activities, Wherein the resource allocation planning system includes at least one of a constraint upon change, a setting state of resources, cost and time information related to activities and detailed activities, calculated plan information, plan performance values, and objective functions. 21. The method of claim 20,
In the similar situation feature vector recommender, when detecting the similar situation feature vector,
If the probability of error of the detected similarity feature vector exceeds a certain threshold value,
Wherein a plan for the problem situation is directly calculated by using a separate plan generator without using a plan corrector.

Images