Feifeng Zheng

Junkai He

Feng Chu

Ming Liu
email: mingliu@tongji.edu.cn

A new distribution-free model for disassembly line balancing problem with stochastic task processing times

Keywords: remanufacturing, end of life products, disassembly line design, stochastic task processing times, distribution-free model

Effective conduct with End of Life (EOL) products is a hot research topic in green and smart manufacturing. For EOL product recycling and remanufacturing, a fundamental problem is to design an efficient disassembly line under consideration of stochastic task processing times. This problem focuses on selecting alternative task processes, determining the number of opened workstations, and assigning operational tasks to the workstations. The goal is to minimise the total cost consisting of workstation operational cost and hazardous component processing cost. Most existing works assume that the probability distribution of task processing times can be estimated, however, it is often not likely to access the complete probability distribution due to various difficulties. Therefore, this study investigates disassembly line design with the assumption that only the mean, standard deviation and an upper bound of task processing times are known. Our main contributions include: (i) a new decomposition color graph is proposed to intuitively describe all possible processes, (ii) a new distribution-free model is proposed, and (iii) some problem properties are established to solve the model. Experimental results show that the distribution-free model can effectively deal with stochastic task processing times without given probability distributions.

Introduction

Remanufacturing industry has been growing fast in the last decade due to its increasing benefits in protecting natural environment, saving non-renewable resources and reducing pollution and waste, etc. However, complicated recycling process for End of Life (EOL) products and high operation cost become two major obstacles for its further development. Existing methods for traditional manufacturing are not likely to be applied directly to remanufacturing management because of its processing specificities. It is a big challenge to develop advanced technologies and creative methods to overcome these barriers. Especially, how to efficiently forward EOL product recycling is one of the popular domains in green and intelligent manufacturing.

Previous works have stressed that line balancing design is an essential and important job in assembly or disassembly operational management [START_REF] Dolgui | Branch and Bound Algorithm for a Transfer Line Design Problem: Stations with Sequentially Activated Multi-spindle Heads[END_REF][START_REF] Dolgui | MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines[END_REF]Guschinskaya 2012, Dolgui, Guschinsky, and[START_REF] Dolgui | Enhanced Mixed Integer Programming Model for a Transfer Line Design Problem[END_REF]. Disassembly line design mainly decides an optimal disassembly process, and assigns the corresponding operational tasks to a number of opened workstations such that the total processing cost is minimised. For better understanding disassembly line operations, we use Figure 1 to illustrate a disassembly line where there are totally three tasks processed in two workstations. An EOL product is decomposed into assemblies A 1 and A 2 by task 1 in workstation 1. Then two tasks 2 and 3 are handled in workstation 2, outputting the final four components. Disassembly lines have to respect the following physical or operational constraints.

Precedence constraint has to be respected and some tasks can only be executed after their precedent operations, respectively, due to physical or structural features of products. In Figure 1, for example, tasks 2 and 3 cannot be started before task 1. Besides, cycle time constraint requires that the total processing time of tasks handled on each workstation cannot exceed some given cycle time [START_REF] Battaïa | A Taxonomy of Line Balancing Problems and Their Solution Approaches[END_REF]. Hazardous components in EOL products, such as batteries in electronic products, usually require additional operations and cost because they may cause pollution or danger.

The deterministic disassembly line design problem is commonly known as disassembly line balancing problem (DLBP) which was introduced by [START_REF] Güngör | Disassembly Line Balancing[END_REF]. In reality, however, task processing times are usually stochastic or uncertain due to the following factors: (i) different EOL products have non-uniform structures and task processing times; (ii) unknown damage degree may also enhance difficulty to estimate task processing times; and (iii) manual processing effectiveness varies with work rate, skill level and motivation [START_REF] Battaïa | A Taxonomy of Line Balancing Problems and Their Solution Approaches[END_REF]. Hence, many existing works model this uncertainty and assume that specific probability distributions of task processing times are known beforehand [START_REF] Gamberini | A Multiple Single-pass Heuristic Algorithm Solving the Stochastic Assembly Line Rebalancing Problem[END_REF]Bentaha, Battaïa, and Dolgui 2014a;Mosadegh, Ghomi, and Guer 2017, etc.).

As pointed out in [START_REF] Ng | Distribution-free Vessel Deployment for Liner Shipping[END_REF], there might be a lack of historical data to estimate these distributions or functions with confidence, and existing models with processing time probability distributions may not be appropriate for DLBP, at least in some cases. Motivated by the above observation, we focus on studying the DLBP problem with partial knowledge of probability distribution, i.e. the mean, standard deviation and upper bound of task processing times. It also requires an event probability such that the operating time of each workstation does not exceed the given cycle time (Bentaha, Battaïa, and Dolgui 2015a). We adopt the modelling method proposed in [START_REF] Ng | Distribution-free Vessel Deployment for Liner Shipping[END_REF], and present a new distribution-free model. The main contributions of this work include:

