Job Sequencing Problem with Integer Lengths

Here we show how to solve job sequencing problems with integer lengths using JijZept and JijModeling. This problem is also described in 6.3. Job Sequencing with Integer Lengths on Lucas, 2014, “Ising formulations of many NP problems”.

What is the Job Sequencing Problem with Integer Lengths?

We consider several tasks with integer lengths (i.e., task 1 takes one hour to execute on a computer, task 2 takes three hours, and so on). We ask: when distributing these tasks to multiple computers, what combinations can be the optimal solution to distribute these computers’ execution time without creating bias?

Example

Let’s take a look at 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, the optimal solution is \(\{1, 2, 7, 8\}, \{3, 4, 5, 6\}\) and \(\{9, 10\}\), whose maximum of execution time of computers is 19.

Generalization

Next, we introcude \(N\) tasks \(\{0, 1, ..., N-1\}\) and list of the execution time \(\bm{L} = \{L_0, L_1, ..., L_{N-1}\}\). Given \(M\) computers, the total execution time of \(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 \(j\)-th computer. Finally, let us denote \(x_{i, j}\) to be a binary variable which is 1 if \(i\)-th task is assigned to \(j\)-th computer, and 0 otherwise.

Constraint: each task must be assigned to one computer

For instance, it is forbidden to assign the 5th task to the 1st and 2nd computers simultaneously. We express this constraint as follows:

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

Objective function: minimize the difference between the execution time of the 0th computer and others

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

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

Modeling by JijModeling

Next, we show an implementation using JijModeling. We first define variables for the mathematical model described above.

import jijmodeling as jm

# defin variables
L = jm.Placeholder('L', ndim=1)
N = L.len_at(0, latex="N")
M = jm.Placeholder('M')
x = jm.BinaryVar('x', shape=(N, M))
i = jm.Element('i', belong_to=(0, N))
j = jm.Element('j', belong_to=(0, 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. Then, we define a two-dimensional list of binary variables x. Finally, we set the subscripts i and j used in the mathematical model.

Constraint

We implement a constraint, Equation (1).

# set problem
problem = jm.Problem('Integer Jobs')
# set constraint: job must be executed using a certain node
problem += jm.Constraint('onehot', x[i, :].sum()==1, forall=i)

x[i, :].sum() is syntactic sugar of sum(j, x[i, j]).

Objective function

Next, we implement an objective function, Equation (2).

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

sum((j, j!=0), ...) denotes taking the sum of all cases where j is not 0.

Let’s display the implemented mathematical model in Jupyter Notebook.

problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{Integer Jobs} & & \\& & \min \quad \displaystyle \sum_{\substack{j = 0\\j \neq 0}}^{M - 1} \left(\left(\sum_{i = 0}^{N - 1} L_{i} \cdot x_{i, 0} - \sum_{i = 0}^{N - 1} L_{i} \cdot x_{i, j}\right)^{2}\right) & \\\text{{s.t.}} & & & \\ & \text{onehot} & \displaystyle \sum_{\ast_{1} = 0}^{M - 1} x_{i, \ast_{1}} = 1 & \forall i \in \left\{0,\ldots,N - 1\right\} \\\text{{where}} & & & \\& x & 2\text{-dim binary variable}\\\end{array}\end{split}\]

Prepare an instance

We set the execution time of each job and the number of computers. At this time, we use the same values from an example as we described before.

# 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}

Solve by JijSolver

We solve this problem using jijsolver.

import jijsolver

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

Visualize the solution

In the end, we visualize the solution obtained.

import matplotlib.pyplot as plt
import numpy as np

df = solution.decision_variables
x_indices = df[df["value"]==1]["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()

With the above visualization, we obtain a graph where the execution times of three computers are approximately equal. The maximum execution time is still 19, so this is the optimal solution.