JobShop¶

Principles learned¶

• Call a native function
• Add multiple list decision variables
• Constrain the number of elements in a list

Problem¶

A set of jobs has to be processed on every machine of the shop. Each job consists in a 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 perform one activity at a time.

The goal is to find a sequence of jobs that minimize 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¶

As in the jobshop example, the ordering of activities within a machine can be modeled with a list variable. The difference here is that this ordering will represent a priority between activities and we will use a native function to derive a schedule from these priority lists. Indeed, natives functions can be used to return some arithmetic operations but also to embed a simple algorithm. We will illustrate this usage here.

For each machine we introduce a list decision variable whose size will be constrained to be equal to the number of jobs. Now the rest of the model consists of a single native function implementing the classical Giffler and Thompson rule (1960) and returning the resulting makespan.

This basic rule amounts to repeatedly planning the earliest available activity, unless it would delay jobs of higher priority on this machine, in which case we schedule the job with highest priority among these. This rule is applied until all jobs are complete. Note that resource and precedence constraints are implicitly modeled through this iterative heuristic.

This chronological algorithm is implemented with several cursors monitoring the progress on machines and jobs (jobProgress, jobProgressTime, machineProgressTime). As the search strategy of LocalSolver is multi-threaded, these variables have to be independent between each thread. To maintain the thread-safety property, a thread-local storage (TLS) is used here.

The only decision variables here are the priority lists which define foreach machine a priority order between jobs. They are constrained to be full (each job has a priority). To execute the algorithm described above as a native function, a `call` expression is created. The content of the lists variables is given as input of the native function by using the `addOperand` method.

