International Journal of Production Research

ISSN: (Print) (Online) Journal homepage: https://www.tandfonline.com/loi/tprs20

Assembly line balancing with fractional task

allocations

Thiago Cantos Lopes , Nadia Brauner & Leandro Magatão

To cite this article: Thiago Cantos Lopes , Nadia Brauner & Leandro Magatão (2021): Assembly
line balancing with fractional task allocations, International Journal of Production Research, DOI:
10.1080/00207543.2020.1866224

To link to this article: https://doi.org/10.1080/00207543.2020.1866224

Published online: 12 Jan 2021.

Submit your article to this journal

Article views: 153

View related articles

View Crossmark data

Full Terms & Conditions of access and use can be found at

https://www.tandfonline.com/action/journalInformation?journalCode=tprs20
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
https://doi.org/10.1080/00207543.2020.1866224

Assembly line balancing with fractional task allocations

Thiago Cantos Lopes a,b , Nadia Brauner b and Leandro Magatão a

a Graduate Program in Electrical and Computer Engineering (CPGEI), Federal University of Technology – Paraná (UTFPR), Curitiba, Brazil;
b University Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, Grenoble, France

ABSTRACT ARTICLE HISTORY

Assembly line balancing usually presupposes binary task-station assignments. Some authors have Received 11 July 2020
previously described efficiency increases due to fractional task allocations or work-sharing. However, Accepted 2 December 2020
the internal storage requirements for such efficiency increases have not been analytically described. KEYWORDS
This paper defines the Fractional Allocation Assembly Line Balancing Problem and presents mixed- Assembly line balancing;
integer linear programming models to bridge that gap. The main opportunity afforded by the cyclical scheduling; fractional
studied flexibility is increased throughput, which is associated to higher internal storage costs. Worst- task allocation;
case analyses define mathematical expressions for these costs both for paced (line length) and mixed-integer linear
unpaced lines (buffers). A screening on a 1050-instance dataset is conducted. Results suggest that programming; space cost
fractional allocations can often allow better resource utilisation with relatively low costs: the higher minimisation
space requirement costs are often one-time investments, while lower cycle time represents funda-
mentally continuous gains. Lastly, the proposed formulation was adapted and applied to industrial
data. This mixed-model assembly line case study suggests that fractional allocations can also lead to
more robust balancing regarding demand uncertainty.

1. Introduction
stations. Nonetheless, this represents an additional bal-
Assembly lines are product-oriented production layouts ancing flexibility, and the common conclusion drawn
commonly employed in various industrial settings. The from these literature bodies is this added flexibility allows
most classical optimisation problem associated to them higher throughputs (or equivalently, lower cycle times).
is the assembly line balancing problem (Scholl 1999), The concept of fractional task allocations is also found
which consists in assigning task to stations. The most in lines with station parallelism: in them, tasks are per-
basic of such problems is the Simple Assembly Line Bal- formed 50% of the time in each of the parallel stations
ancing Problem (SALBP), which has multiple simplifying (assuming there are two of them). This body of liter-
assumptions (Baybars 1986). These have been questioned ature also concludes that higher throughput is achiev-
and relaxed by many authors, defining many general able under the greater assignment flexibilities. However,
problem variants (Boysen, Fliedner, and Scholl 2008). parallel stations require significant layout changes and
Out of SALBP’s basic hypotheses, fewer works challenge increased worker training costs due to the increase in
the binary nature of the task-station assignments. number of tasks performed. A current limitation of the
To the best of the authors’ knowledge, two overlap- work-sharing and dynamic balancing literatures is not
ping bodies of literature have considered challenging this adequately describing the costs and trade-offs required
hypothesis: dynamic balancing and work-sharing (Chen by the fractional allocation of tasks. Consequently, task-
and Askin 2006; Anuar and Bukchin 2006). sharing has not yet been formalised in terms of a proper
These literature bodies allow some tasks to be per- variant of the assembly line balancing problem: The
formed sometimes at one station and sometimes at the most recent reviews on the topic (Boysen, Fliedner, and
next or previous one. This means that for that task, its Scholl 2008; Battaïa and Dolgui 2013) do not address this
allocation decision variable is a fraction that states how potential flexibility.
often the task is performed on each station. Naturally, This paper formally defines the Fractional Alloca-
some restrictions apply: e.g. each station pair can only tion Assembly Line Balancing Problem (FA-ALBP) as a
share one task, and each task can only be shared by two direct variant from SALBP. Its main contribution to the

CONTACT Leandro Magatão [email protected]

© 2021 Informa UK Limited, trading as Taylor & Francis Group

2 T. C. LOPES ET AL.

related literature is the description of how internal stor- share a task with both its upstream and downstream
age costs are tied to these fractional allocations for each neighbour simultaneously. Bukchin and Sofer (2011) go
line type. This formalisation allows a better understand- further by allowing more general task sequences. Both
ing of the trade-offs tied to this performance enhancing works, however, limit their analyses to asynchronous
opportunity. unpaced lines and the costs of task-sharing are con-
The article is structured as follows: Section 2 presents sidered given parameters which do ‘not depend on
the relevant literature and contextualises the article’s con- the sharing proportion of the task’ – a hypothesis
tribution. Section 3 presents the formal notation and that is questioned by the present paper. Furthermore,
general definitions of the considered problem. Section 4 the bi-directional work-sharing complicates analytical
presents the cycle time minimisation (throughput max- descriptions of buffer requirements, requiring simula-
imisation) aspect of the problem, while Section 4.2 tions to address that aspect of the problem (Anuar and
presents the internal storage minimisation one. Experi- Bukchin 2006). Nonetheless, work-sharing tends to offer
ments are presented in Section 5 and the key discussions better efficiency, both as lower cycle times (Bukchin
and contributions are presented in Section 6. and Sofer 2011) and as lower makespan (Gultekin 2012;
Bukchin and Wexler 2015).
Other examples of work-sharing encompass perform-
2. Literature review
ing tasks in different stations for different product mod-
Assembly line balancing problems are generally NP-Hard els (Yang, Gao, and Li 2014) and splitting some tasks
optimisation problems (Álvarez-Miranda and Pereira via alterations in the precedence diagram (Grzechca
2019). Its most basic version, the Simple Assembly and Foulds 2015). Hence, task splitting/sharing, or par-
Line Balancing Problem (SALBP) has several simplifying tial/fractional task-station allocations are research top-
hypotheses that reflect the earliest studies on produc- ics that were addressed by some authors in multiple
tion lines. In the definition presented by Baybars (1986), manners.
the hypothesis that ‘a task cannot be split among two In a recent paper, Jeong and Jeon (2020) further inves-
or more stations’ is second only to ‘all input parame- tigated the conditions for balanceability (reaching the
ters are known with certainty’. Multiple problem variants minimum possible cycle time) tied to work-sharing for
are defined by deviating from the other hypothesis, but both straight and U-shapped assembly lines. However,
are beyond the scope of this review. Readers can refer the authors consider unlimited buffers between stations
to Boysen, Fliedner, and Scholl (2008) and Battaïa and and do not investigate the impact of work-sharing on
Dolgui (2013) for classifications of such variants. Chen internal storage requirements.
and Askin (2006) define flexibility on task-station assign- However, a limitation of the aforementioned literature
ments for specific tasks as ‘dynamic line balancing’: some is that line control (Boysen, Fliedner, and Scholl 2007)
tasks are fixed to stations while others are allowed to be is either not discussed or presumed to be unpaced asyn-
shared between two adjacent stations. In their experi- chronous, a context in which buffers are naturally used
ments, this flexibility leads to higher productivity. How- to compensate performance oscillations and to allow
ever, other authors define dynamic balancing differently: higher throughputs (Lopes, Sikora et al. 2020; Lopes,
Shtub (1993) discusses it as part of the just-in-time phi- Michels et al. 2020). Recent works showed that a line’s
losophy of Japanese manufacturers (Schonberger 1982), control can influence its performance (Lopes et al. 2018).
and Ahn and Righter (2006) present it in terms of a Paced lines can also employ line length to compensate
flexible assignment of cross-trained workers to stations. for fluctuations in processing times (Boysen, Fliedner,
These works often employ simulations to analyse policies and Scholl 2008), a feature that has also been shown
or combine them to optimisation approaches (Dagkakis, to allow lower cycle time (Lopes, Pastre et al. 2020) in
Rotondo, and Heavey 2019). specific contexts. Work-sharing or fractional task allo-
For instance, Pasupa and Suzuki (2019) recently pre- cations naturally cause station-wise performance oscil-
sented a simulation-based case study for dynamic line lations, which must be compensated by internal storage.
balancing under heterogeneous workers. In this litera- However, the current literature on the subject lacks an
ture, a common theme is the achievement of a higher analytical description on how internal storage is tied to
throughput. Anuar and Bukchin (2006) share Chen fractional allocations.
and Askin (2006)’s definition of dynamic line balanc- Lastly, it is important to compare the flexibilities of
ing, but later works (Bukchin and Sofer 2011; Bukchin task-sharing to those of parallel stations. The later are
and Wexler 2015) simply refer to it as ‘work-sharing’. common to various practical contexts and have been
Anuar and Bukchin (2006) consider that the assem- extensively studied (Sawik 2012; Öztürk et al. 2015;
bly sequence is fully given, and that each station can Michels et al. 2018). In some contexts, parallelism is
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 3

