JPH02226467A - Scheduling problem solution supporting system including dynamic job processing - Google Patents

Abstract

PURPOSE:To efficiently derive a suitable scheduling solution by executing a scheduling processing while generating and/or erasing a job during the progress of a scheduling processing. CONSTITUTION:While a job allocator 12 allocates the job by means of a decisive procedure, and a job modifier 13 successively improves an allocating state, a dynamic job generation/erasing condition supervising part 23 in an allocating state evaluating part 21 generates the dynamic job and/or dynamically erase the job while referencing the contents of a dynamic job attribute describing part 22. Further a result is accumulated and managed by a job pool supervising part 24. A job generating/erasing mechanism 25 generates the job to be generated, and erases the job to be erased. Thus the suitable schedule solution can be efficiently derived.

Description

[Detailed Description of the Invention] [Summary] The present invention provides dynamic job processing in which a single computer processes a scheduling problem that can be understood in the framework of allocating jobs, including dynamic jobs, to machines so as to satisfy predetermined constraints. Regarding the scheduling problem solving support system including.

The purpose of this invention is to provide a means to efficiently derive a reasonable schedule solution while dynamically creating or deleting jobs.

a first processing means that sequentially allocates jobs to machines according to a deterministic procedure, and generates an allocation state of all jobs by relaxing constraint conditions when the scheduling is not successful; Based on the allocation status of all jobs generated by the first processing means, allocated jobs or job groups that can be exchanged between arbitrary machines are extracted, and the job or job group is exchanged between the machines. The second processing means generates a schedule solution by calculating evaluation values to sequentially improve the constraints so that they are more satisfied, and also includes a dynamic job control mechanism.

[Industrial application field]

The present invention relates to a scheduling problem solving support system including dynamic job processing in which a computer processes a scheduling problem that can be understood in the framework of allocating jobs, including dynamic jobs, to machines so as to satisfy predetermined constraints. .

Many scheduling problems can be thought of as ``problems of assigning jobs to machines.'' A machine is an object that is bound by a job for a certain period of time and executes two assigned jobs. For example, when freight is transported between required points by truck, the truck or the like that transports the freight is a machine, and the freight transport request is a job.

This kind of scheduling problem is one of the problems to which planning-based expert systems can be applied, but due to the characteristics of this type of problem, such as the tendency to fall into combinatorial problems, it is difficult to generate a solution quickly, and there is no way to solve it. Therefore, there is a need for technical means to enable the construction of practical systems.

[Conventional technology]

For example, given n offices and m trucks,
Let us consider the processing of a scheduling problem in which a trunk operation plan is created to realize the required number of flights between these offices.

In that case, the geographical relationship of each business office (route connecting the business offices, time required for operation between them, etc.), the time required for loading, unloading, etc. at each business office, the business hours of the business office, and the Requirements for the arrival and unloading of cargo, etc. are given as constraint conditions.

The solution to this problem is 1, for example each trunk T1. What time does T2... leave from which office, what time does he arrive at which office, how many minutes does he work there, and what time does he leave for another office? This is a one-day schedule, and it is necessary to find a solution that satisfies the above-mentioned constraints.

Such scheduling problems are generally solved by treating a truck as a "machine" and assigning a job to an 8!1 machine, with the operation from one business office to another as a "job" to be processed by that machine. I can add one more.

When solving this type of problem, the two-way surface is expressed as a formula and the solution is found mathematically. There are analysis methods such as so-called operation research, but in real-life problems like the one mentioned above, unless one problem is significantly simplified.

It is extremely difficult to quantify it, so
It is often not applicable in practice.

Furthermore, even if it is possible to formulate a formula, if the constraints change, it will generally be necessary to reconsider the structure of the formula.
It is often difficult to respond to changes in circumstances.

On the other hand, instead of an analytical method, a method has been considered that exhaustively searches for all combinations of job υj assignments to a machine on one time axis that satisfy the constraint conditions, but the search space is limited. Because it is too broad, it is generally difficult to obtain a schedule solution in a practical processing time.

