Interfacing with LocalSolver: An Assembly Line Sequencing Optimiser

You can see this app running online at: LocalSolver Assembly Line Sequencing Optimiser

What this app does:

  • Solves a sequencing problem commonly found in assembly line production

This app aims to demonstrate:

  • How to interface to LocalSolver using LocalSolver’s lsp language and the command line
  • How to load example data using Python code

LocalSolver worked example

  • The code that solves the optimisation problem within this app is taken from an online LocalSolver example and is used with permission.

Setup Instructions

Before you can run this app, you will need to install LocalSolver, and obtain a trial license. Details can be found on the LocalSolver website

Next, use the app name 'tropofy_localsolver_assembly_line_sequencing' to quickstart as in Running and Debugging Tropofy Apps

Full Source

"""
Authors: www.tropofy.com

Copyright 2015 Tropofy Pty Ltd, all rights reserved.

This source file is part of Tropofy and governed by the Tropofy terms of service
available at: http://www.tropofy.com/terms_of_service.html

The LocalSolver example this app is based on can be found at
http://www.localsolver.com/exampletour.html?file=car_sequencing.zip

Used with permission.

This source file is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the license files for details.


Problem Description:
"A number of cars are to be produced; they are not identical, because different options are available as variants on the basic model.
The assembly line has different stations which install the various options (air-conditioning, sun-roof, etc.).
These stations have been designed to handle at most a certain percentage of the cars passing along the assembly line.
Furthermore, the cars requiring a certain option must not be bunched together, otherwise the station will not be able to cope.
Consequently, the cars must be arranged in a sequence so that the capacity of each station is never exceeded.
For instance, if a particular station can only cope with at most half of the cars passing along the line,
the sequence must be built so that at most 1 car in any 2 requires that option.
The problem has been shown to be NP-hard."
[http://www.localsolver.com/exampletour.html?file=car_sequencing.zip]
"""
import pkg_resources
import subprocess
from sqlalchemy.types import Text, Integer
from sqlalchemy.schema import Column, ForeignKeyConstraint, UniqueConstraint

from tropofy.app import AppWithDataSets, Step, StepGroup
from tropofy.widgets import ExecuteFunction, SimpleGrid
from tropofy.database.tropofy_orm import DataSetMixin


class ALSOModelName(DataSetMixin):
    name = Column(Text, nullable=False)
    num_cars_to_assemble = Column(Integer, nullable=False)

    @classmethod
    def get_table_args(cls):
        return (UniqueConstraint('data_set_id', 'name'),)


class ALSOOptionName(DataSetMixin):
    name = Column(Text, nullable=False)

    @classmethod
    def get_table_args(cls):
        return (UniqueConstraint('data_set_id', 'name'),)


class ALSOOptionsInModel(DataSetMixin):
    model_name = Column(Text, nullable=False)
    option_name = Column(Text, nullable=False)

    @classmethod
    def get_table_args(cls):
        return (
            ForeignKeyConstraint(['model_name', 'data_set_id'], ['alsomodelname.name', 'alsomodelname.data_set_id'], ondelete='CASCADE', onupdate='CASCADE'),
            ForeignKeyConstraint(['option_name', 'data_set_id'], ['alsooptionname.name', 'alsooptionname.data_set_id'], ondelete='CASCADE', onupdate='CASCADE')
        )


class ALSOMaxCarsInBlockForOption(DataSetMixin):
    option_name = Column(Text, nullable=False)
    max_cars_in_block = Column(Integer, nullable=False)
    block_size = Column(Integer, nullable=False)

    @classmethod
    def get_table_args(cls):
        return (ForeignKeyConstraint(['option_name', 'data_set_id'], ['alsooptionname.name', 'alsooptionname.data_set_id'], ondelete='CASCADE', onupdate='CASCADE'),)


class ALSOAssemblyLineModelSequence(DataSetMixin):
    model_name = Column(Text, nullable=False)
    sequence = Column(Integer, nullable=False)

    @classmethod
    def get_table_args(cls):
        return (ForeignKeyConstraint(['model_name', 'data_set_id'], ['alsomodelname.name', 'alsomodelname.data_set_id'], ondelete='CASCADE', onupdate='CASCADE'),)


class ExecuteLocalSolver(ExecuteFunction):

    def get_button_text(self, app_session):
        return "Solve Assembly Line Sequencing Problem"

    def execute_function(self, app_session):
        call_local_solver(app_session)