The speed of the search may be lower in Python than in C++, Java or C# (see performance issues in Python for native functions).

Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python27\
python jobshop.py instances\ft10.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python jobshop.py instances/ft10.txt
```########## jobshop.py ##########

import localsolver
import sys

if len(sys.argv) < 2:
print ("Usage: python jobshop.py inputFile [outputFile] [timeLimit]")
sys.exit(1)

class JobshopInstance :
def __init__(self, filename):
self.nb_activities = self.nb_jobs * self.nb_machines

# The input files follow the "Taillard" format.
with open(filename) as f:
first_line = lines[1].split()
# Number of jobs
self.nb_jobs = int(first_line[0])
# Number of machines
self.nb_machines = int(first_line[1])
# processing time on each machine for each job (given in the processing order)
self.processing_time = [[int(lines[i].split()[j]) for j in range(self.nb_machines)] for i in range(3,3+self.nb_jobs)]
# processing order of machines for each job
self.job_machine_order = [[int(lines[i].split()[j])-1 for j in range(self.nb_machines)] for i in range(4+self.nb_jobs,4+2*self.nb_jobs)]

class Scheduler :
"""Scheduler allows to obtain a schedule in output from the priority
list variables. It is based on the simple J. Giffler and G.L. Thompson
algorithm (1960)."""
def __init__(self, instance):
self.instance = instance
self.priority_list = [[0 for j in range(instance.nb_jobs)] for m in range(instance.nb_machines)]
self.job_progress = [0 for j in range(instance.nb_jobs)]
self.job_progress_time = [0 for j in range(instance.nb_jobs)]
self.machine_progress_time = [0 for j in range(instance.nb_machines)]

def schedule(self):
for k in range(self.instance.nb_activities):
job = self.choose_job()
self.schedule_next_activity(job)

def get_make_span(self):
return max(self.machine_progress_time)

def call(self, context):
if not parsingSucces:
return float("nan")
self.init_lists_attibutes()
self.schedule()
return self.get_make_span()

# Get the candidate activity with earliest starting time and
# schedule it, unless it would delay jobs of higher priority
# whose next machine is this one, in which case we schedule
# the job with highest priority among these.
def choose_job(self):
job = self.select_job_with_earliest_starting_next_activity()
machine = self.next_machine(job)
end = self.job_next_activity_end(job)
return self.select_next_priority_job(machine, end)

# Return the job whose next activity has the earliest start date
def select_job_with_earliest_starting_next_activity(self):
earliest_start = float("inf")
selected_job = -1
for job in range(self.instance.nb_jobs):
if not self.has_next_activity(job):
continue
machine = self.next_machine(job)
start = max(self.machine_progress_time[machine], self.job_progress_time[job])
if start < earliest_start:
earliest_start = start
selected_job = job
return selected_job

# Select the job of highest priority among jobs
# - whose next machine is machine
# - whose next activity earliest start is before given time
def select_next_priority_job(self, machine, time):
for k in range(self.instance.nb_jobs):
job = self.priority_list[machine][k]
if self.next_machine(job)!=machine :
continue
if self.job_progress_time[job] <= time :
return job

# Schedule the next activity of the given job,
# and update progression variables accordingly.
def schedule_next_activity(self, job):
m = self.next_machine(job)
end = self.job_next_activity_end(job)
self.job_progress[job] += 1
self.machine_progress_time[m] = end
self.job_progress_time[job] = end

def has_next_activity(self, job):
return self.job_progress[job] < self.instance.nb_machines

def job_next_activity_end(self, job):
next_activity = self.job_progress[job]
machine = instance.job_machine_order[job][next_activity]
duration = instance.processing_time[job][next_activity]
start = max(self.machine_progress_time[machine], self.job_progress_time[job])
return start + duration

def next_machine(self, job):
next_activity = self.job_progress[job]
if next_activity == instance.nb_machines:
return -1
return instance.job_machine_order[job][next_activity]

# Fill the priorityList matrix by parsing the LSNativeContext object.
# Return false if the list variables aren't full, what happens
# when the solver hasn't reached feasibility yet.
for m in range(instance.nb_machines):
for j in range(instance.nb_jobs):
val = context[m*instance.nb_jobs + j]
if val < 0:
return False
self.priority_list[m][j] = val
return True

def init_lists_attibutes(self):
self.job_progress = [0 for j in range(instance.nb_jobs)]
self.job_progress_time = [0 for j in range(instance.nb_jobs)]
self.machine_progress_time = [0 for j in range(instance.nb_machines)]

# Return the schedule from the final values of the priority list
# variables. It is only called once at the end if an output file is
#  mentionned.
def write_solution(self, f, final_priority_list):
self.priority_list = final_priority_list
solution = [[] for m in range(self.instance.nb_machines)]
self.init_lists_attibutes()
for k in range(self.instance.nb_activities):
job = self.choose_job()
machine = self.next_machine(job)
solution[machine].append(job)
self.schedule_next_activity(job)
solution_string = str(solution).replace("]","\n")
solution_string = filter(lambda ch: ch not in "[,]", solution_string)
f.write(solution_string)

with localsolver.LocalSolver() as ls:

instance = JobshopInstance(sys.argv[1])

#
# Declares the optimization model
#
model = ls.model

# For each machine the decision variable is a permuation of all jobs
priority_lists_variables = [model.list(instance.nb_jobs) for m in range(instance.nb_machines)]

# All activities must be processed
for m in range(instance.nb_machines):
model.constraint(model.eq(model.count(priority_lists_variables[m]), instance.nb_jobs))

# Creation of a "Scheduler" object, a native funciton
# for decoding the priority list variables (that is to say computing
# the makespan from these priority lists).
sch = Scheduler(instance)

# Minimize the makespan: end of the last job on the last machine
makespan_func = model.create_native_function(sch.call);
call_makespan_func = model.call(makespan_func)

# To call the native function, the priorityListsVariables matrix is
# flatenned in one vector and each element of that vector is added
# as operand.
for m in range(instance.nb_machines):
for t in range(instance.nb_jobs):

model.minimize(call_makespan_func)

model.close()

#
# Parameterizes the solver
#
if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
else: ls.create_phase().time_limit = 60

ls.solve()

#
# Writes the solution in a file
#
if len(sys.argv) >= 3:
final_priority_list = [list(priority_lists_variables[m].value) for m in range(instance.nb_machines)]
with open(sys.argv[2],"w") as f:
sch.write_solution(f, final_priority_list)
```
Compilation / Execution (Windows)
cl /EHsc jobshop.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
jobshop instances\ft10.txt
Compilation / Execution (Linux)
g++ jobshop.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o jobshop
./jobshop instances/ft10.txt
```/********** jobshop.cpp **********/

#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <algorithm>
#include <cinttypes>
#include "localsolver.h"

using namespace localsolver;

class JobshopInstance {
public:
// Number of jobs
int nbJobs;

// Number of machines
int nbMachines;

// Number of activities, i.e. nbJobs*nbMachines
int nbActivities;

// processing order of machines for each job
std::vector<std::vector<lsint> > jobMachineOrder;

// processing time on each machine for each job (given in the processing order)
std::vector<std::vector<lsint> > processingTime;

JobshopInstance(const std::string& fileName) {
nbActivities = nbJobs * nbMachines;
}

private:

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

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

// processing times for each jobs on each activity, index starts at 0
infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
processingTime.resize(nbJobs);
for (int j = 0; j < nbJobs; j++) {
processingTime[j].resize(nbMachines);
for (int m = 0; m < nbMachines; m++) {
infile >> processingTime[j][m];
}
}
// machine order for each job, index starts at 0
infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
infile.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
jobMachineOrder.resize(nbJobs);
for (int j = 0; j < nbJobs; j++) {
jobMachineOrder[j].resize(nbMachines);
for (int m = 0; m < nbMachines; m++) {
int x;
infile >> x;
jobMachineOrder[j][m] = x - 1;
}
}

if (processingTime.size() != nbJobs || processingTime[0].size() != nbMachines) {
std::cerr << "Error in reading input file. Wrong processingTime matrix size." << std::endl;
exit(1);
}
if (jobMachineOrder.size() != nbJobs || jobMachineOrder[0].size() != nbMachines) {
std::cerr << "Error in reading input file. Wrong jobMachineOrder matrix size." << std::endl;
exit(1);
}

infile.close();
}

};

class Scheduler : public LSNativeFunction {
// Scheduler allows to obtain a schedule in output from the priority
// list variables. It is based on the simple J. Giffler and G.L. Thompson
// algorithm (1960).

private:
const JobshopInstance* instance;

// here. Each thread must have have independant following variables.

public:

Scheduler(const JobshopInstance* instance) : instance(instance) {
}

void schedule() {
for (int k = 0; k < instance->nbActivities; k++) {
int job = chooseJob();
scheduleNextActivity(job);
}
}

lsdouble getMakespan() {
return *std::max_element(machineProgressTime.begin(), machineProgressTime.end());
}

lsdouble call(const LSNativeContext& context) {
initPriorityList();
if (!parsingSucess) return std::numeric_limits<lsdouble>::quiet_NaN();
initStaticVectors();
schedule();
return getMakespan();
}

// Return the schedule from the final values of the priority list
// variables. It is only called once at the end if an output file is
//  mentionned.
void writeSolution(std::ofstream& outfile, std::vector<std::vector<int> >& finalPriorityList) {
priorityList.swap(finalPriorityList);
std::vector<std::vector<int> > solution(instance->nbMachines, std::vector<int>(0));
initStaticVectors();
for (int k = 0; k < instance->nbActivities; k++) {
int job = chooseJob();
int machine = nextMachine(job);
solution[machine].push_back(job);
scheduleNextActivity(job);
}

for (int m = 0; m < instance->nbMachines; m++) {
for (int j = 0; j < instance->nbJobs; j++) {
outfile << solution[m][j] << " ";
}
outfile << std::endl;
}
}

private:

// Get the candidate activity with earliest starting time and
// schedule it, unless it would delay jobs of higher priority
// whose next machine is this one, in which case we schedule
// the job with highest priority among these.
int chooseJob() {
int job = selectJobWithEarliestStartingNextActivity();
int machine = nextMachine(job);
lsint end = jobNextActivityEnd(job);
return selectNextPriorityJob(machine, end);
}

// Return the job whose next activity has the earliest start date
int selectJobWithEarliestStartingNextActivity() {
lsint earliestStart = std::numeric_limits<lsint>::max();
int selectedJob;
for (int job = 0; job < instance->nbJobs; job++) {
if (!hasNextActivity(job)) continue;
int machine = nextMachine(job);
lsint start = std::max(machineProgressTime[machine], jobProgressTime[job]);
if (start < earliestStart) {
earliestStart = start;
selectedJob = job;
}
}
return selectedJob;
}

// Select the job of highest priority among jobs
// - whose next machine is machine
// - whose next activity earliest start is before given time
int selectNextPriorityJob(int machine, lsint time) {
for (int k = 0; k < instance->nbJobs; k++) {
int job = priorityList[machine][k];
if (nextMachine(job) != machine) continue;
if (jobProgressTime[job] <= time) return job;
}
return -1;
}

// Schedule the next activity of the given job,
// and update progression variables accordingly.
void scheduleNextActivity(int job) {
int m = nextMachine(job);
lsint end = jobNextActivityEnd(job);
jobProgress[job]++;
machineProgressTime[m] = end;
jobProgressTime[job] = end;
}

bool hasNextActivity(int job) {
return jobProgress[job] < instance->nbMachines;
}

lsint jobNextActivityEnd(int job) {
int nextActivity = jobProgress[job];
int machine = instance->jobMachineOrder[job][nextActivity];
lsint duration = instance->processingTime[job][nextActivity];
lsint start = std::max(machineProgressTime[machine], jobProgressTime[job]);
return start + duration;
}

int nextMachine(int job) {
int nextActivity = jobProgress[job];
if (nextActivity == instance->nbMachines) return -1;
return instance->jobMachineOrder[job][nextActivity];
}

// Fill the priorityList matrix by parsing the LSNativeContext object.
// Return false if the list variables aren't full, what happens
// when the solver hasn't reached feasibility yet.
for (int m = 0; m < instance->nbMachines; m++) {
for (int j = 0; j < instance->nbJobs; j++) {
int val = context.getIntValue(m * instance->nbJobs + j);
if (val < 0) return false;
priorityList[m][j] = val;
}
}
return true;
}

void initPriorityList() {
if(priorityList.size()==0){
priorityList.resize(instance->nbMachines);
for(int m=0; m < instance->nbMachines; m++) {
priorityList[m].resize(instance->nbJobs);
}
}
}
void initStaticVectors() {
jobProgress.clear();
jobProgress.resize(instance->nbJobs, 0);
jobProgressTime.clear();
jobProgressTime.resize(instance->nbJobs, 0);
machineProgressTime.clear();
machineProgressTime.resize(instance->nbMachines, 0);
}

};

class JobshopProblem {
public:
// LocalSolver
LocalSolver localsolver;

// Instance of the JSSP:
const JobshopInstance* instance;

// Decision variables
std::vector<LSExpression> priorityListsVariables;

// Native function for computing the makespan from the priority lists.
LSExpression callMakespanFunc;

// Constructor
JobshopProblem(const JobshopInstance* jsi) : localsolver() {
instance = jsi;
}

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

// For each machine the decision variable is a permuation of all jobs
priorityListsVariables.resize(instance->nbMachines);
for (int m = 0; m < instance->nbMachines; m++) {
priorityListsVariables[m] = model.listVar(instance->nbJobs);
}

for (int m = 0; m < instance->nbMachines; m++) {
model.constraint(model.count(priorityListsVariables[m]) == instance->nbJobs);
}

// Creation of a "Scheduler" object, a native funciton
// for decoding the priority list variables (that is to say computing
// the makespan from these priority lists).
Scheduler sch(instance);

LSExpression makespanFunc = model.createNativeFunction(&sch);
callMakespanFunc = model.call(makespanFunc);

// To call the native function, the priorityListsVariables matrix is
// flatenned in one vector and each element of that vector is added
// as operand.
for (int m = 0; m < instance->nbMachines; m++) {
for (int j = 0; j < instance->nbJobs; j++) {
}
}

// Objective: minimize the total makespan.
model.minimize(callMakespanFunc);

model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);

LSParam params = localsolver.getParam();

localsolver.solve();

}

// Writes the solution in a file with the following format :
//  - for each machine, the job sequence
void writeSolution(const std::string& fileName) {
std::ofstream outfile(fileName.c_str());
if (!outfile.is_open()) {
std::cerr << "File " << fileName << " cannot be opened." << std::endl;
exit(1);
}
std::cout << "Solution written in file " << fileName << std::endl;

std::vector<std::vector<int> > finalPriorityList(instance->nbMachines, std::vector<int>(instance->nbJobs, 0));
for (int m = 0; m < instance->nbMachines; m++) {
LSCollection jobsCollection = priorityListsVariables[m].getCollectionValue();
for (int j = 0; j < instance->nbJobs; j++) {
finalPriorityList[m][j] = jobsCollection[j];
}
}
Scheduler sch(instance);
sch.writeSolution(outfile, finalPriorityList);

outfile.close();
}

};

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

const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "60";

JobshopInstance instance(instanceFile);
JobshopProblem model(&instance);

try {
model.solve(atoi(strTimeLimit));
if(solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const std::exception& e){
std::cerr << "Error occurred: " << e.what() << std::endl;
return 1;
}
}
```
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc Jobshop.cs /reference:localsolvernet.dll
jobshop instances\ft10.txt
```/********** JobShop.cs **********/

using System;
using System.IO;
using System.Linq;
using localsolver;

public class JobshopInstance {
// Number of jobs
public int nbJobs;

// Number of machines
public int nbMachines;

// Number of activities, i.e. nbJobs*nbMachines
public int nbActivities;

// processing order of machines for each job
public int[,] jobMachineOrder;

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

public JobshopInstance(string fileName) {
nbActivities = nbJobs * nbMachines;
}

// The input files follow the "Taillard" format.
nbJobs = int.Parse(splitted[0]);
nbMachines = int.Parse(splitted[1]);

processingTime = new long[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; j++)
{
if (splitted.Length != nbMachines)
{
Console.WriteLine("Error in reading input file. Wrong processingTime matrix size.");
System.Environment.Exit(1);
}
for (int m = 0; m < nbMachines; m++)
{
processingTime[j, m] = long.Parse(splitted[m]);
}
}

jobMachineOrder = new int[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; j++)
{
if (splitted.Length != nbMachines)
{
Console.WriteLine("Error in reading input file. Wrong jobMachineOrder matrix size.");
System.Environment.Exit(1);
}
for (int m = 0; m < nbMachines; m++)
{
jobMachineOrder[j, m] = int.Parse(splitted[m]) - 1;
}
}
}
}
}

public class Scheduler {
// Scheduler allows to obtain a schedule in output from the priority
// list variables. It is based on the simple J. Giffler and G.L. Thompson
// algorithm (1960).

JobshopInstance instance;

// here. Each thread must have have independant following variables.
static int[] jobProgress;
static long[] machineProgressTime;
static long[] jobProgressTime;
static int[,] priorityList;

public Scheduler(JobshopInstance instance) {
this.instance = instance;
}

public void Schedule() {
for (int k = 0; k < instance.nbActivities; k++) {
int job = ChooseJob();
ScheduleNextActivity(job);
}
}

public double GetMakespan() {
return machineProgressTime.Max();
}

public double Call(LSNativeContext context) {
InitStaticVectors();
if (!parsingSucess) return Double.NaN;
ResetStaticVectors();
Schedule();
return GetMakespan();
}

// Return the schedule from the final values of the priority list
// variables. It is only called once at the end if an output file is
//  mentionned.
public void WriteSolution(StreamWriter output, int[,] finalPriorityList) {
priorityList = finalPriorityList;
int[,] solution = new int[instance.nbMachines, instance.nbJobs];
int[] machineProgress = new int[instance.nbMachines];
ResetStaticVectors();
for (int k = 0; k < instance.nbActivities; k++) {
int job = ChooseJob();
int machine = NextMachine(job);
solution[machine, machineProgress[machine]] = job;
machineProgress[machine]++;
ScheduleNextActivity(job);
}

for (int m = 0; m < instance.nbMachines; m++) {
for (int j = 0; j < instance.nbJobs; j++) {
output.Write(solution[m, j] + " ");
}
output.WriteLine();
}
}

// Get the candidate activity with earliest starting time and
// schedule it, unless it would delay the job of higher priority
// whose next machine is this one, in which case we schedule
// the job with highest priority.
int ChooseJob() {
int job = SelectJobWithEarliestStartingNextActivity();
int machine = NextMachine(job);
long end = JobNextActivityEnd(job);
return SelectNextPriorityJob(machine, end);
}

// Return the job whose next activity has the earliest start date
int SelectJobWithEarliestStartingNextActivity() {
long earliestStart = long.MaxValue;
int selectedJob = -1;
for (int job = 0; job < instance.nbJobs; job++) {
if (!HasNextActivity(job)) continue;
int machine = NextMachine(job);
long start = Math.Max(machineProgressTime[machine] , jobProgressTime[job] );
if (start < earliestStart) {
earliestStart = start;
selectedJob = job;
}
}
return selectedJob;
}

// Select the job of highest priority among jobs
// - whose next machine is machine
// - whose next activity earliest start is before given time
int SelectNextPriorityJob(int machine, long time) {
for (int k = 0; k < instance.nbJobs; k++) {
int job = priorityList[machine,k];
if (NextMachine(job) != machine) continue;
if (jobProgressTime[job] <= time) return job;
}
return -1;
}

// Schedule the next activity of the given job,
// and update progression variables accordingly.
void ScheduleNextActivity(int job) {
int m = NextMachine(job);
long end = JobNextActivityEnd(job);
jobProgress[job]++;
machineProgressTime[m] = end;
jobProgressTime[job] = end;
}

bool HasNextActivity(int job) {
return jobProgress[job] < instance.nbMachines;
}

long JobNextActivityEnd(int job) {
int nextActivity = jobProgress[job];
int machine = instance.jobMachineOrder[job, nextActivity];
long duration = instance.processingTime[job, nextActivity];
long start = Math.Max(machineProgressTime[machine], jobProgressTime[job]);
return start + duration;
}

int NextMachine(int job) {
int nextActivity = jobProgress[job];
if (nextActivity == instance.nbMachines) return -1;
return instance.jobMachineOrder[job, nextActivity];
}

// Fill the priorityList matrix by parsing the LSNativeContext object.
// Return false if the list variables aren't full, what happens
// when the solver hasn't reached feasibility yet.
for (int m = 0; m < instance.nbMachines; m++) {
for (int j = 0; j < instance.nbJobs; j++) {
int val = (int)context.GetIntValue(m * instance.nbJobs + j);
if (val < 0) return false;
priorityList[m, j] = val;
}
}
return true;
}

void InitStaticVectors() {
if (priorityList == null) {
priorityList = new int[instance.nbMachines, instance.nbJobs];
}
if(jobProgress == null){
jobProgress = new int[instance.nbJobs];
}
if(jobProgressTime == null){
jobProgressTime = new long[instance.nbJobs];
}
if(machineProgressTime == null){
machineProgressTime = new long[instance.nbMachines];
}

}

void ResetStaticVectors() {
for(int j = 0; j < instance.nbJobs; j++){
jobProgress[j] = 0;
jobProgressTime[j] = 0;
}
for(int m = 0; m < instance.nbMachines; m++){
machineProgressTime[m] = 0;
}
}

}

class JobshopProblem  : IDisposable {

// Solver.
LocalSolver localsolver;

// Instance of the JSSP:
JobshopInstance instance;

// LS Program variables.
LSExpression[] priorityListsVariables;

// Native function for computing the makespan from the priority lists.
LSExpression callMakespanFunc;

// Constructor
public JobshopProblem (JobshopInstance instance) {
localsolver = new LocalSolver();
this.instance = instance;
}

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

void Solve(int limit) {
/* Declares the optimization model. */
LSModel model = localsolver.GetModel();

// For each machine the decision variable is a permuation of all jobs
priorityListsVariables = new LSExpression[instance.nbMachines];
for (int m = 0; m < instance.nbMachines; m++) {
priorityListsVariables[m] = model.List(instance.nbJobs);
}

// All machines must receive each job
for (int m = 0; m < instance.nbMachines; m++) {
model.Constraint(model.Eq(model.Count(priorityListsVariables[m]), instance.nbJobs));
}

// Creation of a "Scheduler" object, a native funciton
// for decoding the priority list variables (that is to say computing
// the makespan from these priority lists).
Scheduler sch = new Scheduler(instance);
LSNativeFunction schedulerFunction = new LSNativeFunction(sch.Call);
LSExpression makespanFunc = model.CreateNativeFunction(schedulerFunction);
callMakespanFunc = model.Call(makespanFunc);

// To call the native function, the priorityListsVariables matrix is
// flatenned in one vector and each element of that vector is added
// as operand.
for (int m = 0; m < instance.nbMachines; m++) {
for (int j = 0; j < instance.nbJobs; j++) {
}
}

// Objective: minimize the total makespan.
model.Minimize(callMakespanFunc);

model.Close();

// Parameterizes the solver.
LSPhase phase = localsolver.CreatePhase();
phase.SetTimeLimit(limit);

LSParam param = localsolver.GetParam();

localsolver.Solve();
}

// Writes the solution in a file with the following format :
//  - for each machine, the job sequence
void WriteSolution(string fileName) {
using (StreamWriter output = new StreamWriter(fileName)) {
int[,] finalPriorityList = new int[instance.nbMachines, instance.nbJobs];
for (int m = 0; m < instance.nbMachines; m++) {
LSCollection jobsCollection = priorityListsVariables[m].GetCollectionValue();
for (int j = 0; j < instance.nbJobs; j++) {
finalPriorityList[m, j] = (int)jobsCollection.Get(j);
}
}
Scheduler sch = new Scheduler(instance);
sch.WriteSolution(output, finalPriorityList);
}
}

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

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

JobshopInstance instance = new JobshopInstance(instanceFile);
using (JobshopProblem model = new JobshopProblem(instance)) {
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_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. jobshop instances/ft10.txt
```/********** Jobshop.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class Jobshop {

private static class JobshopInstance {

// Number of jobs
int nbJobs;

// Number of machines
int nbMachines;

// Number of activities, i.e. nbJobs*nbMachines
int nbActivities;

// processing time on each machine for each job
long[][] processingTime;

// processing order of machines for each job
int[][] jobMachineOrder;

JobshopInstance(String fileName) {
nbActivities = nbJobs * nbMachines;
}

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

if (nbJobs < 1) {
System.out.println("Wrong number of jobs");
System.exit(1);
}
if (nbMachines < 1) {
System.out.println("Wrong number of machines");
System.exit(1);
}
input.nextLine();
input.nextLine();
// processing times for each jobs on each activity, index starts at 0
processingTime = new long[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; j++) {
for (int m = 0; m < nbMachines; m++) {
processingTime[j][m] = input.nextInt();
}
}
input.nextLine();
input.nextLine();
// machine order for each job, index starts at 0
jobMachineOrder = new int[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; j++) {
for (int m = 0; m < nbMachines; m++) {
jobMachineOrder[j][m] = input.nextInt() - 1;
}
}

input.close();

} catch (IOException ex) {
ex.printStackTrace();
}
}

}

private static class Scheduler implements LSNativeFunction {
// Scheduler allows to obtain a schedule in output from the priority
// list variables. It is based on the simple J. Giffler and G.L. Thompson
// algorithm (1960).

final JobshopInstance instance;

// Each thread must have have independant following variables.

public Scheduler(JobshopInstance instance) {
this.instance = instance;
}

public void schedule() {
for (int k = 0; k < instance.nbActivities; k++) {
int job = chooseJob();
scheduleNextActivity(job);
}
}

public double getMakespan() {
double makespan = machineTime.get()[0];
for (int m = 1; m < instance.nbMachines; m++) {
if (makespan < machineTime.get()[m]) {
makespan = machineTime.get()[m];
}
}
return makespan;
}

@Override
public double call(LSNativeContext context) {
initStaticVectors();
if (!parsingSucess) return Double.NaN;
resetStaticVectors();
schedule();
return getMakespan();
}

// Return the correct scheduled from the final values of the priority list
// variables. It is only called once at the end if an output file is
//  mentionned.s
public void writeSolution(PrintWriter output, int[][] finalPriorityList) {
priorityList.set(finalPriorityList.clone());
int[][] solution = new int[instance.nbMachines][instance.nbJobs];
int[] machineProgress = new int[instance.nbMachines];
resetStaticVectors();
for (int k = 0; k < instance.nbActivities; k++) {
int job = chooseJob();
int machine = nextMachine(job);
solution[machine][machineProgress[machine]] = job;
machineProgress[machine]++;
scheduleNextActivity(job);
}
for (int m = 0; m < instance.nbMachines; m++) {
for (int j = 0; j < instance.nbJobs; j++) {
output.write(solution[m][j] + " ");
}
output.write("\n");
}
}

// Get the candidate activity with earliest starting time and
// schedule it, unless it would delay the job of higher priority
// whose next machine is this one, in which case we schedule
// the job with highest priority.
private int chooseJob() {
int job = selectJobWithEarliestStartingNextActivity();
int machine = nextMachine(job);
long endJob = jobNextActivityEnd(job);
int nextPriorityJobOnMachine = selectNextPriorityJob(machine);
if(jobProgressTime.get()[nextPriorityJobOnMachine] < endJob) return nextPriorityJobOnMachine;
else return job;
}

// Return the job whose next activity has the earliest start date
private int selectJobWithEarliestStartingNextActivity() {
long earliestStart = Integer.MAX_VALUE;
int selectedJob = -1;
for (int job = 0; job < instance.nbJobs; job++) {
if (!hasNextActivity(job)) continue;
int machine = nextMachine(job);
long start;
if( machineTime.get()[machine] < jobProgressTime.get()[job]) start = jobProgressTime.get()[job];
else start = machineTime.get()[machine];
if (start < earliestStart) {
earliestStart = start;
selectedJob = job;
}
}
return selectedJob;
}

// Select the job of highest priority among jobs
// - whose next machine is machine
// - whose next activity earliest start is before given time
private int selectNextPriorityJob(int machine) {
for (int k = 0; k < instance.nbJobs; k++) {
int job = priorityList.get()[machine][k];
if (nextMachine(job) == machine) return job;
}
return -1;
}

// Schedule the next activity of the given job,
// and update progression variables accordingly.
private void scheduleNextActivity(int job) {
int m = nextMachine(job);
long end = jobNextActivityEnd(job);
jobProgress.get()[job]++;
machineTime.get()[m] = end;
jobProgressTime.get()[job] = end;
}

private boolean hasNextActivity(int job) {
return jobProgress.get()[job] < instance.nbMachines;
}

private long jobNextActivityEnd(int job) {
int nextActivity = jobProgress.get()[job];
int machine = instance.jobMachineOrder[job][nextActivity];
long duration = instance.processingTime[job][nextActivity];
long start;
if( machineTime.get()[machine] < jobProgressTime.get()[job]) start = jobProgressTime.get()[job];
else start = machineTime.get()[machine];
return start + duration;
}

private int nextMachine(int job) {
int nextActivity = jobProgress.get()[job];
if (nextActivity == instance.nbMachines) return -1;
return instance.jobMachineOrder[job][nextActivity];
}

// Fill the priorityList matrix by parsing the LSNativeContext object.
// Return false if the list variables aren't full, what happens
// when the solver hasn't reached feasibility yet.
for (int m = 0; m < instance.nbMachines; m++) {
for (int j = 0; j < instance.nbJobs; j++) {
long val = context.getIntValue(m * instance.nbJobs + j);
if (val < 0) {
return false;
}
priorityList.get()[m][j] = Math.toIntExact(val);
}
}
return true;
}

private void initStaticVectors() {
if (priorityList==null) {
priorityList = ThreadLocal.withInitial( () -> new int[instance.nbMachines][instance.nbJobs]);
}
if(jobProgress == null){
jobProgress = ThreadLocal.withInitial( () -> new int[instance.nbJobs]);
}
if(jobProgressTime == null){
jobProgressTime = ThreadLocal.withInitial( () -> new long[instance.nbJobs]);
}
if(machineTime == null){
machineTime = ThreadLocal.withInitial( () -> new long[instance.nbMachines]);
}

}

private void resetStaticVectors() {
for(int j = 0; j < instance.nbJobs; j++){
jobProgress.get()[j] = 0;
jobProgressTime.get()[j] = 0;
}
for(int m = 0; m < instance.nbMachines; m++){
machineTime.get()[m] = 0;
}
}

}

private static class JobshopProblem {

// Solver
private LocalSolver localsolver;

// instance of the JSSP :
public JobshopInstance instance;

// Decision variables
private LSExpression[] priorityListsVariables;

// Native function for computing the makespan from the priority lists.
private LSExpression callMakespanFunc;

public JobshopProblem(JobshopInstance instance) {
localsolver = new LocalSolver();
this.instance = instance;
}

void solve(int limit) {

// Declares the optimization model.
LSModel model = localsolver.getModel();

// For each machine the decision variable is a permuation of all jobs
priorityListsVariables = new LSExpression[instance.nbMachines];
for (int m = 0; m < instance.nbMachines; m++) {
priorityListsVariables[m] = model.listVar(instance.nbJobs);
}

// All machines must receive each job
for (int m = 0; m < instance.nbMachines; m++) {
model.constraint(model.eq(model.count(priorityListsVariables[m]), instance.nbJobs));
}

// Creation of a "Scheduler" object, a native funciton
// for decoding the priority list variables (that is to say computing
// the makespan from these priority lists).
Scheduler sch = new Scheduler(instance);
LSExpression makespanFunc = model.createNativeFunction(sch);
callMakespanFunc = model.call(makespanFunc);

// To call the native function, the priorityListsVariables matrix is
// flatenned in one vector and each element of that vector is added
// as operand.
for (int m = 0; m < instance.nbMachines; m++) {
for (int j = 0; j < instance.nbJobs; j++) {
}
}

// Objective: minimize the total makespan.
model.minimize(callMakespanFunc);

model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);

LSParam param = localsolver.getParam();

localsolver.solve();

}

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

int[][] finalPriorityList = new int[instance.nbMachines][instance.nbJobs];
for (int m = 0; m < instance.nbMachines; m++) {
LSCollection jobsCollection = priorityListsVariables[m].getCollectionValue();
for (int j = 0; j < instance.nbJobs; j++) {
finalPriorityList[m][j] = Math.toIntExact(jobsCollection.get(j));
}
}
Scheduler sch = new Scheduler(instance);
sch.writeSolution(output, finalPriorityList);

output.close();
}
}

}

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

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

try {
JobshopInstance instance = new JobshopInstance(instanceFile);
JobshopProblem model = new JobshopProblem(instance);
model.solve(Integer.parseInt(strTimeLimit));

if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}

}

}
```