Tsung-Chyan Lai
email: tclai@hrbeu.edu.cn

Yuri N Sotskov
email: sotskov48@mail.ru

Alexandre Dolgui
email: alexandre.dolgui@mines.nantes.fr

Aksana Zatsiupa

Stability radii of optimal assembly line balances with a fixed workstation set

Keywords: Assembly line, Uncertain operation durations, Stability analysis

For an assembly line, it is required to minimize the line's cycle time for processing a partially ordered set of the assembly operations on a linearly ordered set of the workstations. The operation set is partitioned into two subsets, manual and automated. The durations of the manual operations are variable and those of the automated operations are fixed. We conduct a stability analysis for this problem. First, we derive a sufficient and necessary condition for the optimal line balance to have an infinitely large stability radius. Second, we derive formulas and an algorithm for calculating the stability radii for the optimal line balances. Third, we report computational results for the stability analysis of the benchmark instances. Finally, we outline managerial implications of the stability results for choosing most stable line balances, which save their optimality in spite of the variations of the operation durations, and for identifying the right time for the re-balancing of the assembly line.

Introduction

The assembly line consists of m workstations, which are linked by a conveyor belt (or another equipment) moving an in-process product from one workstation to the next at a constant pace. The set V of n assembly operations is fixed. Each workstation needs to perform a specific subset of the operations from the set V within the line's cycle-time. All the m workstations start simultaneously to process their own operations. A partial order on the operation set V arises due to technological and economical considerations, which are represented by the precedence digraph G = (V, A) with the set A of arcs. A Simple Assembly Line Balancing Problem is to find an optimal assembly line balance, i.e. an assignment of the operations V to the m workstations such that the cycle-time is minimal. The abbreviation SALBP-2 for denoting this problem has been introduced by [START_REF] Baybars | A survey of exact algorithms for the simple assembly line balancing problem[END_REF]. The problem SALBP-2 is NP-hard [START_REF] Gutjahr | An algorithm for the line balancing problem[END_REF][START_REF] Wee | Assembly line balancing as generalized bin packing[END_REF] since the bin-packing problem is NP-hard and is a special case of the problem SALBP-2, where in the bin-packing problem, the digraph G = (V, A) has no arcs, A = ∅.

Throughout this paper, it is assumed that the set V consists of two specific subsets of the assembly operations. The non-empty subset V ⊆ V includes all the manual operations and the subset V \ V includes all the automated operations. The initial vector t = (t 1 , t 2 , . . . , t n ) of the operation durations is known before solving the problem SALBP-2. However, for the subset V ⊆ V of the manual operations j ∈ V, each duration t j may vary due to different factors such as the operator skill, motivation, learning effect, etc. In contrast to the manual operations, the duration t i of each automated operation i ∈ V \ V is fixed. We assume that V = {1, 2, . . . , ñ} and V \ V = {ñ + 1, ñ + 2, . . . , n}, 1 ≤ ñ ≤ n. The vectors of the operation durations are denoted as follows: t = (t 1 , t 2 , . . . , t ñ), t = (t ñ+1 , t ñ+2 , . . . , t n ), t = ( t, t) = (t 1 , t 2 , . . . , t n ). Let a subset V b r k ∅ of the set V be assigned to the workstation S k , where k ∈ {1, 2, . . . , m}. The assignment b r :

V = V b r 1 ∪ V b r 2 ∪ . . . ∪ V b r
m of the operations V to the ordered workstations (S 1 , S 2 , . . . , S m ),

V b r k ∩ V b u l = ∅, 1 ≤ k < l ≤ m
, is called a line balance, if the following two conditions hold. Condition I. The assignment b r does not violate the partial order given on the set V by the precedence digraph G = (V, A), i.e. each arc (i, j) ∈ A implies that operation i ∈ V is assigned to workstation S k and operation j ∈ V is assigned to workstation S l in a way such that 1 ≤ k ≤ l ≤ m. Condition II. The assignment b r uses all the m workstations, i.e. the subset V b r k is not empty for each workstation S k , k ∈ {1, 2, . . . , m}.

Let Note that Condition II allows us to restrict a set of the line balances since the set B(G, m) contains the optimal line balance without fail. Let B(G, m, t) denote a set of all the optimal line balances, B(G, m, t) ⊆ B(G, m), with the vector t = ( t, t) of the operation durations. If operation i belongs to the set V \ V, its duration t i is fixed. Without loss of generality, we assume that t i > 0 for each automated operation i ∈ V \ V since the automated operation with the fixed zero duration has no influence on a solution to the problem SALBP-2. The initial duration t i is a strictly positive real number t i > 0 for each operation i ∈ V. A value of the duration t j > 0 of the manual operation j ∈ V ⊆ V can vary during the assembly line lifespan. The varied duration t ′ j may be even equal to zero, which means that the manual operation j from the set

V b r k := V b r k ∩ V (1)
is processed by an additional operator in parallel with the processing of other operations assigned to workstation S k . Due to the additional operator, the processing of the manual operation j does not increase the workstation time, i.e.

t ′ (V b r k ) = ∑ i∈V br k t ′ i = ∑ i∈V br k \{ j} t ′ i , (2)
where t ′ indicates the modified vector t ′ = ( t ′ , t) = (t 2) is valid because of holding equality t ′ j = 0. We summarize the above in the following remark. Remark 1. The initial duration t i is a strictly positive real number for each operation i ∈ V. A value of the duration t j > 0 of the manual operation j ∈ V can vary during the assembly line lifespan. The varied duration t ′ j may be equal to zero: t ′ j ≥ 0. The aim of this paper is to investigate the stability of the optimal line balance with respect to variations t ′ t of the operation durations. The stability radius ρ b 0 (t) of the optimal line balance b 0 is interpreted as a maximum of simultaneous and independent variations t ′ of the durations t of operations V without violating the optimality of the line balance b 0 , i.e. b 0 ∈ B(G, m, t) ∩ B(G, m, t ′ ). A formal definition of the stability radius is given in Section 2.1 along with a sufficient and necessary condition for a zero stability radius. In Section 3, it is shown that the stability radius may be infinitely large, ρ b 0 (t) = ∞. Formulas for calculating the stability radius ρ b 0 (t) for the line balance b 0 ∈ B(G, m, t) are given in Section 4.1. The calculation of the stability radius is illustrated in Sections 2.2, 3.3, and 4.3. In Section 4.2, it is shown on how to restrict a subset of the set B(G, m) \ {b 0 }, which must be compared with the line balance b 0 ∈ B(G, m, t) for calculating the stability radius ρ b 0 (t). An algorithm for calculating the stability radius is presented in Section 5. Section 6 reports the computational results for the stability analysis of the benchmark instances from the old dataset and the recent one [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF] tested in [START_REF] Morrison | An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset[END_REF][START_REF] Otto | How to design effective priority rules: Example of simple assembly line balansing[END_REF]. In Section 7, the managerial implications are spelled out on how to use the stability results in the assembly industry. Concluding remarks and perspectives are discussed in Section 8.

Contributions of this work, previous results, and related literature

The assembly lines are widely used in a mass production for assembling components into final products. An effectively balanced assembly line allows a factory to increase its efficiency via reducing a production cost. Since the production conditions may change over time, the need of a re-balancing of the assembly line may arise from time to time in order to serve customer demands in the competitive market environment. The assembly re-balancing is tedious procedures requiring significant costs and amounts of a manpower [START_REF] Chen | Optimizing assembly planning through a three-stage integrated approach[END_REF][START_REF] Chica | A robustness information and visualization model for time and space assembly line balancing under uncertain demand[END_REF][START_REF] Gamberini | A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem[END_REF]. It is a stability analysis that can help us to identify the right time for the re-balancing. In spite of its practical importance, the literature on the stability analysis of the assembly line balances is scanty [START_REF] Chica | A robustness information and visualization model for time and space assembly line balancing under uncertain demand[END_REF][START_REF] Gurevsky | Balancing of simple assembly lines under variations of task processing times[END_REF][START_REF] Gurevsky | Stability measure for a generalized assembly line balancing problem[END_REF][START_REF] Sotskov | Stability radius of the optimal assembly line balance with fixed cycle time[END_REF][START_REF] Sotskov | Stability of optimal line balance with given station set[END_REF][START_REF] Sotskov | Stability analysis of optimal balance for assembly line with fixed cycle time[END_REF][START_REF] Sotskov | Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines[END_REF]. Next, we discuss a concept of the stability radius for the problem SALBP-2 (Section 2.1). Section 2.3 contains a brief literature review of other results and approaches for examining the robustness and stability of the assembly line balances. Contributions of this work are discussed in Section 2.4.

The stability radius of the optimal line balances for the problem SALBP-2

We study the following question. How much can all or some components of the vector t be simultaneously and independently modified that the line balance b 0 , which is optimal for the initial vector t = ( t, t), remains optimal for the modified vector t ′ = ( t ′ , t) of the operation durations? We study the stability radius of the optimal line balance that is defined similarly to the stability radius of the optimal schedule [START_REF] Bräsel | Stability of a schedule minimizing mean flow time[END_REF][START_REF] Sotskov | Stability of an optimal schedule[END_REF]. If the stability radius of the ¨B r r r j l 1 line balance b 0 ∈ B(G, m, t) is strictly positive, then the line balance b 0 remains optimal for all variations t ′ j of the operation durations t j , j ∈ V, within the ball with this radius and center t. On the other hand, if the stability radius of the line balance b 0 is equal to zero, then b 0 may no longer be optimal even for infinitely small variations of the operation durations.

t 1 = 7 l 3 E t 3 = 6 l 5 t 5 = 3 E l 4 t 4 = 2 l 2 t 2 = 5
In contrast to a stochastic assembly line [START_REF] Dong | Balancing and sequencing of stochastic mixed-model assembly u-lines to minimise the expectation of work overload time[END_REF][START_REF] Erel | A survey of the assembly line balancing procedures[END_REF][START_REF] Gamberini | A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem[END_REF][START_REF] Kahan | Beckup strategy for robots' failures in an automotive assembly system[END_REF], we do not assume the given probability distribution for the random duration t j of the manual operation j ∈ V. Note also that operation durations t i , i ∈ V, are assumed to be real numbers, in contrast to the assumption used by [START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF] and many other authors that the operation durations are integer numbers. Let R ñ denote space of all real ñ-vectors (t 1 , t 2 , . . . , t ñ) with the following metric: The distance d( t, t ′ ) between vector t = (t 1 , t 2 , . . . , t ñ) and vector Let W(b r , t) denote the set of subsets V b r k defined in (1), k ∈ {1, 2, . . . , m}, for which t(V b r k ) = c(b r , t). The following sufficient and necessary condition for a zero value of the stability radius has been proven in [START_REF] Sotskov | Stability of optimal line balance with given station set[END_REF].

