# Job Shop (JSP)¶

## Principles learned¶

• Add multiple list decision variables

• Constrain the number of elements in a list

• Use interval decision variables

• Order interval decision variables by pairing them up with a list variable

## Problem¶

A set of jobs has to be processed on every machine of the shop. Each job consists in an ordered sequence of tasks (called activities), each representing the processing of the job on one of the machines. Each job has one activity per machine, and cannot start an activity while the previous activity of the job is not completed. Each activity has a given processing time and each machine can only process one activity at a time.

The goal is to find a sequence of jobs that minimizes the makespan: the time when all jobs have been processed.

## Data¶

The instances provided follow the Taillard format. The format of the data files is as follows:

• First line: number of jobs, number of machines, seed used to generate the instance, upper and lower bound previously found.

• For each job: the processing time on each machine (given in the processing order).

• For each job: the processing order (ordered list of visited machines).

## Program¶

We use interval decision variables to model the time ranges of the activities. The length of the interval is constrained by the processing time of each activity.

The precedence constraints are easily written: for each job, any activity of this job must be placed after the activity processed by the previous machine.

In addition to the interval decisions representing the time ranges of the activities, we also use list decision variables. As in the Flowshop example, a list models the ordering of activities within a machine. We constrain all the jobs to be processed on each machine thanks to the “count” operator.

The disjunctive resource constraints — each machine can only process one activity at a time — can be reformulated as follows: given a sequence of jobs, the activity corresponding to any job must be placed after the activity corresponding to the previous job.

To model these constraints, we pair up the interval decisions (the time ranges) with the list decisions (the job orderings). We write a lambda function, expressing the relationship between the two consecutive activities. This function is used within an “and” operator over all activities processed by a machine.

The makespan to minimize is the time when all the activities have been processed.

If you are interested in a more general case, where the activities are not ordered on each machine, you can now study our openshop model.

Execution:
localsolver jobshop.lsp inFileName=instances/ft10.txt [outFileName=] [lsTimeLimit=]
```use io;

/* Read instance data. The input files follow the "Taillard" format */
function input() {
local usage = "Usage: localsolver jobshop.lsp inFileName=instanceFile "
+ "[outFileName=outputFile] [lsTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;

// Processing times for each job on each machine (given in the processing order)
processingTimesInProcessingOrder[j in 0...nbJobs][m in 0...nbMachines] = inFile.readInt();
for [j in 0...nbJobs][k in 0...nbMachines] {
local m = inFile.readInt() - 1;
// Processing order of machines for each job
machineOrder[j][k] = m;
// Reorder processing times: processingTime[j][m] is the processing time of the
// task of job j that is processed on machine m
processingTime[j][m] = processingTimesInProcessingOrder[j][k];
}
inFile.close();

// Trivial upper bound for the start times of the tasks
maxStart = sum[j in 0...nbJobs][m in 0...nbMachines] (processingTime[j][m]);
}

/* Declare the optimization model */
function model() {
// Interval decisions: time range of each task
// tasks[j][m] is the interval of time of the task of job j which is processed
// on machine m
tasks[j in 0...nbJobs][m in 0...nbMachines] <- interval(0, maxStart);

for [j in 0...nbJobs][m in 0...nbMachines]

// Precedence constraints between the tasks of a job
for [j in 0...nbJobs][k in 0...nbMachines-1]

// Sequence of tasks on each machine
jobsOrder[m in 0...nbMachines] <- list(nbJobs);

for [m in 0...nbMachines] {
// Each job has a task scheduled on each machine
constraint count(jobsOrder[m]) == nbJobs;

// Disjunctive resource constraints between the tasks on a machine
constraint and(0...nbJobs-1,
}

// Minimize the makespan: end of the last task of the last job
makespan <- max[j in 0...nbJobs] (end(tasks[j][machineOrder[j][nbMachines - 1]]));
minimize makespan;
}

/* Parameterize the solver */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 60;
}

/* Write the solution in a file with the following format:
*  - for each machine, the job sequence */
function output() {
if (outFileName != nil) {
outFile = io.openWrite(outFileName);
println("Solution written in file ", outFileName);
for [m in 0...nbMachines]
outFile.println[j in 0...nbJobs](jobsOrder[m].value[j], " ");
}
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python jobshop.py instances\ft10.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python jobshop.py instances/ft10.txt
```import localsolver
import sys

