Scheduling Mixed-Model Assembly Lines Under Uncertain Component Arrival Times: A Review of Models and Solution Approaches

1. Introduction

A mixed-model assembly line produces several variants of a base product in intermixed order, without setups between units. Automotive final assembly is the standard example, but the same arrangement is found in the assembly of trucks, tractors, household appliances and electronic equipment. Because the variants differ in the work they require at each station and in the parts they consume, the launch sequence matters. A sequence that places several work-intensive variants in a row overloads the operators at the affected stations, and a sequence that bunches the users of one option drains that option's line-side stock in bursts (Boysen et al., 2009).

Sequencing research grew up alongside the Toyota Production System, in which levelled production is the condition that allows upstream processes and suppliers to work with small, steady lots (Monden, 1998). The models it produced share an assumption that is seldom stated: the parts are there. Each order in the sequence can be built at the moment it reaches a station. On a line fed just-in-time or just-in-sequence this is a matter of logistics performance and not a given. A sequenced module that arrives late, or a tote that fails incoming inspection, leaves the planner with an order that cannot be completed in its slot.

This article reviews what the published literature offers for sequencing mixed-model lines when component arrival times are uncertain. The question is practical. Planners already respond to missing parts, by swapping orders, pulling bodies out of the sequence or completing vehicles in a rework area. What the literature can contribute is a view of which of these responses should be designed into the plan and which left to the shift.

2. Scope and Approach

The article is a narrative review of the published literature. It draws on the main surveys of assembly line sequencing, resequencing and part logistics, on the foundational papers they build on, and on the general literature on scheduling under uncertainty, from which most of the applicable modelling ideas come. No claim of exhaustive coverage is made. Line balancing, the assignment of tasks to stations, is treated only as the context in which sequencing takes place; it is surveyed by Becker and Scholl (2006).

3. The Deterministic Foundation

Boysen et al. (2009) sort the sequencing literature into three approaches that differ in what they treat as the objective. Each rests on full knowledge of orders and parts, and each responds differently when that knowledge fails.

3.1. Mixed-model sequencing and work overload

The first approach models the line in detail: station lengths, processing times per variant, operator movement and the cycle time. Its roots lie in the joint balancing and sequencing procedure of Thomopoulos (1967). The objective is usually to minimise work overload, the work that operators cannot finish within their station boundaries and that must be covered by utility workers or left for repair. Yano and Rachamadugu (1991) formulated this problem for lines with product options, and Bard et al. (1992) set out an analytic framework that distinguishes line designs by launch discipline and station type. Because the model tracks each operator's position, any change in the sequence, such as the removal of an order whose parts are missing, alters the overload at every later cycle.

3.2. Car sequencing

Car sequencing replaces the detailed model with rules of the form "at most H out of N consecutive units may carry option O". A sequence is sought that violates as few rules as possible. The approach is popular in industry because rules are easy to state and maintain, and it became a benchmark for constraint programming and local search after the ROADEF challenge of 2005, which is described with the state of the art by Solnon et al. (2008). Whether rules are a good surrogate for work overload has been examined computationally by Golle et al. (2014). For the present subject the relevant property is that sequencing rules are local, so the damage done by a removed or swapped order is confined to a window around it.

3.3. Level scheduling

The third approach takes the supply side as its objective. Miltenburg (1989) formalised the Toyota idea as the search for a sequence in which the cumulative production of each model stays close to its proportional share at every position, and the many variants of this problem are surveyed by Kubiak (1993). A level sequence draws parts at a nearly constant rate, which is what allows suppliers and feeders to work with small buffers. Drexl and Kimms (2001) combined part-usage levelling with station-load constraints in one model. Level scheduling thus aims to prevent material shortages by smoothing demand, but it has nothing to say when a shortage occurs anyway.

4. Where Arrival Uncertainty Enters

Parts reach an assembly line by several routes, and the routes differ in how exposed they are to timing risk. Battini et al. (2009) compare the main feeding policies, among them line stocking in pallets, kitting and supermarket-based replenishment, in terms of the stock and handling each implies. Bulk parts held at the line in quantity are rarely the problem. The exposed categories are large, variant-specific modules such as seats, cockpits and bumpers, which are delivered just-in-sequence in the exact order of the vehicles, often straight from the truck to the point of fit. The decision problems of this supply chain, from call-off to line-side presentation, are reviewed by Boysen et al. (2015).

Just-in-sequence supply ties the supplier's production to the assembly sequence, so uncertainty runs in both directions. The supplier needs the sequence to be announced early and then kept; the assembler needs the modules to arrive on time and in order. Meissner (2010) discusses the control of such flows and the role of sequence stability, the degree to which the sequence that is finally built matches the one that was communicated. The sequence is disturbed inside the plant as well. Bodies leave the paint shop in a different order from the one in which they entered, because of rework and colour batching, and Inman (2003) shows how a storage and retrieval system between paint and assembly must be sized to restore the planned order. A late component is thus one of several disturbances competing for the same recovery resources.

Boysen et al. (2012) survey resequencing and separate physical resequencing, in which units change places by means of buffers such as mix banks, pull-off tables or automated stores, from virtual resequencing, in which customer orders are reassigned among physically identical units. Both are available as responses to a missing part. Their survey also makes clear that most resequencing models were built for disturbances originating in the body and paint shops, not for late deliveries.

5. Modelling Options

