JP2000040099A - Schedule creation apparatus and method, job selection method, and recording medium recording schedule creation software - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To provide a scheduling technique that directly reflects a user's intention. SOLUTION: A comparison condition data D3 is a comparison condition for comparing jobs, that is, a comparison key which is used as a comparison key with which and which attribute values among a plurality of attribute values exist for each job. And an equivalence condition for at least one of the keys. Job selection unit 3
Is a selection means for selecting, based on a comparison key, a job to be assigned to a resource next from jobs to be selected, that is, jobs not yet assigned to a resource. Selects a job to be assigned based on the next priority comparison key from among the plurality of jobs when there are a plurality of jobs satisfying a predetermined equivalence condition for the comparison key.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an improvement in a technique for creating a schedule using a computer, and more specifically, to a flexible scheduling that directly reflects a user's intention. is there.

[0002]

2. Description of the Related Art In various fields of planning such as production planning, project planning, and timetable preparation, a technique of creating a schedule using a computer is used. Scheduling, also called scheduling, refers to assigning a job to a resource so as to satisfy a given condition. Here, a job is an object to be scheduled, and is a unit of work to be performed, such as each step of the work. The resource is an object to which a job is assigned, and is a resource necessary for processing a job like individual production equipment or personnel.

In scheduling, it is necessary to select appropriate jobs and assign them to appropriate resources one after another so as to satisfy given conditions. For example, when processing several production facilities and a plurality of jobs each with a fixed delivery date, if a long-running job is biased to some production facilities, the delivery deadline will break, and at a certain production facility, If a job that cannot be started until a certain time later is allocated after processing a job that has been completed, wasteful free time increases.

That is, in general, a job is set with a condition that, for example, it cannot be started until a certain time or must be completed by a certain delivery date, that is, a period in which the job can be allocated. On the other hand, there are a plurality of resources that can process the same job, that is, a plurality of resources that can be allocated, and some resources that can be allocated from the viewpoint of a certain job are called “alternative resources”. And
Of the allocatable periods set for a job, the time at which the job can be started earliest is called the “earliest start time”, and the latest end time allowed for the job is called the “latest end time”.

[0005] A period in which a job assigned to a resource uses the resource is referred to as "work time", and a time obtained by subtracting the work time from a period from the earliest start time to the latest end time is referred to as "margin time". . A state in which a job is not yet allocated to a resource is referred to as “unallocated”, and a state in which the end time of the allocated job is later than the latest end time is “delivery deadline”, and the end time of the job from the latest end time. The period up to is called "delivery delay". Further, in a state where scheduling is completed, a period from the end time of a certain job to the start time of the next assigned job is referred to as “free time”.

Here, there are several methods of performing scheduling, and one of them will be described on the premise of each term as described above. For example, in the initial state, nothing is assigned to a resource, and all jobs are unassigned. One job is selected from such unassigned jobs, the resource to be assigned is determined from the alternative resources, and the selected job is assigned to the resource. Then, scheduling is performed by repeating such a series of processing of job selection and allocation, and the scheduling is terminated when a predetermined termination condition is satisfied.

In such scheduling, when a job to be assigned next is selected from a plurality of unassigned jobs, the unassigned jobs are compared with each other using the attribute value of the job as a comparison key, and You need to choose the best job.

For example, when each job has an attribute value such as the earliest start time and the spare time, first, the earliest start time is used as a comparison key, and the job with the earliest start time is selected. If there are a plurality of jobs whose earliest start times are exactly the same, the margin time of those jobs is set to the second time.
The jobs are compared with each other as a comparison key of, and the job with the shorter margin time is selected and assigned to the resource.

Here, there is a close relationship between the priority of applying some comparison keys and the result of scheduling. For example, when selecting one job from unassigned jobs, select the job with the earliest start time, and assign the resource to the earliest assignable resource within the assignable time at the earliest time. If this is done, the idle time of the resource will generally decrease and the operating rate will increase. In addition, for example, a time for setup (setup time) may be required at the time of job switching. In this case, selecting a job with the shortest setup time increases the operating rate.

[0010]

However, in the above-described conventional scheduling technique, the priority order from which comparison key is used for job comparison is fixed. There was a problem that the scheduling result was offset. Here, a specific example of the conventional scheduling will be described. In this example, the number of jobs assigned to each resource at the same time is limited to one, and the job is not divided or assigned to a plurality of resources.

First, as a first example, "earliest start time" is used as a first comparison key for selecting a job to be allocated.
In the “earliest order”, and as the second comparison key, select the jobs in the “smallest order” of the “time to spare” and assign the selected jobs to resources to schedule. The case of performing the operation will be described. In this case, the general procedure of scheduling is as follows. (1) In the initial state, all jobs are unassigned. (2) Select the job with the earliest start time from the unassigned jobs. At this time, if there are a plurality of jobs having the same earliest start time, a job having a short margin time is selected. If there are no unassigned jobs, the scheduling ends.

(3) Allocate the selected job to a resource. Specifically, select a resource to which the job can be assigned at the earliest time among the alternative resources,
Assign at the earliest time. If there are a plurality of resources having the same condition as the allocation destination, the resource specified first is selected, for example, in ascending order of the ID numbers of the resources. After the assignment is completed, the process returns to (2) and the process is repeated.

