#
Example NP problems published in A. Lucas, *Front. Phys.* (2014) - Job sequencing problem with
integer lengths¶

This example code implements the **job sequencing problem with integer lengths**
introduced
in the paper A. Lucas,
"Ising
formulations of many NP problems", *Front. Phys.* (2014) using Fixstars Amplify. Other
NP-complete and NP-hard problems introduced in the same paper are also discussed below (the
corresponding
sections in the paper are shown in the brackets).

- Graph partitioning problem (Sec. 2.2).
- Maximum clique problem (Sec. 2.3)
- Exact cover problem (Sec. 4.1)
- Set packing problem (Sec. 4.2)
- Minimum vertex cover problem (Sec. 4.3)
- Satisfiability problem (SAT) (Sec. 4.4)
- Minimum maximum matching problem (Sec. 4.5)
- Graph coloring problem (Sec. 6.1)
- Clique cover problem (Sec. 6.2)
**Job sequencing problem with integer lengths**(Sec. 6.3)- Hamiltonian cycle problem (Sec. 7.1)
- Directed feedback vertex set problem (Sec. 8.3)
- Minimum feedback edge set problem (Sec. 8.5)
- Graph isomorphism problem (Sec. 9)

## Job sequencing problem¶

Suppose you have $N$ jobs, and you know how long each job will take. There are $M$ machines that can run those jobs, and we assign each of the $N$ jobs to one of the machines. The idea is to find the allocation that gives the fastest time for all jobs to complete.

However, each machine executes its assigned jobs serially. That is, a machine cannot have multiple jobs running simultaneously. We also assume that the time taken for each job is an integer.

For example, if you have three jobs that take one hour each, and you have two machines, and you assign two jobs to one machine and one job to the other, it will take two hours for all jobs to complete. And since it is impossible to complete all jobs in less than two hours, this is the optimal solution.

Here, we create a program that solves this job sequencing problem using Fixstars Amplify. The formulation follows the one in section 6.3 of A. Lucas, Front. Phys. (2014).

## Problem definition¶

First, we create an example problem. Let us determine the number of jobs, the number of machines, and the time each job will take.

```
import numpy as np
# Number of machines
M = 3
# Number of jobs
N = 7
# Times each job will take
job_lengths = np.array([7, 5, 3, 2, 2, 2, 2])
assert N == len(job_lengths)
```

## Formulation¶

Hereafter, let $L_i$ be the time to complete the $i$-th job.

### Formulation guidelines¶

Prepare a binary variable table $q$ of $N\times M$ to represent which machine to run each job on. When machine $j$ deals with the $i$-th job, the $i$ row $j$ column of $q$ should be $1$.

For example, suppose we have the following job schedule.

Job | Machine |
---|---|

Job 0 | Machine 0 |

Job 1 | Machine 2 |

Job 2 | Machine 2 |

Job 3 | Machine 1 |

Job 4 | Machine 1 |

Job 5 | Machine 1 |

Job 6 | Machine 1 |

The above job schedule can be represented by the variable table $q$ below.

$q$ | Machine 0 | Machine 1 | Machine 2 |
---|---|---|---|

Job 0 | 1 | 0 | 0 |

Job 1 | 0 | 0 | 1 |

Job 2 | 0 | 0 | 1 |

Job 3 | 0 | 1 | 0 |

Job 4 | 0 | 1 | 0 |

Job 5 | 0 | 1 | 0 |

Job 6 | 0 | 1 | 0 |

Also, to make it easier to understand what the maximum execution time to minimize is, we will assign jobs so that machine $0$ always has the longest execution time.

### Objective function¶

Since we assign jobs so that the runtime of machine $0$ is longer than the runtimes of the other machines, the time it takes to complete all jobs is equal to the execution time of machine $0$. Therefore, the objective function should be the execution time of machine $0$, i.e., the sum of the time taken by the jobs assigned to machine $0$. This can be done using the time $L_i$ taken for the job $i$:

$$ \sum_{i = 0}^{N - 1} q_{i, 0} L_i. $$

### Constraints¶

$q$ must satisfy the following.

- Condition 1: Each job is assigned to one machine. That is, each row of $q$ has precisely $1$.
- Condition 2: For each machine, its execution time is less than machine $0$.

We can express condition 1 as:

$$ \sum_{j = 0}^{M-1} q_{i, j} = 1 \quad \text{for} \quad i \in \{0, 1, \ldots, N-1\}. $$

