JP6440840B2 - Planning work support system and planning work support method - Google Patents

Description

  The present invention relates to a planned work support system and a planned work support method.

  The optimization problem is a model used for finding a mathematical solution to a problem constrained by actual constraints. Among them, the 0-1 integer programming problem that obtains a variable as a solution by a Boolean value can be applied to an allocation plan that determines the allocation relationship between a task and a worker. With application fields.

  However, it is difficult to find a constraint-satisfying solution before optimization because various constraints are added or the calculation range expands explosively when applied to actual problems. For example, the 0-1 integer programming problem that determines whether there is a solution that satisfies the constraint condition is one of representative examples of NP complete problems that cannot be solved in polynomial time. For this reason, many studies have been made to solve problems with relaxation conditions peculiar to application fields and to seek approximate solutions that are close to optimal solutions. Common solutions for finding the optimal solution for integer programming problems include the simplex method and the brute force method. Heuristics that find approximate solutions are also used for problems where optimization techniques are difficult to apply.

  The following technologies have been proposed as related to such technologies. That is, a route candidate generating means for generating a candidate for an operation route of a crew member for the operation adjustment diagram based on a given operation adjustment diagram, and selection of the operation route candidate for each of the generated operation route candidates is “1”. "0" or "0" as a variable represented by a value of 0 or more and 1 or less so that the sum of the variables of operation route candidates related to the crew is 1 or more for each crew of all trains constituting the operation scheduling diagram. A first model expression expressed and a second model expression expressed so that a sum of variables of operation route candidates related to the crew of each crew member is 1 for each crew member. A solution calculating means for calculating the value of each of the variables for which the model formula is satisfied, and the operational route candidate when all the values of the variables calculated by the solution calculating means are integers. Appropriateness of each of a plurality of evaluation indicators with provisional operation arrangement plan acquisition means for acquiring a combination as a provisional operation arrangement plan and evaluation values when the operation route candidates are matched with the conditions for matching the evaluation indicators. An evaluation process for evaluating an operation route candidate by determining and calculating an evaluation value for the generated operation route candidate and an interim operation arrangement plan acquired by the provisional operation arrangement plan acquisition unit Total evaluation value calculating means for calculating a value obtained by accumulating the value of the variable of each operational route candidate and the evaluation value of the operational route candidate calculated by the evaluation means as a total evaluation value for the provisional operational arrangement plan; An operation arrangement plan creation device comprising: a repetitive control means for repeatedly executing the processing by the solution calculation means and the provisional operation arrangement plan acquisition means (Patent Document 1) Irradiation), and the like have been proposed.

Japanese Patent No. 4945370

  Even with the techniques that have been proposed in the past, depending on the characteristics of the problem, the solution space and relaxation conditions do not fit, and it is not always possible to find and derive accurate approximate solutions or optimal solutions, or the user's tolerance range. In some cases, a long calculation time is required.

  SUMMARY OF THE INVENTION An object of the present invention is to provide a technique for speeding up the solution processing of a planning problem and efficiently obtaining a solution with better accuracy than before.

  The planned work support system of the present invention that solves the above-mentioned problem is a combination of a predetermined number of variables based on the number of resources to be assigned to events, a predetermined set of variables according to the number of events, and a plurality of resources for a plurality of events A storage device for storing plan information indicating each allocation state of the bit string, and a violation event for a predetermined constraint condition in the plan information, each bit corresponding to the same resource between the bit string of each variable and the variable, For each of the above, a predetermined logical operation with a predetermined value is performed to identify multiple allocation and non-allocation of resources, and a bit sequence of the corresponding variable in the plan information is changed by a predetermined algorithm in order to eliminate the violation event, and a solution candidate The solution candidate and the plan information are replaced, and the violation event is resolved and the solution candidate is created. Characterized in that it comprises a computing device for generating an output plan information by returning Ri.

  Further, the planned work support method of the present invention combines a predetermined number of variables, which are bit strings based on the number of resources to be allocated to events, in a predetermined set according to the number of events, and allocates a plurality of resources to a plurality of events. An information processing system including a storage device that stores plan information indicating a state of the bit string corresponds to a violation event of a predetermined constraint condition in the plan information corresponding to the bit string of each variable and the same resource between the variables. For each bit, a predetermined logical operation with a predetermined value is performed to identify multiple allocation and non-allocation of resources, and the bit string of the corresponding variable in the plan information is changed by a predetermined algorithm to eliminate the corresponding violation event To create a solution candidate, replace the solution candidate with the plan information, eliminate the violation event, and create a solution candidate And generating an output plan information by repeating the process.

  According to the present invention, it is possible to speed up the solution processing of a planning problem and efficiently obtain a solution with better accuracy than before.

1 is a network configuration diagram including a planned work support system of a first embodiment. It is a figure which shows the hardware structural example of the automatic proposal subsystem in 1st Embodiment. It is a figure which shows the hardware structural example of the data server of 1st Embodiment. It is a figure explaining the data structure of the plan information in 1st Embodiment. It is a flowchart which shows the procedure example 1 of the plan operation assistance method of 1st Embodiment. It is a flowchart which shows the procedure example 2 of the plan operation assistance method of 1st Embodiment. It is a figure which shows the output screen example 1 in 1st Embodiment. It is a figure which shows the example 2 of an output screen in 1st Embodiment. It is a figure explaining the data structure of the plan information in 2nd Embodiment. It is a figure which shows the example of an output screen in 2nd Embodiment. It is a figure which shows the example of the comparison table which determines the crew member allocation incomplete in 2nd Embodiment.

---- Overall configuration ---
Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a diagram showing a network configuration example including an automatic proposal subsystem 10 which is a planned work support system of the present embodiment. The planned work support system 10 shown in FIG. 1 is a computer system that speeds up the solution processing of a planning problem and can efficiently obtain a solution with better accuracy than before. Such a planned work support system 10 includes an automatic proposal subsystem 100 and a data server 200. However, in the following description, the automatic suggestion subsystem 100 that executes processing independently will be described as the main configuration of the planned work support system 10.

  Such a planned work support system 10 is connected to the network 20 and is capable of data communication with the user terminal 300 and the situation change contact machine 400. The automatic suggestion subsystem 100 may hold all data held by the data server 200, and the automatic suggestion subsystem 100 alone may constitute the planned work support system.

  Note that the above-described user terminal 300 is a computer used by a user in charge of planning work in a company or the like. The user terminal 300 accesses the communication devices of the automatic suggestion subsystem 100, the data server 200, and the status change communication device 400, and receives notifications of user instructions and reception and display of processing results for these devices. Process.

Further, the situation change communication device 400 is a computer, and senses changes caused by various events and resources to be planned by its own sensor or by notification from other appropriate management devices, etc., and uses a predetermined protocol. Thus, the communication regarding the above-described change is executed to the data server 200 (or the automatic suggestion subsystem 100). Since the situation change communication device 400 is a computer, functions corresponding to such processing are implemented by a program. For example, when a person receives information via a sensor or a network about what kind of problem a person has and what task occurs when the person performs the work according to the initial plan. It can be assumed that the corresponding information is transmitted to the data server 200 and the status information 216 is sequentially updated. In addition, as another process of communication related to the change, for example, the initial plan 2180 to the input plan 2181 of the plan DB 218 is changed based on the information related to the change. The functions of the situation change communication device 400 may be similarly performed by the user terminal 300 that has received information regarding changes by the user.
--- Hardware configuration ---
FIG. 2 is a diagram illustrating a hardware configuration example of the automatic suggestion subsystem 100 according to the first embodiment. The hardware configuration of the automatic proposal subsystem 100 constituting the planned task support system 10 of the present embodiment is as follows. The automatic proposal subsystem 100 includes a storage device 101 configured with an appropriate nonvolatile storage element such as a hard disk drive, a memory 103 configured with a volatile storage element such as a RAM, and a program 102 held in the storage device 101 in the memory 103. An arithmetic device 104 such as a CPU that performs various determinations, computations, and control processes, and a communication device 105 that is connected to the network 20 and performs communication processing with other devices are performed.

  The CPU constituting the arithmetic unit 104 includes a register that simultaneously reads, calculates, stores, and outputs a plurality of bits, and performs processing according to a control instruction of a program module arranged in the memory 103.

  FIG. 3 is a diagram illustrating a hardware configuration example of the data server 200 according to the first embodiment. The hardware configuration of the data server 200 that configures the planned task support system 10 of this embodiment together with the above-described automatic suggestion subsystem 100 is as follows. The data server 200 reads out a storage device 201 composed of an appropriate non-volatile storage element such as a hard disk drive, a memory 203 composed of a volatile storage element such as a RAM, a program 202 held in the storage device 201 to the memory 203, etc. And a central processing unit 204 such as a CPU for performing overall control of the system itself and performing various determinations, computations and control processes, and a communication unit 205 connected to the network 20 and responsible for communication processing with other devices.

  Note that the storage device 201 stores data of the calculation log 215, the status information 216, the business model 217, the plan DB 218, the solution candidate DB 219, the approval plan 220, and the attribute information 221. These data are created and stored in advance by the user, or received and stored by another device connected to the network.

  Among these, the calculation log 215 is a log related to various calculation processes in creating a solution candidate, and is stored in the data server 200 by the automatic suggestion subsystem 100.

  The status information 216 is information related to the event and resource status notified from the status change communication device 400 or the user terminal 300. For example, information such as the operating status of a machine or system in a transportation facility such as a delay or failure, the location of personnel assigned to them, and the status of attendance are supported.

  The business model 217 is a rule base that defines why a plan change (solution candidate creation) should be performed in a predetermined situation indicated by the situation information 216 described above. This is a set of data indicating (reason for creating a solution candidate), priority (evaluation order of solution candidates), and the like.

  Further, in the plan DB 218, the initial plan 2180 is an initial plan that satisfies a predetermined constraint condition regarding the event to be planned. On the other hand, the input plan 2181 is based on the above-mentioned initial plan 2180 content, specifically based on the event indicated by the above-mentioned situation information 216 notified by the situation change contactor 400 and the user terminal 300 and the situation change of the resource. The plan is to change the corresponding bit value. Although this input plan 2181 does not necessarily satisfy a predetermined constraint condition, the input plan 2181 is somewhat close to the initial plan 2180 described above.

  Note that in both the initial plan 2180 and the input plan 2181 described above, a predetermined number of words (chunks) based on the number of resources to be assigned to events is set according to the number of events described above. It becomes information indicating each allocation state of a plurality of resources for a combination and a plurality of events in a bit string. An example of the initial plan 2180 and the input plan 2181 is shown as plan information in FIG.

  FIG. 4 is a diagram for explaining the data structure of the plan information in this embodiment. Here, for example, plan information is considered as a solution to the problem of allocating eight tasks (events) to eight workers (resources). In this case, when a Boolean value X (i, j) indicates whether or not the i-th worker is assigned to the j-th task, as shown in the matrix 500 of FIG. X) is an information amount of 8 × 8 = 64 bits.

  In this embodiment, as shown in the plan information 550, a plurality of bits (4 bits = 4 workers in the example of FIG. 4) corresponding to a plurality of resources are collected as one variable “word”, and this word is It is assumed that two sets are collectively referred to as “chunks”, and the plan (X) is handled by combining these chunks by the number of tasks described above. That is, in the plan information 550 of FIG. 4, the number of resources n = 8, the number of bits p = 4, and the number of words q constituting a chunk = 2. In the above word, the configuration example including 4 bits is shown. However, for example, in a computer having a 64-bit register, the word may include 64 bits, and may be appropriately increased or decreased according to the specification of the computer. . In any case, the computer, that is, the automatic suggestion subsystem 100, speeds up the processing by performing the multi-bit processing of the plan information having such a configuration by a single logical operation.

  The solution candidate 2190 in the solution candidate DB 219 is a solution candidate obtained in the solution search process. Among the plurality of solution candidates 2190, the solution candidate 2190 that is output from the automatic proposal subsystem 100 to the user terminal 300 and presented to the user terminal is set as a proposal plan 21911.

  Further, the approval plan 220 in the storage device 201 is the automatic proposal subsystem that receives the proposal plan 2191 that is the solution candidate described above when the user terminal 300 receives an approval instruction for the corresponding proposal plan 2191. 100 creates an approval plan 220 based on the corresponding proposal plan 2191 and stores it in the data server 200.