(1) A new decomposition colour graph is proposed to describe various decomposition processes of EOL products so that potential disassembly processes can be more clearly shown, compared with existing decomposition graphs in literature.

(2) A distribution-free model is developed for DLBP with stochastic task processing times, where the decision-maker only needs the knowledge of the mean, standard deviation and an upper bound of task processing times. (3) Several problem properties are established, and then a fast algorithm is constructed for solving the proposed distribution-free model.

The remainder of this paper is organised as follows. In Section 2, a brief literature review is given. Section 3 proposes a decomposition colour graph, and describes the considered problem. We build a new distribution-free model in Section 4, and present a few problem properties which are applied in solving the proposed model in Section 5. Section 6 provides several case studies to evaluate proposed method. Finally, we summarise this work in Section 7.

Literature review

The DLBP problem under non-deterministic environment has been well studied in literature [START_REF] Güngör | A Solution Approach to the Disassembly Line Balancing Problem in the Presence of Task Failures[END_REF][START_REF] Altekin | Task-failure-driven Rebalancing of Disassembly Lines[END_REF][START_REF] Paksoy | Mixed Model Disassembly Line Balancing Problem with Fuzzy Goals[END_REF][START_REF] Giri | Coordinating a Supply Chain under Uncertain Demand and Random Yield in Presence of Supply Disruption[END_REF]Ilgin, Akçay, and Araz 2017, etc.). We first review previous studies for the scenario with stochastic task processing times. Most of them follow some specific probability distributions. We then review existing literature that applies distribution-free models to handle processing time uncertainty.

DLBP with stochastic task processing times

A lot of previous works have focused on the uncertainty of task processing times in disassembly lines. [START_REF] Gamberini | A Multiple Single-pass Heuristic Algorithm Solving the Stochastic Assembly Line Rebalancing Problem[END_REF] studied a disassembly line re-balancing problem so as to minimise the total expected completion cost. The probability of having incomplete tasks was the main consideration in the stochastic situation. Different probability scenarios were used in the proposed heuristic algorithm. Bentaha, Battaïa, and Dolgui (2014a) investigated the DLBP where task processing times are random variables with known probability distributions. They developed a stochastic programming model which chooses the best disassembly alternative for an EOL product, and assigned the corresponding disassembly tasks to workstations to minimise the line cost. Then, a sample average approximation method integrating Monte Carlo sampling and L-shaped algorithm was proposed to solve the model. Bentaha et al. (2014) presented a mathematical model for designing disassembly lines to maximise the line profit, i.e. the difference between the revenue generated by the retrieved components and the line operation cost. They proposed an exact solution method based on Monte Carlo sampling to deal with the uncertainties. [START_REF] Mosadegh | Heuristic Approaches for Mixed-model Sequencing Problem with Stochastic Processing Times[END_REF] proposed a stochastic DLBP model to minimise expected total work overload. They employed a dynamic programming model as well as two greedy heuristics to solve the problem. The problem was further modelled as a shortest path problem, and solved by a Dijkstra's algorithm-based heuristic. [START_REF] Altekin | Remedial Actions for Disassembly Lines with Stochastic Task Times[END_REF] incorporated remedial actions into profit-oriented disassembly lines with stochastic task processing times, where partial disassembly is allowed. They introduced two types of remedial operations, i.e. stopping the line for Finish-type tasks and offline disassembly for Pass-type tasks. For other related work, one may refer to [START_REF] Dolgui | Scenario Based Robust Line Balancing: Computational Complexity[END_REF], [START_REF] Tiwari | A Collaborative Ant Colony Algorithm to Stochastic Mixed-model U-shaped Disassembly Line Balancing and Sequencing Problem[END_REF], [START_REF] Rossi | Maximizing the Robustness for Simple Assembly Lines with Fixed Cycle Time and Limited Number of Workstations[END_REF][START_REF] Altekin | A Comparison of Piecewise Linear Programming Formulations for Stochastic Disassembly Line Balancing[END_REF]. Most of the above literature assumes that a complete probability distribution of task processing time is known as a prior.

Some authors have considered the case where EOL products contain hazardous components, and it consumes additional time or cost to disassemble these components (Bentaha, Battaïa, and Dolgui 2013b). Bentaha, Battaïa, and Dolgui (2014c) investigated the profit-oriented disassembly line balancing problem considering partial disassembly, presence of hazardous components and known probability distributions of task processing times. Bentaha, Battaïa, and Dolgui (2014d) further adopted Lagrangian relaxation and Monte Carlo sampling technique for solving the profit-oriented model. Bentaha, Battaïa, and Dolgui (2013a) developed a second-order cone programming model with convex piecewise linear functions to draw lower and upper-bounding schemes in dealing with processing time uncertainties. Bentaha et al. (2015) applied the same approaches to solve the scenario where the cycle time constraints are jointly satisfied with a predetermined probability level.