employed if a task exceeds the cycle time in duration (3) Precedence relations must be respected for all prod-
(Becker and Scholl 2009) or as a manner to add addi- ucts that flow through the line;
tional scheduling flexibility to mixed-model lines (Lopes, (4) Only one task can be shared between two stations;
Michels et al. 2019). Parallel stations can be seen as a form (5) Each station can share tasks with either their
of fractional task allocation, i.e. tasks are 50% (assuming upstream or downstream neighbour, but not both at
two simple parallel stations) assigned to each worksta- once;
tions. This means that they tend to have most of the (6) Both stations that share the task can perform it,
allocation flexibilities of task-sharing. However, not all and the task’s duration is constant, regardless of the
contexts are adequate for parallel stations: loss of worker station that performs it.
specialisation, layout complications, and increases in tool
duplication costs tend to be larger for parallel stations Figure 1 presents a precedence diagram and illustrates
than to fractional task allocations. the differences between SALBP and FA-ALBP, as well as
In fact works that consider parallel stations often seek some requirements of the latter. These definitions reflect
to limit or minimise their number (Álvarez-Miranda, a series of feasibility and practical considerations, such
Chace, and Pereira 2020) in order to minimise these as producing a solution that can be straightforwardly
costs. implemented. For instance, allowing stations to share
This paper defines a deterministic fractional alloca- tasks with both the upstream and downstream neigh-
tion assembly line balancing problem in which each sta- bour makes the problem easier to solve (Polynomial time
tion is only allowed to share one task. By doing so, it is for cycle time minimisation) and allows maximum cycle
possible to define analytically the required internal stor- time reduction (Bukchin and Sofer 2011). However, this
age costs for both paced and unpaced lines, without any can also produce confusing scheduling solutions that
simulation requirement (Anuar and Bukchin 2006). would be very impractical to implement. Hence, for each
station, fractional task allocations are limited to either the
previous or the next one. This means that the line can
3. Problem description
be seen as a set of regular stations and task-sharing sta-
The Fractional Allocation Assembly Line Balancing tion blocks. The former are typical of traditional assembly
Problem (FA-ALBP) consists in assigning a set of tasks lines, and always processes the current product within the
T (each with a given duration Dt ) to a set of stations cycle time. The latter consists of two adjacent stations that
S, while respecting the precedence relations Pt for each share a task, meaning the processing time of each station
task. Two problem goals are considered: first, to minimise oscillates between a value higher than CT and another
the line’s cycle time, second, to minimise the line’s space one lower than CT. In average, however, these blocks (and
requirements. its stations) must process one product every cycle time,
In this paper, these objectives are treated as hierar- meaning its oscillations must be compensated by internal
chical in nature, meaning that minimising cycle time storage (buffers or line length). Cyclical scheduling can be
is considered strictly more important than minimising used to validate the block’s capacity to reach the required
space requirements. This leads to a two-stage approach: average cycle time with the available internal storage.
in the first stage, the line’s cycle time is minimised; in the
second, space requirements are minimised, while impos-
4. Proposed MILP model
ing as a constraint cycle time performance obtained by
the first stage. This section presents the proposed mathematical model
In this paper, the number of stations is considered used to describe the studied problem. The employed
given, hence line efficiency is measured in terms of the notation is presented by Table 1. In this section, the model
cycle time CT. Space costs are measured in terms of either describes the cycle time minimisation step.
line length or buffer requirements, depending on the line In order to represent this task-station allocation prob-
control. While tasks are indivisible for each individual lem, three sets of decision variables are employed: xt,s ,
product, tasks can be fractionally assigned to stations in yt,s , and zt,s . Each variable in the first one (xt,s ) is set to 1
the following sense: when task t is fully assigned to station s, meaning it is per-
formed in it for all products. The second one (yt,s ) is set to
(1) The fractional assignment value states the percent- 1 when task t is shared between stations s and s + 1. The
age of products for which the task will be performed third one (zt,s ) states the percentage of products for which
at each station; task t is performed at station s, e.g. z1,2 = 0.5 means that
(2) A task can only be split/shared by two adjacent for 50% of products, task 1 is performed at station 2.
stations; The proposed model for time efficiency maximisation is
4 T. C. LOPES ET AL.

Figure 1. Precedence diagram example and solution examples.

! !
Table 1. Employed notation. s · zp,s ≤ s · zt,s ∀t ∈ T, p ∈ Pt (5)
Parameter Type Description s∈S s∈S
T Set of integers Lists all tasks t
!
Dt Integer Duration of task t (a non-negative Dt · zt,s ≤ CT ∀s ∈ S (6)
integer) t∈T
S Set of integers Lists all stations s !" #
Pt List of integers List of direct predecessors p of each yt,s−1 + yt,s ≤ 1 ∀s ∈ S : s > 1 (7)
task t
t∈T
K Integer Denominator for fractional
allocations zt,s ≥ xt,s ∀t ∈ T, s ∈ S (8)
Variable Type Description
CT Integer Cycle time (a non-negative integer) zt,s ≤ xt,s + yt,s + yt,s−1 ∀t ∈ T, s ∈ S : s > 1 (9)
xt,s Binary Set to 1 if task t is assigned to
station s zt,1 ≤ xt,1 + yt,1 ∀t ∈ T (10)
yt,s Binary Set to 1 if task t is shared between
stations s and s + 1 xt,s , yt,s ∈ {0, 1} ∀t ∈ T, s ∈ S (11)
zt,s Fractional Percentage of products for which
task t is performed at station s, a K · zt,s ∈ Z+ ∀t ∈ T, s ∈ S (12)
fraction with denominator K

The problem’s goal (Expression (1)) is to minimise the

presented by Expressions (1) –(12).
cycle time, as the number of stations is given by hypoth-
esis. Equation (2) states that every task must be either
Minimise CT (1) always performed at a station or shared between a sta-
subject to : tion pair. Constraint (3) states that the sum of fractional
!" # allocations for every task must add up to 100%, i.e. every
xt,s + yt,s = 1 ∀t ∈ T (2) task is performed for every product. Constraint (4) states
s∈S the direct precedence relations requirements: tasks must
!
zt,s = 1 ∀t ∈ T (3) be assigned or shared at a station pair prior to their
s∈S direct successors. Inequality (5) also states precedence
! " # ! " # constraints in terms of the fractional decision variables.
s · xp,s + yp,s ≤ s · xt,s + yt,s Constraint (6) states the cycle time constraint: every sta-
s∈S s∈S tion’s average performance is a potential bottleneck for
∀t ∈ T, p ∈ Pt (4) the line’s performance.
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 5

