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.

In [ ]:

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.

In [ ]:

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.

In [ ]:

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$.

In [ ]:

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$.

In [ ]:

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.

In [ ]:

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.

In [ ]:

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).

In [ ]:

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.

In [ ]:

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.

In [ ]:

result.best.objective

Lastly, we will visualize the solution.

In [ ]:

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]