The attribute information 221 is information that defines the attribute of the corresponding event and resource for each bit in the initial plan 2180 and the input plan 2181 described above. For example, a predetermined bit (the XX digit) of a word indexed at a predetermined position in a word arrangement (in the case of FIG. 4, 8 rows × 2 columns) constituting certain plan information is “personnel A”. The bit corresponds to the presence / absence of the assignment.
--- Functional structure ---
Subsequently, functions provided in the automatic suggestion subsystem 100 that mainly executes processing in the planned work support system 10 of the present embodiment will be described. As described above, the functions described below can be said to be functions that are implemented, for example, when the automatic suggestion subsystem 100 executes the program 102. Of the functions exemplified below, the automatic proposal processing unit 110 is responsible for general planning work support processing, and the logical operation processing unit 111 is responsible for logical operations on chunk bit strings, etc. It is assumed that the input / output processing unit 112 is responsible for data input / output with the status change communication device 400.

  The automatic suggestion subsystem 100 according to the present embodiment indicates that a violation event of a predetermined constraint condition in the input plan 2181 in the plan DB 218 of the data server 200 is a bit string of each chunk and each bit corresponding to the same resource between the chunks. A predetermined logical operation with respect to a predetermined value is performed to identify multiple allocation and non-allocation of resources, and a bit algorithm of the corresponding chunk in the input plan 2181 is changed by a predetermined algorithm in order to eliminate the corresponding violation event, and a solution candidate 2190 is determined. It has a function of generating a proposal plan 2191 and an approval plan 220 as output plan information by creating and replacing the solution candidate 2190 and the input plan 2181 and repeating the above-described violation event elimination and solution candidate creation processing.

  In addition, the automatic suggestion subsystem 100 determines whether or not a violation event has occurred based on the change tendency of the accumulated value when the logical operation is cumulatively performed on the bit string of the chunk when the above-described multiple allocation and unallocation of the resource are specified. And a function for specifying the position.

  In addition, when the above-described solution candidate 2190 is created, the automatic proposal subsystem 100 determines that a variable A (chunk) that is to be multiple-assigned when the input plan 2181 includes multiple assignments of resources as a result of specifying the violation event. By replacing the zero-valued variable B (chunk), a solution candidate 2190 having a predetermined number of bits whose value is non-zero is provided.

  Further, when the input plan 2181 includes resource unallocation as a result of the above-described violation event identification, the automatic suggestion subsystem 100 includes the variable C (chunk) having the bit position where unallocation has occurred, A function for creating a solution candidate 2190 is provided by replacing a variable D (chunk) in which only the bit value at the bit position of 1 is 1.

  Further, the automatic suggestion subsystem 100 performs a predetermined logical operation on at least one of the variable B (chunk) and the variable D (chunk) described above and another variable (chunk) constituting the input plan 2181 to thereby obtain a solution candidate. 2190 is provided.

  Further, the automatic suggestion subsystem 100 calculates the inner product value of the initial plan 2180 (initial plan) and the solution candidate 2190 of the above-described plan DB 218 and acquires the first evaluation value of the corresponding solution candidate 2190, and the above-described function. A function of obtaining the second evaluation value of the solution candidate 2190 by adding up and summing up the bit values of the exclusive OR of the initial plan 2180 and the solution candidate 2190, and the above-described first evaluation value and second evaluation For at least one of the values, a screen data listing the solution candidates 2190 in the order of the evaluation values is output to a predetermined device such as the user terminal 300.

  In addition, the automatic suggestion subsystem 100 classifies the solution candidates 2190 according to the evaluation value levels based on at least one of the first evaluation value and the second evaluation value described above, and the solution candidates 2190 for each level. A function is further provided that counts the number and updates the screen data of the solution candidate 2190 at the corresponding level when the summed value is equal to or greater than a predetermined value and outputs the screen data to a predetermined device such as the user terminal 300.

