Job Sequencing Problem with Integer Lengths

Here we show how to solve the job sequencing problems with integer lengths using OpenJij, JijModeling, and ommx-openjij-adapter. This problem is also mentioned in 6.3. Job Sequencing with Integer Lengths in Lucas, 2014, “Ising formulations of many NP problems”.

Overview of the Job Sequencing Problem with Integer Lengths

We consider several computers and tasks with integer lengths (i.e., task 1 takes one hour to execute on a computer, task 2 takes three hours, and so on). When allocating these tasks to multiple computers to execute, the question is what combinations can be used to distribute the execution time of the computers without creating bias. We can obtain a leveled solution by minimizing the largest value.

Example

As an example of this problem, consider the following situation.

Here are 10 tasks and 3 computers. The length of each of the 10 tasks is 1, 2, …, 10. Our goal is to assign these tasks to the computers and minimize the maximum amount of time the tasks take. In this case, one of the optimal solution is \(\{1, 2, 7, 8\}, \{3, 4, 5, 6\}\) and \(\{9, 10\}\), whose maximum execution time of computers is 19.

Mathematical Model

Next, we introduce \(N\) tasks \(\{0, 1, ..., N-1\}\) and list of the execution time \(L = \{L_0, L_1, ..., L_{N-1}\}\). Given \(M\) computers, the total execution time of the \(j\) th computer to perform its assigned tasks is \(A_j = \sum_{i \in V_j} L_i\) where \(V_j\) is a set of assigned tasks to the \(j\) th computer. Finally, let us denote \(x_{i, j}\) to be a binary variable which is 1 if the \(i\) th task is assigned to the \(j\) th computer, and 0 otherwise.

Constraint: Each task must be performed on one computer

Each task must be performed on one computer; for example, task 3 is not allowed to be executed on both computers 1 and 2.

\[ \sum_{j=0}^{M-1} x_{i, j} = 1 \quad (\forall i \in \{ 0, 1, \dots, N-1 \}) \tag{1} \]

Objective Function: Minimize the difference in execution time between computers

We consider the execution time of the \(0\) th computer as the reference and minimize the difference between that and others. This reduces the execution time variability and the tasks are distributed equally.

\[ \min\left\{ \sum_{j=1}^{M-1} (A_0 - A_j)^2\right\} \tag{2} \]

Formulation with JijModeling

Next, we show how to formulate the above mathematical model using JijModeling. We first define the variables and parameters used in the model.

import jijmodeling as jm

problem = jm.Problem('Integer Jobs')

L = problem.Float('L', ndim=1)
N = problem.DependentVar("N", L.len_at(0))
M = problem.Natural('M')
x = problem.BinaryVar('x', shape=(N, M))

L is a one-dimensional array representing the execution time of each task. N denotes the number of tasks. M is the number of computers. x is a two-dimensional binary variable.

Constraint

Let us formulate the constraint in equation (1).

# set constraint: job must be executed using a certain node
problem += problem.Constraint('onehot', lambda i: jm.sum(M, lambda j: x[i, j]) == 1, domain=N)

Objective Function

Next, let us formulate the objective function in equation (2).

# set objective function: minimize difference between node 0 and others
A_0 = jm.sum(N, lambda i: L[i]*x[i, 0])
problem += jm.sum(
    jm.filter(lambda j: j != 0, M),
    lambda j: (A_0 - jm.sum(N, lambda i: L[i]*x[i, j])) ** 2,
)

jm.filter(lambda j: j != 0, M) means to take all \(j\) such that \(j \neq 0\).

Let us display the formulated mathematical model in the Jupyter Notebook.

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Integer Jobs}\\\displaystyle \min &\displaystyle \sum _{\substack{j=0\\j\neq 0}}^{M-1}{{\left(\sum _{i=0}^{N-1}{{L}_{i}\cdot {x}_{i,0}}-\left(\sum _{i=0}^{N-1}{{L}_{i}\cdot {x}_{i,j}}\right)\right)}^{2}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{onehot}&\quad \displaystyle \sum _{j=0}^{M-1}{{x}_{i,j}}=1\quad \forall i\;\text{s.t.}\;i\in \left\{0,\ldots ,N-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N\times M;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}L&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\M&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(L,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Creating an Instance

Let us set up the instance as follows.

# set a list of jobs
inst_L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# set the number of Nodes
inst_M = 3
instance_data = {'L': inst_L, 'M': inst_M}

As in the example above, we consider distributing 10 tasks with lengths \(\{1, 2, \dots, 10\}\) across 3 computers.

Running Optimization with OpenJij

Let us solve the optimization problem using OpenJij’s simulated annealing.

from ommx_openjij_adapter import OMMXOpenJijSAAdapter

instance = problem.eval(instance_data)

adapter = OMMXOpenJijSAAdapter(instance)
best_sample = adapter.sample(
    instance, num_reads=100, uniform_penalty_weight=8.0,beta_max=100
).best_feasible_unrelaxed

Visualizing the Solution

Let us visualize the obtained solution.

import matplotlib.pyplot as plt
import numpy as np

df = best_sample.decision_variables_df
x_indices = df[(df["name"] == "x") & (df["value"] > 0.5)]["subscripts"].to_list()
# get the instance information
L = instance_data["L"]
M = instance_data["M"]
# initialize execution time
exec_time = np.zeros(M, dtype=np.int64)
# compute summation of execution time each nodes
for i, j in x_indices:
    plt.barh(j, L[i], left=exec_time[j],ec="k", linewidth=1,alpha=0.8)
    plt.text(exec_time[j] + L[i] / 2.0 - 0.25 ,j-0.05, str(i+1),fontsize=12)
    exec_time[j] += L[i]
plt.yticks(range(M))
plt.ylabel('Computer numbers')
plt.xlabel('Execution time')
plt.show()

The visualization shows that execution time is distributed across the 3 computers. The maximum execution time is 19, confirming that the optimal solution has been obtained. The execution times of the three computers are approximately equal.