Here, a specific procedure for performing scheduling by applying such a procedure to the job data shown in FIG. 4 and the resource data shown in FIG. 5 will be described. In this case, when the scheduling is just started, all the jobs have not been allocated as described in the procedure (1). Next, a job is selected according to the above procedure (2).

That is, in the job data shown in FIG.
The jobs with the earliest start times are J-01 and J-02. According to the above procedure (2), J-02 having a short margin time is selected. The job J-02 thus selected is allocated to the resource according to the above procedure (3). Regarding the resource to which the job J-02 is assigned, there are M2 and M3 as alternative resources of J-02, and when the period is expressed by date, both can be assigned from 4/1. In such a case, it is allocated to M2 previously specified as a substitute resource.

As a result, the work time of job J-02 is 3
Therefore, the resource M2 is 4/1 as shown in FIG.
To 4/3 will be used for job J-02. As a result of such assignment, job J-02 is no longer unassigned, and the process returns to procedure (2) described above.

Subsequently, when a job is selected in the same manner from the remaining unassigned jobs, the job J-01 is selected this time. As alternative resources to which this job J-01 can be assigned, there are resources M1 and M2, of which the job J-02 has already been assigned to resource M2 in the previous process. Therefore, the resource M
Regarding 2, the time at which the current job J-01 can be allocated is from 4/3.

On the other hand, resource M1 can be allocated from 4/1. In this case, the resource M1 is selected as a resource that can be allocated at an earlier time, and the job J-0
1 is allocated to the period from 4/1 to 4/5 of the resource M1. Thereafter, by repeating the selection and assignment of jobs in the same manner, the schedule shown in FIG. 13 is finally obtained. In the schedule obtained in this way, the total free time is two days, but the total delay in delivery of all jobs is 37 days.

In the scheduling example described above, a job is selected as a first comparison key in the order of “earliest start time” and “early”, and as a second comparison key, a job is selected in the order of “smallest time” and “smallest”. Then, as a second example,
The first comparison key and the second comparison key are exchanged, and the first comparison key is set in the order of “smallest time” and the second comparison key is set the “earliest start time” in the “early order”. An example will be described in which scheduling is performed by selecting.

In the second example, in the initial state where processing has just started, all jobs are unassigned as described in the above procedure (1). This is the same as the first example described above. Is the same. However, in the next procedure (2), a comparison key opposite to that in the first example is used, so that the job J-03 having a short margin time is selected from the unassigned jobs. This J-
The alternative resources to which 03 can be assigned are resources M1 and M3, and both of these resources M1 and M3 can be assigned a job from 4/2. For this reason, among these resources M1 and M3, the resource M1 previously specified as the substitute resource is selected as the resource to which the job J-03 is allocated. FIG. 6 shows the result of assigning job J-03 to this resource M1.

In the second example, the job selected next is the job J-02 among the unallocated jobs, and the alternative resources to which the job J-02 can be allocated are the resources M2 and M3. Then, of these two alternative resources M2 and M3, the job J-02 is allocated to the resource M2 that can place the job earlier. Thereafter, similarly, according to the priority order of the comparison key different from that of the first example, the jobs are selected and assigned from the jobs having a short margin time, and the schedule is created.

As described above, contrary to the first example, when the spare time is the same, the job with the earliest start time is selected and assigned to the resource. In the second example, the total of the delivery delay is one day, but the total of the idle time is 22 days.

As is apparent from a comparison of the result with the above-described first example, in the first example in which the earliest start time is used as the first comparison key, the idle time is reduced, but the delivery delay is very short. On the other hand, on the other hand, the second using the spare time as the first comparison key
In the example, the delivery delay is reduced but the vacant time is greatly increased, so that both the delivery delay and the vacant time cannot be reduced appropriately. As described above, in the prior art, while performing the scheduling process, the order of the comparison keys is fixed to a consistent order throughout the job selection, so that it is difficult to obtain a well-balanced schedule from a plurality of criteria. Met.

As for the selection of a job in the scheduling, in the scheduling using fuzzy inference (Japanese Patent Laid-Open No. Hei 8-118210), a plurality of attributes of the job are inputted, and the priority for selecting the job is determined by fuzzy inference. In addition, a technique has been proposed in which a job is selected based on the selection, thereby performing selection in consideration of a plurality of attributes.

However, even when such a technique is used, not only is it difficult to adjust membership functions and parameters used for inference, but also the priority order of comparison keys is predetermined and can be dynamically changed according to the situation. Therefore, there is a problem that the user's intention cannot be directly reflected in the scheduling procedure or the result.

That is, even if such a fuzzy inference is used, a method of considering a plurality of attributes and a fixed balance are fixed.
It has not been possible to realize flexible priority processing based on a non-linear evaluation criterion such as giving priority to a job with a short margin time on a day. Also, even with such a method using fuzzy, priorities are fixed for all jobs before allocation, so that the priorities cannot be changed according to an intermediate scheduling situation such as resource load. There was a problem.

The present invention has been proposed to solve the above-mentioned problems of the prior art, and an object of the present invention is to provide a scheduling technique which directly reflects a user's intention. Another object of the present invention is to
An object of the present invention is to provide a technique for performing flexible scheduling by dynamically changing the priority according to a situation.