Inequality (7) states that a station cannot simultane- partitioned between the second and third stations. There-
ously share tasks with both the previous and following fore, the FA-ALBP instance is feasible if and only if the
neighbour, and that only one task can be shared per sta- bi-partition has a solution.
tion. Constraints (8) –(10) logically tie the variable sets x If the number of stations is part of the instance, FA-
and y to z. Expression (11) presents the binary require- ALBP is NP-complete in the strong sense. This is proven
ments for variable sets x and y. Last, Expression (12) based on the fact that the 3-Partition (Garey and John-
states an optional special integer requirement for the oth- son 1979) problem reduces to FA-ALBP. Given $ integers
erwise continuous variable set z: by adding it, z is allowed a1 , . . . , a3·n , b such that b/4 < aj < b/2 and j aj = n ·
to be a fraction of a given integer denominator K. b, the following instance of FA-ALBP can be constructed
For instance, if K = 4, the fractional allocations vari- with 4 · n tasks and 2 · n stations:
ables zt,s can only assume the values 0, 0.25, 0.5, 0.75, and
1. Section 4.2 discusses the relevance of this factor for • CT = 2 · b
each assembly line type. • Dt = at ∀t ∈ {1, . . . , 3 · n}
Regarding implementation by general solvers, this • Dt = 3 · b ∀t ∈ {3 · n + 1, . . . , 4 · n}
constraint can be added using auxiliary integer variables. • Pt = ∅ ∀t ∈ {1, . . . , 4 · n}
Furthermore, upon implementation, pre-processing can
eliminate some variables, by fixing their values as zero: In order for this instance to be feasible, the n large tasks
a valid upper bound on CT allows discarding some of (Dt = 3 · b) must all be shared: their duration exceeds
the xt,s variables using natural adaptations of the earliest cycle time. There are 2 · n stations, each can only share
and latest stations concepts (Gökçen and Erel 1997). Sim- one task with one of its neighbours (either previous or
ilarly, the yt,s variables at the last station s = |S| are always next station). This means only n tasks can be shared,
zero because there is no station s + 1 in this case. If, for therefore, only the n large tasks are shared. This defines n
any practical reason a specific task t cannot be shared, all blocks of two stations with b time available. The instance
the associated yt,s variables should also be set to zero as is feasible if and only if the first 3 · n tasks (integers aj )
well. can be partitioned in blocks of sum b. That is, if and only
if the 3-Partition has a solution.

4.1. Problem’s complexity 4.2. Internal storage cost m inimisation

The studied problem’s complexity depends on the num- The model presented in Section 4 allows to compute
ber of stations. For a fixed number of stations of at least 3, the best cycle time CT ∗ that can be obtained by adding
the problem is at least NP-complete in the weak sense. the fractional task allocation flexibility. This value can
This is proven based on the fact that the bi-partition differ from the optimal cycle time of the equivalent
problem (Hayes 2002) reduces to FA-ALBP with cycle SALBP instance (Chen and Askin 2006; Anuar and
time restriction. Given integers a1 , . . . , an , b such that
$ Bukchin 2006). If that is the case, it is interesting to
j aj = 2 · b, the following instance of FA-ALBP can be investigate the internal storage cost tied to this addi-
constructed with n tasks and 3 stations: tional flexibility. Such storage is needed to compensate
for production rate oscillations of stations in task-sharing
• CT = b blocks. This can be done by solving the balancing prob-
• D 1 = b + a1 lem once again, with an additional constraint tied to
• Dt = at ∀t ∈ {2, . . . , n} cycle time performance (Expression (13)) and a new goal
• P1 = ∅ function that reflects the aforementioned internal storage
• Pt = {1} ∀t ∈ {2, . . . , n} costs.
CT ≤ CT ∗ (13)
The first task precedes all others, therefore, it must
be assigned to the first station. Because its size exceeds These costs are dependent on the assembly line’s control:
cycle time, it must also be shared between the first and for continuous paced lines they mean longer stations,
second stations. This consumes all task-sharing possi- hence a longer line length. These translate to greater
bilities, since the second station cannot simultaneously internal storage because products enter the line at
share tasks with both neighbours. The first task has dura- a constant rate, meaning longer lines (measured in
tion b + a1 , which must be split as follows: b time units time units) mean greater Work-in-Progress. Meanwhile,
are performed at the first station, and a1 at the second. for unpaced asynchronous lines internal storage mean
The remaining tasks with durations a2 , . . . , an must be buffers between stations. These costs are conceptually
6 T. C. LOPES ET AL.

illustrated in Figure 2. The following sections present are performed at each station, the line length increases
goal functions that reflect worst-case bounds for these linearly with the shared task’s duration, as indicated by
space costs for each of these line types. Equation (14).

4.2.1. Line length cost on paced lines L = 2 · CT + F(z) · D (14)

There are multiple variants of paced assembly lines
from a scheduling perspective (Boysen, Fliedner, and The cost factor F is hence a function of the fraction z.
Scholl 2009). In this section, it is assumed that (i) Figure 3(a) presents the results of initial screenings with
products launch is rigidly disciplined (i.e. one prod- multiple values of z, which did not provide a clear growth
uct enters the line every CT time units), and (ii) that or decline pattern.
stations are rigidly separated (i.e. no station overlap is However, a more clear pattern, shown by Figure 3(b),
allowed). These hypotheses reflect ‘default’ assumptions is obtained by plotting F against the irreducible denom-
about paced assembly lines. Furthermore, considering inator dz of the allocation fraction z. For instance, for
them allows analysing the impact of fractional allocations z = 68 , dz = 4. Notice that, because of Constraint (12), dz
in isolation. is at most K.
Under these considerations, it is possible to show that In fact, the pattern observed in Figure 3(b) matches
each task-sharing ‘block’ can be studied independently: the expression Fd = (2 · dz − 2)/dz . This can be proven
by placing boundaries between blocks and regular sta- by tracking the position p in which the worker finishes
tions, it is clear that a product must cross each bound- processing a product on the block’s first station. Figure 4
ary every CT time units (hypothesis (i)). Furthermore, serves as visual support for this proof. After each prod-
because station boundaries are rigid (hypothesis (ii)), uct, the paced nature of the line means the worker walks
the scheduling required within a block does not affect CT time units upstream to reach the next product. If by
neighbouring stations and blocks. This is illustrated by doing that he walks out of his station boundaries, then
Figure 2. This implies that the total line length is the sum idle time occurs. However, this is a worst-case analysis
of lengths of all blocks and stations. in which no idle time is allowed: idle time would imply
The length of regular stations are determined by their violating cycle time because B1 + B2 + D = 2 · CT. This
total processing time, which is given by the sum of tasks means that the finishing position can never be less than
performed in them. This means it is only necessary to CT time units, which can serve as a zero reference point
analyse blocks of adjacent stations that share a task. Let for this analysis. The finishing position changes for each
D state the duration of the task shared in the block, and product by the difference (δ) between cycle time and the
B1 and B2 indicate the ‘base’ time of each station in the processing time of that product, as illustrated by Figure 4.
block, i.e. the time required when they do not perform Furthermore, positive differences for the block’s first sta-
the shared task. In order to define a worst-case scenario tion translate into negative ones for the second station,
for these blocks, it is assumed that the sum of the pro- and vice-versa. This imposes a symmetry in which the
cessing time of tasks assigned to these two stations is length of both station is the same and equal to the cycle
two cycle times (B1 + B2 + D = 2 · CT). This means that time plus a cost tied to the variable part. As suggested
there can be no idle time in these stations and that the by Figure 3(b), this cost should be (K − 1)/K for each
percentage of time the shared task will be performed station (or (2 · K − 2)/K for the block), where K is z’s
at each station is fixed when B1 , B2 and D are given. irreducible integer denominator. This is proven hereafter:
Notice that Constraint (12) requires zt,s to be a fraction First, consider the simpler case in which the shared
of denominator K, meaning that it is possible to define task processing time D is equal to K and cycle time CT
cyclical schedules based on K products. This can be done is an integer. In this case, if the task is assigned n out of K
by defining residual problems of models developed to times to the block’s first station, then n, K and K−n are
describe mixed-model paced lines (Defersha and Mohe- relative primes because K is an irreducible denominator
balizadehgashti 2018). These residual problems will only by hypothesis. If the screening is correct, the cost should
have K binary variables, meaning they are tractable, and equal K−1 for the simpler case. This is true if and only if
can be solved extensively for multiple values of z and D the optimal cyclical schedule of K products matches that
for the purposes of screening the required line length value. By tracking the position in which the last product’s
costs. processing was completed, the cyclical schedule defines a
Preliminary tests indicated that the length of the block walk in integer values such that the difference between
(L = L1 + L2 ) can be stated as twice the cycle time plus two consecutive positions is either +δ + or −δ − . The
a cost that is proportional to the shared task’s duration. highest position equals the station’s length cost, which
This means that, by fixing the percentage of times (z) task should be K−1, based on the preliminary screenings.
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 7

Figure 2. Comparison of internal storage costs for different line controls (T.U. = time units).

Figure 3. Length cost factor F behaviour. (a) As a function of the fraction. (b) As a function of the denominator.

