# Assembly Line Balancing (SALBP)¶

## Principles learned¶

• Set succession constraints

• Use intermediate variables

• Use set variables with operator “find”

## Problem¶

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.

## Data¶

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

• Cycle time limit

• 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;

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

if(inFileName == nil) throw usage;

// Read the cycle time limit

while(line.count() > 1) {
local predecessor = toInt(line) - 1;
local successor = toInt(line) - 1;
}
inFile.close();
}

/* Declare the optimization model */
function model() {
// Decision variables: station[s] is the set of tasks assigned to station s
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
for [i in 0...nbTasks][j in successors[i]]

// 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(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_12_0/bin/python
python assembly_line_balancing.py instances/instance_n20_1.alb
```import localsolver
import sys

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

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

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)

processing_time_dict = {}
for _ in range(2):
next(file_it)
processing_time = [elem for elem in sorted(processing_time_dict.items(),
key=lambda x: x)]

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):

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
if i in successors_data.keys():
for j in successors_data[i]:

# 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("{},{}\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
output_file = sys.argv if len(sys.argv) >= 3 else None
time_limit = int(sys.argv) 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\localsolver120.lib
assembly_line_balancing instances\instance_n20_1.alb
Compilation / Execution (Linux)
g++ assembly_line_balancing.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -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 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;

// Objective
LSExpression nbUsedStations;

public:
ifstream infile;
infile.open(fileName.c_str());

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

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;

for (int i = 0; i < nbTasks; ++i) {
}
for (int i = 0; i < 2; ++i)
infile >> tmp;

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) {
}
model.constraint(model.partition(stations));

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

// 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
for (int i = 0; i < nbTasks; ++i) {
}
for (int i = 0; i < nbTasks; ++i)
for (int j : successorsData[i])

// 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.open(fileName.c_str());
outfile << nbUsedStations.getIntValue() << 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;
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "20";
try {
AssemblyLineBalancing model;
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 nbMaxStations;
public int cycleTime;
public int[] processingTimeData;
public List<int>[] successorsData;

// LocalSolver
LocalSolver localsolver;

// Decision variables
LSExpression[] stationVars;

// Intermediate expressions
LSExpression[] timeInStation;

// Objective
LSExpression nbUsedStations;

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

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

{
{
string[] line;

for (int i = 0; i < 2; ++i)

// Read the cycle time limit
for (int i = 0; i < 6; ++i)

for (int i = 0; i < nbTasks; ++i)
{
processingTimeData[i] = int.Parse(line);
}
for (int i = 0; i < 2; ++i)

while (true)
{
if (line == "")
break;
int predecessor = int.Parse(line) - 1;
int successor = int.Parse(line) - 1;
if (successorsData[predecessor] == null)
successorsData[predecessor] = new List<int>();
}
}
}

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)
{
}
model.Constraint(model.Partition(stations));

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

// 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
for (int i = 0; i < nbTasks; ++i)
for (int i = 0; i < nbTasks; ++i)
if (successorsData[i] != null)
foreach (int j in successorsData[i])

// 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());
for (int i = 0; i < nbTasks; ++i)
{
output.Write(i + 1);
output.Write(',');
}
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: AssemblyLineBalancing inputFile [solFile] [timeLimit]");
Environment.Exit(1);
}
string instanceFile = args;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "20";
using (AssemblyLineBalancing model = new AssemblyLineBalancing())
{
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_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/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 nbMaxStations;
int cycleTime;
int[] processingTimeData;
ArrayList<ArrayList<Integer>> successorsData;

// LocalSolver
private final LocalSolver localsolver;

// Decision variables
private LSExpression[] stationVars;

// Intermediate expressions
private LSExpression[] timeInStation;

// Objective
private LSExpression nbUsedStations;

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

private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
input.nextLine();

for (int i = 0; i < nbTasks; ++i)
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();

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

String line = input.nextLine();
while (!line.isEmpty()) {
String lineSplit[] = line.split(",");
int predecessor = Integer.parseInt(lineSplit) - 1;
int successor = Integer.parseInt(lineSplit) - 1;
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) {
}
model.constraint(model.partition(stations));

// Objective: nbUsedStations is the total number of used stations
nbUsedStations = model.sum();
for (int s = 0; s < nbMaxStations; ++s) {
}

// 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
for (int i = 0; i < nbTasks; ++i) {
}
for (int i = 0; i < nbTasks; ++i) {
ArrayList<Integer> successors_i = successorsData.get(i);
for (int j : successors_i) {
}
}

// 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());
for (int i = 0; i < nbTasks; ++i) {
output.print(i + 1);
output.print(",");
}
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: AssemblyLineBalancing inputFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "20";
try (LocalSolver localsolver = new LocalSolver()) {
AssemblyLineBalancing model = new AssemblyLineBalancing(localsolver);