[0027]

According to one aspect of the present invention, there is provided a schedule creation apparatus for creating a schedule by assigning a plurality of jobs to a plurality of resources. Means for selecting which job is to be assigned next, based on the comparison key, and means for allocating the selected job to one of the resources. When there are a plurality of jobs that satisfy the condition, a job to be assigned is selected from the plurality of jobs based on the next priority comparison key. The invention of claim 7 is the invention of claim 1
In the schedule creation method of creating a schedule by assigning a plurality of jobs to a plurality of resources, based on a plurality of comparison keys having different priorities, which job A step of selecting to assign or select, and a step of assigning the selected job to any resource, wherein the selecting step includes: when there are a plurality of jobs satisfying a predetermined equivalence condition for the comparison key,
The job to be assigned is selected from the plurality of jobs based on the next priority comparison key. A tenth aspect of the present invention captures the first and seventh aspects of the present invention from the viewpoint of a recording medium on which a computer program is recorded, and assigns a plurality of jobs to a plurality of resources using a computer to schedule. On a recording medium on which schedule creation software to be created is recorded, the software causes the computer to select which job to assign next based on a plurality of comparison keys having different priorities, and to select one of the selected jobs. In the selection of the job, when there are a plurality of jobs satisfying a predetermined equivalence condition for a comparison key, a job to be assigned is selected from the plurality of jobs based on a comparison key of the next priority. It is characterized by making it. According to a sixth aspect of the present invention, there is provided a job selecting method for selecting which of a plurality of jobs is to be assigned to a resource for scheduling using a value relating to the job as a comparison key, wherein the same value is used even if the comparison key has a different value. It is characterized in that an equivalence condition for determining that the condition is satisfied is determined. Claims 1, 7, 1
In the inventions of Nos. 0 and 6, a range of a difference that can be identified is set as an equivalence condition for each comparison key for selecting a job. Then, as a result of comparison using a comparison key having a certain priority, jobs having a smaller difference so as to satisfy the equivalent condition are selected by the comparison key having the next priority.
Flexible scheduling is realized. In addition, by setting as an equivalence condition how much difference can be identified for each comparison key, the intention of the user is directly reflected in the scheduling. For example, if the first comparison key is the earliest start time and the equivalence condition is
"Within" and the second comparison key as a margin time. Earlier start time difference is 3 when comparing two jobs
If it is larger, the job with the earliest start time is selected,
If the earliest start time difference is less than three, it is regarded as having the same value under the same value condition, and the next comparison key, that is, a job with a short margin time, is selected. This enables flexible scheduling that directly reflects the user's intention.

According to a fourth aspect of the present invention, in the schedule creation device according to any one of the first to third aspects, resource data indicating what kind of resources are present and what kind of job is to be assigned are Using job data represented by a plurality of attribute values corresponding to each job and comparison condition data representing a comparison condition when sequentially selecting a job to be assigned to a resource, the comparison condition data is one of the plurality of attribute values. It is characterized by indicating which priority is used as the comparison key, and an equivalence condition for at least one of the comparison keys. In the invention of claim 4,
A comparison condition for which of the attribute values possessed by the job as which comparison key, and under which conditions the comparison key can be used to select the job with the next priority comparison key It can be easily controlled by rewriting the data. Therefore, it is easy to reflect the user's intention in the scheduling and to apply the present invention to various fields.

According to a fifth aspect of the present invention, in the schedule creation apparatus according to any one of the first to fourth aspects, the comparison key is an earliest start time and a latest end time of each job. And The invention of claim 5 is
Since the earliest start time related to when execution of the job is possible and the latest end time directly related to the delivery date are used as comparison keys, it can be effectively applied to many fields related to scheduling.

According to a second aspect of the present invention, in the schedule creation device of the first aspect, the equivalence condition is set based on a value that changes according to which job is assigned to which resource. And According to an eighth aspect of the present invention, the invention of the second aspect is viewed from the viewpoint of a method. In the schedule creation method according to the sixth or seventh aspect, the method changes according to which job is assigned to which resource. The equivalence condition is set based on a value. According to the second and eighth aspects of the present invention, since the equivalence condition can be set using a value that cannot be determined unless the scheduling progresses halfway, more flexible scheduling can be performed according to the scheduling situation. For example, since the setup time between two jobs changes in accordance with the combination of the types of two consecutive jobs, the end times of those jobs also change accordingly. According to the second and eighth aspects of the present invention, the equivalence condition can be set based on the time interval between the end time that fluctuates in this way and the earliest start time of each candidate job.

According to a third aspect of the present invention, in the schedule creation device according to the first or second aspect, when there are a plurality of comparison keys, the selecting means selects a job satisfying an equivalence condition for a first comparison key, and selects a second job. When a job is selected based on a subsequent comparison key, a job is selected based on a comparison key having the next priority from among jobs satisfying the same condition with respect to the immediately preceding comparison key. . The ninth aspect of the present invention captures the invention of the third aspect from the viewpoint of a method.
In the schedule creation method according to any one of the first to third aspects, when there are a plurality of comparison keys, selecting a job that satisfies an equivalence condition for a first comparison key, and selecting a job based on a second or later comparison key. In addition, a job is selected based on a comparison key having the next priority from among jobs that satisfy the same condition with respect to the immediately preceding comparison key. According to the third and ninth aspects of the present invention, when an optimum job is sequentially selected by using a plurality of comparison keys, only the jobs that fall within the range of the equivalent condition based on the comparison key of the immediately preceding priority are set next. It is a candidate to be compared with the comparison key. For this reason,
As a result of selecting the optimum jobs one after another based on the individual comparison keys, it is possible to avoid the problem that, in the case of the first comparison key, a job far from the optimum one is finally selected. The “optimal job” differs according to the content and format of the comparison key. For example, the job corresponding to the minimum value when the comparison key is an ascending numerical value, and the job corresponding to the maximum value when the comparison key is a descending numerical value is the optimum job.