The sufficiency of this value is proven first, by contra- K steps, a repeated position must be reached (Pigeon-
diction: suppose that there is a position p in the walk hole principle). If that repeated position is 0, the result
such that both p + δ + > K − 1 and p − δ − < 0. Because is true. Otherwise, the repetition occurred in less than K
δ + + δ − = K, those inequalities can be re-arranged to steps. This would imply that there is a smaller walk that
show that δ − − 1 < p < δ − , meaning either p or δ − is defines a cyclical schedule with fewer than K products.
not an integer (Figure 4). This is impossible because both However, this is impossible because the relative prime
differences are integer by hypothesis and the walk is a nature of the integers differences (δ + and δ − ) means their
walk on integer numbers. Therefore, it is always possible minimal common divisor is their product which can only
to perform a step and stay within the range [0, K − 1]. be reached with n steps forward (+δ + ) and (K − n) steps
This means that K−1 should be sufficient to define a backward (−δ − ), which total K steps. This is relevant
walk of arbitrary length. Its necessity is proven next: Con- because a cyclical schedule means a walk in integer val-
sider that the starting position of the walk is 0. After K ues such that the sum of movements forward equals the
steps it is possible to return to the initial position. This is sum of movements backward. Therefore, K−1 is both
true because there are K positions in the range and after sufficient and necessary for the cyclical schedule. This
8 T. C. LOPES ET AL.

Figure 4. Scheduling scheme for minimal block length.

result can be easily generalised for other values of D and 4.2.2. Buffer cost on asynchronous lines
fractional values of cycle time. The former follows from In unpaced asynchronous lines, internal storage (buffers)
observing that, for the same allocation fraction z, the δ are commonly used to compensate for temporary dis-
steps are proportional to D (Figure 4). The latter reduces turbances in processing times such as mixed-model pro-
to a case with integer cycle time by multiplying all task duction (Boysen, Fliedner, and Scholl 2008). In this
durations by the cycle time’s denominator. section, the worst-case for the minimum number of
This leads to two conclusions, first, that having lower buffers required by a given fractional task allocation is
denominators in the fractional task allocations lead to analysed. Once again, in order to reach a target cycle
lower costs, which might motivate using a low value for time CT, a cyclical schedule based on K products is used.
K, such as 2 or 4. Second, the length cost of the fractional Similar to paced lines, this analysis is based on defin-
task allocations is bounded between one and two times ing the worst-case for each block of task-sharing stations.
the duration of shared tasks. In order to do so, no intra-station idle time is allowed:
This means that Expression (15) presents a worst-case Neighbouring regular stations have processing times of
MILP formulation for line length cost minimisation step CT time units, and the sum of processing times of station
of FA-ALBP in the case of paced lines. If only fractions pairs in blocks is 2 · CT. This implies that the duration
of up to a denominator K are used, then Expression (16) D of the shared task is necessarily smaller than twice the
can be used instead. cycle time. The analysis is presented in two parts: first on
! ! buffer costs between regular stations and blocks, second
Minimise 2 · Dt · yt,s on buffer costs within and between blocks.
t∈T s∈S (15) Given a balancing solution, for a task-sharing block,
subject to : (2)−(13) the minimal buffer requirements can be derived by defin-
ing a cyclical scheduling and buffer allocation residual
! ! problem. This can be viewed as residual version of a com-
Minimise Fd (K) · Dt · yt,s
bined balancing and buffer allocation problem (Lopes,
t∈T s∈S (16)
Sikora et al. 2019).
subject to : (2)−(13)
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 9

Consider the entry buffer: by hypothesis, it is pre- CT − B1 − " + B1 + D − CT > J · CT (22)

ceded by a regular upstream station. Hence, one product
D > J · CT + " (23)
must enter every CT time units (T.U.), while the block’s
first workstation will take more or less than CT T.U. This means tasks shorter or equal to the cycle time (D ≤
depending on whether it has performed the shared task. CT) require one entry buffer to be shared, and those big-
Naturally, both stations of the block will process, on aver- ger (D > CT) may require two. It is not possible to require
age, one product every CT T.U.. While these oscillations more than two since D ≤ 2 · CT. A symmetrical argu-
imply that at least one unitary buffer is necessary, it is also ment, visually supported by Figure 5, proves the same
possible to show that it will be sufficient under a specific requirement for departure buffers between blocks and
condition (D ≤ CT). The proof of this result is visually regular stations. These are worst-case analysis, meaning
supported by Figure 5, and is based on measuring the for some cases they might not be required.
time each product stays in the entry buffer: the difference Once the worst-case requirements for buffer capac-
between the processing time in the block’s first station is ity between a regular station and a block station is
compensated by the buffer. If processing is longer than defined, it is easy to determine the other two cases: buffer
CT (share task is performed by the block’s first station) requirements between stations of a block and between
the difference equals the increment of time spent in the blocks. Both follow the same argument, hereafter pre-
buffer for the next product. Conversely, lower processing sented for the intra-block case: Add a dummy regular
times than CT (shared task not performed by the block’s station between each station of the block. In the worst-
first station) will demand products earlier from the buffer, case, this imposes a buffer requirement of capacity J
leading to a decrease of the time spent in the buffer by the between the regular station and each of the block’s sta-
next product. tions. This means that 2 · J buffers are sufficient within
Let δ + and δ − as the differences between CT and the block: any schedule defined using the dummy regu-
the long and short processing times, respectively. Let wp lar station remains feasible when it is removed because it
indicate the time product p spent in the buffer. These val- moves products regularly every CT T.U., meaning when
ues must be positive, as negative values would indicate one departs it, the next one enters. As mentioned before
insufficient buffer capacity. Furthermore, their maximum J is either one or two, depending on the tasks duration
value dictates the minimal buffer capacity requirements: when compared to CT. In the particular case of two adja-
because products are feed by the upstream station every cent blocks, this argument leads to the conclusion that
CT T.U., if the maximum time products stay in the sta- the worst-case requirements for buffers between them is
tion is J · CT (where J is an integer) then a buffer with the sum of two requirements: that between the first block
capacity J is sufficient. Expression (17) states how wp+1 and a regular station and that between a regular station
can be computed in function of wp and the information and the second block. Hence, the cost of adjacent blocks
about whether the first station performed the shared task add up in the worst-case.
or not. From this scheduling rule, it is easy to infer the A particular case warrants further exploring, namely
feasibility condition expressed by Expression (18). that in which a task is evenly shared between stations,
i.e. the 50–50 case. Because of its particular regularity, it
wp+1 = wp − δ − or wp+1 = wp + δ + (17) is always possible to define schedules that require fewer
− +
wp − δ ≥ 0 or wp + δ ≤ J · CT (18) buffers than the other fractional allocations do. Figure 6
presents an example of a cyclical scheduling between a
In order to determine the worst-case requirements of block and two adjacent regular stations that (i) has a long
buffer capacity, we try to violate this feasibility condition, task (D > CT), (ii) does not require intra-block buffers,
as stated by Expression (19). The first part can be turned and (iii) requires only one buffer between each regular
into an equality, by adding a positive value ", as stated by station and the block (J = 1).
Expression (20). This allows wp to be replaced in the sec- Lastly, if a task is shared between the first and sec-
ond part (Expression (21)). Further replacing the values ond station in the line, then that block does not require
of δ + and δ − by functions of CT, D and the base time of an input buffer. The same argument holds for the last
the block’s first station (B1 ) leads to Expression (22). Its two stations of the line and an output buffer. This is
terms can be rearranged into the condition that implies J namely because it is commonly considered that the first
buffers are insufficient, i.e. Expression (23). station is never starved and the last one is never blocked
wp − δ − < 0 and wp + δ + > J · CT (19) (Scholl 1999).
− This means that Expression (24) presents a worst-case
wp = δ − " (20) MILP formulation for line buffer cost minimisation step
δ − − " + δ + > J · CT (21) of FA-ALBP in the case of unpaced lines. In it, the cost
10 T. C. LOPES ET AL.

Figure 5. Scheduling scheme for time products stay in buffers.

Figure 6. Cyclic scheduling for a task sharing block between two regular stations.
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 11