t ′ = (t ′ 1 , t ′ 2 , . . . , t ′ ñ) is defined as d( t, t ′ ) = max{|t i -t ′ i | : i ∈ V}, where |t i -t ′ i | is the absolute value of the difference t i -t ′ i . Let R ñ + denote space of the non-negative real ñ-vectors, R ñ + ⊆ R ñ. Definition 1. The ball O ρ ( t) in space R ñ with the radius ρ ∈ R 1 + and the center t ∈ R ñ + is called a stability ball of the line balance b 0 ∈ B(G, m, t) if for any modified vector t ′ = ( t ′ , t) of the operation durations with t ′ ∈ O ρ ( t) ∩ R ñ + ,
Theorem 1. For the optimal line balance b 0 , the equality ρ b 0 (t) = 0 holds if and only if there exists another optimal line balance b s ∈ B(G, m, t), b s b 0 , such that the condition (3) does not hold:

W(b 0 , t) ⊆ W(b s , t).
(3) 7,5,6,2,3). The set V = {1, 2} consists of the manual operations. The set V \ V = {3, 4, 5} consists of the automated operations. The precedence digraph G = (V, A) is presented in Fig. 1, where transitive arcs are omitted for simplicity. The following ten line balances exist for Example 1. b 0 :

2.2. Example 1 Assume that m = 4, n = 5, ñ = 2, t = ( t, t) = (t 1 , t 2 , t 3 , t 4 , t 5 ) = (
V = {1} ∪ {3} ∪ {2} ∪ {4, 5}; b 1 : V = {1} ∪ {3} ∪ {2, 4} ∪ {5}; b 2 : V = {1} ∪ {2, 3} ∪ {4} ∪ {5}; b 3 : V = {1, 3} ∪ {2} ∪ {4} ∪ {5}; b 4 : V = {1} ∪ {3} ∪ {2, 5} ∪ {4}; b 5 : V = {1} ∪ {2, 3} ∪ {5} ∪ {4}; b 6 : V = {1, 3} ∪ {2} ∪ {5} ∪ {4}; b 7 : V = {1} ∪ {3} ∪ {4} ∪ {2, 5}; b 8 : V = {1} ∪ {3, 4} ∪ {2} ∪ {5}; b 9 : V = {1, 3} ∪ {4} ∪ {2} ∪ {5}.
The cycle-times for the line balances B(G, m) are as follows:

c(b 0 , t) = 7, c(b 1 , t) = 7, c(b 2 , t) = 11, c(b 3 , t) = 13, c(b 4 , t) = 8, c(b 5 , t) = 11, c(b 6 , t) = 13, c(b 7 , t) = 8, c(b 8 , t) = 8, c(b 9 , t) = 13.
There are two optimal line balances, B(G, m, t) = {b 0 , b 1 }. We test the condition of Theorem 1 for the line balance b 0 . The sets W(b i ) for both optimal line balances are as follows:

W(b 1 , t) = { V b 1 1 , V b 1 3 } = {{1}, {2}}, W(b 0 , t) = { V b 1 1 } = {{1}}.
One can convince that condition (3) holds, i.e. the set W(b 1 , t) is a subset of the set W(b 0 , t): {{1}} ⊂ {{1}, {2}}. Due to Theorem 1, the stability radius of the line balance b 0 is strictly positive: ρ b 0 (t) > 0. We test the condition of Theorem 1 for the line balance b 1 ∈ B(G, m, t). There exists another optimal line balance b 0 such that condition (3) does not hold, namely, the set W(b 0 , t) is not a subset of the set W(b 1 , t): {{1}, {2}} {{1}}. Due to Theorem 1, the stability radius of the line balance b 1 is equal to zero: ρ b 1 (t) = 0.

A survey of the robustness and other stability results

At the design stage of the assembly line, the following Simple Assembly Line Balancing Problem, which is dual to the problem SALBP-2, has to be solved: To minimize a cardinality of the ordered set (S 1 , S 2 , . . . , S m ) of the workstations that must process the partially ordered set V of the operations within the fixed cycle-time c. The abbreviation SALBP-1 is used to denote this problem [START_REF] Baybars | A survey of exact algorithms for the simple assembly line balancing problem[END_REF][START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF][START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF]. A sufficient and necessary condition for a zero stability radius for the problem SALBP-1, and formulas for calculating the stability radii have been proven in [START_REF] Sotskov | Stability analysis of optimal balance for assembly line with fixed cycle time[END_REF]. The enumerative algorithms for constructing optimal and stable line balances have been developed in [START_REF] Sotskov | Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines[END_REF]. [START_REF] Gurevsky | Balancing of simple assembly lines under variations of task processing times[END_REF] considered the stability analysis for the problem SALBP-E, which is to find a line balance b 0 such that the product m × c(b 0 , t) is minimal. A lower bound on the stability radius of the optimal line balance for the problem SALBP-E was derived. The stability analysis for a more general assembly line was developed in [START_REF] Gurevsky | Stability measure for a generalized assembly line balancing problem[END_REF], where several workplaces were associated with the workstation, the operations assigned to the workstation were partitioned into blocks, where the operations grouped into the same block have to be processed simultaneously. [START_REF] Hamta | A hybrid pso algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect[END_REF] addressed a multi-objective optimization of the assembly line balancing problem, where each operation duration was uncertain. The heuristic algorithm was developed as a combination of a particle swarm optimization with a variable neighborhood search. [START_REF] Chica | A robustness information and visualization model for time and space assembly line balancing under uncertain demand[END_REF] studied the time and space assembly line balancing problem involving the joint minimization of the cycle time, the number of workstations, and the workstation area. The authors introduced robustness functions to measure how robust the assembly line is when the production plans are changed as demands change.

In [START_REF] Corominas | Applications balancing assembly line with skilled and unskilled workers[END_REF], the re-balancing of the assembly line at the motorcycle plant was studied. The company found that it was necessary to re-balance the assembly line since it needed to increase the production in the months of spring and summer. The goal was to minimize the number of temporary workers required for the given cycle time and permanent workers. The assembly line re-balancing was also considered in [START_REF] Gamberini | A multiple single-pass heuristic algorithm solving the stochastic assembly line rebalancing problem[END_REF][START_REF] Gamberini | A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem[END_REF].

In [START_REF] Toksari | Simple and u-type assembly line balancing problems with a learning effect[END_REF], the learning effect was studied for the assembly line balancing problem, where the workers acquire more experience by repeatedly performing the same assembly operations and thus the operation duration shortens at later production periods. It was shown how solutions can be obtained for special cases of the straight-type and U-type line balancing problems with a learning effect. The learning effects for the assembly line balancing problem were also studied in [START_REF] Chakravarti | Line balancing with task learning effects[END_REF]; [START_REF] Guo | Intelligent production control decision support system for flexible assembly lines[END_REF]; [START_REF] Hamta | A hybrid pso algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect[END_REF].

A mixed-model U-type assembly line was studied in [START_REF] Dong | Balancing and sequencing of stochastic mixed-model assembly u-lines to minimise the expectation of work overload time[END_REF], where both the operation assignment and the production sequence affect the workload variance among the workstations. A stochastic programming was used, where the operation durations were stochastic variables with a normal distribution and the objective was to minimize an expectation of the work overload time for the given cycle-time and workstations. The problem of balancing U-type assembly line under uncertainty was addressed in [START_REF] Hazir | A decomposition based solution algorithm for u-type assembly line balancing with interval data[END_REF]. The robust optimization was employed that considered the worst-case scenarios. To avoid an over-pessimism, it was assumed that a subset of the operation durations may take their largest possible values. [START_REF] Hazir | Assembly line balancing under uncertainty: robust optimization models and exact solution method[END_REF] dealt with the assembly line balancing problem under uncertainty using a robust optimization, where intervals of the operation durations were given. [START_REF] Yilmaz | Multi-manned assembly line balancing problem with balanced load density[END_REF] addressed the balancing of the multi-manned assembly line with load constraints and conventional ones, where a remedial constraint was provided to balance the load density of the operations for each worker. The mathematical model combines the minimization of multi-manned workstations, the operator number, and the difference of operation load densities. In [START_REF] Qian | Solving multi-manned assembly line balancing problem by a heuristic-mixed genetic algorithm[END_REF], it was allowed that more than one operator can work simultaneously in the workstation. A genetic algorithm was proposed for solving this problem. In [START_REF] Sivasankaran | Literature review of assembly line balancing problems[END_REF], a recent survey on the assembly line balancing is reported, where problems are classified based on the number of models, nature of operation durations (deterministic or stochastic), and type of the assembly line. An exhaustive review of the literature with an original taxonomy of line balancing problems, for assembly, disassembly and machining lines, is proposed in [START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF]. The suggested taxonomy is based on the following five elements: task attributes, workstation attributes, constraints to be respected, criteria used.

Contributions of this work for practitioners

In the labor-intensive assembly line, the durations of the manual operations are variable depending on the operator qualifications, experiences, the learning effect etc. As a result, the line balance b 0 ∈ B(G, m), which is optimal for the problem SALBP-2 with the operation durations t = ( t, t), may lose its optimality even for slightly modified operation durations. In such a case, the need to solve the problem SALBP-2 may arise again in order to re-balance the assembly line due to the changes of the operation durations. Each re-balancing of the assembly line in process takes time and incurs an additional expenditure. The assembly line modification has to start when the income from it will be larger than the total expenditure caused by the modification. So, an evaluation of the factual expenditures and benefits should be conducted for the re-balancing decision.

This work shows that the above expenditures and benefits may be evaluated based on the set B(G, m, t) of the optimal assembly line balances and calculating their stability radii ρ b 0 (t), b 0 ∈ B (G, m, t). If factual variations of the operation durations are no larger than the stability radius ρ b 0 (t) of the current assembly line balance b 0 , then the modification of the line balance b 0 is not needed. Moreover, using the optimal line balance b 0 with the largest stability radius ρ b 0 (t) allows the factory to use the optimal line balance b 0 for a longer time without any re-balancing. Furthermore, if the re-balancing is needed, it may be realized easily via using the constructed set B(G, m, t) of the optimal line balances (or k-best line balances if the optimal line balance is unique, |B(G, m, t)| = 1). Since the problem SALBP-2 is NP-hard, an exact algorithm for solving the problem must estimate (either implicitly or explicitly) the objective values c = c(b r , t) for the line balances b r ∈ B (G, m). We propose to make these estimations explicitly via constructing the set B(G, m). Using the constructed set B(G, m), one can solve the problem SALBP-2 exactly, investigate the stability of the optimal line balances, and select the most stable line balance b 0 that remains optimal for all variations t ′ of the operation durations within the stability ball O ρ ( t) with the largest radius ρ = ρ b 0 (t).

Using the proven results, we developed Algorithm RAD for constructing the set B(G, m) of the line balances, the set B(G, m, t) of the optimal line balances, and calculating their stability radii. The computational experiments on a laptop showed that the CPU-time for constructing the set B(G, m, t) along with calculating stability radii ρ b r (t) for the line balances b r ∈ B(G, m, t) is not large for a small-size assembly line and for some moderate-size assembly lines.

3. An infinite stability radius of the optimal line balance Theorem 1 gives the sufficient and necessary condition for a zero stability radius. To present a criterion for the infinitely large stability radius, we need to introduce the simple assembly line balancing problem SALBP * -2, which has the same input data as the original problem SALBP-2 has, except that the initial vector t * of the operation durations is now as follows:

t * = ( t * , t) := (0, 0, . . . , 0, t n+1 , t n+2 , . . . , t n ). The line balance b u ∈ B(G, m) is optimal for the problem SALBP * -2, if b u ∈ B(G, m, t * ).

The main notations

The notations used in this study are listed as follows:

m total number of workstations S k workstation S k ∈ {S 1 , S 2 , . . . , S m } V
the set of assembly operations n total number of assembly operations V the set of manual operations, V ⊆ V ñ total number of manual operations, 1

≤ ñ ≤ n G = (V, A) precedence digraph with arc set A t = (t 1 , t 2 , . . . , t n ) vector of the operation durations, t = ( t, t) t = (t 1 , t 2 , . . . , t ñ)
durations of the manual operations, these durations are variable t = (t ñ+1 , t ñ+2 , . . . , t n ) durations of the automated operations, these durations are fixed

V b r k the subset of operations assigned to the workstation S k in the line balance b r , V b r k ∅ V b r k the subset of manual operations assigned to the workstation S k in the line balance b r , V b r k = V b r k ∩ V B(G)
the set of all assignments of the operations V to the m workstations, which do not violate the partial order given on the set

V by the digraph G = (V, A) B(G, m) = {b 0 , b 1 , . . . , b h } the set of all line balances, B(G, m) ⊂ B(G) B(G, m, t)
the set of optimal line balances with vector t of the operation durations,

B(G, m, t) ⊆ B(G, m) c(b r , t) cycle-time c = c(b r , t) for the line balance b r with the vector t = ( t, t) of the operation durations, c(b r , t) = max m k=1 ∑ i∈V br k t i t(V b r k ) workstation time, t(V b r k ) = ∑ i∈V br k t i d( t, t ′ )
distance between vector t = (t 1 , t 2 , . . . , t ñ) and vector

t ′ = (t ′ 1 , t ′ 2 , . . . , t ′ ñ), d( t, t ′ ) = max{|t i -t ′ i | : i ∈ V} O ρ ( t)
stability ball with the radius ρ of the optimal line balance in space R ñ of the real vectors t = (t 1 , t 2 , . . . , t ñ) ρ b 0 (t) stability radius of the line balance b 0 ∈ B(G, m, t), i.e. the maximal value of the radius ρ of the stability ball

O ρ ( t), t = ( t, t) W(b r , t) the set of subsets V b r k such that t(V b r k ) = c(b r , t).

A sufficient and necessary condition for the infinite stability radius

Theorem 2. Assume that for each manual operation i ∈ V, there exists a line balance b

u ∈ B(G, m) with V b u l = {i}. The stability radius ρ b 0 (t) of the line balance b 0 ∈ B(G, m, t) is infinite, if and only if b 0 ∈ B(G, m, t * ) and V b 0 k = {i} for each manual operation i ∈ V and some workstation S k . Proof. Sufficiency. Let b 0 ∈ B(G, m, t *
) and V b 0 k = {i} for each operation i ∈ V and some workstation S k . We have to prove that ρ b 0 (t) = ∞. First, we show that increasing the duration t i of any manual operation i ∈ V cannot violate the optimality of the line balance b 0 . Inequality

c(b 0 , t) ≤ c(b r , t) holds for any line balance b r ∈ B(G, m) since b 0 ∈ B(G, m, t). Due to continuous increasing the duration t i , namely, t ′ i = t i + ∆, equality c(b 0 , t ′ ) = c(b r , t ′
) will be reached for some value ∆ := ∆ i ≥ 0 with setting t ′ j = t j for all other operations j i. Further increasing the duration of operation i, namely,

t ′′ i = t ′ i + θ i = t i + ∆ i + θ i , implies c(b 0 , t ′′ ) = t ′′ (V b 0 u ) = t ′′ i + θ i ≤ t ′′ (V b r k(i,b r ) ) ≤ c(b r , t ′′ ), (4)
where t ′′ j = t j for all other operations j ∈ V \ {i}. Hereafter, S k(i,b r ) denotes the workstation

S k(i,b r ) ∈ S such that i ∈ V b r k(i,b r ) . The first inequality in (4) is valid since |V b r k(i,b r )
| ≥ 1 and since V b 0 k = {i} for any manual operation i ∈ V due to the condition of Theorem 2. Thus, it is proven that increasing the duration t i by any large value ∆ i + θ i cannot violate the optimality of the line balance b 0 ∈ B(G, m, t ′′ ).

By a contradiction, we shall prove that decreasing the duration t i of any manual operation i ∈ V cannot violate the optimality of the line balance b 0 . Assume that due to decreasing the durations t i of manual operations i ∈ V by values ε i with 0 ≤ ε i ≤ t i , a vector t ε is obtained from the initial vector t:

t ε i = t i + ε i , i ∈ V, t ε j = t j , j ∈ V \ V, such that the line balance b 0 loses its optimality, i.e. b 0 B(G, m, t ε ), where t ε = (t ε 1 , t ε 2 , . . . , t ε n ). In other words, there exists a line balance b w ∈ B(G, m) \ {b 0 } such that c(b 0 , t ε ) > c(b w , t ε ) = min{c(b r , t ε ) : b r ∈ B(G, m)}. The condition V b 0 k = {i} being valid for any manual operation i ∈ V implies c(b 0 , t ε ) = max { max i∈ V {t ε (V b 0 k(i,b 0 ) )}, max j∈V\ V {t ε (V b 0 k( j,b 0 ) )} } , max i∈ V { t ε (V b 0 k(i,b 0 ) ) } ≤ max i∈ V { t ε (V b w k(i,b w ) ) } for each line balance b w ∈ B(G, m) \ {b 0 }. Hence, inequality c(b 0 , t ε ) > min b w ∈B(G,m)\{b 0 } c(b w , t ε ) (5)
holds if and only if max

j∈V\ V { t ε (V b 0 k( j,b 0 ) ) } > min b w ∈B(G,m)\{b 0 } c(b w , t ε ). (6) Due to V b 0 k = {i}, i ∈ V, we obtain that for any workstation S k( j,b 0 ) ∈ S with j ∈ V \ V, there is no a manual operation i ∈ V such that i ∈ V b 0 k( j,b 0 ) . Hence, equality t ε (V b 0 k( j,b 0 ) ) = t * (V b 0 k( j,b 0 ) ) holds for each workstation S k( j,b 0 ) ∈ S with j ∈ V \ V. As a result we obtain max j∈V\ V { t ε (V b 0 k( j,b 0 ) ) } = max j∈V\ V { t * (V b 0 k( j,b 0 ) ) } . (7)
Since any component of the vector t ε is not greater than the corresponding component of the vector t * , we obtain

t ε (V b w k( j,b w ) ) = t * (V b w k( j,b w ) ) for each operation j ∈ V. Hence, min b w ∈B(G,m)\{b 0 } c(b w , t ε ) ≥ min b w ∈B(G,m)\{b 0 } c(b w , t * ).
From the inequalities (4), ( 5), ( 6), and the equality (7), we obtain

max i∈V\ V { t * (V b 0 k( j,b 0 ) ) } > min b w ∈B(G,m)\{b 0 } c(b w , t * ). ( 8
)
The inequality (8

) implies c(b w , t * > min b w ∈B(G,m)\{b 0 } c(b w , t * ). Hence, b 0 B(G, m, t *
) that contradicts to the condition of Theorem 2. Sufficiency is proven.

Necessity. Assume that ρ b 0 (t) = ∞. First by a contradiction, we prove that the assumption ρ b 0 (t) = ∞ implies b 0 ∈ B(G, m, t * ). Note that the vector t * = ( t * , t) belongs to the stability ball O ρ ( t) of the line balance b 0 ∈ B(G, m, t) (Remark 1) and the distance d( t, t * ) between vector t = (t 1 , t 2 , . . . , t ñ) and vector then ρ b 0 (t) ≤ max i∈ V t i < ∞ that contradicts to the above assumption ρ b 0 (t) = ∞. Next, we prove that from the assumption ρ b 0 (t) = ∞ and the condition of Theorem 2, it follows that V b 0 k = {i} for each operation i ∈ V and some workstation S k ∈ S . Contrarily, we assume that there is a manual

t * = (t * 1 , t * 2 , . . . , t * ñ) is equal to max i∈ V t i . Therefore, if b 0 B(G, m, t * ), l 1 t 1 = 5 ¨B r r r j l 5 t 5 = 7 l 4 t 4 = 4 E E l 2 c t 2 = 8 l 3 t 3 = 3
operation i ∈ V such that V b 0 k(i,b 0 ) \ {i} ∅. For each operation i ∈ V, there exists the line balance b u ∈ B(G, m) such that V b u l = {i}, l ∈ {1, 2, .
. . , m} (the condition of Theorem 2). We choose any large number Θ u with Θ u > c(b u , t) and consider the modified vector

t ′ = ( t ′ , t) such that t ′ i = t i +Θ u and t ′ j = t j for all operations j ∈ {1, 2, . . . , n} \ {i}. The condition b 0 ∈ B(G, m, t) implies c(b 0 , t) ≤ c(b u , t) < Θ u . (9)
Due to (9), we obtain

c(b 0 , t ′ ) = max { c(b 0 , t), Θ u + t(V b 0 k(i,b 0 ) ) } = Θ u + t(V b 0 k(i,b 0 ) ), (10) c(b u , t ′ ) = max {c(b u , t), Θ u + t i } = Θ u + t i . (11)
Due to (10) and ( 11) and taking into account i ∈ V b 0 k(i,b 0 ) , where V b 0 k(i,b 0 ) \ {i} ∅, and t j > 0 for each operation j ∈ V (Remark 1), we obtain c(b

0 , t ′ ) = Θ u + t(V b 0 k(i,b 0 ) ) > Θ u + t i = c(b u , t ′ ). Hence, b 0 B(G, m, t ′ ) that implies ρ b 0 (t) ≤ d( t, t ′ ) = Θ u < ∞ contradicting the above assumption ρ b 0 (t) = ∞.
This completes the proof.

Returning to Example 1, we test the condition of Theorem 2 for the line balance b 0 . The modified problem SALBP * -2 has the same input date as the original problem has, except that the initial vector of the operation durations is now as follows: t * = (0, 0, 6, 2, 5). The problem SALBP * -2 has the same set of the line balances B(G, m) = {b 0 , b 1 , . . . , b 9 } as Example 1 has. The minimal cycle-time for the problem SALBP * -2 is equal to 6. The condition of Theorem 2 holds for the line balance b 0 . Indeed, equality

V b 0 k = {i} holds for each i ∈ V: V b 0 1 = {1}, V b 0 3 = {2}. The condition b 0 ∈ B(G, m, t * ) holds since c(b 0 , t * ) = 6.
Due to Theorem 2, we conclude that the stability radius of the line balance b 0 is infinite, ρ b 0 (t) = ∞. Thus, the line balance b 0 ∈ B(G, m, t) is better for the assembly industry than the line balance b 1 ∈ B(G, m, t), since the line balance b 0 remains optimal for all variations t, while even small variations of the durations i ∈ V may deprive the optimality of the line balance b 1 .

Example 2

Assume that m = 4, n = 5, ñ = 2, t = ( t, t) = (t 1 , t 2 , t 3 , t 4 , t 5 ) = (5, 8, 3, 4, 7). The set V = {1, 2} contains the manual operations. The set V \ V = {3, 4, 5} contains the automated operations. The precedence digraph G = (V, A) is presented in Fig. 2, where transitive arcs are omitted. There exist ten line balances for Example 2 as follows:

b 0 : V = {1} ∪ {2} ∪ {3, 4} ∪ {5}; b 1 : V = {1} ∪ {2} ∪ {3} ∪ {4, 5}; b 2 : V = {1} ∪ {2, 3} ∪ {4} ∪ {5}; b 3 : V = {1, 2} ∪ {3} ∪ {4} ∪ {5}; b 4 : V = {1} ∪ {3} ∪ {2} ∪ {4, 5}; b 5 : V = {1} ∪ {3} ∪ {2, 4} ∪ {5}; b 6 : V = {1, 3} ∪ {2} ∪ {4} ∪ {5}; b 7 : V = {1} ∪ {3, 4} ∪ {2} ∪ {5}; b 8 : V = {1} ∪ {3} ∪ {4} ∪ {2, 5}; b 9 : V = {1, 3} ∪ {4} ∪ {2} ∪ {5}.
The minimal cycle-time c for the optimal line balance is equal to 8 and the following four line balances are optimal: b 0 :

V = {1} ∪ {2} ∪ {3, 4} ∪ {5}; b 6 : V = {1, 3} ∪ {2} ∪ {4} ∪ {5}; b 7 : V = {1} ∪ {3, 4} ∪ {2} ∪ {5}; b 9 : V = {1, 3} ∪ {4} ∪ {2} ∪ {5}.
The sets W(b i ) for the optimal line balances are as follows:

W(b 0 , t) = {{2}}, W(b 6 , t) = {{1}, {2}}, W(b 7 , t) = {{2}}, W(b 9 , t) = {{1},
0 ∈ B(G, m, t): V b 0 1 = {1}, V b 0 2 = {2}. Condition b 0 ∈ B(G, m, t * ) holds since c(b 0 , t * ) = 7. Due to Theorem 2, the stability radius of the line balance b 0 is infinite: ρ b 0 (t) = ∞. For the optimal line balance b 7 ∈ B(G, m, t) = {b 0 , b 7 }, for each manual operation i ∈ V, equality V b 7 k = {i} holds: V b 7 1 = {1}, V b 7 3 = {1}. Condition b 7 ∈ B(G, m, t * ) holds since c(b 7 , t * ) = 7. Due to Theorem 2, we obtain ρ b 7 (t) = ∞.
4. The calculation of stability radii for the optimal line balances Theorems 1 and 2 give criteria for the extreme values of the stability radii: ρ b 0 (t) = 0 or ρ b 0 (t) = ∞. In Sections 4.1 and 4.2, we show how to calculate the stability radius if 0 < ρ b 0 (t) < ∞.

Formulas for calculating the stability radius

Assume that for the line balance b 0 ∈ B(G, m, t), there does not exist the line balance b s ∈ B(G, m, t), b s b 0 , such that the condition (3) does not hold. Due to Theorem 1, the stability radius ρ b 0 (t) is strictly positive. Assume also that ρ b 0 (t) < ∞. Let the sign ⊕ denote a direct summation of two sets ) denote a non-decreasing sequence of the durations of the operations from the set

V b 0 u and V b r k , i.e. V b 0 u ⊕ V b r k := { V b 0 u ∪ V b r k } \ { V b 0 u ∩ V b r k } . Let
V b r k \ V b 0 u , where w uk = | V b r k \ V b 0 u |. Theorem 3. If b 0 ∈ B(G, m, t) with 0 < ρ b 0 (t) < ∞, then ρ b 0 (t) = min {∆(b 0 , t), δ(b 0 , t)} , where (12)
∆(b 0 , t) = min b s ∈B(G,m,t)\{b 0 } u min | V b 0 u ⊕ V bs k |≥1 k max t(V b 0 u )<c(b s ,t)=t(V bs k ) max β=0,1,...,w uk -1 c(b s , t) -t(V b 0 u ) - ∑ β α=0 t uk (α) | V b 0 u ⊕ V b s k | -β , (13) δ(b 0 , t) = min b r ∈B(G,m)\B(G,m,t) u min | V b 0 u ⊕ V br k |≥1 k max t(V br k )>c(b 0 ,t) max β=0,1,...,w uk -1 t(V k b r ) -t(V u b 0 ) - ∑ β α=0 t uk (α) | V b 0 u ⊕ V b r k | -β . ( 14
)
The proof of Theorem 3 is given in Appendix A, where it is shown that the real number ∆(b 0 , t) (δ(b 0 , t), respectively) is equal to the minimal variation of the manual operation durations allowing to decrease the workstation time of the bottleneck workstation of another optimal line balance b s (of the non-optimal line balance b r ). If the set B(G, m, t) is a singleton, B(G, m, t) = {b 0 }, then due to Theorem 1 we obtain ρ b 0 (t) > 0 and Theorem 3 implies the following claim.

Corollary 1. If B(G, m, t) = {b 0 } and ρ b 0 (t) < ∞, then ρ b 0 (t) = δ(b 0 , t).
In formulas ( 13) and ( 14), a denominator of the fraction in the right-hand side may be equal to zero. If we assume that a positive number divided by 0 is the infinity, then formula (12) gives the infinity in the right-hand side, ρ b 0 (t) = ∞. However, the more simple criterion for the infinite stability radius is given in Theorem 2. In Section 4.2, it is shown how to restrict the set of line balances that have to be compared with the line balance b 0 for calculating the stability radius ρ b 0 (t).

The redundant line balances for calculating the stability radius

Due to Theorem 3, a calculation of the stability radius ρ b 0 (t) > 0 is reduced to the timeconsuming calculation on the set B(G, m). In order to restrict the set of line balances b r ∈ B(G, m) \ {b 0 }, with which the optimal line balance b 0 may be compared for calculating ρ b 0 (t), one can use the upper bound on the following value:

δ(b 0 , b r , t) := u min | V b 0 u ⊕ V bs k |≥1 k max t(V br k )>c(b 0 ,t) max β=0,1,...,w uk -1 t(V b r k ) -t(V b 0 u ) - ∑ β α=0 t uk (α) | V b 0 u ⊕ V b r k | -β , (15)
which is given in Theorem 3 in the right-hand side of the equality (14). The implementation of Lemma 1, Corollary 2, Theorems 1 and 3 is demonstrated on the calculation of the stability radii for the following example.

l 6 t 6 = 3 ¨¨B ¨B r r r j l 2 t 2 = 5 l 4 E t 4 = 4 l 1 t 1 = 2 l 5 t 5 = 5 l 3 t 3 = 1

Example 3

Assume that m = 3, n = 6, ñ = 3, t = ( t, t) = (t 1 , t 2 , t 3 , t 4 , t 5 , t 6 ) = (2, 5, 1, 4, 5, 3). The set V = {1, 2, 3} includes manual operations. The set V \ V = {4, 5, 6} includes automated operations. The digraph G = (V, A) is presented in Fig. 3, where the transitive arcs are omitted. If all operation durations are integers, the following lower bound on the minimal cycle-time c is valid:

min {c(b r , t) : b r ∈ B} = c ≥           n ∑ i=1 t i m           , ( 17
)
where ⌈a⌉ denotes the smallest integer number that is greater than or equal to the real number a. One can convince that the line balance b 0 :

V = {2, 6} ∪ {1, 4} ∪ {3, 5} is optimal since ⌈ ∑ n i=1 t i m ⌉ = ⌈ ∑ 6 i=1 t i 3 ⌉ = ⌈ 20 3 ⌉ = 6 = c(b 0 , t)
, which imply that c(b 0 , t) is equal to the righthand side of the inequality ( 17). Similarly, one can be convinced that there are four optimal line balances as follows: b

0 : V = {2, 6} ∪ {1, 4} ∪ {3, 5}; b 1 : V = {2, 6} ∪ {3, 4} ∪ {1, 5}; b 2 : V = {2, 6} ∪ {4} ∪ {1, 3, 5}; b 3 : V = {2, 6} ∪ {1, 3, 4} ∪ {5}.
Other line balances are non-optimal for the vector t = (4, 1, 6, 3, 7, 4) of the operation durations. For the optimal line balances b i , i ∈ {0, 1, 2, 3}, the sets W(b i , t) are as follows:

W(b 0 , t) = {{2}}; W(b 1 , t) = {{2}}; W(b 2 , t) = {{2}, {1, 3}}; W(b 3 , t) = {{2}}.
= W(b 0 , t) ⊆ W(b 1 , t) = {{2}}, {{2}} = W(b 0 , t) ⊆ W(b 2 , t) = {{2}, {1, 3}}, {{2}} = W(b 0 , t) ⊆ W(b 3 , t) = {{2}}, where {b 1 , b 2 , b 3 } = B(G, m, t) \ {b 0 }. Due to Theorem 1, the line balance b 0 ∈ B(G, m, t) is stable: ρ b 0 (t) > 0.
Similarly, we can obtain inequalities ρ b 1 (t) > 0 and ρ b 3 (t) > 0. Using Theorem 3, we calculate stability radii ρ b 0 (t), ρ b 1 (t), ρ b 3 (t). Due to Corollary 2, we have to compare the line balance b 0 with the line balances b 1 , b 2 , and b 3 , which are also optimal for the vector t = (2, 5, 1, 4, 5, 3). Using the formula (15), we calculate

δ(b 0 , b 1 , t) = 1, δ(b 0 , b 2 , t) = 2, δ(b 0 , b 3 , t) = 1.
Using the bound ( 16) with the left-hand side δ(b 0 , b 1 , t) = 1 and Lemma 1, one can be convinced that to calculate a value δ(b 0 , t) given in ( 14), it is sufficient to compare the line balance b 0 with seven line balances: b 4 : 5. An algorithm for the calculation of stability radii for the optimal line balances

V = {6} ∪ {2, 3, 4} ∪ {1, 5}; b 5 : V = {2, 3, 6} ∪ {4} ∪ {1, 5}; b 6 : V = {2, 3, 6} ∪ {4, 5} ∪ {1}; b 7 : V = {3, 6} ∪ {2, 4} ∪ {1, 5}; b 8 : V = {6} ∪ {2, 4} ∪ {1, 3, 5}; b 9 : V = {2, 6} ∪ {4, 5} ∪ {1, 3}; b 10 : V = {2, 3, 6} ∪ {1, 4} ∪ {5}. Using the formula (15), we calculate δ(b 0 , b 4 , t) = 3 2 , δ(b 0 , b 5 , t) = 1, δ(b 0 , b 6 , t) = 1, δ(b 0 , b 7 , t) = 3 2 , δ(b 0 , b 8 , t) = 3 2 , δ(b 0 , b 9 , t) = 1, δ(b 0 , b 10 , t) = 1. Using the formula (14), we obtain δ(b 0 , t) = min { 3 2 , 1, 1, 3 2 , 3 2 , 1, 1 } = 1.
If the set B(G, m) is constructed, it is not difficult to find the set B(G, m, t), having chosen the line balances from the set B(G, m) with the minimal cycle-time. Using Theorem 1, one can choose all unstable optimal line balances B 0 (G, m, t) ⊆ B(G, m, t). Using Theorem 2, one can choose all optimal line balances B ∞ (G, m, t) with infinite stability radii if they exist. Next, we present an algorithm for constructing sets B(G, m), B(G, m, t), B 0 (G, m, t), B ∞ (G, m, t), and calculating the stability radii for all optimal line balances. The fist step of this algorithm uses the algorithm for constructing the set B(G, m) developed in [START_REF] Sotskov | Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines[END_REF].

Algorithm RAD Input:

The set V of the manual operations, the set V \ V of the automated operations, the digraph G = (V, A), the workstation number m, the operation durations t = ( t, t).

Output: The set B(G, m) of the line balances, the set B(G, m, t) of the optimal line balances, the set B 0 (G, m, t) of the unstable line balances, the set B ∞ (G, m, t) of the optimal line balances with infinite stability radii, the stability radii ρ b i (t) for all optimal line balances.

Step 1. Construct the set B(G, m) using the algorithm described in [START_REF] Sotskov | Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines[END_REF].

SET k = 1, B 0 (G, m, t) = ∅, B ∞ (G, m, t) = ∅.
Step 2. Choose all line balances B(G, m, t) = {b 1 , b 2 , . . . , b q } with a minimal cycle-time c from the set B(G, m). The set B(G, m, t) of the optimal line balances is constructed.

Step 3. SET b 0 = b k . Step 4. IF B(G, m, t) = {b 0 } THEN ρ b 0 (t) > 0 GOTO step 8. Step 5. ELSE FOR each optimal line balance b i ∈ B(G, m, t), construct the set W(b i , t). Step 6. FOR each optimal line balance b i ∈ B(G, m, t) \ { {b 0 } ∪ B 0 (G, m, t) ∪ B ∞ (G, m, t) } DO IF W(b 0 , t) ⊆ W(b i , t) for each line balance b i ∈ B(G, m, t) \ {b 0 } THEN GOTO step 8 ELSE GOTO step 7 ENDDO. Step 7. SET ρ b 0 (t) = 0 SET B 0 (G, m, t) := B 0 (G, m, t) ∪ {b 0 }.
Step 8. Construct the modified problem SALBP * -2 via setting operation durations as follows: t * = ( t * , t) = (0, 0, . . . , 0, t n+1 , t n+2 , . . . , t n ).

Step 9. Calculate the minimal cycle-times c * for the problem SALBP * -2.

IF c(b 0 , t * ) = c * THEN GOTO step 11.

Step 10. FOR each manual operation i ∈ V DO IF equality {i} = V b 0 k does not hold THEN GOTO step 11 ENDDO.

SET

ρ b 0 (t) = ∞ SET B ∞ (G, m, t) := B ∞ (G, m, t) ∪ {b 0 }.
Step 11. FOR each optimal line balance b

s ∈ B(G, m, t) \ {b 0 } DO Calculate ∆(b 0 , b s , t) = min u | V b 0 u ⊕ V bs k |≥1 max k t(V b 0 u )<c(b s ,t)=t(V bs k ) ∆ b s ,k b 0 ,u , where ∆ b s ,k b 0 ,u is determined in (A.18) SET ∆(b 0 , t) = min b s ∈B(G,m,t)\{b 0 } ∆(b 0 , b s , t) ENDDO. Step 12. FOR each non-optimal line balance b r ∈ B(G, m) \ B(G, m, t) DO Step 13. IF δ(b 0 , b g , t) > c(b r ,t)-c(b 0 ,t) min { ñ,ñ br +ñ b 0 } for each line balance b g ∈ B(G, m) \ {b 0 , b r } THEN GOTO step 14 ELSE GOTO step 12 ENDDO. Step 14. Calculate δ(b 0 , b r , t) = min u | V b 0 u ⊕ V br k |≥1 max k t(V br k )>c(b 0 ,t) δ b r ,k b 0 ,u , where δ b r ,k b 0 ,u is determined in (A.8) SET δ(b 0 , t) = min b r ∈B(G,m)\{b 0 } δ(b 0 , b r , t) SET ρ b 0 (t) = min {∆(b 0 , t), δ(b 0 , t)} SET k := k + 1.
Step 15. IF k ≤ q THEN GOTO step 3 ELSE The sets B 0 (G, m, t) and B ∞ (G, m, t) are constructed and the stability radii

ρ b i (t) are calculated, b i ∈ B(G, m, t) STOP.
Steps 6 and 7 of the above Algorithm RAD are based on Theorem 1, steps 8 -10 on Theorem 2, step 13 on Lemma 1, steps 11, 12 and 14 on Theorem 3 and Corollary 1.

Computational results

Algorithm RAD was implemented in C++ and tested on the benchmark instances available on http://www.assembly-line-balancing.de. The computational experiments were run on a laptop with the following characteristics: Intel(R), Pentium(R), CPU 2020M @2.40GHz 2.40GHz, 4.00GB Internal Memory. The main characteristics of the benchmark instances, which determine their complexity, are presented in Table 1 for the benchmark dataset given in [START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF], and in Table 2 for the benchmark dataset given in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF]. In Tables 1 and2, the first column gives the instance name (a number is used as the instance name in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF]). The second column gives the number of the operations followed by the minimal duration t min (column 3), the maximal duration t max (column 4), and the sum of durations ∑ t i (column 5). The last two columns give the complexity measures for the instances tested. Column 6 gives the Order Strength (OS ) of the digraph G = (V, A) in percentages:

OS = |A| |A C | • 100%, where |A C | = n(n-1)
2 is the number of arcs in the complete circuit-free digraph G = (V, A C ) of order n. Column 7 gives the Time Variability ration (T V) defined as follows: T V = t max t min . Different from the usual problem SALBP-2, our problem required extra data. So, each benchmark instance was supplemented by the number ñ of the manual operations and a partition of the set V into subset V = {1, 2, . . . , ñ} of the manual operations and subset V \ V = {ñ + 1, ñ + 2, . . . , n} of the automated operations. Numbers ñ were randomly chosen from the following set:

{⌈ n 10 ⌉ , ⌈ 2n 10 ⌉ , ⌈ 3n 10 ⌉ , ⌈ 4n 10 ⌉ , ⌈ 5n 10 ⌉ , ⌈ 6n 10 ⌉ , ⌈ 7n 10 ⌉ , ⌈ 8n 10 ⌉ , ⌈ 9n 10
⌉} , i.e. the percentages of the manual operations were close to 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%, and 90%, respectively. After determining the number ñ, the set V = {1, 2, . . . , ñ} was randomly chosen from the set V = { j 1 , j 2 , . . . , j n }. In addition, we determined numbers m of the workstations in different variants of the benchmark instances. In Tables 3, 4 and 5, number m was taken from the set {3, 4, 5, 6}. For the small instances presented in Table 6, number m was taken from the set {3, 4, . . . , n-2, n-1}. For each benchmark instance tested, several variants of the instance SALBP-2 have been randomly generated for solving them by Algorithm RAD. The variants of benchmark instances were deferred one from another by the number i as follows: instance name-i. These composite names of the instances are indicated in column 2 of Tables 3456. The instances are also numbered in column 1 through all Tables 3456.

For each instance presented in Tables 3456, Algorithm RAD calculated the minimal cycle time c, constructed the sets B(G, m), B(G, m, t), B 0 (G, m, t) and B ∞ (G, m, t), and calculated the stability radii ρ b i (t) for all optimal line balances b i ∈ B (G, m, t). The obtained computational results are summarized in Tables 3 and6 for the benchmark dataset given in [START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF], and in Tables 4 and5 for the benchmark dataset given in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF]. The CPU-time used for each instance is given in column 12 in minutes. If the needed CPU-time was greater than the allowed limit of 6 hours, then Algorithm RAD was stopped. The instances, which were not solved within 6 hours, are not presented in Tables 3456, except the instance with number 87 presented in Table 5. In particular, the instances with names 67, 69, 70, 71, 73, 74, and 75 from the benchmark dataset given in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF] were solved only for m = 2 and m = 3, since solving each of them for m = 4 needed CPU-time more than 6 hours.