Distribution-free models

As the probability distributions of task processing times may not always be well estimated, some authors developed efficient approaches, such as the distribution-free model, to handle this kind of problems with a partial knowledge of probability distributions. [START_REF] Ng | Distribution-free Vessel Deployment for Liner Shipping[END_REF] considered a vessel deployment problem for linear shipping, in which a new distribution-free optimisation model was proposed. The mean, standard deviation and an upper bound of the uncertain demand are required. [START_REF] Ng | Container Vessel Fleet Deployment for Liner Shipping with Stochastic Dependencies in Shipping Demand[END_REF] further relaxed the input requirements such that only the mean and the standard deviation of shipping demand are provided.

The distribution-free approach has also been applied to stochastic inventory modelling [START_REF] Lee | The Effect of Advertising on the Distribution-free Newsboy Problem[END_REF][START_REF] Kwon | A Minimax Distribution-free Procedure for a Newsvendor Problem with Free Shipping[END_REF][START_REF] Sarkar | Periodic Review Fuzzy Inventory Model with Variable Lead Time and Fuzzy Demand[END_REF], and two-sample location statistical analysis for testing the distribution homogeneity of different samples [START_REF] Rousson | On Distribution-free Tests for the Multivariate Two-sample Location-scale Model[END_REF][START_REF] Gaur | A New Class of Distribution-free Tests for Testing Ordered Location Parameters Based on Sub-samples[END_REF][START_REF] Ozturk | Distribution-free Two-sample Methods for Judgment Post-stratified Data[END_REF].

To the best of our knowledge, there is no result for the DLBP problem with stochastic task processing times such that only a part of knowledge on probability distribution is accessible.

Problem description

In the section, we first introduce a new so-called decomposition colour graph to intuitively describe all possible decomposition processes for an EOL product. Then we describe the studied DLBP with its fundamental assumptions. An example of disassembling a hand light is further given for better understanding disassembly schema.

Decomposition colour graph

A decomposition structure consists of subassemblies and disassembly tasks. Corresponding to these, a decomposition colour graph G = (V, A) has two types of vertices ✷ and , as shown in Figure 2. A rectangle ✷ denotes a subassembly (i.e. a state), and a circle represents a disassembly task (i.e. an action). Let S ={ ✷} and T ={ } . Then the vertex set V = S ∪ T and S ∩ T = ∅. In each rectangle, there is a set of digits representing the indices of product components in the subassembly. Especially, the source of the graph, denoted by S 0 , is a rectangle representing an initial subassembly that contains all the components of the EOL product.

In the graph G, A is the set of arcs each of which connects between a subassembly vertex ✷ and a task vertex . Especially, an arc starting from a subassembly vertex and ending at a task vertex states a feasible and possible disassembly way for subassembly. An arc from a task vertex to a subassembly vertex represents the resulting subassemblies by the task. Between any two neighbour vertices, there may be several arcs with different colours. All the arcs in the same colour together with task vertices in G constitute a decomposition or disassembly process.

Definition 1 A decomposition color graph is a directed acyclic one with colored arcs, G = (V, A), where V ={v 1 ,v 2 ,..., v u } is a set of vertices, and A ={a 1 , a 2 ,...,a v } is a set of colored arcs, i.e. a k = (v i ,v j ) with v i ,v j ∈ V . The vertex set V can be partitioned into two disjoint subsets S ={✷} and T ={ }such that V = S ∪ T and S ∩ T = ∅.Ifa k = (v i ,v j ), then either v i ∈ S and v j ∈ T or v i ∈ T and v j ∈ S. Now, we give the calculation of the number of decomposition processes in the decomposition colour graph. If there exists at least one subassembly vertex with out-degree larger than one, then let X be the complete set of such subassembly vertices, and |X | the set size. Otherwise, if all the subassembly vertices with out-degree equal to one, then the set contains only the source vertex, i.e. X ={ S 0 }.Let p i be the out-degree of any subassembly vertex v i , and n the number of decomposition processes in graph G. Then we have the following conclusions.

Proposition 1 In a decomposition color graph G, the number of decomposition processes or arc colors, i.e. n, is equal to

v i ∈X p i -(|X |-1). Proof. First, if the set X contains a single subassembly vertex v i , i.e. |X |=1, then it is trivial that n = p i .
Now consider the case where |X |≥2. Let v k be the leftmost vertex of set X in the graph G. There are p k decomposition processes induced by the vertex by the previous argument. For each of the rest

