Invited ReviewSequencing mixed-model assembly lines: Survey, classification and model critique
Introduction
Since the times of Henry Ford and his famous Model-T, product requirements and thereby the requirements of production systems have changed dramatically. Originally, assembly lines were developed for a cost efficient mass production of a single standardized product. Nowadays, a multitude of options (e.g. manual or electric sunroof, air conditioning yes/no) is selectable by the customers, so that the manufacturers of these products need to handle a (theoretical) product variety which exceeds several billions of models (for detailed figures of European car manufacturers see, e.g. Pil and Holweg, 2004, Meyr, 2004, Röder and Tibken, 2006). To enable such a highly diversified product portfolio without jeopardizing the benefits of an efficient flow-production, so called mixed-model assembly lines are utilized. Practical applications stem not only from the automobile industry, but also from many segments of consumer goods industries, e.g. consumer electronics, white goods, furniture and clothing (see Sarker and Pan, 2001, Boysen et al., in press).
In a mixed-model assembly line, the application of flexible workers and machinery leads to a substantial reduction in setup times and cost, so that different products can be jointly manufactured in intermixed product sequences (lot size of one) on the same line. In addition to flexible resources being available, the production processes of manufactured goods require a minimum level of homogeneity. Thus, there usually exists a common base product, which is customizable by the (de-)selection of optional features out of a pre-specified set of options.
In addition to the long- to mid-term assembly line balancing problem (see Baybars, 1986, Scholl and Becker, 2006, Becker and Scholl, 2006, Boysen et al., 2006a, Boysen et al., in press), mixed-model assembly lines give rise to a short-term sequencing problem, which has to decide on the production sequence of a given number of model copies within the planning horizon, e.g., one day or shift.
Although (almost) any intermixed sequence of models is technically feasible, its significant economic impacts necessitate a thorough planning. In particular the labor utilization at workstations and the spreading of material demand are determined by the model sequence and are, hence, in the center of two different general objectives (c.f. Bard et al., 1994).
- •
Work overload: The installation of varying options typically leads to variations in processing times at work stations. In automobile production, for instance, the installation of an electrical sunroof requires a different amount of time than that of a manual one. If several work intensive models follow each other at the same station, work overloads might occur, which need to be compensated, e.g., by additional utility workers. Work overloads can be avoided if a sequence of models is found, where those models which cause high station times alternate with less work-intensive ones.
- •
Just-in-Time objectives: JIT-centric sequencing approaches focus on the deviating material requirements. Different models are composed of different product options and thus require different materials and parts, so that the model sequence influences the progression of material demands over time. As an assembly line is commonly coupled with preceding production levels by means of a JIT-supply of required materials (e.g. Monden, 1998), the model sequence needs to facilitate this. An important prerequisite for JIT-supply as stated in literature (e.g. Joo and Wilhelm, 1993) is a steady demand rate of material over time, as otherwise the advantages of JIT are sapped by enlarged safety stocks that become necessary to avoid stock-outs during demand peaks. Accordingly, JIT-centric sequencing approaches aim at distributing the material requirements evenly over the planning horizon.
These two basic objectives (minimizing work overload and leveling part usage) were taken up in three alternative sequencing approaches discussed in literature:
- •
Mixed-model sequencing: This approach aims at avoiding/minimizing sequence-dependent work overload based on a detailed scheduling which explicitly takes operation times, worker movements, station borders and other operational characteristics of the line into account.
- •
Car sequencing: To avoid the significant effort of data collection that accompanies mixed-model sequencing, car sequencing attempts to minimize sequence-dependent work overload in an implicit manner. This is achieved by formulating a set of sequencing rules of type , which postulate that among No subsequent sequence positions at most Ho occurrences of a certain option o are allowed. If a sequence is found which does not violate such rules, work overload can be avoided. Even if avoidance is not fully possible, the work overload is supposed to be the lower the fewer rules are violated.
- •
Level scheduling: While the first two approaches aim at minimizing violations of capacity constraints, level scheduling seeks to find sequences which are in line with the JIT-philosophy. For this purpose “ideal” production rates are defined and models are sequenced in such a manner that deviations between actual and ideal rates are minimized. Although the majority of papers focus on the demand rates of material, the same principles can also be employed to smoothen capacity utilization.
All three sequencing approaches are discussed in this paper. Section 2 establishes the exact scope of this review and identifies the common structural characteristics of all reviewed models. The subsequent Sections 3 Mixed-model sequencing, 4 Car sequencing, 5 Level scheduling address the alternative model sequencing approaches individually and provide a tupel-notation (e.g. see Graham et al., 1979) to classify relevant problem extensions. While existing survey papers (mixed-model sequencing: Yano and Bolat, 1989; car-sequencing: Solnon et al., in press; level scheduling: Kubiak, 1993, Dahmala and Kubiak, 2005, Boysen et al., 2006b) exclusively focus on one sequencing approach separately, this work aims at providing an integrated review and classification, which is of particular value for two reasons:
- •
As both objectives (minimizing work overload and leveling part usage) proved to be highly important for practical applications, hybrid sequencing approaches were developed to optimize both goals simultaneously. These approaches can only be captured in an integrated review and are, thus, considered in Section 6.
- •
By investigating the relationship between the three sequencing approaches important fields of future research can be identified, as is discussed in Section 7.
The primary aim of this paper is to provide a comprehensive and integrated analysis of sequencing approaches for mixed-model assembly to line out the status quo as well as current and future challenges in this vast field of research.
Section snippets
Scope of the review
The assembly lines considered in this paper consist of multiple stations arranged along some kind of transportation system, e.g., a conveyor belt, which is steadily moving workpieces from station to station (paced assembly lines). Workers escort the workpieces while processing a set of pre-specified tasks in each production cycle. As soon as all tasks are completed, the worker returns upstream until he reaches the next workpiece or the border of his station. W.l.o.g. it is assumed that the
Problem statement
The line balance of a mixed-model assembly system is typically determined on the basis of a so called joint precedence graph, where the diverging processing times of the respective models are averaged (see van Zante-de Fokkert and de Kok, 1997, Boysen et al., 2006d). In order to avoid excessive capacities, the cycle time is then determined such that it is observed on average over all models. As a consequence, the processing times of some models are higher than the cycle time, whereas that of
Problem statement
Instead of a detailed scheduling of work content, car sequencing considers and controls the succession of work intensive product options (e.g., sunroof, air conditioning) in order to avoid work overload. A set of product options can be subject to sequencing rules, which restrict the maximum number of occurrences within a subsequence of a certain length. The car sequencing problem then seeks to find a sequence of models which meets the required demands for each model without violating the given
Problem statement
As part of the famous “Toyota Production System” level scheduling received wide attention in research (see the surveys by Kubiak, 1993; as well as Dahmala and Kubiak, 2005) and practical applications (e.g. Monden, 1998, Duplaga et al., 1996, Mane et al., 2002). This approach aims at evenly smoothing the material requirements induced by the production sequence over time, so that a just-in-time supply of material is facilitated and safety stocks are minimized. For that purpose, each material
Classifying hybrid model sequencing approaches
Both “minimization of work overload” and “leveling part usage” turned out to be valuable but often conflicting objectives for model sequencing. Consequently, several hybrid approaches have been developed. In order to classify those approaches, the three classifications are unified to a single hierarchical classification scheme. At the first level the distinction between the three model sequencing approaches is made. This is clarified by the abbreviations: MM (mixed-model sequencing), CS (car
Discussion of models
Open research can be divided into two categories: (i) research needs within the respective model family, which can be identified with the help of our classification scheme-based literature analysis, and (ii) research needs regarding the relation of models.
Conclusion
This paper gives a comprehensive review of the three major approaches for sequencing mixed-model assembly lines as well as related multi-criteria and hybrid problems. A hierarchical classification scheme is developed, which covers all proposed problem extensions in a systematic manner. The classification provides insights in the status quo of research in each field, but also allows a comparison of the different approaches with regard to the level of planning detail and the actual problem
References (206)
- et al.
A simple approach to the product rate variation problem via axiomatics
Operations Research Letters
(1998) - et al.
A survey on problems and methods in generalized assembly line balancing
European Journal of Operational Research
(2006) - et al.
Controlling mixed-model assembly lines in real-time by using distributed systems
European Journal of Operational Research
(2006) - et al.
Algorithms for the real-time scheduling of jobs on mixed model assembly lines
Computers & Operations Research
(1994) - et al.
Constraint satisfaction problems: Algorithms and applications
European Journal of Operational Research
(1999) - et al.
Resource-constrained project scheduling: Notation, classification, models and methods
European Journal of Operational Research
(1999) - et al.
Multi-agent systems in production planning and control: An application to the scheduling of mixed-model assembly lines
International Journal of Production Economics
(2000) - et al.
An evolutionary approach to multi-objective scheduling of mixed-model assembly lines
Computers & Industrial Engineering
(1999) - et al.
Human factor policy testing in sequencing of manual mixed model assembly lines
Computers & Operations Research
(2004) Mixed-model assembly line sequencing problems
OMEGA
(1978)
An effective mixed-model assembly line sequencing heuristic for Just-in-Time production systems
Journal of Operations Management
Production planning to support mixed-model assembly
Computers & Industrial Engineering
Comparing two weighted approaches for sequencing mixed-model assembly lines with multiple objectives
International Journal of Production Economics
A typology of cutting and packing problems
European Journal of Operational Research
Solving real car sequencing problems with ant colony optimization
European Journal of Operational Research
Optimization and approximation in deterministic sequencing and scheduling: A survey
Annals of Discrete Mathematics
Formulation and Solution of a Selection and Sequencing Problem in Car Manufacture
Computers & Industrial Engineering
A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines
Computers & Operations Research
Sequencing in mixed model assembly lines: A genetic algorithm approach
Computers & Operations Research
An endosymbiotic evolutionary algorithm for the integration of balancing and sequencing in mixed-model U-lines
European Journal of Operational Research
On the complexity of the car sequencing problem
Operations Research Letters
Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems
European Journal of Operational Research
Minimizing variation of production rates in just-in-time systems: A survey
European Journal of Operational Research
Some structural properties for the just-in-time level schedule problem
Production Planning & Control
Analysis of parts requirements variance for a JIT supply chain
International Journal of Production Research
A simulation analysis for two-level sequence-scheduling for just-in-time (JIT) mixed-model assembly lines
International Journal of Production Research
A parametric procedure for multi-criterion sequence scheduling for just-in-time mixed-model assembly lines
International Journal of Production Research
Assembly line balancing with parallel workstations and dead time
International Journal of Production Research
An analytic framework for sequencing mixed model assembly lines
International Journal of Production Research
Sequencing mixed-model assembly lines to level parts usage and minimize line length
International Journal of Production Research
A note on the relation between the product rate variation (PRV) and the apportionment problem
Journal of Operational Research Society
Heuristics and exact algorithms for solving the Monden problem
European Journal of Operational Research
A survey of exact algorithms for the simple assembly line balancing problem
Management Science
Sequencing job on an automobile assembly line: Objectives and procedures
International Journal of Production Research
Stochastic procedures for scheduling minimum job sets on mixed model assembly lines
Journal of Operational Research Society
A mathematical model for selecting mixed models with due dates
International Journal of Production Research
Scheduling algorithms to minimize utility work at a single station on a paced assembly line
Production Planning & Control
A surrogate objective for utility work in paced assembly lines
Production Planning & Control
Reihenfolgeplanung bei Variantenfließfertigung: Ein integrativer Ansatz
Zeitschrift für Betriebswirtschaft
Comments on “Solving real car sequencing problems with ant colony optimization
European Journal of Operational Research
Comment on Gravel, M., Gagné,T.C., Price W.L., 2005. Review and comparison of three methods for the solution of the car sequencing problem
Journal of the Operational Research Society
A classification of assembly line balancing problems
European Journal of Operational Research
Level-Scheduling bei Variantenfließfertigung: Literaturüberblick, Klassifikation und Modellkritik
Journal für Betriebswirtschaft
Produktionsplanung bei Variantenfließfertigung: Planungshierarchie und Elemente einer Hierarchische Planung
Zeitschrift für Betriebswirtschaft
Assembly line job sequencing principles
International Journal of Production Research
The structure of manufacturing systems: Insights on the impact of variability
International Journal of Flexible Manufacturing Systems
Cited by (359)
The maximum length car sequencing problem
2024, European Journal of Operational ResearchBalancing mixed-model assembly lines for random sequences
2024, European Journal of Operational ResearchIntegrating virtual resequencing with car resequencing via selectivity banks for mixed-model assembly lines
2024, Computers and Industrial EngineeringAdaptive local search algorithm for solving car sequencing problem
2023, Journal of Manufacturing SystemsRobust mixed-model assembly line balancing and sequencing problem considering preventive maintenance scenarios with interval processing times
2023, Swarm and Evolutionary Computation