Table 2. Values of Gt,s in function of station s and task t. for both paced and unpaced lines as L-cost and B-cost,
General case 50–50 Case respectively. B-costs state the number of required buffers,
Fraction a straightforward cost. In order to more adequately com-
station s Middle Begin/end Middle Begin/end
pare paced to unpaced lines, L-cost states the normalised
Dt ≤ CT 4 3 2 1
Dt > CT 8 6 2 1
line length cost: Products enter the line every CT time
units, meaning this is the temporal length of a regu-
lar workstation (Thomopoulos 1968). This means that
parameter Gt,s assumes the discrete values presented in dividing the line length cost (which is measured in time
Table 2. units by Expression (16)) by CT informs a normalised
line length cost (e.g ‘1.5 products’) that can be directly
!! compared to the buffer cost (e.g. ‘buffers with capacity for
Minimise Gt,s · yt,s 2 products’).
t∈T s∈S (24) For each number of stations and value of K, three
subject to : (2)−(13) MILP models are solved: The first minimises cycle time
and defines the performance requirement value CT ∗ for
the latter two. The second minimises the line length cost
5. Experiments and results
(L-cost) required by a paced line to meet the perfor-
The proposed models were tested in three complemen- mance requirement. The third minimises the buffer cost
tary experiments: First, Section 5.1 presents an illustra- (B-cost) required by an asynchronous line to meet the
tive and motivating example for a specific instance of the same performance requirement.
classical assembly line balancing dataset (Scholl 1999). Table 3 shows that the flexibility FA-ALBP allows is
Second, Section 5.2 presents a screening on 1050 often capable of realising all the improvement poten-
instances of a more recent extended dataset Otto, Otto, tial of the associated SALBP instance, i.e. the difference
and Scholl (2013). Lastly, Section 5.3 presents a case between its CT ∗ and the previously mentioned trivial
study in which the core studied concepts are applied to lower bound, LB. For some combinations of parameters,
industrial data. however, this potential will be small or inexistent (nine
The first experiment discusses in detail the advantages stations). Furthermore, it is noticeable that higher val-
and trade-offs of the flexibility afforded by the fractional ues of K allow greater cycle time reduction for some
allocations. The second inquires on how specific instance cases, although they also require higher internal stor-
parameters affect the aforementioned trade-offs. age costs. Lastly, paced lines seem to require generally
The third one discusses how to adapt the formulation lower space costs to realise the cycle time improvement
to mixed-model lines as well as insights on the relevance potential afforded by the fractional allocations.
of demand stability for the solutions’ performance. All Figure 7 presents a visual comparison between SALBP
MILP models were solved using Gurobi 9.0 on a Core and FA-ALBP in regards to feasible values of cycle time.
i7-8700 CPU (3.2 GHz, 6 CPUs, 12 threads) with 32 GB Notice that for some numbers of stations, the FA-ALBP
RAM and a 300 second time limit. performs as well as (and even better than) SALBP with
one full additional station. This is particularly interesting
as CT reductions and requiring fewer stations to reach the
5.1. Illustrative example
same CT translate to continuous monetary returns, while
The Gunter instance was chosen from the Scholl (1999) the line length and buffer costs that are required for the
dataset for the following reasons: First, it’s optimal FA-ALBP solution are essentially one-time investments.
SALBP-2 solutions$ differed significantly from the triv-
ial lower bound (( t Dt /|S|)) for multiple numbers of
5.2. Screening
stations. Second, it is an instance that originates from a
practical case study, meaning it is representative rather Additional tests on 1050 instances were performed in
than randomly generated. order to verify more general trends about the problem
The FA-ALBP models were applied to this instance and the relevance of its parameters, in particular ordering
with all benchmark number’s of stations (7–14) and with strength (how restrictive precedence relations are) and
three values of K (2, 12, and ∞). Table 3 presents the opti- task duration distributions. Otto, Otto, and Scholl (2013)
mal cycle time value (CT ∗ ) for each instance,$ and com- provided systematically generated instances for simple
pares it to the trivial lower-bound (LB = ( t Dt /|S|)). assembly line balancing, which were used for this screen-
The internal storage costs required to realise the cycle ing. Instances were first solved for SALBP-2 with a fixed
time differences to the SALBP solutions is presented number of stations. The equivalent FA-ALBP instances
12 T. C. LOPES ET AL.

Table 3. Results for the Gunther instance.

SALBP FA-ALBP K = 2 FA-ALBP K = 12 FA-ALBP K → ∞
Stations CT ∗ LB CT ∗ L-cost B-cost CT ∗ L-cost B-cost CT ∗ L-cost B-cost
7 72 69 70 0.57 1 70 1.14 4 69 1.71 7
8 63 61 62 0.37 2 61 1.31 3 61 0.75 3
9 54 54 54 0 0 54 0 0 54 0 0
10 50 49 49 0.1 2 49 0.2 3 49 0.2 3
11 48 44 45 0.42 1 45 0.84 3 44 1.73 11
12 44 41 42 0.33 1 42 0.66 3 42 0.66 3
13 42 38 40 1.55 3 40 3.1 10 39 6.77 25
14 40 35 38 3.84 8 37 3.11 22 36 7.66 30

Figure 7. Feasible cycle time comparison between SALBP and FA-ALBP for the Gunther instance.

were then solved with a cycle time minimisation objec- Tables 4 and 5 present the results for small and
tive (Expressions (1)–(12)) so that the obtained FA-ALBP medium instances, respectively: average time required
cycle times can be compared to SALBP ones. Two fur- (in seconds) per instance is informed. The cycle time
ther executions of the FA-ALBP model used the obtained differences are described in three terms: the average the-
cycle time as a constraint, and employed the described oretical potential (avg. Theo.) compares $ the obtained
internal storage minimisation goals for paced (Expres- SALBP cycle time to the lower bound (( t Dt /|S|)); the
sions (16) and (2)–(12)) and unpaced lines (Expres- average realised potential (avg. Real.) means the average
sions (24) and (2)–(12)). All FA-ALBP instances set difference between cycle times obtained for SALBP and
K = 2. Furthermore, the CT minimisation FA-ALBP run FA-ALBP as a percentage of the SALBP’s cycle time. The
used SALBP’s answer for warmstarts, and the space cost best case column (Best Real.) presents the highest such
minimisation FA-ALBP runs used the CT minimisation percentage value. Internal storage costs are informed as
FA-ALBP one. average increases in line length compared to the line’s
base length (7 for small instances and 15 for large ones).

Table 4. Screening results for small instances (20 tasks 7 stations; CPU times in seconds).
FA-ALBP CT Difference Avg. costs (%)
Parameter SALBP
OS/dist(Dt ) Time CT time L time B time Avg. Theo. Avg. Real. Best Real. L-cost B-cost
0.2 0.8 26.5 33.9 28 2.0% 1.4% 15.1% 9.9% 42.9%
0.6 0.1 3.9 2.1 1.8 3.6% 2.1% 9.9% 9.4% 40.1%
0.9 0.1 0.9 0.1 0.1 8.2% 3.9% 17.2% 8.1% 33.7%
PB 0.3 7.6 9.3 7.6 3.4% 1.9% 9.9% 9.4% 39.6%
PM 0.7 26 30.7 23.8 3.5% 1.9% 7.9% 8.9% 39.4%
BM 0.2 5.9 6.3 7.1 3.9% 2.3% 17.2% 9.6% 40.3%

Table 5. Screening results for medium instances (50 tasks, 15 stations; CPU times in seconds).
FA-ALBP CT Difference Avg. costs (%)
Parameter SALBP
OS/dist(Dt ) Time CT time L time B time Avg. Theo. Avg. Real. Best Real. L-cost B-cost
0.2 298.7 300 14.3 14.7 0.7% 0.0% 3.4% 0.2% 0.9%
0.6 197.9 300 103.1 100.6 1.4% 0.3% 20.5% 2.4% 14.1%
0.9 8.1 64.2 68.2 55.2 7.0% 3.7% 9.2% 1.7% 8.6%
PB 202.4 262 47.9 48.3 1.9% 0.7% 20.5% 1.7% 8.6%
PM 248.7 276 60.1 54.1 1.8% 0.5% 5.7% 1.1% 6.7%
BM 191 261 72 69.6 2.0% 0.8% 9.2% 2.4% 12.4%
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 13

For paced lines, the line length cost (L-cost) is normalised

