# US 2023/0056830 A1 · Optimization function generation apparatus, optimization function generation method, and program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0056830 A1
- Document ID: US20230056830A1
- Status: Published application
- Kind: A1
- Application number: 17/797,071
- Filed: 2020-02-06
- Published: 2023-02-23
- Earliest claimed: 2020-02-06
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Kazuhiro MIYAHARA; Keitaro HORIKAWA; Kinya TOMITA
- Web page: https://patentgrep.com/patent/US20230056830A1

## CPC

- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
- G06N 10/80: Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

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.

## Claims

### Claim 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; and
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.

### Claim 2 (depends on 1)

The optimization function creation apparatus according to claim 1, wherein
the constraint conditions are a condition (hereinafter referred to as a “first constraint condition”) that start(q)+q.time≤start(p) (where start(p) represents an execution start time point of a process p) is satisfied with respect to processes p∈P and q∈p.precede, and a condition (hereinafter referred to as a “second constraint condition”) that |{p∈r.processes|start(p)≤t≤start(p)+p.time}|≤1 is satisfied with respect to each time point t up to the maximum time point End and each resource r∈R, and
the optimization function is a function that takes the minimum value when the first constraint condition and the second constraint condition are satisfied.

### Claim 3 (depends on 2)

The optimization function creation apparatus according to claim 2, wherein
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 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, and
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.

### Claim 4 (depends on 2)

The optimization function creation apparatus according to claim 2, wherein
the variable that represents a quantum state is a spin that represents a particular state by taking the value 1 and represents a state other than the particular state by taking the value −1,
the optimization function is an Ising Hamiltonian 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, and
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.

### Claim 5 (depends on 3)

The optimization function creation apparatus according to claim 3, wherein
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.

### Claim 6

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; and
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.

### Claim 7 (depends on 1)

A non-transitory computer-readable recording medium storing a program for causing a computer to function as the optimization function creation apparatus according to claim 1.

### Claim 8 (depends on 4)

The optimization function creation apparatus according to claim 4, wherein
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.