# The input files follow the "Taillard" format
with open(filename) as f:

first_line = lines.split()
# Number of jobs
nb_jobs = int(first_line)
# Number of machines
nb_machines = int(first_line)

# Processing times for each job on each machine (given in the processing order)
processing_times_in_processing_order = [[int(lines[i].split()[j])
for j in range(nb_machines)]
for i in range(3, 3 + nb_jobs)]

# Processing order of machines for each job
machine_order = [[int(lines[i].split()[j]) - 1 for j in range(nb_machines)]
for i in range(4 + nb_jobs, 4 + 2 * nb_jobs)]

# Reorder processing times: processing_time[j][m] is the processing time of the
# task of job j that is processed on machine m
processing_time = [[processing_times_in_processing_order[j][machine_order[j].index(m)]
for m in range(nb_machines)]
for j in range(nb_jobs)]

# Trivial upper bound for the start times of the tasks
max_start = sum(sum(processing_time[j]) for j in range(nb_jobs))

return nb_jobs, nb_machines, processing_time, machine_order, max_start

def main(instance_file, output_file, time_limit):
nb_jobs, nb_machines, processing_time, machine_order, max_start = read_instance(instance_file)

with localsolver.LocalSolver() as ls:
#
# Declare the optimization model
#
model = ls.model

# Interval decisions: time range of each task
# tasks[j][m] is the interval of time of the task of job j which is processed
# on machine m
tasks = [[model.interval(0, max_start) for m in range(nb_machines)]
for j in range(nb_jobs)]

for j in range(nb_jobs):
for m in range(0, nb_machines):

# Create a LocalSolver array in order to be able to access it with "at" operators

# Precedence constraints between the tasks of a job
for j in range(nb_jobs):
for k in range(nb_machines - 1):
model.constraint(

# Sequence of tasks on each machine
jobs_order = [model.list(nb_jobs) for m in range(nb_machines)]

for m in range(nb_machines):
# Each job has a task scheduled on each machine
sequence = jobs_order[m]
model.constraint(model.eq(model.count(sequence), nb_jobs))

# Disjunctive resource constraints between the tasks on a machine
sequence_lambda = model.lambda_function(
model.constraint(model.and_(model.range(0, nb_jobs - 1), sequence_lambda))

# Minimize the makespan: end of the last task of the last job
for j in range(nb_jobs)])
model.minimize(makespan)

model.close()

# Parameterize the solver
ls.param.time_limit = time_limit

ls.solve()

#
# Write the solution in a file with the following format:
# - for each machine, the job sequence
#
if output_file != None:
final_jobs_order = [list(jobs_order[m].value) for m in range(nb_machines)]
with open(output_file, "w") as f:
print("Solution written in file ", output_file)
for m in range(nb_machines):
for j in range(nb_jobs):
f.write(str(final_jobs_order[m][j]) + " ")
f.write("\n")

if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python jobshop.py instance_file [output_file] [time_limit]")
sys.exit(1)

instance_file = sys.argv
output_file = sys.argv if len(sys.argv) >= 3 else None
time_limit = int(sys.argv) if len(sys.argv) >= 4 else 60
main(instance_file, output_file, time_limit)
```
Compilation / Execution (Windows)
cl /EHsc jobshop.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
jobshop instances\ft10.txt
Compilation / Execution (Linux)
g++ jobshop.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o jobshop
./jobshop instances/ft10.txt
```#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;
using namespace std;