by dividing it by the cycle time (Thomopoulos 1968), so
that the increase can be measured in number of stations.
For unpaced lines, buffers are considered to be equiva-
lent in size to stations for the purposes of the buffer cost
(B-cost) measure.
In each line of Table 4 the results are presented
for the subset of instances with the specified parame-
ter (Otto, Otto, and Scholl 2013). The first three lines
divide instances in terms of order strength (OS), i.e.
how restrictive the precedence diagram is. The following
three separates instances in terms of their task duration
distributions (dist(Dt )): peak at the bottom (PB), peak
in the middle (PM), and bimodal (BM). It is apparent
that higher OS translates to both higher theoretical and
realised cycle time differences. However, this is a general
tendency and not a guarantee as illustrated by the 15.1% Figure 8. Realised cycle time reduction versus available
best case with OS = 0.2. The task duration distribution, potential.
however, appears to be less relevant for the difference
between SALBP and FA-ALBP cycle times.
It is also noticeable that FA-ALBP is more compu- bounded by its potential. The figure suggests that (for
tationally costly than SALPB, as shown by the average K = 2) around two thirds (y = 23 x, R2 = 0.81) of the
time required to solve the small instances to optimal- available potential (difference between SALBP’s CT and
ity. Furthermore, the average space cost associated to the a perfect division) is realised. Furthermore, this benefit
cycle time reduction does not seem proportional to it seems easier to extract for SALPB instances with higher
and its average behaviour seems insensitive to instance potential.
parameters. Lastly, Figure 9 describes in more detail the internal
The medium cases are noticeably more difficult, with storage costs of the realised cycle time reductions for
whole subsets of instances failing to reach optimal- paced lines (Figure 9(a)) and unpaced ones (Figure 9(b)).
ity proofs within the time limit. It is also noticeable It is apparent that, while higher cycle time reductions
that, in average, the cycle time reduction was smaller tend to imply higher costs, the correlation is rather weak.
with many instances reporting no difference (similarly It is also important to notice that storage costs are mostly
to the case study with nine stations, see Figure 7). one-time investments and only part of the total costs of
This is mostly attributable to the lower observed poten- running the assembly line, while cycle time reductions
tial, which seems to emerge from the greater flexibil- reflect on continuous performance improvements, mean-
ity of medium instances (50 tasks) when compared to ing that a 20% longer line for a 10% cycle time reduction
smaller ones (20 tasks). However, under high prece- can be a very favourable trade-off. In terms of line pace
dence constraints (OS = 0.9), similar results to the small comparison, paced lines tend to require much smaller
cases were obtained. Furthermore, the best case for costs than unpaced ones to realise the same cycle time
medium instances presented higher realised CT differ- reductions. This, however, depends on the assumption
ence (20.5%) than the small ones (17.2%). Task distribu- that buffers are equal stations in size, which is reasonable
tions do not appear to be any more relevant for medium for final lines in the automobile industry, but may not be
instances than they were for previously, and average space the case for smaller products such as electronics devices
costs also seem mostly unaffected by parameters, except – for which (even ‘infinite’) buffers can be substantially
for low OS. However, this is easily explained: medium smaller than stations.
instances with low OS often produced solutions with the
same value of CT as the SALBP equivalent, meaning that
5.3. Application to practical data
no buffers or additional line lengths in comparison to
SALBP is required. This section describes the results obtained by the pro-
The relationship between realised potential and the- posed mathematical formulation when applied to data of
oretical potential is further elucidated by Figure 8, in a practical industrial case. The instance data describes
which each instance is translated to a semi-transparent a car seat assembly line dedicated to the manufacture
point. Naturally, the realised cycle time reduction is of two product models: a simpler high-demand one,
14 T. C. LOPES ET AL.

Figure 9. Realised cycle time versus required internal storage cost. (a) Paced lines. (b) Unpaced lines.

Figure 10. Processing times for each balancing solution. (a) Cyclical scheduling benchmark. (b) Fractional allocation.

and a more complex one with lower demand. The line Section 4’s model, as presented by Expressions (25)–(27).
is asynchronous unpaced, has seven workstations as In it, M is the set of product models (in this case, M =
well as physical space available for two unitary buffers {1, 2}), Constraint (26) is the adapted version of Con-
(Bmax = 2). This line was first studied in the context of straint (6): each task t is modelled as having a specific
cyclical scheduling (Lopes, Sikora et al. 2020) – which duration Dt,m for each product model m. If a task does
requires stable demands. The present paper described not exist for a product model, its duration is set as zero.
fractional allocations for single model assembly lines, Constraint (27) states the buffer resource limit. In this
therefore, some adaptations were required for the present case study, K = 2 was used because it offers a reasonable
case study. First, each product model m is modelled as trade-off between cycle time reduction, space require-
having its own cycle time CTm . Second, models have ments and implementation simplicity. In this case study,
expected relative demand Om , which must sum to 100%. expected relative demands are, approximately, of 83% and
This case study discusses what happens if these demands 17% for product models 1 and 2, respectively – 5 units
are not stable. Third, the throughput of a line with frac- of the first product model per unit of the second one,
tional task allocations is measured as a weighted average similarly to Lopes, Sikora et al. (2020).
of these model-wise cycle times. Finally, task allocations
are required to be the same for both product models,
in order to maintain the benefits of worker specialisa- !
tion. Data required to reproduce this case study is made Minimise Om · CTm (25)
available as this paper’s supplementary material. m∈M
This allows a mixed-model version of the proposed subject to :
formulation to be defined using most of the constraints of
Constraints (2)−(5), (7)−(12)
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 15

Table 6. Performance comparison for multiple demand scenarios.

Cyclical scheduling Fractional allocations
Relative
Demand perfor-
scenario Avg. CT Theo. Eff. Avg. CT Theo. Eff. mance
100–0% 1316 96.2% 1276 99.2% 103.1%
90–10% 1349.5 96.8% 1345.9 97.1% 100.3%
83–17% 1372 97.2% 1392.5 95.7% 98.5%
80–20% 1412.6 95.3% 1415.8 95.1% 99.8%
70–30% 1537.9 90.2% 1485.7 93.3% 103.5%
60–40% 1667.2 85.6% 1555.6 91.7% 107.2%
50–50% 1792.5 81.9% 1625.5 90.3% 110.3%
40–60% 1921.8 78.5% 1695.4 88.9% 113.4%
30–70% 2051.1 75.5% 1765.3 87.7% 116.2%
20–80% 2180.4 72.8% 1835.2 86.6% 118.8%
10–90% 2309.7 70.5% 1905.1 85.5% 121.2%
0–100% 2439 68.4% 1975 84.5% 123.5%

!
Dt,m · zt,s ≤ CTm ∀s ∈ S, m ∈ M (26) these formulations in terms of their average cycle time
t∈T values (Avg. CT), as well as their theoretical efficiency
!! (Theo. Eff.), i.e. comparison to a simple division of total
Gt,s · yt,s ≤ Bmax (27) task time by the number of stations. Lastly, the solu-
s∈S t∈T tions’ relative performance is computed by dividing their
The balancing solution obtained using this formulation average cycle times.
is compared to that obtained by a recent simultane- Notice that, on the one hand, the benchmark out-
ous balancing-sequencing-buffer allocation one (Lopes, performs the fractional task allocations solution for the
Sikora et al. 2019), using the same buffer limit. This original or ‘expected scenario’ (highlighted in italic), as
benchmark is hereafter referred to as ‘Cyclical Schedul- well as for the neighbouring 80–20% one. On the other
ing’. These model-wise processing ties of these solutions hand, the cyclical scheduling benchmark is outperformed
are presented by Figure 10. In it, the darker bars repre- for both product models individually ( 100–0% and
sent product model one, and the lighter ones represent 0–100% scenarios), as well as all other demand scenarios.
product model two. In Figure 10(b), the second and third Indeed, the benchmark’s solution performance is contin-
stations have have two processing times for each prod- gent on the stability of demands. This leads to increas-
uct model – representing the cases in which the shared ingly poorer performance the more realised demands
task is and is not performed at that station. For those differ from the expected ones. Furthermore, the worst
stations, the model-wise cycle time is bounded by the relative performance by the fractional allocations formu-
average between the high and low values. Consequently, lation was 98.5% (1.5% worse), while its highest relative
Figure 10(b) presents lower model-wise cycle time val- performance was over 20% better than the benchmark.
ues than Figure 10(a). However, this better performance This suggests that fractional task allocations can lead to
is associated to processing time oscillations that require more robust solutions in the context of mixed-model
a model-wise cyclical scheduling to be realised. The lines.
buffer allocations for each solution also differ: for the
benchmark, single unitary buffers are optimally assigned
6. Discussions and conclusions
after stations one and two. Meanwhile the fractional task
allocations solution assigns buffers to after stations one This paper questions the assumption of the binary nature
and three. of task-station assignments in assembly line balancing
The solutions’ performances are compared by consid- problems. While other works had addressed some aspects
ering multiple realised demand scenarios that differ from of what amounts to adjacent stations ‘sharing tasks’,
the expected scenario ( 83–17%). For both formulations, none had analytically investigated the internal storage
the balancing solution is fixed and its average cycle time costs required to realise the cycle time reduction poten-
(Avg. CT) is computed for each realised demand sce- tial. A mathematical model for the Fractional Allocation
nario. For the fractional allocations solution, the perfor- Assembly Line Balancing Problem (FA-ALBP) is pre-
mance is measured as a weighted average of the model- sented, with three variants: one that seeks to minimise
wise cycle times. For the cyclical scheduling benchmark, the line’s cycle time, and two that seek to minimise the
an additional residual cyclical sequencing and scheduling internal storage required to realise a given cycle time
problem is solved. Table 6 compares the performance of value.
16 T. C. LOPES ET AL.

