[0001]The present invention relates to a schedule creation
assisting device and a schedule creation assisting method.
[Background Art]
[0002]
10 The concept of searching for a solution that maximizes or
minimizes desired parameters under specified conditions, in other words, the concept of what is called a combinatorial optimization problem, can be applied to complex problems in the real world such as eliminating traffic congestion and reducing distribution 15 costs in global supply chains. [0003]
However, in such problems, the number of solution candidates is tremendously large, making it difficult to solve the problem within a practical time unless the computer is one 20 having a relatively high computing power, such as a supercomputer or a quantum computer. [0004]
For example, as a conventional technique related to quantum computers, a technique regarding a computer which enables a high-25 speed computation for an inverse problem or a combinatorial optimization problem requiring an exhaustive search has been proposed in which spins are used as variables in the computation, a problem intended to be solved is set using spin-spin interaction and a local field acting on each spin, all spins are 30 caused to orient toward one direction by an external magnetic field at time t = 0, the external magnetic field is gradually reduced such that the external magnetic field becomes zero at time t = τ, each spin is time-evolved on the assumption that the direction is determined to follow an effective magnetic field 35 determined by all actions of spin-spin interaction and the external magnetic field of each site at time t, and in this process, the directions of the spins are not completely aligned

3
to the effective magnetic fields but are caused to be quantum mechanically corrected directions so that the system can maintain an approximate ground state (see PTL 1). [Citation List] 5 [Patent Literature] [0005]
[PTL 1] WO2016/157333 [Summary of Invention] [Technical Problem]
10 [0006]
Unfortunately, there has not been proposed a configuration in which quantum computer techniques as described above are applied appropriately to the work of creating an overall schedule for a large number of workers who work in cooperation.
15 [0007]
For example, the work of creating schedules of a call center requires creation of weekly or monthly shift schedules for hundreds of operators. In the current situation, an experienced person in charge creates schedules manually under predetermined
20 rules (Example: Shift patterns such as early shifts and late shifts shall be combined and arranged in a fixed order and frequency for a specified period). [0008]
Such schedule creation can be made efficient to a certain
25 extent by using functions in spreadsheet software on a common PC. However, in the case where the number of workers is larger than a certain level, or in the case where there are nonlinear constraint conditions a plurality of which affect one another, it is impossible to obtain a solution within a practical time.
30 Hence, spreadsheet software can deal with only situations in a very small organization having only linear constraint conditions. [0009]
Creation of schedules for the case where a large number of workers work in corporation is greatly affected not only by basic
35 factors such as rules for the number of working days for each worker and the number of necessary workers for each day but also various factors such as circumstances of each worker, workers'

4
vague requests, the work system, and various kinds of rules. In addition, those factors themselves vary depending on the number of workers, the organization that the workers belong to, and demand for the operation, and the factors interfere and affect 5 one another in some cases. [0010]
In addition, there are cases where a sudden change occurs in those factors, such as a sudden increase/decrease in the demand for the operation and abrupt absence of workers. In such
10 situations, even if an attempt was made to create a schedule in a conventional way by using a common PC, the amount of calculation would increase exponentially according to the number of factors, nonlinear constraint conditions, and the like as described above, and the calculation would take an enormous amount of time or lead
15 to an overflow. Simply put, the schedule probably cannot be created at a desired timing. [0011]
Hence, an object of the present invention is to provide a technique for efficiently creating a schedule with nonlinear
20 constraint conditions taken into account for a large number of workers who work in corporation. [Solution to Problem] [0012]
A schedule creation assisting device of the present
25 invention to solve the above object comprising: a storage unit that stores information on a total working time length in a specified period of each of workers who work in cooperation in a specified operation, a number of the workers necessary at each timing during the period, and a constraint condition regarding
30 allocation of the workers to the operation; and a computation unit that computes an Ising model in which, regarding an objective function including, as terms, the total working time length in the period, the number of necessary workers, and a constraint condition function that is minimized when the
35 constraint condition is satisfied, whether each of the workers is to attend at work is set as a spin, and a sensitivity between variables of the constraint condition function is set as an

5
intensity of interaction between the spins, wherein the computation unit outputs, to a specified device, a schedule in which whether each of the workers is to attend at work at the each timing during the specified period is specified based on a 5 result of the computation. [0013]
A schedule creation assisting method of the present invention comprising: by an information processing device including a storage unit that stores information on a total
10 working time length in a specified period of each of workers who work in cooperation in a specified operation, a number of the workers necessary at each timing during the period, and a constraint condition regarding allocation of the workers to the operation, computing an Ising model in which, regarding an
15 objective function including, as terms, the total working time length in the period, the number of necessary workers, and a constraint condition function that is minimized when the constraint condition is satisfied, whether each of the workers is to attend at work is set as a spin, and a sensitivity between
20 variables of the constraint condition function is set as an intensity of interaction between the spins; and outputting, to a specified device, a schedule in which whether each of the workers is to attend at work at the each timing during the specified period is specified based on a result of the computation.
25 [Advantageous Effects of Invention] [0014]
The present invention makes it possible to efficiently create a schedule with nonlinear constraint conditions taken into account for a large number of workers who work in cooperation.
30 [Brief Description of Drawings] [0015]
[Fig. 1] Fig. 1 is a network configuration diagram including a schedule creation assisting device of the present embodiment. [Fig. 2] Fig. 2 is a diagram illustrating an example of a hardware
35 configuration of the schedule creation assisting device in the present embodiment. [Fig. 3] Fig. 3 is a diagram illustrating a timing chart example

6
in the present embodiment.
[Fig. 4] Fig. 4 is a diagram illustrating a procedure example 1
in the present embodiment.
[Fig. 5] Fig. 5 is a diagram illustrating a configuration example 5 of a basic information table in the present embodiment.
[Fig. 6] Fig. 6 is a diagram illustrating a configuration example
of a constraint condition table in the present embodiment.
[Fig. 7] Fig. 7 is a diagram illustrating the configuration
example of the constraint condition table in the present 10 embodiment.
[Fig. 8] Fig. 8 is a flowchart showing a schedule creation
assisting method in the present embodiment.
[Fig. 9] Fig. 9 is a diagram illustrating a screen example in
the present embodiment. 15 [Description of Embodiments]
[0016]
---Regarding Annealing Machine---
As described in the foregoing PTL 1, the applicant of the
present application has developed quantum computing techniques 20 and has been working to solve various problems, for example, in
exhaustive search problems based on big data (including the
concept of combinatorial optimization problems).
[0017]
In general, expectation for quantum computers is high for 25 such exhaustive search problems. A quantum computer uses basic
elements called qubits which represent "0" and "1" simultaneously.
Thus, the quantum computer is capable of calculating all the
solution candidates simultaneously as initial values and has a
possibility of achieving exhaustive search. However, the quantum 30 computer needs to keep quantum coherence over the entire
calculation time.
[0018]
Under these circumstances, a method called adiabatic
quantum computation has come to attract attention (Reference: E. 35 Farhi, et al., "A quantum adiabatic evolution algorithm applied
to random instances of an NP-complete problem," Science 292, 472
(2001).). In this method, a problem is converted such that the

7
ground state of a physical system is the solution, and the solution is sought for through finding the ground state. [0019]
The Hamiltonian of the physical system to which a problem 5 is set is defined as H^p. Here, at the start of computation, the Hamiltonian is not set to H^p, but to another Hamiltonian H^0 which is different from H^p and the ground state of which is clear and easy to prepare. Next, the Hamiltonian is transformed from H^0 to H^p taking a sufficient time. Taking a sufficient
10 time makes the system keep staying in the ground state, providing the ground state of the Hamiltonian H^p. This is the principle of the adiabatic quantum computation. Defining τ as the calculation time, the Hamiltonian is expressed by Expression (1). [Expression 1]
15

The solution is obtained by time evolution based on a Schrodinger equation of Expression (2). [0020] 20 [Expression 2]

Adiabatic quantum computation is applicable to a problem that requires exhaustive search, and it is possible to reach a solution in a one-way process. However, if the calculation 25 process needs to conform to the Schrodinger equation of Expression (2), quantum coherence needs to be kept as in the case of a quantum computer. [0021]
While the quantum computer repeats gate operations on 1 30 qubit or between 2 qubits, adiabatic quantum computation causes