[0032]

Embodiments of the present invention (hereinafter referred to as "embodiments") will be described below with reference to the drawings. It is generally considered that the present invention is realized by controlling a computer having a peripheral device by software. In this case, the software is created by combining the instructions according to the description in this specification, and the common parts with the above-described prior art use the technique described in the prior art. Further, the software includes not only program codes but also data prepared in advance for use in executing the program codes.

[1. First Embodiment] [1-1. Configuration of First Embodiment] FIG. 1 is a functional block diagram showing a configuration of a first embodiment of the present invention.
This conceptually shows that the operation of the software S as described above is realized by the computer C. That is, the computer C includes a CPU (C1),
It includes hardware such as a main memory C2 using a RAM, an auxiliary storage device C3 such as a hard disk device, an input device C4 such as a keyboard and a mouse, and an output device C5 such as a CRT display and a printer. Such software S realizes the operational effects of the present invention by utilizing physical resources such as hardware.

However, the specific software and hardware configuration for realizing the present invention can be variously changed. For example, software formats include compilers,
There are various types of interpreters, assemblers, etc., and for exchanging information with the outside, various types of removable recording media, such as floppy disks, and network connection devices are also conceivable. Further, a recording medium such as a CD-ROM in which software or a program for realizing the present invention is recorded,
Alone is also one embodiment of the present invention. Further, a part of the functions of the present invention can be realized by a physical electronic circuit such as an LSI.

As described above, various modes for realizing the present invention using a computer can be considered. In the following, the present invention will be described using virtual circuit blocks for realizing individual functions included in the present invention and the embodiments. The invention and embodiments will be described.

That is, the first embodiment is a schedule creation device that creates a schedule by assigning a plurality of jobs to a plurality of resources. In the software S according to the first embodiment, what kind of job is to be scheduled Yes and what resources are provided are given as job data D1 and resource data D2, respectively.

The job data D1 holds attribute data such as name, substitute resource, earliest start time, latest end time, and work time for each job. The resource data D2 holds data on resources, such as the capabilities of each resource, the operating time, and the assigned job. Also, the first
In the embodiment, when the next job to be assigned to the resource is selected, which attribute of the job is used as a comparison key to compare the jobs is given as comparison condition data D3.

The comparison condition data includes a comparison condition for performing job comparison, that is, which attribute value exists for each job, which attribute is to be used as a comparison key, and a comparison key. And an equivalence condition for at least one of the following. Here, the equivalence condition is a condition for regarding the comparison key to be regarded as the same value even if the attribute values of the job are different.

The software S has an equivalence condition setting unit 1, a priority comparison unit 2, a job selection unit 3, and a schedule processing unit 4. The equivalence condition setting section 1 is a section that is set by inputting comparison condition data D3. The priority comparing unit 2 is a part that determines the order in which the individual comparison keys are used as criteria for selecting a job by comparing the priorities of a plurality of comparison keys included in the comparison condition data D3 with each other.

The job selecting section 3 selects, from the jobs to be selected, that is, the jobs not yet assigned to the resources, which job is to be assigned to the resource next, based on the comparison key. When there are a plurality of jobs satisfying a predetermined equivalence condition with respect to the comparison key, the job selection unit selects a job to be assigned from the plurality of jobs based on the next priority comparison key. Is configured.

The schedule processing section 4 is a means for creating a scheduling by performing a process of allocating the selected job to any resource. The comparison keys in the first embodiment are the earliest start time and the latest end time of each job.

[1-2. Operation of the First Embodiment] The first embodiment having the above-described configuration operates as follows. [1-2-1. Procedure of Entire Scheduling] In the first embodiment, a job is selected using the comparison key and the equivalent condition represented in the comparison condition data. Such a job selection is performed by the following overall scheduling. This is done as part of the procedure. That is, the general procedure for creating a scheduling is as follows. (1) First, the user sets the job data D1 and the resource data D2 by using the input device C4 or the like. Similarly, the comparison condition data D3 is set through the equivalence condition setting unit 1. (2) Then, the job selection unit 3 selects one job from the jobs to be selected. Note that if there are no more selectable jobs at this time, all the jobs have been allocated to resources, and the scheduling ends. (3) Subsequently, the scheduling processing unit 4 determines a resource to which the selected job is to be allocated, allocates the job to the determined resource, and returns to the above-described job selection in (2).