|X |-1 vertices in X ,sayv i ∈ X \{v k },it induces p i -1 more decomposition processes. It implies that n = v i ∈X p i -(|X |-1) in this case.
The proposition is established.

Below we give an example to illustrative a decomposition colour graph. The EOL product consists of five components {1, 2, 3, 4, 5}, which can be observed in the rectangle box besides the source vertex S 0 in Figure 3. By the figure, component 3 is a hazardous one, which is disassembled via task T 7 . Note that the sink task T e in the graph is a dummy task vertex, since its preceding vertex S e is a subassembly vertex that contains all the disassembled EOL product components. That is, all the components have already been disassembled in the vertex S e . Moreover, each hazardous component is labelled by an underline of the corresponding index, and a task that outputs a hazardous component is labelled by a gray circle.

Since there is only a single subassembly vertex, i.e. the source of the graph, with out-degree larger than one in the figure, we conclude by Proposition 1 that there are only two possible decomposition processes. All the red arcs together with task vertices connected by the arcs constitute one decomposition process, and so do the blue arcs and their connected vertices.

According to the description of decomposition processes, we have the following observations.

Observation 1 A decomposition process consists of a partial of tasks in the decomposition colour graph.

Observation 2 Any selected decomposition process indicates the number of disassembly tasks as well as their precedence relations.

Observation 3 A decomposition process has no knowledge on the assignment of tasks to the workstations together with the number of opened workstations.

By the above observations, one decomposition process describes a complete and feasible procedure that consists of disassembly tasks with their precedence constraints. Different decomposition processes are reflected via different colours in the proposed graph.

The studied DLBP problem

The studied DLBP problem is to decide a disassembly line with a single disassembly product consideration. A solution to this problem consists of the selection of alternative tasks which forms a specific decomposition process, the determination on the number of opened workstations together with the assignment of selected tasks to the workstations. Bentaha, Battaïa, and Dolgui (2015a) studied the scenario where stochastic processing times of tasks are known with a normal probability distribution. They also assumed that the EOL product contains some hazardous components, and handling such components requires extra cost.

We study a similar case in this work, however, only the knowledge of the mean, standard deviation and an upper bound of task processing times are required, instead of the complete probability distribution. This work is motivated by the observation that it is not always possible to obtain the complete distribution of stochastic task processing times in practice due to various difficulties. We first propose a new distribution-free model for the DLBP, then provide some problem properties for solving the proposed model.

The objective of the problem is to design a disassembly line under stochastic situation so as to minimise the total processing cost, which consists of both workstation operation cost and hazardous component handling cost. The remaining of this work follows the fundamental assumptions below:

(1) the precedence constraints between tasks have to be respected;

(2) a disassembly task may be a candidate for different disassembly processes;

(3) the given cycle time for any disassembly line cannot be exceeded; (4) more than one task can be assigned to one opened workstation;

(5) handling hazardous tasks of the EOL product causes an extra cost; (6) The processing time of each task is a stochastic variable with knowledge of its mean, standard deviation and upper bound; (7) the processing times of any two tasks are independent from each other.

In the following, we give an example of hand light decomposition process for better understanding the DLBP. As shown in Figure 4, a hand light can be decomposed into seven components by a disassembly line as follows: battery, bulb, cover, glass, head housing, main housing and spring, which are denoted from 1 to 7, respectively.

In the example, we conclude by Proposition 1 that there are three possible decomposition processes for disassembling a hand light. We adopt decomposition colour graph to describe all the possible decomposition processes. The arcs in the three possible decomposition processes are labelled with three different colours, i.e. blue, red and black. All the arcs in the same colour and the tasks vertices connected by the arcs constitute of a decomposition process (see Figure 5), which specifies the processing sequence or task precedence. In the figure, it indicates that component 2, which is to be disassembled by task T 7 , is a hazardous one.

The distribution-free model

The critical hypothesis in this work is that it is not always possible to specify the accurate distribution in practice. In this section, we propose a distribution-free model under the previously mentioned assumptions.

Distribution-free constraint construction

In order to develop the distribution-free model, a distribution-free constraint is constructed below. With a similar idea to Ng (2014), we first assume that the stochastic processing time t i for task i is expressed as:

t i = d i (1 + Z i ), i ∈ T , where d i = E[t i ]
is the mean processing time of task i, and Z i is a random variable representing the deviation proportion from the mean. We also assume that there exists some positive number b i satisfying Z i ≤ b i . Therefore, t i ≤ d i (1 + b i ) for any i ∈ T . Now, we recall the chance constrained inequality in Bentaha, Battaïa, and Dolgui (2015a).