8
interaction over the entire qubit system at the same time, and
thus, the concept of coherence is different.
[0022]
For example, consider a gate operation on a certain qubit. 5 In this case, if there is an interaction between the qubit and
other qubits, it will cause decoherence. But for adiabatic
quantum computation, all the qubits are interacted simultaneously,
and thus decoherence as in this example will not occur. In
consideration of this difference, adiabatic quantum computation 10 is thought to be more robust in terms of decoherence than the
quantum computer.
[0023]
As has been described above, adiabatic quantum computation
is effective for a difficult question that requires exhaustive 15 search. Then, spins are used as variable for computation, and a
problem to be solved is set as interactions between spins and
local fields acting on respective spins.
[0024]
At time t = 0, all the spins are made to be oriented in 20 one direction using an external magnetic field, and the external
magnetic field is gradually reduced such that it becomes zero at
time t = τ.
[0025]
Each spin is time-evolved on the assumption that the 25 direction of each spin is determined according to the effective
magnetic field determined by all the actions at time t which are
the external magnetic field at each site and interactions between
spins.
[0026]
30 In this process, the direction of the spin is not made to
be perfectly aligned with the effective magnetic field but to be
oriented in a direction corrected quantum-mechanically, so that
the system can almost keep the ground state.
[0027]
35 In addition, a term to keep each spin at the original
direction during time evolution (a relaxation term) is added to
the effective magnetic field to improve the convergence of the

9
solution. [0028]
The schedule creation assisting device in the present embodiment on the assumption here is an annealing machine that 5 performs the foregoing adiabatic quantum computation, but, of course, is not limited to this. The present invention can be applied to any device capable of solving combinatorial optimization problems following the schedule creation assisting method of the present invention as appropriate.
10 [0029]
Specifically, the applicable devices include not only hardware for implementing the annealing method using an electronic circuit (a digital circuit or the like) but also hardware using a superconducting circuit or the like. The
15 embodiment is also applicable to hardware implementing an Ising model by a method other than the annealing method. For example, it includes a laser network method (optical parametric oscillation) and a quantum neural network, too. Although part of the concept is different as described above, the present
20 invention can also be realized by using a quantum gate method in which calculation using an Ising model is replaced with gates such as Hadamard gates, rotation gates, and controlled NOT gates. [0030] ---Network Configuration---
25 Hereinafter, an embodiment of the present invention will
be described in detail using drawings. Fig. 1 is a network configuration diagram including a schedule creation assisting device 100 of the present embodiment. [0031]
30 The schedule creation assisting device 100 illustrated in
Fig. 1 is a computer device that efficiently creates schedules in which nonlinear constraint conditions regarding a large number of workers who work in cooperation are taken into account, and specifically, on the assumption here, it is an annealing machine
35 as an example. [0032]
Since an overview of the annealing machine has been already

10
described based on PTL 1, details of the specific configuration,
operations, and the like of the annealing machine will be omitted
as appropriate (the same applies in the following).
[0033]
5 The schedule creation assisting device 100 of the present
embodiment is coupled to a user terminal 200 such that data can be communicated between them via an appropriate network 10 such as the Internet. [0034]
10 The user terminal 200 receives a schedule proposal from
the schedule creation assisting device 100. [0035]
The user of the user terminal 200 is specifically a business entity that has a large number of operators and performs call
15 center operation with them, and on the assumption here, it is an organization such as a financial institution, an insurance company, or a major manufacturer. Examples of the user on the assumption also include a medical institution and a caregiving business entity that have a large number of nurses or caregiving
20 staff members and carry out nursing work or caregiving work for patients or the like. [0036]
In any case, any business entity that allocates a necessary number, which is relatively large, of workers to days or time
25 slots and carries out an operation as a whole can be the foregoing user. In other words, it can be said that the present invention can be applied to the operations of such business entities. [0037]
As a specific example that can be assumed, for example, in
30 the case of creating a schedule for a call center of a bank, the reality is that a person in charge having specified experience manually inputs and creates monthly shift schedules for all the operators in a scale of several hundreds. In other words, such operation is manual work and tends to be dependent on individual
35 skills. [0038]
For this reason, although it is possible to create

11
schedules based on shifts according to fixed rules in a
conventional way, it is difficult to create schedules for
flexibly dealing with irregular shifts or external factors.
[0039]
5 In addition, even if functions or the like in spreadsheet
software are used, it is difficult to create schedules being free from realistic obstacles such as "holiday setting is limited only for Saturdays and Sundays" and "the number of workers that can be dealt with is up to 100".
10 [0040]
The obstacles result from mathematical difficulties and the absence (immature in a strict sense) of techniques for solving the mathematical difficulties. Although spreadsheet software is capable of solving a problem at high speed if the constraint
15 conditions are linear, it has a characteristic that it takes an enormous amount of time to solve a problem with nonlinear constraint conditions. [0041]
Thus, in the case of creating a schedule in a conventional
20 technique as above, as the number of nonlinear constraint conditions regarding elements, in other words, workers or the like increases, the amount of calculation increases exponentially and thus requires a long time to complete calculation. However, employing the schedule creation assisting device 100 using an
25 annealing machine makes it possible to perform calculation, not being much dependent on the increase in the number of elements. [0042] ---Hardware Configuration---
The hardware configuration of the schedule creation
30 assisting device 100 of the present embodiment is as described in Fig. 2 [0043]
Specifically, the schedule creation assisting device 100 includes a storage unit 101, a memory 103, a computation unit
35 104, and a communication unit 105. [0044]
Of these, the storage unit 101 includes an appropriate

12
nonvolatile memory device such as a solid state drive (SSD) or a
hard disk drive.
[0045]
The memory 103 includes a volatile memory device such as 5 RAM.
[0046]
The computation unit 104 is a CPU that performs operation
such as loading a program 102 stored in the storage unit 101 into
the memory 103 and executing it to manage and control the device 10 and that also performs various kinds of determination,
computation, and control processing.
[0047]
The communication unit 105 on the assumption here is a
network interface card or the like that is coupled to the network 15 10 and performs processing for communication with the user
terminal 200.
[0048]
Note that in the case where the schedule creation assisting
device 100 is a stand-alone machine, it is preferable that the 20 schedule creation assisting device 100 further includes an input
device for receiving key input and voice input from the user and
an output device such as a display for displaying processing data.
[0049]
The storage unit 101 stores, in addition to the program 25 102 for implementing the functions necessary for the schedule
creation assisting device of the present embodiment, at least a
basic information table 125 and a constraint condition table 126.
Details of these tables will be described later.
[0050]
30 The program 102, in other words, the algorithm for
implementing the operation as an annealing machine, holds
information on an Ising model 1021 which is a problem to be
solved. This Ising model 1021 is set in advance by the
administrator or the like based on various kinds of information 35 on the operation and workers the information on which needs to
be provided and other information that affects those factors.
[0051]

13
Note that the adiabatic quantum computation described in an overview of the annealing machine is also called another name, quantum annealing, in which the concept of classical annealing is extended into quantum mechanics. Specifically, it can be 5 interpreted that adiabatic quantum computation can originally perform classical operation, and that quantum-mechanical effects were added to the adiabatic quantum computation to improve performance on high speed and the correct answer rate of a solution. In this respect, in the present invention, the
10 computation unit itself is classical but parameters determined quantum-mechanically are introduced in the computation process to achieve a computation method and device that are classical but include quantum-mechanical effects. Here, of course, a configuration having a quantum computer as the computation unit
15 may be employed. [0052]
Based on the above concept, the following example illustrates a classical algorithm to obtain the ground state as the solution and a device to achieve it while describing
20 relationship with adiabatic quantum computation. [0053]
In the schedule creation assisting device 100 on the above premise, N variables sjz (j = 1, 2, ..., N) take a value range of -1 ≤ sjz ≤ 1, and a problem is set using the local fields gj
25 and inter-variable interactions Jij (i, j = 1, 2, ..., N). [0054]
The computation unit 104, dividing the time by m, performs computation discretely from t = t0 (t0 = 0) to tm (tm = τ). To calculate the variable SjZ(tk) at each time tk, the value of the
30 variable of Sjz(tk-1) (i = 1, 2, ..., N) at the previous time tk-1 and the coefficient of the relaxation term, 9pina or 9pinb, are used to calculate Bjz(tk) = {ΣiJijSiz(tk-1) + gj + sgn(sjz(tk-1)) •9pina} •tk/τ or Bjz(tk) = {ΣiJiJSjz(tk-1) + gj + 9pinb.SjZ(tk-1)}•tk/τ. The function f is determined such that the value range
35 of the foregoing variable Sjz(tk) is -1 ≤ sjz(tk) ≤ 1, and Sjz(tk) = f(Bjz(tk),tk) is obtained. As the time step is advanced from t = t0 to t = tm, the foregoing variable Sjz is made closer to -