The general literature on scheduling under uncertainty offers a small number of strategies, and they recur across application areas. Herroelen and Leus (2005) distinguish reactive, stochastic and proactive approaches for project scheduling; Aytug et al. (2005) discuss how production schedules are executed when the shop does not behave as planned; and Ouelhadj and Petrovic (2009) classify dynamic scheduling into completely reactive, predictive-reactive and robust proactive forms. Figure 1 arranges the responses available on a mixed-model line under three headings, according to whether the uncertainty is absorbed before the line, anticipated in the sequence or handled during the shift. Table 1 compares the corresponding modelling approaches.

5.1. Buffers and time allowances

The oldest response is to hold more: more line-side stock, an earlier delivery time, or a sequence buffer in front of final assembly. These measures need no change to the sequencing model, which is their attraction, and for small common parts they are usually the right answer. For sequenced modules they are costly, because every unit of stock is specific to one vehicle and occupies space at the most congested part of the plant. Safety lead time also moves the freeze point of the sequence earlier, which reduces the planner's freedom to react to other disturbances.

5.2. Stochastic programming

If arrival times can be described by probability distributions, sequencing can be posed as a two-stage stochastic programme (Birge and Louveaux, 2011). The first stage fixes the sequence; the second stage, evaluated for each scenario of arrivals, contains the recourse actions and their cost, for example the overload and rework caused by orders that must be skipped. Since the number of scenarios grows quickly with the number of exposed components, the expectation is normally replaced by an average over a sample of scenarios, the sample average approximation analysed by Kleywegt et al. (2002). The approach is transparent about what it optimises. Its practical difficulty is the distributional input: delivery delays are rare, correlated across parts that share a truck, and poorly recorded.

5.3. Robust optimisation

Robust optimisation dispenses with probabilities and asks for a solution that performs acceptably for every realisation in a stated uncertainty set (Ben-Tal et al., 2009). For discrete problems the min-max and min-max regret criteria were developed by Kouvelis and Yu (1997). Protecting against every component being late at once would yield a uselessly cautious sequence, and the budgeted uncertainty set of Bertsimas and Sim (2004) addresses this by limiting the number of parameters that may deviate together. In sequencing terms, the planner seeks an order that remains workable if any limited number of deliveries slip by up to a stated amount. The budget is a judgement, but it is one that logistics staff can relate to their experience.

5.4. Predictive-reactive resequencing

The alternative to anticipating disturbances is to repair the sequence when they occur. Vieira et al. (2003) give the standard framework: a predictive schedule is released and is revised periodically, on events, or by a hybrid of the two, and the revision may regenerate the schedule or repair it locally. On an assembly line local repair is the rule, since the line cannot stop and the upstream sequence is already committed. The affected order is moved back by a few positions, exchanged with a similar order, or built incomplete and finished off line. Each option has a cost that the deterministic models can evaluate, and each feeds back to sequenced suppliers, whose own deliveries were built to the original order.

6. Solution Methods and Evidence

The deterministic problems are hard in the complexity-theoretic sense in almost all their practical forms, and exact methods, chiefly branch and bound and mixed-integer programming, reach optimality only for sequences of moderate length (Boysen et al., 2009). Industrial instances are handled by constructive heuristics and by metaheuristics such as simulated annealing, tabu search and ant colony optimisation, and local search methods were prominent among the entries to the ROADEF challenge (Solnon et al., 2008). Adding uncertainty multiplies the work. A stochastic model must evaluate each candidate sequence across scenarios, and a robust model must find the worst case for each candidate. Decomposition by scenario and the embedding of a fast deterministic evaluator inside a metaheuristic are the usual ways through.

The evidence on which approach performs best is thin. Published comparisons are computational, carried out on generated instances with assumed delay patterns, and they inherit the weaknesses of those assumptions. Discrete-event simulation of the line together with its supply is the natural test bed, because it can represent trucks, unloading, sequence buffers and rework loops in one model. Rolling-horizon experiments, in which the sequence is re-optimised as arrival information is updated, come closest to the way planners work. They can be expected to narrow the difference between sophisticated and simple policies, since frequent re-planning corrects much of what a single plan gets wrong, and this is a reason to report such experiments alongside single-plan comparisons.

7. Gaps and Directions for Research

Four gaps stand out. The first is integration. Sequencing, part feeding and resequencing have each been surveyed thoroughly, but as separate problems; a model in which the sequence is chosen with knowledge of the delivery schedule and of the recovery options available downstream is still rare. The second concerns the description of uncertainty. Arrival delays on real inbound flows are neither independent nor identically distributed, and research that characterises them from transport and receiving records would give both stochastic and robust models a firmer base.

The third gap is the valuation of sequence stability. A recovery that is cheap for the assembler may be expensive for sequenced suppliers and for the customer whose order slips, and few models carry these costs. The fourth is information. Track-and-trace data on inbound trucks and containers turn part of the uncertainty into advance warning, and the value of an hour's notice, in terms of the recovery options it keeps open, has not been worked out. Progress on these points would also help decide a design question that plants currently settle by habit: how much to spend on buffers and how much on planning.

8. Conclusion

The sequencing of mixed-model assembly lines is a mature field built on the assumption that parts are available. Supply uncertainty has been addressed mostly outside the sequencing model, through feeding policies and buffers, and disturbances inside it mostly through resequencing rules developed for paint shop scrambling. The tools needed to do better exist: two-stage stochastic programmes, budgeted robust formulations and predictive-reactive repair are well understood and have been applied to related scheduling problems. What is missing is their combination in models that treat the sequence, the inbound flow and the recovery actions together, supported by empirical descriptions of how component arrivals vary in practice.

Conflict of interest

To be declared by the author(s) before publication.

Funding

To be declared by the author(s) before publication.