# Formulations, Features of Solution Space, and Algorithms for Line-PureSeru System Conversion

Authors: Wei Sun; Qianqian Li; Chunhui Huo; Yang Yu; Ke Ma
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The line-seru conversion is usually used to improve productivity, especially in volatile business environment. Due to the simplicity, most researches focused on line-pureseru system conversion. We summarize the two existing models (i.e., a biobjective model and a single-objective model) of line-pure system conversion and formulate the three other usually used single-objective models in an integrated framework by combining evaluated performances and constraints. Subsequently, we analyze the solution space features of line-pureseru system conversion by dividing the whole solution space into several subspaces according to the number ofserus. We focus on investigating the features between C
m
a
x (and TLH) and subspaces. Thirdly, according to the distinct features between C
m
a
x (and TLH) and subspaces, we propose four effective algorithms to solve the four single-objective models, respectively. Finally, we evaluate the computational performance of the developed algorithms by comparing with enumeration based on extensive experiments.


---

## Body

## 1. Introduction

Theseru production, conceived at Sony, is an innovation of assembly system used widely in the Japanese electronics industry and recognized a new production pattern.Seru production is proposed to overcome the less flexible shortcoming of assembly line, especially confronted with the dynamic and volatile business environments.Seru is an assembly unit including several simple equipment and one (or more) multiskilled operator(s).Seru is the pronunciation of cell in Japanese; therefore,Seru production is also called Japanese style cellular production. Inseru, worker(s) must be multiskilled [1–4] because workers need to operate most or all the processes of production. In general, there are three types ofseru: divisionalseru, rotatingseru, andyatai [5, 6]. In a divisionalseru, tasks are divided into different sections and workers are partially cross-trained. Each section is operated by one or more workers. However, workers in rotatingseru oryatai are completely cross-trained and do all tasks. In this research, rotatingserus oryatai are considered.Seru system can be generally divided into two types: (
1
) pureseru system with onlyseru(s) and (
2
) hybrid system withseru(s) and short line. As Stecke et al. [5, 6] claimed, with combined strengths from Toyota’s lean philosophy and Sony’s one-person production organization,seru system is a more productive, efficient, and flexible system than conveyor assembly line. As we know, the productivity of the assembly line is decided by the worker with the worst skill. It is amazing thatseru system can greatly decrease the influence of the worker with the worst skill on the productivity by worker reconfiguration.Seru is more flexible than assembly line, because the workers inseru system are multiskilled operators who can operate multiple tasks and process multiple products.Seru’s flexibility is different with cellular manufacturing, where workers operate the certain part/product family.Seru system can response to market change quickly, due to movable workstations, light equipment, and multiskilled workers. Moreover,seru system can be continuously improved, because workers inseru can study to process more tasks and products.Due to the merit ofseru system [5–7],seru system has successfully been applied by many leading Japanese companies such as Sony, Canon, Panasonic, NEC, Fujitsu, Sharp, and Sanyo. Presently, many companies converted assembly line intoseru system (line-seru conversion) to increase the productivity [8–10]. By adopting line-seru conversion, Canon and Sony reduced 720,000 and 710,000 square meters of floor space, respectively [5, 6]. Moreover, Canon’s costs were reduced significantly, by 55 billion yen in 2003, and by a total of 230 billion yen from 1998 to 2003. As a result, Canon emerged as a leading electronics maker [11, 12]. Other benefits [13, 14] include the reductions of throughput time, setup time, required labor hours, WIP inventories, and finished-product inventories. For example, the makespan was reduced by 53% at Sony Kohda and 35,976 required workers, that is equal to 25% of Canon’s previous total workforce, have been saved.Seru systems also influence profits, product quality, and workforce motivation in a positive way.The essence of line-seru conversion lies in how to convert traditional conveyor assembly line into aseru system to obtain the optimal conversion solution. It is a very hot and important decision making problem because the total productivity of manufacturers may be improved dramatically [15, 16]. Such technical and decision making problems were defined as line-seru (or line-cell) conversion problems [10, 16]. Kaku et al. [10, 16] built a biobjective line-seru conversion model with minimizing makespan (they use the term “total throughput time”) and TLH. They claimed that their model considered three types ofseru systems, that is, (
1
) pureseru system, (
2
) hybrid system withserus and short line, and (
3
) assembly line. However, the third one, in fact, is not considered as aseru system, because it does not contain anyseru. Therefore, there are only two types ofseru systems, that is, pureseru system and hybrid system withserus and short line.Pureseru system is theseru system only containingseru(s) and is very simple and a special case of all otherseru assembly systems. The results obtained from pureseru system models not only provide insights into the pureseru system environment but also provide a basis for heuristics that are applicable to more complicatedseru system environments, for example, hybrid system withserus and short line. In practice, problems in more complicatedseru system environments are often decomposed into subproblems that deal with the pureseru system. Therefore, many literatures focused on the conversion of assembly line to pureseru system (line-pureseru system conversion), such as Yu et al. [17–20] and Sun et al. [21]. A simple case of line-pureseru system conversion is shown in Figure 1, where twoserus are constructed, that is, workers 2 and 5 inseru 1 and workers 1, 3, and 4 inseru 2.Figure 1
A case of line-pureseru system conversion [20].To establish the main mathematical models is very important for the research on line-pureseru system conversion. Yu et al. [17] formulated the biobjective model of Min-C
m
a
x and TLH. Subsequently, the researches of Yu et al. [18, 20] were based on the biobjective model. Considering the biobjective model has higher computational complexity, Sun et al. [21] formulated the single-objective model of Min-C
m
a
x with TLH constraint. Additionally, there are several other usually used single-objective models in line-pureseru system conversion. We should not formulate one model in one research but integrate these models into a common framework. Therefore, the first objective of the research is to formulate the five models of line-pureseru system conversion in an integrated framework by combining the evaluated performances and constraints.Moreover, the algorithms for line-pureseru system conversion are also the key. However, the existing algorithms for line-pureseru system conversion were based on enumeration (i.e., GA and local search) or metaheuristic and did not consider the distinct features of solution space of line-pureseru system conversion. For example, enumeration in Yu et al. [17] searched the whole solution space; Yu et al. [18, 20] and Sun et al. [21] used GA or local search to seek the optimal solution in the whole solution space. In fact, solution space of line-pureseru system conversion has the distinct features; that is, the solution space can be divided into several subspaces according to the number ofserus, and minimum C
m
a
x and minimum TLH usually exist in the special subspaces. That is to say, considering the features of solution space of line-pureseru system conversion, we maybe do not need to search the whole solution space to seek the optimal solution. Therefore, the second motivation of the research is to investigate the distinct features of solution space of line-pureseru system conversion. Subsequently, the third of objective is to develop the effective algorithms for the different models according to the obtained features of solution space of line-pureseru system conversion.This paper, originally motivated by line-seru applications of Sony and Canon, has three purposes. First, two existing models (i.e., a biobjective model and a single-objective model) and the three other usually used single-objective models in line-pure system conversion are formulated in an integrated framework by combining evaluated performances with constraints. Subsequently, we analyze the solution space features of line-pureseru system conversion by dividing solution space into several subspaces according to the number ofserus. We focus on investigating the features between C
m
a
x (makespan) and TLH (total labor hours) and subspaces with different number ofserus. Thirdly, we propose four effective algorithms to solve the four single-objective model, respectively, according to the distinct features of line-pureseru system.The remainder of this research is organized in the following ways. By combining the evaluated performances and constraints, Section2 formulates five models usually used in line-pureseru system conversion in an integrated framework. Section 3 investigates the solution space feature of line-pureseru system conversion based onW divided subspaces according to the number ofserus. Subsequently, we focus on analyzing the features between C
m
a
x (and TLH) and subspaces with different number ofserus. In Section 4, according to the distinct features of solution space, especially the features between C
m
a
x (and TLH) and subspaces with different number ofserus, we propose four algorithms to solve the four single-objective models, respectively. Section 5 uses extensive experiments to evaluate the computational performance of the proposed algorithms by comparing with enumeration. Finally, we end the paper with conclusions and with suggestions for future research in Section 6 and give the further research emphases, that is, the conversion from assembly line to the hybrid system withserus and short line.


## 2. Formulation of Several Main Models of Line-PureSeru System Conversion

### 2.1. Assumptions

The following assumptions are considered in line-pureseru system conversion:(1)
The types and batches of products to be processed are known in advance. There areN product types that are divided into M product batches. Each batch contains a single product type.
(2)
In the line-pureseru system conversion, most assembly tasks within aseru are manual, so need for only simple and cheap equipment and the cost of duplicating equipment is ignored [5].
(3)
A product batch needs to be assembled entirely within a singleseru.
(4)
All product types have the same assembly tasks. If tasks of some product were unique, we assume the task time for these unique tasks was zero.
(5)
The assembly tasks within eachseru are the same as the ones within the assembly line. Therefore, the total number of tasks equals W.
(6)
In the assembly line, each task (or station) is in charge of a single worker. That means that a worker only performs a single assembly task in the assembly line. In contrast, aseru worker needs to perform all assembly tasks and assembles an entire product from-start-to-finish, and there is no disruption or delay between adjacent tasks.


### 2.2. Notations

