JobShop

Principles learned

  • Call a native function
  • Maintain thread-safety property
  • Add multiple list decision variables
  • Constrain the number of elements in a list

Problem

../_images/jobshop.png

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.

Download the example

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

Consult the dedicated section of the documentation for more information about 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.read_instance(filename)
        self.nb_activities = self.nb_jobs * self.nb_machines

    # The input files follow the "Taillard" format.
    def read_instance(self, filename):
        with open(filename) as f:
            lines = f.readlines()
        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):
        parsingSucces = self.read_flattened_matrix(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.
    def read_flattened_matrix(self, context):
        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):
            call_makespan_func.add_operand(priority_lists_variables[m][t])

    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.param.set_nb_threads(1)

    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) {
        readInstance(fileName);
        nbActivities = nbJobs * nbMachines;
    }

private:

    // The input files follow the "Taillard" format.
    void readInstance(const std::string& fileName) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
        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;

    // To maintain thread-safety property, thread_local (since C++11) is used
    // here. Each thread must have have independant following variables.
    static thread_local std::vector<int> jobProgress;
    static thread_local std::vector<lsint> machineProgressTime;
    static thread_local std::vector<lsint> jobProgressTime;
    static thread_local std::vector<std::vector<int>> priorityList;

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();
        bool parsingSucess = readFlattenedMatrix(context);
        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.
    bool readFlattenedMatrix(const LSNativeContext& context) {
        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++) {
                callMakespanFunc.addOperand(priorityListsVariables[m][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();
        params.setNbThreads(4);

        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();
    }

};

thread_local std::vector<int> Scheduler::jobProgress;
thread_local std::vector<lsint> Scheduler::machineProgressTime;
thread_local std::vector<lsint> Scheduler::jobProgressTime;
thread_local std::vector<std::vector<int>> Scheduler::priorityList;

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.Threading;
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) {
      ReadInstance(fileName);
      nbActivities = nbJobs * nbMachines;
    }

    // The input files follow the "Taillard" format.
    void ReadInstance(string fileName) {
        using (StreamReader input = new StreamReader(fileName)) {
            input.ReadLine();
            string[] splitted = input.ReadLine().Split(' ');
            nbJobs = int.Parse(splitted[0]);
            nbMachines = int.Parse(splitted[1]);

            input.ReadLine();
            processingTime = new long[nbJobs, nbMachines];
            for (int j = 0; j < nbJobs; j++)
            {
                splitted = input.ReadLine().Trim().Split(' ');
                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]);
                }
            }

            input.ReadLine();
            jobMachineOrder = new int[nbJobs, nbMachines];
            for (int j = 0; j < nbJobs; j++)
            {
                splitted = input.ReadLine().Trim().Split(' ');
                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;

    // To maintain thread-safety property, ThreadStatic is used
    // here. Each thread must have have independant following variables.
    [ThreadStatic]
    static int[] jobProgress;
    [ThreadStatic]
    static long[] machineProgressTime;
    [ThreadStatic]
    static long[] jobProgressTime;
    [ThreadStatic]
    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();
        bool parsingSucess = ReadFlattenedMatrix(context);
        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.
    bool ReadFlattenedMatrix(LSNativeContext context) {
        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++) {
                callMakespanFunc.AddOperand(model.At(priorityListsVariables[m], 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();
        param.SetNbThreads(4);

        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) {
            readInputJobShop(fileName);
            nbActivities = nbJobs * nbMachines;
        }

        // The input files follow the "Taillard" format.
        private void readInputJobShop(String fileName) {
            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;

        // To maintain thread-safety property, ThreadLocal is used here.
        // Each thread must have have independant following variables.
        private static ThreadLocal<int[]> jobProgress;
        private static ThreadLocal<long[]> machineTime;
        private static ThreadLocal<long[]> jobProgressTime;
        private static ThreadLocal<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() {
            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();
            boolean parsingSucess = readFlattenedMatrix(context);
            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.
        private boolean readFlattenedMatrix(LSNativeContext context) {
            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++) {
                    callMakespanFunc.addOperand(model.at(priorityListsVariables[m], 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();
            param.setNbThreads(4);

            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);
        }


    }

}