It is to be noted that the schedule processing section 4 can freely assign the selected job to which resource by any method or reference. For example, in the case of so-called pile-up or hill-side scheduling, the entire procedure is as follows. Become like (1) First, all jobs are temporarily assigned to each resource without considering the capacity of each resource. (2) Next, the job selection unit 3 selects one job from the jobs allocated to the resource capacity or more. If there are no more selectable jobs at this time, all the jobs are within the capacity of the resource, and the scheduling ends. (3) Then, the scheduling processing unit 4 moves the selected job to a time that does not exceed the capacity of the resource, and returns to the job selection in (2) described above.

As described above, the present embodiment is particularly characterized in selecting a job, and the selected job may be processed in any manner and in any manner to create a schedule. Therefore, the operation of this embodiment and other embodiments will be described below with emphasis on job selection by the job selection unit 3.

[1-2-2. Job Selection Procedure] That is, the data of the job to be selected from the job data D1 is input to the job selection unit 3, and the priority order among the comparison key and the equivalent condition included in the comparison condition data D3 Passed in descending order. Then, at each time point, the job selection unit 3 takes out two remaining jobs to be selected, compares them, and compares the remaining job with another job to perform a binary comparison. FIG. 2 shows an example of a procedure in which the job selecting unit 3 selects a job by binomial comparison between jobs.

[1-2-3. Example of Job Selection] A procedure for selecting a job using an example of comparison condition data shown in FIG. 3 and an example of job data shown in FIG. 4 will be described with reference to FIG. It is assumed that the resource data has the contents shown in FIG. First, when comparing jobs J-01 and J-03, the following binary comparison is performed.

That is, two jobs J-01 to be compared
And J-03 are set to variables A and B, respectively.
The variable n is set to 0 (step 1). Subsequently, the value of n is set to 1
Increase, that is, increment (step 2).
When this step is first executed, n that was 0 is 1
Becomes Here, looking at the comparison condition data, since there is an n-th key, for example, a first key (step 3),
The second comparison key “earliest start time” and the corresponding equivalence condition “the difference between the earliest start times is within 3” are set in a predetermined variable or work area (step 4).

Then, using the n-th comparison key set in this way and its equivalence condition, a check is made on the jobs J-01 and J-03 currently set in A and B, respectively. Specifically, first, the job J-01,
The earliest start time of J-03 is 4/1, 4/2, respectively, and the difference between them is 1 day. Therefore, the same condition is satisfied here, and the process returns to step 2.

In step 2, the value of n is increased by one again, and n is set to 2. The comparison condition data D3 includes n
First, at this time, since the second comparison key exists (step 3), the comparison key "time margin" is set in the work area described above (step 4). Since no equivalence condition is set for this comparison key, the equivalence condition is "none" at this time. In this case, in the subsequent check of the equivalence condition (step 5), it is determined that the equivalence condition was not satisfied because there is no equivalence condition.

For this reason, the job J-01 set in A and the job B-01 in
Are compared with each other (step 6). In this case, since the order of the comparison key “time margin” is set in ascending order, that is, it is determined that the job with the smaller time margin is selected first, so that the job J-03 (B ) Is selected, and the job J-03 is output to the schedule processing unit 4.

[1-2-4. Another Example of Job Selection] Also, when comparing jobs J-01 and J-10 in the same manner, the result is as follows. That is, first, these job J
-01 and J-10 are set to A and B, respectively, and n is set to 0 (step 1). Subsequently, the value of n is increased and n
Is set to 1 (step 2). Here, looking at the comparison condition data, the first key exists (step 3).
"The earliest start time difference is within 3" is set (step 4).

Here, first, an equivalence condition is checked (step 5). At this time, jobs J-01 and J-1
The earliest start times of 0 are 4/1 and 4/20, respectively, and the difference is 19, which does not satisfy the equivalence condition. Therefore, next, the comparison is made at the earliest start time which is the comparison key (step 6). In this determination, since the order is set to ascending order, the job J-01 having the earliest start time is selected.

[1-2-5. Example of Scheduling] An example of scheduling using the above job selection will be described with reference to the comparison condition data of FIG. 3 and the job data of FIG. First, at the time of starting scheduling, initially, all jobs are unassigned.

Then, the same condition “the difference between the earliest start times is 3
If the job that satisfies the “equal to” condition and the first comparison key is the earliest start time and is arranged in ascending order, and satisfies the equivalence condition, the jobs J-01, J-02, J-03, and J-0
4, J-05 are candidates for selection. Further, a comparison using the second comparison key is performed. Since the equivalence condition is not set for this second comparison key, the job J-03, which is the job with the shortest margin time, is selected. Thus, first, when the job J-03 is allocated to the resource M1, the status of the schedule shown in FIG. 6 is obtained.

Subsequently, the next job to be assigned is selected. The remaining candidates by the first comparison key are jobs J-01 and J-01.
J-02, J-04, and J-05. As described above, based on the second comparison key, the job J-02 having the shortest margin time is selected and assigned to M2. Can be

Similarly, the job satisfying the equivalent condition of the first comparison key is determined based on the second comparison key.
J-04 and J-01 are selected in this order and assigned to resources. When the last job J-01 is allocated to the resource, the job with the earliest start time among the unallocated jobs is job J-06, and the earliest start time is 4/5. Become.

Accordingly, in addition to the first comparison key and the same value condition, the job J-07, J-07,
J-08 and J-09 are candidates for selection. Jobs J-08 and J-09 have the shortest spare time, but the second comparison key is between these two jobs J-08 and J-09. There is no difference in the spare time, and no other comparison key is set any more. In such a case, the data is selected in the order in which the data was read and assigned to the resource.