We define the following terms:(i) Indices
i: index of workers (i
=
1,2
,
…
,
W). Also, the total number of tasks is W, according to assumption (
5
).
j: index ofserus (j
=
1,2
,
…
,
J).
n: index of product types (n
=
1,2
,
…
,
N).
m: index of product batches (m
=
1,2
,
…
,
M).
k: index of the sequence of product batches in aseru (k
=
1,2
,
…
,
M).
r: index of the sequence of product batches in the short line (1,2
,
…
,
M).(ii) Parameters
(1)
V
m
n
=
1
,
i
f
p
r
o
d
u
c
t
t
y
p
e
o
f
p
r
o
d
u
c
t
b
a
t
c
h
m
i
s
n
;
0
,
o
t
h
e
w
i
s
e
.
B
m: size of product batch m.
T
n: cycle time of product type n in the assembly line.
S
L
P
n: setup time of product type n in the assembly line.
S
C
P
n: setup time of product type n in aseru.
η
i: upper bound on the number of tasks for worker i in aseru. If the number of tasks assigned to worker i is more than η
i, worker i’s average task time within aseru will be longer than her or his task time within the original assembly line.
ε
i: worker i’s coefficient of influencing level of doing multiple assembly tasks.
β
n
i: skill level of worker i for each task of product type n.(iii) Decision Variables
(2)
X
i
j
=
1
,
i
f
w
o
r
k
e
r
i
i
s
a
s
s
i
g
n
e
d
t
o
c
e
l
l
j
;
0
,
o
t
h
e
w
i
s
e
,
Z
m
j
k
=
1
,
i
f
p
r
o
d
u
c
t
b
a
t
c
h
m
i
s
a
s
s
i
g
n
e
d
t
o
c
e
l
l
j
i
n
s
e
q
u
e
n
c
e
k
;
0
,
o
t
h
e
w
i
s
e
.(iv) Variables
C
i: coefficient of variation of worker i’s increased task time after line-seru conversion, that is, from a specialist to a completely cross-trained worker. If the number of worker i’s tasks within aseru is over her or his upper bound η
i, that is, W
>
η
i, then the worker will cost more average task time than her or his task time within the original assembly line. C
i is given in (3).
T
C
m: assembly task time of product batch m per station in aseru. In aseru, the task time of product type n is calculated by the average task time of workers in theseru. T
C
m is represented as (4).
F
C
m: flow time of product batch m in aseru. F
C
m is represented as (5).
S
C
m: setup time of product batch m in aseru. Setup time is considered when two different types of products are processed consecutively; otherwise, the setup time is zero. For example, in (6), two adjacent assembled products in aseru are expressed as m and m
′. If the product type of m is different than that of m
′, that is, V
m
n
=
1, V
m
′
n
=
0, then S
C
m is S
C
P
n
V
m
n. However, if the product types of m and m
′ are identical, that is, V
m
n
=
V
m
′
n
=
1, then S
C
m is 0.
F
C
B
m: begin time of product batch m in aseru. There is no waiting time between two product batches so that F
C
B
m is the aggregation of flow time and setup time of the product batches processed prior to product batch m in the sameseru. F
C
B
m is represented as (7):(3)
C
i
=
1
+
ε
i
W
-
η
i
,
W
>
η
i
1
,
W
≤
η
i
,
∀
i
,
(4)
T
C
m
=
∑
n
=
1
N
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
V
m
n
T
n
β
n
i
C
i
X
i
j
Z
m
j
k
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
X
i
j
Z
m
j
k
,
(5)
F
C
m
=
B
m
T
C
m
W
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
X
i
j
Z
m
j
k
,
(6)
S
C
m
=
S
C
P
n
V
m
n
,
V
m
n
=
V
m
′
n
=
1
0
,
V
m
n
=
1
,
V
m
′
n
=
0
,
m
′
∣
Z
m
j
k
=
1
,
Z
m
′
j
k
-
1
=
1
,
∀
j
,
k
,
(7)
F
C
B
m
=
∑
p
=
1
m
-
1
∑
j
=
1
J
∑
k
=
1
m
F
C
p
+
S
C
p
Z
m
j
k
Z
p
j
k
-
1
.


### 2.3. Evaluated Performances

The following two performances are usually used to evaluateseru system’s productivity.


#### 2.3.1. Makespan

Makespan (C
m
a
x) of the pureseru system is the due time of the last completed product batch and can be expressed as(8)
C
m
a
x
=
m
a
x
m
=
1
M
F
C
B
m
+
F
C
m
+
S
C
m
.


#### 2.3.2. Total Labor Hour

The total labor hours (TLH) are the work time of all workers assembling the total product batches:(9)
T
L
H
=
∑
m
=
1
M
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
F
C
m
X
i
j
Z
m
j
k
.


### 2.4. Constraints

Each decision variable determines one process. Therefore, the line-pureseru system conversion is a two-stage decision process, that is,seru-formation andseru-load, decided by X
i
j and Z
m
j
k, respectively.According to the two decision processes and the two evaluated performances, we divide the constraints into the following categories.


#### 2.4.1.Seru-Formation Constraints

Consider(10)
1
≤
∑
i
=
1
W
X
i
j
≤
W
,
∀
j
,
(11)
∑
j
=
1
J
X
i
j
=
1
,
∀
i
,
(12)
∑
j
=
1
J
∑
i
=
1
W
X
i
j
=
W
.Equation (10) is theseru’s worker constraint which ensures that each formattedseru contains least one worker and most W workers. Equation (11) is the worker assignment constraint which guarantees that each worker must be only assigned to aseru. Equation (12) is the worker number constraint which guarantees that the total number of workers in all formattedserus equals W, that is, the total number of workers in the assembly line.


#### 2.4.2.Seru-Load Constraints

Consider(13)
∑
j
=
1
J
∑
k
=
1
M
Z
m
j
k
=
1
,
∀
m
,
(14)
∑
m
=
1
M
∑
k
=
1
M
Z
m
j
k
=
0
,
∀
j
∣
∑
i
=
1
W
X
i
j
=
0
.Equation (13) is theseru-load constraint; that is, a product batch is only loaded to aseru. Equation (14) guarantees a product batch must be assigned to aseru in which at least one worker is assigned.


#### 2.4.3.C
m
a
x Constraint

Consider(15)
C
m
a
x
o
f
p
u
r
e
s
e
r
u
s
y
s
t
e
m
≤
g
i
v
e
n
C
m
a
x
.Equation (15) constrains that pureseru system’s C
m
a
x is not worse than the given value. For example, we can set the given C
m
a
x as 90% of the assembly line’s C
m
a
x.


#### 2.4.4. TLH Constraint

Consider(16)
T
L
H
o
f
p
u
r
e
s
e
r
u
s
y
s
t
e
m
≤
g
i
v
e
n
T
L
H
.Equation (16) constrains that total labor hours (TLH) of pureseru system are not worse than the given value.


### 2.5. Several Main Models of Line-PureSeru System Conversion

By combining the above two evaluated performances ofC
m
a
x and TLH with four constraints ofseru-formation,seru-load, C
m
a
x, and TLH, we formulate several main mathematical models of line-pureseru system conversion.


#### 2.5.1. Model of Min-C
m
a
x (Model of Min-C
m
a
x: m
i
n (8), s.t. (10)–(14))

Model of Min-C
m
a
x is to minimize makespan (i.e., (8)) of pureseru system. Therefore, objective is expressed as m
i
n (8) and constraints includeseru-formation constraints andseru-load constraints, that is, (10)–(14).


#### 2.5.2. Model of Min-C
m
a
x with TLH Constraint (Model of Min-C
m
a
x with TLH Constraint: m
i
n (8), s.t. (10)–(14), (16))

TLH constraint sometimes needs to be considered in model of Min-C
m
a
x, and so model of Min-C
m
a
x with TLH constraint is formulated as above.


#### 2.5.3. Model of Min-TLH (Model of Min-TLH:m
i
n (9), s.t. (10)–(14))

Model of Min-TLH is to minimize TLH (i.e., (9)) of pureseru system. Therefore, objective is expressed as m
i
n (9) and constraints includeseru-formation constraints andseru-load constraints.


#### 2.5.4. Model of Min-TLH withC
m
a
x Constraint (Model of Min-TLH with C
m
a
x Constraint: m
i
n (9), s.t. (10)–(14), (15))

C
m
a
x constraint sometimes can be considered in model of Min-TLH, and so model of Min-TLH with C
m
a
x constraint is formulated as above.


#### 2.5.5. Biobjective Model of Min-C
m
a
x and TLH (Model of Min-C
m
a
x and TLH: m
i
n ((8) and (9)), s.t. (10)–(14))

Model of Min-C
m
a
x and TLH is to minimize C
m
a
x and TLH simultaneously. Therefore, biobjective is expressed as m
i
n ((8) and (9)) and constraints includeseru-formation constraints andseru-load constraints.


### 2.6. Researches on the Five Models’ Formulations

So far, most researches focused on the biobjective model of Min-C
m
a
x and TLH in Section 2.5.5. For example, Yu et al. [17, 20] formulated the biobjective model of Min-C
m
a
x and TLH and investigated the mathematical analysis and influence factors. In addition, as the biobjective model has higher computational complexity, Sun et al. [21] formulated the single-objective model of Min-C
m
a
x with TLH constraint in Section 2.5.2.Although the three other models were not researched until now, they are usually considered in line-pureseru system conversion. In fact, they are similar to model of Min-C
m
a
x with TLH constraint in Section 2.5.2, because they are single-objective models. It is unacceptable to formulate one model in one research. Therefore, the first contribution of the research is to summarize the existing two models and to formulate the three other usually used single-objective models in a framework by combining the above two evaluated performances and four constraints.In addition, previous researches did not investigate the distinct features of solution space of line-pureseru system conversion. As a result, the existing algorithms for line-pureseru system are not developed according to the distinct features.


## 2.1. Assumptions

The following assumptions are considered in line-pureseru system conversion:(1)
The types and batches of products to be processed are known in advance. There areN product types that are divided into M product batches. Each batch contains a single product type.
(2)
In the line-pureseru system conversion, most assembly tasks within aseru are manual, so need for only simple and cheap equipment and the cost of duplicating equipment is ignored [5].
(3)
A product batch needs to be assembled entirely within a singleseru.
(4)
All product types have the same assembly tasks. If tasks of some product were unique, we assume the task time for these unique tasks was zero.
(5)
The assembly tasks within eachseru are the same as the ones within the assembly line. Therefore, the total number of tasks equals W.
(6)
In the assembly line, each task (or station) is in charge of a single worker. That means that a worker only performs a single assembly task in the assembly line. In contrast, aseru worker needs to perform all assembly tasks and assembles an entire product from-start-to-finish, and there is no disruption or delay between adjacent tasks.


## 2.2. Notations

