JPH043227A - Allocating device - Google Patents

Abstract

PURPOSE:To efficiently create the better allocation state by constituting this device so that even in the case the condition of a temporary allocation state generated temporarily is equal to the condition of the original allocation state, it is regarded as the improvement of condition and the allocation state is updated and corrected. CONSTITUTION:A temporary allocation generating part 8a corrects tentatively a set allocation state 4, based on experiential knowledge 7 and generates repeatedly a temporary allocation state, updates and sets this temporary allocation state as a new allocation state, when it is considered that the condition of the temporary allocation state is improved, and also, generates repeatedly the temporary allocation state based on the experiential knowledge 7, based on this updated and set allocation state. In such a manner, while enhancing effectively the condition of the allocation state, the better allocation state can be derived efficiently.

Description

DETAILED DESCRIPTION OF THE INVENTION [Purpose of the Invention (Field of Industrial Application) The present invention provides an allocation system that can determine the allocation of jobs and resources efficiently and in a manner that provides the best allocation situation. Regarding equipment.

(Prior Art) It is necessary to allocate and set elements included in a set and elements included in another set under various circumstances, such as the assignment of jobs and resources, for example. In the past, this type of allocation setting was done through trial and error based solely on the experiential knowledge of experts such as administrators, but recently, the allocation process has been performed mechanically (automatically) according to predetermined allocation rules. Various attempts have been made to implement this. However, as the number of jobs and resources increases, the allocation process becomes extremely difficult and requires a large amount of time. Furthermore, as allocation rules and their constraints become more diverse, the above-mentioned allocation process is becoming increasingly difficult.

Therefore, recently, various attempts have been made to derive a better allocation situation by appropriately modifying the mechanically set allocation situation as described above by applying the experiential knowledge, that is, know-how, possessed by experts. For example, attempts have been made to evaluate whether or not the quality improves when the allocation status is modified according to know-how, and to execute the modification/change of the allocation status when it is confirmed that the quality improves.

In a device that corrects and changes the allocation situation by introducing the know-how of experts in this manner, it is possible to derive a better allocation situation relatively easily and in a short time.

However, in reality, it is difficult to guarantee that the allocation situation derived as described above is the best. In other words, in the conventional device, when the improvement in the quality of the modified allocation situation is no longer expected, the allocation situation required at that time is simply set as the best allocation situation.

For this reason, if the quality of the allocation situation cannot be expected to improve by modifying it, the allocation situation cannot be modified any further, and the possibility of other allocation situations cannot be confirmed. In other words, there is a problem in that the scope for changing the temporary allocation situation based on the current allocation situation is very narrow, and it is only possible to confirm the possibility of various allocation situations.

(Problem to be solved by the invention) In this way, in the conventional allocation device, even if the know-how of experts is introduced to correct the allocation situation, how much correction should be made to improve the situation? It is difficult to confirm whether the allocation status is obtained, and it is extremely difficult to efficiently obtain a better allocation status.

The present invention has been made in consideration of these circumstances, and its purpose is to provide a highly practical allocation device that can easily and efficiently set a better allocation situation. be.

[Structure of the invention]

(Means for Solving the Problems) The allocation device according to the present invention initializes the allocation status between the elements included in the first set and the elements included in the second set according to, for example, a predetermined allocation rule. , the set assignment status is temporarily changed based on empirical knowledge (expert know-how) to repeatedly create a temporary assignment status, and the quality of this temporarily created temporary assignment status is compared to the original one. When the allocation situation is deemed to be better than the current allocation situation, the provisional allocation situation is updated as a new allocation situation, and the provisional allocation situation is repeatedly created again based on this new allocation situation. It is characterized by being made to be able to

In particular, even if the quality of the temporarily determined provisional allocation status is equivalent to the quality of the original allocation status, the allocation status will be updated sequentially by starting the process to update the allocation status. It is characterized by the fact that

(Function) According to the present invention, temporary allocation situations are repeatedly created by temporarily modifying the set allocation situation based on empirical knowledge, and the quality of the provisional allocation situation is deemed to have improved. This provisional assignment status is updated as a new assignment status when the assignment status is updated, and the provisional assignment status is repeatedly created based on the above-mentioned empirical knowledge based on this updated assignment status. It becomes possible to efficiently seek a better allocation situation while effectively increasing the quality.

In other words, if temporary assignment situations are repeatedly created based on empirical knowledge and the temporarily created temporary assignment situation is deemed to be better than the original assignment situation, then Since the above-mentioned generation of the temporary allocation status is repeated while updating the created temporary allocation status as a new allocation status, it is expected that the quality of the temporarily generated temporary allocation status will be temporarily improved. Even if such a case occurs, it is possible to effectively derive a better allocation situation in the end.

(Embodiment) Hereinafter, an allocation device according to an embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a schematic diagram of the configuration of the apparatus of the embodiment, where ■ is a job database and 2 is a resource database. This embodiment apparatus allocates and sets a plurality of jobs stored in the job database 1 and a plurality of resources stored in the resource database 2 so as to satisfy predetermined allocation conditions (rules).

For example, the allocation processing unit 3 sequentially obtains resources that can be allocated to jobs sequentially read out from the job database 1 from the resource database 2 so as to satisfy a predetermined allocation rule, and initializes the allocation status between jobs and resources. do.

The allocation processing in the allocation processing unit 3 is performed, for example, at
This is done by appropriately adopting various algorithms that have been proposed in the past, such as using the IFIFo method to allocate resources in order of priority.

The assignment status initialized in this manner is stored in the assignment status storage unit 4 on the day of the first day, and the evaluation device 5 evaluates the goodness of the assignment status. The goodness of this allocation situation is that
For example, the evaluation is performed using the constraint time of the resources allocated to the job as the evaluation value, but it is of course also possible to evaluate the goodness of the allocation situation using the remaining resource status and other conditions as the evaluation value. The goodness (evaluation value) of the allocation situation determined by the evaluation device 5 is determined by the goodness of the allocation situation in the goodness storage unit 4 corresponding to the allocation situation stored in the allocation situation storage unit 4.
is stored in

Note that the allocation processing unit 3 may generate a plurality of the above-mentioned job and resource allocation situations.

In such a case, the goodness of each of the plurality of generated allocation situations is evaluated. Then, the evaluation values for each of these allocation situations are compared with each other, and the allocation situation with the best evaluation value among them is initially set as the allocation situation determined according to a predetermined allocation rule.

The feature of this device that initializes the allocation status between jobs and resources in this way is that the allocation process is performed as described above in accordance with the know-how that is the experiential knowledge of various experts accumulated in the know-how database 7. The present invention is equipped with an improvement device 8 for correcting and changing the assignment status between jobs and resources initialized in section 3, and sequentially seeking better assignment status while temporarily generating a temporary assignment status. It is in.

That is, this improvement device 8 uses the know-how database 6 for the allocation situation determined by the allocation processing section 3.
A temporary allocation situation creation section 8a is provided which applies the expert's know-how stored in the storage system to make changes and corrections to the allocation situation to temporarily create a temporary allocation situation. This temporarily created temporary allocation status is stored in the temporary storage section 8b.
The evaluation device 5 evaluates the goodness of the allocation situation, and the evaluation result is stored in the goodness storage section 8c.

Therefore, the comparison judgment unit 8d uses the evaluation value of the provisional allocation status temporarily generated as described above and the allocation processing unit 3.
The evaluation value of the goodness of the allocation situation, which was obtained in According to the judgment result of the comparison judgment section 8e, for example, when it is deemed that the temporarily set provisional allocation situation is better, the allocation situation updating section 8d is activated and the allocation processing section 3 The set allocation status is updated and changed to the above-mentioned temporary allocation status.

The improvement device 8 repeatedly creates such a temporary allocation situation and evaluates the quality of the allocation situation,
Each time a provisional allocation situation that is expected to improve in quality is obtained,
The allocation status is sequentially updated using this temporary allocation status.

Note that this updating of the allocation status is also performed when the quality of the temporarily obtained provisional allocation status is equivalent to the quality of the original allocation status that is the basis for the modification. By updating the allocation status in this way, the allocation status is successively updated so that there is always a higher possibility of obtaining a better allocation status.

FIG. 2 schematically shows the flow of the procedure for changing the allocation status executed by the improvement device 8 in this manner. As shown in FIG. 2, in the improvement device 8, the allocation status initialized by the allocation processing unit 3 according to a predetermined allocation rule is inputted (step a), and this allocation status is temporarily stored (step b). Then, after evaluating the goodness of the allocation situation stored at this time (step C), the above-mentioned allocation situation is temporarily modified by applying the know-how 11 to the allocation situation, and a temporary temporary Create an allocation status (step d). After storing the temporary allocation situation created in this way as a temporary allocation result (step e), the quality of this temporary allocation situation is similarly evaluated (step f). .

After evaluating the quality of the initially set allocation situation as described in step 2 and the quality of the temporary allocation situation created by applying know-how to this allocation situation, these evaluation values are compared with each other. and examine how the goodness of the allocation situation has changed (step g). As a result of this comparison process,
For example, when the temporarily created temporary allocation situation becomes better, or when the quality is the same, the temporary allocation situation is stored in the storage unit as a new allocation situation. The allocation status is updated and changed (step h). Note that if the quality of the provisional allocation status is worse than the quality of the original allocation status, the allocation status is not updated.

By repeatedly creating such a provisional allocation status and updating the allocation status based on the judgment result of the quality of the allocation status, a better allocation status can be achieved by gradually increasing the quality of the allocation status. You will be asked for it.

The process of changing the allocation status based on such know-how will be explained using a specific example. Figure 3 shows the assumption of the allocation process when assigning jobs 1, 2 to 6 to three trucks A, B, and C. ,B.

C schematically shows the initial allocation situation when the tasks are mechanically allocated in order from earliest to earliest.

In this case, the quality of the allocation situation is evaluated as, for example, the total time each truck is restricted by the work assigned to each truck. In this example, the restraint time of truck A is determined to be r6J, the restraint time of truck B is r4J, the restraint time of truck C is "4", and the total time is "14".

The smaller the evaluation value indicated by this total time, the better the allocation situation is evaluated.

Correcting and changing the assignment status determined in this way based on the know-how of experts is carried out by applying the knowledge of, for example, interchanging work assigned to different tracks. . Specifically, by applying this knowledge and exchanging work 4.5 between truck A and truck B, the temporary assignment situation temporarily created by this is shown in Figure 3 (b). ). However, the goodness of the provisional allocation situation changed and corrected in this way is that the detention time of truck A is r5J,
) Since the restraint time of rack B is calculated as "5J", the restraint time of truck C is "4", and the total time is "14", the quality is equivalent to the original allocation situation, and the allocation The effect of the modification has not appeared.