class LocalSolverAssemblyLineSequencingOptimiser(AppWithDataSets):

    def get_name(self):
        return 'LocalSolver Assembly Line Sequencing Optimiser'

    def get_examples(self):
        return {"Demo - The Tropesla assembly line": load_data_set}

    def get_static_content_path(self, app_session):
        return pkg_resources.resource_filename('te_ls_assembly_line', 'static')

    def get_gui(self):
        step_group1 = StepGroup(name='Enter your Data')
        step_group1.add_step(Step(name='Enter your model names', widgets=[SimpleGrid(ALSOModelName)]))
        step_group1.add_step(Step(name='Enter the options for models', widgets=[SimpleGrid(ALSOOptionName)]))
        step_group1.add_step(Step(name='Define the options in each model', widgets=[SimpleGrid(ALSOOptionsInModel)]))
        step_group1.add_step(Step(name='Set block rules for options', widgets=[SimpleGrid(ALSOMaxCarsInBlockForOption)]))

        step_group2 = StepGroup(name='Solve')
        step_group2.add_step(Step(name='Solve assembly line sequencing problem using LocalSolver', widgets=[ExecuteLocalSolver()]))

        step_group3 = StepGroup(name='View the Solution')
        step_group3.add_step(Step(name='Assembly line sequence', widgets=[SimpleGrid(ALSOAssemblyLineModelSequence)]))

        return [step_group1, step_group2, step_group3]

    def get_icon_url(self):
        return "/{}/static/{}/car_sequencing.png".format(
            self.url_name,
            self.get_app_version()
        )


def load_data_set(app_session):
    model_names = [('Tropesla TSV1', 10), ('Tropesla TSV2', 10), ('Tropesla TSV3', 30), ('Tropesla TSV4', 20), ('Tropesla TSV5', 15), ('Tropesla TSV6', 25), ('Tropesla TSV7', 25), ('Tropesla TSV8', 20)]
    option_names = ['turbo charger', '6 Speed Gear Box', 'Reversing Camera', 'Head Rest Entertainment System', 'Leather Trim', 'Sports Body Kit']

    models = [app_session.data_set.add(ALSOModelName(name=s[0], num_cars_to_assemble=s[1])) for s in model_names]
    options = [app_session.data_set.add(ALSOOptionName(name=s)) for s in option_names]

    options_in_models = [
        [1, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 0, 1, 1],
        [1, 1, 0, 1, 0, 0, 0],
        [1, 0, 0, 0, 1, 0, 1],
        [1, 0, 1, 0, 0, 1, 0],
        [1, 1, 0, 0, 0, 1, 1],
        [3, 0, 1, 1, 0, 0, 0],
        [1, 1, 0, 1, 1, 0, 0]
    ]
    for model in models:
        for option in options:
            if options_in_models[models.index(model)][options.index(option)]:
                app_session.data_set.add(ALSOOptionsInModel(model_name=model.name, option_name=option.name))

    max_cars_in_block_for_otions = [(3, 5), (1, 3), (3, 5), (1, 3), (2, 3), (1, 2)]  # (max_car,block_size)
    for option in options:
        app_session.data_set.add(ALSOMaxCarsInBlockForOption(
            option_name=option.name,
            max_cars_in_block=max_cars_in_block_for_otions[options.index(option)][0],
            block_size=max_cars_in_block_for_otions[options.index(option)][1]
        ))


def call_local_solver(app_session):
    invoke_localsolver_using_lsp_file(app_session, write_localsolver_input_file(app_session))


def write_localsolver_input_file(app_session):
    input_file_name = 'input.in'
    input_file_path = app_session.get_file_path_in_local_data_set_dir(input_file_name)
    f = open(input_file_path, 'w')

    num_cars = sum([m.num_cars_to_assemble for m in app_session.data_set.query(ALSOModelName).all()])
    f.write('%s %s %s\n' % (num_cars, len(app_session.data_set.query(ALSOOptionName).all()), len(app_session.data_set.query(ALSOModelName).all())))
    option_names = [option.name for option in app_session.data_set.query(ALSOOptionName).all()]

    max_cars_string = ""
    block_size_string = ""
    for option_name in option_names:
        for block_rule in app_session.data_set.query(ALSOMaxCarsInBlockForOption).filter(ALSOMaxCarsInBlockForOption.option_name == option_name).all():
            max_cars_string += str(block_rule.max_cars_in_block) + " "
            block_size_string += str(block_rule.block_size) + " "
    f.write(max_cars_string + "\n")
    f.write(block_size_string + "\n")

    for model in app_session.data_set.query(ALSOModelName).all():
        model_has_options_string = str(app_session.data_set.query(ALSOModelName).all().index(model)) + " "
        model_has_options_string += str(app_session.data_set.query(ALSOModelName).filter(ALSOModelName.name == model.name).one().num_cars_to_assemble) + " "
        for option_name in option_names:
            if app_session.data_set.query(ALSOOptionsInModel).filter(ALSOOptionsInModel.model_name == model.name).filter(ALSOOptionsInModel.option_name == option_name).all():
                model_has_options_string += "1 "
            else:
                model_has_options_string += "0 "
        f.write(model_has_options_string + "\n")
    f.close()
    return input_file_name