class Jobshop {
private:
// Number of jobs
int nbJobs;
// Number of machines
int nbMachines;
// Processing order of machines for each job
vector<vector<int>> machineOrder;
// Processing time on each machine for each job (given in the machine order)
vector<vector<int>> processingTime;
// Trivial upper bound for the start times of the tasks
int maxStart;

// LocalSolver
LocalSolver localsolver;
// Decision variables: time range of each task
// Decision variables: sequence of tasks on each machine
vector<LSExpression> jobsOrder;
// Objective = minimize the makespan: end of the last task of the last job
LSExpression makespan;

public:
Jobshop() : localsolver() {}

// The input files follow the "Taillard" format
ifstream infile;
infile.open(fileName.c_str());

infile.ignore(numeric_limits<streamsize>::max(), '\n');
infile >> nbJobs;
infile >> nbMachines;
infile.ignore(numeric_limits<streamsize>::max(), '\n');

// Processing times for each job on each machine (given in the processing order)
infile.ignore(numeric_limits<streamsize>::max(), '\n');
vector<vector<int>> processingTimesInProcessingOrder = vector<vector<int>>(nbJobs, vector<int>(nbMachines));
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {
infile >> processingTimesInProcessingOrder[j][m];
}
}

// Processing order of machines for each job
infile.ignore(numeric_limits<streamsize>::max(), '\n');
infile.ignore(numeric_limits<streamsize>::max(), '\n');
machineOrder.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j) {
machineOrder[j].resize(nbMachines);
for (int m = 0; m < nbMachines; ++m) {
int x;
infile >> x;
machineOrder[j][m] = x - 1;
}
}

// Reorder processing times: processingTime[j][m] is the processing time of the
// task of job j that is processed on machine m
for (int j = 0; j < nbJobs; ++j) {
processingTime.resize(nbJobs);
for (int m = 0; m < nbMachines; ++m) {
processingTime[j].resize(nbMachines);
vector<int>::iterator findM = find(machineOrder[j].begin(), machineOrder[j].end(), m);
unsigned int k = distance(machineOrder[j].begin(), findM);
processingTime[j][m] = processingTimesInProcessingOrder[j][k];
}
}

// Trivial upper bound for the start times of the tasks
maxStart = 0;
for (int j = 0; j < nbJobs; ++j)
maxStart += accumulate(processingTime[j].begin(), processingTime[j].end(), 0);

infile.close();
}

void solve(int timeLimit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// Interval decisions: time range of each task
// tasks[j][m] is the interval of time of the task of job j which is processed on machine m
for (unsigned int j = 0; j < nbJobs; ++j) {
for (unsigned int m = 0; m < nbMachines; ++m) {

}
}

// Create a LocalSolver array in order to be able to access it with "at" operators
for (int j = 0; j < nbJobs; ++j) {
}

// Precedence constraints between the tasks of a job
for (int j = 0; j < nbJobs; ++j) {
for (int k = 0; k < nbMachines - 1; ++k) {
}
}

// Sequence of tasks on each machine
jobsOrder.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m) {
jobsOrder[m] = model.listVar(nbJobs);
}

for (int m = 0; m < nbMachines; ++m) {
// Each job has a task scheduled on each machine
LSExpression sequence = jobsOrder[m];
model.constraint(model.eq(model.count(sequence), nbJobs));

// Disjunctive resource constraints between the tasks on a machine
LSExpression sequenceLambda = model.createLambdaFunction([&](LSExpression i) {
});
model.constraint(model.and_(model.range(0, nbJobs - 1), sequenceLambda));
}

// Minimize the makespan: end of the last task of the last job
makespan = model.max();
for (int j = 0; j < nbJobs; ++j) {
}
model.minimize(makespan);

model.close();

// Parameterize the solver
localsolver.getParam().setTimeLimit(timeLimit);

localsolver.solve();
}

/* Write the solution in a file with the following format:
*  - for each machine, the job sequence */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());
cout << "Solution written in file " << fileName << endl;

for (int m = 0; m < nbMachines; ++m) {
LSCollection finalJobsOrder = jobsOrder[m].getCollectionValue();
for (int j = 0; j < nbJobs; ++j) {
outfile << finalJobsOrder.get(j) << " ";
}
outfile << endl;
}
outfile.close();
}
};

