Flow Shop¶
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¶
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 exampleData¶
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 j-th 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\pythonpython flowshop.py instances\tai20_5.txt
- Execution (Linux)
- export PYTHONPATH=/opt/localsolver_11_5/bin/pythonpython 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(next(file_it))
nb_machines = int(next(file_it))
initial_seed = int(next(file_it))
upper_bound = int(next(file_it))
lower_bound = int(next(file_it))
processing_time = [[int(next(file_it)) 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] * nb_machines
first_end_selector = model.lambda_function(lambda i, prev: prev + 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.lambda_function(lambda i, prev: \
model.max(prev, end[mL - 1][i]) + \
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.param.time_limit = int(sys.argv[3])
else:
ls.param.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\localsolver115.libflowshop instances\tai20_5.txt
- Compilation / Execution (Linux)
- g++ flowshop.cpp -I/opt/localsolver_11_5/include -llocalsolver115 -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.createLambdaFunction([&](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.createLambdaFunction([&](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.
localsolver.getParam().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 << "An error occurred: " << e.what() << endl;
return 1;
}
}
- Compilation / Execution (Windows)
- copy %LS_HOME%\bin\localsolvernet.dll .csc Flowshop.cs /reference:localsolvernet.dllFlowshop 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.LambdaFunction((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.LambdaFunction((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.
localsolver.GetParam().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.jarjava -cp %LS_HOME%\bin\localsolver.jar;. Flowshop instances\tai20_5.txt
- Compilation / Execution (Linux)
- javac Flowshop.java -cp /opt/localsolver_11_5/bin/localsolver.jarjava -cp /opt/localsolver_11_5/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 final LocalSolver localsolver;
// Decision variable
private LSExpression jobs;
// Objective
private LSExpression makespan;
private Flowshop(LocalSolver localsolver) {
this.localsolver = localsolver;
}
// 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) {
// 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.lambdaFunction((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.lambdaFunction((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.
localsolver.getParam().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 (LocalSolver localsolver = new LocalSolver()) {
Flowshop model = new Flowshop(localsolver);
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);
}
}
}