This page is for an old version of Hexaly Optimizer. We recommend that you update your version and read the documentation for the latest stable release.

Assembly Line Balancing (SALBP)

Principles learned

  • Set succession constraints

  • Use intermediate variables

  • Use set variables with operator “find”

Problem

../_images/assembly_line_balancing.svg

We consider a simple assembly line balancing problem (SALBP) as defined by Prof. Dr. Armin Scholl, Friedrich Schiller University Jena. We have a set of tasks that must be gathered in groups called stations. Each task requires a certain processing time. Moreover, some tasks cannot be performed if some other tasks have not been completed before. Finally, the sum of the tasks’ processing times in each station cannot exceed a given limit. Therefore, the goal is to minimize the number of stations such that the cycle time limit constraints and the tasks’ order are satisfied. On the left diagram, the tasks are the letter circles, the order constraints are represented by arrows and the grey areas are the stations.

Download the example


Data

The instances provided come from Alena Otto. They are formatted into the following format:

  • Number of tasks

  • Cycle time limit

  • Tasks’ processing times

  • Precedence relations

Program

This LocalSolver model defines a sequence of set variables called “station”. Each set represents a station which can either contain some tasks or be empty. To ensure that each task belongs to an unique station, set variables must form a partition.

We state an upper bound for the number of stations equals to the number of tasks according to the naive solution where each task is contained in a different station.

The number of used stations is computed as the number of non-empty sets and should be minimized. The cycle time constraint is written with a variadic sum of processing times over the tasks of each set. The succession constraints verify that for each task, its station’s number is inferior or equal to its successors’ ones thanks to the “find” operator.

Execution:
localsolver assembly_line_balancing.lsp inFileName=instances/instance_n20_1.alb [lsTimeLimit=] [solFileName=]
use io;

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

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

    inFile.readln();
    
    // Read number of tasks
    nbTasks = inFile.readInt();
    maxNbStations = nbTasks;
    inFile.readln();

    // Read the cycle time limit
    cycleTime = inFile.readInt();
    for [i in 0..4] inFile.readln();

    // Read the processing times
    for [t in 0..nbTasks-1]
        processingTime[inFile.readInt() - 1] = inFile.readInt();
    inFile.readln();

    // Read the successors' relations
    successors[0..nbTasks-1] = {};
    local line = inFile.readln().split(",");
    while(line.count() > 1) {
        local predecessor = toInt(line[0]) - 1;
        local successor = toInt(line[1]) - 1;
        successors[predecessor].add(successor);
        line = inFile.readln().split(",");
    }
    inFile.close();
}

/* Declare the optimization model */
function model() {
    // Decision variables: station[s] is the set of tasks assigned to station s
    station[s in 0..maxNbStations-1] <- set(nbTasks);
    constraint partition[s in 0..maxNbStations-1](station[s]);

    // Objective: nbUsedStations is the total number of used stations
    nbUsedStations <- sum[s in 0..maxNbStations-1](count(station[s]) > 0);

    // All stations must respect the cycleTime constraint
    timeInStation[s in 0..maxNbStations-1] <- sum(station[s], i => processingTime[i]);
    for [s in 0..maxNbStations-1]
        constraint timeInStation[s] <= cycleTime;

    // The stations must respect the succession's order of the tasks
    taskStation[i in 0..nbTasks-1] <- find(station, i);
    for [i in 0..nbTasks-1][j in successors[i]]
        constraint taskStation[i] <= taskStation[j];

    // Minimization of the number of active stations
    minimize nbUsedStations;
}

/* Parametrize the solver */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 20;
}