P r i∈I t i ( ξ)x ij ≤ C, ∀ j ∈ J ≥ 1 -α, ( 1
)
where J is the available workstation set, and x ij is a binary variable equal to 1 if task i is assigned to workstation j.The above constraint ensures that the operating time for any opened workstation is smaller than or equal to the cycle time C with a probability of 1α.

Next, we replace the above chance constrained inequality with a new constraint below [START_REF] Ng | Distribution-free Vessel Deployment for Liner Shipping[END_REF], which is based on the property or conversion analysis in Section 5.

i∈T

(d i + µ i )x ij ≤ C, ∀ j ∈ J (2)
where µ i ≥ 0 is some real number to be explained and solved later. The inequality indicates that the operating time of any opened workstation j cannot exceed the cycle time C.

Problem formulation

In the following, we give basic notations, define decision variables, and then describe the distribution-free model. β j probability related to the operating time limit of workstation j, where j ∈ J ; d i mean processing time of task i ∈ T , and d i > 0; µ i a non-negative real-number parameter which reflects the deviation from the mean processing time of task i ∈ T .

Decision variables

x ij a binary variable equals 1 if task i is assigned to workstation j; 0 otherwise, where i ∈ T , j ∈ J ;

x ej a binary variable equals 1 if the dummy task T e is assigned to workstation j; 0 otherwise, where j ∈ J ; h j a binary variable equals 1 if a hazardous task is assigned to workstation j; 0 otherwise, where j ∈ J .

The distribution-free model: min

⎧ ⎨ ⎩ C • C f j∈J jx ej + C • C h j∈J h j ⎫ ⎬ ⎭ .

Subject to:

Constraint (2)

i∈A 0 j∈J x ij = 1( 3 ) j∈J x ij ≤ 1, ∀i ∈ T (4) j∈J x ej = 1( 5 ) j∈J j • x ij ≤ j∈J j • x ej , ∀i ∈ T (6) i∈Q k j∈J x ij = i∈P k j∈J x ij , ∀k ∈ S \{0} (7) i∈Q k x iv ≤ i∈P k v j=1
x ij , ∀k ∈ S \{0}, ∀v ∈ J (8)

h j ≥ x ij , ∀ j ∈ J , ∀i ∈ H (9) x ej , x ij , h j ∈{ 0, 1}, ∀i ∈ T , ∀ j ∈ J (10)
The objective function is to minimise the total cost consisting of two parts: (i) the operating cost of opened workstations, i.e. C • C f j∈J jx sj , and (ii) the cost for handling hazardous tasks, i.e. C • C h j∈J h j . As the dummy task T e is assigned to the last opened workstation j with x ej = 1, the value of j defines the number of opened workstations.

Constraint (3) ensures that one of the disassembly processes must be selected for disassembly. Constraint (4) indicates that each task is to be assigned to at most one workstation. Constraints ( 5) and ( 6) together state that the dummy task T e is assigned to the last opened workstation whose index j is determined by x ej = 1. Constraint (7) describes the flux conservation and guarantees that only one successor is selected for each subassembly S k , k ∈ S \{0}. Constraint (8) presents the precedence constraint between consecutive disassembly tasks, i.e. for any task, its preceding task must be assigned to a smaller-indexed or the same workstation. Constraint (9) determines the workstation that handles hazardous tasks. The number of workstations dealing with hazardous tasks is equal to j∈J h j . Constraint (10) gives the variation ranges of decision variables.

Solution approaches

We first conduct problem property analysis, and then propose a fast algorithm for solving the above distribution-free model in this section.

Property analysis

For the distribution-free model, in order to explain the reason of using inequality (2) in place of the chance constrained inequality (1)inBentaha, Battaïa, and Dolgui (2015a), we present several problem properties by the following Lemmas and Propositions.

As inequality (1) denotes a joint chance constrained form for all opened workstations, while proposed inequality ( 2)is with independent chance constrained form for each opened workstation, we first prove their consistency via Proposition 2.

Proposition 2 For each opened workstation j, its operating time should remain within the given cycle time, with a probability at least 1β j , where j∈J (1β j ) = 1α. Using the expression of inequality (1), we have

P r i∈T t i ( ξ)x ij ≤ C ≥ 1 -β j , ∀ j ∈ J .
Proof. Bentaha, Battaïa, and Dolgui (2015a) assumed the independence between different workstations. Equivalently, it is independent for each opened workstation to maintain its operating time no more than the given cycle time C. We apply the well-known equation P(AB) = P(A)P(B) for any two independent events A and B, where P(A) and P(B) represent the probabilities of events A and B, respectively. P(AB) is the joint probability when the two events happen simultaneously. In this way, we can rewrite inequality (1) into the following inequality:

