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\pythonpython assembly_line_balancing.py instances\instance_n20_1.alb
- Execution (Linux)
-
export PYTHONPATH=/opt/hexaly_13_0/bin/pythonpython 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.libassembly_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.dllAssemblyLineBalancing 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.jarjava -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.jarjava -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.