The industrial problem: TSALBP

An assembly line is a flow-oriented production system made up of a number of workstations, arranged in series and in parallel. Assembly lines are of great importance in the industrial production of high quantity standardized commodities and more recently even gained importance in low volume production of customized products. The assembly line configuration involves determining an optimal assignment of a subset of tasks to each station of the plant to minimize the inefficiency of the line or its total downtime while respecting all the constraints imposed on the tasks and on the stations. Such problem is called assembly line balancing (ALB) and it is a very complex combinatorial optimization problem (known to be NP-hard) which has become an active field of research over more than half a century.
A more realistic extension of assembly line balancing is one proposed by Bautista (www.nissanchair.com/TSALBP), which considers an additional space constraint to get a simplified but closer version to real-world problems, defining the Time and Space ALB problem (TSALBP). TSALBP presents eight variants depending on three optimization criteria: the line cycle time, the number of stations, and their area. Four of those variants present a multi-objective nature.

Metaheuristics and Multiobjective Optimization

Ant Colony Optimization (ACO) is a population-based metaheuristic that can be used to find approximate solutions to difficult optimization problems. In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. To apply ACO, the optimization problem is transformed into the problem of finding the best path on a weighted graph. The artificial ants incrementally build solutions by moving on the graph. The solution construction process is stochastic and is biased by a pheromone model, that is, a set of parameters associated with graph components (either nodes or edges) whose values are modified at runtime by the ants.
Genetic algorithms (GAs) were formally introduced in the 1970s by John Holland at University of Michigan. The continuing price/performance improvements of computational systems has made them attractive for some types of optimization. In particular, genetic algorithms work very well on mixed (continuous and discrete) combinatorial problems. They are less susceptible to getting ‘stuck’ at local optima than gradient search methods. To use a genetic algorithm you must represent a solution to your problem as a genome (or chromosome). The genetic algorithm then creates a population of solutions and applies genetic operators such as mutation and crossover to evolve the solutions in order to find the best one(s).

Source code and instances

In this section you can download the available software packages of the project. More information about the project of my PhD can be found at the Nissan Chair website, active member of the project.

TSALBP v 2.0   [DOWNLOAD]

This project contains the latest published algorithms and preference schemes for the TSALBP. See Publications section for the references of the algorithms and multiobjective mechanisms. In addition, this version of the software makes use of a Qt graphical user interface and a XML parameters file format. Examples of the XML parameter files are located in the distribution package to perform quick runs of the algorithms.

The source code is programmed using C++ language but as TSALBP v2.0 can be launched by a GUI, Qt libraries and gnuplot (>= 4.4)  are also needed to compile the project. After solving dependences, you can then compile the software using qmake and the installation templates included in the distribution (tsalbp_v2_0.pro) . More information about the changes and installation steps are detailed in the README.txt file of the package.

The compilation will also need an extra package called Paradiseo 1.1 (download from here). Check the installation steps of Paradiseo in its Web site. Once you have downloaded it, you need to install it on your system and link it in the makefile template files as shown in the README.txt file.

When TSALBP is installed, run the application in the console mode or using the Qt GUI:

    $ ./tsalbp_v2_0  <datasetFile> <outputFile> <parameterXMLFile> <seed>    (for console based running)

$ ./tsalbp_v2_0  –gui    (for GUI running)

Do not hesitate to contact author for help: mchserrano[arroba]gmail.com

NTIGEN  (Nissan TSALBP Instance GENerator)  [DOWNLOAD]

The main goal of the NTIGen software is to generate real-like TSALBP instances with different features to serve as a benchmark for showing the performance of our presented approaches and future research works. The user of NTIGen is allowed to incorporate the Nissan industrial real-like features to the generated instances being these instances similar to the original Nissan instance context.

Just download the code (it is programmed in C++) and compile the source files (no external dependences). Then run the software with the following arguments:

    $ ./tsalbp_generator <datasetFile>  <outputFile> <configurationFile>

Examples of XML configuration files to generate instances are again included in the package.

Set of original TSALBP instances   [DOWNLOAD]

11 instances having the following tagged format in plain text files:

@name
XXXX

@noTasks
XXXX

@cycleTime
XXXX

@boundsArea
XXXX,XXXX

@boundsStations
XXXX,XXXX

@data
XXXX   XXXX
…..

@precs
XXXX -> XXXX

…..

last line: end mark “-1 -> –1″

Set of NTIGEN generated TSALBP instances with scenario information  [DOWNLOAD]

8 instances generated by the NTIGEN software containing information about different Nissan scenarios. The format of the files is the same as in the original instances but adding the tag @noScenarios and the tasks’ time in the different scenarios within the @data section:

@noScenarios
XXXX

@data
XXXX  
XXXX  XXXX  …. XXXX  XXXX
…..