Optimization function generation apparatus, optimization function generation method, and program
Provided is a technology for creating an optimization function for solving a scheduling problem for creating a process execution plan such that execution of all processes will be completed by a predetermined time point under constraint conditions regarding the processes and resources required by the processes, the optimization function relating to a variable that represents a quantum state. The technology includes: an input setting unit that sets a set P of processes, a set R of resources, a maximum time point End, the time p.time it takes to execute a process p, a set p.precede of processes of which execution needs to be completed before execution of the process p is started, and a set r.processes of processes that require a resource r when executed, as input to the scheduling problem for creating a plan of execution start time points of processes such that execution of all processes included in the set P will be completed by the maximum time point End under the predetermined constraint conditions; and an optimization function creation unit that creates the optimization function using the input.
1 . An optimization function creation apparatus comprising:
an input setting circuitry configured to set a set P of processes, a set R of resources, a maximum time point End, the time p.time it takes to execute a process p(∈P), a set p.precede(⊆P) of processes of which execution needs to be completed before execution of the process p is started, and a set r.processes(⊆P) of processes that require a resource r(∈R) when executed, as input to a scheduling problem for creating a plan of execution start time points of processes such that execution of all processes included in the set P will be completed by the maximum time point End under predetermined constraint conditions;
an optimization function creation circuitry configured to create an optimization function for solving the scheduling problem using the input, the optimization function relating to a variable that represents a quantum state, wherein
the constraint conditions comprise a first constraint condition that start(q)+q.time≤start(p) holds true for processes p∈P and q∈p.precede,
the start(p) represents an execution start time point of a process p,
the constraint conditions further comprise a second constraint condition that {p∈r.processes|start(p)≤t≤start(p)+p.time}|≤1 holds true for each time point t up to the maximum time point End and each resource r∈R,
the optimization function is a function that takes the minimum value when the first constraint condition and the second constraint condition are satisfied,
the variable that represents a quantum state is a quantum bit that represents a particular state by taking the value 1 and represents a state other than the particular state by taking the value 0,
the optimization function is an objective function of Quadratic Unconstrained Binary Optimization (“QUBO”) defined based on a function that expresses the first constraint condition and a function that expresses the second constraint condition,
the function expressing the first constraint condition is a function that takes the value 0 when the first constraint condition is satisfied, and otherwise takes a value greater than 0,
the function expressing the second constraint condition is a function that takes the value 0 when the second constraint condition is satisfied, and otherwise takes a value greater than 0,
the variable that represents a quantum state is a variable that is defined so as to represent, with the value 1, a state where a time point t is at or after an execution start time point of a process p,
the quantum bit is defined as a variable x p,t whose value is “1” in a case where the time point t is at or after the execution start time point of the process p, and otherwise “0,” and
the objective function of QUBO is defined as a function JSP,
JSP
=
AfterStart
+
Order
+
Resource
,
AfterStart
=
∑
0
≤
t
<
End
-
1
∑
p
∈
P
x
p
,
t
(
1
-
x
p
,
t
+
1
)
,
Order
=
∑
0
≤
t
<
End
∑
p
∈
P
∑
q
∈
p
.
precede
x
p
,
t
(
1
-
x
q
,
t
-
q
.
time
)
,
Resource
=
∑
r
∈
R
∑
0
≤
t
<
End
Count
(
r
,
t
)
(
Count
(
r
,
t
)
-
1
)
,
Count
(
r
,
t
)
=
∑
p
∈
r
.
processes
(
x
p
,
t
-
x
p
,
t
-
p
.
time
)
the AfterStart represents a function expressing the meaning of the quantum bit x p,t ,
the Order represents a function expressing the first constraint condition, and
the Resource represents a function expressing the second constraint condition, and
a process execution plan creation circuitry configured to create, by executing the optimization function solving the scheduling problem using the input, a process execution plan as output of the optimization function to schedule process execution.
2 . A method for creating an optimization function, comprising:
an input setting step of setting, by an optimization function creation apparatus, a set P of processes, a set R of resources, a maximum time point End, the time p.time it takes to execute a process p(∈P), a set p.precede(⊆P) of processes of which execution needs to be completed before execution of the process p is started, and a set r.processes(⊆P) of processes that require a resource r(∈R) when executed, as input to a scheduling problem for creating a plan of execution start time points of processes such that execution of all processes included in the set P will be completed by the maximum time point End under predetermined constraint conditions;
an optimization function creating step of creating, by the optimization function creation apparatus, an optimization function for solving the scheduling problem using the input, the optimization function relating to a variable that represents a quantum state, wherein
the constraint conditions comprise a first constraint condition that start(q)+q.time≤start(p) holds true for processes p∈P and q∈p.precede,
the start(p) represents an execution start time point of a process p,
the constraint conditions further comprise a second constraint condition that |{p∈r.processes|start(p)≤t≤start(p)+p.time}|≤1 holds true for each time point t up to the maximum time point End and each resource r∈R,
the optimization function is a function that takes the minimum value when the first constraint condition and the second constraint condition are satisfied,
the variable that represents a quantum state is a quantum bit that represents a particular state by taking the value 1 and represents a state other than the particular state by taking the value 0,
the optimization function is an objective function of Quadratic Unconstrained Binary Optimization (“QUBO”) defined based on a function that expresses the first constraint condition and a function that expresses the second constraint condition,
the function expressing the first constraint condition is a function that takes the value 0 when the first constraint condition is satisfied, and otherwise takes a value greater than 0,
the function expressing the second constraint condition is a function that takes the value 0 when the second constraint condition is satisfied, and otherwise takes a value greater than 0,
the variable that represents a quantum state is a variable that is defined so as to represent, with the value 1, a state where a time point t is at or after an execution start time point of a process p,
the quantum bit is defined as a variable x p,t whose value is “1” in a case where the time point t is at or after the execution start time point of the process p, and otherwise “0,” and
the objective function of QUBO is defined as a function JSP,
JSP
=
AfterStart
+
Order
+
Resource
,
AfterStart
=
∑
0
≤
t
<
End
-
1
∑
p
∈
P
x
p
,
t
(
1
-
x
p
,
t
+
1
)
,
Order
=
∑
0
≤
t
<
End
∑
p
∈
P
∑
q
∈
p
.
p
r
e
c
e
d
e
x
p
,
t
(
1
-
x
q
,
t
-
q
.
time
)
,
Resource
=
∑
r
∈
R
∑
0
≤
t
<
End
Count
(
r
,
t
)
(
Count
(
r
,
t
)
-
1
)
,
Count
(
r
,
t
)
=
∑
p
∈
r
.
p
r
o
c
e
s
s
e
s
(
x
p
,
t
-
x
p
,
t
-
p
.
time
)
the AfterStart represents a function expressing the meaning of the quantum bit x p,t ,
the Order represents a function expressing the first constraint condition, and
the Resource represents a function expressing the second constraint condition; and
a process execution plan creating step of creating, by executing the optimization function solving the scheduling problem using the input, a process execution plan as output of the optimization function to schedule process execution by the optimization function creation apparatus.
3 . A non-transitory computer-readable recording medium storing a program for causing a computer to perform the method for creating an optimization function according to claim 2 .
4 . An optimization function creation apparatus comprising:
an input setting circuitry configured to set a set P of processes, a set R of resources, a maximum time point End, the time p.time it takes to execute a process p(∈P), a set p.precede(⊆P) of processes of which execution needs to be completed before execution of the process p is started, and a set r.processes(⊆P) of processes that require a resource r(∈R) when executed, as input to a scheduling problem for creating a plan of execution start time points of processes such that execution of all processes included in the set P will be completed by the maximum time point End under predetermined constraint conditions;
an optimization function creation circuitry configured to create an optimization function for solving the scheduling problem using the input, the optimization function relating to a variable that represents a quantum state, wherein
the constraint conditions comprise a first constraint condition that start(q)+q.time≤start(p) holds true for processes p∈P and q∈p.precede,
the start(p) represents an execution start time point of a process p,
the constraint conditions further comprise a second constraint condition that {p∈r.processes|start(p)≤t≤start(p)+p.time}|1 holds true for each time point t up to the maximum time point End and each resource r∈R,
the optimization function is a function that takes the minimum value when the first constraint condition and the second constraint condition are satisfied,
the variable that represents a quantum state is a quantum bit that represents a particular state by taking the value 1 and represents a state other than the particular state by taking the value 0,
the optimization function is an objective function of Quadratic Unconstrained Binary Optimization (“QUBO”) defined based on a function that expresses the first constraint condition and a function that expresses the second constraint condition,
the function expressing the first constraint condition is a function that takes the value 0 when the first constraint condition is satisfied, and otherwise takes a value greater than 0,
the function expressing the second constraint condition is a function that takes the value 0 when the second constraint condition is satisfied, and otherwise takes a value greater than 0,
the variable that represents a quantum state is a variable that is defined so as to represent, with the value 1, a state where a time point t is at or after an execution start time point of a process p,
the quantum bit is defined as a variable xp,t whose value is “1” in a case where the time point t is at or after the execution start time point of the process p, and otherwise “0,” and
the objective function of QUBO is defined as a function JSP,
JSP
=
AfterStart
+
Order
+
Resource
,
AfterStart
=
∑
0
≤
t
<
End
-
1
∑
p
∈
P
(
t
+
1
)
*
x
p
,
t
(
1
-
x
p
,
t
+
1
)
,
Order
=
∑
0
≤
t
<
End
∑
p
∈
P
∑
q
∈
p
.
p
r
e
c
e
d
e
x
p
,
t
(
1
-
x
q
,
t
-
q
.
time
)
,
Resource
=
∑
r
∈
R
∑
0
≤
t
<
End
Count
(
r
,
t
)
(
Count
(
r
,
t
)
-
1
)
,
Count
(
r
,
t
)
=
∑
p
∈
r
.
p
r
o
c
e
s
s
e
s
(
x
p
,
t
-
x
p
,
t
-
p
.
time
)
the AfterStart represents a function expressing the meaning of the quantum bit x p,t ,
the Order represents a function expressing the first constraint condition, and
the Resource represents a function expressing the second constraint condition, and
a process execution plan creation circuitry configured to create, by executing the optimization function solving the scheduling problem using the input, a process execution plan as output of the optimization function to schedule process execution.
5 . A method for creating an optimization function, comprising:
an input setting step of setting, by an optimization function creation apparatus, a set P of processes, a set R of resources, a maximum time point End, the time p.time it takes to execute a process p(∈P), a set p.precede(⊆P) of processes of which execution needs to be completed before execution of the process p is started, and a set r.processes(⊆P) of processes that require a resource r(∈R) when executed, as input to a scheduling problem for creating a plan of execution start time points of processes such that execution of all processes included in the set P will be completed by the maximum time point End under predetermined constraint conditions;
an optimization function creating step of creating, by the optimization function creation apparatus, an optimization function for solving the scheduling problem using the input, the optimization function relating to a variable that represents a quantum state, wherein
the constraint conditions comprise a first constraint condition that start(q)+q.time≤start(p) holds true for processes p∈P and q∈p.precede,
the start(p) represents an execution start time point of a process p,
the constraint conditions further comprise a second constraint condition that {p∈r.processes|start(p)≤t≤start(p)+p.time}|≤1 holds true for each time point t up to the maximum time point End and each resource r∈R,
the optimization function is a function that takes the minimum value when the first constraint condition and the second constraint condition are satisfied,
the variable that represents a quantum state is a quantum bit that represents a particular state by taking the value 1 and represents a state other than the particular state by taking the value 0,
the optimization function is an objective function of Quadratic Unconstrained Binary Optimization (“QUBO”) defined based on a function that expresses the first constraint condition and a function that expresses the second constraint condition,
the function expressing the first constraint condition is a function that takes the value 0 when the first constraint condition is satisfied, and otherwise takes a value greater than 0,
the function expressing the second constraint condition is a function that takes the value 0 when the second constraint condition is satisfied, and otherwise takes a value greater than 0,
the variable that represents a quantum state is a variable that is defined so as to represent, with the value 1, a state where a time point t is at or after an execution start time point of a process p,
the quantum bit is defined as a variable x p,t whose value is “1” in a case where the time point t is at or after the execution start time point of the process p, and otherwise “0,” and
the objective function of QUBO is defined as a function JSP,
JSP
=
AfterStart
+
Order
+
Resource
,
AfterStart
=
∑
0
≤
t
<
End
-
1
∑
p
∈
P
(
t
+
1
)
*
x
p
,
t
(
1
-
x
p
,
t
+
1
)
,
Order
=
∑
0
≤
t
<
End
∑
p
∈
P
∑
q
∈
p
.
p
r
e
c
e
d
e
x
p
,
t
(
1
-
x
q
,
t
-
q
.
time
)
,
Resource
=
∑
r
∈
R
∑
0
≤
t
<
End
Count
(
r
,
t
)
(
Count
(
r
,
t
)
-
1
)
,
Count
(
r
,
t
)
=
∑
p
∈
r
.
p
r
o
c
e
s
s
e
s
(
x
p
,
t
-
x
p
,
t
-
p
.
time
)
the AfterStart is a function expressing the meaning of the quantum bit x p,t ,
the Order is a function expressing the first constraint condition, and
the Resource is a function expressing the second constraint condition; and
a process execution plan creating step of creating, by executing the optimization function solving the scheduling problem using the input, a process execution plan as output of the optimization function to schedule process execution by the optimization function creation apparatus.
6 . A non-transitory computer-readable recording medium storing a program for causing a computer to perform the method for creating an optimization function according to claim 5 .