We define the following terms:(i) Indices
i: index of workers (i
=
1,2
,
…
,
W). Also, the total number of tasks is W, according to assumption (
5
).
j: index ofserus (j
=
1,2
,
…
,
J).
n: index of product types (n
=
1,2
,
…
,
N).
m: index of product batches (m
=
1,2
,
…
,
M).
k: index of the sequence of product batches in aseru (k
=
1,2
,
…
,
M).
r: index of the sequence of product batches in the short line (1,2
,
…
,
M).(ii) Parameters
(1)
V
m
n
=
1
,
i
f
p
r
o
d
u
c
t
t
y
p
e
o
f
p
r
o
d
u
c
t
b
a
t
c
h
m
i
s
n
;
0
,
o
t
h
e
w
i
s
e
.
B
m: size of product batch m.
T
n: cycle time of product type n in the assembly line.
S
L
P
n: setup time of product type n in the assembly line.
S
C
P
n: setup time of product type n in aseru.
η
i: upper bound on the number of tasks for worker i in aseru. If the number of tasks assigned to worker i is more than η
i, worker i’s average task time within aseru will be longer than her or his task time within the original assembly line.
ε
i: worker i’s coefficient of influencing level of doing multiple assembly tasks.
β
n
i: skill level of worker i for each task of product type n.(iii) Decision Variables
(2)
X
i
j
=
1
,
i
f
w
o
r
k
e
r
i
i
s
a
s
s
i
g
n
e
d
t
o
c
e
l
l
j
;
0
,
o
t
h
e
w
i
s
e
,
Z
m
j
k
=
1
,
i
f
p
r
o
d
u
c
t
b
a
t
c
h
m
i
s
a
s
s
i
g
n
e
d
t
o
c
e
l
l
j
i
n
s
e
q
u
e
n
c
e
k
;
0
,
o
t
h
e
w
i
s
e
.(iv) Variables
C
i: coefficient of variation of worker i’s increased task time after line-seru conversion, that is, from a specialist to a completely cross-trained worker. If the number of worker i’s tasks within aseru is over her or his upper bound η
i, that is, W
>
η
i, then the worker will cost more average task time than her or his task time within the original assembly line. C
i is given in (3).
T
C
m: assembly task time of product batch m per station in aseru. In aseru, the task time of product type n is calculated by the average task time of workers in theseru. T
C
m is represented as (4).
F
C
m: flow time of product batch m in aseru. F
C
m is represented as (5).
S
C
m: setup time of product batch m in aseru. Setup time is considered when two different types of products are processed consecutively; otherwise, the setup time is zero. For example, in (6), two adjacent assembled products in aseru are expressed as m and m
′. If the product type of m is different than that of m
′, that is, V
m
n
=
1, V
m
′
n
=
0, then S
C
m is S
C
P
n
V
m
n. However, if the product types of m and m
′ are identical, that is, V
m
n
=
V
m
′
n
=
1, then S
C
m is 0.
F
C
B
m: begin time of product batch m in aseru. There is no waiting time between two product batches so that F
C
B
m is the aggregation of flow time and setup time of the product batches processed prior to product batch m in the sameseru. F
C
B
m is represented as (7):(3)
C
i
=
1
+
ε
i
W
-
η
i
,
W
>
η
i
1
,
W
≤
η
i
,
∀
i
,
(4)
T
C
m
=
∑
n
=
1
N
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
V
m
n
T
n
β
n
i
C
i
X
i
j
Z
m
j
k
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
X
i
j
Z
m
j
k
,
(5)
F
C
m
=
B
m
T
C
m
W
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
X
i
j
Z
m
j
k
,
(6)
S
C
m
=
S
C
P
n
V
m
n
,
V
m
n
=
V
m
′
n
=
1
0
,
V
m
n
=
1
,
V
m
′
n
=
0
,
m
′
∣
Z
m
j
k
=
1
,
Z
m
′
j
k
-
1
=
1
,
∀
j
,
k
,
(7)
F
C
B
m
=
∑
p
=
1
m
-
1
∑
j
=
1
J
∑
k
=
1
m
F
C
p
+
S
C
p
Z
m
j
k
Z
p
j
k
-
1
.


## 2.3. Evaluated Performances

The following two performances are usually used to evaluateseru system’s productivity.


### 2.3.1. Makespan

Makespan (C
m
a
x) of the pureseru system is the due time of the last completed product batch and can be expressed as(8)
C
m
a
x
=
m
a
x
m
=
1
M
F
C
B
m
+
F
C
m
+
S
C
m
.


### 2.3.2. Total Labor Hour

The total labor hours (TLH) are the work time of all workers assembling the total product batches:(9)
T
L
H
=
∑
m
=
1
M
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
F
C
m
X
i
j
Z
m
j
k
.


## 2.3.1. Makespan

Makespan (C
m
a
x) of the pureseru system is the due time of the last completed product batch and can be expressed as(8)
C
m
a
x
=
m
a
x
m
=
1
M
F
C
B
m
+
F
C
m
+
S
C
m
.


## 2.3.2. Total Labor Hour

The total labor hours (TLH) are the work time of all workers assembling the total product batches:(9)
T
L
H
=
∑
m
=
1
M
∑
i
=
1
W
∑
j
=
1
J
∑
k
=
1
M
F
C
m
X
i
j
Z
m
j
k
.


## 2.4. Constraints

Each decision variable determines one process. Therefore, the line-pureseru system conversion is a two-stage decision process, that is,seru-formation andseru-load, decided by X
i
j and Z
m
j
k, respectively.According to the two decision processes and the two evaluated performances, we divide the constraints into the following categories.


### 2.4.1.Seru-Formation Constraints

Consider(10)
1
≤
∑
i
=
1
W
X
i
j
≤
W
,
∀
j
,
(11)
∑
j
=
1
J
X
i
j
=
1
,
∀
i
,
(12)
∑
j
=
1
J
∑
i
=
1
W
X
i
j
=
W
.Equation (10) is theseru’s worker constraint which ensures that each formattedseru contains least one worker and most W workers. Equation (11) is the worker assignment constraint which guarantees that each worker must be only assigned to aseru. Equation (12) is the worker number constraint which guarantees that the total number of workers in all formattedserus equals W, that is, the total number of workers in the assembly line.


### 2.4.2.Seru-Load Constraints

Consider(13)
∑
j
=
1
J
∑
k
=
1
M
Z
m
j
k
=
1
,
∀
m
,
(14)
∑
m
=
1
M
∑
k
=
1
M
Z
m
j
k
=
0
,
∀
j
∣
∑
i
=
1
W
X
i
j
=
0
.Equation (13) is theseru-load constraint; that is, a product batch is only loaded to aseru. Equation (14) guarantees a product batch must be assigned to aseru in which at least one worker is assigned.


### 2.4.3.C
m
a
x Constraint

Consider(15)
C
m
a
x
o
f
p
u
r
e
s
e
r
u
s
y
s
t
e
m
≤
g
i
v
e
n
C
m
a
x
.Equation (15) constrains that pureseru system’s C
m
a
x is not worse than the given value. For example, we can set the given C
m
a
x as 90% of the assembly line’s C
m
a
x.


### 2.4.4. TLH Constraint

Consider(16)
T
L
H
o
f
p
u
r
e
s
e
r
u
s
y
s
t
e
m
≤
g
i
v
e
n
T
L
H
.Equation (16) constrains that total labor hours (TLH) of pureseru system are not worse than the given value.


## 2.4.1.Seru-Formation Constraints

Consider(10)
1
≤
∑
i
=
1
W
X
i
j
≤
W
,
∀
j
,
(11)
∑
j
=
1
J
X
i
j
=
1
,
∀
i
,
(12)
∑
j
=
1
J
∑
i
=
1
W
X
i
j
=
W
.Equation (10) is theseru’s worker constraint which ensures that each formattedseru contains least one worker and most W workers. Equation (11) is the worker assignment constraint which guarantees that each worker must be only assigned to aseru. Equation (12) is the worker number constraint which guarantees that the total number of workers in all formattedserus equals W, that is, the total number of workers in the assembly line.


## 2.4.2.Seru-Load Constraints

Consider(13)
∑
j
=
1
J
∑
k
=
1
M
Z
m
j
k
=
1
,
∀
m
,
(14)
∑
m
=
1
M
∑
k
=
1
M
Z
m
j
k
=
0
,
∀
j
∣
∑
i
=
1
W
X
i
j
=
0
.Equation (13) is theseru-load constraint; that is, a product batch is only loaded to aseru. Equation (14) guarantees a product batch must be assigned to aseru in which at least one worker is assigned.


## 2.4.3.C
m
a
x Constraint

Consider(15)
C
m
a
x
o
f
p
u
r
e
s
e
r
u
s
y
s
t
e
m
≤
g
i
v
e
n
C
m
a
x
.Equation (15) constrains that pureseru system’s C
m
a
x is not worse than the given value. For example, we can set the given C
m
a
x as 90% of the assembly line’s C
m
a
x.


## 2.4.4. TLH Constraint

Consider(16)
T
L
H
o
f
p
u
r
e
s
e
r
u
s
y
s
t
e
m
≤
g
i
v
e
n
T
L
H
.Equation (16) constrains that total labor hours (TLH) of pureseru system are not worse than the given value.


## 2.5. Several Main Models of Line-PureSeru System Conversion

By combining the above two evaluated performances ofC
m
a
x and TLH with four constraints ofseru-formation,seru-load, C
m
a
x, and TLH, we formulate several main mathematical models of line-pureseru system conversion.


### 2.5.1. Model of Min-C
m
a
x (Model of Min-C
m
a
x: m
i
n (8), s.t. (10)–(14))

Model of Min-C
m
a
x is to minimize makespan (i.e., (8)) of pureseru system. Therefore, objective is expressed as m
i
n (8) and constraints includeseru-formation constraints andseru-load constraints, that is, (10)–(14).


### 2.5.2. Model of Min-C
m
a
x with TLH Constraint (Model of Min-C
m
a
x with TLH Constraint: m
i
n (8), s.t. (10)–(14), (16))

TLH constraint sometimes needs to be considered in model of Min-C
m
a
x, and so model of Min-C
m
a
x with TLH constraint is formulated as above.