Conventionally, when such a situation occurs, the allocation change is given up and another allocation change is attempted to find an allocation situation that improves the quality of the allocation. If an allocation situation that can improve the quality of the allocation situation cannot be obtained, the allocation correction is stopped at that point, and the best allocation situation among the allocation situations sought so far is used as the final allocation situation. As a result of the assignment.

However, in this device, if the quality of the temporarily created temporary allocation situation is equivalent to the quality of the original allocation situation, as described above, this temporarily obtained temporary allocation situation is used as the new allocation situation. It is set to be updated as follows. Based on this new allocation situation, the allocation correction based on the above-mentioned know-how is then repeated.

By setting the update of the allocation status in this way, for example, in this example, as shown in FIG. Jobs 3 and 5 can be swapped between jobs. As a result, the goodness of the temporary allocation situation shown in FIG. 3(C) is that the restricted time of truck A is r4J, the restricted time of truck B is r5J, the restricted time of truck C is "2", and the total The time will be determined as "11" and its goodness will be increased compared to the original allocation situation. As a result, this temporary allocation situation can be obtained as a better allocation result.

In other words, in this device, if the quality of the allocation does not improve even if the quality of the allocation status is changed or modified to improve its quality, in other words, even if the quality is the same, the original allocation status is temporarily used as a temporary allocation status. The update settings are to be set at .