Thereafter, when the scheduling is performed similarly, the schedule shown in FIG. 7 is obtained, and the total of the delivery delay is 14
The total day and free time is six days. Here, FIG. 8 shows a result of comparing the scheduling result according to the present embodiment with the above-described conventional method, that is, the conventional technology. That is, as shown in this figure, in the present embodiment, the scheduling result is that either one of the delivery delay or the idle time is small but the other is large, as compared with the conventional method. The schedule results are balanced.

[1-3. Effects of the First Embodiment] As described above, in the first embodiment, the comparison condition data D3 is set to the comparison condition data D3 for each comparison key for selecting a job, assuming that the range of the difference that can be identified is the same value condition. Set it. Then, in the job selection unit 3, as a result of comparison using a comparison key of a certain priority, jobs having a smaller difference so as to satisfy the equivalent condition are selected by the comparison key of the next priority, thereby realizing flexible scheduling. Is done. Also,
The user's intention is directly reflected in the scheduling by setting, as an equivalence condition, how much difference can be identified for each comparison key. That is,
When it is desired to adjust the contents of the scheduling according to the user's intention, the contents and significance of the adjustment are more easily understood by the user than adjusting various parameters as in the related art.

In the first embodiment, which of the attribute values possessed by the job is used as the comparison key, and if any condition is satisfied for any of the comparison keys, the comparison key of the next priority About whether you can select a job in
It can be easily controlled by rewriting the comparison condition data D3. Therefore, it is easy to reflect the user's intention in the scheduling and to apply the present invention to various fields.

In the first embodiment, since the earliest start time related to when the job can be executed and the latest end time directly related to the due date are used as comparison keys, the first embodiment is effective in many fields related to scheduling. Can be applied.

[2. Second Embodiment] Next, the second embodiment incorporates a value that dynamically changes during scheduling as the same condition as that of the first embodiment (FIG. 1) so that the job This is an example that allows effective selection.

That is, when two jobs are continuously allocated to a certain resource, depending on the combination of the two jobs, a time for preparation which is not included in the net work time of the job may be required. The time for this preparation is called setup time. For example, in the case of machining, the time required for tool exchange and setup is the setup time, and the setup time varies depending on the combination of two consecutive jobs.

Under such a premise, for example, it is assumed that a job is allocated from the earliest time and the situation is as shown in FIG. In this figure, the shaded portion indicates the setup time, and the arrow indicates the earliest end time of the last job among all resources, and this time is referred to as the earliest allocation time. The earliest allocation time is a value that dynamically changes during the course of scheduling depending on which resource is assigned to which job.

With respect to this situation, in the prior art, a case is considered where the priority of the comparison key is specified in the order of earliest start time and setup time. In this example, there are two jobs JA and JB, and the earliest start time and setup time are 4/1, 10 for job JA and 10 for job J, respectively.
-B is 4/5, 5 and the earliest assigned time is 4/10
And

In this case, since the earliest start time of each of the jobs JA and JB is earlier than the earliest allocation time, it is possible to actually allocate the jobs without making any idle time. When only a fixed value such as the setup time is used as the comparison key, the job J- has a longer setup time because the first comparison key is the earliest start time.
Since A is selected, effective scheduling becomes difficult.

Similarly, if there are jobs JA and JB, and the priority order of the comparison key is specified in the order of the setup time and the earliest start time, contrary to the above example, the setup time is A smaller number of jobs JB are selected earlier than jobs JA. However, for example, in the case where the earliest allocation time shown in FIG. 9 is 3/10 instead of 4/10, the earliest start time of the previously selected job JB is greatly reduced to 4/1. Free time occurs. Since the idle time is much longer than the setup time of the job JB, the idle time increases as a whole. Therefore, if the earliest assigned time is 3/10,
It is desirable to select the job JA with the earliest start time.

That is, in the second embodiment, the equivalence condition is
This is an example of setting based on a value that dynamically changes during scheduling according to which job is assigned to which resource. Specifically, when selecting the next job to be assigned in the situation of FIG. 9 described above, in the second embodiment, comparison condition data as shown in FIG. 10 is set in advance.

In this case, from the equivalence condition of the first comparison key,
All jobs whose earliest start time is earlier than (earliest assigned time + 5) are regarded as the same. In other words, such a job is less likely to make a free time when allocating to a resource, and the job having the shortest setup time can be selected by the second comparison key.

That is, in the second embodiment, if all the jobs are later than (earliest assigned time + 5) as a result of setting such equivalence conditions, the job with the earliest start time among them is Will be selected. In other words, if all jobs are later than (earliest assigned time + 5), an idle time longer than the setup time often occurs, so it is better to select the job with the earliest start time as early as possible.

As described above, in the second embodiment, since the equivalence condition can be set using a value that cannot be determined unless the scheduling progresses halfway, more flexible scheduling can be performed according to the scheduling situation. it can.

[3. Third Embodiment] The third embodiment is an example in which the scheduling is effectively performed by combining the equivalence condition of the comparison key and the next comparison key. As shown in the first embodiment, two jobs are selected. This solves the problem that the job selection may not be performed properly only by performing the binary comparison.