The input data for each instance includes the operation number n (column 3), the workstation number m (column 4). The percentage of the manual operations λ = | V| |V| • 100% is given in column 5. Column 6 gives the Order Strength of the digraph G = (V, A). Using this input data, the program calculated the minimal cycle-time c given in column 7. The program calculated how many line balances |B(G, m)| exist (column 8 in Tables 3456), how many line balances |B(G, m, t)| are optimal (column 9), and how many optimal line balances |B 0 | = |B 0 (G, m, t)| are unstable (column 10). In column 11, values of the calculated stability radii are presented in the condensed form in a nonincreasing order of them. To determine all stability radii for the instance, a reader has to use column 11 along with columns 9 and 10 in the corresponding table. For example, column 9 and column 10 in Table 3 contain number 10 and number 4, respectively, for the instance named Mertens-2 (column 2) with instance number 2 (column 1). Column 11 for the instance Mertens-2 contains the following numbers: 1, . . . , 1, 0, . . . , 0. This means that instance Mertens-2 has ten optimal line balances, stability radii for four of them being equal to 0, and stability radii for six of them, 6 = 10 -4, being equal to 1. The program tested the condition of Theorem 3 for detecting the optimal line balances b i ∈ B(G, m, t) with infinite stability radii, ρ b i (t) = ∞. The instances with numbers 92, 98, 105, 106, 112, and 113 have optimal line balances, which save their optimality for all durations of the manual operations. For example, column 9 and column 10 in Table 6 contain number 442 and number 132, respectively, for the instance named Jackson-10 (column 2) with number 105 given in column 1. Column 11 for instance Jackson-10 contains the following: 146:∞; 164:1; 0, . . . , 0. This means that instance Jackson-10 has 442 optimal line balances, stability radii for 146 of them being infinite, stability radii for 164 of them being equal to 1, and stability radii for the remaining 132 optimal line balances being equal to 0.

