Welcome

In this page, we briefly discuss setting up a productive environment for the assignment. The following pages provide an high-level view of the architecture and main components of the provided source code.

Useful links:

Subject
Base code (cloned for you by Github classroom)
Documentation (this)
Javadoc
Moodle

Setting up

Start by accepting the GitHub classroom assignment :

Go to the invite link
Select your name in the list to associate it with you github account (there is a particular link that you can follow if you do not appear in the list). This should create a private repository to which only yourself and the teachers have access.
- your repository should be named in the format {GROUP} {LASTNAME1} / {LASTNAME2}
Clone the repository and get started.
- consider setting up SSH github seems to put more and more restriction on other authentication modes.

Working in IntelliJ

For working on this project, we recommend using the IntelliJ-IDEA development environment. It is available in INSA's classrooms as well as on montp.insa-toulouse.fr.

To import the project in IntelliJ (once IntelliJ is running):

Open a new project : Open project or File > Open
Select the pom.xml file in the cloned repository.
Select Open as project.

To run the program in IntelliJ, you can

Right click on the src/main/java/jobshop/Main class in the project view.
Select Run Main.main(). The program should execute but complain that some arguments are missing.
Specify the expected command line arguments :
- open the run configuration dialog: Run > Edit Configuration
- fill in the Program arguments text box with --solver basic --instance aaa1 aaa2 (more details on the meaning of the arguments is given in the next documentation page)

Working on the command line (Maven)

Compilation instructions are given for Linux (it should work on Windows as well but you are on your own).

❯ mvn compile    # Compiles the project

The project can be executed directly with the mvn command by specifying the arguments like so:

❯ mvn compile exec:java -Dexec.args="--solver basic --instance aaa1 ft"

You can also build an executable jar file, and run it with the java command. This is especially useful if you want to run it on another machine.

 # Create a jar file with all dependencies in as `target/jobshop-1.0-SNAPSHOT-jar-with-dependencies.jar`
❯ mvn package assembly:single
# Run the jar file. Only requires a Java Runtime Environment (JRE)
❯ java -jar target/jobshop-1.0-SNAPSHOT-jar-with-dependencies.jar --solver basic --instance ft06

Entry Points

Unit tests

Several unit tests are provided to test that the different functionalities work. As always in java project, the source code for the test can be found in the src/test/java directory.

Among the existing unit tests, the jobshop.encodings.ManualEncodingTests contains two tests that are currently disabled and should be completed.

`jobshop.Main`

This is the principal entry point that aims at helping you running many solvers on many instances and comparing the results. It expects several command line arguments to specify which solvers to run and which instance to solve.

Usage: jsp-solver [-h] [-t TIMEOUT] --solver SOLVER [SOLVER ...]
                  --instance INSTANCE [INSTANCE ...]

Solves jobshop problems.