Therefore, the inventors of the present invention have proposed the following technique as a system/method for quickly obtaining a solution to a scheduling problem.

One is to perform deterministic scheduling using heuristics, which is an i! By separating the streams and limiting the solution space to a subspace, calculation time is shortened (Patent application No. 62-26756).
No. 1).

One method is to create a new state by relaxing the constraints and allocating all jobs to machines and sequentially exchanging jobs or job groups that can be exchanged between nine machines according to the calculation results of evaluation values. and finally find a schedule solution that satisfies all constraints (
(Patent Application No. 1989-274089).

Furthermore, a scheduling problem solving support system (patent application Sho-1073) in which the above two techniques are applied in stages is proposed.
No. 30) is proposed. The technologies to be applied in stages are detailed below.

FIG. 4 is a diagram for explaining stepwise application.

In FIG. 4, 10 is a problem that is input as a scheduling target, 11 is a processing device consisting of a CPU, memory, etc., 12 is a job allocator that uses heuristics to select a job and assign it to a machine, and 13 1 is a job modifier that improves the state and generates a schedule solution; 14 is a schedule solving unit that outputs the obtained schedule solution; and 15 is a schedule solution for a given problem IO.

Given a problem defined by jobs, machines, and constraints, the job allocator 12 uses heuristics to allocate jobs to machines on the time axis. Jobs are assigned to machines according to the following steps and scheduled.

Finally, if all jobs satisfy the constraint conditions and are assigned to each machine, scheduling is considered successful, and the result is set as schedule solution 15.

When assigning a definitive job, if the constraint conditions cannot be met and unassigned jobs remain,
By relaxing the given constraints, unassigned jobs can be assigned to i-machines without satisfying the constraints, and -9
The scraping states of all jobs are generated and the results are notified to the job modifier 13.

If the job allocator 12 is unable to derive a schedule solution and notifies all jobs δ allocation state information whose constraint conditions are not satisfied, the job modifier 13 sets the all-job allocation state as an initial state and uses a different By extracting assigned jobs or job groups that can be exchanged between machines, and calculating the evaluation value of the state in which the jobs or job groups are exchanged between those machines, it is possible to sequentially move towards more satisfying the constraint conditions. We will make improvements to this and perform processing to generate a schedule solution. The schedule solution obtained in this way is outputted via the schedule solution output section I4.

In the present invention, a schedule solution is generated through two-step control: deterministic scheduling using heuristics by the job allocator 12, and scheduling based on the sequential improvement method by the job modifier 13.

Since the job allocator 12 definitively allocates two jobs to machines, even if the number of jobs increases, the processing time for all jobs only increases linearly. Furthermore, even if a schedule solution cannot be reached, an allocation state that is somewhat close to the solution is generated and the process ends. Therefore,
If the job modifier 13 sequentially improves the state generated by the job allocator 12, it is possible to reach the schedule solution by improving from a state close to 5 solutions and with fewer state evaluations and job exchanges. You will be able to do this.

In other words, if an initial state is generated using only the job modifier 13 and the initial state is successively improved, a combinational problem such as the number of exchange executions will increase as the number of jobs increases. However, through cooperation with the job allocator 12, it is possible to reduce the number of exchange executions, etc., and to realize high-speed solution generation even for scheduling problems that involve handling large-scale data.

FIG. 5 shows the processing flow of the job allocator, FIG. 6 shows the processing flow of the job modifier, and FIG. 7 shows an example of processing by the job modifier.

In the scheduling problem of creating a one-day land transport plan using trucks, for example, m trucks are designated as machines, and the problem is between n locations.

A job such as "flight from office P to office Q" is specified. In addition, time required between offices and other constraints are set.