In the computational experiments, the stability analysis was applied to twelve moderate-size instances with numbers 12, 77 -87 and to 102 small-size instances. Let us partition the set T of all 114 instances presented in Tables 3 -6 into four subsets:

T = U ∪ O ∪ D ∪ E with respect
to their stability radii. An instance is included in the set U if there exists at least one unstable optimal line balance for this instance, i.e. B 0 (G, m, t) ∅. The set U consists of 40 instances with the following numbers: 2, 6, 8 -13, 15 -21, 25, 26, 28, 30, 31, 33, 34, 36, 37, 69, 91, 92, 94 -96, 98 -106, 108. This is more than 35.08% of the instances tested. An instance is included in the set O if there is only one optimal line balance for this instance, i.e. |B(G, m, t)| = 1. The set Table 3: The cardinalities of the sets of line balances, optimal line balances, and stability radii for the instances given in [START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF] Instance O consists of 30 instances with the following numbers: 1, 5, 7, 14, 22, 35, 39, 42, 43, 50, 51, 54, 55, 58, 59, 62 -64, 66, 67, 70, 77, 79, 81, 83, 85, 86, 89, 93, 107. This is more than 26.31% of the instances tested. Due to Theorem 1, the optimal line balance for any instance from the set O is stable: B 0 (G, m, t) = ∅. Therefore, an intersection of the sets U and O is empty. An instance is included in the set D if it has at least two optimal line balances with the different stability radii, all optimal line balances being stable. The set D consists of 15 instances with the following numbers: 23, 27, 32, 40, 45, 49, 57, 65, 68, 73, 74, 80, 112 -114. This is more than 13.15% of the instances. The remaining instances generate the set