j∈J P r i∈T t i ( ξ)x ij ≤ C ≥ 1 -α.
We then assume that, for each opened workstation j, its operating time remains within the cycle time with a probability of at least (1β j ). According to the equation P(AB) = P(A)P(B), we have j∈J (1β j ) = 1α. Therefore, inequality (1) can be expressed with several independent functions for all opened workstations:

P r i∈T t i ( ξ)x ij ≤ C ≥ 1 -β j , ∀ j ∈ J . ( 11
)
It completes the proof.

The following Proposition 3 is based on Lemma 1, and it calculates the value of variable µ i in constraint (2). With any given µ i , the proposed distribution-free model can be well solved.

Lemma 1 (Refer to Ng 2014) Given λ>0, the following inequality satisfies:

E[e λZ i ]≤1 + E[Z 2 i ] b 2 i (e λb i -λb i -1) Proposition 3 (Refer to Ng 2014) Recall the definition of β j in Proposition 2, we define f (π i ) := min λ i >0 (e -λ i π i /d i 1 + E[Z 2 i ] b 2 i (e λ i b i -λ i b i -1) -β j ).
Let the parameter µ i satisfy the following equation.

f (µ i ) = 0. ( 12
)
Then any feasible solution x ij of the distribution-free model must satisfy:

P r i∈T t i ( ξ)x ij > C ≤ β j .
Until now, it is not clear whether Equation ( 12) has a solution for any β j ∈ (0, 1). The following propositions demonstrate that this equation has a unique solution for any disassembly task i ∈ T .

Proposition 4 (Refer to Ng 2014) f (π i ) is a decreasing function.

Proposition 5 (Refer to Ng 2014) The equation f (µ i ) = 0 has a unique solution for all β j ∈ (0, 1).

A fast algorithm

Based on above property analysis, the key remaining work is to solve Equation ( 12) and find µ i so as to further solve the distribution-free model. By the fact that Bentaha, Battaïa, and Dolgui 2015a)