### 2.5.3. Model of Min-TLH (Model of Min-TLH:m
i
n (9), s.t. (10)–(14))

Model of Min-TLH is to minimize TLH (i.e., (9)) of pureseru system. Therefore, objective is expressed as m
i
n (9) and constraints includeseru-formation constraints andseru-load constraints.


### 2.5.4. Model of Min-TLH withC
m
a
x Constraint (Model of Min-TLH with C
m
a
x Constraint: m
i
n (9), s.t. (10)–(14), (15))

C
m
a
x constraint sometimes can be considered in model of Min-TLH, and so model of Min-TLH with C
m
a
x constraint is formulated as above.


### 2.5.5. Biobjective Model of Min-C
m
a
x and TLH (Model of Min-C
m
a
x and TLH: m
i
n ((8) and (9)), s.t. (10)–(14))

Model of Min-C
m
a
x and TLH is to minimize C
m
a
x and TLH simultaneously. Therefore, biobjective is expressed as m
i
n ((8) and (9)) and constraints includeseru-formation constraints andseru-load constraints.


## 2.5.1. Model of Min-C
m
a
x (Model of Min-C
m
a
x: m
i
n (8), s.t. (10)–(14))

Model of Min-C
m
a
x is to minimize makespan (i.e., (8)) of pureseru system. Therefore, objective is expressed as m
i
n (8) and constraints includeseru-formation constraints andseru-load constraints, that is, (10)–(14).


## 2.5.2. Model of Min-C
m
a
x with TLH Constraint (Model of Min-C
m
a
x with TLH Constraint: m
i
n (8), s.t. (10)–(14), (16))

TLH constraint sometimes needs to be considered in model of Min-C
m
a
x, and so model of Min-C
m
a
x with TLH constraint is formulated as above.


## 2.5.3. Model of Min-TLH (Model of Min-TLH:m
i
n (9), s.t. (10)–(14))

Model of Min-TLH is to minimize TLH (i.e., (9)) of pureseru system. Therefore, objective is expressed as m
i
n (9) and constraints includeseru-formation constraints andseru-load constraints.


## 2.5.4. Model of Min-TLH withC
m
a
x Constraint (Model of Min-TLH with C
m
a
x Constraint: m
i
n (9), s.t. (10)–(14), (15))

C
m
a
x constraint sometimes can be considered in model of Min-TLH, and so model of Min-TLH with C
m
a
x constraint is formulated as above.


## 2.5.5. Biobjective Model of Min-C
m
a
x and TLH (Model of Min-C
m
a
x and TLH: m
i
n ((8) and (9)), s.t. (10)–(14))

Model of Min-C
m
a
x and TLH is to minimize C
m
a
x and TLH simultaneously. Therefore, biobjective is expressed as m
i
n ((8) and (9)) and constraints includeseru-formation constraints andseru-load constraints.


## 2.6. Researches on the Five Models’ Formulations

So far, most researches focused on the biobjective model of Min-C
m
a
x and TLH in Section 2.5.5. For example, Yu et al. [17, 20] formulated the biobjective model of Min-C
m
a
x and TLH and investigated the mathematical analysis and influence factors. In addition, as the biobjective model has higher computational complexity, Sun et al. [21] formulated the single-objective model of Min-C
m
a
x with TLH constraint in Section 2.5.2.Although the three other models were not researched until now, they are usually considered in line-pureseru system conversion. In fact, they are similar to model of Min-C
m
a
x with TLH constraint in Section 2.5.2, because they are single-objective models. It is unacceptable to formulate one model in one research. Therefore, the first contribution of the research is to summarize the existing two models and to formulate the three other usually used single-objective models in a framework by combining the above two evaluated performances and four constraints.In addition, previous researches did not investigate the distinct features of solution space of line-pureseru system conversion. As a result, the existing algorithms for line-pureseru system are not developed according to the distinct features.


## 3. Features of Solution Space of Line-PureSeru System Conversion

### 3.1. Complexity of Solution Space SatisfyingSeru-Formation andSeru-Load Constraints

In line-pureseru system conversion,seru-formation is the first step. It is to determine how manyserus to be formed and how to assign workers into theserus [17]and it is decided by decision variable X
i
j.A feasible solution ofseru-formation must satisfyseru-formation constraint, that is, (10)–(12). Yu et al. [17] proved thatseru-formation is an instance of the unordered set partition and an NP-hard problem. The number of all feasible solutions ofseru-formation can be expressed recursively as the following:(17)
F
W
=
∑
J
=
1
W
P
W
,
J
,where P
(
W
,
J
) is the count of partitioning W workers in assembly line into J
serus and can be expressed as the Stirling numbers of the second kind [22]. The numbers of F
(
1
) to F
(
10
) are 1, 2, 5, 15, 52, 203, 877, 4140, 21147, and 115975, respectively [23–25]. Obviously, F
(
W
) increases exponentially with W.Seru-load is the second step of line-pureseru system conversion and is decided by decision variable Z
m
j
k. It determines which product batches are dispatched to theserus formed inseru-formation [26, 27]. A feasible solution ofseru-load must satisfyseru-load constraint, that is, (13) and (14).Seru-load is NP-hard. Therefore, most researches used typical dispatching rules, such as FCFS (first-come, first-served) and SPT (shortest processing time). Even though the typical dispatching rules are used inseru-load, line-pureseru system conversion still is NP-hard, because it containsseru-formation which is NP-hard.Yu et al. [20] proved that line-pureseru system conversion with SPT is an instance of the unordered set partition and the complexity of solution space can be expressed as (17). Line-pureseru system conversion with FCFS is an instance of the ordered set partition and the complexity of solution space can be expressed as(18)
T
W
=
∑
J
=
1
W
P
W
,
J
∗
J
!
.The numbers ofT
(
1
) to T
(
10
) are 1, 3, 13, 75, 541, 4,683, 47,293, 545,835, 7,087,261, and 102,247,563, respectively. In the research, we use FCFS rule to assign product batches toserus.


### 3.2. Solution Spaces of the Five Models

In the above five models, model of Min-C
m
a
x, model of Min-TLH, and biobjective model of Min-C
m
a
x and TLH have the identical solution space described in Section 3.1, because all of them only includeseru-formation constraints andseru-load constraints.However, model of Min-C
m
a
x with TLH constraint and model of Min-TLH with C
m
a
x constraint have the different solution space, because the two models contain the other constraints exceptseru-formation constraints andseru-load constraints. Therefore, the solution spaces of the two models must be not more than that of Section 3.1.


### 3.3. Existing Algorithms for the Five Models

Most researches focused on the algorithms for the biobjective model of Min-C
m
a
x and TLH in Section 2.5.5. Yu et al. [20] proposed a based-NSGA-II algorithm to solve the biobjective model; Yu et al. [18] combined local search into NSGA-II to improve the running time and solutions qualification; Yu et al. [17] used enumeration and based-NSGA-II algorithm to solve the biobjective model to analyze the impact factor on C
m
a
x and TLH improvements by line-pureseru system conversion. Sun et al. [21] developed a variable neighborhood search (VNS) for model of Min-C
m
a
x with TLH constraint in Section 2.5.2.However, the algorithms for the three other models were not researched until now.The existing algorithms for line-pureseru system conversion were based on the metaheuristic (i.e., GA and local search) and did not consider the distinct features of solution space. For example, enumeration in [17] searched the whole solution space; Yu et al. [18, 20] and Sun et al. [21] used GA or local search to seek the optimal solution in the whole solution space. In fact, solution space of line-pureseru system conversion has the distinct features; that is, the solution space can be divided into several subspaces according to the number ofserus, and minimum C
m
a
x and minimum TLH usually exist in the special subspaces. That is to say, considering the features of solution space of line-pureseru system conversion, we maybe do not need to search the whole solution space to seek the optimal or suboptimal solution.Therefore, we investigate the distinct features of solution space of line-pureseru system conversion and then propose effective algorithms to solve the four single-objective models based on the distinct features of solution space.


### 3.4. Subspaces with Different Number ofSerus

Definition 1.
Subspace in solution space of line-pureseru system conversion is the set of solutions with the same number ofserus.
For example, of (18), the whole solution space can be divided into W subspaces according to the number ofserus, that is, the subspaces with 1,2
,
…, and W
serus. Therefore, (18) can be expressed as the following:(19)
T
W
=
P
W
,
1
∗
1
!
+
⋯
+
P
W
,
J
∗
J
!
+
⋯
+
P
W
,
W
∗
W
!
.Table1 summarizes the number of solutions in subspace with J
serus for the lines with 6–9 workers.Table 1
Number of solutions in subspace withJ serus.
Workers
Number of solutions in subspace withJ serus
Total solutions
1
2
3
4
5
6
7
8
9
6
1
62
540
1560
1800
720
—
—
—
4683
7
1
126
1806
8400
16800
15120
5040
—
—
47293
8
1
254
5796
40824
126000
191520
141120
40320
—
545835
9
1
510
18150
186480
834120
1905120
2328480
1451520
362880
7087261The value in column of “workers” represents the number of workers in the assembly line. For the row “6,” the numbers of solutions in subspaces with 1, 2, 3, 4, 5, and 6serus are 1
=
P
(
6,1
)
∗
1
!, 62
=
P
(
6,2
)
∗
2
!, 540
=
P
(
6,3
)
∗
3
!, 1560
=
P
(
6,4
)
∗
4
!, 1800
=
P
(
6,5
)
∗
5
!, and 720
=
P
(
6,6
)
∗
6
!, respectively.To show the proportion of solutions in each subspace to the total solutions in the whole solution space, Table2 normalizes the data in Table 1.Table 2
Proportion of solutions in subspace withJ serus.
Workers
Proportion of solutions in subspace withJ serus
1
2
3
4
5
6
7
8
9
6
0.02
1.32
11.53
33.31
38.44
15.37
—
—
—
7
0.00
0.27
3.82
17.76
35.52
31.97
10.66
—
—
8
0.00
0.05
1.06
7.48
23.08
35.09
25.85
7.39
—
9
0.00
0.01
0.26
2.63
11.77
26.88
32.85
20.48
5.12From Table2, we can see that the number of solutions in subspaces with few or moreserus is very small. Therefore, if minimum C
m
a
x and minimum TLH exist in such subspaces, we can dramatically decrease the searching space.