/* Write the solution in a file following the format:
* - 1st line: value of the objective
* - 2nd line: number of tasks
* - following lines: task's number, station's number */
function output() {
    if(solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    solFile.println(nbUsedStations.value);
    solFile.println(nbTasks);
    for [i in 0..nbTasks-1]
        solFile.println(i + 1, ",", taskStation[i].value + 1);
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python assembly_line_balancing.py instances\instance_n20_1.alb
Execution (Linux)
export PYTHONPATH=/opt/localsolver_11_5/bin/python
python assembly_line_balancing.py instances/instance_n20_1.alb
import localsolver
import sys


#
# Functions to read the instances
#
def read_elem(filename):
    with open(filename) as f:
        return [str(elem) for elem in f.read().split()]


def read_instance(instance_file):
    file_it = iter(read_elem(instance_file))

    for _ in range(3):
        next(file_it)

    # Read number of tasks
    nb_tasks = int(next(file_it))
    max_nb_stations = nb_tasks
    for _ in range(2):
        next(file_it)

    # Read the cycle time limit
    cycle_time = int(next(file_it))
    for _ in range(5):
        next(file_it)

    # Read the processing times
    processing_time_dict = {}
    for _ in range(nb_tasks):
        task = int(next(file_it)) - 1
        processing_time_dict[task] = int(next(file_it))
    for _ in range(2):
        next(file_it)
    processing_time = [elem[1] for elem in sorted(processing_time_dict.items(),
                                                  key=lambda x: x[0])]

    # Read the successors' relations
    successors = {}
    while True:
        try:
            pred, succ = next(file_it).split(',')
            pred = int(pred) - 1
            succ = int(succ) - 1
            if pred in successors:
                successors[pred].append(succ)
            else:
                successors[pred] = [succ]
        except:
            break
    return nb_tasks, max_nb_stations, cycle_time, processing_time, successors


def main(instance_file, output_file, time_limit):
    nb_tasks, max_nb_stations, cycle_time, processing_time_data, \
        successors_data = read_instance(instance_file)

    with localsolver.LocalSolver() as ls:
        #
        # Declare the optimization model
        #
        model = ls.model

        # Decision variables: station_vars[s] is the set of tasks assigned to station s
        station_vars = [model.set(nb_tasks) for s in range(max_nb_stations)]
        stations = model.array(station_vars)
        model.constraint(model.partition(stations))

        # Objective: nb_used_stations is the total number of used stations
        nb_used_stations = model.sum(
            (model.count(station_vars[s]) > 0) for s in range(max_nb_stations))

        # All stations must respect the cycleTime constraint
        processing_time = model.array(processing_time_data)
        time_lambda = model.lambda_function(lambda i: processing_time[i])
        time_in_station = [model.sum(station_vars[s], time_lambda)
                           for s in range(max_nb_stations)]
        for s in range(max_nb_stations):
            model.constraint(time_in_station[s] <= cycle_time)

        # The stations must respect the succession's order of the tasks
        task_station = [model.find(stations, i) for i in range(nb_tasks)]
        for i in range(nb_tasks):
            if i in successors_data.keys():
                for j in successors_data[i]:
                    model.constraint(task_station[i] <= task_station[j])

        # Minimization of the number of active stations
        model.minimize(nb_used_stations)

        model.close()

        # Parameterize the solver
        ls.param.time_limit = time_limit

        ls.solve()

        # Write the solution in a file following the format:
        # - 1st line: value of the objective
        # - 2nd line: number of tasks
        # - following lines: task's number, station's number
        if output_file is not None:
            with open(output_file, 'w') as f:
                f.write("%d\n" % nb_used_stations.value)
                f.write("%d\n" % nb_tasks)
                for i in range(nb_tasks):
                    f.write("{},{}\n".format(i + 1, task_station[i].value + 1))


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python assembly_line_balancing.py instance_file \
            [output_file] [time_limit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 20
    main(instance_file, output_file, time_limit)
Compilation / Execution (Windows)
cl /EHsc assembly_line_balancing.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver115.lib
assembly_line_balancing instances\instance_n20_1.alb
Compilation / Execution (Linux)
g++ assembly_line_balancing.cpp -I/opt/localsolver_11_5/include -llocalsolver115 -lpthread -o assembly_line_balancing
./assembly_line_balancing instances/instance_n20_1.alb
#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

class AssemblyLineBalancing {
private:
    // Data from the problem
    int nbTasks;
    int nbMaxStations;
    int cycleTime;
    string tmp;
    vector<int> processingTimeData;
    vector<vector<int>> successorsData;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variables
    vector<LSExpression> stationVars;

    // Intermediate expressions
    vector<LSExpression> timeInStation;
    vector<LSExpression> taskStation;

    // Objective
    LSExpression nbUsedStations;

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

        for (int i = 0; i < 3; ++i)
            infile >> tmp;

        // Read number of tasks
        infile >> nbTasks;
        nbMaxStations = nbTasks;
        processingTimeData.resize(nbTasks);
        successorsData.resize(nbTasks);
        for (int i = 0; i < 2; ++i)
            infile >> tmp;

        // Read the cycle time limit
        infile >> cycleTime;
        for (int i = 0; i < 5; ++i)
            infile >> tmp;

        // Read the processing times
        for (int i = 0; i < nbTasks; ++i) {
            int task;
            infile >> task;
            infile >> processingTimeData[task - 1];
        }
        for (int i = 0; i < 2; ++i)
            infile >> tmp;

        // Read the successors' relations
        string delimiter = ",";
        while (infile.eof() != true) {
            string relation;
            infile >> relation;
            string predecessor = relation.substr(0, relation.find(delimiter));
            string successor = relation.substr(relation.find(delimiter) + 1, relation.size());
            if (predecessor == relation)
                break;
            successorsData[stoi(predecessor) - 1].push_back(stoi(successor) - 1);
        }
        infile.close();
    }

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

        // Decision variables: stationVars[s] is the set of tasks assigned to station s
        stationVars.resize(nbMaxStations);
        LSExpression stations = model.array();
        for (int s = 0; s < nbMaxStations; ++s) {
            stationVars[s] = model.setVar(nbTasks);
            stations.addOperand(stationVars[s]);
        }
        model.constraint(model.partition(stations));

        // Objective: nbUsedStations is the total number of used stations
        nbUsedStations = model.sum();
        for (int s = 0; s < nbMaxStations; ++s)
            nbUsedStations.addOperand((model.count(stationVars[s]) > 0));

        // All stations must respect the cycleTime constraint
        timeInStation.resize(nbMaxStations);
        LSExpression processingTime =
            model.array(processingTimeData.begin(), processingTimeData.end());
        LSExpression timeLambda = model.lambdaFunction([&](LSExpression i) { return processingTime[i]; });
        for (int s = 0; s < nbMaxStations; ++s) {
            timeInStation[s] = model.sum(stationVars[s], timeLambda);
            model.constraint(timeInStation[s] <= cycleTime);
        }

        // The stations must respect the succession's order of the tasks
        taskStation.resize(nbTasks);
        for (int i = 0; i < nbTasks; ++i) {
            taskStation[i] = model.find(stations, i);
        }
        for (int i = 0; i < nbTasks; ++i)
            for (int j : successorsData[i])
                model.constraint(taskStation[i] <= taskStation[j]);

        // Minimization of the number of active stations
        model.minimize(nbUsedStations);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /* Write the solution in a file following the format:
     * - 1st line: value of the objective
     * - 2nd line: number of tasks
     * - following lines: task's number, station's number */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());
        outfile << nbUsedStations.getIntValue() << endl;
        outfile << nbTasks << endl;
        for (int i = 0; i < nbTasks; ++i)
            outfile << i + 1 << "," << taskStation[i].getIntValue() + 1 << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: assembly_line_balancing 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] : "20";
    try {
        AssemblyLineBalancing 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 AssemblyLineBalancing.cs /reference:localsolvernet.dll
AssemblyLineBalancing instances\instance_n20_1.alb
using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

public class AssemblyLineBalancing : IDisposable
{
    // Data from the problem
    public int nbTasks;
    public int nbMaxStations;
    public int cycleTime;
    public int[] processingTimeData;
    public List<int>[] successorsData;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variables
    LSExpression[] stationVars;

    // Intermediate expressions
    LSExpression[] timeInStation;
    LSExpression[] taskStation;

    // Objective
    LSExpression nbUsedStations;

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

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

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] line;
            input.ReadLine();

            // Read number of tasks
            nbTasks = int.Parse(input.ReadLine());
            nbMaxStations = nbTasks;
            processingTimeData = new int[nbTasks];
            successorsData = new List<int>[nbTasks];
            for (int i = 0; i < 2; ++i)
                input.ReadLine();

            // Read the cycle time limit
            cycleTime = int.Parse(input.ReadLine());
            for (int i = 0; i < 6; ++i)
                input.ReadLine();

            // Read the processing times
            for (int i = 0; i < nbTasks; ++i)
            {
                line = input.ReadLine().Split();
                processingTimeData[i] = int.Parse(line[1]);
            }
            for (int i = 0; i < 2; ++i)
                input.ReadLine();

            // Read the successors' relations
            while (true)
            {
                line = input.ReadLine().Split(',');
                if (line[0] == "")
                    break;
                int predecessor = int.Parse(line[0]) - 1;
                int successor = int.Parse(line[1]) - 1;
                if (successorsData[predecessor] == null)
                    successorsData[predecessor] = new List<int>();
                successorsData[predecessor].Add(successor);
            }
        }
    }

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

        // Decision variables: stationVars[s] is the set of tasks assigned to station s
        stationVars = new LSExpression[nbMaxStations];
        LSExpression stations = model.Array();
        for (int s = 0; s < nbMaxStations; ++s)
        {
            stationVars[s] = model.Set(nbTasks);
            stations.AddOperand(stationVars[s]);
        }
        model.Constraint(model.Partition(stations));

        // Objective: nbUsedStations is the total number of used stations
        nbUsedStations = model.Sum();
        for (int s = 0; s < nbMaxStations; ++s)
            nbUsedStations.AddOperand(model.Count(stationVars[s]) > 0);

        // All stations must respect the cycleTime constraint
        timeInStation = new LSExpression[nbMaxStations];
        LSExpression processingTime = model.Array(processingTimeData);
        LSExpression timeLambda = model.LambdaFunction(i => processingTime[i]);
        for (int s = 0; s < nbMaxStations; ++s)
        {
            timeInStation[s] = model.Sum(stationVars[s], timeLambda);
            model.Constraint(timeInStation[s] <= cycleTime);
        }

        // The stations must respect the succession's order of the tasks
        taskStation = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
            taskStation[i] = model.Find(stations, i);
        for (int i = 0; i < nbTasks; ++i)
            if (successorsData[i] != null)
                foreach (int j in successorsData[i])
                    model.Constraint(taskStation[i] <= taskStation[j]);

        // Minimization of the number of active stations
        model.Minimize(nbUsedStations);

        model.Close();

        // Parametrize the solver
        localsolver.GetParam().SetTimeLimit(limit);

        localsolver.Solve();
    }

    /* Write the solution in a file following the format:
    * - 1st line: value of the objective
    * - 2nd line: number of tasks
    * - following lines: task's number, station's number */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(nbUsedStations.GetIntValue());
            output.WriteLine(nbTasks);
            for (int i = 0; i < nbTasks; ++i)
            {
                output.Write(i + 1);
                output.Write(',');
                output.WriteLine(taskStation[i].GetIntValue() + 1);
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: AssemblyLineBalancing 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] : "20";
        using (AssemblyLineBalancing model = new AssemblyLineBalancing())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac AssemblyLineBalancing.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. AssemblyLineBalancing instances\instance_n20_1.alb
Compilation / Execution (Linux)
javac AssemblyLineBalancing.java -cp /opt/localsolver_11_5/bin/localsolver.jar
java -cp /opt/localsolver_11_5/bin/localsolver.jar:. AssemblyLineBalancing instances/instance_n20_1.alb
import java.util.*;
import java.io.*;
import localsolver.*;

public class AssemblyLineBalancing {

    // Data from the problem
    int nbTasks;
    int nbMaxStations;
    int cycleTime;
    int[] processingTimeData;
    ArrayList<ArrayList<Integer>> successorsData;

    // LocalSolver
    private final LocalSolver localsolver;

    // Decision variables
    private LSExpression[] stationVars;

    // Intermediate expressions
    private LSExpression[] timeInStation;
    private LSExpression[] taskStation;

    // Objective
    private LSExpression nbUsedStations;

    private AssemblyLineBalancing(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            input.nextLine();

            // Read number of tasks
            nbTasks = input.nextInt();
            nbMaxStations = nbTasks;
            processingTimeData = new int[nbTasks];
            successorsData = new ArrayList<ArrayList<Integer>>(nbTasks);
            for (int i = 0; i < nbTasks; ++i)
                successorsData.add(i, new ArrayList<Integer>());
            for (int i = 0; i < 3; ++i)
                input.nextLine();

            // Read the cycle time limit
            cycleTime = input.nextInt();
            for (int i = 0; i < 7; ++i)
                input.nextLine();

            // Read the processing times
            for (int i = 0; i < nbTasks; ++i)
                processingTimeData[input.nextInt() - 1] = input.nextInt();
            for (int i = 0; i < 3; ++i)
                input.nextLine();

            // Read the successors' relations
            String line = input.nextLine();
            while (!line.isEmpty()) {
                String lineSplit[] = line.split(",");
                int predecessor = Integer.parseInt(lineSplit[0]) - 1;
                int successor = Integer.parseInt(lineSplit[1]) - 1;
                successorsData.get(predecessor).add(successor);
                line = input.nextLine();
            }
        }
    }

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

        // Decision variables: stationVars[s] is the set of tasks assigned to station s
        stationVars = new LSExpression[nbMaxStations];
        LSExpression stations = model.array();
        for (int s = 0; s < nbMaxStations; ++s) {
            stationVars[s] = model.setVar(nbTasks);
            stations.addOperand(stationVars[s]);
        }
        model.constraint(model.partition(stations));

        // Objective: nbUsedStations is the total number of used stations
        nbUsedStations = model.sum();
        for (int s = 0; s < nbMaxStations; ++s) {
            nbUsedStations.addOperand(model.gt(model.count(stationVars[s]), 0));
        }

        // All stations must respect the cycleTime constraint
        timeInStation = new LSExpression[nbMaxStations];
        LSExpression processingTime = model.array(processingTimeData);
        LSExpression timeLambda = model.lambdaFunction(i -> model.at(processingTime, i));
        for (int s = 0; s < nbMaxStations; ++s) {
            timeInStation[s] = model.sum(stationVars[s], timeLambda);
            model.constraint(model.leq(timeInStation[s], cycleTime));
        }

        // The stations must respect the succession's order of the tasks
        taskStation = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i) {
            taskStation[i] = model.find(stations, i);
        }
        for (int i = 0; i < nbTasks; ++i) {
            ArrayList<Integer> successors_i = successorsData.get(i);
            for (int j : successors_i) {
                model.constraint(model.leq(taskStation[i], taskStation[j]));
            }
        }

        // Minimization of the number of active stations
        model.minimize(nbUsedStations);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /*
     * Write the solution in a file following the format:
     * - 1st line: value of the objective
     * - 2nd line: number of tasks
     * - following lines: task's number, station's number
     */
    void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(new FileWriter(fileName))) {
            output.println(nbUsedStations.getIntValue());
            output.println(nbTasks);
            for (int i = 0; i < nbTasks; ++i) {
                output.print(i + 1);
                output.print(",");
                output.println(taskStation[i].getIntValue() + 1);
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: AssemblyLineBalancing 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()) {
            AssemblyLineBalancing model = new AssemblyLineBalancing(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);
        }
    }
}