The automatic suggestion subsystem 100 also has a function of outputting the processing status related to the solution candidate 2190 to a predetermined device such as the user terminal 300.
--- Flow example ---
Hereinafter, the actual procedure of the planned work support method in the present embodiment will be described with reference to the drawings. Various operations corresponding to the planned work support method described below are realized by a program 102 that is read out and executed by the automatic suggestion subsystem 100 mainly constituting the planned work support system 10 into the memory 103. And this program is comprised from the code | cord | chord for performing the various operation | movement demonstrated below.

  FIG. 5 is a flowchart showing a processing procedure example 1 of the planned task support method in the present embodiment, and more specifically, a flowchart showing processing contents by the automatic suggestion subsystem 100. In this case, the automatic suggestion subsystem 100 receives a predetermined instruction from the user terminal 300 (301), executes an overall solution search process (302) described later in detail, and obtains a plurality of overall solutions (solution candidates 2190). .

  Next, the automatic suggestion subsystem 100 uses the plurality of overall solutions obtained in step 302 as the input plan 2181, determines the violation status of the predetermined constraint condition regarding this, and predetermined alarm information regarding the constraint violation location found by the determination Is output to the user terminal 300 (303). In this case, the automatic suggestion subsystem 100 further receives, via the user terminal 300, an alarm selection operation by the user while displaying a plurality of such alarms. Since processing similar to the processing for specifying the constraint violation location by the determination of the constraint violation status is executed in the above-described overall solution search processing (302), it will be described in the explanation of the overall solution search processing described later. .

  In addition, the automatic suggestion subsystem 100 performs sequential proposal creation using a pattern for canceling the alarm selected by the user (304). The above-described pattern is information held by the business model 217, and is a rule that defines why the plan change (solution candidate creation) should be performed in the predetermined situation indicated by the situation information 216. This pattern is a set of data indicating the contents of plan change, the reason for proposal (reason for creating a solution candidate), the priority (evaluation order of solution candidates) and the like for each type of situation.

  As a pattern described above, a local pattern that does not necessarily consider how the result of making a plan change based on one alarm will affect the plan change for another alarm is adapted to a wide variety of tasks. It is easy to create a plurality. The sequential proposals obtained here are a plurality of proposals for solving the warning noticed by the user, and are information such as plan change contents and proposal reasons. The pattern and the constraint condition may be obtained by obtaining a control input from the situation change contact machine 400. The automatic suggestion subsystem 100 sequentially stores such a series of calculation processes on the data server 200 as a calculation log 215.

  Subsequently, the automatic proposal subsystem 100 matches the sequential proposal content generated in step 304 described above with the overall solution obtained in step 302 described above (305). A part of the plurality of overall solutions includes sequential proposal contents as part of the solution candidates, and the automatic proposal subsystem 100 determines which whole solution contains the sequential proposal contents, and sequentially proposes information. Update. For example, character string information indicating a proposal that leads to the Pareto optimal solution is appended to the proposal reason information of the sequential proposal included in the Pareto optimal solution specialized for one of the multiple purposes.

  Next, the automatic proposal subsystem 100 sequentially outputs the proposal contents together with the input plan 2181 to the user terminal 300 (306).

  Subsequently, the automatic proposal subsystem 100 accepts the user's proposal selection from the user terminal 300 (307), and does not satisfy a predetermined termination condition (eg, instruction from the user terminal, presence / absence of alarm) at that time (308: n), the above-mentioned input plan 2181 is updated by reflecting the result of the sequential proposal selection (309), and the process returns to step 303. That is, the automatic suggestion subsystem 100 replaces the solution candidate that is the result of changing a part of the input plan 2181 with the input plan 2181 and repeats the processing from step 303 onward.

  At the stage of step 309, since the restriction condition related to the alarm noticed by the user in step 303 is satisfied, other alarms may remain, but the alarm noticed by the user in step 303 is resolved. Has been. In other words, the automatic suggestion subsystem 100 can sequentially eliminate all the alarms interactively with the user by the above-described repeated processing (step 303 to step 308: n to step 309 to step 303). it can. At that time, the automatic suggestion subsystem 100 can sequentially present the reason for the plan change to the user via the user terminal 300, and can support the determination operation of the user.

  Next, details of the above-described overall solution search process (302) will be described. FIG. 6 is a flowchart showing a procedure example 2 of the planned work support method according to the first embodiment. Specifically, FIG. 6 is a flowchart for explaining the processing content of the entire solution search process in step 302 in the flow of FIG. .

  In this case, the automatic suggestion subsystem 100 reads the input plan 2181 as the solution candidate A from the plan DB 218 of the data server 200 (401). This input plan 2181 is plan information in which a part of the initial plan 2180 is changed in accordance with an input from the status change communication device 400 or the user terminal 300. In other words, it corresponds to a plan that may contain a constraint violation.

  Next, the automatic suggestion subsystem 100 uses the input plan 2181 described above, that is, the solution candidate A, as information about the predetermined event and its allocated resource, for example, the transportation schedule, the operating status of the bases and the traffic machines, and the like. Various data relating to the personnel etc. obtained are obtained from the status information 216 of the data server 200, and for the information obtained here, a crew member who has been in charge of the transportation facility B at a certain base A at the other base C on the next day The presence or absence of violations of personnel movements according to the transportation operation between the bases) is analyzed by a predetermined algorithm (402) so as to meet the crew schedule of the transportation facility D.

  Subsequently, the automatic suggestion subsystem 100 determines whether the solution candidate A satisfies a predetermined condition based on the analysis result in step 402 described above (403). As a result of the determination, if the solution candidate A is not satisfied (403: constraint violation), the automatic suggestion subsystem 100 sets the solution candidate A as an executable solution, and the constraint violation in the chunk in the solution candidate A that is the input plan Predetermined evaluation (described later) such as location identification is performed (404).

  The automatic suggestion subsystem 100 also applies the corresponding constraint violation event extracted on the basis of a predetermined criterion, such as the head order in the word or chunk arrangement, from the constraint violation locations specified for the solution candidate A in step 404 described above. A plan change plan A (which can be said to be partial information indicating the changed part of the solution candidate A) is created so as to eliminate the violation (405). The creation of the plan change plan A may adopt the process using the pattern already described in step 304 in the flow of FIG. 5. For example, the above-described transportation personnel list is used to obtain the status information of the data server 200. 216 and comprehensively search all possibilities based on various information such as status information 216 such as selecting and assigning personnel to be assigned to resolve constraint violations based on this information regardless of the means of transportation. May be generated. A plurality of such plan change proposals A can be created. The automatic suggestion subsystem 100 stores the plan change plan A created in step 405 (a new solution candidate that reflects the plan change plan A in the solution candidate A) in the search list in the memory 103. And

  On the other hand, as a result of the determination in step 403 described above, when the solution candidate A satisfies the predetermined condition, that is, when the constraint is satisfied (403: constraint satisfaction), the automatic suggestion subsystem 100 satisfies the solution candidate A as constraint satisfaction. It is determined that the solution candidate A satisfies the constraint, and the goodness of the solution is evaluated based on the approximation with the initial plan 2180 (described later) (406), and the result is stored in the memory 103 described above. Output to the search list, calculation log 215, and user terminal 300. Further, the automatic suggestion subsystem 100 stores the above constraint satisfaction solution as a solution candidate in the solution candidate DB 219 of the data server 200.

  Subsequently, the automatic suggestion subsystem 100 performs search order control (407). In this case, the automatic suggestion subsystem 100 determines the plan change plan B to be calculated next from among the plurality of plan change plans stored in the search list. As described above, the order of extracting plan change proposals from the search list is as follows. When the user defines depth-first search as the basic policy of the plan solution, the order in which the number of constraint violations is large or the breadth-first search is the basic of the plan solution. If the user has determined as a policy, an algorithm that is determined in accordance with an existing search strategy such as the order in which the solution is estimated to be in a shallower place in the solution space may be employed. In addition, a so-called pruning method may be employed in which a search direction with a low possibility is excluded early from the search list.

  Next, the automatic suggestion subsystem 100 creates a solution candidate B by applying the plan change plan A determined in step 407 to the solution candidate A that is an executable solution that has undergone the above step 405 (408). With this process, for example, the assignment of a certain person changed from the solution candidate A by applying the plan change plan A means that the state has changed from the original state. Moreover, it will have changed to the state different from the solution candidate C obtained by applying another plan change plan C to the solution candidate A. The search is performed by repeating such state transitions. When the search space is regarded as a structure in which solution candidates are arranged in a tree structure, the constraint satisfaction solution becomes a plurality of terminal nodes, and the destination is not searched from the constraint satisfaction solution. The executable solution becomes an intermediate node and a candidate for the next state transition.

  In addition, the automatic suggestion subsystem 100 outputs the calculation process and the calculation situation regarding each step up to the above to the calculation log 215 and the user terminal 300 (409).

  Next, the automatic suggestion subsystem 100 compares predetermined information such as a user operation at the user terminal 300, a timer output for detecting the arrival of a predetermined time, and an input value of a predetermined sensor with a predetermined end condition, and ends the flow. A determination is made (410). If the result of this determination is that the flow is not terminated (410: n), the automatic suggestion subsystem 100 replaces the above solution candidate B and solution candidate A, and repeats the processing from step 402 onward.

  On the other hand, when the flow is terminated as a result of the above determination (410: y), the automatic suggestion subsystem 100 includes a plurality of solution candidates (including constraint satisfaction solutions and proposal plans) obtained up to the above. Then, evaluation is performed using an objective function to be described later, and the evaluation result is associated with the corresponding solution candidate and output to the user terminal 300 as information of the proposed plan (411), and the process is terminated. In this case, the automatic suggestion subsystem 100 classifies the evaluation values of the above solution candidates for each predetermined level, calculates values such as the maximum evaluation value, the minimum evaluation value, and the average value for each level. The calculation result is stored in the storage device 201 of the data server 200 as the attribute information 221 of the proposal plan. The proposed plan described above includes an overall constraint satisfaction solution that satisfies all the constraint conditions but does not have the maximum objective function, and a Pareto optimal solution in which one of the objective functions has the maximum value. It is preferable that the automatic proposal subsystem 100 outputs a solution that satisfies a predetermined evaluation item from these solution candidates to the user terminal 300 as a proposal plan.

  Here, the solution search status monitoring screen 501 output from the automatic suggestion subsystem 100 to the user terminal 300 in step 409 in accordance with the processing in steps 402 to 408 described above will be described with reference to FIG. The monitoring screen 501 shown in FIG. 7 includes an information display column 5011 that displays the solution candidates and the number of constraint satisfaction solutions found in the processing so far, the width and depth or time for searching the solution space, and the solution display in the solution space. A progress status matrix 5012 with diversity (value of the later-described expression 37) on the vertical axis and time (number of executions of steps 404 and 406) on the horizontal axis, and a button 5013 for accepting search interruption and result display at that time from the user , And a cancel button 5014 are included. Among these, when the above-described button 5013 is clicked on the user terminal 300, the automatic suggestion subsystem 100 that has received the button 5013 determines that the end condition of step 410 in the above-described flow is satisfied.

  Among the display elements on the screen 501 described above, in the progress situation matrix 5012, the automatic suggestion subsystem 100 displays, for example, a place where the search has been completed in black and a future search plan in white. As the search progresses, the above black area increases in principle from the upper left to the lower right of the screen. However, since solutions are unevenly distributed in the solution space, they may not always be colored according to principle.

  Further, as a measure of solution diversity in the progress situation matrix 5012, an output value of an objective function for solution evaluation is used. As the objective function in this case, a solution close to the initial plan 2180 is determined as a good solution, and the similarity between the solution candidate and the input plan 2181 at the first time is used. Or you may define the total number of plan changes as the distance of two types of solutions. Further, for example, another function indicating the total working hours or the total overtime hours of the personnel as resources may be used as a measure of diversity. The automatic suggestion subsystem 100 quantizes the evaluation value of the objective function described above into five levels, and divides the vertical axis indicating the diversity of the solution in the progress situation matrix 5012 into five squares corresponding to the five levels and displays them. doing.

  In step 409 in the above-described flow, the automatic suggestion subsystem 100 sequentially counts the total value of the obtained solution candidates for each evaluation value level, and the above-mentioned total value is a predetermined reference value at a certain level. If the value exceeds, it is assumed that on the above-described screen 501, a square that is advanced by one in the right direction of the time axis at the level is painted black.

  In the neighborhood search method shown in the flow of FIG. 6, a constraint satisfying solution in the vicinity is searched from the input plan 2181 as a starting point. Therefore, even when the search is interrupted, a solution close to the input plan 2181 is obtained to some extent. In the present embodiment, since information management is performed with a memory-saving data structure, many solution candidates can be stored in a memory allocated to the search list. Therefore, when solutions are evaluated in the order of FIFO when a plan is extracted from the search list (breadth-first search), a wide variety of solutions can be expected near the input plan 2181 in the solution set obtained when the processing is interrupted. A solution candidate that is significantly different from the input plan 2181 can provide an unexpected solution that the user does not imagine or tends to overlook.

FIG. 7 shows an example of a screen 502 output from the automatic suggestion subsystem 100 to the user terminal 300 in step 411 described above. A screen 502 shown here is a screen for displaying a list of solution evaluation results. In the above-described step 411, the automatic suggestion subsystem 100 evaluates a plurality of solution candidates using a plurality of objective functions, performs sorting using each evaluation value as a key, and outputs the result. Here, a solution candidate having a maximum evaluation value is a Pareto optimal solution, and the automatic suggestion subsystem 100 performs highlighting processing in a form surrounded by a rectangle 5021 on the screen 502 so as to stand out in comparison and examination. .
--- Algorithm details of each step ---
Here, the details of the algorithm used in each step in the above-described flow will be described more specifically, including necessary mathematical expressions.
<Definition of main variables used for explanation>
First, definitions of main variables used in the description will be shown using the following equations 1 to 8. For example, when there are n workers and n tasks, consider a plan for assigning an i-th worker to a j-th task. As shown in the following equation 1, the plan is represented by a matrix X (i, j) which is a Boolean set, and is a solution obtained by calculation.

.... Number 1

For the element value of X (i, j), there is no assignment if it is zero, and there is an assignment when it is 1. This configuration corresponds to the matrix 500 of FIG. There are 2 ^ ^{(n × n)} types of combinations that X (i, j) can take, and the set constitutes a space called a solution space. The process of searching for an appropriate solution that satisfies a predetermined constraint condition from the solution space by calculation is called search.

In addition, as shown in Equation 2 below, the plan has a constraint that a single worker is assigned to any task.

.... Number 2

Furthermore, as shown in the following equation (3), there is a constraint that one task is assigned to any worker.

.... Number 3

Also, as shown in Equation 4, when the cost for the i-th worker to handle the j-th task can be defined, the objective function f () can be expressed using the variable alpha α (i, j). . At this time, the plan for minimizing the objective function f () is an optimal solution that minimizes the cost. It can be similarly expressed by using another index such as performance instead of cost.

.... Number 4

When such an objective function f () cannot be uniquely defined in a simple form, there is no mathematical optimal solution, and the existing optimization method cannot be applied. Alternatively, even if it can be defined, it is often difficult to find an optimal solution within a practical time for problems with complicated constraints or large-scale problems. The neighborhood search method used in the present embodiment is a heuristic method for searching for a solution close to the initial value starting from the initial value, and is one of methods for searching for a solution close to the optimal solution. The present invention can also be applied to other approximate solution solving methods.

  Further, as shown in Equation 5, a variable including a bit set of the number of bits (p) handled by the register in the automatic suggestion subsystem 100 at a time is called a word (W). A set of q words (p * q = n) is called a chunk (C). Plan (X) is n chunk sets. This configuration corresponds to the plan information 550 in FIG.

・ ・ ・ ・ ・ ・ ・ Number 5

Furthermore, as shown in the definition in Equation 6, a solution candidate (X ′) close to this input plan, starting from the input plan (A) that may not satisfy some of the constraints, is a solution that satisfies the constraints. The automatic proposal subsystem 100 searches for a proposal plan that becomes The input plan is assumed to be somewhat close to the constraint satisfaction solution. For example, the input plan is a part of the initial plan 2180 that satisfies the constraint conditions and is partially changed according to the current situation.