### 3.5. Value ofC
m
a
x and TLH in Subspaces

Yu et al. [17] performed 64 arrays of full factorial experiment to analyze influence factors and proposed some managerial insights. Two insights on C
m
a
x and TLH are as follows: (
1
) to minimize C
m
a
x, the pureseru system with fewerserus should be created and assign the workers with similar skill levels for product types to the sameseru; and (
2
) to minimize TLH, the pureseru system with moreserus should be created.Yu et al. [17] used the solutions with 1seru and W
serus to briefly explain the two insights: (
1
) they proved that when W
≤
η
i, if theseru system with aseru is formatted, then the C
m
a
x performance of pureseru system must be better than that of the assembly line. Additionally, they stated that the pureseru system with fewerserus is easy to balance C
m
a
x amongserus than the pureseru system with moreserus. Therefore, the pureseru system with fewerserus can produce better C
m
a
x; and (
2
) they proved that when W
≤
η
i and W
≤
M, the pureseru system with W
serus should be formatted in order to minimize TLH, because this makes full use of each worker’s skill.To further investigate the two insights, in the research, we analyze the features ofC
m
a
x and TLH in each subspace in detail. Figures 2–4 show C
m
a
x and TLH of all solutions in each subspace for the cases with 6–8 workers, respectively. The results of Figures 2–4 are exactly obtained by enumeration. The detailed data of the used cases with 6–8 workers are described in Section 5.1.Figure 2
C
m
a
x and TLH in subspaces for the line with 6 workers.
(a)
(b)Figure 3
C
m
a
x and TLH in subspaces for the line with 7 workers.
(a)
(b)Figure 4
C
m
a
x and TLH in subspaces for the line with 8 workers.
(a)
(b)


### 3.6. Distinct Features betweenC
m
a
x (and TLH) and Subspaces

By observingC
m
a
x and TLH in Figures 2–4, we can investigate the distinct features between C
m
a
x (and TLH) and subspaces as follows.Feature 1.
MinimumC
m
a
x usually exists in the subspaces with fewserus.
Explanation. As shown in Figures 2–4, the minimum C
m
a
x always exists in the subspaces with 2serus.Feature 2.
Except the subspace with 1seru, the minimum C
m
a
x of the subspaces with fewerserus usually is less than that of the subspaces with moreserus.
Explanation. As shown in Figure 3, the minimum C
m
a
x of the subspaces with J (1
<
J
<
7)serus always is less than that of the subspaces with J
+
1
serus. The trend can be found in all of Figures 2 and 3. Table 3 shows the detailed information on the minimum C
m
a
x of the subspaces with J
serus for the cases with 6–8 workers.Table 3
MinimumC
m
a
x in subspace with J serus.
Workers
MinimumC
m
a
x in subspace with J serus
1
2
3
4
5
6
7
8
6
2963
2954
2970
2973
2981
3177
—
—
7
2980
2963
2966
3014
3021
3123
3208
—
8
2980
2962
2971
2971
3045
3121
3122
3163Features1 and 2 mean that it not necessary to search the whole solution space to obtain minimum C
m
a
x, especially in single-objective models. To fast obtain minimum C
m
a
x, therefore, we can search the subspaces from fewerserus to moreserus. Consequently, we propose effective algorithms to fast find minimum C
m
a
x. The detailed procedure is described in Section 4.1.Feature 3.
Minimum TLH usually exists in the subspaces with moreserus.
Explanation. Assume M
_
J express the maximum J. In Figures 2–4, the minimum TLH always exists in the subspace with M
_
J
serus.Feature 4.
Minimum TLH of the subspaces with moreserus usually is less than that of the subspaces with fewerserus.
Explanation. As shown in Figures 2–4, the minimum TLH of the subspaces withJ serus always is less than that of the subspaces with J
-
1
serus. Table 4 shows the detailed information on the minimum TLH of the subspaces with J
serus for the cases with 6–8 workers.Table 4
Minimum TLH in subspace withJ serus.
Workers
Minimum TLH in subspace withJ serus
1
2
3
4
5
6
7
8
6
17610
17559
17534
17494
17463
17453
—
—
7
20665
20586
20506
29505
20504
20482
20442
—
8
23641
23519
23475
23437
23365
23354
23303
23260Features3 and 4 mean that it not necessary to search the whole feasible solution space to obtain the minimum TLH, especially in single-objective models. To fast obtain minimum TLH, therefore, we can search the subspaces from moreserus to fewserus. Consequently, we propose effective algorithms to fast find the minimum TLH. The detailed procedure is described in Section 4.2.


## 3.1. Complexity of Solution Space SatisfyingSeru-Formation andSeru-Load Constraints

In line-pureseru system conversion,seru-formation is the first step. It is to determine how manyserus to be formed and how to assign workers into theserus [17]and it is decided by decision variable X
i
j.A feasible solution ofseru-formation must satisfyseru-formation constraint, that is, (10)–(12). Yu et al. [17] proved thatseru-formation is an instance of the unordered set partition and an NP-hard problem. The number of all feasible solutions ofseru-formation can be expressed recursively as the following:(17)
F
W
=
∑
J
=
1
W
P
W
,
J
,where P
(
W
,
J
) is the count of partitioning W workers in assembly line into J
serus and can be expressed as the Stirling numbers of the second kind [22]. The numbers of F
(
1
) to F
(
10
) are 1, 2, 5, 15, 52, 203, 877, 4140, 21147, and 115975, respectively [23–25]. Obviously, F
(
W
) increases exponentially with W.Seru-load is the second step of line-pureseru system conversion and is decided by decision variable Z
m
j
k. It determines which product batches are dispatched to theserus formed inseru-formation [26, 27]. A feasible solution ofseru-load must satisfyseru-load constraint, that is, (13) and (14).Seru-load is NP-hard. Therefore, most researches used typical dispatching rules, such as FCFS (first-come, first-served) and SPT (shortest processing time). Even though the typical dispatching rules are used inseru-load, line-pureseru system conversion still is NP-hard, because it containsseru-formation which is NP-hard.Yu et al. [20] proved that line-pureseru system conversion with SPT is an instance of the unordered set partition and the complexity of solution space can be expressed as (17). Line-pureseru system conversion with FCFS is an instance of the ordered set partition and the complexity of solution space can be expressed as(18)
T
W
=
∑
J
=
1
W
P
W
,
J
∗
J
!
.The numbers ofT
(
1
) to T
(
10
) are 1, 3, 13, 75, 541, 4,683, 47,293, 545,835, 7,087,261, and 102,247,563, respectively. In the research, we use FCFS rule to assign product batches toserus.


## 3.2. Solution Spaces of the Five Models

In the above five models, model of Min-C
m
a
x, model of Min-TLH, and biobjective model of Min-C
m
a
x and TLH have the identical solution space described in Section 3.1, because all of them only includeseru-formation constraints andseru-load constraints.However, model of Min-C
m
a
x with TLH constraint and model of Min-TLH with C
m
a
x constraint have the different solution space, because the two models contain the other constraints exceptseru-formation constraints andseru-load constraints. Therefore, the solution spaces of the two models must be not more than that of Section 3.1.


## 3.3. Existing Algorithms for the Five Models

Most researches focused on the algorithms for the biobjective model of Min-C
m
a
x and TLH in Section 2.5.5. Yu et al. [20] proposed a based-NSGA-II algorithm to solve the biobjective model; Yu et al. [18] combined local search into NSGA-II to improve the running time and solutions qualification; Yu et al. [17] used enumeration and based-NSGA-II algorithm to solve the biobjective model to analyze the impact factor on C
m
a
x and TLH improvements by line-pureseru system conversion. Sun et al. [21] developed a variable neighborhood search (VNS) for model of Min-C
m
a
x with TLH constraint in Section 2.5.2.However, the algorithms for the three other models were not researched until now.The existing algorithms for line-pureseru system conversion were based on the metaheuristic (i.e., GA and local search) and did not consider the distinct features of solution space. For example, enumeration in [17] searched the whole solution space; Yu et al. [18, 20] and Sun et al. [21] used GA or local search to seek the optimal solution in the whole solution space. In fact, solution space of line-pureseru system conversion has the distinct features; that is, the solution space can be divided into several subspaces according to the number ofserus, and minimum C
m
a
x and minimum TLH usually exist in the special subspaces. That is to say, considering the features of solution space of line-pureseru system conversion, we maybe do not need to search the whole solution space to seek the optimal or suboptimal solution.Therefore, we investigate the distinct features of solution space of line-pureseru system conversion and then propose effective algorithms to solve the four single-objective models based on the distinct features of solution space.


## 3.4. Subspaces with Different Number ofSerus