In response to input of such a scheduling problem, the job allocator 12 shown in FIG. 4 performs definitive scheduling through the processing shown in FIG. 5. ■~0 in the following description corresponds to processes ■~@ shown in FIG.

■ At present, select a machine of interest to which δIJ can be assigned. Note that if there is no machine that can be allocated, the machine that is released from the job earliest is focused on, time is advanced until the time when the machine is released, and that machine is set as the machine of interest.

Next, a set of jobs to be allocated to candidates is selected.In this selection, for example, two time parameters are used as the time width for targeting reasonable jobs: the maximum required time and the minimum possible time. Use. The required maximum time is the time after which a machine can be assigned to any job, and the minimum possible time is the maximum allowable time and job assignment so that one machine has less idle time. This is the time determined from the relationship with the generated tack level. These times are given as constants depending on one problem, but it is preferable to set appropriate values by tuning through one trial.

■ A set Jsl of jobs whose final job allocation start time is within the required maximum time from the current time (hereinafter referred to as maximum required jobs) based on the target machine.
Extract.

(2) Also, with the machine of interest as a reference, a set Js2 of jobs (hereinafter referred to as minimum possible jobs) whose first time of job allocation start time is included within the minimum possible time from the current time is extracted.

(2) Next, it is determined whether a machine other than the machine of interest is capable of processing the set Jsl of the maximum required jobs. Here, the following judgment is made.

Assume that there are jobs J1 to j4 as the maximum required jobs, as shown in (a) in FIG.

First, the machine M3 that can process the first job J and becomes vacant the latest is associated with the job J1. Next, regarding job J2, machine M2 is similarly associated. The same applies to job J. , Finally, job J4 can also be assigned to machines other than the focused machine.
, it means that the maximum required job can be processed by a machine other than the target machine.

■ Set Js of the maximum required jobs for machines other than the focused machine
If it is not possible to process l, select this set Js as 1 selection job.
Adopt l.

■ Set Js of the maximum required jobs for machines other than the focused machine
Since it is better to start the machine of interest as soon as possible, the minimum possible job set Js2 is adopted as the selected job.

■ Determine the job to be assigned to the machine of interest from among the selected jobs. Along with considering constraints.

Evaluate the elements of the selection job set and assign the best job.

■ Determine whether it was possible to allocate a job that satisfies the constraint conditions, and if a solution that satisfies the constraint conditions cannot be obtained, move to process @.

■ Determine whether all jobs have been scheduled. When the schedules for all jobs are completed, it means that the necessary schedule solution has been obtained, and the result is notified to the schedule solution output unit 14 shown in FIG. 4.

Finish the process.

[Phase] If there are still jobs to be processed, check whether a new job needs to be generated depending on the passage of 7 hours or changes in conditions. If job generation is not necessary, return control to process ■.

Repeat the process in the same way. For example, if the truck is at a business office without a garage when the end of business hours approaches, it is necessary to generate a job to move the truck to a business office with a garage.

■ If it is necessary to generate a job, generate the zip, set it in an internal table (not shown), and process it.■
Control is returned to and the process is repeated in the same way.

■ If a job that satisfies the constraint conditions cannot be assigned, the constraint conditions are relaxed and the unassigned jobs are forcibly assigned to the machine. and.

The result is notified to the job modifier 13 shown in FIG. 4, and the processing of the job allocator 12 is ended.

In the Jilib modifier 13, the job allocator 12
In response to the notification from 1, for example, processes such as those shown in FIG. 6 are executed.

■ First, the receiver obtains information on the allocation status of all jobs whose constraint conditions are not satisfied. With this as the initial state, improvements are made sequentially through the following processes.

■ The current allocation state is checked based on the constraints, and if all the constraints are satisfied, that state is determined to be a schedule solution, and the schedule solution output section shown in Figure 4 outputs the result of that state. 14.

■ If the status does not satisfy the constraint conditions, search for a mutually interchangeable subset of the jobs assigned to any machine based on the assignment status of the job, and select it as a swap candidate. do.

