Flowshop

Principles learned

  • Define the actual set of decision variables
  • Add a list decision variable
  • Access the list elements with an “at” operator
  • Access an array with an “at” operator at an index that is an expression
  • Define a sequence of expressions
  • Define an array with a recursive function

Problem

../_images/flowshop.png

A set of jobs has to be processed on every machine of the shop. Each machine can work in parallel but the sequence of jobs on every machine must be the same. Each machine can only process one job at a time. The workflow is the following: the first job of the sequence goes to the first machine to be processed; meanwhile, other jobs wait; when the first machine has processed the first job, the first job goes to the second machine and the second job of the sequence starts to be processed by the first machine; and so on. If a job has been processed by a machine but the next machine is still busy, it waits until the next machine is empty, but it leaves its last machine empty.

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 are from Taillard. 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 machine: the processing time of each job on this machine

Program

The only decision variable of the model is a list variable which describes the sequence of jobs. We constrain all the jobs to be processed thanks to the “count” operator.

In general, a job starts on a machine when it has been processed by the previous machine and when the machine is empty (when the previous job has been processed by the machine): it is the maximum of these two times. The start time expressions are created as so with the “max” operator. A job ends on a machine after it has been processed. The end time expressions are created by summing the start time and the processing time of the jth job of the sequence on this machine. This processing time is simply an “at” operator to retrieve the processing time on the right index.

The definition of ending times for the first machine will be different to the definition for other machines:

  • On the first machine, each job starts right after the previous job has ended, because it was queuing to start processing; and the first job starts at t=0. It can be written as a recursive array. Note that the conventional value (0) of the predecessor of the first item is appropriate here since the first job starts at 0.
  • On every other machine, the end time of each job depends on the end of the previous job in the sequence and the end of the previous job on the same machine. Here again this definition is written with a recursive array.

The makespan to minimize is just the time when the last job of the sequence has been processed by the last machine: end[nbMachines-1][nbJobs-1].

If you are interested in the general case, where the ordering on each machine is free, you can now study our jobshop model.

Execution:
localsolver flowshop.lsp inFileName=instances/tai20_5.txt [lsTimeLimit=] [solFileName=]
/********** flowshop.lsp **********/

use io;

/* Reads instance data */
function input() {
    local usage = "Usage: localsolver flowshop.lsp "
        + "inFileName=inputFile [lsTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;
    local inFile = io.openRead(inFileName);

    nbJobs = inFile.readInt();
    nbMachines = inFile.readInt();
    initialSeed = inFile.readInt();
    upperBound = inFile.readInt();
    lowerBound = inFile.readInt();
    processingTime[m in 0..nbMachines-1][j in 0..nbJobs-1] = inFile.readInt();
}

/* Declares the optimization model. */
function model() {
    // Permutation of jobs
    jobs <- list(nbJobs);

    // All jobs have to be assigned
    constraint count(jobs) == nbJobs;

    // On machine 0, the jth job ends on the time it took to be processed after 
    // the end of the previous job
    end[0] <- array(0..nbJobs-1, (i, prev) => prev + processingTime[0][jobs[i]]);

    // The jth job on machine m starts when it has been processed by machine n-1
    // AND when job j-1 has been processed on machine m. It ends after it has been processed.
    for[m in 1..nbMachines-1] {
        end[m] <- array(0..nbJobs-1, (i, prev) => max(prev, end[m-1][i]) + processingTime[m][jobs[i]]);
    }

    // Minimize the makespan: end of the last job on the last machine
    makespan <- end[nbMachines-1][nbJobs-1];
    minimize makespan;
}

/* Parameterizes the solver. */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 5;
}

/* Writes the solution in a file */
function output() {
    if (solFileName == nil) return;

    local solFile = io.openWrite(solFileName);
    solFile.println(makespan.value);
    for[j in jobs.value]
        solFile.print(j + " ");
    solFile.println();
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python27\
python flowshop.py instances\tai20_5.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python flowshop.py instances/tai20_5.txt
########## flowshop.py ##########

import localsolver
import sys

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


def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]


with localsolver.LocalSolver() as ls:

    #
    # Reads instance data
    #
    file_it = iter(read_integers(sys.argv[1]))

    nb_jobs = int(file_it.next())
    nb_machines = int(file_it.next())
    initial_seed = int(file_it.next())
    upper_bound = int(file_it.next())
    lower_bound = int(file_it.next())

    processing_time = [[int(file_it.next()) for j in range(nb_jobs)] for j in range(nb_machines)] 

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

    # Permutation of jobs
    jobs = model.list(nb_jobs)    

    # All jobs have to be assigned
    model.constraint(model.eq(model.count(jobs), nb_jobs))

    # For each machine create proccessingTime[m] as an array to be able to access it 
    # with an 'at' operator
    processing_time_array = [model.array(processing_time[m]) for m in range(nb_machines)]

    # On machine 0, the jth job ends on the time it took to be processed after the end of the previous job
    end = [None for j in range(nb_machines)]
    
    first_end_selector = model.function(lambda i,prev: prev + model.at(processing_time_array[0],jobs[i]))
    
    end[0] = model.array(model.range(0, nb_jobs), first_end_selector)
   
    # The jth job on machine m starts when it has been processed by machine n-1
    # AND when job j-1 has been processed on machine m. It ends after it has been processed.
    for m in range(1,nb_machines):
        mL = m
        end_selector = model.function(lambda i,prev: \
                    model.max(prev, model.at(end[mL - 1], i)) + \
                    model.at(processing_time_array[mL], jobs[i]))
        end[m] = model.array(model.range(0, nb_jobs), end_selector)
        

    # Minimize the makespan: end of the last job on the last machine
    makespan = end[nb_machines-1][nb_jobs-1]
    model.minimize(makespan)

    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 = 5

    ls.solve()

    #
    # Writes the solution in a file
    #
    if len(sys.argv) >= 3:
        with open(sys.argv[2], 'w') as f:
            f.write("%d\n" % makespan.value)
            for j in jobs.value:
                f.write("%d " % j)
            f.write("\n")
