# 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=]
```/********** assembly_line_balancing.lsp **********/

use io;

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

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

// 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 following format:
* - value of the objective (number of stations)
* - 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_11_0/bin/python
python assembly_line_balancing.py instances/instance_n20_1.alb
```########## assembly_line_balancing.py ##########

import localsolver
import sys

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

for i in range(3):
to_throw = next(file_it)

for i in range(2):
to_throw = next(file_it)

# Read the cycle time limit
cycleTime = int(next(file_it))
for i in range(5):
to_throw = next(file_it)

processingTimeDict = {}
for i in range(2):
to_throw = next(file_it)
processingTime = [elem for elem in sorted(processingTimeDict.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 nbTasks, maxNbStations, cycleTime, processingTime, successors

#
# Modeling and solve
#
def main(instance_file, output_file, time_limit):

with localsolver.LocalSolver() as ls:

# Declare the optimization model
model = ls.model

# Decision variables: station[s] is the set of tasks assigned to station s
station = [model.set(nbTasks) for s in range(maxNbStations)]
station_array = model.array(station)
model.constraint(model.partition(station_array))

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

# All stations must respect the cycleTime constraint
processingTime_array = model.array(processingTime)
time_selector = model.lambda_function(lambda i: processingTime_array[i])
timeInStation = [model.sum(station[s], time_selector) for s in range(maxNbStations)]
for s in range(maxNbStations):
model.constraint(timeInStation[s] <= cycleTime)

# The stations must respect the succession's order of the tasks
if i in successors.keys():
for j in successors[i]:

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

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" % nbUsedStations.value)
f.write("{},{}\n".format(i + 1, taskStation[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\localsolver110.lib
assembly_line_balancing instances\instance_n20_1.alb
Compilation / Execution (Linux)
g++ assembly_line_balancing.cpp -I/opt/localsolver_11_0/include -llocalsolver110 -lpthread -o assembly_line_balancing
./assembly_line_balancing instances/instance_n20_1.alb
```/********** assembly_line_balancing.cpp **********/

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

using namespace localsolver;
using namespace std;

class ALBInstance {
public:
int nbMaxStations;
int cycleTime;
string to_throw;
vector<int> processingTime;
vector<vector<int>> successors;

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

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

for (int i = 0; i < 2; ++i)
infile >> to_throw;

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

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

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

ALBInstance(const string& fileName) {
}
};

class AssemblyLineBalancing {
private:
// LocalSolver
LocalSolver localsolver;

// Instance data
const ALBInstance* instance;

// Decision variables
vector<LSExpression> station;

// Intermediate expressions
vector<LSExpression> timeInStation;

// Objective
LSExpression nbUsedStations;

public:
// Constructor
AssemblyLineBalancing(const ALBInstance* albi) : instance(albi) {
}

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

// station[s] is the set of tasks assigned to station s
station.resize(instance->nbMaxStations);
LSExpression stationArray = model.array();
for(int s = 0; s < instance->nbMaxStations; ++s) {
}
model.constraint(model.partition(stationArray));

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

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

// The stations must respect the succession's order of the tasks
for (int i = 0; i < instance->nbTasks; ++i) {
}
for (int i = 0; i < instance->nbTasks; ++i)
for (int j : instance->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(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());
outfile << nbUsedStations.getIntValue() << endl;
for (int i = 0; i < instance->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";
ALBInstance instance(instanceFile);
AssemblyLineBalancing model(&instance);
try {
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
```/********** AssemblyLineBalancing.cs **********/

using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

public class ALBInstance
{
public int nbMaxStations;
public int cycleTime;
public int[] processingTime;
public List<int>[] successors;

// Constructor
public ALBInstance(string fileName)
{
}

{
{
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)
{
processingTime[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 (successors[predecessor] == null)
successors[predecessor] = new List<int>();
}
}
}
}

public class AssemblyLineBalancing : IDisposable
{
// LocalSolver
LocalSolver localsolver;

// Instance data
ALBInstance instance;

// Decision variables
LSExpression[] station;

// Intermediate expressions
LSExpression[] timeInStation;

// Objective
LSExpression nbUsedStations;

// Constructor
public AssemblyLineBalancing(ALBInstance instance)
{
this.localsolver = new LocalSolver();
this.instance = instance;
}

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

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

// station[s] is the set of tasks assigned to station s
station = new LSExpression[instance.nbMaxStations];
LSExpression stationArray = model.Array();
for (int s = 0; s < instance.nbMaxStations; ++s)
{
}
model.Constraint(model.Partition(stationArray));

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

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

// The stations must respect the succession's order of the tasks
for (int i = 0; i < instance.nbTasks; ++i)
{
}
for (int i = 0; i < instance.nbTasks; ++i)
if(instance.successors[i] != null)
foreach (int j in instance.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)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(nbUsedStations.GetIntValue());
for (int i = 0; i < instance.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";
ALBInstance instance = new ALBInstance(instanceFile);
using (AssemblyLineBalancing model = new AssemblyLineBalancing(instance))
{
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_0/bin/localsolver.jar
java -cp /opt/localsolver_11_0/bin/localsolver.jar:. AssemblyLineBalancing instances/instance_n20_1.alb
```/********** AssemblyLineBalancing.java **********/

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

public class AssemblyLineBalancing {

private static class ALBInstance {
int nbMaxStations;
int cycleTime;
int[] processingTime;
ArrayList<ArrayList<Integer>> successors;

// Constructor
private ALBInstance(String fileName) throws IOException {
}

private void readInput(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++)
processingTime[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 static class ALBProblem {

// LocalSolver
private final LocalSolver localsolver;

// Instance data
private final ALBInstance instance;

// Decision variables
private LSExpression[] station;

// Intermediate expressions
private LSExpression[] timeInStation;

// Objective
private LSExpression nbUsedStations;

// Constructor
private ALBProblem(LocalSolver localsolver, ALBInstance instance) {
this.localsolver = localsolver;
this.instance = instance;
}

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

// station[s] is the set of tasks assigned to station s
station = new LSExpression[instance.nbMaxStations];
LSExpression stationArray = model.array();
for (int s = 0; s < instance.nbMaxStations; s++) {
}
model.constraint(model.partition(stationArray));

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

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

// The stations must respect the succession's order of the tasks
for (int i = 0; i < instance.nbTasks; i++) {
}
for (int i = 0; i < instance.nbTasks; i++) {
ArrayList<Integer> successors_i = instance.successors.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 < instance.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()) {
ALBInstance instance = new ALBInstance(instanceFile);
ALBProblem model = new ALBProblem(localsolver, instance);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null)
model.writeSolution(outputFile);
}
catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}
```