14
1 or 1. In the end, if sjz < 0, Sjzd is set as Sjzd = -1, and if
Sjz > 0, as Sjzd = 1, and the solution is determined.
[0055]
The coefficient gpinb is, for example, a value between 50% 5 and 200% of the average value of |Jij|. As for the local field gj for the problem setting, the correction term δgj’ may be added to gj’ only for a certain site j’ to increase the magnitude of gj’ only for the site j’. The correction term δgj’ is, for example, a value between 10% and 100% of the average value of
10 |Jij|. [0056]
Next, the basic principle of the annealing machine will be described by starting from a quantum-mechanical description and moving to a classical form.
15 [0057]
The Ising spin Hamiltonian ground-state search problem given by Expression (3) includes a problem in a classification called NP-hardness and is known to be a useful problem (Reference: F. Barahona, "On the computational complexity of
20 Isingspin glass models," J. Phys. A: Math. Gen. 15, 3241 (1982)). [0058] [Expression 3]

Jij and gj are problem setting parameters, and σ^Z is the 25 z component of the Pauli spin matrix and takes an eigenvalue of
±1. The symbols i, j indicate the site of a spin. Ising spins
are variables that can only take values of ±1. Since the
eigenvalue of σ^z is ±1 in Expression (3), it expresses an Ising
spin system. 30 [0059]
The Ising spins of Expression (3) do not have to be literal
spins, but they may be physically anything as long as the
Hamiltonian is described by Expression (3).
[0060]

15
For example, whether each worker is to attend at work can
be associated with ±1, the high and low of a logic circuit can
be associated with ±1, the vertical polarization waves and
horizontal polarization waves of light can be associated with ±1,
5 or the phases of 0 and π can be associated with ±1.
[0061]
In the method shown here as an example, as in adiabatic quantum computation, a system for computation is prepared in the ground state of the Hamiltonian given by Expression (4) at time 10 t = 0. [0062] [Expression 4]

Here, γ is a constant of proportionality determined by the
15 magnitude of the external field that are uniformly applied to all the sites j, and σ^jx is the x component of the Pauli spin matrix. If the system for computation is literal spins, the external field means a magnetic field. [0063]
20 Expression (4) means that a transverse magnetic field is applied, and the case where all the spins are oriented in the x direction (γ > 0) is the ground state. The Hamiltonian for problem setting is defined as an Ising spin system having only z components, but Expression (4) includes the x components of the
25 spins. Hence, the spins during the computation process are not Ising but are vectors (Bloch vectors). At t = 0, the system starts as the Hamiltonian in Expression (4). As time t progresses, the Hamiltonian is gradually changed. In the end, the system is changed to the Hamiltonian expressed by Expression
30 (3) to obtain its ground state as the solution. [0064] [Expression 5]

16

Here, a^ expresses the three components of the Pauli spin matrix as a vector. The ground state is a state in which the spin is oriented in the magnetic field direction, and can 5 be expressed as = B/|B|, where <•> means the quantum-mechanical expectation value. Since in the adiabatic process, the system always seeks to keep the ground state, the direction of the spin always follows the direction of the magnetic field. [0065]
10 The above discussion can be extended to a multi-spin system. At t = 0, the Hamiltonian is given by Expression (4). This means that the magnetic field BjX = y is uniformly applied to all the spins. When t > 0, the x component of the magnetic field is gradually reduced, which is expressed as BjX = y(1 - t/i) . Since
15 the z components are affected by spin-spin interactions, the effective magnetic field is expressed by Expression (6). [0066] [Expression 6]

20 Since the direction of the spin can be defined by
<σ^z>/<σ^X>, if the direction of the spin follows the effective magnetic field, the direction of the spin is determined by Expression (7). [0067]

Expression (7) is a quantum-mechanical description, but since it is expressed by expectation values, Expression (7) is a
25 [Expression 7]

17
relational expression based on classical quantities. This point
is different from Expressions (1) to (6).
[0068]
Since a classical system does not have nonlocal correlation 5 (quantum entanglement) that quantum mechanics has, the direction of the spin is perfectly determined by the local field at each site, and Expression (7) determines the behavior of the classical spin system. Since a quantum system has nonlocal correlation, Expression (7) is modified, which will be described later. Here,
10 the classical system determined by Expression (7) will be described to mention the basic form of the invention. [0069]
Fig. 3 illustrates a timing chart (1) to obtain the ground state of a spin system. Since the illustration in Fig. 3 is
15 based on classical quantities, the spin at site j is expressed by sj not by σ^j. With this, the effective magnetic field Bj in Fig. 3 is a classical quantity. At t = 0, the effective magnetic field Bj in the right direction is applied at all the sites, and all the spins Sj are initialized so that that the spins Sj are
20 directed to the right. [0070]
As time t passes, a magnetic field in the z axis direction and spin-spin interactions are gradually applied to the spins. In the end, the spins are oriented in the +z direction or the -
25 z direction, and the z component of the spin Sj becomes sjz = +1 or -1. Ideally, time t is continuous, but in the actual computation process, time can be discrete to improve the convenience. The following description is based on a case where time t is discrete.
30 [0071]
Since the spins illustrated as an example here have not only z components but also x components, they are vector spins. Behavior as vectors can be understood also from Fig. 3. Y components have not appeared so far in the discussion. The
35 reason is that since the direction of the external field is defined in the xz plane, the external field does not have a y component, and thus <σ^Y> = 0.

18
[0072]
In the assumption here, each spin in the system for computation is a three-dimensional vector having a size of 1 (this is called a Bloch vector, the state of which can be 5 described with a point on a spherical surface). However, in the case of the axes in the example in the figure, only two dimensions need to be considered (the state can be described with a point on a circle). [0073]
10 Here, since γ is constant, Bjx(t) > 0 (γ > 0) or Bjx(t) <
0 (γ < 0) holds. In this case, a two-dimensional spin vector can be described only with a semicircle. Hence, by specifying Sjz with [-1, 1], one variable Sjz determines a two-dimensional spin vector. Thus, in the example here, although a spin is a
15 two-dimensional vector, it also can be expressed as one-dimensional continuous variable having a value range of [-1, 1]. [0074]
In the timing chart of Fig. 3, the effective magnetic field is calculated for each site at time t = tk, and using the
20 calculated value, the direction of the spin at t = tk is calculated with Expression (8). [0075] [Expression 8]

25 Since Expression (8) is what Expression (7) was rewritten
into so that the expression is based on classical quantities, it does not have the mark <•>. Next, the effective magnetic field at t = tk+l is calculated by using the value of the spin at t = tk. The effective magnetic field at each time specifically
30 written is Expressions (9) and (10). [0076] [Expression 9]

19

[Expression 10]

In the following, the spin and the effective magnetic field 5 are calculated alternately according to the procedure schematically illustrated with the timing chart of Fig. 3. [0077]
In a classical system, the size of the spin vector is 1. In this case, each component of the spin vector is expressed as 10 Sjz(tk) = sin θ and Sjx(tk) = cos θ, by using the parameter θ defined by tan θ = Bj z(tk)/Bjx(tk). [0078]
These can be rewritten as Sjz(tk) sin(arctan(Bjz(tk)/Bjx(tk))) and Sjx(tk) 15 cos(arctan(Bjz(tk)/Bjx(tk))). [0079]
As is clear from Expression (9), the variable of Bjx(tk) is only tk, and τ and γ are constants. Thus, Sjz(tk) = sin(arctan(Bjz(tk)/Bjx(tk))) and Sjx(tk) 20 cos(arctan(Bjz(tk)/Bjx(tk))) can be expressed in generalized forms as Sjz(tk) = f1(Bjz(tk),tk) and Sjx(tk) = f2(Bjz(tk),tk), which are functions having Bjz(tk) and tk as variables. [0080]
Since the spin is described as a two-dimensional vector, 25 the two components Sjz(tk) and sjx(tk) appear. However, if Bjz(tk) is determined based on Expression (10), Sjx(tK) is not necessary. [0081]
This corresponds to that the state of the spin can be 30 described only by Sjz(tk) having a value range of [-1, 1]. Since

20
the final solution Sjzd needs to be Sjzd = -1 or 1, if Sjz(τ) > 0,
it is determined that Sjzd = 1, and if Sjz(τ) < 0, it is determined
that Sjzd = -1.
[0082]
5 Fig. 4 illustrates a flowchart in which the algorithm
described above is organized. Here, tm = τ. Each of the steps s1 to s9 in the flowchart of Fig. 4 corresponds to the process at a time in the timing chart of Fig. 3 from time t = 0 to t = τ. Specifically, the steps s2, s4, and s6 in the flowchart
10 correspond to the above Expressions (9) and (10) at t = t1, tk+l, and tm, respectively. The final solution is obtained by determining at step s8 that Sjzd=-1 if sjz < 0 or that Sjzd = 1 if Sjz > 0 (s9). [0083]
15 The description up to this point has shown how the problem
expressed by Expression (3) is solved. Next, a description is given of how a specific problem is expressed by Expression (3) including the local field gj and the inter-variable interaction Jij (i, j = 1, 2, ..., N), by showing a specific example.
20 [0084]
A specific problem, in other words, an Ising model 1021 on the assumption here is an Ising model in which, for example, based on information on the total number of working days of each of the operators working for a call center operation in a
25 specified month, the number of operators necessary for each day in the month, and constraint conditions regarding allocation of each operator to the call center operation, an objective function is set that includes, as terms, the total number of working days for the month, the number of operators necessary for each day in
30 the month, and the constraint condition functions that are minimized when the above constraint conditions are satisfied, and regarding the objective function, whether each operator is to attend at work is defined as a spin, and the sensitivity between the variables of the constraint condition function is
35 defined as the intensity of interaction between the spins. [0085]
In this case, the local field gj on the assumption here is

21
set as the degree of influence on the objective function given by the values of the variables representing the total number of working days for the month, the number of operators necessary for each day in the month, and the constraint condition functions 5 that are minimized when the constraint conditions are satisfied, as described above. [0086]
Through the discussion described above, the inter-variable interaction Jij (related to between the items of the above
10 objective function) and the local field gj are specifically set. Searching for the ground state of the Ising model 1021 expressed by Expression (3) is performed, in other words, searching for the ground state that minimizes the objective function including the total number of working days for the month, the number of
15 operators necessary for each day in the month, and the constraint condition functions that are minimized when the constraint conditions are satisfied is performed. Through the searching, the work shifts for each operator, in other words, the overall schedule for the month for the call center operation is
20 determined. [0087]
Note that the calculation using an Ising model and the annealing method is used only for "minimizing the objective function". Hence, if there are constraint conditions that need
25 to be satisfied when the objective function is minimized, those conditions need to be added to the objective function in some way. [0088]
For example, think about a constraint condition expressed

This constraint condition can be converted into "a function that is minimized when the constraint condition is satisfied", 35 which is the following expression.
30 by Expression (11). [Expression 11]

22
[0089] [Expression 12]

5
10
15


Since the square portion always has a positive value, this expression takes the minimum value only when the inside of the square is 0. Since the inside is 0 only when ΣXi – A = 0, by finding a solution of the optimization problem that minimizes this function, the solution with which ΣXi = A is satisfied is automatically obtained. [0090]
For example, since in the foregoing annealing method, the items desired to be constraint conditions also need to be included in the objective function, the objective function and the constraint conditions are treated to the degree of the same importance. [0091]
For example, assume an optimization problem as below. [0092] [Expression 13]


20

These can be follows. [0093] [Expression 14]

changed into formularization for annealing as


25

23
Here, P and Q are constants, which are factors that determine which item is preferentially minimized. For example, in the case of uniformly minimizing the three items (in other words, solving the problem without biasing the intensities of 5 the constraint conditions), P and Q are set to be the same or similar values. In this way, the values are set to balance between the items. [0094]
However, if the problem setting is based on that "the
10 constraint condition of the second item is strictly kept, but a great importance is not attached to the constraint condition of the third item", the value of P which is the coefficient of the item of a great importance is set larger than the value of Q to obtain a desired solution.
15 [0095]
As described above, the annealing method makes it possible to assign priority for the constraint conditions and make setting, for example, for a constraint condition of less importance like "it should be satisfied as much as possible".
20 [0096]
Note that various settings regarding the Ising model are made as appropriate according to each condition and information for creating a schedule in the present embodiment based on existing general concepts.
25 [0097]
---Specific Examples Of Spin (Variable) Setting---
Consider a variable x_(i,j,k) that is 1 when a worker i carries out a work type k in a time slot j and that is 0 when
30 the worker i does not (see Fig. 5). Basically, each one of the variables x_(i,j,k) is assigned to a spin one by one in the CMOS annealing machine. [0098]
In the case of not taking the "work type" into account,
35 this variable simply gives "whether a worker i is to work in a time slot j". Specifically, in the following Table 1, the cells having 1 mean carrying out the work, and the cells having 0 mean

24 not carrying out the work.

25

[0099] [Table 1]

Time Slot Worker
1
(i=1) Worker
2
(i=2) Worker
3
(i=3) ...
... ... ... ...
■■•
... Worker
30 (i=30)
9:00 to
9:10
(j=1) x1,1,k x2,1,k x3,1,k
x30,1,k
9:10 to
9:20
(j=2) x1,2,k x2,2,k x3,2,k
x30,2,k
9:20 to
9:30
(j=3) x1,3,k x2,3,k x3,3,k
x30,3,k
9:30 to
9:40
(j=4) x1,4,k x2,4,k x3,4,k
x30,4,k
… … … …
…
20:50 to
21:00
(j=72) x1,72,k x2,72,k x3,72,k
x30,72,k

The Number
of
Necessary
Operators
10
12
10
10
…
3

The
Number
of
Working
Shifts 400±50 400±50 400±50 … 400±50

5

[Table 2]

Value of x1,1,1 Value of x1,1,2 work type
0 0 Rest
1 0 Inbound Operation
0 1 Outbound Operation
1 1 (not applicable)

26

*That two variables
are both 1 is
prohibited by
constraint condition

27
[0100]
In the case of taking the "work type" into account, in the above Table 2, the work type "inbound" is associated with k = 1, and the work type "outbound" is associated with k = 2. 5 Thus, one cell on the timetable is expressed by the combination of the two variables. Specifically, if two variables (x_(i,j,1) and x_(i,j,2)) belonging to a cell are both 0, the cell means "rest", if x_(i,j,1) is 1, and x_(i,j,2) is 0, the cell means "inbound", and if x_(i,j,1) is 0, and x_(i,j,2) is
10 1, the cell means "outbound". Here, since the case where x_(i,j,1) and x_(i,j,2) are both 1 means that "one person carries out two different kinds of work in one and the same time slot", this case needs to be excluded as a constraint condition.
15 [0101]

Here, consider a variable x_(i,j,k) that is 1 when a worker i carries out a work type k on a day j and that is 0 when the worker i does not. Here, L_i is the lower limit of
20 the number of working days for the worker i, U_i is the upper limit, and N_j is the number of workers necessary for the day j. Basically, each one of the variables x_(i,j,k) is assigned to a spin one by one in the CMOS annealing machine (see Table 3).

28

[0102] [Table 3]

Day Worker
1
(i=1) Worker
2
(i=2) Worker
3
(i=3) ...
... ... ... ...
■■•
... Worker
30 (i=30)
1st (j=1) x1,1,k x2,1,k x3,1,k
x30,1,k
2nd (j=2) x1,2,k x2,2,k x3,2,k
x30,2,k
3rd (j=3) x1,3,k x2,3,k x3,3,k
x30,3,k
4th (j=4) x1,4,k x2,4,k x3,4,k
x30,4,k
… … … …
…
31st (j=31) x1,31,k x2,31,k x3,31,k
x30,31,k

The Number of Necessary Operators
N1
N2
N3
N4
…
N31

The
Number
of
Working L1 to U1 L2 to
U2 L3 to U3 … L30 to U30
Shifts

29
In the case of not taking the "work type" into account, this variable simply gives "whether a worker i is to work on a day j". Specifically, in Table 3, the cells having 1 mean attendance at work, and the cells having 0 mean holidays. 5 [0103]
In the case of taking the "work type" into account, for example, it is conceivable that the "early shift" is associated with k = 1, the "late shift" with k = 2, and the "midnight shift" with k = 3. In this case, there are three variables 10 that correspond to the top leftmost cell of the table in Fig. 7, (x_1,1,1, x_1,1,2, and x_1,1,3). Since each of the three variables takes a value of 0 or 1, there are eight possible combinations as shown in the following Table 4.

30
[0104]
[Table 4]

Value of
x1,1,1 Value of
x1,1,2 Value of
x1,1,3 work type
0 0 0 holiday
1 0 0 early shift
0 1 0 late shift
0 0 1 midnight shift
1 1 0 ×(prohibit by constraint condition)
1 0 1 ×(prohibit by constraint condition)
0 1 1 ×(prohibit by constraint condition)
1 1 1 ×(prohibit by constraint condition)

31
In this case, a constraint condition that "of the three variables (x_1,1,1, x_1,1,2, and x_1,1,3), only one variable can take 1" needs to be added to prohibit the results in the bottom four lines in the above table. 5 [0105]
---Example of Data Structure---
Next, a description will be given of various kinds of information used by the schedule creation assisting device 100 of the present embodiment. Fig. 5 illustrates an example of
10 a basic information table 125 in the present embodiment. [0106]
The basic information table 125 of the present embodiment stores information on the total number of working shifts for specified months for each of the operators that work in
15 corporation in a call center operation and the number of
operators necessary for each time slot on each day in the month. [0107]
This example is a combinatorial optimization problem in which the length of the time slot is 10 minutes, the number of
20 necessary operators specified across each horizontal line needs to be satisfied in each time slot, and the number of working hours (the number of working shifts) for each operator needs to be kept. In this problem, the shorter the length of the divided time slot, the larger the number of cells necessary
25 for calculation (the cells in this table = factors), and the higher the necessary calculation power. Since the number of cells is large, if constraints are applied, such as prohibited patterns, the minimum number of consecutive shifts (the guideline for the minimum number of consecutive working shifts),
30 the maximum number of consecutive shifts (the guideline for the maximum number of consecutive working shifts), and the like, the number of constraint condition functions according to the constraint conditions is enormous. However, employing the CMOS annealing method makes it possible to determine
35 preferred results, in other words, a preferred schedule within

32
a realistic time. [0108]
Note that the example shown in the basic information table 125 of Fig. 5 only has limited information for 5 convenience of explanation, and thus it is assumed that the table stores information on other various events (the same applies in the following). [0109]
Figs. 6 and 7 illustrate an example of a constraint
10 condition table 126 in the present embodiment. The constraint condition table 126 of the present embodiment stores information on the constraint conditions regarding allocation of each operator to the foregoing call center operation. [0110]
15 The data structure of the table is a set of records
including data such as the identification information ("#" in the figure) of each constraint condition, which is used as a key, the description of the constraint condition, an implementation example with an optimization solver, and an
20 implementation example with an annealing machine (a constraint condition function). [0111]
The present embodiment not only shows implementation examples with an annealing machine, in other words, constraint
25 condition functions, but to compare them with a conventional technique, the present embodiment also shows, side by side, examples of functions in which the constraint condition is implemented with an optimization solver. [0112]
30 ---Example of Procedure---
Hereinafter, a description will be given of an actual procedure of the schedule creation assisting method in the present embodiment based on the figures. Various operations corresponding to the schedule creation assisting method
35 described below are implemented by using a program that the

33
schedule creation assisting device 100 loads into a memory or
the like and executes. This program includes code for
performing various operations described below.
[0113]
5 Fig. 8 is a diagram illustrating an example of a
procedure for the schedule creation assisting method in the present embodiment. In this case, the schedule creation assisting device 100 computes an Ising model 1021 which is set as a processing target in which regarding an objective function
10 including, as terms, the total number of working shifts of each operator for a certain month, the number of necessary operators, and the constraint condition functions, whether each operator is to attend at work is defined as a spin, and the sensitivity between variables of the constraint condition
15 function is set as the intensity of interaction between the spins. [0114]
The schedule creation assisting device 100 obtains conditions desired by each operator from the user terminal 200
20 and stores them in the constraint condition table 126 as constraint conditions (s10). Alternatively, in this process, each operator may specify the constraint conditions that match desired constraint conditions out of the constraint condition table 126, and the schedule creation assisting device 100 may
25 receive the specification from each operator. [0115]
The schedule creation assisting device 100 converts the constraint conditions obtained at s10 into constraint condition functions as already described (s11). These
30 constraint condition functions are functions that are minimized when the constraint conditions are satisfied. Note that in the case of receiving the specification of constraint conditions at s10 as described above, the schedule creation assisting device 100 extracts constraint condition functions
35 already defined for the constraint conditions from the

34
constraint condition table 126. [0116]
As an annealing machine, the schedule creation assisting device 100 sets, as a problem, an Ising model 1021 in which 5 the foregoing three items (the total number of working shifts, the number of necessary operators, and the constraint condition functions) are set and calculates and determines the ground state that minimizes the objective function (s12). Searching for the ground state in itself is the same as or similar to
10 the process in conventional techniques. [0117]
Specifically, the constraint conditions regarding each operator and the rules on the basic information such as the total number of working shifts and the number of necessary
15 operators are satisfied, transition toward the final state indicating whether each time slot is assigned (in theory based on sensitivities) progresses as time passes, and a state in which the results of assignment for each operator are settled is searched for as the ground state.
20 [0118]
The schedule creation assisting device 100 transmits information indicating whether each time slot is assigned to each operator determined at s12 (the screen 900 of Fig. 9) to the user terminal 200 as a schedule (s13) and ends the process.
25 [0119]
The user terminal 200, receiving provision of such information, displays a schedule screen 900 as illustrated in Fig. 9 on an output device such as a display. [0120]
30 The operator of the user terminal 200 views the schedule
screen 900, recognizes the timetable, for example, for the next month, tomorrow, or one hour ahead, and checks and examines the call center operation appropriately. [0121]
35 Note that examples of schedule created according to the

35
types of constraint conditions are shown as follows. Here, the result (Table 5) of creating a schedule on the premise that there is no such constraint condition regarding continuous work (Expression 15: Working shifts shall be continuous to the 5 extent possible) and a schedule (Table 6) for the case where the constraint condition is solved are both shown for comparison. [0122] [Expression 15]


36
[Table 5]
In the case where there are no constraint conditions

Time Slot Operator 1 Operator 2 Operator 3 Operator 4 The Number of Necessary Operators
9:00 to 9:10 work rest rest work 2
9:10 to 9:20 rest work rest work 2
9:20 to 9:30 work rest work rest 2
9:30 to 9:40 rest work rest work 2
9:40 to 9:50 work rest work rest 2
9:50 to 10:00 rest work work work 3
10:00 to 10:10 work work work work 4
10:10 to 10:20 work work work work 4
10:20 to 10:30 work work work rest 3
10:30 to 10:40 work rest work work 3
10:40 to 10:50 rest work work rest 2
10:50 to 11:00 work rest rest work 2
11:00 to 11:10 rest work work rest 2
11:10 to 11:20 work work rest work 3

37

11:20 to 11:30 work work work work 4
The
Number
of 10 10 10 10
Working
Shifts
[Table 6]
In the case where there are constraint conditions

Time Slot Operator 1 Operator 2 Operator 3 Operator 4 The Number of Necessary Operators
9:00 to 9:10 work rest rest work 2
9:10 to 9:20 work rest rest work 2
9:20 to 9:30 work rest work rest 2
9:30 to 9:40 rest work work rest 2
9:40 to 9:50 rest work work rest 2
9:50 to 10:00 rest work work work 3
10:00 to 10:10 work work work work 4
10:10 to 10:20 work work work work 4
10:20 to 10:30 work work work rest 3
10:30 to 10:40 work work work rest 3

38

10:40 to 10:50 rest work rest work 2
10:50 to 11:00 rest work rest work 2
11:00 to 11:10 work rest rest work 2
11:10 to 11:20 work rest work work 3
11:20 to 11:30 work work work work 4
The
Number
of
Working
Shifts 10 10 10 10

39
As shown above, in the case where there is no constraint, working shifts are fragmentary, and there are many portions where "work → rest → work → rest" are repeated at intervals of 10 minutes. Thus, the timetable is not realistic. 5 [0123]
In contrast, in the case where the constraint was considered, the working shifts are basically continuous, and the same type of work can be carried out for a certain length of time. Thus, the timetable is realistic.
10 [0124]
Next, the result (Table 7) of creating a schedule on the premise that there is no constraint condition regarding discontinuous work (Expression 16: Too many holidays shall not be continued in a row) and a schedule (Table 8) for the case
15 where the constraint condition is solved are shown. Note that here is shown an example of results of the constraint condition regarding discontinuous work in work shifts of a month. An example of an expression of the constraint condition considered this time is shown below. This time, the "work type" is not
20 mentioned, and thus, the variable x(i,j) in which the subscript (k) related to the work type is omitted is considered. Here, the symbol A is an adjusted integer. [0125] [Expression 16]


40
[Table 7]
In the case where there are no constraint conditions

Day Operator 1 Operator 2 Operator 3 Operator 4 The Number of Necessary Operators
1st work holiday work work 3
2nd work holiday work work 3
3rd work holiday work work 3
4th work holiday work holiday 2
5th work work work holiday 3
6th work work work holiday 3
7th work work work holiday 3
8th work work holiday work 3
9th work work holiday work 3
10th work work holiday work 3
11th holiday work holiday work 2
12th holiday work work work 3
13th holiday work work work 3
14th holiday work work work 3
The
Number
of
Working
Shifts 10 10 10 10
[Table 8]
5 In the case where there are constraint conditions

Day Operator 1 Operator 2 Operator 3 Operator 4 The Number of Necessary Operators
1st holiday work work work 3
2nd holiday work work work 3

41

3rd work work holiday work 3
4th work work holiday holiday 2
5th work work work holiday 3
6th work holiday work work 3
7th work holiday work work 3
8th holiday work work work 3
9th holiday work work work 3
10th work work holiday work 3
11th work work holiday holiday 2
12th work holiday work work 3
13th work holiday work work 3
14th work work work holiday 3
The
Number of
Working
Shifts 10 10 10 10

42
As shown above, in the case where there is no constraint, work days or holidays continue more than necessary, and the work shifts include "10 consecutive work days" and "4 consecutive holidays", the work shifts of the month is 5 unrealistic also in terms of laws, office rules, and burdens on each operator. In contrast, in the case where the constraint was considered, consecutive work days and consecutive holidays are randomly arranged to an appropriate degree. Thus, the work shifts of the month are realistic.
10 [0126]
Next, the result (Table 9) of creating a schedule on the premise that there is no constraint condition regarding prohibited patterns (Expression 17: An early shift on the next day of a late shift shall be prohibited) and a schedule (Table
15 10) for the case where the constraint condition is solved are shown. Here is shown an example of results of the constraint condition regarding a prohibited pattern in work shifts of a month. An example of an expression of the constraint condition considered this time is shown below. Since this time, of the

This constraint condition means that "an early shift is not to be assigned on the next day of a late shift".
20 "work types", only the early shift (k = 1) and the late shift (k = 2) are mentioned, the number of the subscript (k) concerning the work type considered here is up to 2. [0127] [Expression 17]

43
[0128] [Table 9]
In the case where there are no constraint conditions

Day Operator 1 Operator 2 Operator 3 Operator 4 The Number
of Necessary
Operators

Early Shift Late Shift
1st holiday early shift early shift ▲late shift 2 1
2nd holiday early shift ▲late shift early shift 2 1
3rd ▲late shift early shift holiday early shift 2 1
4th early shift ▲late shift holiday holiday 1 1
5th early shift early shift ▲late shift holiday 2 1
6th ▲late shift holiday early shift early shift 2 1
7th early shift holiday early shift ▲late shift 2 1
8th holiday early shift ▲late shift early shift 2 1
9th holiday ▲late shift early shift early shift 2 1
10th ▲late shift early shift holiday early shift 2 1
11th early shift ▲late shift holiday holiday 1 1
12th early shift holiday early shift ▲late shift 2 1
13th early shift holiday early shift ▲late shift 2 1

44

14th early shift early shift ▲late shift holiday 2 1
Days
of
Early
Shift 7 7 6 6
Days
of
Late
Shift 3 3 4 4
[Table 10]
In the case where there are constraint conditions

Day Operator 1 Operator 2 Operator 3 Operator 4 The Number
of Necessary
Operators

Early Shift Late Shift
1st holiday early shift ▲late shift early shift 2 1
2nd holiday early shift ▲late shift early shift 2 1
3rd early shift early shift holiday ▲late shift 2 1
4th early shift ▲late shift holiday holiday 1 1
5th early shift ▲late shift early shift holiday 2 1
6th ▲late shift holiday early shift early shift 2 1
7th ▲late shift holiday early shift early shift 2 1
8th holiday early shift ▲late shift early shift 2 1

45

9th holiday early shift ▲late shift early shift 2 1
10th early shift early shift holiday ▲late shift 2 1
11th early shift ▲late shift holiday holiday 1 1
12th early shift holiday early shift ▲late shift 2 1
13th early shift holiday early shift ▲late shift 2 1
14th ▲late shift early shift early shift holiday 2 1
Days
of
Early
Shift 7 7 6 6
Days
of
Late
Shift 3 3 4 4

46
In the above tables, a symbol ▲ is prefixed to each late shift to make it easy to distinguish. As shown above, in the case where there is no constraint, there are many portions where an early shift is assigned on the next day of a late 5 shift. It means that before the operator takes enough rest, the operator has to work on the next day. Thus, the work shifts of the month are not realistic. In contrast, in the case where the constraint was considered, either a late shift or a holiday is assigned on the next day of a late shift. Thus,
10 the work shifts of the month are realistic. [0129]
Next, the result (Table 11) of creating a schedule on the premise that there is no constraint condition regarding the compatibility between operators (Expression 18:
15 Combinations of only recruits shall be avoided & an instructor shall be combined) and a schedule (Table 12) for the case where the constraint conditions are solved are shown. Here is shown an example of results of the constraint conditions regarding the compatibility between operators in work shifts of a month.
20 [0130]
Here, this time, the "work type" is not mentioned, and thus, the variable x(i,j) in which the subscript (k) related to the work type is omitted is considered. Here, the symbols A and B are adjusted integers.
25 [0131]
[Expression 18]


47
[Table 11]
In the case where there are no constraint conditions

Day Operator 1
(Expert A)
Instructor
for
Recruit A Operator 2
(Expert B)
Instructor
for
Recruit B Operator
3
(Recruit
A) Operator
4
(Recruit
B) The Number of Necessary Operators
1st work holiday work work 3
2nd work holiday work work 3
3rd work work holiday holiday 2
4th holiday work holiday work 2
5th holiday work work work 3
6th work work holiday holiday 2
7th work work holiday holiday 2
8th work holiday work work 3
9th work holiday work work 3
10th work work holiday holiday 2
11th holiday work work holiday 2
12th work work holiday work 3
13th work work holiday holiday 2
14th holiday work work holiday 2
The
Number
of
Working
Shifts 10 10 7 7
[Table 12]
5 In the case where there are constraint conditions

Operator 1 Operator 2
(Expert A) (Expert B) Operator Operator The
3 4 Number of
Day Instructor Instructor
for for (Recruit (Recruit Necessary
Recruit A Recruit B A) B) Operators

48

1st work work holiday work 3
2nd work work work holiday 3
3rd work holiday work holiday 2
4th holiday work holiday work 2
5th work work holiday work 3
6th holiday work holiday work 2
7th work holiday work holiday 2
8th work work work holiday 3
9th work work work holiday 3
10th holiday work holiday work 2
11th holiday work holiday work 2
12th work work holiday work 3
13th work holiday work holiday 2
14th work holiday work holiday 2
The
Number
of
Working
Shifts 10 10 7 7

49
As above, in the case where there is no constraint, there are "days on which two recruits attend at work on the same day", "days on which recruit A attends at work but operator 1 who is the instructor for recruit A does not", and "days on 5 which recruit B attends at work but operator 2 who is the instructor for recruit B does not". The work shifts of the month are not realistic. In contrast, in the case where the constraints were considered, the number of recruits that attend at work on each day is only one, and on the day when a recruit
10 attends at work, the recruit's instructor always attends. Thus, the work shifts of the month are realistic. [0132]
Next, the result (Table 13) of creating a schedule on the premise that there is no constraint condition regarding
15 reflection of operators' requests (Expression 19: Operator 2 wants to take holidays during the period from 1st to 7th & operator 3 wants to work on early shifts & operator 4 wants to work on late shifts) and a schedule (Table 14) for the case where the constraint conditions are solved are shown.
20 [0133]
[Expression 19]

These constraint conditions mean "operator 2 wants to
take holidays in the first half of the period (1st to 7th)",
25 "operator 3 wants to work on early shifts to the extent
possible", and "operator 4 wants to work on late shifts to the
extent possible".

50
[0134] [Table 13]
In the case where there are no constraint conditions

Day Operator
1
(no
requests) Operator 2
(wants to
take
holidays in
the first
half of the
period) Operator
3
(wants
to work
on early
shifts) Operator
4
(wants
to work
on late
shifts) The Number
of
Necessary
Operators

Early Shift Late Shift
1st holiday early shift ▲late shift early shift 2 1
2nd holiday early shift ▲late shift early shift 2 1
3rd early shift early shift holiday ▲late shift 2 1
4th early shift ▲late shift holiday holiday 1 1
5th early shift ▲late shift early shift holiday 2 1
6th ▲late shift holiday early shift early shift 2 1
7th ▲late shift holiday early shift early shift 2 1
8th holiday early shift ▲late shift early shift 2 1
9th holiday early shift ▲late shift early shift 2 1
10th early shift early shift holiday ▲late shift 2 1
11th early shift ▲late shift holiday holiday 1 1
12th early shift holiday early shift ▲late shift 2 1

51

13th early shift holiday early shift ▲late shift 2 1
14th ▲late shift early shift early shift holiday 2 1
The
Number
of
Working
Shifts 10 10 10 10
[Table 14]
In the case where there are constraint conditions

Day Operator
1
(no
requests) Operator 2
(wants to
take
holidays in
the first
half of the
period) Operator
3
(wants
to work
on early
shifts) Operator
4
(wants to
work on
late shifts) The Number
of
Necessary
Operators

Earl
y Shif
t Late Shift
1st early shift holiday early shift ▲late shift 2 1
2nd early shift holiday early shift ▲late shift 2 1
3rd holiday early shift early shift ▲late shift 2 1
4th early shift ▲late shift holiday holiday 1 1
5th early shift holiday early shift ▲late shift 2 1
6th early shift holiday early shift ▲late shift 2 1
7th ▲late shift early shift early shift holiday 2 1

52

8th ▲late shift early shift early shift holiday 2 1
9th holiday early shift early shift ▲late shift 2 1
10th early shift early shift holiday ▲late shift 2 1
11th ▲late shift early shift holiday holiday 1 1
12th holiday early shift early shift ▲late shift 2 1
13th holiday early shift early shift ▲late shift 2 1
14th early shift early shift holiday ▲late shift 2 1
The
Number
of
Working
Shifts 10 10 10 10

53
In the above tables, a symbol ▲ is prefixed to each late shift to make it easy to distinguish. [0135]
As shown above, in the case where there is no constraint, 5 "there are holidays for operator 2 also in the latter half of the period", "late shifts are assigned to operator 3", "early shifts are assigned to operator 4". Thus, the work shifts of the month are far from operators' requests. In contrast, in the case where the constraints are considered, the work shifts 10 of the month reflect the operators' requests. [0136]
Next, the result (Table 15) of creating a schedule on the premise that there is no constraint condition regarding equal work between operators (Expression 20: The number of 15 working hours shall be equal between operators) and a schedule (Table 16) for the case where the constraint condition is solved are shown. [0137] [Expression 20]

This constraint condition means that "the number of working shifts of each operator shall be set to as close to a guideline D as possible.

54
[0138] [Table 15]
In the case where there are no constraint conditions

Time Slot Operator 1 Operator 2 Operator 3 Operator 4 The Number of Necessary Operators
9:00 to 9:10 work work holiday holiday 2
9:10 to 9:20 work work holiday holiday 2
9:20 to 9:30 work work holiday holiday 2
9:30 to 9:40 work work holiday holiday 2
9:40 to 9:50 work work work holiday 3
9:50 to 10:00 work work work holiday 3
10:00 to 10:10 work work work work 4
10:10 to 10:20 work work work work 4
10:20 to 10:30 work work work work 4
10:30 to 10:40 work work work holiday 3
10:40 to 10:50 work work work holiday 3
10:50 to 11:00 work work holiday holiday 2
11:00 to 11:10 work work holiday holiday 2
11:10 to work work work holiday 3

55

11:20
11:20 to 11:30 work work work holiday 3
Actual
Number of
Working
Shifts 15 15 9 3
Guideline of The
Number of
Working
Shifts 10 10 10 10
[Table 16]
In the case where there are constraint conditions

Time Slot Operator 1 Operator 2 Operator 3 Operator 4 The Number of Necessary Operators
9:00 to 9:10 work rest rest work 2
9:10 to 9:20 work rest rest work 2
9:20 to 9:30 work rest work rest 2
9:30 to 9:40 rest work work rest 2
9:40 to 9:50 rest work work work 3
9:50 to 10:00 rest work work work 3
10:00 to 10:10 work work work work 4
10:10 to work work work work 4

56

10:20
10:20 to 10:30 work work work work 4
10:30 to 10:40 work work work rest 3
10:40 to 10:50 rest work work work 3
10:50 to 11:00 rest work rest work 2
11:00 to 11:10 work rest rest work 2
11:10 to 11:20 work rest work work 3
11:20 to 11:30 work work work rest 3
Actual
Number of
Working
Shifts 10 10 11 11
Guideline of The
Number of
Working
Shifts 10 10 10 10

57
As shown above, in the case where there is no constraint, the working hours are uneven between operators, and the table shows a mixture of operators having no rest time and operators having too many rests. Thus, the timetable is unrealistic. 5 In contrast, in the case where the constraint was considered, the number of working hours is approximately equal between operators. Thus, the timetable is fair and realistic. [0139]
Note that, for example, it will be preferable if in case
10 of emergency, such as a shortage of operators due to a sudden demand increase or abrupt absence of operators, the schedule creation assisting device 100 obtains a constraint condition corresponding to the event from the user terminal 200 and executes the foregoing procedure.
15 [0140]
As a constraint condition in such a situation, for example, a constraint condition on the premise in which an operator who is allocated to a different operation in the same time slot on the same day in the latest created schedule is to
20 "attend at work" or like conditions can be assumed. [0141]
In that case, the schedule creation assisting device 100 executes step s11 according to the constraint condition to generate a constraint condition function, and solves an Ising
25 model regarding the corresponding objective function. [0142]
Although the best mode and the like for carrying out the present invention has been specifically described above, the present invention is not limited to these, but various
30 modifications can be made without departing from the spirit of the invention. [0143]
The present embodiment described above makes it possible to create a schedule efficiently considering nonlinear
35 constraint conditions regarding a large number of workers who

58
work in cooperation. [0144]
The description of the present specification makes at least the following things clear. Specifically, in the 5 schedule creation assisting device of the present embodiment, the computation unit may include, in the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of continuous working time length, seeking to increase continuous work, and
10 restricting continuous work, which are the constraint conditions regarding continuous work, and compute the Ising model. [0145]
This makes it possible to efficiently create a schedule
15 that minimizes labor costs and in which conditions regarding continuous work of each worker (Example: The workers' requests and the rules of their organization. The same applies in the following) are taken into account as much as possible. This in turn makes it possible to create more efficiently a schedule
20 with nonlinear constraint conditions taken into account for a large number of workers who work in cooperation. [0146]
In the schedule creation assisting device of the present embodiment, the computation unit may include, in the terms of
25 the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of intervals of work timings, seeking to increase consecutive holidays, and restricting consecutive holidays, which are the constraint conditions regarding discontinuous work, and
30 compute the Ising model. [0147]
This makes it possible to efficiently create a schedule that minimizes labor costs and in which conditions regarding discontinuous work of each worker are taken into account as
35 much as possible. This in turn makes it possible to create

59
more efficiently a schedule with nonlinear constraint
conditions taken into account for a large number of workers
who work in cooperation.
[0148]
5 In the schedule creation assisting device of the present
embodiment, the computation unit may include, in the terms of the objective function, the constraint condition function concerning at least one of prohibition of continuous work in a specified time slot and prohibition of work in a
10 predetermined time slot immediately after working in the specified time slot, which are the constraint conditions regarding a prohibited pattern, and compute the Ising model. [0149]
This makes it possible to efficiently create a schedule
15 that minimizes labor costs and in which conditions regarding prohibited patterns of work for each worker (Example: A day shift immediately after a midnight shift shall be prohibited) are taken into account as much as possible. This in turn makes it possible to create more efficiently a schedule with
20 nonlinear constraint conditions taken into account for a large number of workers who work in cooperation. [0150]
In the schedule creation assisting device of the present embodiment, the computation unit may include, in the terms of
25 the objective function, the constraint condition function concerning at least one of seeking a state in which workers having specified attributes work at the same time or avoiding the state, which are the constraint conditions regarding the compatibility of workers, and compute the Ising model.
30 [0151]
This makes it possible to efficiently create a schedule that minimizes labor costs and in which conditions regarding the compatibility of each worker with other workers (Example: A recruit and a worker capable of giving instruction to the
35 recruit shall attend at work on the same shift. A worker and

60
a certain worker shall not attend at work on the same shift) are taken into account as much as possible. This in turn makes it possible to create more efficiently a schedule with nonlinear constraint conditions taken into account for a large 5 number of workers who work in cooperation. [0152]
In the schedule creation assisting device of the present embodiment, the computation unit may include, in the terms of the objective function, the constraint condition function
10 concerning seeking work shifts in a specified pattern, which is the constraint condition regarding workers' requests, and compute the Ising model. [0153]
This makes it possible to efficiently create a schedule
15 that minimizes labor costs and in which conditions regarding requests from each worker (Example: A certain shift should be assigned if possible on a specified day) are taken into account as much as possible. This in turn makes it possible to create more efficiently a schedule with nonlinear constraint
20 conditions taken into account for a large number of workers who work in cooperation. [0154]
In the schedule creation assisting device of the present embodiment, the computation unit may include, in the terms of
25 the objective function, the constraint condition function concerning seeking a state in which the work time length in each work pattern is equal between the workers, which is the constraint condition regarding equality between workers, and compute the Ising model.
30 [0155]
This makes it possible to efficiently create a schedule that minimizes labor costs and in which conditions regarding equality between workers are taken into account as much as possible. This in turn makes it possible to create more
35 efficiently a schedule with nonlinear constraint conditions

61
taken into account for a large number of workers who work in
cooperation.
[0156]
The schedule creation assisting device of the present 5 embodiment may be a CMOS annealing machine that solves a combinatorial optimization problem regarding the Ising model. [0157]
This makes it possible to efficiently calculate, at room temperature, a practical solution of a combinatorial
10 optimization problem with constraint conditions affecting one another, in other words, nonlinear constraint conditions taken into account, by simulating the operation of an Ising model, using a circuit including semiconductors such as devices of complementary metal oxide semiconductors (CMOS) or the like.
15 This in turn makes it possible to create much more efficiently a schedule with nonlinear constraint conditions taken into account for a large number of workers who work in cooperation. [0158]
In the schedule creation assisting method in the present
20 embodiment, the information processing device may include, in the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of continuous working time length, seeking to increase continuous work, and restricting continuous work, which are
25 the constraint conditions regarding continuous work, and compute the Ising model. [0159]
In the schedule creation assisting method in the present embodiment, the information processing device may include, in
30 the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of intervals of work timings, seeking to increase consecutive holidays, and restricting consecutive holidays, which are the constraint conditions regarding discontinuous
35 work, and compute the Ising model.

62
[0160]
In the schedule creation assisting method in the present embodiment, the information processing device may include, in the terms of the objective function, the constraint condition 5 function concerning at least one of prohibition of continuous work in a specified time slot and prohibition of work in a predetermined time slot immediately after working in the specified time slot, which are the constraint conditions regarding a prohibited pattern, and compute the Ising model.
10 [0161]
In the schedule creation assisting method in the present embodiment, the information processing device may include, in the terms of the objective function, the constraint condition function concerning at least one of seeking a state in which
15 workers having specified attributes work at the same time or avoiding the state, which are the constraint conditions regarding the compatibility of workers, and compute the Ising model. [0162]
20 In the schedule creation assisting method in the present
embodiment, the information processing device may include, in the terms of the objective function, the constraint condition function concerning seeking work shifts in a specified pattern, which is the constraint condition regarding workers' requests,
25 and compute the Ising model. [0163]
In the schedule creation assisting method in the present embodiment, the information processing device may include, in the terms of the objective function, the constraint condition
30 function concerning seeking a state in which the work time length in each work pattern is equal between the workers, which is the constraint condition regarding equality between workers, and compute the Ising model. [0164]
35 In the schedule creation assisting method in the present

63
embodiment, the information processing device may be a CMOS annealing machine that solves a combinatorial optimization problem regarding the Ising model. [Reference Signs List] 5 [0165]
10 network
100 schedule creation assisting device (annealing machine)
101 storage unit
102 program
10 1021 Ising model
103 memory
104 computation unit
105 communication unit
125 basic information table 15 126 constraint condition table 200 user terminal

WE CLAIMS

A schedule creation assisting device comprising:
a storage unit that stores information on a total working
5 time length in a specified period of each of workers who work
in cooperation in a specified operation, a number of the
workers necessary at each timing during the period, and a
constraint condition regarding allocation of the workers to
the operation; and
10 a computation unit that computes an Ising model in which,
regarding an objective function including, as terms, the total
working time length in the period, the number of necessary
workers, and a constraint condition function that is minimized
when the constraint condition is satisfied, whether each of
15 the workers is to attend at work is set as a spin, and a
sensitivity between variables of the constraint condition
function is set as an intensity of interaction between the
spins, wherein
the computation unit outputs, to a specified device, a 20 schedule in which whether each of the workers is to attend at work at the each timing during the specified period is specified based on a result of the computation. [Claim 2]
The schedule creation assisting device according to 25 claim 1, wherein
the computation unit
includes, in the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of continuous working time length, 30 seeking to increase continuous work, and restricting continuous work, which are the constraint conditions regarding continuous work, and computes the Ising model. [Claim 3]
The schedule creation assisting device according to 35 claim 1, wherein

65
the computation unit
includes, in the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of intervals of work timings, 5 seeking to increase consecutive holidays, and restricting consecutive holidays, which are the constraint conditions regarding discontinuous work, and computes the Ising model. [Claim 4]
The schedule creation assisting device according to 10 claim 1, wherein
the computation unit
includes, in the terms of the objective function, the
constraint condition function concerning at least one of
prohibition of continuous work in a specified time slot and
15 prohibition of work in a predetermined time slot immediately
after working in the specified time slot, which are the
constraint conditions regarding a prohibited pattern, and
computes the Ising model.
[Claim 5]
20 The schedule creation assisting device according to
claim 1, wherein
the computation unit
includes, in the terms of the objective function, the
constraint condition function concerning at least one of
25 seeking a state in which workers having specified attributes
work at the same time or avoiding the state, which are the
constraint conditions regarding the compatibility of workers,
and computes the Ising model.
[Claim 6]
30 The schedule creation assisting device according to
claim 1, wherein
the computation unit
includes, in the terms of the objective function, the
constraint condition function concerning seeking work shifts
35 in a specified pattern, which is the constraint condition

66
regarding workers' requests, and computes the Ising model. [Claim 7]
The schedule creation assisting device according to
claim 1, wherein
5 the computation unit
includes, in the terms of the objective function, the constraint condition function concerning seeking a state in which the work time length in each work pattern is equal between the workers, which is the constraint condition
10 regarding equality between workers, and computes the Ising model. [Claim 8]
The schedule creation assisting device according to claim 1, wherein
15 the schedule creation assisting device is a CMOS
annealing machine that solves a combinatorial optimization problem regarding the Ising model. [Claim 9]
A schedule creation assisting method comprising:
20 by an information processing device including a storage
unit that stores information on a total working time length in a specified period of each of workers who work in cooperation in a specified operation, a number of the workers necessary at each timing during the period, and a constraint condition
25 regarding allocation of the workers to the operation,
computing an Ising model in which, regarding an objective function including, as terms, the total working time length in the period, the number of necessary workers, and a constraint condition function that is minimized when the constraint
30 condition is satisfied, whether each of the workers is to attend at work is set as a spin, and a sensitivity between variables of the constraint condition function is set as an intensity of interaction between the spins; and
outputting, to a specified device, a schedule in which
35 whether each of the workers is to attend at work at the each

67
timing during the specified period is specified based on a result of the computation. [Claim 10]
The schedule creation assisting method according to 5 claim 9, wherein
the information processing device
includes, in the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of continuous working time length, 10 seeking to increase continuous work, and restricting continuous work, which are the constraint conditions regarding continuous work, and computes the Ising model. [Claim 11]
The schedule creation assisting method according to 15 claim 9, wherein
the information processing device
includes, in the terms of the objective function, the constraint condition function concerning at least one of an upper limit or a lower limit of intervals of work timings, 20 seeking to increase consecutive holidays, and restricting consecutive holidays, which are the constraint conditions regarding discontinuous work, and computes the Ising model. [Claim 12]
The schedule creation assisting method according to 25 claim 9, wherein
the information processing device
includes, in the terms of the objective function, the
constraint condition function concerning at least one of
prohibition of continuous work in a specified time slot and
30 prohibition of work in a predetermined time slot immediately
after working in the specified time slot, which are the
constraint conditions regarding a prohibited pattern, and
computes the Ising model.
[Claim 13]
35 The schedule creation assisting method according to

68
claim 9, wherein
the information processing device
includes, in the terms of the objective function, the constraint condition function concerning at least one of 5 seeking a state in which workers having specified attributes work at the same time or avoiding the state, which are the constraint conditions regarding the compatibility of workers, and computes the Ising model. [Claim 14] 10 The schedule creation assisting method according to claim 9, wherein
the information processing device
includes, in the terms of the objective function, the constraint condition function concerning seeking work shifts 15 in a specified pattern, which is the constraint condition regarding workers' requests, and computes the Ising model. [Claim 15]
The schedule creation assisting method according to claim 9, wherein 20 the information processing device
includes, in the terms of the objective function, the constraint condition function concerning seeking a state in which the work time length in each work pattern is equal between the workers, which is the constraint condition 25 regarding equality between workers, and computes the Ising model. [Claim 16]
The schedule creation assisting method according to claim 9, wherein 30 the information processing device
is a CMOS annealing machine that solves a combinatorial
optimization problem regarding the Ising model.