n m λ OS c |B(G, m)| |B(G, m, t)| |B 0 | ρ b r (t), CPU-time name b r ∈ B(G,
E = T \ {U ∪ O ∪ D}. Each in-
stance in the set E has more than one optimal line balances, these line balances being stable with the same stability radius. The set E consists of 29 instances with the following numbers: 3, 4, 24, 29, 38, 41, 44, 46 -48, 52, 53, 56, 60, 61, 71, 72, 75, 76, 78, 82, 84, 87, 88, 90, 97, 109 -111. Table 4: The cardinalities of the sets of line balances, optimal line balances, and stability radii for the instances given in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF] Instance This is more than 25.43% of the instances tested. Based on our computational results, one could make the following observations. For 51.74% = 26.31%+25.43% of the instances, which belong either to the set O or to the set E, constructing one Table 5: The cardinalities of the sets of line balances, optimal line balances, and stability radii for the instances given in [START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF] Instance optimal line balance is practically sufficient for solving the problem SALBP-2, since the optimal line balance is either unique for each instance from the set O or all optimal line balances have the same stability radius for each instance from the set E.

n m λ OS c |B(G, m)| |B(G, m, t)| |B 0 | ρ b r (t), CPU-time name b r ∈ B(G,
n m λ OS c |B(G, m)| |B(G, m, t)| |B 0 | ρ b r (t), CPU-time name b r ∈ B(G,
For the remaining 48.23% = 35.08%+13.15% of the instances, which generate the set U ∪ E, it is useful to construct more than one optimal line balances instead of a single one. If the instance belongs to the set U, then the first constructed optimal line balance b 0 ∈ B(G, m, t) may be unstable: b 0 ∈ B 0 (G, m, t). The optimality of the line balance b 0 is practically doubtful, since even infinitely small variations of the durations of manual operations may deprive its optimality.

For solving an instance from the set D, it is also not sufficient to construct only one optimal line balance, since the first constructed optimal line balance may have the smallest stability radius. The optimal line balance with a larger stability radius will remain optimal for a longer time of the lifespan of the assembly line than the optimal line balance with a smaller stability radius.

Even for the instance from the set E, it is useful to construct more than one optimal line balances, since all the constructed optimal line balances may be saved in an archive of the assembly line balances and then used for the faster re-balancing of the assembly line when variations of the operation durations will be larger than the stability radius of the used line balance. For any instance from the set U, it will be useful to construct a set of the k-best line balances, which may be used for the faster re-balancing of the assembly line.

The managerial implications of the stability results

We answer the following three questions: 1 Why and how are our stability results useful? 2 How does one obtain a stable optimal line balance if it exists? 3 How does one overcome a large size of the instance SALBP-2 for making the stability analysis either for all optimal line balances or for one of them? First of all, one can observe that an exact algorithm used for solving the NP-hard problem SALBP-2, traditionally, terminates once an optimal line balance is constructed, which may make sense if the numerical data is deterministic and fixed for the whole lifespan of the assembly line, while it is doubtful if the numerical data may vary. Since the duration of each manual operation may vary due to human factors, it is doubtful to provide a single optimal line balance, which corresponds to the deterministic initial operation durations without knowing its stability when the operation durations will vary. In contrast, Algorithm RAD presented in Section 5 constructs all alternative optimal line balances, calculate the stability radius for each of them, and allows a manager to select the one with the largest stability radius for the practical use. In essence, the traditional algorithm seeks one optimal line balance, while Algorithm RAD seeks all optimal line balances and allows a manager to select the most stable optimal line balance in the sense of having the largest stability radius. Since typically there are several or even many alternative optimal line balances, it is better to examine all alternative optimal ones and then select the one to one's most advantage instead of just arbitrarily choosing one. Our computational results indicate that it is more often to have alternative optimal line balances. Even in the case, there is only one optimal line balance b 0 (the set O), Algorithm RAD is still superior to a traditional one in the sense that Algorithm RAD offers an additional information on the stability radius ρ b 0 (t). This piece of information is useful especially for managers. If the variation of each manual operation is less than the stability radius ρ b 0 (t), one knows that there is no need for re-balancing the assembly line. Since the re-balancing is usually costly, there is an economic benefit by using our approach. In addition, a manager may be nervous and even make mistakes without this piece of information since she (he) simply does not know the right time for the re-balancing.

Second, our computational results given in Tables 3456indicate that there is a high probability that the first constructed optimal line balance b 0 ∈ B(G, m, t) is unstable (the set U), which means that even infinitely small variations of the operation durations may cause the line balance b 0 no longer optimal. Indeed, each instance in the set U has at least one unstable optimal line balance b 0 ∈ B 0 (G, m, t). Since the optimality of the unstable line balance b 0 is practically doubtful, more optimal line balances have to be constructed and thus it is useful to choose an optimal line balance with the largest stability radius. The calculation of stability radius ρ b 0 (t) > 0, b 0 ∈ B(G, m, t), may end up with the time-consuming comparing the line balances B(G, m). In the worst case, the optimal line balance b 0 have to be compared with most of the line balances from the set B(G, m) \ {b 0 }, which seems impossible for a large-size problem SALBP-2. However, thanks to Theorem 1 for such a large assembly line, it is possible to test whether there exists a stable optimal line balance or not. Due to Theorem 2 for such a large-size assembly line, it is also possible to test whether there exists an optimal line balance with the infinite stability radius or not. Note that testing the condition (3) of Theorem 1 for the optimal line balance b 0 ∈ B(G, m, t) and the condition of Theorem 2 may be realized for any problem SALBP-2, for which optimal line balance may be constructed by a branch-and-bound algorithm. Indeed, to construct all optimal line balances B(G, m, t) for the problem SALBP-2 after constructing one optimal line balance b 0 ∈ B(G, m, t) by the branch-and-bound algorithm, it is sufficient to consider further the branches of the already constructed solution tree, for which the lower bound on the cycle-time c(b r , t), which may be generated by this branch of the solution tree, is equal to the reached minimal cycle-times c(b 0 , t).

Third, our computational experiments on the usual laptop showed that the CPU-time for constructing the set B(G, m) of the line balances, the set B(G, m, t) of the optimal line balances, and calculating their stability radii is not large for a small assembly line and for some moderate assembly lines. Of course, for constructing the sets B(G, m) and B(G, m, t) for a large-size problem SALBP-2, a faster computer is needed. Thanks to formula (16) given in Lemma 1, one can estimate how many line balances must be compared with the optimal one to calculate the stability radius. If it is impossible to construct the whole set B(G, m), one can construct its subset and then save it in the archive of the line balances. It is also possible to restrict for testing the part of the assembly line around the bottleneck workstation, where the essential changes of the operation durations hold. We believe that due to the increasing speed of computers it will be possible to construct several optimal line balances or even the whole set B(G, m, t) for a large-size problem SALBP-2 with the large Order Strength of the digraph G = (V, A). It should be also noted that one can restrict the number of line balances under consideration. Due to this, the number of the tested line balances may be considerably smaller than |B(G, m)|. Next, we show the details of why stability analysis is useful (Section 7.1), how to restrict these calculations and how large-size problem SALBP-2 allows the stability analysis based on Algorithm RAD (Section 7.2).

Why is the stability analysis useful

In the assembly industry, the problem SALBP-2 arises either for a newly designed assembly line or for the currently used assembly line when the re-balancing will be required. The labor cost per assembly product may be estimated as a sum of the wage rates of all workstations multiplied by the cycle time c. Durations t = (t 1 , t 2 , . . . , t ñ), ñ ≤ n, of the manual operations are variable depending on the operators that have to be paid for the whole cycle time c irrespective of factual times used for their own operations. So, for the labor-intensive assembly line, a line balance generated for the fixed operation durations may result in a lower effectiveness and an increased production cost when the durations of the manual operations change. Furthermore, increasing the cycle-time c caused by changed durations of the manual operations will make ineffective the use of the expensive industrial robots making the automated operations. To avoid these drawbacks in the above cases, we developed the stability analysis of the problem SALBP-2 in Sections 2 -5. In particular, due to the stability analysis, one can use the optimal line balance, which remains optimal in the largest stability ball in space of the variations of the operation durations t. Using such most stable line balance will guarantee its optimality for a longer time of the lifespan of the assembly line. A knowledge of the stability radius of the current assembly line balance allows a factory to find the right time for the re-balancing of the assembly line if the cycle-time of the assembly line changes. If the variation of the durations of manual operations are no greater than the stability radius of the current assembly line balance, then there no a better line balance than the current one. Otherwise, re-balancing may decrease the current cycle-time of the assembly line. When the re-balancing will start, the archive of the previously constructed optimal line balances or k-best line balances may be used for the faster re-balancing of the assembly line. The time needed for the re-balancing is crucial if it must be realized with a stoppage of the assembly line.

How large may the problem SALBP-2 be for the stability analysis

The complete stability analysis of all optimal line balances B(G, m, t) based on Algorithm RAD is time-consuming for the problem SALBP-2 with the large size since Algorithm RAD includes a construction of line balances B(G, m), the testing of conditions of Theorems 1, 2, 3, or Corollaries 1 or 2, and the calculation of the stability radii for all optimal line balances. Our computational experiments on the laptop showed that the CPU-time for constructing the set B(G, m) of the line balances and the set B(G, m, t) of the optimal ones is restricted by 6 hours for the small assembly line and for some moderate ones with the large Order Strength of the digraph G = (V, A). Using Lemma 1, one can estimate how many line balances have to be compared with the optimal one to calculate its stability radius. If it is impossible to construct the whole set B(G, m, t), one can construct its subset and then save it in the archive of the competitive line balances. In order to increase the size of the problem SALBP-2, for which the complete stability analysis may be applied, one can decompose the problem SALBP-2 into several subproblems due to the precedence constraints determined by the digraph G = (V, A). As an illustration, we consider Example 4 with m = 11, n = 16, ñ = 7, t = ( t, t) = (t 1 , t 2 , t 3 , t 4 , t 5 , t 6 , t 7 , t 8 , t 9 , t 10 , t 11 , t 12 , t 13 , t 14 , t 15 , t 16 ) = (7,5,5,8,1,5,2,6,2,3,3,4,7,3,4,5). The set V = {1, 2, . . . , 7} includes all the manual operations. The set V \ V = {8, 9, . . . , 16} includes all the automated operations. The digraph G = (V, A) without transitive arcs for Example 4 is presented in Fig. 5. It is easy to be convinced that Example 4 is decomposable into Examples 1, 2, and 3, for which the stability analysis was already realized in Sections 2.2, 3.3, and 4.3, respectively. Using this decomposition, the complete stability analysis for Example 4 may be realized even without using a computer.

Since the computer speed will be more and more fast, it will be possible to construct several optimal line balances or even the whole set B(G, m, t) for the practical problem SALBP-2 with moderate and even large sizes. Using a powerful computer or supercomputer, one can construct a set of the potentially optimal line balances, i.e. the optimal line balances or k-best ones for the initial vector t of the operation durations. Then if the durations of the operations will change considerably, one can select an appropriate line balance from the archive of the optimal line balances. It should be also noted that the stability analysis must be realized once for the whole lifespan of the assembly line. In fact, it may be realized at the stage of designing a new line balance, i.e. at the off-line phase of exploiting the assembly line. Then the result of the stability analysis will be used at the on-line phase of using the assembly line when a manager has less time for computing.

Conclusion

Since the durations of manual operations are variable, it is impossible to construct the optimal line balance, which will be the best for all variable operation durations. Nevertheless traditionally, the solution procedure for the problem SALBP-2 ends when the first optimal line balance b 0 ∈ B(G, m, t) is constructed. Due to the computational results presented in Tables 3456, we can argue that for the problem SALBP-2 there is a high probability that the first constructed optimal line balance b 0 ∈ B(G, m, t) is unstable and so even infinitely small variations of the operation durations may destroy the optimality of the line balance b 0 at hand. Each instance in the set U has at least one unstable optimal line balance b r ∈ B 0 (G, m, t). The optimality of the unstable line balance b r is doubtful for the real assembly line, which is labor-intensive. Therefore, more optimal line balances have to be constructed for designing an optimal assembly line balance since the first constructed optimal line balance b 0 ∈ B(G, m, t) may be unstable if the instance belongs to the set U. Thus, for each practical instance of the problem SALBP-2 from the set U, it is not sufficient to construct only one optimal line balance as is done by a traditional exact algorithm for solving the problem SALBP-2. As there are several optimal line balances, it is useful to choose the optimal line balance with the largest stability radius. The algorithm for constructing optimal line balances and calculating their stability radii is given in Section 5. This algorithm is based on Theorems 1, 2, and 3, Corollaries 1 and 2, and Lemma 1 presented in Sections 4.1 and 4.2. In Section 3, we derived the set B ∞ (G, m, t) of the line balances with infinitely large stability radii (Theorem 2). Such line balances keep their optimality for any variation of the durations of the manual operations. The calculation of the stability radius ρ b 0 (t) > 0, b 0 ∈ B(G, m, t), is reduced to the time-consuming calculation on the set B(G, m) of the line balances. In the worst case, the optimal line balance b 0 have to be compared with almost all line balances from the set B(G, m) \ {b 0 }, which is impossible for most practical assembly lines because of their large sizes. Due to Theorem 1, one can easily test whether there exists a stable optimal line balance or not, and due to Theorem 2, one can easily test whether there exists an optimal line balance with the infinite stability radius or not even for such a large-size problem SALBP-2.

A possible research direction is a deeper investigation of the set B ∞ (G, m, t), since using the line balance with the infinite stability radius may be promising in the assembly industry. Further research may focus on developing more effective algorithms for enumerating all optimal line balances and calculating their stability radii. Another future research avenue may deal with the problem SALBP-E of maximizing the profit of the assembly line. The results obtained in this paper may be used for developing formula, algorithm, and software for calculating the exact value of the stability radius of the optimal line balance for the problem SALBP-E. Our stability approach may be applied to the labor-intensive disassembly line balancing problems. It is also interesting to modify the stability approach for the U-type assembly line balancing problems.

  B(G) denote the set of all assignments b r satisfying Condition I. The subset B(G, m) = {b 0 , b 1 , . . . , b h } of the set B(G) consists of all line balances. The cycle-time c(b r , t) for the line balance b r with the vector t = ( t, t) of the operation durations is determined as c(b r , t) = max m k=1 = t(V b r k ) is a workstation time. The line balance b 0 is optimal with the operation durations t = ( t, t) if it achieves a minimal cycle-time c as follows: Condition III. c = c(b 0 , t) = min {c(b r , t) : b r ∈ B(G, m)} .

Figure 1 :

 1 Figure 1: The precedence digraph G = (V, A) without transitive arcs for Example 1.

  the line balance b 0 remains optimal. The maximal value ρ b 0 (t) of the radius ρ of the stability ball O ρ ( t) is called a stability radius of the line balance b 0 .

Figure 2 :

 2 Figure 2: The precedence digraph G = (V, A) without transitive arcs for Example 2.

  {2}}. The condition (3) does not hold for the line balance b 6 , W(b 6 , t) = {{1}, {2}} {{2}} = W(b 0 , t) ∈ B(G, m, t), and for the line balance b 9 , W(b 9 , t) = {{1}, {2}} {{2}} = W(b 0 , t) ∈ B(G, m, t). Due to Theorem 1, the stability radii of the line balances b 6 and b 9 are equal to zero. We test the condition of Theorem 2 for the line balance b 0 . The equality V b 0 k = {i}, k ∈ {1, 2, 3, 4}, holds for each i ∈ V = {1, 2}, namely, V b 0 1 = {1} and V b 0 2 = {2}. The problem SALBP * -2 has the same input date as Example 2 has, except the initial vector is now determined as follows: t * = (0, 0, 3, 4, 7). Since the precedence digraph is the same, the problem SALBP * -2 has the line balances B(G, m) = {b 0 , b 1 , . . . , b 9 } as Example 2 has. The minimal cycle-time for the problem SALBP * -2 is equal to 7. The condition of Theorem 2 holds for the line balance b

Lemma 1 .

 1 Assume that b 0 ∈ B(G, m, t), b r ∈ B(G, m) \ {b 0 }, ñb r = max { | V b r k | : k ∈ {1, 2, . . . , m} } . There is no need to compare the line balance b 0 with the line balance b r if inequality δ(b 0 , b g , t) ≤ c(b r , t)c(b 0 , t) min { ñ, ñb r + ñb 0 } (16) holds for the line balance b g ∈ B(G, m) \ {b 0 , b r }. The proof of Lemma 1 is given in Appendix B, where it is assumed that the line balance b 0 is already compared with the line balance b g , and the bound ρ b 0 (t) ≤ δ(b 0 , b g , t) := ρ is obtained. Due to Lemma 1, the line balance b r ∈ B(G, m) \ {b 0 } may make smaller the achieved stability ball O ρ ( t) only if the inequality (16) does not hold. For each optimal line balance b g ∈ B(G, m, t) \ {b 0 }, the right-hand side of the inequality (16) is equal to zero since c(b g , t)c(b 0 , t) = 0 for each line balance b g ∈ B(G, m, t). Therefore, while calculating ρ b 0 (t), one has to compare the line balance b 0 with all optimal line balances b g ∈ B(G, m, t) \ {b 0 }. We obtain the following Corollary 2. If |B(G, m, t)| ≥ 2, then the optimal line balance b 0 ∈ B(G, m, t) has to be compared with all other optimal line balances b g ∈ B(G, m, t) \ {b 0 } in the course of calculating the stability radius ρ b 0 (t) using Theorem 3.

Figure 3 :

 3 Figure 3: The precedence digraph G = (V, A) without transitive arcs for Example 3.

  For the line balance b 2 , there exists a line balance b 0 ∈ B(G, m, t) such that the condition (3) does not hold: {{2}, {1, 3}} = W(b 2 , t) W(b 0 , t) = {{2}}. Due to Theorem 1, we obtain ρ b 2 (t) = 0. For the line balance b 0 , we obtain {{2}}

Figure 4 :

 4 Figure 4: The stability ball O ρ (t) with radius ρ = ρ b 0 (t) = 1 and center t = {2, 5, 1} for the line balance b 0 ∈ B(G, m, t).

Figure 5 :

 5 Figure 5: The precedence digraph G = (V, A) without transitive arcs for Example 4.

  ′ 1 , t ′ 2 , . . . , t ′ ñ, t ñ+1 , t ñ+2 , . . . , t n ) := (t ′ 1 , t ′ 2 , . . . , t ′

	t ′ ñ+1 , t ′ ñ+2 , . . . , t ′ n ), for which the workstation time	∑	i∈V br k	t ′ i is calculated. The second equality in (	ñ,

Table 1 :

 1 The characteristics of the instances from the dataset given in[START_REF] Scholl | Balancing and Sequencing of Assembly Lines[END_REF]

	Instance	n	t min	t max	∑	t i	OS	T V
	name
	1	2	3	4	5	6	7
	Mertens	7	1	6	29	52.38 6.00
	Bowman	8	3	17	75	75.00 5.67
	Jaeschke	9	1	6	37	83.33 6.00
	Jackson	11	1	7	46	58.18 7.00
	Mansoor 11	2	45	185	60.00 22.50
	Mitchell 21	1	13	105	70.95 13.00
	Roszieg	25	1	13	125	71.67 13.00
	Lutz1	32 100 1400 14140 83.47 14.00
	Hahn	53 40 1775 14026 83.82 44.38

Table 2 :

 2 The characteristics of the instances from the dataset given in[START_REF] Otto | Systematic data generation and test design for solution algorithms on the example of salbp-gen for assembly line balansing[END_REF]

	Instance	n	t min t max	∑	t i	OS	T V
	name
	1	2	3	4	5	6	7
	67	20 26 308	2942	50.5 11.85
	69	20 21	25	1972	54.7 11.90
	70	20 35 323	2985	50.5 9.23
	71	20 47 305	2957	53.2 6.49
	73	20 27 262	1933	50.5 9.70
	74	20 22 275	2792	50.5 12.50
	75	20 22 283	2886	50.5 12.86
	443	20 27 322	2933	81.6 11.93
	444	20 35 357	2879	80.0 10.20
	453	20 20 344	2859	84.2 17.20
	454	20 55 358	2855	82.6 6.51
	457	20 42 446	2886	82.6 10.62
	486	20 254 624	9141	83.7 2.46
	498	20 27 605	5304	85.3 22.41
	507	20 36 497	4330	85.3 13.81
	511	20 46 483	4281	84.7 10.50
	515	20 46 483	4281	84.7 10.50
	472	50 37 308	7403	90.4 8.32
	474	50 21 272	6464	90.4 12.95
	482	50 197 676 237100 90.4 3.43
	520	50 28 566 103030 89.7 20.21
	523	50 29 531	9799	89.6 18.3
	524	50 43 635 127810 89.6 14.77

Table 6 :

 6 The cardinalities of the sets of line balances, optimal line balances, and stability radii for the instances with small sizes

		Instance	n	m	λ	OS	c |B(G, m)| |B(G, m, t)| |B 0 |	ρ b r (t),	CPU-time
		name									b r ∈ B(G, m, t)	(min)
	1	2	3	4	5	6	7	8	9	10	11	12
	88	Bowman-4	8	3 50 75.00 28	68	3	0	0.33, 0.33, 0.33	0.0019
	89	Bowman-5	8	4 88 75.00 22	165	1	0	0.25	0.0028
	90	Bowman-6	8	5 25 75.00 17	225	2	0	1, 1	0.0024
	91	Bowman-7	8	6 50 75.00 17	176	22	13	5:1.5; 4:1; 0,..., 0	0.0043
	92	Bowman-8	8	7 25 75.00 17	74	33	6	27:∞; 0,..., 0	0.0060
	93	Jaeschke-5	9	3 56 83.33 13	95	1	0	0.25	0.0016
	94	Jaeschke-6	9	4 89 83.33 10	294	4	3	0.25, 0, 0, 0	0.0024
	95	Jaeschke-7	9	5 67 83.33 9	535	27	27	0,..., 0	0.0029
	96	Jaeschke-8	9	6 22 83.33 8	595	16	6	0.5,..., 0.5, 0,..., 0	0.0111
	97	Jaeschke-9	9	7 33 83.33 7	401	15	0	1,..., 1	0.0106
	98 Jaeschke-10 9	8 33 83.33 6	150	24	12	12:∞; 0,..., 0	0.0021
	99	Jackson-4	11 3 91 58.18 16	543	7	7	0,..., 0	0.0051
	100	Jackson-5	11 4 64 58.18 12	2997	9	9	0,..., 0	0.0216
	101	Jackson-6	11 5 36 58.18 11	9414	132	116	15:0.33; 0.25;	0.1514
											0,. . . , 0
	102	Jackson-7	11 6 18 58.18 9	18378	286	136	1,..., 1, 0,..., 0	2.8625
	103	Jackson-8	11 7 27 58.18 8	23171	84	64	1,..., 1, 0,..., 0	2.9405
	104	Jackson-9	11 8 36 58.18 7	18953	34	16	0.5,...,0.5, 0,...,0	2.0204
	105 Jackson-10 11 9 36 58.18 7	9747	442	132	146:∞; 164:1;	5.2337
											0,. . . , 0
	106 Jackson-11 11 10 55 58.18 7	2874	802	264	461:∞; 77:1;	6.3924
											0,. . . , 0
	107 Mansoor-4 11 3 36 60.00 63	471	1	0	0.33	0.0049
	108 Mansoor-5 11 4 91 60.00 48	2559	7	3	0.25,..., 0.25,	0.0217
											0, 0, 0
	109 Mansoor-6 11 5 55 60.00 45	7965	165	0	0.25,..., 0.25	0.3818
	110 Mansoor-7 11 6 73 60.00 45	15509	1408	0	0.25,..., 0.25	20.6506
	111 Mansoor-8 11 7 45 60.00 45	19631	4180	0	0.33,..., 0.33	128.163
	112 Mansoor-9 11 8 36 60.00 45	16219	6121	0	655:∞; 27:	262.090
											1.67; 5439:1
	113 Mansoor-10 11 9 64 60.00 45	8468	4870	0	50:∞; 4820:0.5	191.463
	114 Mansoor-11 11 10 82 60.00 45	2544	2011	0	1720:1.5; 291:0.5	32.2215

Acknowledgment

The authors are grateful to the anonymous referees for their useful suggestions on the early draft of this paper. The first and second authors acknowledge the research grant from Ministry of Science and Technology, Taiwan.

Appendix A. The proof of Theorem 3

Assume that for the line balance b 0 ∈ B(G, m, t), there does not exist another optimal line balance b s ∈ B (G, m, t) such that the condition (3) holds. Due to Theorem 1, the stability radius ρ b 0 (t) is strictly positive: ρ b 0 (t) > 0. Assume also that the stability radius ρ b 0 (t) cannot be infinitely large: ρ b 0 (t) < ∞. First, we consider the following case (j).

Case (j): B(G, m, t) = {b 0 }. In order to calculate the value of the stability radius ρ b 0 (t) > 0, we shall look for a line balance b r ∈ B(G, m) \ {b 0 } and for a vector t ϵ = (t ϵ 1 , t ϵ 2 , . . . , t ϵ ñ) ∈ R ñ + such that the strict inequality c(b r , t ϵ ) < c(b 0 , t ϵ ) (A.1) holds, where t ϵ = ( t ϵ , t) and the vector t ϵ may be as close as desired to the vector t provided that the inequality (A.1) holds. Since the value c(b 0 , t) linearly depends on the components of the vector t = (t 1 , t 2 , . . . , t ñ), before reaching the desired strict inequality (A.1) via a continuous change of the components of the vector t, we first reach equality

for an appropriate vector

+ of the operation durations. For such a vector t ′ , the optimal line balance b 0 becomes unstable, i.e.

Due to Theorem 1, from the equality (A.3), it follows that there exists a line balance b r ∈ B(G, m, t ′ ) such that condition W(b 0 , t ′ ) ⊆ W(b r , t ′ ) does not hold. Hence, we can construct a vector t ϵ , for which the inequality (A.1) holds and d( t ϵ , t ′ ) = ϵ, (A.4) where a positive number ε ∈ R 1 + may be as small as desired. Thus, the calculation of the stability radius ρ b 0 (t) for the line balance b 0 ∈ B(G, m, t) is reduced to the construction of the vector t ′ ∈ R ñ + , which is the closest one to the vector t provided that the equalities (A.2) -(A.4) hold. To obtain the desired vector

in the case (j), we shall compare the line balance b 0 with all non-optimal line balances b r ∈ B(G, m) \ {b 0 }.

will be added to the duration

and the same value δ (b r ,k) b 0 ,u will be subtracted from the duration t j of each operation

It should be noted that in the latter modification (A.7) of the initial vector t ∈ R n + of the operation durations, the component t

+ may appear negative (the negative component of the modified vector is not allowed). In order to obtain a nonnegative modified vector t ′ ∈ R n + , which is the closest one to the vector t provided that the equalities (A.2) -(A.4) hold, we shall test operations from the set V b r k \ V b 0 u in a non-decreasing order of their durations. It is easy to be convinced that a non-negative vector t ′ ∈ R n + will be obtained if the value δ (b r ,k) b 0 ,u defined in (A.5) will be substituted in (A.6) and (A.7) by the value

Thus, in order to obtain the minimal distance d(t, t ′ ) between the desired vector t ′ and the initial vector t, one has to take the following maximum on k:

then the following minimum on u:

and then the following minimum on

Let b r be a line balance, just for which the value δ(b 0 , t) is reached in (A.11). We can obtain the desired vector t ′ ∈ R n + via a substitution of the value δ (b r ,k) b 0 ,u in (A.6) and (A.7) by the value δ(b 0 , t) defined in (A.11). For such a vector t ′ and for the line balance b r , the equalities (A.2) and (A.3) must hold. Furthermore, due to the equalities (A.11), the distance d( t, t ′ ) is minimal for all modified vectors of the operation durations and for all line balances b r ∈ B(G, m) \ B(G, m, t) = B(G, m) \ {b 0 }, for which the equality (A.2) holds. Thus in the case (j), we obtain

Next, we have to show how to obtain a vector t ϵ ∈ R n + from the vector t ′ ∈ R n + such that the inequality (A.1) and the equality (A.4) hold, where a value ϵ ∈ R 1 + may be chosen as an infinitely small non-negative real number. Let t i t ′ i in the vectors t and t ′ , i.e. the duration of the operation i ∈ V is modified in the new vector t ′ . Note that at least one such an operation i has to exist in the set V since the equality (A.3) and the inequality ρ b 0 (t) > 0 hold. Since the vector t ′ is defined in (A.6) and (A.7), the above operation i has to belong either to the set

In the former case, we set t ϵ i := t ′ i + ϵ. In the latter case, we set t ϵ i := t ′ i -ϵ. Other components of the vector t ϵ will remain the same as in the vector t ′ , i.e. t ϵ j = t ′ j for all operations j ∈ V = {1, 2, . . . , n} with j i. It is easy to see that the equality (A.2), which is valid for the vector t ′ , implies the inequality (A.1) for the newly constructed vector t ϵ . Since a real number ϵ ∈ R 1 + may be chosen as small as desired, we obtain

From the inequalities (A.12) and (A.13), we conclude that equality ρ b 0 (t) = δ(b 0 , t) holds in the case (j). Next, we consider the remaining possible case (jj).

Case (jj): B(G, m, t) \ {b 0 } ∅. Similarly as in the case (j), we can calculate the value

where δ b r ,k b 0 ,u is determined in (A.8). The first minimum in the right-hand side of the equality (A.14) has to be taken for all non-optimal line balances b r ∈ B(G, m) \ B(G, m, t). In the case (jj), along with calculating δ(b 0 , t), we have to compare the line balance b 0 with all other optimal line balances b s ∈ B(G, m, t), where b s b 0 .

Let

) will be reached if the following value .15) will be added to the duration t i of each operation i ∈ V b 0 u :