・ ・ ・ ・ ・ ・ ・ Equation 6

Here, it is assumed that a function for performing a logical operation or a bit operation on the above-described word or chunk is used (XOR, AND, OR, SHIFT, etc.). Furthermore, as shown in Equation 7, functions that interpret a bit set of words and chunks as one multi-value variable value are described as Val (w) and Val (h). Although it is a function that is defined for explaining the comparison operation, the chunk variable can take a very large value, and therefore, it is not necessarily an implementation that directly digitizes this. It is technically equivalent to the processing procedure described below, and it is easy to implement an algorithm that performs a size comparison determination between chunks or a logical operation without digitization.

・ ・ ・ ・ ・ ・ ・ Equation 7

Further, in the solution search, the automatic suggestion subsystem 100 searches for a solution candidate in the vicinity of the input plan after specifying an unsatisfied portion in the input plan that does not satisfy the constraint condition. Do not change existing allocations that meet local constraints as much as possible. Furthermore, as shown in Equation 8, the automatic suggestion subsystem 100 uses the resource management lists ah and bh for managing the changed records so as not to repeatedly search for the same solution candidate through chained changes. Control the search direction. In this resource management list, if a bit value is zero, it means that the corresponding resource is not yet changed, and if the bit value is 1, it means changed. The resource management list is attribute information about the solution candidate X ′. The automatic suggestion subsystem 100 stores and updates the resource management list in the solution candidates 116 and the attribute information 221 on the data server 200.

・ ・ ・ ・ ・ ・ ・ Equation 8


<Processing flow of neighborhood search method>
Next, further detailed description of the neighborhood search method (flow of FIG. 6) in this embodiment is shown below. In this case, the automatic suggestion subsystem 100 stores the input plan as an initial value of the solution candidate X in the search list in step SA corresponding to step 401.

  Next, in step SB corresponding to step 402 and step 403, the automatic suggestion subsystem 100 extracts the solution candidate X from the search list described above, and determines whether the constraint condition is satisfied.

  Subsequently, in Step SC corresponding to Step 404 and Step 405, the automatic suggestion subsystem 100 determines that another solution candidate X that locally solves the problem if the solution candidate X does not satisfy the constraint condition as a result of the above determination. 'Is created (resolving multiple assignments and unassignment).

  Further, in step SD corresponding to step 406, the automatic suggestion subsystem 100 evaluates the solution candidate X when the solution candidate X satisfies the constraint condition as a result of the above determination.

  Next, in Step SE corresponding to Steps 407 to 410, the automatic suggestion subsystem 100 makes a determination regarding the end condition, and when not terminating the flow, returns the process to Step SB described above. On the other hand, when ending the flow, the automatic suggestion subsystem 100 outputs the calculation results so far to the user terminal 300 (step 411). The above-mentioned termination condition includes interruption by a user operation.

<Step SB: Method for Confirming Constraints>
Here, the details of step SB described above will be described. There are multiple allocations and unallocations as situations where the plan is not satisfied with constraints, and there are cases where each plan is within a chunk or between multiple chunks. These combinations include the following four unsatisfied situations. For example, multiple allocation within a chunk refers to a state where a plurality of bit values are 1 in the chunk. Multiple allocation between chunks refers to a state where the bit value of a specific bit position is 1 in a plurality of chunks.
・ Multiple allocation within chunks ・ Unallocated within chunks ・ Multiple allocation between chunks ・ Unallocated between chunks In automatic evaluation subsystem 100, most of the bit values constituting a plan are zero values in the evaluation of constraints. Process by word or chunk by using something. First, as shown in Equation 9, for q word sets in a chunk, after comparing q times with a zero value q times, there is only one non-zero word element and the sum of its constituent bit values is 1. If so, it is determined that there is no multiple assignment or unassignment in the chunk.

・ ・ ・ ・ ・ ・ ・ Equation 9

Next, the automatic suggestion subsystem 100 checks the relationship among a plurality of chunks. In this case, it is premised on a chunk that has been examined in advance using the above-described equation 9 to determine that neither multiple allocation nor unallocation is present in the chunk. The automatic suggestion subsystem 100 cumulatively calculates the exclusive OR of the chunks as shown in Equation 10 below. If the plan satisfies the constraint condition, the bit positions at which the bit value is 1 do not collide between arbitrary plural chunks. Further, when the exclusive OR of the two variables is calculated, the value becomes 1 only at a position where the bit values are different. As a result, when the cumulative value of the exclusive OR is digitized by the Val function, it monotonously increases. Therefore, the automatic suggestion subsystem 100 simultaneously determines the presence / absence and position of multiple allocations among a plurality of chunks and unallocated issues by using this feature amount.

........ 10

<Step SC: Solution Search Method, Canceling Multiple Assignment in Chunk>
Next, details of step SC described above will be described. Multiple allocation includes multiple allocation within a chunk and multiple allocation between chunks. Of these, multiple allocation within a chunk refers to a state where there are a plurality of bits having a bit value of 1 in a certain chunk. On the other hand, multiple allocation between chunks refers to a state in which a bit value at the same position in another chunk is 1 at a bit position where the bit value is 1 in a certain chunk.

Therefore, first, the automatic suggestion subsystem 100 cancels multiple allocation within a chunk. At this time, as shown in Equation 11, the automatic suggestion subsystem 100 performs a multiple assignment first determination to check how many words have a non-zero word value in the sth chunk. As a result of this determination, when xmax words having a non-zero word value are found, the automatic suggestion subsystem 100 stores index set information indicating the position of the non-zero word in the corresponding chunk in the temporary variable u. To do.

..... number 11

The x-th non-zero word indexed in set u is denoted w (u, x). As shown in Expression 12, when there are a plurality of non-zero words, the automatic suggestion subsystem 100 creates a plurality of chunk change proposals c ′ that leave any one of them.

.... Number 12

Further, the automatic suggestion subsystem 100 further sets the bit value 1 to w (u, x) described above in the chunk change plan (or the chunk that has passed the multiple allocation first determination) as shown in Equation 13. A multiple assignment second determination is performed to check the number of bits.

・ ・ ・ ・ ・ ・ ・ Equation 13

If the non-zero word w (u, x) includes a plurality of bits having a bit value of 1 and the constraint is not satisfied in the determination of Equation 13, the automatic proposal subsystem 100 leaves one of them. Create word change plan w '. A set of indexes indicating the position of the bit value 1 in a non-zero word is denoted by v. Further, a function SHIFT () in which only the bit value at the position (v, y) is 1 is used. At this time, the word change plan w ′ (u, x) (v, y) in which the bit value 1 at the bit position (v, y) in w (u, x) is left is obtained by Equation 14.

..... number 14

Hereinafter, the notation of u and v is omitted, and the position of the yth bit in the xth word is referred to as a bit position (x, y). The automatic proposal subsystem 100 obtains a chunk change proposal h (x, y) by replacing w ′ with the corresponding word of the input plan as shown in Equation 15.

.... Number 15

When it is determined that the constraint is not satisfied in either or both of the above-described multiple allocation first determination and multiple allocation second determination, the automatic proposal subsystem 100 generates a plurality of chunk change proposals h (x, y). Their combination is a component of the proposal plan. At that time, if there is an existing allocation plan in another chunk at the bit position where the bit value in the chunk change proposal h (x, y) is 1, a multiple allocation constraint violation occurs. Therefore, as shown in Expression 16, the automatic proposal subsystem 100 calculates the logical product of the negation of the chunk h (x, y) and the other chunks, so that the existing allocation in the other chunks is associated with the combination. Create a released chunk set. This is called a solution candidate X ′. A plurality of solution candidates X ′ are created along with the cancellation of the multiple allocation in the chunk. Further, if there are a plurality of chunks including multiple assignments in the input plan, the automatic proposal subsystem 100 creates a solution candidate X ′ as a combination thereof. The number of solution candidates X ′ is based on the number of bits 1 in the chunk. In the solution candidate X ′, the multiple assignment in the chunk is canceled.

・ ・ ・ ・ ・ ・ ・ Equation 16

<Step SC: Solution Search Method, Canceling Multiple Allocation between Chunks>
Next, the automatic suggestion subsystem 100 eliminates multiple allocations among a plurality of chunks. As shown in Equation 10, when there are multiple allocations between chunks, if the exclusive OR of the chunks is calculated cumulatively, the exclusive logic is found at the place where the second 1 is found at the same bit position. The cumulative value of the sum decreases. The chunk in which the problem is detected using Equation 10 is the foundth. The automatic suggestion subsystem 100 here can find the lost-th chunk that collided with the found-th chunk by examining the cumulative value of the exclusive OR in reverse order as shown in Equation 17. In the processing so far, since the multiple allocation in the chunk is canceled, if a collision occurs, the two chunks have the same value.

..... 17

Here, as shown in Expression 18, the automatic suggestion subsystem 100 creates a chunk correction proposal in which either the found th chunk or the lost th chunk is zero. There can be multiple chunk correction proposals. Further, the solution candidates X ″ are solution candidates in which the chunk correction proposal is reflected in the input plan. A plurality of solution candidates X ″ can be created along with the cancellation of multiple allocation between chunks. The number of solution candidates X ″ is based on the number of collision bits at the same position. By the processing of Equation 18, multiple allocation within and between chunks in solution candidate X ″ is canceled. That is, in the following, it is summarized into unallocated problems within and between chunks in the solution candidate X ″.

When creating a solution candidate X ″ based on the solution candidate X ′, the number of proposed plans to be searched is the arithmetic product (mh ′) of the number mh ′ of solution candidates X ′ and the number mh ″ of solution candidates X ″. '* Mh ") is the maximum value. When the bit position that has been assigned in multiple chunks simultaneously corresponds to multiple assignment between chunks, the number of proposed plans is less than the arithmetic product.

..... number 18

<Step SC: Solution Search Method, Allocation of Unallocated Resources>
An unassigned chunk can be included in an input plan that is determined not to have multiple assignments (or a solution candidate that has canceled multiple assignments is also referred to as an input plan below). In this case, as shown in Equation 19, when the value of a certain chunk is zero, the automatic suggestion subsystem 100 determines that the chunk is not assigned.

・ ・ ・ ・ ・ ・ ・ Equation 19

Here, as shown in Expression 20, when the automatic suggestion subsystem 100 calculates the logical sum of the plurality of chunks cumulatively, the bit value corresponding to the logical sum at the bit position that is not allocated among the plurality of chunks. Results in zero. This is equivalent to determining that there is an unallocated plan and that a non-zero bit position is unallocated if the negation of the logical sum is not zero. Unlike the sum calculation of a plurality of bits as shown in Equation 2, the logical sum operation is performed in parallel on a variable unit basis, so the processing is fast.