As an interchangeable subset: 1. For example, jobs assigned to two different machines, each job sequence consisting of one or more jobs following a job with the same starting office, or jobs with the same starting office. You can select columns and more for each job from 2 to 3 jobs that have the same arrival office. In addition, cases in which a job or a sequence of jobs assigned to a machine is simply moved to another machine, including the case where one subset is empty, are also swap candidates.

■ When a swap candidate is found, an evaluation value related to the constraint condition is calculated for the state obtained by exchanging the job subset of the candidate between the corresponding machines. For example, the excess time of each flight can be taken as this evaluation value.

(2) Determine whether the evaluation value of the state obtained by replacement is improved from the evaluation value of the current state before replacement, based on the determination conditions. If it is determined that there is no improvement, the process returns to process (2) and searches for another swap candidate.

■ If swapping provides an improvement, swap the job or job group that is a swap candidate.

After updating the state to the new state, control is returned to process (2) to check whether the row state is a solution. Repeat the following 7 processes (1) and (2) to improve the status one by one to obtain a schedule solution.

The successive improvement process by the job modifier 13 will be explained according to a specific example shown in FIG.

Note that for the sake of simplicity, the process will be described here as independent from the process by the job allocator 12.

For example, as shown in Figure 7 (a), there are four offices, office A to office ri, and there are four flights (two round trips) between offices A and B, and between all other offices. Assume that each job has two flights. Assume that there are three trucks (T1.T2°T3) that are machines that execute the job.

It is also assumed that a first-order constraint condition is given.

(1) Trunk Tl, T2. T3 is each office A.

It is initially placed in B and C.

(2) Travel time between each office is 50 minutes.

(3) The required flight time assigned to each truck must be 200 minutes or less.

(4) Operate all trucks.

(5) Each truck must be deployed to offices A, B, and C upon completion.

Here, the evaluation value is the value of the time exceeding 200 minutes out of the total research time required for the flight assigned to each truck.

Specify a primary condition as a judgment condition.