int main(int argc, char** argv) {
if (argc < 2) {
cout << "Usage: jobshop instanceFile [outputFile] [timeLimit]" << endl;
exit(1);
}

const char* instanceFile = argv;
const char* outputFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "60";

Jobshop model;
try {
const int timeLimit = atoi(strTimeLimit);
model.solve(timeLimit);
if (outputFile != NULL)
model.writeSolution(outputFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Jobshop.cs /reference:localsolvernet.dll
Jobshop instances\ft10.txt
```using System;
using System.IO;
using localsolver;

public class Jobshop : IDisposable
{
// Number of jobs
private int nbJobs;

// Number of machines
private int nbMachines;

// Processing order of machines for each job
private int[,] machineOrder;

// Processing time on each machine for each job (given in the machine order)
private long[,] processingTime;

// Trivial upper bound for the start times of the tasks
private long maxStart;

// LocalSolver
private LocalSolver localsolver;

// Decision variables: time range of each task

// Decision variables: sequence of tasks on each machine
private LSExpression[] jobsOrder;

// Objective = minimize the makespan: end of the last task of the last job
private LSExpression makespan;

public Jobshop()
{
localsolver = new LocalSolver();
}

// The input files follow the "Taillard" format
{
{
nbJobs = int.Parse(splitted);
nbMachines = int.Parse(splitted);

// Processing times for each job on each machine (given in the processing order)
long[,] processingTimesInProcessingOrder = new long[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; ++j)
{
for (int m = 0; m < nbMachines; ++m)
processingTimesInProcessingOrder[j, m] = long.Parse(splitted[m]);
}

// Processing order of machines for each job
machineOrder = new int[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; ++j)
{
for (int m = 0; m < nbMachines; ++m)
machineOrder[j, m] = int.Parse(splitted[m]) - 1;
}

// Reorder processing times: processingTime[j, m] is the processing time of the
// task of job j that is processed on machine m
processingTime = new long[nbJobs, nbMachines];
// Trivial upper bound for the start times of the tasks
maxStart = 0;
for (int j = 0; j < nbJobs; ++j)
{
for (int m = 0; m < nbMachines; ++m)
{
int machineIndex = nbMachines;
for (int k = 0; k < nbMachines; ++k)
{
if (machineOrder[j, k] == m)
{
machineIndex = k;
break;
}
}
processingTime[j, m] = processingTimesInProcessingOrder[j, machineIndex];
maxStart += processingTime[j, m];
}
}
}
}

public void Dispose()
{
localsolver.Dispose();
}

public void Solve(int timeLimit)
{
// Declare the optimization model
LSModel model = localsolver.GetModel();

// Interval decisions: time range of each task
// tasks[j][m] is the interval of time of the task of job j which is processed on machine m
for (int j = 0; j < nbJobs; ++j)
{
for (int m = 0; m < nbMachines; ++m)
{

}
}

// Create a LocalSolver array in order to be able to access it with "at" operators

// Precedence constraints between the tasks of a job
for (int j = 0; j < nbJobs; ++j)
{
for (int k = 0; k < nbMachines - 1; ++k)
{
}
}

// Sequence of tasks on each machine
jobsOrder = new LSExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m)
jobsOrder[m] = model.List(nbJobs);

for (int m = 0; m < nbMachines; ++m)
{
// Each job has a task scheduled on each machine
LSExpression sequence = jobsOrder[m];
model.Constraint(model.Count(sequence) == nbJobs);

// Disjunctive resource constraints between the tasks on a machine
LSExpression sequenceLambda = model.LambdaFunction(
);
model.Constraint(model.And(model.Range(0, nbJobs - 1), sequenceLambda));
}

// Minimize the makespan: end of the last task of the last job
makespan = model.Max();
for (int j = 0; j < nbJobs; ++j)
model.Minimize(makespan);

model.Close();

// Parameterize the solver
localsolver.GetParam().SetTimeLimit(timeLimit);

localsolver.Solve();
}

/* Write the solution in a file with the following format:
*  - for each machine, the job sequence */
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
Console.WriteLine("Solution written in file " + fileName);
for (int m = 0; m < nbMachines; ++m)
{
LSCollection finalJobsOrder = jobsOrder[m].GetCollectionValue();
for (int i = 0; i < nbJobs; ++i)
{
int j = (int)finalJobsOrder.Get(i);
output.Write(j + " ");
}
output.WriteLine();
}
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: Jobshop instanceFile [outputFile] [timeLimit]");
System.Environment.Exit(1);
}

string instanceFile = args;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "60";

using (Jobshop model = new Jobshop())
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac Jobshop.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Jobshop instances\ft10.txt
Compilation / Execution (Linux)
javac Jobshop.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. Jobshop instances/ft10.txt
```import java.util.*;
import java.io.*;
import localsolver.*;

public class Jobshop {
// Number of jobs
private int nbJobs;
// Number of machines
private int nbMachines;
// Processing time on each machine for each job (given in the machine order)
private long[][] processingTime;
// Processing order of machines for each job
private int[][] machineOrder;
// Trivial upper bound for the start times of the tasks
private long maxStart;

// LocalSolver
final LocalSolver localsolver;
// Decision variables: time range of each task
// Decision variables: sequence of tasks on each machine
private LSExpression[] jobsOrder;
// Objective = minimize the makespan: end of the last task of the last job
private LSExpression makespan;

public Jobshop(LocalSolver localsolver) throws IOException {
this.localsolver = localsolver;
}

// The input files follow the "Taillard" format
public void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
input.nextLine();
nbJobs = input.nextInt();
nbMachines = input.nextInt();

input.nextLine();
input.nextLine();
// Processing times for each job on each machine (given in the processing order)
long[][] processingTimesInProcessingOrder = new long[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {
processingTimesInProcessingOrder[j][m] = input.nextInt();
}
}
// Processing order of machines for each job
input.nextLine();
input.nextLine();
machineOrder = new int[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {
machineOrder[j][m] = input.nextInt() - 1;
}
}
// Reorder processing times: processingTime[j][m] is the processing time of the
// task of job j that is processed on machine m
processingTime = new long[nbJobs][nbMachines];
// Trivial upper bound for the start times of the tasks
maxStart = 0;
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {
int machineIndex = nbMachines;
for (int k = 0; k < nbMachines; ++k) {
if (machineOrder[j][k] == m) {
machineIndex = k;
break;
}
}
processingTime[j][m] = processingTimesInProcessingOrder[j][machineIndex];
maxStart += processingTime[j][m];
}
}
}
}

public void solve(int timeLimit) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// Interval decisions: time range of each task
// tasks[j][m] is the interval of time of the task of job j which is processed
// on machine m
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {

}
}