As a result, the range of allocation situations that can be changed and corrected by applying the expert's know-how increases, making it possible to efficiently search for better allocation situations.

Further, in the example shown in FIG. 4, a plurality of buses A,
B and C exist, and their job is overnight job 1.
,2. 7 is present. Figure 4(a)
The jobs 1, 2, etc. mentioned above are sent to buses A, B, and C. This shows an example of assigning jobs 7 to 7 in order, and job 7 requires bus A.
This indicates an overflow situation (unallocated).

If we apply expert know-how to such an assignment situation and replace jobs 1 and 2 assigned to buses A and B, the temporary assignment status will be as shown in Figure 4 (b).
). However, in this hypothetical allocation situation,
After all, work 7 cannot be assigned to bus A, and its quality is the same as the original assignment situation. However, even under such circumstances, this device updates the original allocation status with a temporary provisional allocation status as described above, and reapplies the know-how based on this updated allocation status. This is an attempt to correct the allocation.

As a result, under the assignment situation shown in Figure 4(a), job 7
Even though it was completely impossible to allocate bus A to bus A, the allocation status has been modified as shown in Figure 4 (b). For example, as shown in Figure 4 (C), It becomes possible to correct the assignment status, effectively assign job 7 to bus A, and eliminate unassigned jobs.