Line length is the cost metric for paced lines; on the case of paced lines, these costs are trivially proportional
other hand, buffer requirements is the cost metric for (WIP) or equal (TIS) to the line length cost measured
asynchronous unpaced ones. These costs are determined in time units. For unpaced lines, the WIP and TIS costs
using worst-case analysis for both types of line control. In can easily be shown to equal those of paced lines with the
both cases, these costs are shown to be functions of the same balancing solution.
shared task’s duration and of the allocation fraction, in With minor adaptations, the proposed methodology
particular its irreducible integer denominator (contrary was also applied to industrial data of a mixed-model
to previously hypothesised by Bukchin and Sofer (2011)). assembly line. The resulting solution offered better cycle
For paced lines, line costs are continuous and propor- time performance than a previous cyclical scheduling
tional to the shared task’s duration. For unpaced ones, benchmark solution for both product models. The result-
the buffer requirements are discrete, they depend on ing line balancing also lead to better performance the
task’s duration relative to the cycle time, on whether more realised demands differ from the expected ones.
the allocation fraction is 1/2 (K = 2) or not, and on That was achieved with the simplest possible sharing
whether the assignment happens on the first/last stations (50–50%) of a single task.
or not. The following key managerial insights can be drawn
This paper shows that for specific instances, fractional from the present work: fractional allocations are a per-
allocations allow lower cycle times with the same num- formance enhancing possibility tied to an internal storage
ber of stations or the same cycle time with fewer stations cost trade-off. They can be seen as an alternative to par-
than what is possible with SALBP. Furthermore, con- allel stations with some advantages tied to the fact that
trary to the base problem, the longest task is not a bound only one task is shared: Regarding worker training, they
on cycle time, meaning that lower values of cycle time require less and are also tied to less specialisation losses.
are possible for FA-ALBP than SALBP even when the Regarding physical structure, they require fewer layout
latter has unlimited stations. Increasing the fractional changes, as well as less tool duplication costs, specially
allocation’s maximum integer denominator K can allow for asynchronous lines. The main disadvantage of frac-
greater reductions, but is also associated with higher tional allocations are the internal storage costs, which are
internal storage costs and more complex cyclical schedul- tied to greater work-in-progress and time-in-system than
ing. The most adequate value for K can, therefore, depend the parallel stations alternative. Furthermore, while this
on instance and context-specific managerial preferences, paper focuses on single model assembly lines, the indus-
although the smallest value of K = 2 seems to offer a trial data case study suggests that fractional allocations
simple and effective compromise. can also be useful for mixed-model lines. Indeed, the
This difference in cycle time is not, however, guar- case’s balancing solutions was remarkably more robust
anteed to exist. Screening on a 1050-instance dataset regarding demand fluctuations.
showed that for many instances, SALBP optimal solu- Finally, FA-ALBP is shown to be at least either weakly
tions are close to a perfect division of tasks’ durations or strongly NP-complete, depending on how the num-
amongst stations. However, some instances lead to cycle ber of stations scales with instance size. This means that
time reductions as high as 20%. Experiments suggest larger instances might be intractable for generic solvers:
that this difference tends to be larger for more restric- experiments suggest that just the cycle time minimisa-
tive instances (precedence diagrams with high order tion effort tends to be significantly harder than SALBP.
strength), and that the distributions of task durations is Indeed, a drawback of the proposed mathematical model
not an as relevant factor. In terms of the internal stor- is its difficulty in solving larger size instances. Consid-
age cost required to realise these cycle time differences, ering that a follow-up step of internal storage cost min-
paced lines tend to outperform their unpaced counter- imisation is also desirable, further works should seek
parts assuming that buffers are similar in size to stations to adapt effective SALBP (meta)-heuristic procedures
for the latter. The required storage costs vary signifi- or exact solution methods, such as branch, bound and
cantly on an instance by instance basis. However, these remember (Li, Kucukkoc, and Tang 2020), for FA-ALBP
are mostly one-time investments and cycle time reduc- in order to produce high quality solutions for larger
tions represent continuous gains. This suggests fractional instance sizes. Another direction for further works is
allocations can be an interesting alternative to increase exploring in more detail work-sharing on mixed-model
performance: contrary to increasing the number of work- lines. The industrial case study highlighted robustness
stations, internal storage usually has relatively low con- against demand uncertainty. However, more research
tinuous operating costs. Such indirect costs tied to inter- can investigate adequate throughput performance met-
nal storage such as Work in Progress (WIP) and Time in rics and the explicit incorporation of mixed-model
System (TIS) can be analysed for both line types: In the sequencing.
 INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 17

Disclosure statement References

