#
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 VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, M))
```

Next, a list of the total execution time for each machine, expressed by the above `q`

is
created. 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`

.

```
from amplify import PolyArray, einsum
execution_times: PolyArray = einsum("i,ij->j", job_lengths, q) # type:ignore
```

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

```
cost = execution_times[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 import one_hot
constraint1 = one_hot(q, axis=1)
```

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 passing an empty tuple to the `axis`

parameter of the `less_equal`

function will create constraints for each element of the PolyArray at once.

```
from amplify import less_equal
constraint2 = less_equal(execution_times[1:] - execution_times[0], 0, axis=())
```

Now, we convert the created objective function and constraints together into an optimization model.

```
model = cost + constraint1 + 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 set the client and execute the solver with Fixstars Amplify Annealing Engine (AE).

```
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = timedelta(milliseconds=1000) # timeout is 1000 ms
# Solve the problem
result = solve(model, client)
```

Since Amplify SDK 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.best.objective
```

Lastly, we will visualize the solution.

```
import matplotlib.pyplot as plt
values = q.evaluate(result.best.values)
assigned_machines = np.where(values == 1)[1]
# Draw x-axis
plt.xticks(range(M), [f"machine {i}" for i in range(M)])
# Vizualize the solution
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]
```