named arguments:
  -h, --help             show this help message and exit
  -t TIMEOUT, --timeout TIMEOUT
                         Solver  timeout  in  seconds  for  each  instance.
                         (default: 1)
  --solver SOLVER [SOLVER ...]
                         Solver(s) to use  (space  separated  if  more than
                         one)
  --instance INSTANCE [INSTANCE ...]
                         Instance(s) to  solve  (space  separated  if  more
                         than one). All instances  starting  with the given
                         String will be  selected.  (e.g.  "ft" will select
                         the instances ft06, ft10 and ft20.

Example usage

# Running the Main program with maven (LINUX)
mvn compile exec:java -Dexec.args="--solver basic --instance ft06"

# Windows (PowerShell)
mvn compile exec:java "-Dexec.args=--solver basic --instance ft06"

The command line above indicates that we want to solve the instance namedft06 with the basic solver. It should give an output like the following:

                         basic
instance size  best      runtime makespan ecart
ft06     6x6     55            1       60   9.1
AVG      -        -          1.0        -   9.1

Fields in the result view are the following :

instance: name of the instance
size: size of the instance {num-jobs}x{num-tasks}
best: best known result for this instance
runtime: time taken by the solver in milliseconds (rounded)
makespan: makespan of the solution
ecart: normalized distance to the best result: 100 * (makespan - best) / best

One can also specify multiple solvers (below basic and random) and instances (below ft06, ft10 and ft20) for simultaneous testing (note that the random solver is not defined yet):

❯ mvn compile exec:java -Dexec.args="--solver basic random --instance ft06 ft10 ft20"

                         basic                         random
instance size  best      runtime makespan ecart        runtime makespan ecart
ft06     6x6     55            1       60   9.1            999       55   0.0
ft10     10x10  930            0     1319  41.8            999     1209  30.0
ft20     20x5  1165            0     1672  43.5            999     1529  31.2
AVG      -        -          0.3        -  31.5          999.0        -  20.4

Here the last line give the average runtime and ecart for each solver.

Tip: When selecting instances to solve, you can only provide a prefix to instance names. All instances that start with this prefix will be selected. For instance running the program with the option --instance la will select all Lawrences instance (la01 to la40).

Instances

The project comes with a set of predefined jobshop instances that you will use for the project. All instances are provided in the instances/ folder of the repository.

Test instances

Test instances start with the aaa prefix. We provide three of them

aaa1: a very small instance that you can use to get acquainted with the different encodings
aaa2: a slightly more complex instance that has been used during the classes
aaa3: an instance that produces deterministic results for the greedy methods

Benchmark instances

All other instances are common benchmarks that you can use to test the performance of your algorithms.

You can find more informations (lower and upper bounds, best known solutions, ...) on the website http://jobshop.jjvh.nl/index.php.

Encodings

Several encoding and associated utilities are provided in the jobshop.encodings package. The abstract class Encoding provides a common interface for all encodings. The only requirement for an encoding is to be able to transform itself into a Schedule.

The jobshop.encodings package contains a Task class that allows representing a particular task of a jobshop instance. A Task object contains a pair of integers (job, task) that respectively specify the job in which the task appears, and the index of the task in this job. For instance the task created with new Task(0, 2) would represent the third task of the first job.

Schedule

The Schedule is direct encoding of a solution: it associates every task in the jobshop instance to a start time.

It plays a particular role as it is the standard way of representing a solution. As a consequence, all other encodings must provide a way to produce a schedule.

Convenience methods:

isValid(): returns true if the schedule is valid (no violated constraints).
makespan(): computes the makespan of the solution.
criticalPath(): returns a critical path in the solution.
asciiGantt(): generates a Gantt chart view of the solution in ASCII art.

ResourceOrder

The resource order encoding specifies the order in which each machine will process its tasks.

Each machine is associated with an array of tasks that specifies the order on which the tasks must be scheduled on the machine.

For instance, the (completely fictional) encoding:

machine 0: [(0, 1), (1, 0)]
machine 1: [(0, 0), (1, 1)]
machine 2: [(1, 2), (0, 2)]

specifies that the first machine (machine 0) will first process the second task of the first job (0, 1) and only when it is finished can start processing the first task of the second job (1, 0).

Note that the ResourceOrder encoding might represent invalid solutions. In this case, its toSchedule() method will return an empty result.

Solvers

The `Solver` interface

jobshop.solvers.Solver provides a common interface for all solvers.

Implementing the Solver interface requires implementing a method solve(Instance instance, long deadline) where:

instance is the jobshop instance that should be solved.
deadline is the absolute time by which the solver should have exited. This deadline is in milliseconds and can be compared with the result of System.currentTimeMillis().

The solve() method should return a Optional<Schedule> object, that provides the found solution (if any) as a Schedule.

`BasicSolver`

A very simple solver that tries to schedule all first tasks, then all second tasks, then all third tasks, ... It does so using the ResourceOrder encoding.

`GreedySolver`

The greedy solver is not implemented yet. Its constructor accepts a parameter that specifies the priority that should be used to produce solutions.

`DescentSolver`

Not implemented yet. It should use the Nowicki and Smutnicki neighborhood for which some initial code is provided in the jobshop.solver.neighborhood package.

Benchmarking Tips and Tricks

Below are a few advices to facilitate the evaluation of your solvers. Feel free to follow them if them seem relevant to you and to adapt them to your own use-cases.

Easily testing with different parameters

One can expect some solvers to have a lot of possible parameters. It would be impractical to manually define a name for each of the possible variants. What would be really nice would be to have the program automatically understand that:

taboo refers to the taboo method with the default parameters
taboo__est-spt__20 refers to the taboo method with a taboo size of 20 and the est-spt solver to provide the initial solution
taboo__descent__10 refers to the taboo method with a taboo size of 10 and the descent solver to provide the initial solution

Here is a partial example of an implementation of the Solver.getSolver() method that leverages regular expressions to do exactly that. It should of course be adapted to match the parameters of your own solvers, for instance, a value for the parameter 'maxIter' in the taboo method or the neighborhood to use.

/** Static factory method to create a new solver based on its name. */
static Solver getSolver(String name) {
    switch (name) {
        case "basic": return new BasicSolver();
        ...
        // taboo with some default parameters
        case "taboo": return new TabooSolver(getSolver("est_lrpt"), 20);
        default:
            // not one of the predefined solvers, try to see if we can extract parameters from the solver name
            // using Pattern/Matcher from java.util.regex package
            Pattern taboo = Pattern.compile("taboo__([a-z_]+)__([0-9]+)");
            Matcher m = taboo.matcher(name);
            if (m.find()) {
                String baseSolverName = m.group(1);
                int tabooSize = Integer.parseInt(m.group(2));
                return new TabooSolver(getSolver(baseSolverName), tabooSize);
            }
            // not a taboo, try matching with descent
            Pattern descent = Pattern.compile("descent__([a-z_]+)");
            ...
            throw new RuntimeException("Unknown solver: "+ name);
    }
}

Using INSA's compute servers

To launch your experimental analysis, you can use one of the available compute servers (accessible with INSA's VPN): srv-gei-gpu1 , srv-gei-gpu2 or srv-ens-calcul

Those server are suppose to be always on. You can check with the uptime command for how long a server has been running. Please notify us if the server has been recently restarted of if you have any problem acccessing them.

# Example to connect to srv-gei-gpu2
moi@mamachine:~$ ssh srv-gei-gpu2
moi@srv-gei-gpu2 password: 
...
Welcome to Ubuntu 18.04.5 LTS (GNU/Linux 5.4.0-72-generic x86_64)
...
moi@srv-gei-gpu2:~$ cd PATH/TO/MY/CODE
moi@srv-gei-gpu2:~/MyCode$ mvn compile
moi@srv-gei-gpu2:~/MyCode$
moi@srv-gei-gpu2:~/MyCode$ nohup  mvn compile exec:java -Dexec.args="--solver method1 method2 (...)  --instance ta (...)" > MyOuFile 2> MyErrFile &

Before running any benchmark, you should check that the server is not already under heavy load, which might impact the performance of your program. You can manually check that with the top command.

Automating the collection and analysis of results

The jobshop.Main program that is provided to you is a good start to build you own benchmarking suite. However, the results that are printed on the standard output are mostly intended to be easily readable by a human being, not by a computer program.

To automate the the collection of results and their analysis, you might want to modify the jobshop.Main program to:

accept an additional command line argument that specifies a filename to which the collected data must be exported.
if this argument is specified, then write the results to this file in commonly accepted format. A very common format for this is the CSV (Comma Separated Value) format that can be:
- opened in spreadsheet software such as Excel or LibreOffice
- read from most programming languages (including python with the csv or pandas modules)
have automated scripts that process the results files, for instance to produce some graphs. In python, the matplotlib package is useful for making some graphs and the pandas package to perform some statistical analysis. The gnuplot program is also commonly used to create graphs from CSV data.

JobShop Scheduling (INSA 4IR)