That is, in the first embodiment, when an optimum job is sequentially selected by using a plurality of comparison keys, only the jobs which are in the range of the same value condition based on the comparison key of the immediately preceding priority are selected. It is a candidate to be compared with the next comparison key.
For this reason, as a result of selecting the optimum jobs one after another on the basis of the individual comparison keys, a job far from the optimum one may be finally selected as the first comparison key.

Here, such a specific example will be described by taking as an example a case where scheduling is performed using the job data shown in FIG. 11 and the comparison condition data shown in FIG. In this example, when the jobs J-01 and J-02 are compared first, the earliest start times are 4/1 and 4/4, respectively, and the difference is 3. In this case, these two jobs J-
Since 01 and J-02 satisfy the equivalence condition of the first comparison key, the job J-02 is selected as a result of the comparison with the spare time of the second comparison key.

Next, the selected job J-02 and
Job J-0, the next candidate not yet assigned
When the comparison of No. 3 is performed, since the earliest start time difference is 3, the same condition is satisfied for the first comparison key, and the comparison is performed with the spare time of the second comparison key. As a result, the job J-03 is selected this time. Will be. Similarly, when the job J-03 is compared with the job J-04, the job J-04 is selected. When the job J-04 is compared with the job J-05, the job J-05 is selected.

However, comparing the jobs J-05 and J-01, the difference between the earliest start times is 12, so that the same condition is not satisfied, and the job J-01 is eventually selected. However, as shown at the beginning of this series of procedures, in this case, it is actually desirable to select job J-02.

As described above, if only two jobs are compared, the selected job differs depending on the order in which the jobs are compared. In particular, as a result of continuing the comparison, the job greatly deviates from the high priority standard, and May not select the desired job. Therefore, in the third embodiment, when there are a plurality of comparison keys, the job selection unit 3 shown in FIG. 1 selects a job that satisfies the same condition for the first comparison key, and selects a job based on the second and subsequent comparison keys. Is selected from the jobs satisfying the equivalence condition for the immediately preceding comparison key based on the next priority comparison key.

Specifically, in the third embodiment, it is conceivable to select a job in the following procedure. Procedure 1. First, n is set to 1. Procedure 2. Further, the job data is scanned, and the first comparison key is used to search for a minimum value in the case of ascending order and a maximum value in the case of descending order. The minimum or maximum value and the job having such a minimum or maximum value are set in variables M and J. At the same time, select flags are set for all jobs. Procedure 3. If there is no next (n + 1) th comparison key, J is output as the selected job, and the process ends. Otherwise, proceed to the next step 4. Step 4. Scan only jobs with the selection flag set,
Using M, the selection flag is set only when the nth equivalence condition is satisfied, and when the equivalence condition is not satisfied, the flag is reset without setting the flag. At the same time, among jobs satisfying the same value condition, the minimum value is set to M 'in the case of ascending order and the maximum value is set to M' in the case of descending order by the (n + 1) th comparison key, and the job having such a minimum value or a maximum value is set. Is set to J.

Procedure 5 Increase the value of n by one, and M to M '
Step 3. Return to

That is, to show a simple example, job 1,
By sorting 2, 3, 4, 5 according to the order satisfying the condition of the first comparison key, jobs 2, 3, 4, 1,
An order of 5 is obtained, and among them, jobs 2, 3, and 4 have the same value based on the same value condition. Subsequently, these jobs 2, 3, and 4 are checked based on the second comparison key, and the results are sorted to obtain the order of jobs 3, 2, and 4. Among these, jobs 3 and 2 have the same value. . further,
These jobs 3 and 2 are checked based on the third comparison key, and the results are sorted to obtain the order of jobs 2 and 3, and job 2 is selected.

To realize such processing, specifically, first, processing for searching for the value of each job using the first comparison key is performed, and when sorting is performed according to the value of each job as described above. In the same manner, the value of the second comparison key is checked, and similarly, when sorting according to the value of the second comparison key, the value of the third comparison key is checked. You can choose the best one.

Next, a specific description will be given using the job data shown in FIG. 4 and the comparison condition data shown in FIG. First, the procedure 1 described above. Thus, n is set to 1.・ Next, Procedure 2. Since the first comparison key is the earliest start time, and the comparison keys are in ascending order, the job whose earliest start time is the minimum and its value are searched. At the same time, select flags are set for all jobs. As a result of such scanning, M is set to 4/1 and J is set to J-01.・ Procedure 3. Step 4. Since the second comparison key exists. Proceed to. -This procedure 4. At this stage, all jobs are scanned since the selection flag is set at this stage. At this time, the value of M is 4/1, and the condition of the same value is “the earliest start time difference is within 3”, so the jobs for which the selection flag is set are J-01, J-02, J-03, J −04, J
It becomes only -05. The second comparison key is the spare time, and the comparison keys are in ascending order. For this reason, since the minimum value of the margin time is 0 in the job for which the selection flag is set, M ′ is set to 0, and J is set to J-03. -Next, procedure 5. N is increased by one to 2 and M is set to 0. -And this time, step 3. Since there is no third comparison key, J-03 set to J is output as the selected job, and the process is terminated.