.... Number 20

When there are m unallocated chunks in a plan without multiple allocation, the number of unallocated chunks (the number of bit positions where a specific bit position is unallocated in all chunks) is m in principle. In the heuristics where the input plan is the starting point of the search, the solution space is first limited to a range of planning problems extracted from unassigned m people and m tasks, and all cases are searched. On the assumption that the input plan is close to the constraint satisfaction solution, m << n holds. Therefore, the total number m of constraint satisfaction solutions for the selected planning problems! (M factorial) is the total number n of constraint satisfaction solutions of the original planning problem! Small enough.

A supplementary explanation will be given for the efficiency of solution search. In the problem shown in Equation 1, there are 2 ^ ^{(n * n)} solution candidates in the entire solution space, and the infeasible solution occupies the majority. The brute force method uses n brute force heuristics systematically in order of mechanical indices for feasible constraint satisfaction solutions. This refers to a method of picking out constraint satisfaction solutions. In this brute force method, the amount of calculation with a large n is extremely large, and it is often impossible to extract all constraint satisfaction solutions within a practical time. In addition, if the search is interrupted, the brute force method only finds a location that is biased in the solution space (for example, the assignment of a specific person is fixed), which is far from the input plan. There was a problem that was likely to result only in results. On the other hand, the neighborhood search method of this embodiment is practically fast, and shows a specific method for obtaining a reasonable solution in the vicinity of the input plan even when the processing is interrupted in the middle.

<Step SC: Solution Search Method, Wide Area Search Starting from Unassignment Cancellation>
The neighborhood search method described above is one of the heuristic solutions, and a better solution at a distance from the neighborhood may be overlooked. Metaheuristics is a technique that prevents heuristic solutions from being satisfied with the discovery of a local optimal solution. In the case of the neighborhood search method, a method of randomly including solution candidates that do not improve the situation in the search range, a method of using a plurality of search start positions, or the like can be used. Actually, the solution candidates obtained by the allocation of the unallocated resources described above do not include a solution candidate that allocates an existing allocation in the input plan to another resource. However, in practical planning work, there are not a few occasions when existing assignments are canceled. Therefore, in an input plan with no multiple assignments and no assignments, wide area search metaheuristics is added to search for combinations that can be executed starting from the unassignment. In particular, it involves releasing another existing assignment to resolve an unassigned location.

Here, a method for eliminating unallocated chunks will be described. When the z-th chunk is unallocated in the chunk and has not been searched in the resource management list bh, the automatic suggestion subsystem 100 sets a bit at a position (x, y) as a subset as shown in Equation 21. A change word w (x, y) in which the value 1 is set is created.

・ ・ ・ ・ ・ ・ ・ Equation 21

Furthermore, the automatic suggestion subsystem 100 checks the value of the exclusive OR of the xth word aw (x) and the changed word w (x, y) in the resource management list ah. When the bit value 1 of the change word hits a bit position that is zero in the resource management list, the value of the exclusive OR becomes larger than the value of the list. Here, as shown in Expression 22, the automatic suggestion subsystem 100 narrows down candidates for the bit position (x, y) to be changed by this identification method, and updates the resource management list using the logical sum for the changed position. To do.

........ 22

Further, as shown in Equation 23, the automatic suggestion subsystem 100 sets the chunk correction plan h as an array in which the bit value 1 is set only in the zth unallocated chunk, the xth word, and the yth bit position in the input plan. (X, y, z) is created.

.... Number 23

Next, as shown in Expression 24, the automatic suggestion subsystem 100 creates a logical product with the negation of the chunk correction plan h (x, y, z), and creates a solution candidate X ′. Since the existing allocation is canceled by this logical product, a new multiple allocation resulting from the cancellation of the unallocation does not occur. However, new intra-chunk unallocation due to cancellation of unallocation can occur. To cope with this, the automatic suggestion subsystem 100 updates the resource management list bh so that the bit value of the position z is 1.

.... Number 24

Next, a method for eliminating unallocation between chunks in a solution candidate will be described. When there is unallocated intra-chunk in the solution candidate X ′, another solution candidate can be searched by repeatedly applying the method for eliminating unallocated in the chunk. Here, the automatic suggestion subsystem 100 determines whether or not the z-th chunk can be replaced using the resource management list bh. As shown in Equation 25, when the bit position where unallocation occurs among a plurality of chunks is (x, y), the automatic proposal subsystem 100 creates a chunk change proposal having a bit value of 1 only at that position. . Furthermore, the automatic suggestion subsystem 100 creates a solution candidate that is replaced with an existing chunk.

.... Number 25

Similar to the logical product operation used in the method for resolving unallocated chunks, this swap operation does not take into account existing allocations. Therefore, new unallocated chunks are generated at the bit positions where existing allocations exist. sell. In that case, it becomes a solution candidate including unallocated between chunks. The automatic suggestion subsystem 100 can search for solution candidates one after another by repeatedly applying a method for eliminating unallocation between chunks under the constraints of the resource management lists ah and bh.

  When there is no multiple allocation for a certain solution candidate and all the unallocations in the chunk are eliminated, the solution candidate is a constraint-satisfying solution without examining the relationship between the chunks. Similarly, when there is no multiple assignment for a certain solution candidate and all unassignments between chunks are eliminated, the solution candidate is a constraint satisfaction solution. The automatic proposal subsystem 100 can search for all constraint satisfaction solutions by examining solution candidates one after another and repeatedly searching for any approach. Since the resource management list accompanies the solution candidate and contributes to the suppression of the search range, the same solution is not searched twice even if two approaches of unassigned cancellation within a chunk and unassigned cancellation between chunks are used together. That is, it always converges while searching for possible combinations.

With the above processing, the automatic suggestion subsystem 100 can search for all constraint satisfaction solutions starting from the initial input plan. In comparative evaluation between a plurality of constraint satisfaction solutions, the optimal solution may be compared and extracted using the formula (4).
<Effects of computational complexity compared to the basic implementation method implemented according to the basic formula>
Next, the effect that the solution according to the present embodiment is superior in terms of calculation compared to the existing solution that solves the allocation planning problem will be described. In the processing method based on a logical operation using a bit set in this embodiment, the logical operation corresponds to parallel processing of a plurality of bit information, and the processing is fast.

  Here, the effect of the number of calculations of the constraint condition evaluation method will be described first. As a comparison, the calculation amount of the basic mounting method implemented according to the formulas 2 and 3 will be considered first. In the basic implementation method for the solution candidate X of the n * n matrix satisfying the constraint condition, the addition operation is performed (2 × n × n) times in two directions, and the 2n total values are compared with 1. The operation is performed 2n times to determine whether there is a problem.

  On the other hand, in the method of the present embodiment, by utilizing the fact that there are many zero values in the plan X that satisfies the constraints to some extent, p-bit (p × q = n) words are used in the processing in the chunk (horizontal direction). , N × (p + q) logical operations are performed. The number of comparisons with the zero value is (q + 1) times. Further, in the processing between chunks (vertical direction), by using the exclusive OR feature that reacts to the change of the bit value, n chunk logic operations (n × q words in terms of implementation) are cumulatively performed. Logical operation). The number of comparisons with the cumulative value of the exclusive OR is n times. That is, the total number of calculations related to the two constraints is (n × (p + 2q)) times, and the total number of comparisons is (n + q + 1) times.

  Since there is a definition of p × q = n, 2 × n × n> (n × (p + 2q)) and 2n> (n + q + 1) hold. Therefore, the method of the present embodiment has a smaller number of calculations than the basic mounting method, and is faster with less memory.

  If the solution candidate does not satisfy the constraint, a comparison operation is added that specifies the bit position in question in the chunk or word. Even in this case, if the input plan is a sparse state with many zero values (the number of non-zero words is k (k << n)), the number of comparison operations of the method in this embodiment is n *. (P + k * q), which is less than the number of comparison operations n * n of the basic method and is advantageous. That is, the expression of this embodiment is practically faster than the basic mounting system.

Next, the effect on the calculation amount of the solution search will be described. In the problem shown in Equation 1, there are 2 ^ ^{(n * n)} solution candidates in the entire solution space, and the infeasible solution occupies the majority. The brute force method uses only heuristics to execute only the constraint satisfaction solutions that can be executed in a mechanical index order. A method of picking out (n factorial) constraint satisfaction solutions. Since the calculation cannot be performed in polynomial time, the amount of calculation of the brute force method with a large n is extremely large, and it is often impossible to extract all constraint satisfaction solutions within a practical time. In addition, if the search is interrupted, a result in which only a biased place in the solution space is examined (for example, the assignment of a specific person is fixed) is obtained, and only a result that is far from the input plan is obtained. There was a drawback that was not likely to be a situation.