Also, since the runtime of machine $j$ can be expressed as $\sum_{i = 0}^{N - 1} q_{i, j} L_i$, the condition 2 is

$$ \sum_{i = 0}^{N - 1} L_i q_{i, j} \leq \sum_{i = 0}^{N - 1} q_{i, 0} L_i \quad \text{for} \quad j \in \{1, 2, \ldots, M - 1\}. $$

Conversely, when conditions 1 and 2 are satisfied, $q$ represents the job assignment, and the objective function is equal to the time until all jobs are completed.

## Implementation¶

Using the problem and formulation described above, let us implement and solve the problem.
First, we create a $N\times M$ binary variables array $q$ using `BinarySymbolGenerator`

in
Fixstars Amplify SDK.

```
from amplify import BinarySymbolGenerator
gen = BinarySymbolGenerator()
q = gen.array(N, M)
```

Next, a function is defined to calculate the total execution time for each machine. The total
execution
time for machine $j$ is represented by $\displaystyle \sum_{i = 0}^{N - 1} q_{i, j} L_i$. The $L$ in
this
expression is an array representing the time spent on each job, which in code is a NumPy array named
`job_lengths`

. By taking the inner product of `job_lengths`

and the $j$ column
of
$q$, we can calculate the total execution time.

We will use this function later to construct the objective function and condition 2.

```
def calc_execution_time(j):
return (job_lengths * q[:, j]).sum()
```

Next, we construct the objective function. As explained earlier, the objective function equals the total run time of machine $0$.

```
cost = calc_execution_time(0)
```

Now, we create a constraint condition corresponding to condition 1. Condition 1 is a constraint that is "each job is assigned to exactly $1$ machines", meaning that there is only one $1$ in each row of $q$.

```
from amplify.constraint import one_hot
constraint1 = [one_hot(q[i, :]) for i in range(N)]
```

Let us construct a constraint condition corresponding to condition 2. Condition 2 is the condition
that
the execution time of machine $0$ is greater than or equal to the execution time of the other
machines.
Note that inequality constraints such as `less_equal`

can only be used for integer-valued
equations.

```
from amplify.constraint import less_equal
constraint2 = [
less_equal(calc_execution_time(j) - calc_execution_time(0), 0) for j in range(1, M)
]
```

Now, we convert the created objective function and constraints together into a logical model.

This time, the objective function and constraints are explicitly converted to a logic model using
`BinaryQuadraticModel`

. In this way, it is possible to use some useful functions, for
example,
to see the number of logical variables, including auxiliary variables, issued during the logical model
conversion.

In many other sample programs, instead of using `BinaryQuadraticModel`

explicitly, the sum
of
the objective function and constraints is directly passed to the solver as follows. However, even in
this
case, the solver internally performs the same conversion to a logical model as
`BinaryQuadraticModel`

.

model = cost + sum(constraint1) + sum(constraint2) solver = Solver(client) result = solver.solve(model) # <-- internally converting to a logical model

```
from amplify import BinaryQuadraticModel
model = BinaryQuadraticModel(cost, sum(constraint1) + sum(constraint2))
```

The number of input variables used in the present problem is $N \times M = 21$, but the
`model`

created above contains inequality constraints, so when it is converted to a logical
model auxiliary
variables are added. As a result, the number of logical variables is more significant than the
number of binary decision variables included in $q$. Let us check the actual number of logical
variables
considered in the logical model.

```
model.num_logical_vars
```

Let us set the client and execute the solver with Fixstars Amplify Annealing Engine (AE).

```
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = 1000
# Define and execute the solver
solver = Solver(client)
result = solver.solve(model)
```

Since `Solver`

automatically filters the solutions that satisfy the constraints, if the
`result`

is not empty, you know that there is a solution that satisfies the constraints.

```
if len(result) == 0:
print("No solution has been found.")
else:
print("A solution has been found.")
```

Since the time for all jobs to complete is equal to the value of the objective function, it can be checked as follows.

```
result[0].energy
```

Lastly, we will visualize the solution.

```
import matplotlib.pyplot as plt
values = q.decode(result[0].values)
assigned_machines = np.where(values == 1)[1]
# x軸を描画
plt.xticks(range(M), [f"machine {i}" for i in range(M)])
# 描画
bottom = np.zeros(M)
for i, j in enumerate(assigned_machines):
bar = plt.bar(j, job_lengths[i], bottom=bottom[j])
plt.bar_label(bar, labels=[f"job {i}"], label_type="center")
bottom[j] += job_lengths[i]
```