def invoke_localsolver_using_lsp_file(app_session, input_file_name):
    app_session.data_set.query(ALSOAssemblyLineModelSequence).delete()
    lsp_file_path = pkg_resources.resource_filename('te_ls_assembly_line', 'car_sequencing.lsp')
    solution_file_name = 'output.txt'
    solution_file_path = app_session.get_file_path_in_local_data_set_dir(solution_file_name)
    open(solution_file_path, 'w').close()  # clear the solution file if it exists
    p = subprocess.Popen(
        ["localsolver", lsp_file_path, "inFileName=%s" % input_file_name, "solFileName=%s" % solution_file_name, "lsTimeLimit=10"], 
        cwd=app_session.local_data_set_dir,
        stdout=subprocess.PIPE,
    )
    out, _ = p.communicate()

    with open(solution_file_path) as f:
        content = f.readlines()
        if content:
            app_session.task_manager.send_progress_message(out.replace("\n", "<br>"))
            models = app_session.data_set.query(ALSOModelName).all()
            counter = 1
            for s in content[1].split():
                app_session.data_set.add(ALSOAssemblyLineModelSequence(model_name=models[int(s)].name, sequence=counter))
                counter = counter + 1  # beware solution.index(s) finding the wrong one
        else:
            app_session.task_manager.send_progress_message(
                '''The data you have entered exceeds the limits of the trial version of LocalSolver used to run this app.
                LocalSolver's Trial Version does not allow more than 1000 expressions and 100 decisions.'''
            )

LocalSolver lsp File

/********** car_sequencing.lsp **********/

/* Reads instance data. */
function input() {

  usage = "\nUsage: localsolver car_sequencing.lsp "
    + "inFileName=inputFile solFileName=outputFile [lsTimeLimit=timeLimit]\n";

  if (inFileName == nil) error(usage);
  if (solFileName == nil) error(usage);

  inFile = openRead(inFileName);
  nbPositions = readInt(inFile);
  nbOptions = readInt(inFile);
  nbClasses = readInt(inFile);

  ratioNums[1..nbOptions] = readInt(inFile);
  ratioDenoms[1..nbOptions] = readInt(inFile);

  for [c in 1..nbClasses] {
    readInt(inFile); // Note: index of class is read but not used
    nbCars[c] = readInt(inFile);
    options[c][1..nbOptions] = readInt(inFile);
  }
}

/* Declares the optimization model. */
function model() {	
  // 0-1 decisions: 
  // cp[c][p] = 1 if class c is at position p, and 0 otherwise
  cp[1..nbClasses][1..nbPositions] <- bool();

  // constraints: 
  // for each class c, no more than nbCars[c] assigned to positions
  for [c in 1..nbClasses] 
    constraint sum[p in 1..nbPositions](cp[c][p]) == nbCars[c];

  // constraints: one car assigned to each position p
  for [p in 1..nbPositions] 
    constraint sum[c in 1..nbClasses](cp[c][p]) == 1;

  // expressions: 
  // op[o][p] = 1 if option o appears at position p, and 0 otherwise
  op[o in 1..nbOptions][p in 1..nbPositions] <- 
    or[c in 1..nbClasses : options[c][o]](cp[c][p]);

  // expressions: compute the number of cars in each window
  nbCarsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1] 
    <- sum[k in 1..ratioDenoms[o]](op[o][p+k-1]);

  // expressions: compute the number of violations in each window
  nbViolationsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1] 
    <- max(nbCarsWindows[o][p]-ratioNums[o], 0);

  // objective: minimize the sum of violations for all options and all windows
  obj <- sum[o in 1..nbOptions]
    [p in 1..nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);
  minimize obj;	
}

/* Parameterizes the solver. */
function param() {
  if (lsTimeLimit == nil) lsTimeLimit = 60;
  lsTimeBetweenDisplays = 3;
  lsNbThreads = 4;
}

/* Writes the solution in a file following the following format: 
 * - 1st line: value of the objective;
 * - 2nd line: for each position p, index of class at positions p. */
function output() {
  solFile = openWrite(solFileName);
  println(solFile, getValue(obj));
  for [p in 1..nbPositions][c in 1..nbClasses : getValue(cp[c][p])] 
    print(solFile, c-1, " ");
  println(solFile);
}