In this way, this device applies experts' know-how to the initial allocation situation according to predetermined allocation rules and changes the allocation to improve its quality. Even if the quality of the provisional allocation status is equivalent to the original allocation status, the original allocation status will be updated based on the allocation status of the board.

As a result, it becomes possible to effectively expand the range of changes in the allocation situation that can be modified by applying know-how, and effectively seek a better allocation situation. Therefore, even when the number of jobs and resources to be allocated increases, it is possible to proceed with the allocation process very easily and efficiently, and to effectively obtain a better allocation status. Many practical effects can be achieved.

Note that the present invention is not limited to the embodiments described above. For example, the number of jobs and resources to be subjected to allocation processing and the allocation rules (conditions) are set depending on the allocation problem. Furthermore, the algorithm for initially setting the allocation status by processing these allocations can be modified in various ways. Furthermore, the modification of assignments based on know-how is not limited to the above-mentioned job replacement. Furthermore, for the evaluation of the allocation status, elements such as time information, amount (necessary expenses), etc. can be adopted.

In addition, the present invention can be implemented with various modifications without departing from the gist thereof.

[Effects of the Invention] As explained above, according to the present invention, temporarily created temporary Even in cases where the quality of the allocation status is equivalent to the quality of the original allocation status, this is regarded as an improvement in the quality and the allocation status is updated and corrected. As a result,
It greatly expands the range of changes in allocation correction, making it extremely easy and -
It is important to efficiently derive a better allocation situation.
It can bring about great practical effects, such as increased performance.

[Brief explanation of the drawing]

FIG. 1 is a schematic configuration diagram of an allocation device according to an embodiment of the present invention, FIG. 2 is a diagram schematically showing the flow of allocation status change processing in the embodiment device, and FIGS. 3 and 4 are FIG. 6 is a diagram schematically showing the allocation status and the process of changing the allocation status. DESCRIPTION OF SYMBOLS 1... Job database, 2... Resource database, 3... Allocation processing unit, 4... Allocation status storage unit, 5... Evaluation device, B... Goodness storage unit, 7...
・I U-how database, 8...Improved equipment, 8a...
-Temporary allocation status creation unit, 8b...temporary storage unit,
8c...Goodness storage section, 8e...Comparison judgment section, 8d.
...Status update department.

Claims (3)

[Claims] (1) In the allocation device that allocates and determines the elements included in the first set and the elements included in the second set, there is an evaluation device that evaluates the goodness of the allocation situation, and an evaluation device that changes the allocation situation based on empirical knowledge. and a means for temporarily setting a temporary allocation situation, and repeatedly generates temporary allocation situations, and determines that the quality of the temporarily generated temporary allocation situation is better than the original allocation situation. When the provisional allocation situation is considered, the temporarily set temporary allocation situation is updated as a new allocation situation, and the provisional allocation situation is repeatedly generated based on the updated allocation situation. Featured allocation device. (2) The allocation status is obtained by initializing the allocation status of elements included in the first set and elements included in the second set according to a predetermined allocation rule. The allocation device according to 1). (3) The update allocation status setting is activated even if the temporarily set provisional allocation status is equivalent to the original allocation status, assuming that the allocation status has improved. The allocation device according to claim 1, characterized in that: