Improved integer programming models for simple assembly line balancing and related problems

• Date: 01 July 2018
• DOI: http://doi.org/10.1111/itor.12206
• Published date: 01 July 2018

Intl. Trans. in Op. Res. 25 (2018) 1345–1359

DOI: 10.1111/itor.12206

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Improved integer programming models for simple assembly line

balancing and related problems

Marcus Rittaand Alysson M. Costab

aInstituto de Inform´

atica, Universidade Federaldo Rio Grande do Sul, Av. Bento Gonc¸alves 9500, Porto Alegre,Brazil

bSchool of Mathematics and Statistics, University of Melbourne, Parkville 3010, Australia

E-mail: marcus.ritt@inf.ufrgs.br [Ritt]; alysson.costa@unimelb.edu.au [Costa]

Received 22 January 2015; received in revised form 15 May 2015; accepted 31 July 2015

Abstract

We propose a stronger formulation of the precedenceconstraints and the station limits for the simple assem-

bly line balancing problem. The linear relaxation of the improved integer program theoretically dominates

all previous formulations using impulse variables, and produces solutions of significantly better quality in

practice. The improved formulation can be used to strengthen related problems with similar restrictions. We

demonstrate their effectiveness on the U-shaped assembly line balancing problem and on the bin packing

problem with precedence constraints.

Keywords:assembly line balancing; integer linear programming; valid inequalities; precedence constraints; station limits

1. Introduction

Let (N,≤)be a weak partially ordered set of tasks with integral execution time tifor i∈N.The

simple assembly line balancing problem (SALBP) is to find an assignment a:N→Sof the tasks to

a linear sequence of stations S={1,2,...,m}, respecting the partial order, thatis, all tasks i,j∈N

with i≤jsatisfy a(i)≤a(j).Thecycle time of an assignment is the largest time needed to execute

the tasks assigned to some station. The problem is said to be of type 1 (SALBP-1) whenthe goal is to

minimize the number stations for a given cycle time, and to be of type 2 (SALBP-2) when the goal is

to minimize the cycle time for a given number of stations. The decision version of both problems is

NP-complete, since without precedence constraints SALBP-1 reduces to the bin packing problem,

and SALBP-2 to the problem of minimizing the makespan of a schedule of the tasks on identical

parallel machines.

The SALBP has been extensively studied in the literature, and there are excellent constructive

and heuristic algorithms, as well as exact solution methods available (e.g., Scholl and Voß, 1996;

Scholl and Klein, 1999; Fleszar and Hindi, 2003; Blum, 2008; Sewell and Jacobson, 2012). A very

good overview of the methods can be found in the survey of Scholl and Becker (2006).

C

2015 The Authors.

International Transactionsin Operational Research C

2015 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.