Simple Assembly Line Balancing Problem (SALBP)

Problem

In the Simple Assembly Line Balancing Problem, we consider a set of tasks that must be gathered in workstations. Each task requires a certain processing time. The sum of the tasks’ processing times in each workstation cannot exceed a certain limit, called cycle time. There are also precedence constraints between the tasks. Each task must either be in the same workstation or in a later workstation than all its predecessors. Finally, the objective function is to minimize the number of workstations.

Principles learned

  • Add set decision variables to model the contents of the workstations
  • Define a lambda function to compute the total time spent in each workstation
  • Retrieve the index of each task’s workstation thanks to the ‘find‘ operator

Data

The instances provided come from Otto et al. and are formatted as follows:

  • The number of tasks
  • The cycle time limit
  • For each task, its index and processing time
  • For each precedence constraint, the predecessor’s index and the successor’s index

Program

The Hexaly model for the Simple Assembly Line Balancing Problem (SALBP) uses set decision variables. Each set represents the tasks assigned to a workstation. Thanks to the ‘partition‘ operator, we ensure that each task is assigned to exactly one workstation.

The total time spent in each workstation is computed with a lambda function to apply the ‘sum’ operator over all assigned tasks. Note that the number of terms in this sum varies during the search, along with the size of the set. We can then constrain this quantity to be lower than the cycle time.

Using the ‘find‘ operator, we can then retrieve the index of the workstation that was chosen to process each task. This allows us to write the precedence constraints between the tasks: each task should be in an earlier workstation than all its successors.

We compute the number of used workstations, which is equal to the number of non-empty set variables, and we minimize it.

Execution
hexaly assembly_line_balancing.hxm inFileName=instances/instance_n20_1.alb [hxTimeLimit=] [solFileName=]
use io;

/* Read instance data */
function input() {
    local usage = "Usage: hexaly assembly_line_balancing.hxm "
            + "inFileName=inputFile [hxTimeLimit=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...5] inFile.readln();

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

    // Read the successors' relations
    successors[i in 0...nbTasks] = {};
    local line = inFile.readln().split(",");
    while(line.count() > 1) {
        local predecessor = line[0].toInt() - 1;
        local successor = line[1].toInt() - 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] <- set(nbTasks);
    constraint partition[s in 0...maxNbStations](station[s]);

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

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

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

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

/* Parametrize the solver */
function param() {
    if (hxTimeLimit == nil) hxTimeLimit = 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]
        solFile.println(i + 1, ",", taskStation[i].value + 1);
}
Execution (Windows)
set PYTHONPATH=%HX_HOME%\bin\python
python assembly_line_balancing.py instances\instance_n20_1.alb
 
Execution (Linux)
export PYTHONPATH=/opt/hexaly_13_0/bin/python
python assembly_line_balancing.py instances/instance_n20_1.alb
import hexaly.optimizer
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 hexaly.optimizer.HexalyOptimizer() as optimizer:
        #
        # Declare the optimization model
        #
        model = optimizer.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 optimizer
        optimizer.param.time_limit = time_limit

        optimizer.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%HX_HOME%\include /link %HX_HOME%\bin\hexaly130.lib
assembly_line_balancing instances\instance_n20_1.alb
 
Compilation / Execution (Linux)
g++ assembly_line_balancing.cpp -I/opt/hexaly_13_0/include -lhexaly130 -lpthread -o assembly_line_balancing
./assembly_line_balancing instances/instance_n20_1.alb
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace hexaly;
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;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    vector<HxExpression> stationVars;

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

    // Objective
    HxExpression 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
        HxModel model = optimizer.getModel();

        // Decision variables: stationVars[s] is the set of tasks assigned to station s
        stationVars.resize(nbMaxStations);
        HxExpression 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);
        HxExpression processingTime = model.array(processingTimeData.begin(), processingTimeData.end());
        HxExpression timeLambda = model.lambdaFunction([&](HxExpression 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 optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.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 %HX_HOME%\bin\Hexaly.NET.dll .
csc AssemblyLineBalancing.cs /reference:Hexaly.NET.dll
AssemblyLineBalancing instances\instance_n20_1.alb
using System;
using System.IO;
using System.Collections.Generic;
using Hexaly.Optimizer;

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

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression[] stationVars;

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

    // Objective
    HxExpression nbUsedStations;

    public AssemblyLineBalancing()
    {
        optimizer = new HexalyOptimizer();
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.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
        HxModel model = optimizer.GetModel();

        // Decision variables: stationVars[s] is the set of tasks assigned to station s
        stationVars = new HxExpression[nbMaxStations];
        HxExpression 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 HxExpression[nbMaxStations];
        HxExpression processingTime = model.Array(processingTimeData);
        HxExpression 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 HxExpression[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 optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.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 %HX_HOME%\bin\hexaly.jar
java -cp %HX_HOME%\bin\hexaly.jar;. AssemblyLineBalancing instances\instance_n20_1.alb
Compilation / Execution (Linux)
javac AssemblyLineBalancing.java -cp /opt/hexaly_13_0/bin/hexaly.jar
java -cp /opt/hexaly_13_0/bin/hexaly.jar:. AssemblyLineBalancing instances/instance_n20_1.alb
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class AssemblyLineBalancing {

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

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression[] stationVars;

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

    // Objective
    private HxExpression nbUsedStations;

    private AssemblyLineBalancing(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* 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
        HxModel model = optimizer.getModel();

        // Decision variables: stationVars[s] is the set of tasks assigned to station s
        stationVars = new HxExpression[nbMaxStations];
        HxExpression 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 HxExpression[nbMaxStations];
        HxExpression processingTime = model.array(processingTimeData);
        HxExpression 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 HxExpression[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 optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.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 (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            AssemblyLineBalancing model = new AssemblyLineBalancing(optimizer);
            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);
        }
    }
}

Results

Hexaly Optimizer reaches an average gap of 0.3% on the Simple Assembly Line Balancing Problem (SALBP) in 1 minute of running time on a large benchmark from the literature composed of 1,000 task instances. Our Flexible Job Shop (FJSP) benchmark page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers like Gurobi and CP Optimizer on this challenging problem.