According to the third embodiment, by repeating the binomial comparison of jobs, it is possible to avoid a problem that a job greatly deviating from a high priority standard is selected.

[4. Other Embodiments] The present invention is not limited to the above embodiments, but includes other embodiments as exemplified below. For example,
The specific field to which the present invention is applied is free, and the types and number of jobs and resources, the contents of comparison keys and attribute values, the method of assigning the selected job to the resource, the format of equivalence conditions, etc. It can be set freely according to the task.

[0085]

As described above, according to the present invention,
Scheduling that directly reflects the user's intention becomes possible.

[Brief description of the drawings]

FIG. 1 is a functional block diagram showing a configuration of a first embodiment of the present invention.

FIG. 2 is a flowchart showing a procedure of a binomial comparison in the first embodiment of the present invention.

FIG. 3 is a view showing an example of comparison condition data according to the embodiment of the present invention.

FIG. 4 is a view showing an example of job data according to the embodiment of the present invention.

FIG. 5 is a diagram showing an example of resource data according to the embodiment of the present invention.

FIG. 6 is a diagram showing a state of scheduling in the first embodiment of the present invention.

FIG. 7 is a diagram showing a scheduling result in the first embodiment of the present invention.

FIG. 8 is a diagram comparing a scheduling result according to the first embodiment of the present invention with a scheduling result according to the related art.

FIG. 9 is a diagram showing a scheduling situation according to the second embodiment of the present invention.

FIG. 10 is a view showing comparison condition data according to the second embodiment of the present invention.

FIG. 11 is a diagram illustrating an example of job data according to a third embodiment of the present invention.

FIG. 12 is a diagram illustrating a conventional scheduling state.

FIG. 13 is a diagram illustrating a conventional scheduling state.

FIG. 14 is a diagram illustrating a conventional scheduling state.

[Explanation of symbols]

 C ... Computer S ... Software C1 ... CPU C2 ... Main memory C3 ... Auxiliary storage device C4 ... Input device C5 ... Output device D1 ... Job data D2 ... Resource data D3 ... Comparison condition data 1 ... Equivalent condition setting unit 2 ... Priority comparison Unit 3: Job selection unit 4: Schedule processing unit

Claims (10)

[Claims] 1. A schedule creating apparatus for creating a schedule by allocating a plurality of jobs to a plurality of resources, comprising: selecting means for selecting a job to be assigned next based on a plurality of comparison keys having different priorities from each other; Means for allocating the selected job to one of the resources, wherein, when there are a plurality of jobs satisfying a predetermined equivalence condition for the comparison key, the next priority is selected from among the plurality of jobs. A schedule creation device configured to select a job to be assigned based on the comparison key. 2. The schedule creation apparatus according to claim 1, wherein the equivalence condition is set based on a value that changes according to what kind of job is assigned to which resource. 3. When there are a plurality of comparison keys, the selection means selects a job that satisfies the equivalence condition for the first comparison key, and selects a job based on the second and subsequent comparison keys.
3. The schedule creation device according to claim 1, wherein a job is selected based on a comparison key having the next priority from jobs satisfying the same condition with respect to the immediately preceding comparison key. 4. A resource data indicating what kind of resource is present, a job to be assigned to the job data represented by a plurality of attribute values corresponding to each job, and a job to be assigned to the resource are sequentially selected. And comparison condition data representing a comparison condition at the time. The comparison condition data is used to determine which of the plurality of attribute values is to be used as the comparison key at what priority, and at least one of the comparison keys. The schedule creation device according to any one of claims 1 to 3, wherein the same condition is expressed. 5. The schedule creation device according to claim 1, wherein the comparison key is an earliest start time and a latest end time of each job. 6. A method for selecting a job to be assigned to a resource from among a plurality of jobs by using a job-related value as a comparison key for a job, wherein the comparison key is regarded as having the same value even if the value is different. A job selection method characterized in that equivalence conditions for the job are determined. 7. A scheduling method for creating a schedule by allocating a plurality of jobs to a plurality of resources, the method comprising: selecting a job to be assigned next based on a plurality of comparison keys having different priorities. Allocating the selected job to one of the resources, wherein the selecting step includes, when there are a plurality of jobs satisfying a predetermined equivalence condition for the comparison key, the next job among the plurality of jobs. A schedule creation method, wherein a job to be assigned is selected based on a priority comparison key. 8. The method according to claim 6, wherein the equivalence condition is set based on a value that changes according to what kind of job is assigned to which resource. 9. The selecting step includes, when there are a plurality of comparison keys, selecting a job satisfying an equivalence condition for a first comparison key, and selecting a job based on the second and subsequent comparison keys,
9. The schedule creation method according to claim 6, wherein a job is selected based on the next priority comparison key from among jobs satisfying the same condition with respect to the immediately preceding comparison key. 10. A recording medium recording schedule creation software for creating a schedule by allocating a plurality of jobs to a plurality of resources by using a computer, wherein the software stores the schedule creation software in a plurality of resources having different priorities from each other. The user is caused to select which job is to be assigned next based on the comparison key, and to cause the selected job to be assigned to any resource. In the selection of the job, there are a plurality of jobs satisfying a predetermined equivalence condition for the comparison key. A recording medium storing software for creating a schedule, wherein a job to be assigned is selected from the plurality of jobs based on the next priority comparison key.