Compilation / Execution (Windows)
cl /EHsc flowshop.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
flowshop instances\tai20_5.txt
Compilation / Execution (Linux)
g++ flowshop.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o flowshop
./flowshop instances/tai20_5.txt
/********** flowshop.cpp **********/

#include <iostream>
#include <fstream>
#include <vector>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

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

    // Number of machines
    int nbMachines;

    // Initial seed used to generate the instance
    long initialSeed;

    // Upper bound
    int upperBound;

    // Lower bound
    int lowerBound;

    // Processing time
    vector<vector<lsint> > processingTime;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variable
    LSExpression jobs;

    // Objective
    LSExpression makespan;

    // Reads instance data.
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> nbJobs;
        infile >> nbMachines;
        infile >> initialSeed;
        infile >> upperBound;
        infile >> lowerBound;

        processingTime.resize(nbMachines);
        for (int m = 0; m < nbMachines; m++) {
            processingTime[m].resize(nbJobs);
            for (int j = 0; j < nbJobs; j++) {
                infile >> processingTime[m][j];
            }
        }
    }

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

        // Permutation of jobs
        jobs = model.listVar(nbJobs);

        // All jobs have to be assigned
        model.constraint(model.count(jobs) == nbJobs);

        // For each machine create proccessingTime[m] as an array to be able to access it 
        // with an 'at' operator
        vector<LSExpression> processingTimeArray(nbMachines);
        for (int m = 0; m < nbMachines; m++) {
            processingTimeArray[m] = model.array(processingTime[m].begin(), processingTime[m].end());
        }            
        
        // On machine 0, the jth job ends on the time it took to be processed after 
        // the end of the previous job
        vector<LSExpression> end(nbMachines);
        LSExpression firstEndSelector = model.createFunction([&](LSExpression i, LSExpression prev) { 
            return prev + processingTimeArray[0][jobs[i]]; 
        });    
        end[0] = model.array(model.range(0, nbJobs), firstEndSelector);

        // The jth job on machine m starts when it has been processed by machine n-1
        // AND when job j-1 has been processed on machine m. It ends after it has been processed.
        for (int m = 1; m < nbMachines; ++m) {
            int mL = m;
            LSExpression endSelector = model.createFunction([&](LSExpression i, LSExpression prev) { 
                return model.max(prev, end[mL - 1][i]) + processingTimeArray[mL][jobs[i]];
            });
            end[m] = model.array(model.range(0, nbJobs), endSelector);
        }

        // Minimize the makespan: end of the last job on the last machine
        makespan = end[nbMachines - 1][nbJobs - 1];
        model.minimize(makespan);
        model.close();            


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

    // Writes the solution in a file
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << makespan.getValue() << endl;
        LSCollection jobsCollection = jobs.getCollectionValue();
        for (int j = 0; j < nbJobs; j++) {
            outfile << jobsCollection[j] << " ";
        }
        outfile << endl;       
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: flowshop inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }

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

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