and the same value ∆ (b r ,k) b 0 ,u will be subtracted from the duration t j of each operation j ∈ V \ V b s u :

(A.17)

A non-negative real vector t ′ will be obtained if the value ∆ (b s ,k) b 0 ,u defined in (A.15) will be substituted by the value ∆ b s ,k b 0 ,u defined in (A.18): .18) In order to obtain the minimal distance d(t, t ′ ) of the desired vector t ′ to the vector t, one has to take the following maximum on k:

∆ b s ,k b 0 ,u , and then the following minimum on b r ∈ B(G, m, t) \ {b 0 }:

Arguing similarly as in the case (j), one can show that inequality ρ b 0 (t) ≥ min{δ(b 0 , t), ∆(b 0 , t)} holds in the case (jj). Similarly as in the case (j), one can construct a vector t ϵ ∈ R n + from the vector t ′ ∈ R n + such that the inequalities (A.1) -(A.4) hold. Arguing similarly as in the case (j), one can show that inequality ρ b 0 (t) ≤ min{δ(b 0 , t), ∆(b 0 , t)} holds in the case (jj). Summarizing, we conclude that equality ρ b 0 (t) = min{δ(b 0 , t), ∆(b 0 , t)} holds in the case (jj). Thus, if ρ b 0 (t) 0, equality ρ b 0 (t) = min{δ(b 0 , t), ∆(b 0 , t)} holds and Theorem 3 is proven.

As the inequalities ρ b 0 (t) ≤ δ(b 0 , b g , t) ≤ δ(b 0 , b r , t) hold, the value δ(b 0 , b r , t) cannot be smaller than the value δ(b 0 , b g , t). Therefore, there is no need to consider the line balance b r in the course of the stability radius calculation using formula (12). Lemma is proven.