Sequencing mixed-model assembly lines to level parts usage and minimize line length

The problem of sequencing units on a mixed-model assembly line can be viewed with several objectives in mind. Past research has focused mainly on two separate performance measures: (1) minimizing the length of the line (which is equivalent to minimizing the risk of stopping the conveyor when system variability is present and the station lengths are fixed); or (2) maintaining a rate of assembly equal to the demand rate for each model type in the production schedule. The latter is the more appropriate in a just-in-time environment. We present a bicriteria formulation of the problem that can be used to examine the tradeoffs between line length and parts usage. The resultant model takes the form of a mixed integer nonlinear program and is solved with a combination of heuristics and branch and bound. Results are reported for a wide range of problem sizes, as defined by the number of stations on the line, the number of different model types, and the total number of units to be assembled. In almost all cases, at least one of the heuristics found either the optimum or the best available solution. Computation times were quite reasonable for the heuristics, but grew exponentially for branch and bound. In general, it was only possible to verify optimality on problems with ⩽20 units.