On the other hand, the theoretically worst input in the system of this embodiment is a case where all bit values are 0 in the input plan, and no task is assigned to anyone. At this time, the determination of multiple allocation passes, but n! It takes as many searches as there are street constraint satisfaction solutions. For this reason, it is almost the same as the brute force method. However, since a plan that is reasonably reasonable is used on the assumption that it is the initial value of the input plan, if the number of unallocated resources in the input plan is m (m << n), the number of constraint satisfaction solutions is m! << n! Therefore, in many cases, the processing can be completed earlier than the brute force method.
--- Second Embodiment ---
In the second embodiment, an example in which the planned task support technology of the present embodiment is applied to a railway crew member operation / organization task will be described. The task of planning which train a railway crew member is in charge of is called an operation organizing task, and is a task that is required to solve an assignment problem similar to that in the first embodiment. Therefore, the mathematical formulas and diagrams used in the description of the second embodiment are the same as those in the first embodiment, and the description of the same configuration and operation is omitted. In the second embodiment, a description will be mainly given of differences that occur in the flows of FIGS. 5 and 6. 9 to 11 and Expressions 26 to 35 will be used to explain mainly the processing corresponding to the overall solution search.

  First, the processing contents of the automatic suggestion subsystem 100 in the second embodiment will be supplementarily described with reference to FIG. In this case, in step 303, the automatic suggestion subsystem 100 outputs the unsatisfied part of the input plan to the user terminal 300 as an alarm for the user. In addition, the automatic suggestion subsystem 100 receives from the user terminal 300 an instruction to search for a local option that locally satisfies the constraint indicated by the alarm.

  Next, in step 304, the automatic suggestion subsystem 100 searches for local options from the situation information 216 in which the crew and train information is stored. This local option is information consisting of a proposal (train, crew), reason for proposal, and order of proposal. In the reason for suggestion information, a predetermined character corresponding to the search content based on the search key used when searching is used. Create a column. The logic of what to search for what kind of alarm is predetermined and stored in the storage device 101 as a plurality of patterns.

  In step 305, the automatic proposal subsystem 100 matches the above-mentioned local options with the proposal plan (overall solution) calculated in step 302. Specifically, if a local option is included in a certain proposal plan, the attribute information of the proposal plan (for example, the local option forms part of the optimal solution) is used as the character of the proposal reason information. Add to the column. By adding the characteristics of the overall solution to the reason for the proposal, the user viewing it can match each proposed local plan while matching the proposed plan that is the overall solution with the sequential local options. It can be determined whether the proposal is an element that leads to an optimal solution. Since proposal reason information is strengthened, it can support a user's decision making.

  Subsequently, in step 306, the automatic suggestion subsystem 100 outputs a screen 503 exemplified in FIG. 10 to the user terminal 300. This screen 503 is a screen example in which attribute information (such as an optimal solution) of the proposed plan is output to the user terminal 300. In such a screen 503, when the crew members who are on the train of “train number 35” are not assigned, the crew numbers “102”, “103”, and “104” can be assigned. The search result is output as a proposal.

  Next, in step 307, the automatic proposal subsystem 100 receives from the user terminal 300 that the above-mentioned user has selected the desired proposal on the screen 503, and reflects the corresponding proposal (train, crew member) in the input plan to change the state. Let If there are still unsatisfied locations in the plan that has made the state transition, the automatic suggestion subsystem 100 returns the process to step 303 and repeats these processes to execute problem solving interactively. Or you may carry out control or operation guidance so that a proposal plan may be accepted at once, without solving interactively.

  Here, with reference to FIG. 6, the processing contents of the overall solution search in the second embodiment will be supplementarily described. In this case, the automatic suggestion subsystem 100 specifies at which time the constraint is not satisfied when evaluating the solution in step 404, and uses the time information (˜m) as the attribute information 221 of the solution candidate. The data is stored in the storage device 201 of the data server 200.

  Subsequently, in step 405, the automatic suggestion subsystem 100 manages whether it has been changed during the search by using the resource management list. The automatic proposal subsystem 100 creates a plan change plan that is consistent with the resource management list, and updates and saves the resource management list for resources (crew, trains, etc.) used in the plan change plan. The resource management list in the second embodiment is one-dimensional array information, and is different from the first embodiment (Equation 8, ah, bh) in that time is added to the type of resource and the length is different. .

  Next, in step 406, the automatic suggestion subsystem 100 evaluates the solution, further creates the attribute information 221 together with the solution candidate satisfying the constraint, and stores it in the storage device 201 of the data server 200.

  In Step 409, the automatic suggestion subsystem 100 outputs the screen 501 illustrated in FIG. 7 to the user terminal 300 when outputting the calculation status. Further, in step 411, the automatic suggestion subsystem 100 sorts the solution candidates in the order of evaluation values, thereby determining the superiority or inferiority of the solution or the optimum solution. In this step 411, the automatic suggestion subsystem 100 outputs the above sort result to the user terminal 300 as the screen 502 illustrated in FIG. The solution with the maximum specific evaluation value is the Pareto optimal solution. The solution having the maximum specific evaluation value in the searched range even when the search is interrupted is called a Pareto optimal solution candidate.

  FIG. 9 is an explanatory diagram of the plan information 950 in the second embodiment. The plan information 950 shown in FIG. 9 expresses, as a 1-bit position information, a plan for when and what work (train crew, station waiting, etc.) a crew member is assigned using a bit set. A quantum time axis is provided for each time unit, and the end time is m. On the horizontal axis, in addition to the number of crew n, a special crew number (0) indicating the berth of the train is provided. On the vertical axis, in addition to the number of trains a and the number of stations b, a special position number (0) indicating the occupancy of the crew is provided. That is, one plan information as a whole constitutes m × (n + 1) × (a + b + 1) three-dimensional bit sets. There may be more dimensions than three dimensions.

  Even if the plan information 950 has a three-dimensional structure, it can be stored in a word or chunk variable as shown by the plan information 550 in FIG. A bit set in the time axis direction may be stored in a word variable. The automatic suggestion subsystem 100 can process information of a plurality of bits in parallel by a logical operation that manipulates these variables. Further, as in the first embodiment, constraint condition evaluation, solution search, and solution evaluation can be processed at high speed in units of variables.

  The constraints that the plan information 950 should satisfy include the following. In the vertical direction of the crew row, in principle, one bit has a value of 1. That is, a crew member cannot exist in two places at the same time, but exists somewhere. This condition is equivalent to the condition of Formula 2 in the first embodiment.

  Further, the constraint condition to be satisfied by the plan information 950 further includes a condition that the number of bits having a value of 1 is 0 or more in the horizontal direction of the business line. That is, a plurality of crew members can ride on a certain train. This condition relaxes the condition of Equation 3 in the first embodiment, but is affected by other related complicated constraints. If the number of bits whose value is 1 is 0, there are no assigned crew members (constraints are not satisfied). If there are 1, the crew members in charge are present. If there are 2 or more bits, the flight crew members are in addition to the crew members in charge. Exists. In addition, restrictions such as ensuring that the crew's place of stay is the same in the initial plan and the proposed plan after the change, and securing transit time to the train are added.

  In another example of configuring the plan information 950, when many of the components are zero values, block variables having a plurality of chunks spanning time and space as a group variable may be used as the operation unit. At this time, by using a compression status variable, which is another bit set representing only the presence or absence of a block variable, the data capacity of the plan information can be greatly reduced, and the number of logical operations of the variable can be greatly reduced. That is, processing can be performed at high speed while saving resources. By comparing the element value of the compressed status variable with zero, the status can be determined directly from the compressed plan information.

In another example of the plan information 950, a plurality of chunk variable sets are grouped in units of time, and this is used as one slice variable. A one-dimensional bit set indicating the presence or absence of a slice variable having a non-zero value is referred to as a compression status variable sh (size m). The compressed plan information can be configured by the compression status variable sh and a plurality of slice variable sets whose values are non-zero. When slice variables at time t and time (t + 1) have the same value, that is,
Val (sh (t)) = Val (sh (t + 1))
The (t + 1) th element value of the compression status variable sh is set to zero. In the method of decompressing the compressed plan information, first, if the t-th element is non-zero, the corresponding slice variable in the slice variable set is set as the t-th time information of the plan information. Further, if the (t + 1) th element of the compression status variable sh is zero, the tth slice variable in which the element of the compression status variable sh becomes non-zero before (t + 1) is set in the plan information. In this way, the same plan information as before compression can be reconstructed. Even if the reconstruction is not performed, if the element value of the compression status variable sh is zero, the processing of the slice is in the same status as the previous time, and may be excluded from the situation determination and solution candidate creation targets. Memory can be saved and resources can be processed at high speed.

  Note that there are a variety of conditions for the constraint conditions to be satisfied by the plan information 950. There are certain restrictions on train operation according to train connections and timetables, and in order to reflect these restrictions in the plan, data used in later calculations is created in advance. Each bit value in the bit set has a corresponding real information and physical object so that there is a unique train number corresponding to a particular train. In a bit set, a sequence of bit values is a direct index. Therefore, the real information is arranged in the corresponding order, and the real information is created and stored in the attribute information 221 in advance.

  Equations (26) to (29) indicate variables that are created in advance and stored in the memory 203 and the data server 200 before the overall solution search processing in step 302 in the automatic proposal processing unit 110 of the automatic proposal subsystem 100.

As shown in Equation 26, the plan information 950 is type-defined as a variable of the three-dimensional bit set B. The variable B is technically equivalent to the conceptual diagram shown in FIG. This represents a plan for allocating (a + b) tasks to n people every time until time m. For example, when the bit value of the variable B is 1, the task corresponding to the crew corresponding to the time is assigned. The task uses the location variable to indicate the position of the crew, whether it is aboard one of the a trains, waits at any of the b train stations, or is unplanned due to a delay (zero value) ). Then, an input plan sB and a proposed plan (or solution candidate) pB are defined as a subset of the set B. These are technically equivalent to the input plan 2181 and the proposal plan 2191.

.... Number 26

Further, as shown in Expression 27, a part of the input plan is extracted to create a subset tT of time and position (train). The subset tT is an operation schedule. For example, when a certain train has a bit value of 1 at a certain time, it indicates that the train is in operation including the work time after arrival before departure. In the operation schedule, the crew may prepare the operation time required for train departure preparation and arrival work after arrival in the train operation time. In that case, the actual train operation time is determined separately in the train operation timetable.

....

As shown in Equation 28, a train timetable jT is created as a bit set. For example, loc (train) that leaves loc_part (departure station) at time_depart (departure time) indicates a plan to arrive at loc_arrive (arrival station) at time_arrive (arrival time). jT is a list of these five items, and corresponds to a timetable that summarizes the relationship between the station and time for each train.

・ ・ ・ ・ ・ ・ ・ Equation 28

Further, as shown in Equation 29, the route information tB is defined as a bit set indicating the relationship between the departure station, the train, and the arrival station. For example, on a certain route, the train job sets the bit value corresponding to location1 to 1 so as to indicate that it is possible to get on at time 1 at the departure station location1. When a predetermined time elapses, the train job arrives at the arrival station location2 at time time2. After time time2, the value of arrival station location2 is set to 1.

.... 29

Here, as shown in the flow of FIG. 6, a method of performing a neighborhood search for reading an input plan sB in step 401 and searching for a proposed plan pB that is an appropriate solution from the solution space using the input plan sB as a starting point of the search will be described. .

  In this case, the sB_per variable shown in Expression 30 is information obtained by compressing the initial plan 2180 and the input plan 2181 of the plan DB 218 for each crew member, and is two-dimensional information indicating the relationship between the place (train) and time. This sB_per variable is created in advance before searching by adding and summing up the bit values of all crew members at a certain time of a train in the plan sB. When the bit value of the sB_per variable is 1, it indicates that a crew member is assigned to the train at the time. In the predetermined plan, crew members are appropriately assigned and satisfy the constraint condition of sB_per shown in Equation 30.

The pB_per variable shown in Expression 30 is information obtained by compressing the solution candidate (suggested plan) by addition and summing in the same manner as the sB_per variable, and is created by the automatic proposal subsystem 100 in step 402. Some pB_per variables may not follow the same constraints as the sB_per variables. When there is a change in the plan, such as when a problem such as a train delay occurs, the constraint condition is not always satisfied.

.... 30

Some contents of the situation analysis processing in steps 402 and 403 will be described with reference to equations 31 and 32 and FIG. In this case, in the formula 31, the rank () function is a function for counting the number of bit values of the proposal plan pB, and the automatic proposal subsystem 100 determines that it is a constraint violation when the calculation result is not 1. Analyze the situation to see if the constraint is satisfied. The expression 31 is equivalent to the process of determining the calculation result of adding and summing the bit values in the vertical direction or the horizontal direction, and corresponds to the constraint condition of the expression 2 or 3 in the first embodiment. Therefore, the automatic suggestion subsystem 100 can perform determination calculation using the same high-speed processing method as in the first embodiment.

