JPH01109469A - System for resolving scheduling problem - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] This invention relates to a scheduling problem solving system that uses a computer to perform scheduling necessary in fields such as inventory management and production management.

When assigning jobs to machines, the purpose is to separate the job and machine selection and limit the solution space to a subspace, thereby reducing calculation time.

a machine selection unit that selects one machine that is currently in an allocatable state as a machine of interest; a set of candidate jobs that can be processed by the machine of interest; A job selection unit that performs processing to narrow down the selected job set to nine selected job sets based on relationships with machines other than the machine of interest, and a job selection unit in the selected job set.

and a subspace search processing unit that performs a process of allocating the machine of interest.

[Industrial application field]

The present invention relates to a scheduling problem solving system that uses a computer to perform scheduling required in fields such as inventory management and production management.

Scheduling is attracting more and more attention due to improvements in software technology such as expert systems, and demand for its implementation is increasing. This scheduling is necessary in a wide range of fields such as inventory management and production management, but it is necessary for boat fishing.

The purpose is to allocate jeeps to machines according to predetermined constraints. However, scheduling, which is actually applicable, has a wide search space and cannot be easily put into practical use.Therefore, there is a need for a technique to reduce the search space for scheduling and shorten the calculation time.゛.

[Conventional technology]

For example, consider the problem of planning one day's land transportation by truck from one collection point to another.

The data to be scheduled is given to each collection and delivery location in the form of "truck service bound for...". The number of truck deliveries provided varies depending on the collection and delivery location. At each collection and delivery point, work time must be secured for loading, unloading, inspection time, etc. The necessary work time varies depending on the collection and delivery point. The collection and delivery route of each truck begins at a collection and delivery center with a garage as a night facility and ends at a collection and delivery center with a garage. For example, when transporting fresh fish from a fish market, the route is a regular service based on the requirements of the market under the jurisdiction of the collection and delivery center. There are some items that must be transported at specific times.

In addition, business hours are determined for each collection and delivery location.

When solving the problem of how to operate each truck under these conditions using a computer, the truck is considered a machine, and the job that must be transported is considered a job, and one must determine which machine should be assigned to each job. , determined by exploration.

According to the conventional method, when performing this kind of scheduling, all combinations of jobs and machines on the time axis are searched, and constraints are set for each case until a satisfactory solution is obtained. I was told to check it out.

[Problem that the invention seeks to solve]

According to the conventional method, when implementing scheduling, solutions are found individually depending on the case, and constraints are checked for all of the solution space, which takes an enormous amount of calculation time. Even with the use of high-performance computers, it was sometimes impossible to obtain the required solution.

The present invention aims to solve the above-mentioned problems and to make it possible to shorten calculation time by separating job and machine selection and limiting the solution space to a subspace when assigning jobs to machines. There is.

[Means for solving problems]

FIG. 1 is a diagram explaining the principle of the present invention.

In FIG. 1, 10 is a processing device consisting of a CPU, memory, etc., 11 is a machine selection unit that selects a machine of interest, and 12
13 is a job selection unit that extracts ships to be selected;
14 is a necessary maximum job selection section that selects jobs within the required large amount of time regarding the allocable start time; 14 is a minimum possible job selection section that selects jobs within the minimum possible time regarding the allocatable start time; and 15 is a necessary maximum job selection section. A job set selection unit selects a job set to be assigned to the machine of interest from among the jobs selected by the unit 13 and the minimum possible job selection unit 14; Reference numeral 17 represents a constraint condition checking section which performs a search to determine a job to be assigned to the machine of interest while checking the constraints.

The human power information for the processing device IO is information about jobs, machines and constraints. The output information is scheduling result information indicating when each machine should be assigned to each job. A job is a task that must be processed at a certain time, and a machine is a resource that executes that task.

Generally, a job has a range on the time axis that can be assigned to a machine.The problem of scheduling is how to process these jobs by each machine.

The machine selection unit 11 performs a process of selecting, as a machine of interest, one machine that is available for one assignment at a certain point in time or a machine that will be released from a job the earliest. The job selection unit 12 selects the maximum necessary job and the minimum possible job for this machine of interest using the maximum necessary job selection unit 13 and the minimum possible job selection unit 14, respectively.