d i + µ i ≤ d i (1 + Z i ) ≤ d i (1 + b i ) (refer to the Proof of Proposition 3 in
, it follows that µ i ≤ d i • b i .
According to Propositions 4 and 5, the main idea of solving Equation ( 12) is to find a combination of λ i and µ i for any i ∈ T , satisfying f (µ i ) = 0. We devise a fast algorithm based on a double-loop method to control and adjust the value of λ i and µ i . Algorithm 1 below details the process of solving Equation ( 12).

Algorithm 1. Calculation of the value of µ i in function f (µ i ) = 0.

Input: d i , b i , E[Z 2 i ]
, and function f (µ i ). Output: µ i and λ i .

• Step 1: Initialize i = 1; • Step 2:Setµ i = d i • b i and λ i → 0 ( = 0), for example, λ i = 0.001; • Step 3: Calculate the value of f (µ i ); • Step 4:If f (µ i ) ≤ 0.001 or f (µ i ) = 0,
record the current value of µ i and λ i .ThengotoStep 7;

• Step 5:If f (µ i )>0.001, let λ i = λ i + 0.01. If λ i <λ max ,returntoStep 3; • Step 6:Ifλ i = λ max and f (µ i ) is strictly larger than 0.001, then let µ i = µ i -0.01, λ i = 0.001 and return to Step 3.

Otherwise go to Step 7;

• Step 7:Leti = i + 1. If i ∈ T ,returntoStep 2.
Otherwise, stop the whole loop and output µ i for each i ∈ T .

In this algorithm, in order to reduce the solution space, we assume that (i) the loop of calculating µ i begins with the worst case, i.e. µ i = d i • b i , and thus d i (1 + b i ) is the upper bound of task processing times; (ii) the loop of λ i (> 0) begins with a value close to 0. This is based on the observation that each f (µ i ) equals 0 if λ i = 0; (iii) we allow a reasonable and small error range for Equation (12). For instance, the algorithm outputs the first obtained value of µ i satisfying f (µ i ) ≤ 0.001.

In Step 4 of Algorithm 1, we say the solution of Equation ( 12), i.e. µ i , has been acquired if it satisfies f (µ i ) ≤ 0.001. In Step 6, the value of λ max is assumed to be some value which satisfies f (µ i ) ≥ 1 for any µ i , resulting in f (µ i ) 0. The calculating time for this algorithm mainly depends on the step sizes of µ i and λ i . We observe by numerical calculation that it is sufficient to set the step size equal to 0.01, as the experimental results of µ i are almost unchanged if we set smaller step sizes.

Numerical case study

In this section, we examine the proposed distribution-free model by numerical experiments. Commercial solver CPLEX 12.6 is called in Matlab 2014b to solve the model. All computational experiments have been conducted on a personal computer with Core I7 with 4 GB RAM under Microsoft Windows 7 operating system. With respect to Bentaha, Battaïa, and Dolgui (2015a), we first conduct a case study of the previously mentioned hand light example, and then make a further analysis on a number of different instances in literature. For all numerical experiments forward, the results under the corresponding deterministic scenarios are also presented for comparison.

T 1 1 T 2 11 T 3 1 T 4 11 T 5 T 6 11 1 T 7 11 1 T 8 T 9 11 1 T 10 11 1
Objective value 720 990 990

The hand light instance

The input data of the hand light instance is detailed in Table 1 where the digits in the right column are the values of the corresponding parameters in the left column. Especially, the digit '5' in the second row means that no more than five workstations can be opened for processing tasks. The digits of 'Mean task processing times (d i )'in the bottom row respectively represent the average task processing times of the 10 disassembly tasks. For example, the average task processing time of first task equals 50 (i.e. d 1 = 50). The computational results of the hand light instance are reported in Table 2, including the solutions of the deterministic scenario and two stochastic scenarios. Note that 'Distribution model' is solved by the approach in Bentaha, Battaïa, and Dolgui (2015a) and 'Distribution-free model' denotes the proposed model in this work. In each row T i , if there is a number '1', it means that task T i is assigned to workstation j (1 ≤ j ≤ 5), i.e. x ij = 1; otherwise the task will not be assigned and processed.

To start with, a deterministic scenario is considered where each task has a given processing time equalling to d i (i.e. µ i = 0 in constraint (2)). Under this scenario, the numbers of selected alternative tasks |T * | and opened workstations |J * | are respectively equal to 6 and 2. Four tasks T 2 , T 4 , T 9 and T 10 are assigned to workstation 1, while the other two tasks T 6 and T 7 are processed in workstation 2. The set of the selected alternative tasks correspond to the red arcs in the proposed decomposition colour graph (see Figure 5). The objective value of the solution is equal to 720.

Under the first stochastic scenario (i.e. the distribution model), a standard normal distribution is adopted in Bentaha's approach. The solution shows that there are |T * |=6 alternative tasks to be processed in |J * |=3 workstations. It is observed that the set of selected alternative tasks is the same with the deterministic scenario, but the tasks are assigned to three workstations, with the objective value of 990 in the stochastic scenario.

In the proposed distribution-free model, the values of parameters in Algorithm 1 and Proposition 2 are as follows. b i = 0.2 (and thus the proposed upper bound of task processing time is 1.2•d i ), α = 0.05 and E[Z 2 i ]=0.05 corresponding to Bentaha, Battaïa, and Dolgui (2015a). β j = 0.0102 by the definition of (1β j ) |J | = 1α in Proposition 2. Algorithm 1 outputs the 9.5, 2.20, 4.19, 3.81, 8.61, 11.72, 1.89, 6.66, 4.76, 5.74, for the 10 tasks. As shown in Table 2, the algorithm outputs a solution with |T * |=6, |J * |=3 and the objective value of 990. Tasks T 1 and T 3 are assigned to workstation 1, T 6 and T 7 go to workstation 2, and T 9 and T 10 go to workstation 3. The selected tasks correspond to the blue arcs in Figure 5. According to Table 2, the proposed distribution-free approach shows the same number of selected alternative tasks, opened workstations and objective value with the ones in Bentaha, Battaïa, and Dolgui (2015a). It not only demonstrates that the proposed distribution-free model performs well until now, but also verifies the rationality of the proposed decomposition colour graph. We then conduct available instances in the existing literature with different EOL products.

Further discussion with available instances

Below we analyse a set of instances from different previous works. Note that all the input data keeps the same with the experimental data in Bentaha, Battaïa, and Dolgui (2015a). Each of the instances is named by the combination of the first letter of each co-author's surname and the publication year of the work. We collect seven instances that handle different disassembly products, as listed in Table 3. The leftmost three columns of the table provide the instance name, the description of processed product, and the corresponding literature, respectively. The rest four columns give the information of the relevant parameters, i.e. the number of disassembly tasks |T |, the maximum number of workstations |J |, the number of subassembly nodes |S| and the cycle time C. For example, instance BBD13a is from Bentaha, Battaïa, and Dolgui (2013a) to disassemble a kind of compass product with 10 tasks being assigned to at most 3 workstations. For each instance, 25% of the disassembly tasks are assumed to be hazardous and parameter α takes the value of 5%. The fixed unit time costs for each workstation (|C f |) and for hazardous operation (|C h |) take the values of 3 and 2, respectively.

Numerical results are summarised in Table 4 for each instance, with the solutions of the deterministic case and two stochastic cases. We use subscript l 'l ={1, 2, 3}' to denote the corresponding results of the three cases, respectively. Notice that columns '|T * l |' and '|J * l |', respectively, report the number of selected disassembly tasks and opened workstations. Column 'J h l ' denotes the index of selected workstation for hazardous tasks. Finally, column 'Obj l ' records the obtained objective value.

For each instance in Table 4, the optimal objective values of deterministic scenario provide a lower bound for the two corresponding stochastic cases. It is easy to understand that the deterministic scenarios perform better under all instances, as they don't need to consider the effects caused by stochastic task processing times.

Compared with the results of 'distribution model ' and 'distribution-free model' in |, the indices of workstations for hazardous tasks may be different in some instances. The proposed decomposition color graph may well explain the reason: there exist several alternative disassembly line design choices. As a result, the objective values are also different if they take different disassembly line design strategies. In addition, the calculation time of each instance is within 1 second (note that the largest scale is of 37 tasks and 10 available workstations), which demonstrates that the proposed distribution-free model and the algorithm can effectively solve the stochastic scenario.

We conclude by the above numerical results that the proposed distribution-free model performs better than Bentaha's approach, and it can quickly provide more reasonable disassembly line design support, choosing a more cost-saving strategy. Another important advantage is that the distribution-free model can be easily solved with the mean, standard deviation and upper bound information of processing times, based on the property analysis and the fast algorithm, instead of the complete knowledge of probability distributions. Consequently, the distribution-free model and the algorithm are easy-to-implement in DLBP under the stochastic task processing time environment.

Conclusions

In this paper, we propose a decomposition colour graph for better understanding disassembly processes. Considering a possible lack of historical data to estimate probability distributions or functions with confidence, or the data might not be representative, we first propose a distribution-free model for the DLBP with only the mean, standard deviation, and upper bound of task processing times. We then transform the model to a solvable one based on property analysis. The instances in existing literature are utilised for the illustration of the proposed model, numerical experiments show that it can effectively solve DLBP without the knowledge of known probability distributions.

Future research directions may include: (i) find the value of µ i that guarantees the optimum so as to reduce the solution space; (ii) develop advanced heuristic methods to solve more complex DLPB if there is a demand; (iii) apply the distributionfree model to other disassembly line balancing scenarios. Since the main ideology of the distribution-free model is to transfer the probability constraint (or chance constraint) into a solvable linear constraint, therefore, its main function is to effectively deal with the uncertainty in management problems. If there is a demand on solving uncertainty under other DLBPs (for example, mixed-model disassembly line or assembly line design), the distribution-free model may be applicable for it by some problem-based property analysis.

Disclosure statement

No potential conflict of interest was reported by the authors.

Figure 1 .

 1 Figure 1. A brief introduction of a disassembly line.

Figure 2 .

 2 Figure 2. Icons in a decomposition color graph.

Figure 3 .

 3 Figure 3. Illustration of a decomposition color graph.

Figure 4 .

 4 Figure 4. Illustration of a hand light and its subassemblies (Tang et al. 2002).

Figure 5 .

 5 Figure 5. The decomposition colour graph of hand light disassembly processes.

Table 1 .

 1 Input data of the hand light instance.

	Parameter

Table 2 .

 2 Experimental results of the hand light instance.

	Stochastic scenario

Table 3 .

 3 Description of seven different instances.

	Instance	Product description	Literature	|T || J || S|	C
	BBD13a	Compass	Bentaha, Battaïa, and Dolgui (2013a)	10	3	5	0.61
	BBD13b	Piston and connecting rod	Bentaha, Battaïa, and Dolgui (2013b)	25	4	11	120
	KSE09	Sample product	Koc, Sabuncuoglu, and Erel (2009)	23	6	13	20
	L99a	Radio set	Lambert (1999)	30	9	18	50
	L99b	Ball-point pen	Lambert (1999)	20	9	13	10
	MJKL11	Automatic pencil	Ma et al. (2011)3 7	1 0	2 2	4 0
	TZC02	Hand light	Tang et al. (2002)1 0	6	7	9 0

Table 4 .

 4 Experimental results of the seven instances.

	Stochastic scenario

  Table 4, it can be observed that both the number of selected disassembly tasks and opened workstations show the same results under each instance (i.e. |T * 2 |=| T * 3 | and |J * 2 |=| J * 3 |). As for the results in columns |J h 2 | and |J h 3

Funding

This work was partly supported by the National Natural Science Foundation of China [grant number 71771048], [grant number 71531011], [grant number 71571134], [grant number 71571135], [grant number 71428002]. The work was also partially supported by the Fundamental Research Funds for the Central Universities, and Shanghai Pujiang Program.