..... 31

The table shown in FIG. 11 is a comparison table 1100 for checking whether a crew member is unassigned or assigned to a certain train. Restrictions that should be satisfied by the solution candidate (suggested plan) include that a crew member is assigned to a train that operates, and that a crew member that does not operate does not have a crew member assigned. This constraint condition can be determined by comparing the value of the sB_per variable and the value of the pB_per variable and comparing each bit value with the comparison table 1100 of FIG.

Equation 32 shows a calculation method in which the same determination processing as in FIG. Further, this constraint condition has the effect of parallel processing by processing in units of words or chunks when the exclusive OR calculation shown in Equation 32 is used. In addition, multiple judgment items in the comparison table are judged at the same time by the exclusive OR feature that reacts to different bit values, so it is possible to quickly check whether there is a constraint violation by checking the exclusive OR value against zero. it can.

.... Number 32

The contents of the plan change plan creation at step 405 and the partial contents of the state transition process at step 408 will be described using equations 33 to 36. In this case, the calculation formula shown in Equation 33 indicates a method for searching for a crew member who can be on the train (loc1) after it is determined that the crew member is not assigned to a certain train. First, the automatic suggestion subsystem 100 searches the departure station (loc_depart) of the train from the timetable jT variable using loc1 as a search key. Next, in the input plan (sB), the automatic proposal subsystem 100 searches for all crew members (per) waiting at the same departure station at the departure time (time_depart). The searched crew (per) can be on the train and can continue waiting at the station. The automatic proposal subsystem 100 creates a plan change plan for assigning the crew member thus searched to the train.

........ 33

The calculation formula shown in Expression 34 shows a method in which a crew member (per1) waiting at a station (loc1> a) at a certain time (time1) searches for all trains (loc) that can be boarded. Here, the automatic suggestion subsystem 100 searches the timetable jT for a train (loc) that departs from the station at the time (loc_depart). Further, the automatic proposal subsystem 100 creates a plan change plan that assigns the crew to the searched train.

........ 34

The calculation formula shown in Expression 35 indicates a method for changing the plan information pB, particularly from the viewpoint of the time axis direction, when the operation is changed by the calculation shown in Expression 33 or Expression 34. Consider an operational change where a crew member (per1) is on a train (loc). The train is described in advance in the departure time (time_depart), departure station (loc1), arrival time (time_arrive), arrival station (loc2) and timetable, and the automatic suggestion subsystem 100 refers to the information. . When the automatic proposal subsystem 100 changes the assignment of the crew member in the solution candidate pB, all the crew plans after the arrival time of the train (loc), that is, after the operation ends, are set to zero. Further, the automatic suggestion subsystem 100 sets all bit values corresponding to the crew and the train (loc) to 1 so that the crew rides the train from the departure time to the arrival time. Further, the automatic suggestion subsystem 100 sets all bit values corresponding to the crew and the station (loc2) to 1 so that the station waits at the arrival station during the time zone after arrival.

.... 35

The calculation formula shown in Expression 36 represents a high-speed process equivalent to the plan change using Expression 35. In this case, the automatic suggestion subsystem 100 first creates a mask variable mask. This indicates a step-like signal change around the departure time (time_depart) for the train (loc).

  Next, the automatic suggestion subsystem 100 creates a temporary variable tB indicating the operation status of the train with reference to the operation schedule and timetable. This is composed of train crew (job), position (location), and time (time).

  Next, the automatic suggestion subsystem 100 calculates the logical product of the change in the time direction (t) at the position of the crew (per1) and train (loc) of the plan information pB and the negation of the mask variable. The logical product value of 1 is obtained. That is, the train before the departure time is held for the train before the departure time.

  Next, the automatic proposal subsystem 100 obtains a second logical product value by calculating a logical product of the temporary variable tB and the mask variable. That is, a schedule after the departure time is created.

  Next, the automatic proposal subsystem 100 creates a plan that is aligned in the time axis direction by calculating the logical sum of the first logical product value and the second logical product value. Since the plan created in this way is a part of the plan information and is only scheduled for the crew, the plan is finally reflected in the entire plan information.

.... Number 36

The calculation formula shown in Expression 37 indicates a calculation method for evaluating whether a solution candidate (proposed plan) is a good solution, and is performed in the processing in step 406. The automatic proposal subsystem 100 calculates respective evaluation values for a plurality of solution candidates obtained in the search process. In the neighborhood search method, the proposed plan pB close to the input plan sB is appropriate to some extent. If the calculated inner product value of two solutions in the solution space, that is, sB and pB is e1, e1 indicates the closeness of sB and pB in the solution space corresponding to the intersection angle of the two solution vectors.

In Expression 37, the exclusive OR e2 of sB and pB corresponds to the distance between two solution vectors and indicates the total number of plan changes. E3 indicating the sum of the number of bit values of 1 is an index indicating the total crew time. In addition, various indicators such as total working hours, peak overtime hours, and total number of planned changes can be calculated. The optimization objective function shown in Equation 4 may be used, and conversely, the calculation method of Equation 37 may be used as the solution evaluation method in the first embodiment.

..... 37

According to the present embodiment, it is possible to execute a high-speed solution process for a planning problem, and to search a solution space more widely and quickly within a practical time acceptable by the user, unexpectedly various solutions, more accurate This makes it easier to find approximate solutions and optimal solutions. In addition, by visualizing such a search process, it is easy for the user to determine whether to interrupt the process even in a situation where a long-time calculation is performed.

  That is, it is possible to speed up the solution processing of the planning problem and efficiently obtain a solution with better accuracy than before.

  At least the following will be clarified by the description of the present specification. That is, in the planned task support system according to the present embodiment, the computing device, in specifying multiple allocation and non-allocation of the resource, violates a change in cumulative value when the logical operation is cumulatively performed. The presence / absence and location of the occurrence of an event may be specified. According to this, identification of the violation event becomes more efficient and accurate.

  Further, in the planned task support system of the present embodiment, when the solution candidate is created, the computing device, when the result of specifying the violation event includes multiple allocation of resources in the plan information, The variable A and the zero-value variable B are replaced to create a solution candidate with a predetermined number of bits whose value is non-zero, and as a result of specifying the violation event, resource information is included in the plan information. If unassignment is included, a variable C having a bit position where unassignment has occurred and a variable D in which only the bit value at the bit position is 1 are created, and a solution candidate is created, It is also possible to execute a process of creating a solution candidate by performing a predetermined logical operation between at least one of B and variable D and another variable constituting the plan information. This makes solution candidate creation more efficient based on bit operations.

  Further, in the planned work support system of the present embodiment, the storage device further holds initial plan information that is the plan information that is the basis of the plan information and does not violate a constraint condition, Calculating a dot product value of the initial plan information and the solution candidate, obtaining a first evaluation value of the corresponding solution candidate, and a bit value of an exclusive OR of the initial plan information and the solution candidate Screen for enumerating solution candidates in the order of the evaluation values of the process of obtaining the second evaluation value of the solution candidates by addition and aggregation, and at least one of the first evaluation value and the second evaluation value The process of outputting data to a predetermined device may be further executed. According to this, the user can easily understand and select the appropriateness of the solution candidate, so that the solution search becomes faster and more efficient.

Further, in the planned work support system of the present embodiment, the storage device further holds initial plan information that is the plan information that is the basis of the plan information and does not violate a constraint condition, Calculating a dot product value of the initial plan information and the solution candidate, obtaining a first evaluation value of the corresponding solution candidate, and a bit value of an exclusive OR of the initial plan information and the solution candidate The candidate solutions are listed in the order of the evaluation values for at least one of the process of obtaining the second evaluation value of the solution candidates by addition and aggregation and the first evaluation value and the second evaluation value . Processing for outputting screen data to a predetermined device, and classifying the solution candidates by predetermined level based on an evaluation value, totaling the number of solution candidates for each level, and the total value is equal to or greater than a predetermined value If the solution candidate of the corresponding level Update the surface data, and outputting it to said predetermined device may be a one in which further executes.

  According to this, the visibility of the user is improved when the solution candidate is displayed on the screen, and the corresponding user can more easily understand and select the appropriateness of the candidate solution, and thus the solution search is quicker and more efficient. It will be a thing.

  In the planned task support system according to the present embodiment, the arithmetic device may further execute a process of outputting a processing status relating to the solution candidate to a predetermined device.

  This makes it easy and accurate for the user to understand the solution search process and determine whether or not to interrupt the process, avoid waste in the entire process, and thus make the solution search faster and more efficient.

  Further, in the planned work support system of the present embodiment, the storage device includes, as the plan information, n crew members, a trains, b stations, and time information in units of m hours. Is stored in a three-dimensional or more bit set of n × (a + b) × m, which is expressed as a Boolean value with respect to the presence or absence of allocation in the time and position, and the arithmetic unit stores the i th train in the plan information A bit value 1 is set from the departure time to the arrival time of the train in the time range m when the j-th crew member is assigned and the plan candidate is changed while the plan before the departure time of the train is saved. It is operation information in which the other is 0, a process of creating a first bit set of length m, and a mask in which the bit value is 0 before the departure time of the train in the time range m and the other is 1 A process for creating a second bit set of length m, negation of the mask and a first logical product of the plan information, and a second logical product of the mask and the operation information. Then, a process of calculating a logical sum of the first logical product and the second logical product may be executed.

  According to this, it is possible to execute a high-speed solution process for a personnel allocation plan related to railway operation, and to search for a solution space more widely and quickly within a practical time acceptable by the user. It is easier to find good approximate solutions and optimal solutions. That is, it is possible to speed up the solution processing of the personnel allocation planning problem related to railway operation, and to efficiently obtain a solution with better accuracy than before.

  Further, in the planned task support method of the present embodiment, the information processing system, based on the change tendency of the accumulated value when the logical operation is cumulatively performed when the multiple allocation and unallocation of the resource are specified, It may be possible to identify the presence and location of a violation event.

  Further, in the planned work support method of the present embodiment, when the information processing system creates the solution candidate, if the plan information includes multiple allocations of resources as a result of specifying the violation event, multiple allocation is performed. A variable candidate A and a zero-value variable B are replaced to create a solution candidate with a predetermined number of bits whose value is non-zero, and a specific result of the violation event is a resource in the plan information. If a variable C having an unallocated bit position is replaced with a variable D in which only the bit value at the bit position is 1, the process of creating a solution candidate, A process of creating a solution candidate by performing a predetermined logical operation between at least one of the variable B and the variable D and another variable constituting the plan information may be executed.

  Further, in the planned work support method of the present embodiment, the information processing system further holds initial plan information that is the plan information that is the basis of the plan information and does not violate a constraint condition in the storage device, A process of calculating an inner product value of the initial plan information and the solution candidate, obtaining a first evaluation value of the corresponding solution candidate, and adding a bit value of an exclusive OR of the initial plan information and the solution candidate Summarizing and obtaining the second evaluation value of the solution candidate, and screen data listing solution candidates in the order of the evaluation value for at least one of the first evaluation value and the second evaluation value May be further executed.