One of the current evaluation values of the swap candidates is set as eI+ and the other as 82, and the new evaluation values after the exchange are respectively n e + +
+Hx(e, , ez) > max(n
eI , nez ) or ((e1=ne,) and (
It is assumed that the condition is improved when ez >nez ) ) or ((ez = [j2) and (e, >nel) 1 is satisfied.

Here, the exchange of a subset of jobs in swap candidates is a loop swap performed for a sequence of jobs that constitute a bus with the same starting point and arrival point.

There are two types of tail swaps that are performed on a sequence of jobs that constitute all paths after a certain starting point.5 Buses that have the same starting point under these conditions are searched from different job sets and are used as swap candidates.

Scheduling is done with the above conditions in mind.

For example, schedule solutions are obtained through sequential improvement, such as ta+ to fcj shown in FIG. 7(b).

That is, if the initial state processed by the job modifier is as shown in (a), 1, for example, as a swap candidate between tracks Tl and T2.

The part shown in the dotted line frame in the figure is taken up and is the target of loop swap. Note that trucks T2 and T3 to which no jobs are assigned are assigned offices B to B, respectively.
It can be seen that there is a dummy flight from office C to office C.

(The evaluation value in the state of al is 50X12-200=400 for track T1, and -200 for T2.Here, when the above loop swamp is performed, the evaluation value is 01 for track T1. 200 for track T2. Therefore, based on the judgment conditions 5 above, it is judged that an improvement can be obtained, and the replacement is executed.
Obtain the new state of b).

Next, if we search for swap candidates between tracks T2 and T3 with a large interval between evaluation values, and pick up the tail swap shown in the dotted line frame in (b), we will The evaluation value is trunk T2
．． It becomes 0 for both T3. Therefore, it can be seen that an improvement can be obtained under the 1 judgment condition, and the replacement is executed. As a result, state (C) is obtained. This state satisfies all the constraints, so it becomes a schedule solution.

The initial state of fa) shown in FIG. 7(b) is generated in advance by the job allocator 12 shown in FIG.
Since improvements are made sequentially starting from a state close to the schedule solution, schedule solutions can be quickly obtained even for more complex problems.

[Problem to be solved by the invention]

In the case of the processing shown in Figure 4, the jobs to be assigned are treated as elements of a static set, and a scheduling solution is generated for these static jobs. ing. This process corresponds, for example, to the problem of planning flight schedules for passenger aircraft. However, in the case of, for example, the problem of scheduling tank operations to oil storage tanks, it is difficult to decide by when the next transport should be carried out, or when the next transport should be carried out, based on the size of the ship being transported and the consumption status of the oil in the tank. Jobs need to be dynamically created or deleted depending on the progress of the scheduling process. For this reason, it is not possible to properly deal with this problem using only the technique shown in FIG. 4.

SUMMARY OF THE INVENTION An object of the present invention is to provide a means for dynamically creating or deleting jobs while efficiently deriving a reasonable schedule solution.

[Means to solve the problem]

FIG. 1 shows a basic configuration diagram of the present invention. Reference number 10 in the circular is a problem that is input as a scheduling target, 11 is a processing bag consisting of a CPU, memory, etc., 12 is a job allocation that selects jobs and assigns them to machines using heuristics, and 13 is a problem that is input as a scheduling target. A job modifier that improves conditions and generates schedule solutions;
15 is the schedule solution 20 for the given problem 10
is a dynamic job control mechanism provided in the present invention, 2
Reference numeral 1 represents an allocation state evaluation section, 22 a dynamic job attribute description section, 23 a dynamic job creation/deletion condition management section, 24 a job pool management section, and 25 a job creation/deletion mechanism.

Dynamic job system '4'! 5 mechanism 20 is divided into 1 allocation state evaluation section 21 and job creation/deletion mechanism 25. The job creation/deletion mechanism 25 functions to actually create and/or delete jobs during the progress of the scheduling process. The allocation status evaluation unit 21 includes a dynamic job attribute description unit 22 and a dynamic job creation/deletion condition management unit 2.
3 and a job pool management section 24.

The dynamic job attribute description section 22 describes attribute information including conditions for dynamically creating and/or deleting a new job in accordance with the progress of the scheduling process.

The dynamic job creation/deletion condition management section 23 refers to the contents of the dynamic job attribute description section 22 and executes the job allocator 1.
2 and the progress of processing in the job modifier 13, whether to dynamically generate and/or delete a job is managed.

The job pool management unit 24 pools static jobs that have been given before the scheduling process starts and dynamic jobs that are generated and/or deleted as the scheduling process progresses. .

[Effect]

While the job allocator 12 allocates jobs in a deterministic manner, and while the job modifier 13 sequentially improves the allocation state.

Allocation letter! The dynamic job generation/deletion condition management unit 23 in the voice evaluation unit 21 dynamically generates a job and/or dynamically deletes a job while referring to the contents of the dynamic job attribute description unit 22. and.

The results are pooled and managed by the job pool management section 24.

The job creation/deletion mechanism 25 creates jobs to be created and deletes jobs to be deleted.

〔Example〕

FIG. 2 is an explanatory diagram for explaining job generation, etc., and FIG. 3 shows a processing mode of an embodiment of the present invention.

In FIG. 2, the scheduling process proceeds under the condition that IQO is stored in the oil tank, but at time L2, the amount in the oil tank is lower.
It turns out that the limit is reached, and even at the 5th point, #1
The quantity ql is shown as being delivered by SHIP.

During the processing of the job allocator 12, in the case as shown in FIG. The Rukoto.

It is assumed that transportation by #ISHIP at time t1 has been tentatively determined in the processing in the job allocator 12, and under this state, job modifier 1
3 is 1 point 1. Suppose that an improvement has been made in which transportation by #2 SHIP is more preferable.

In such a case, a job for transporting oil to the relevant oil tank will be generated before the second time point t4. That is, a new job will be generated even during processing in the job modifier 13. Of course, in some cases, the job will be deleted.

Conceptually, the dynamic job control mechanism 20 may be considered to execute the processing described in connection with FIG. 2.

In FIG. 3, numerals 12 and 13 correspond to those in FIG. 1, respectively. The processing is performed as follows. That is.

(1) First, as an initial state, it is checked whether a dynamic job needs to be generated at that time. Generated if necessary.

(2) Scheduling processing by the job allocator 12 is executed.

(3) The job is allocated and the 2-allocation status evaluation unit 21 is notified.

(4) The allocation status is evaluated and it is checked whether a job needs to be generated.

(5) If the job is to be generated, the process returns to the scheduling process by the job allocator 12 after job generation. In addition, if there is no need to generate the job, the process returns to the scheduling process by the job allocator 12 as long as there are unallocated jobs remaining in the job pool management section 24, although illustration is omitted.

(6) When the processing by the job allocator 12 is temporarily completed, the scheduling processing by the job modifier 13 is executed.

(7) The job modifier 13 executes the status improvement process and notifies the 2-allocation status evaluation unit 21.

(8) The allocation status is evaluated and it is checked whether a job needs to be created or deleted.

(9) If it is necessary to generate a job, after the job is generated, the process returns to the scheduling process by the job allocation 12 at that point.

001 If it is necessary to delete the job, the process returns to the scheduling process by the job modifier 13 after the job is deleted.

0υ Of course, if necessary, use job modifier 13
After the processing by the job allocator 12 is completed, the job allocator 12
In some cases, processing is performed using

〔Effect of the invention〕

As described above, according to the present invention, it is possible to solve the problem of scheduling processing including dynamic jobs within the framework of allocating jobs to machines.

In the figure, 10 is an input problem, 11 is a processing device 12, a job allocator, 13 is a job modifier, 15 is a schedule solution, 20 is a dynamic job control mechanism, 21 is an allocation state evaluation unit, and 22 is a dynamic job Attribute description section, 23
24 represents a dynamic job creation/deletion condition management unit, 24 represents a job pool management unit, and 25 represents a job creation/deletion mechanism.

Claims (1)

[Scope of Claims] A scheduling problem solving support system that uses a computer to process a scheduling problem that can be understood in the framework of allocating jobs to machines so as to satisfy predetermined constraints, using a deterministic procedure. , a first processing means (12) that sequentially allocates jobs to machines and generates an allocation state of all jobs by relaxing constraint conditions when the scheduling is not successful; Based on the allocation status of all jobs generated by the processing means (12) of No. 1, allocated jobs or job groups that can be exchanged between arbitrary machines are extracted, and the jobs or job groups are exchanged between these machines. The second processing means (13) generates a schedule solution by calculating the evaluation value of the state in which the constraints are satisfied, and at least corresponds to the progress of the scheduling process. a dynamic job attribute description section (22) in which attribute information including conditions for dynamically creating and/or deleting a new job is described, and the contents of the dynamic job attribute description section (22). , progress of processing in the first processing means (12);
A dynamic job generation/deletion condition management unit (2) that manages whether to dynamically generate and/or delete a job in accordance with the progress of processing in the second processing means (13).
3); and a job pool management unit (24) that pools and manages static jobs that have been given before the scheduling process starts and the dynamic jobs that have been generated and/or deleted. A status evaluation unit (21) is provided, and a job creation/deletion mechanism (
25) is prepared, and the allocation state evaluation unit (21) and the job creation/deletion mechanism (25) are configured in a dynamic job control mechanism (20), and the job is created during the progress of the scheduling process. A scheduling problem solving support system including dynamic job processing, characterized in that scheduling processing is executed while creating and/or deleting jobs.