// Create a LocalSolver array in order to be able to access it with "at"
// operators

// Precedence constraints between the tasks of a job
for (int j = 0; j < nbJobs; ++j) {
for (int k = 0; k < nbMachines - 1; ++k) {
}
}

// Sequence of tasks on each machine
jobsOrder = new LSExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m) {
jobsOrder[m] = model.listVar(nbJobs);
}

for (int m = 0; m < nbMachines; ++m) {
// Each job has a task scheduled on each machine
LSExpression sequence = jobsOrder[m];
model.constraint(model.eq(model.count(sequence), nbJobs));

// Disjunctive resource constraints between the tasks on a machine
LSExpression mExpr = model.createConstant(m);
LSExpression sequenceLambda = model
.lambdaFunction(i -> model.lt(model.at(taskArray, model.at(sequence, i), mExpr),
model.constraint(model.and(model.range(0, nbJobs - 1), sequenceLambda));
}

// Minimize the makespan: end of the last task of the last job
makespan = model.max();
for (int j = 0; j < nbJobs; ++j) {
}
model.minimize(makespan);

model.close();

// Parameterize the solver
localsolver.getParam().setTimeLimit(timeLimit);

localsolver.solve();
}

/*
* Write the solution in a file with the following format:
* - for each machine, the job sequence
*/
public void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
System.out.println("Solution written in file " + fileName);

for (int m = 0; m < nbMachines; ++m) {
LSCollection finalJobsOrder = jobsOrder[m].getCollectionValue();
for (int i = 0; i < nbJobs; ++i) {
int j = Math.toIntExact(finalJobsOrder.get(i));
output.write(j + " ");
}
output.write("\n");
}
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: java Jobshop instanceFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "60";

try (LocalSolver localsolver = new LocalSolver()) {
Jobshop model = new Jobshop(localsolver);