No potential conflict of interest was reported by the author(s). Ahn, Hyun-soo, and Rhonda Righter. 2006. “Dynamic Load
Balancing with Flexible Workers.” Advances in Applied Prob-
ability 38(3): 621–642.
Funding Álvarez-Miranda, Eduardo, Sebastián Chace, and Jordi Pereira.
The authors thank the financial support from CNPq [grant 2020. “Assembly Line Balancing with Parallel Workstations.”
number 307211/2017-7] and Coordenação de Aperfeiçoa- International Journal of Production Research. doi:10.1080/
mento de Pessoal de Nível Superior – Brasil (CAPES) – Finance 00207543.2020.1818000.
Code 001. This work has also been partially supported by Álvarez-Miranda, Eduardo, and Jordi Pereira. 2019. “On the
the Frech program Agence Nationale de la Recherche, LabEx Complexity of Assembly Line Balancing Problems.” Com-
PERSYVAL-Lab [grant number ANR-11-LABX-0025-01]. puters and Operations Research 108: 182–186.
Anuar, Rouie, and Yossi Bukchin. 2006. “Design and Operation
of Dynamic Assembly Lines Using Work-sharing.” Inter-
national Journal of Production Research 44 (18–19): 4043–
Notes on contributors
4065.
Thiago Cantos Lopes holds a degree in Battaïa, Olga, and Alexandre Dolgui. 2013. “A Taxonomy of
Mechanical Engineering from the Fed- Line Balancing Problems and Their Solution Approaches.”
eral University of Technology – Paraná International Journal of Production Economics 142 (2):
(UTFPR). He also holds a master’s degree 259–277.
from the Graduate Programme in Electri- Baybars, Ilker. 1986. “Survey of Exact Algorithms for the Simple
cal and Computer Engineering (CPGEI) Assembly Line Balancing Problem.” Management Science 32
at UTFPR. He is currently a Ph.D. candi- (8): 909–932.
date at the same programme. His research Becker, Christian, and Armin Scholl. 2009. “Balancing Assem-
involves applications of Operational Research techniques such bly Lines with Variable Parallel Workplaces: Problem
as mixed-integer linear programming to industrial optimisa- Definition and Effective Solution Procedure.” European Jour-
tion problems, particularly those tied to assembly lines. nal of Operational Research 199 (2): 359–374.
Boysen, Nils, Malte Fliedner, and Armin Scholl. 2007. “A Clas-
Nadia Brauner is Full Professor of Opera-
sification of Assembly Line Balancing Problems.” European
tions Research at Grenoble Alpes Univer-
Journal of Operational Research 183 (2): 674–693.
sity (France). She is Ph.D. and Dr. habil.
Boysen, Nils, Malte Fliedner, and Armin Scholl. 2008. “Assem-
in computer science in 1999 and 2005
bly Line Balancing: Which Model to Use When?” Interna-
respectively. Her research focuses mainly
tional Journal of Production Economics 111 (2): 509–528.
on theoretical and practical scheduling
Boysen, Nils, Malte Fliedner, and Armin Scholl. 2009. “Sequenc-
problems and the practical applications of
ing Mixed-model Assembly Lines: Survey, Classification and
combinatorial optimisation in Operations
Model Critique.” European Journal of Operational Research
Research. She was president of the French OR society, Roadef.
192 (2): 349–373.
She was the director of the Master programme in computer Sci-
Bukchin, Yossi, and Tal Sofer. 2011. “Bi-directional Work Shar-
ence and of the master and PhD programmes in OR in Greno-
ing in Assembly Lines with Strict and Flexible Assembly
ble. She is responsible for OR and Combinatorial Optimisation
Sequences.” International Journal of Production Research 49
courses in the Computer Science and Applied Mathematics
(14): 4377–4395.
programmes at Université Grenoble Alpes. She is deputy direc-
Bukchin, Yossi, and Efrat Wexler. 2015. “The Effect of Buffers
tor of the French OR Research Groupe in Operations Research,
and Work-Sharing on Makespan Improvement of Small
GDR RO.
Batches in Assembly Lines Under Learning Effects.” IIE
Leandro Magatão holds a degree in Elec- Transactions 48 (5): 403–414.
trical Engineering with emphasis on Elec- Chen, Jiaqiong, and Ronald G. Askin. 2006. “Throughput
tronics and Telecommunications from Maximization in Serial Production Lines with Workshar-
Federal University of Technology – Paraná ing.” International Journal of Production Economics 99(1–2):
(UTFPR). He holds a Master’s and a 88–101.
Ph.D. degree at the Graduate Programme Dagkakis, Georgios, Anna Rotondo, and Cathal Heavey.
in Electrical and Computer Engineering 2019. “Embedding Optimization with Deterministic Dis-
(CPGEI) of UTFPR. He is currently an crete Event Simulation for Assignment of Cross-trained
Associate Professor at UTFPR. His lines of research involve Operators: An Assembly Line Case Study.” Computers and
approaches based on Mixed Integer Linear Programming, Con- Operations Research 111: 99–115.
straint Logic Programming and integration between combina- Defersha, Fantahun M., and Fatemeh Mohebalizadehgashti.
torial optimisation techniques. 2018. “Simultaneous Balancing, Sequencing, and Worksta-
tion Planning for a Mixed Model Manual Assembly Line
Using Hybrid Genetic Algorithm.” Computers and Industrial
ORCID Engineering 119: 370–387.
Thiago Cantos Lopes http://orcid.org/0000-0003-3541-2788 Garey, Michael R., and David S. Johnson. 1979. Computers and
Nadia Brauner http://orcid.org/0000-0002-2890-4509 Intractability: A Guide to the Theory of NP-Completeness, 338
Leandro Magatão http://orcid.org/0000-0002-6917-9753 pp. New York: W. H. Freeman.
18 T. C. LOPES ET AL.

Gökçen, Hadi, and Erdal Erel. 1997. “A Goal Program- Assembly Lines: Combining Balancing, Sequencing, and
ming Approach to Mixed-model Assembly Line Balancing Buffer Allocation.” International Journal of Production
Problem.” International Journal of Production Economics 48: Research 58 (2): 615–630.
177–185. Lopes, Thiago Cantos, Celso Gustavo Stall Sikora, Adalberto
Grzechca, W., and L. R. Foulds. 2015. “The Assembly Line Sato Michels, and Leandro Magatão. 2020. “Mixed-Model
Balancing Problem with Task Splitting: A Case Study.” IFAC- Assembly Line Balancing with Given Buffers and Prod-
PapersOnLine 48 (3): 2002–2008. uct Sequence: Model, Formulation Comparisons and Case
Gultekin, Hakan. 2012. “Scheduling in Flowshops with Flexible Study.” Annals of Operations Research 286: 475–500.
Operations: Throughput Optimization and Benefits of Flex- Michels, Adalberto Sato, Thiago Cantos Lopes, Celso Gus-
ibility.” International Journal of Production Research 140 (2): tavo, Stall Sikora, and Leandro Magatão. 2018. “The Robotic
900–911. Assembly Line Design (RALD) Problem: Model and Case
Hayes, Brian. 2002. “The Easiest Hard Problem.” American Studies with Practical Extensions.” Computers and Industrial
Scientist 90 (2): 113–117. Engineering 120: 320–333.
Jeong, In-Jae, and Sumin Jeon. 2020. “Balanceability of a Work- Otto, Alena, Christian Otto, and Armin Scholl. 2013. “System-
sharing Line Using Floating Workers and Its Comparison atic Data Generation and Test Design for Solution Algo-
with Floating Work Strategy.” International Journal of Pro- rithms on the Example of SALBPGen for Assembly Line
duction Research. doi:10.1080/00207543.2020.1795291. Balancing.” European Journal of Operational Research 228
Li, Zixiang, Ibrahim Kucukkoc, and Qiuhua Tang. 2020. (1): 33–45.
“A Comparative Study of Exact Methods for the Simple Öztürk, Cemalettin, Semra Tunali, Brahim Hnich, and Arslan
Assembly Line Balancing Problem.” Soft Computing 24: Örnek. 2015. “Cyclic Scheduling of Flexible Mixed Model
11459–11475. Assembly Lines with Parallel Stations.” Journal of Manufac-
Lopes, Thiago Cantos, Adalberto Sato Michels, Ricardo Lüders, turing Systems 36 (3): 147–158.
and Leandro Magatão. 2020. “A Simheuristic Approach Pasupa, Thanatat, and Sadami Suzuki. 2019. “Impact of Work-
for Throughput Maximization of Asynchronous Buffered sharing on the Performance of Production Line with Hetero-
Stochastic Mixed-model Assembly Lines.” Computers and geneous Workers.” International Journal of Industrial Engi-
Operations Research 115: 104863. neering and Management10 (4): 284–302.
Lopes, Thiago Cantos, Adalberto Sato Michels, Celso Gustavo Sawik, Tadeusz. 2012. “Batch Versus Cyclic Scheduling of Flex-
Stall Sikora, and Leandro Magatão. 2019. “Balancing and ible Flow Shops by Mixed-integer Programming.” Interna-
Cyclical Scheduling of Asynchronous Mixed-model Assem- tional Journal of Production Research 50 (18): 5017–5034.
bly Lines with Parallel Stations.” Journal of Manufacturing Scholl, Armin. 1999. Balancing and Sequencing Assembly Lines.
Systems 50: 193–200. 2nd ed. Heidelberg: Physica.
Lopes, Thiago Cantos, Adalberto Sato Michels, Celso Gus- Schonberger, Richard. 1982. Japanese Manufacturing Tech-
tavo Stall Sikora, Rafael Gobbi Molina, and Leandro Mag- niques: Nine Hidden Lessons in Simplicity. New York, NY:
atão. 2018. “Balancing and Cyclically Sequencing Syn- Free Press.
chronous, Asynchronous, and Hybrid Unpaced Assembly Shtub, Avraham. 1993. “Increasing Efficiency of Assembly
Lines.” International Journal of Production Economics 203: Lines Through Computer Integration, Dynamic Balancing
216–224. and Wage Incentive.” Computer Integrated Manufacturing
Lopes, Thiago Cantos, Giuliano Vidal Pastre, Adalberto Sato Systems 6(4): 273–277.
Michels, and Leandro Magatão. 2020. “Flexible Multi- Thomopoulos, Nick T. 1968. “Some Analytical Approaches to
manned Assembly Line Balancing Problem: Model, Heuris- Assembly Line Problems.” The Production Engineer 47 (7):
tic Procedure, and Lower Bounds for Line Length Minimiza- 345–351.
tion.” Omega 95: 102063. Yang, Caijun, Jie Gao, and Jinlin Li. 2014. “Balancing
Lopes, Thiago Cantos, Celso Gustavo Stall Sikora, Adal- Mixed-model Assembly Lines with Adjacent Task Duplica-
berto Sato Michels, and Leandro Magatão. 2019. “An tion.” International Journal of Production Research 52 (24):
Iterative Decomposition for Asynchronous Mixed-model 7410–7427.