Definition 1.
Subspace in solution space of line-pureseru system conversion is the set of solutions with the same number ofserus.
For example, of (18), the whole solution space can be divided into W subspaces according to the number ofserus, that is, the subspaces with 1,2
,
…, and W
serus. Therefore, (18) can be expressed as the following:(19)
T
W
=
P
W
,
1
∗
1
!
+
⋯
+
P
W
,
J
∗
J
!
+
⋯
+
P
W
,
W
∗
W
!
.Table1 summarizes the number of solutions in subspace with J
serus for the lines with 6–9 workers.Table 1
Number of solutions in subspace withJ serus.
Workers
Number of solutions in subspace withJ serus
Total solutions
1
2
3
4
5
6
7
8
9
6
1
62
540
1560
1800
720
—
—
—
4683
7
1
126
1806
8400
16800
15120
5040
—
—
47293
8
1
254
5796
40824
126000
191520
141120
40320
—
545835
9
1
510
18150
186480
834120
1905120
2328480
1451520
362880
7087261The value in column of “workers” represents the number of workers in the assembly line. For the row “6,” the numbers of solutions in subspaces with 1, 2, 3, 4, 5, and 6serus are 1
=
P
(
6,1
)
∗
1
!, 62
=
P
(
6,2
)
∗
2
!, 540
=
P
(
6,3
)
∗
3
!, 1560
=
P
(
6,4
)
∗
4
!, 1800
=
P
(
6,5
)
∗
5
!, and 720
=
P
(
6,6
)
∗
6
!, respectively.To show the proportion of solutions in each subspace to the total solutions in the whole solution space, Table2 normalizes the data in Table 1.Table 2
Proportion of solutions in subspace withJ serus.
Workers
Proportion of solutions in subspace withJ serus
1
2
3
4
5
6
7
8
9
6
0.02
1.32
11.53
33.31
38.44
15.37
—
—
—
7
0.00
0.27
3.82
17.76
35.52
31.97
10.66
—
—
8
0.00
0.05
1.06
7.48
23.08
35.09
25.85
7.39
—
9
0.00
0.01
0.26
2.63
11.77
26.88
32.85
20.48
5.12From Table2, we can see that the number of solutions in subspaces with few or moreserus is very small. Therefore, if minimum C
m
a
x and minimum TLH exist in such subspaces, we can dramatically decrease the searching space.


## 3.5. Value ofC
m
a
x and TLH in Subspaces

Yu et al. [17] performed 64 arrays of full factorial experiment to analyze influence factors and proposed some managerial insights. Two insights on C
m
a
x and TLH are as follows: (
1
) to minimize C
m
a
x, the pureseru system with fewerserus should be created and assign the workers with similar skill levels for product types to the sameseru; and (
2
) to minimize TLH, the pureseru system with moreserus should be created.Yu et al. [17] used the solutions with 1seru and W
serus to briefly explain the two insights: (
1
) they proved that when W
≤
η
i, if theseru system with aseru is formatted, then the C
m
a
x performance of pureseru system must be better than that of the assembly line. Additionally, they stated that the pureseru system with fewerserus is easy to balance C
m
a
x amongserus than the pureseru system with moreserus. Therefore, the pureseru system with fewerserus can produce better C
m
a
x; and (
2
) they proved that when W
≤
η
i and W
≤
M, the pureseru system with W
serus should be formatted in order to minimize TLH, because this makes full use of each worker’s skill.To further investigate the two insights, in the research, we analyze the features ofC
m
a
x and TLH in each subspace in detail. Figures 2–4 show C
m
a
x and TLH of all solutions in each subspace for the cases with 6–8 workers, respectively. The results of Figures 2–4 are exactly obtained by enumeration. The detailed data of the used cases with 6–8 workers are described in Section 5.1.Figure 2
C
m
a
x and TLH in subspaces for the line with 6 workers.
(a)
(b)Figure 3
C
m
a
x and TLH in subspaces for the line with 7 workers.
(a)
(b)Figure 4
C
m
a
x and TLH in subspaces for the line with 8 workers.
(a)
(b)


## 3.6. Distinct Features betweenC
m
a
x (and TLH) and Subspaces

By observingC
m
a
x and TLH in Figures 2–4, we can investigate the distinct features between C
m
a
x (and TLH) and subspaces as follows.Feature 1.
MinimumC
m
a
x usually exists in the subspaces with fewserus.
Explanation. As shown in Figures 2–4, the minimum C
m
a
x always exists in the subspaces with 2serus.Feature 2.
Except the subspace with 1seru, the minimum C
m
a
x of the subspaces with fewerserus usually is less than that of the subspaces with moreserus.
Explanation. As shown in Figure 3, the minimum C
m
a
x of the subspaces with J (1
<
J
<
7)serus always is less than that of the subspaces with J
+
1
serus. The trend can be found in all of Figures 2 and 3. Table 3 shows the detailed information on the minimum C
m
a
x of the subspaces with J
serus for the cases with 6–8 workers.Table 3
MinimumC
m
a
x in subspace with J serus.
Workers
MinimumC
m
a
x in subspace with J serus
1
2
3
4
5
6
7
8
6
2963
2954
2970
2973
2981
3177
—
—
7
2980
2963
2966
3014
3021
3123
3208
—
8
2980
2962
2971
2971
3045
3121
3122
3163Features1 and 2 mean that it not necessary to search the whole solution space to obtain minimum C
m
a
x, especially in single-objective models. To fast obtain minimum C
m
a
x, therefore, we can search the subspaces from fewerserus to moreserus. Consequently, we propose effective algorithms to fast find minimum C
m
a
x. The detailed procedure is described in Section 4.1.Feature 3.
Minimum TLH usually exists in the subspaces with moreserus.
Explanation. Assume M
_
J express the maximum J. In Figures 2–4, the minimum TLH always exists in the subspace with M
_
J
serus.Feature 4.
Minimum TLH of the subspaces with moreserus usually is less than that of the subspaces with fewerserus.
Explanation. As shown in Figures 2–4, the minimum TLH of the subspaces withJ serus always is less than that of the subspaces with J
-
1
serus. Table 4 shows the detailed information on the minimum TLH of the subspaces with J
serus for the cases with 6–8 workers.Table 4
Minimum TLH in subspace withJ serus.
Workers
Minimum TLH in subspace withJ serus
1
2
3
4
5
6
7
8
6
17610
17559
17534
17494
17463
17453
—
—
7
20665
20586
20506
29505
20504
20482
20442
—
8
23641
23519
23475
23437
23365
23354
23303
23260Features3 and 4 mean that it not necessary to search the whole feasible solution space to obtain the minimum TLH, especially in single-objective models. To fast obtain minimum TLH, therefore, we can search the subspaces from moreserus to fewserus. Consequently, we propose effective algorithms to fast find the minimum TLH. The detailed procedure is described in Section 4.2.


## 4. Algorithms for the Single-Objective Line-PureSeru System Conversion

As mentioned above, most existing algorithms were for the biobjective line-pureseru system conversion. The algorithm of Sun et al. [21] was for single-objective model. However, these algorithms were not developed based on the features of solution space of line-pureseru system conversion, which decreases their running efficiency. Therefore, we propose algorithms to solve the 4 single-objective models based on the distinct features of solution space.


### 4.1. Algorithms for Models of Min-C
m
a
x and Min-C
m
a
x with TLH Constraint