using System;
using System.IO;
using localsolver;

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

    // Number of machines
    int nbMachines;

    // Initial seed used to generate the instance
    long initialSeed;

    // Upper bound
    int upperBound;

    // Lower bound
    int lowerBound;

    // Processing time
    long[][] processingTime;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variable
    LSExpression jobs;

    // Objective
    LSExpression makespan;

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

    // Reads instance data. 
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] firstLineSplit = input.ReadLine().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
            nbJobs = int.Parse(firstLineSplit[0]);
            nbMachines = int.Parse(firstLineSplit[1]);
            initialSeed = int.Parse(firstLineSplit[2]);
            upperBound = int.Parse(firstLineSplit[3]);
            lowerBound = int.Parse(firstLineSplit[4]);

            string[] matrixText = input.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
            processingTime = new long[nbMachines][];
            for (int m = 0; m < nbMachines; m++)
            {
                processingTime[m] = new long[nbJobs];
                for (int j = 0; j < nbJobs; j++)
                {
                    processingTime[m][j] = long.Parse(matrixText[m * nbJobs + j]);
                }
            }
        }
    }

    public void Dispose()
    {
        if (localsolver != null)
            localsolver.Dispose();
    }

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

        // Permutation of jobs
        jobs = model.List(nbJobs);

        // All jobs have to be assigned
        model.Constraint(model.Count(jobs) == nbJobs);

        // For each machine create proccessingTime[m] as an array to be able to access it 
        // with an 'at' operator
        LSExpression[] processingTimeArray = new LSExpression[nbMachines];
        for (int m = 0; m < nbMachines; m++)
            processingTimeArray[m] = model.Array(processingTime[m]);

        // On machine 0, the jth job ends on the time it took to be processed after 
        // the end of the previous job
        LSExpression[] end = new LSExpression[nbJobs];
        LSExpression firstEndSelector = model.Function((i, prev) => prev + processingTimeArray[0][jobs[i]]);
        end[0] = model.Array(model.Range(0, nbJobs), firstEndSelector);

        // The jth job on machine m starts when it has been processed by machine n-1
        // AND when job j-1 has been processed on machine m. It ends after it has been processed.
        for (int m = 1; m < nbMachines; ++m)
        {
            LSExpression endSelector = model.Function((i, prev) => model.Max(prev, end[m - 1][i]) + processingTimeArray[m][jobs[i]]);
            end[m] = model.Array(model.Range(0, nbJobs), endSelector);
        }

        // Minimize the makespan: end of the last job on the last machine
        makespan = end[nbMachines - 1][nbJobs - 1];
        model.Minimize(makespan);

        model.Close();

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

        localsolver.Solve();
    }

    // Writes the solution in a file
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(makespan.GetValue());
            LSCollection jobsCollection = jobs.GetCollectionValue();
            for (int j = 0; j < nbJobs; j++)
            {
                output.Write(jobsCollection[j] + " ");
            }
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Flowshop inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "5";

        using (Flowshop model = new Flowshop())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac Flowshop.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Flowshop instances\tai20_5.txt
Compilation/Execution (Linux)
javac Flowshop.java -cp /opt/localsolver_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Flowshop instances/tai20_5.txt
/********** Flowshop.java **********/

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

public class Flowshop {
    // Number of jobs
    private int nbJobs;

    // Number of machines
    private int nbMachines;

    // Initial seed used to generate the instance
    private long initialSeed;

    // Upper bound
    private int upperBound;

    // Lower bound
    private int lowerBound;

    // Processing time
    private long[][] processingTime;

    // LocalSolver
    private LocalSolver localsolver;

    // Decision variable
    private LSExpression jobs;

    // Objective
    private LSExpression makespan;

    // Reads instance data.
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            nbJobs = input.nextInt();
            nbMachines = input.nextInt();
            initialSeed = input.nextInt();
            upperBound = input.nextInt();
            lowerBound = input.nextInt();

            processingTime = new long[nbMachines][nbJobs];
            for (int m = 0; m < nbMachines; m++) {
                for (int j = 0; j < nbJobs; j++) {
                    processingTime[m][j] = input.nextInt();
                }
            }
        }
    }

    private void solve(int limit) {
        localsolver = new LocalSolver();

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

        // Permutation of jobs
        jobs = model.listVar(nbJobs);

        // All jobs have to be assigned
        model.constraint(model.eq(model.count(jobs), nbJobs));

        // For each machine create proccessingTime[m] as an array to be able to access it
        // with an 'at' operator
        LSExpression[] processingTimeArray = new LSExpression[nbMachines];
        for (int m = 0; m < nbMachines; m++) {
            processingTimeArray[m] = model.array(processingTime[m]);
        }

        // On machine 0, the jth job ends on the time it took to be processed after 
        // the end of the previous job
        LSExpression[] end = new LSExpression[nbJobs];
        LSExpression firstEndSelector = model.function((i, prev) -> model.sum(
                    prev, model.at(processingTimeArray[0], model.at(jobs, i))));
        end[0] = model.array(model.range(0, nbJobs), firstEndSelector);

        // The jth job on machine m starts when it has been processed by machine n-1
        // AND when job j-1 has been processed on machine m. It ends after it has been processed.
        for (int m = 1; m < nbMachines; ++m)
        {
            final int mL = m;
            LSExpression endSelector = model.function((i, prev) -> model.sum(
                    model.max(prev, model.at(end[mL - 1], i)),
                    model.at(processingTimeArray[mL], model.at(jobs, i))));
            end[m] = model.array(model.range(0, nbJobs), endSelector);
        }

        // Minimize the makespan: end of the last job on the last machine
        makespan = model.at(end[nbMachines - 1], nbJobs - 1);
        model.minimize(makespan);
        model.close();

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

        localsolver.solve();
    }

    // Writes the solution in a file
    private void writeSolution(String fileName) throws IOException {
        try(PrintWriter output = new PrintWriter(fileName)) {
            output.println(makespan.getValue());
            LSCollection jobsCollection = jobs.getCollectionValue();
            for (int j = 0; j < nbJobs; j++) {
                output.print(jobsCollection.get(j) + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java Flowshop 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] : "20";

        try {
            Flowshop model = new Flowshop();
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}