Here, a large-required job is 9, for example, job J1. J3. J4, and the minimum possible job is 3. For example, job J1.J shown in Figure 1 (bl)
It is a job like x, Js. In addition, Fig. 1 (Ml,
(In bl, W, ~W, 1 is the possible start time for the assignment, such as between what time and what time the truck must depart. T1 is the maximum required time, and Tt is the minimum possible time. Yes, t is the time when the machine of interest can start a short time + tl is the time when to plus the maximum required time T1, t! is the minimum time T2 possible for [.
The time is the sum of .

Here, the required maximum time T1 is the time that no matter which job is assigned, it will be in time for the job after T1 hours, and the minimum possible time T is the allowable idle time so that the idle time of one machine is reduced. This is the time determined from the relationship between the job occurrence frequency and the job occurrence frequency.

These times are given as constants depending on the two problems, but the optimal values may be selected by trial tuning.

The necessary maximum job selection unit 13 selects a job set whose final time of one allocation startable time is before t, and the minimum possible job selection unit 14 selects a job set whose first time of one allocation startable time is before +t8. Select a job set.

The job set selection unit 15 determines whether the maximum necessary job selected by the maximum necessary job selection unit 13 can be processed by a machine other than the machine of interest.

The maximum necessary job or the minimum possible job is adopted as the selected job set.

The subspace search processing section 16 uses the constraint condition checking section 17 to check the constraint conditions for this selected job set, and determines the jobs to be processed by the machine of interest. After that, scheduling is repeated in the same way for the secondary machine of interest.

[Effect]

In the present invention, jobs and machines are selected separately.

Job selection, which performs scheduling that satisfies constraints, means determining which job to assign when at least one machine is available for assignment. Here, when selecting a job, we introduce the required maximum time, and the 0 machines taken in the subspace when searching for the number of jobs that one machine can process consecutively are the machines that can be assigned now. In addition, by considering the number of jobs included in the required maximum time, it is possible to determine how many jobs the currently allocable machines must process. Therefore, it is sufficient to use a very small subspace as the search space when selecting a job.

Also, when the jobs included within the required maximum time (maximum required job) can be processed by a machine other than the focused machine, it is desirable to minimize the idle time of the current focused machine, so in this case, , the job included in the minimum possible time (minimum possible job) is searched as a candidate for the selected job.This results in efficient scheduling.

〔Example〕

FIG. 2 is a processing explanatory diagram of an embodiment of the present invention, and FIG. 3 is an example of scheduling data for explaining the present invention in detail.
FIG. 4 shows an example of scheduling results for detailed explanation of the present invention.

The present invention is realized by a process such as that shown in FIG. 2, for example. ■~@ in the following explanation.

This corresponds to processes ① to ＠ shown in FIG.

■ Select the machine of interest that can be assigned at the moment.

In addition, if there is no machine that can be allocated.

Focusing on machines that can be freed from jobs the fastest.

Advance time to the point at which it is released, and make that machine the featured machine.

■ Set Js of the maximum required jobs based on the machine of interest
Extract L.

■ Also, a set Js2 of the minimum possible jobs is extracted using the machine of interest as a reference.

■ Machines other than the focused machine are the set of required maximum jobs Js
It is determined whether or not it is possible to process l. Here, the following judgment is made.

Assume that the largest necessary job is job JI-Ja, as shown in FIG. 2(a). first.

The machine M that can process the first job J and becomes available the latest is associated with the ship JI.
Similarly, machine M8 is associated with machine M8. Ship JS
The same applies to Nitsuru 1. Finally, regarding job J4, if there is a machine M that can be assigned to a machine other than the machine of interest, the required maximum job can be processed by a machine other than the machine of interest.

■ 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.

■ A collection of large-required jobs Js on machines other than the featured 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.

■ It is preferable to evaluate the elements of the 0-selection mushroom set that determines the job to be assigned to the machine of interest from among the selected jobs, and to assign the job with the best evaluation.

■ Check the constraints, if any.

When a solution that satisfies the constraints cannot be obtained.

Since it is not possible to schedule, the machine/
Output reference information such as jobs and constraints as necessary, and end the process.

■ Whether or not the schedule has ended, that is.

If the schedule is completed, control is transferred to process O.

[Stock] Determine whether it is necessary to create a new ship due to the passage of time or changes in conditions.

If it is not necessary to generate a ship, return control to process ■,
Repeat the same process 0 For example, if the end of business hours approaches and a truck is at a business office without a garage, it is necessary to create a job to move the truck to a business office with a garage. Become.

■ If it is necessary to generate a job, generate the job, 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 there are no ships to be scheduled,
Outputs the schedule information stored in the internal table and ends the process.

The present invention can be applied, for example, to the problem of planning one day's land transport from one collection/distribution center to another using trunks, as explained in the section (Prior Art).

In this problem of land transportation planning using trucks, the data given as scheduling data is 1, for example, in Figure 3 (A
) or D).

As office information for scheduling.

For example, as shown in Figure 3 (A), information such as business hours, presence or absence of nighttime facilities (garage), initial number of trunks, cargo load, unloading time, inspection time, etc. is input for each office. It is considered information.

Also, as information on the number of trucks, 9, for example, Figure 3 (B)
As shown in , information on the required number of truck flights from the departure office to the destination office is input information. Here, the number surrounded by O marks indicates the departure time or the number of flights including scheduled flights with a fixed departure time.

This regular flight information is input separately, for example, as information shown in FIG. 3(C).

Furthermore, information on the time required by truck from the departure office to the destination office is given as information such as that shown in FIG. 3(D).

Based on such scheduling data,
'Here's how to schedule.

The trunk is treated as a machine, and the job of moving the trunk is based on the number of truck trips shown in Figure 3 (B).
treated as a job.

First, in the initial state in the morning, for example, one truck at the second office is set as the machine of interest and is the first scheduling target. Here, the candidate job set is transportation to the 1st office, transportation to the 3rd office, transportation to the 4th office, etc. In this example, 2 allocations start for non-regular flights. The starting point of the possible time is the current time, and the ending point is the time when each business office ends business hours minus the time required for the trunk and the working time. For scheduled flights, by their departure time or time.

The time available for starting allocation is determined.

The maximum required time is 9, for example 2 hours, and the minimum possible time is 30.
Note that you can set it as you like, such as minutes.

The shorter the required maximum time, the better the search efficiency will be.

If this required maximum time is too short, the optimal solution may not be found.

Initially, there are four trunks at the second office, so the machines other than the machine of interest are the remaining three trunks. In addition, the scheduling of each track is progressing,
Trucks arriving from other offices within the required maximum time are
Once available.

The truck is also counted as one of the counter machines.

Through the process explained with reference to FIG. 2, it is determined whether to adopt the largest necessary job or the smallest possible job as the selected job for the machine of interest.

The machine of interest (trunk) is assigned the task of determining which office it should go to. Thereafter, the trunk that can be currently allocated as the primary machine is selected as the machine of interest, and a job is similarly selected to proceed with scheduling.

With the above scheduling process,! Hiiragi-like.

For example, a scheduling result as shown in FIG. 4 can be obtained. In this result, truck A, which was initially at the second nesting site, left for the first nesting site at 4:00 OO, and
After arriving at the office at 5:00, I worked for 50 minutes and arrived at 5:50.

Return from the first office to the second office. Also, as a regular service from the 9th office to the 2nd office, this truck A leaves the 9th office at 16:00.

Similarly, for other trucks, the departure time from the office where they are currently located.

The target office is determined sequentially through scheduling.

Of course, the present invention is applicable not only to such land transportation planning of trucks, but also to other scheduling problems.

Similarly applicable.

〔Effect of the invention〕

As explained above, according to the present invention, scheduling can be performed by only searching a very small subspace without searching the search space of all combinations of ships and machines. It becomes possible to significantly reduce the calculation time.

[Brief explanation of the drawing]

FIG. 1 is a diagram explaining the principle of the present invention. FIG. 2 is a processing explanatory diagram of an embodiment of the present invention. FIG. 3 is an example of scheduling data for explaining the present invention in detail. FIG. 4 shows an example of scheduling results for detailed explanation of the present invention. In the figure, IO is a processing device, 11 is a machine selection section, 12 is a job selection section, and 13 is a necessary maximum job selection section. Reference numeral 14 represents a minimum possible job selection section, 15 a job set selection section, 16 a subspace search processing section, and 17 a constraint condition check section.

Claims (1)

[Claims] In a scheduling problem-solving system in which a computer performs scheduling to allocate a machine that should process a given job to a given job, machine selection selects one machine that is currently in an allocatable state as a machine of interest. Part (11): A set of candidate jobs that can be processed by the machine of interest is determined based on the required maximum time and minimum possible time regarding the allocation start time corresponding to each job, and the relationship with machines other than the machine of interest.
A job selection unit (1
2); and a subspace search processing unit (16) that performs a process of assigning the machine of interest to a job in the selected job set.