To avoid the obtained solution with minimumC
m
a
x being locally optimal, the algorithm does not search the subspace with the leastseru (i.e., 1seru) but searches subspaces from fewerserus to moreserus to seek minimum C
m
a
x. Therefore, the minimum C
m
a
x may be obtained by searching only a part of solution space.For an instance of Min-C
m
a
x with W workers, after obtaining the optimal solution in subspace with J
seru, the algorithm searches the optimal solution in subspace with J
+
1
serus. If the latter is not better than the former, then the algorithm will stop; otherwise, continue, until the optimal solution with J
+
1
serus is not better than the optimal solution with J
serus. The procedure can be described as shown in Algorithm 1.Algorithm 1:Algorithm for models of Min-C
m
a
x.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-C
m
a
x.
(1) Initialize. Set O = null (record the optimal solution), J
=
1.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x.
(1-2) Obtain the optimalC
m
a
x in S
J.
(1-3)O = optimal C
m
a
x in S
J;
(2)J
=
J
+
1;
(3) WhileJ
<
W Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x.
(3-2) Obtain the optimalC
m
a
x in S
J.
(3-3) If optimalC
m
a
x in S
J < optimal C
m
a
x in S
J
-
1 Then
O = optimal C
m
a
x in S
J;
J
=
J
+
1;
Continue;
Else
Break;
(4) OutputO.In Steps(
2
) and (3-3), J
=
J
+
1 means to search solution space from fewserus to moreserus. Step (3-3) is to judge if the algorithm stops. If yes, output O; otherwise, continue to search the optimal C
m
a
x in the next subspace.Similar to Algorithm1, algorithm for models of Min-C
m
a
x with TLH constraint can be expressed as shown in Algorithm 2.Algorithm 2:Algorithm for models of Min-C
m
a
x with TLH constraint.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-C
m
a
x with TLH constraint.
(1) Initialize. SetO= null (record the optimal solution), J
=
1.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x
and TLH.
(1-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying TLH constraint.
(1-3) Obtain the optimalC
m
a
x in F
J.
(1-4)O = optimal C
m
a
x in F
J;
(2)J
=
J
+
1;
(3) WhileJ
<
W Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x
and TLH.
(3-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying TLH constraint.
(3-3) Obtain the optimalC
m
a
x in F
J.
(3-3) If optimalC
m
a
x in F
J < optimal C
m
a
x in F
J
-
1 Then
O = optimal C
m
a
x in F
J;
J
=
J
+
1;
Continue;
Else
Break;
(4) OutputO.Distinguished from Algorithm1, Algorithm 2 needs to calculate TLH and to judge if TLH constraint is satisfied. They are described in steps (1-1) and (1-2).


### 4.2. Algorithm for Model of Min-TLH and Min-TLH withC
m
a
x Constraint

To avoid the obtained solution with minimum TLH being locally optimal, the algorithm does not search the subspace with the mostseru (i.e., W
seru) but searches subspaces from moreserus to fewserus to seek the minimum TLH. Therefore, the minimum C
m
a
x may be obtained by searching only a part of solution space.For an instance of Min-TLH withW workers, after obtaining the optimal solution in subspace with J
seru, the algorithm searches the optimal solution in subspace with J
-
1
serus. If the latter is not better than the former, then the algorithm will stop; otherwise, continue, until the optimal solution with J
-
1
serus is not better than the optimal solution with J
serus. The procedure can be described as shown in Algorithm 3.Algorithm 3:Algorithm for models of Min-TLH.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-TLH.
(1) Initialize. SetO= null (record the optimal solution), J
=
W.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s TLH.
(1-2) Obtain the optimal TLH inS
J.
(1-3)O = optimal TLH in S
J;
(2)J
=
J
-
1;
(3) WhileJ
>
1 Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s TLH.
(3-2) Obtain the optimal TLH inS
J.
(3-3) If optimal TLH inS
J < optimal TLH in S
J
-
1 Then
O = optimal TLH in S
J;
J
=
J
-
1;
Continue;
Else
Break;
(4) OutputO.In Steps(
2
) and (3-3), J
=
J
-
1 means to search solution space from moreserus to fewserus. Step (3-3) is to judge if the algorithm stops. If yes, output O; otherwise, continue to search the optimal TLH in the next subspace.Similar to Algorithm3, algorithm for models of Min-TLH with C
m
a
x constraint can be expressed as shown in Algorithm 4.Algorithm 4:Algorithm for models of Min-TLH with C
m
a
x constraint.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-TLH withC
m
a
x constraint.
(1) Initialize. SetO= null (record the optimal solution), J
=
W.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s
TLH andC
m
a
x.
(1-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying C
m
a
x constraint.
(1-3) Obtain the optimal TLH inS
J.
(1-4)O = optimal TLH in S
J;
(2)J
=
J
-
1;
(3) WhileJ
>
1 Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s
TLH andC
m
a
x.
(3-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying C
m
a
x constraint.
(3-3) Obtain the optimal TLH inS
J.
(3-4) If optimal TLH inS
J < optimal TLH in S
J
-
1 Then
O = optimal TLH in S
J;
J
=
J
-
1;
Continue;
Else
Break;
(4) OutputO.Distinguished from Algorithm3, Algorithm 4 needs to calculate C
m
a
x and to judge if C
m
a
x constraint is satisfied. They are described in steps (1-1) and (1-2).


### 4.3. Combining Features1 and 2 into the Existing Algorithm

As mentioned above, Sun et al. [21] developed a variable neighborhood search (VNS) for model of Min-C
m
a
x with TLH constraint. However, their VNS seeks the optimal solution in the whole solution space. Therefore, considering Features 1 and 2, that is, to search minimum C
m
a
x satisfying TLH constraint in the subspaces with fewerserus by redefining the neighborhood strategies, Sun’s algorithm running time will be improved.


## 4.1. Algorithms for Models of Min-C
m
a
x and Min-C
m
a
x with TLH Constraint

To avoid the obtained solution with minimumC
m
a
x being locally optimal, the algorithm does not search the subspace with the leastseru (i.e., 1seru) but searches subspaces from fewerserus to moreserus to seek minimum C
m
a
x. Therefore, the minimum C
m
a
x may be obtained by searching only a part of solution space.For an instance of Min-C
m
a
x with W workers, after obtaining the optimal solution in subspace with J
seru, the algorithm searches the optimal solution in subspace with J
+
1
serus. If the latter is not better than the former, then the algorithm will stop; otherwise, continue, until the optimal solution with J
+
1
serus is not better than the optimal solution with J
serus. The procedure can be described as shown in Algorithm 1.Algorithm 1:Algorithm for models of Min-C
m
a
x.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-C
m
a
x.
(1) Initialize. Set O = null (record the optimal solution), J
=
1.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x.
(1-2) Obtain the optimalC
m
a
x in S
J.
(1-3)O = optimal C
m
a
x in S
J;
(2)J
=
J
+
1;
(3) WhileJ
<
W Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x.
(3-2) Obtain the optimalC
m
a
x in S
J.
(3-3) If optimalC
m
a
x in S
J < optimal C
m
a
x in S
J
-
1 Then
O = optimal C
m
a
x in S
J;
J
=
J
+
1;
Continue;
Else
Break;
(4) OutputO.In Steps(
2
) and (3-3), J
=
J
+
1 means to search solution space from fewserus to moreserus. Step (3-3) is to judge if the algorithm stops. If yes, output O; otherwise, continue to search the optimal C
m
a
x in the next subspace.Similar to Algorithm1, algorithm for models of Min-C
m
a
x with TLH constraint can be expressed as shown in Algorithm 2.Algorithm 2:Algorithm for models of Min-C
m
a
x with TLH constraint.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-C
m
a
x with TLH constraint.
(1) Initialize. SetO= null (record the optimal solution), J
=
1.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x
and TLH.
(1-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying TLH constraint.
(1-3) Obtain the optimalC
m
a
x in F
J.
(1-4)O = optimal C
m
a
x in F
J;
(2)J
=
J
+
1;
(3) WhileJ
<
W Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s C
m
a
x
and TLH.
(3-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying TLH constraint.
(3-3) Obtain the optimalC
m
a
x in F
J.
(3-3) If optimalC
m
a
x in F
J < optimal C
m
a
x in F
J
-
1 Then
O = optimal C
m
a
x in F
J;
J
=
J
+
1;
Continue;
Else
Break;
(4) OutputO.Distinguished from Algorithm1, Algorithm 2 needs to calculate TLH and to judge if TLH constraint is satisfied. They are described in steps (1-1) and (1-2).


## 4.2. Algorithm for Model of Min-TLH and Min-TLH withC
m
a
x Constraint

To avoid the obtained solution with minimum TLH being locally optimal, the algorithm does not search the subspace with the mostseru (i.e., W
seru) but searches subspaces from moreserus to fewserus to seek the minimum TLH. Therefore, the minimum C
m
a
x may be obtained by searching only a part of solution space.For an instance of Min-TLH withW workers, after obtaining the optimal solution in subspace with J
seru, the algorithm searches the optimal solution in subspace with J
-
1
serus. If the latter is not better than the former, then the algorithm will stop; otherwise, continue, until the optimal solution with J
-
1
serus is not better than the optimal solution with J
serus. The procedure can be described as shown in Algorithm 3.Algorithm 3:Algorithm for models of Min-TLH.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-TLH.
(1) Initialize. SetO= null (record the optimal solution), J
=
W.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s TLH.
(1-2) Obtain the optimal TLH inS
J.
(1-3)O = optimal TLH in S
J;
(2)J
=
J
-
1;
(3) WhileJ
>
1 Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s TLH.
(3-2) Obtain the optimal TLH inS
J.
(3-3) If optimal TLH inS
J < optimal TLH in S
J
-
1 Then
O = optimal TLH in S
J;
J
=
J
-
1;
Continue;
Else
Break;
(4) OutputO.In Steps(
2
) and (3-3), J
=
J
-
1 means to search solution space from moreserus to fewserus. Step (3-3) is to judge if the algorithm stops. If yes, output O; otherwise, continue to search the optimal TLH in the next subspace.Similar to Algorithm3, algorithm for models of Min-TLH with C
m
a
x constraint can be expressed as shown in Algorithm 4.Algorithm 4:Algorithm for models of Min-TLH with C
m
a
x constraint.
Input:W (the number of workers in assembly line).
Output: The optimal solution of Min-TLH withC
m
a
x constraint.
(1) Initialize. SetO= null (record the optimal solution), J
=
W.
(1-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s
TLH andC
m
a
x.
(1-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying C
m
a
x constraint.
(1-3) Obtain the optimal TLH inS
J.
(1-4)O = optimal TLH in S
J;
(2)J
=
J
-
1;
(3) WhileJ
>
1 Do
(3-1) Generate the solution set (S
J) of sub-space with J serus according to P
(
W
,
J
)
∗
J! and calculate each solution’s
TLH andC
m
a
x.
(3-2) Produce the feasible solution set (F
J) of S
J, that is, the set of solutions satisfying C
m
a
x constraint.
(3-3) Obtain the optimal TLH inS
J.
(3-4) If optimal TLH inS
J < optimal TLH in S
J
-
1 Then
O = optimal TLH in S
J;
J
=
J
-
1;
Continue;
Else
Break;
(4) OutputO.Distinguished from Algorithm3, Algorithm 4 needs to calculate C
m
a
x and to judge if C
m
a
x constraint is satisfied. They are described in steps (1-1) and (1-2).


## 4.3. Combining Features1 and 2 into the Existing Algorithm

As mentioned above, Sun et al. [21] developed a variable neighborhood search (VNS) for model of Min-C
m
a
x with TLH constraint. However, their VNS seeks the optimal solution in the whole solution space. Therefore, considering Features 1 and 2, that is, to search minimum C
m
a
x satisfying TLH constraint in the subspaces with fewerserus by redefining the neighborhood strategies, Sun’s algorithm running time will be improved.


## 5. Computational Experiments

### 5.1. Test Instances

Tables5–9 show the parameters, data distribution and detailed data of level of skill of workers, coefficient of influencing level of skill to multiple stations for workers, and data of batches used in experiments, respectively. From Table 5, it can be observed that the lot size of each batch is N
(
50,5
) and the ability of workers is also different with stations and N
(
0.2,0.05
). Table 6 shows that the mean of skill level (β
n
i) of each worker for processing n product types ranges from 1 to 1.2 and the standard deviations are fixed to 0.1. The detailed data of β
n
i are given in Table 7. The detailed data of ε
i and batches are given in Tables 8 and 9, respectively. In fact, data in Tables 5–9 is the part of data used in Yu et al. [20].Table 5
The parameters used in experiments.
Product types
Batch size
ε
i
S
L
n
S
C
P
n
T
n
η
i
5
N
(
50,5
)
N
(
0.2,0.05
)
2.2
1.0
1.8
10
N
(
50,5
): normal distribution (μ
=
50, σ = 5).Table 6
Data distribution of worker’s level of skill (β
n
i).
Product types
1
2
3
4
5
N
(
1,0.1
)
N
(
1.05,0.1
)
N
(
1.1,0.1
)
N
(
1.15,0.1
)
N
(
1.2,0.1
)Table 7
Data of worker’s level of skill (β
n
i).
Worker/product type
1
2
3
4
5
1
0.92
0.96
1.04
1.09
1.2
2
0.95
0.97
1.09
1.12
1.18
3
0.99
1.01
1.05
1.09
1.21
4
1.03
1.07
1.09
1.12
1.25
5
0.96
1.02
1.05
1.1
1.18
6
1.01
1.1
1.1
1.15
1.23
7
1.04
1.07
1.09
1.17
1.24
8
0.98
1.02
1.1
1.11
1.2
9
0.97
1.03
1.12
1.19
1.26
10
0.98
1.06
1.13
1.18
1.28Table 8
Coefficient of influencing level of skill to multiple stations for workers (ε
i).
Worker
1
2
3
4
5
6
7
8
9
10
ε
i
0.18
0.19
0.2
0.21
0.2
0.2
0.2
0.22
0.19
0.19Table 9
Data of batches.
Batch number
Product type
Batch size (B
m)
1
3
55
2
5
53
3
3
54
4
4
49
5
1
49
6
4
55
7
1
54
8
2
48
9
2
48
10
3
48
11
2
46
12
4
58
13
3
48
14
4
52
15
5
48
16
5
51
17
1
54
18
4
57
19
2
54
20
5
49
21
1
53
22
3
46
23
4
45
24
5
46
25
2
45
26
3
44
27
1
53
28
4
47
29
2
53
30
3
52For the instance withW workers, we use the following data set from Tables 5–9: entire Table 5, first W rows of Table 7, first W columns of Table 8, and entire Table 9.


### 5.2. Hardware and Software Specifications

The four algorithms were coded in C# and executed on an Intel Core™ 2 processors at 2.66 GHz under Windows XP using 3.49 GB of RAM.


### 5.3. Comparative Results with Enumeration

Considering the similarity between Algorithm1 (or 3) and Algorithm 2 (or 4), we used the Algorithms 1 and 3 to solve the models of Min-C
m
a
x and Min-TLH, respectively. The performance comparative results to the enumeration are shown in Table 10.Table 10
Performance comparative results to the enumeration.
Workers
Line
Enumeration
Algorithm1
Algorithm3
C
m
a
x
TLH
C
m
a
x
TLH
Time (in s)
C
m
a
x
Time (in s)
TLH
Time (in s)
6
3394
19995
2954
17602
6.43
2954
0.72
17602
3.12
7
3468
23844
2963
20627
22
2963
1.03
20627
9.08
8
3522
27686
2962
23542
157
2962
5.1
23542
51.3
9
3608
31917
2974
26582
1859
2974
9.2
26582
463.2From Table10, we can see the optimal solutions obtained by Algorithms 1 and 3 are same as the results from enumeration. Moreover, the running time is much less than that of enumeration, because algorithms search the corresponding subspaces according to the distinct features between C
m
a
x (and TLH) and subspaces instead of searching the whole solution space. In addition, the running time of Algorithm 3 is more than that of Algorithm 1. That is because the subspace with moreserus has more feasible solutions than the subspace with fewserus, as shown in Table 1.


## 5.1. Test Instances

Tables5–9 show the parameters, data distribution and detailed data of level of skill of workers, coefficient of influencing level of skill to multiple stations for workers, and data of batches used in experiments, respectively. From Table 5, it can be observed that the lot size of each batch is N
(
50,5
) and the ability of workers is also different with stations and N
(
0.2,0.05
). Table 6 shows that the mean of skill level (β
n
i) of each worker for processing n product types ranges from 1 to 1.2 and the standard deviations are fixed to 0.1. The detailed data of β
n
i are given in Table 7. The detailed data of ε
i and batches are given in Tables 8 and 9, respectively. In fact, data in Tables 5–9 is the part of data used in Yu et al. [20].Table 5
The parameters used in experiments.
Product types
Batch size
ε
i
S
L
n
S
C
P
n
T
n
η
i
5
N
(
50,5
)
N
(
0.2,0.05
)
2.2
1.0
1.8
10
N
(
50,5
): normal distribution (μ
=
50, σ = 5).Table 6
Data distribution of worker’s level of skill (β
n
i).
Product types
1
2
3
4
5
N
(
1,0.1
)
N
(
1.05,0.1
)
N
(
1.1,0.1
)
N
(
1.15,0.1
)
N
(
1.2,0.1
)Table 7
Data of worker’s level of skill (β
n
i).
Worker/product type
1
2
3
4
5
1
0.92
0.96
1.04
1.09
1.2
2
0.95
0.97
1.09
1.12
1.18
3
0.99
1.01
1.05
1.09
1.21
4
1.03
1.07
1.09
1.12
1.25
5
0.96
1.02
1.05
1.1
1.18
6
1.01
1.1
1.1
1.15
1.23
7
1.04
1.07
1.09
1.17
1.24
8
0.98
1.02
1.1
1.11
1.2
9
0.97
1.03
1.12
1.19
1.26
10
0.98
1.06
1.13
1.18
1.28Table 8
Coefficient of influencing level of skill to multiple stations for workers (ε
i).
Worker
1
2
3
4
5
6
7
8
9
10
ε
i
0.18
0.19
0.2
0.21
0.2
0.2
0.2
0.22
0.19
0.19Table 9
Data of batches.
Batch number
Product type
Batch size (B
m)
1
3
55
2
5
53
3
3
54
4
4
49
5
1
49
6
4
55
7
1
54
8
2
48
9
2
48
10
3
48
11
2
46
12
4
58
13
3
48
14
4
52
15
5
48
16
5
51
17
1
54
18
4
57
19
2
54
20
5
49
21
1
53
22
3
46
23
4
45
24
5
46
25
2
45
26
3
44
27
1
53
28
4
47
29
2
53
30
3
52For the instance withW workers, we use the following data set from Tables 5–9: entire Table 5, first W rows of Table 7, first W columns of Table 8, and entire Table 9.


## 5.2. Hardware and Software Specifications

The four algorithms were coded in C# and executed on an Intel Core™ 2 processors at 2.66 GHz under Windows XP using 3.49 GB of RAM.


## 5.3. Comparative Results with Enumeration

Considering the similarity between Algorithm1 (or 3) and Algorithm 2 (or 4), we used the Algorithms 1 and 3 to solve the models of Min-C
m
a
x and Min-TLH, respectively. The performance comparative results to the enumeration are shown in Table 10.Table 10
Performance comparative results to the enumeration.
Workers
Line
Enumeration
Algorithm1
Algorithm3
C
m
a
x
TLH
C
m
a
x
TLH
Time (in s)
C
m
a
x
Time (in s)
TLH
Time (in s)
6
3394
19995
2954
17602
6.43
2954
0.72
17602
3.12
7
3468
23844
2963
20627
22
2963
1.03
20627
9.08
8
3522
27686
2962
23542
157
2962
5.1
23542
51.3
9
3608
31917
2974
26582
1859
2974
9.2
26582
463.2From Table10, we can see the optimal solutions obtained by Algorithms 1 and 3 are same as the results from enumeration. Moreover, the running time is much less than that of enumeration, because algorithms search the corresponding subspaces according to the distinct features between C
m
a
x (and TLH) and subspaces instead of searching the whole solution space. In addition, the running time of Algorithm 3 is more than that of Algorithm 1. That is because the subspace with moreserus has more feasible solutions than the subspace with fewserus, as shown in Table 1.


## 6. Conclusions and Future Research

In the research, three main contributions can be summarized as follows.Firstly, by combining two common evaluated performances ofC
m
a
x and TLH with four constraints ofseru-formation,seru-load, C
m
a
x, and TLH, we summarize the two existing models and formulate three other usually used models in line-pureseru system conversion. The two evaluated performances, four classified constraints, and formulated models are summarized in Table 11.Table 11
Evaluated performances, constraints, and formulated models.
Evaluated performances
Expression
Makespan (C
m
a
x)
C
m
a
x
=
m
a
x
m
=
1
M
(
F
C
B
m
+
F
C
m
+
S
C
m
), (8)
Total labor hours (TLH)
T
L
H
=
∑
m
=
1
M
∑
i
=
1
W
(
∑
j
=
1
J
∑
k
=
1
M
F
C
m
X
i
j
Z
m
j
k
), (9)
Constrains
Equations
Seru-formation
(10), (11), and (12)
Seru-load
(13) and (14)
C
m
a
x
(15)
TLH
(16)
Models
Expression
Min-C
m
a
x
min (8), s.t. (10)–(14)
Min-C
m
a
x with TLH constraint
min (8), s.t. (10)–(14), (16)
Min-TLH
min (9), s.t. (10)–(14)
Min-TLH withC
m
a
x constraint
min (9), s.t. (10)–(14), (15)
Min-C
m
a
x and TLH
min ((8) and (9)), s.t. (10)–(14)Secondly, we investigate the solution space feature of line-pureseru system conversion by dividing them into W subspaces according to the number ofserus (J). Subsequently, we focus on analyzing the features between C
m
a
x (and TLH) and subspaces in detail. The obtained distinct features are shown in Table 12.Table 12
Distinct features betweenC
m
a
x (and TLH) and subspaces.
Features
Content
1
MinimumC
m
a
x usually exists in the subspaces with few serus.
2
Except for the subspace with 1seru, the minimum C
m
a
x of the subspaces with fewer serus usually is less than that of the subspaces with more serus.
3
Minimum TLH usually exists in the subspaces with moreserus.
4
Minimum TLH of the subspaces with moreserus usually is less than that of the subspaces with fewer serus.Thirdly, according to the distinct features of solution space, especially the features betweenC
m
a
x (and TLH) and subspaces, we propose four algorithms to solve four single-objective models, respectively. Table 13 summarizes each proposed algorithm, based-on-features, and solved model.Table 13
Algorithm features and solved model.
Algorithms
Based-on-features
Solved model
Algorithm1
Features1 and 2
Min-C
m
a
x
Algorithm2
Features1 and 2
Min-C
m
a
x with TLH constraint
Algorithm3
Features3 and 4
Min-TLH
Algorithm4
Features3 and 4
Min-TLH withC
m
a
x constraintThe research on the line-seru conversion is relatively lacking. A thorough research problem list can be found in Yin et al. [20], such as partially cross-trained workers (i.e., a worker cannot perform all assembly tasks), different products have different assembly tasks, cost ofkarakuri (a Japanese word meaning duplication of equipment), and human and psychology factors.In addition, line-hybridseru system conversion (i.e., the hybrid system withserus and short line is the second type of the line-seru conversion defined by Kaku et al. [10]) is more complex and more real than line-pureseru system conversion. Therefore, the further research should be focused on the line-hybridseru system conversion.



---

*Source: 9748378-2016-07-11.xml*