Further, in the planned work support method of the present embodiment, the information processing system further holds initial plan information that is the plan information that is the basis of the plan information and does not violate a constraint condition in the storage device, A process of calculating an inner product value of the initial plan information and the solution candidate, obtaining a first evaluation value of the corresponding solution candidate, and adding a bit value of an exclusive OR of the initial plan information and the solution candidate A screen in which solution candidates are listed in the order of evaluation values for at least one of the first evaluation value and the second evaluation value, and a process of collecting and obtaining the second evaluation value of the solution candidates A process of outputting data to a predetermined device, and the solution candidates are classified according to predetermined levels based on evaluation values, and the number of solution candidates is totaled for each level, and the aggregated value is equal to or greater than a predetermined value Of solution candidates at the corresponding level Update the serial screen data, and outputting it to said predetermined device, it may further executes.

  In the planned task support method of the present embodiment, the information processing system may further execute a process of outputting a processing status related to the solution candidate to a predetermined device.

  Further, in the planned work support method of the present embodiment, the information processing system uses the storage device as the plan information for n crew members, a trains, b train stations, and time information in units of m hours. Stores a bit set of three or more dimensions of n × (a + b) × m, which is expressed as a Boolean value with respect to whether or not there is an allocation in time, a position indicating a crew member, a train or a station, and the j-th train in the plan information When preparing a solution candidate to change the plan while saving the plan before the departure time of the train and assigning the other crew members as the bit value 1 from the departure time to the arrival time of the train in the time range m The operation information to be 0, a process for creating a first bit set of length m, and a mask in which the bit value is 0 before the departure time of the train in the time range m and the others are 1. Thus, the process of creating the second bit set of length m, the negation of the mask and the first AND of the plan information are calculated, and the second AND of the mask and the operation information is calculated. Then, a process of calculating a logical sum of the first logical product and the second logical product may be executed.

10 Planned Work Support System 20 Network 100 Automatic Proposal Subsystem 101 Storage Device 102 Program 103 Memory 104 Arithmetic Device 105 Communication Device 110 Automatic Proposal Processing Unit 111 Logical Operation Processing Unit 112 Input / Output Processing Unit 200 Data Server 215 Calculation Log 216 Status Information 217 Business model 218 plan DB
2180 Initial plan 2181 Input plan 219 Solution candidate DB
2190 solution candidate 2191 proposal plan 220 approval plan 221 attribute information 300 user terminal 400 situation change contact machine

Claims (14)

A predetermined number of bit string variables based on the number of resources to be allocated to events are combined in a predetermined set according to the number of events, and plan information indicating each allocation state of multiple resources for multiple events is stored in the bit string A storage device to
For the violation event of the predetermined constraint condition in the plan information, the multiple allocation of resources by performing a predetermined logical operation with a predetermined value for each bit string of each variable and each bit corresponding to the same resource between the variables, and Identify as unallocated, create a solution candidate by changing the bit string of the corresponding variable in the plan information by a predetermined algorithm to eliminate the violation event, replace the solution candidate and the plan information, and replace the violation event An arithmetic unit that generates output plan information by repeating the process of creating a solution and creating a solution candidate;
A planning work support system characterized by comprising: The arithmetic unit is
In specifying multiple allocation and non-allocation of the resource, the presence / absence and location of a violation event is specified based on a change tendency of a cumulative value when the logical operation is cumulatively performed. The planned work support system according to claim 1. The arithmetic unit is
In creating the solution candidate,
As a result of specifying the violation event, if multiple allocations of resources are included in the plan information, the number of bits whose value is non-zero can be obtained by substituting the variable A and the zero value variable B that are multiple allocations. A process of creating a predetermined number of solution candidates;
As a result of specifying the violation event, if the plan information includes unallocated resources, a variable C having a bit position where unallocation has occurred and a variable D in which only the bit value of the bit position is 1 are set. Processing to create a solution candidate by replacing,
A process of creating a solution candidate by performing a predetermined logical operation between at least one of the variable B and the variable D and another variable constituting the plan information;
Is to perform
The planning work support system according to claim 1, wherein: The storage device
It is the plan information that is the basis of the plan information, and further retains the initial plan information without any constraint violation,
The arithmetic unit is
A process of calculating an inner product value of the initial plan information and the solution candidate, and obtaining a first evaluation value of the corresponding solution candidate;
A process of adding and summing up bit values of exclusive OR of the initial plan information and the solution candidate to obtain a second evaluation value of the solution candidate; and
A process of outputting screen data listing solution candidates to a predetermined device in the order of the evaluation values for at least one of the first evaluation value and the second evaluation value;
Is to further execute
The planning work support system according to claim 1, wherein: The storage device
It is the plan information that is the basis of the plan information, and further retains the initial plan information without any constraint violation,
The arithmetic unit is
A process of calculating an inner product value of the initial plan information and the solution candidate, and obtaining a first evaluation value of the corresponding solution candidate;
A process of adding and summing up bit values of exclusive OR of the initial plan information and the solution candidate to obtain a second evaluation value of the solution candidate; and
A process of outputting screen data listing solution candidates to a predetermined device in the order of the evaluation values for at least one of the first evaluation value and the second evaluation value;
The solution candidates are classified according to predetermined levels based on evaluation values, the number of solution candidates is totaled for each level, and the screen data of solution candidates at the corresponding level when the total value is equal to or greater than a predetermined value Updating and outputting this to the predetermined device;
Is to further execute
The planning work support system according to claim 1, wherein: The arithmetic unit is
A process of outputting the processing status related to the solution candidate to a predetermined device is further executed.
The planning work support system according to claim 1, wherein: The storage device
As the plan information, n crews, a trains, b stations, time information in units of m hours, positions indicating crews, trains or stations, and presence / absence of allocation in time are expressed by Boolean values n × (A + b) × m 3D or higher bit set is stored,
The arithmetic unit is
In creating the solution candidate for changing the plan while allocating the j-th crew member to the i-th train in the plan information and preserving the plan before the departure time of the train,
A process of creating a first bit set of length m, which is operation information in which a bit value is 1 from the departure time to the arrival time of the train in the time range m and the others are 0;
A mask having a bit value of 0 before the departure time of the train in the time range m and 1 being the other, and creating a second bit set of length m;
A first AND of the mask and the plan information is calculated, a second AND of the mask and the operation information is calculated, and a logical AND of the first AND and the second AND The process of calculating the sum;
Is to perform
The planning work support system according to claim 1, wherein: A predetermined number of bit string variables based on the number of resources to be allocated to events are combined in a predetermined set according to the number of events, and plan information indicating each allocation state of multiple resources for multiple events is stored in the bit string An information processing system including a storage device
For the violation event of the predetermined constraint condition in the plan information, the multiple allocation of resources by performing a predetermined logical operation with a predetermined value for each bit string of each variable and each bit corresponding to the same resource between the variables, and Identify as unallocated, create a solution candidate by changing the bit string of the corresponding variable in the plan information by a predetermined algorithm to eliminate the violation event, replace the solution candidate and the plan information, and replace the violation event Generate output plan information by repeating the process of creation and solution candidate creation,
Planning work support method characterized by this. The information processing system is
In specifying multiple allocation and non-allocation of the resource, based on the change tendency of the cumulative value when the logical operation is performed cumulatively, the presence and location of occurrence of a violation event is specified,
The planning work support method according to claim 8, wherein: The information processing system is
In creating the solution candidate,
As a result of specifying the violation event, if multiple allocations of resources are included in the plan information, the number of bits whose value is non-zero can be obtained by substituting the variable A and the zero value variable B that are multiple allocations. A process of creating a predetermined number of solution candidates;
As a result of specifying the violation event, if the plan information includes unallocated resources, a variable C having a bit position where unallocation has occurred and a variable D in which only the bit value of the bit position is 1 are set. Processing to create a solution candidate by replacing,
A process of creating a solution candidate by performing a predetermined logical operation between at least one of the variable B and the variable D and another variable constituting the plan information;
The planning work support method according to claim 8, wherein: The information processing system is
In the storage device, it is the plan information that is the basis of the plan information, further holding the initial plan information without constraint condition violations,
A process of calculating an inner product value of the initial plan information and the solution candidate, and obtaining a first evaluation value of the corresponding solution candidate;
A process of adding and summing up bit values of exclusive OR of the initial plan information and the solution candidate to obtain a second evaluation value of the solution candidate; and
A process of outputting screen data listing solution candidates to a predetermined device in the order of the evaluation values for at least one of the first evaluation value and the second evaluation value;
The planning work support method according to claim 8, further comprising: The information processing system is
In the storage device, it is the plan information that is the basis of the plan information, further holding the initial plan information without constraint condition violations,
A process of calculating an inner product value of the initial plan information and the solution candidate, and obtaining a first evaluation value of the corresponding solution candidate;
A process of adding and summing up bit values of exclusive OR of the initial plan information and the solution candidate to obtain a second evaluation value of the solution candidate; and
A process of outputting screen data listing solution candidates to a predetermined device in the order of the evaluation values for at least one of the first evaluation value and the second evaluation value;
The solution candidates are classified according to predetermined levels based on evaluation values, the number of solution candidates is totaled for each level, and the screen data of solution candidates at the corresponding level when the total value is equal to or greater than a predetermined value Updating and outputting this to the predetermined device;
The planning work support method according to claim 8, further comprising: The information processing system is
9. The planned work support method according to claim 8, further comprising executing a process of outputting a processing status relating to the solution candidate to a predetermined device. The information processing system is
In the storage device, as the plan information, n crew members, a trains, b stations, time information in units of m hours, positions indicating crew members, trains or stations, and presence / absence of allocation in time Stores a bit set of three or more dimensions of n × (a + b) × m expressed by
In creating the solution candidate for changing the plan while allocating the j-th crew member to the i-th train in the plan information and preserving the plan before the departure time of the train,
A process of creating a first bit set of length m, which is operation information in which a bit value is 1 from the departure time to the arrival time of the train in the time range m and the others are 0;
A mask having a bit value of 0 before the departure time of the train in the time range m and 1 being the other, and creating a second bit set of length m;
A first AND of the mask and the plan information is calculated, a second AND of the mask and the operation information is calculated, and a logical AND of the first AND and the second AND The process of calculating the sum;
The planning work support method according to claim 8, wherein:

Images