# A Novel Assembly Line Scheduling Algorithm Based on CE-PSO

Authors: Xiaomei Hu; Zhenghao Xu; Long Yang; Rujiang Zhou
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With the widespread application of assembly line in enterprises, assembly line scheduling is an important problem in the production since it directly affects the productivity of the whole manufacturing system. The mathematical model of assembly line scheduling problem is put forward and key data are confirmed. A double objective optimization model based on equipment utilization and delivery time loss is built, and optimization solution strategy is described.  Based on the idea of solution strategy, assembly line scheduling algorithm based on CE-PSO is proposed to overcome the shortcomings of the standard PSO. Through the simulation experiments of two examples, the validity of the assembly line scheduling algorithm based on CE-PSO is proved.


---

## Body

## 1. Introduction

With the rapid development of economy and technology, there is a trend of diversification in manufacturing companies [1]. In order to meet this tendency, many advanced manufacturing modes, such as just-in-time (JIT), material requirements planning (MRP), manufacturing resource planning (MRPII), enterprise resource planning (ERP), and computer integrated manufacturing (CIM), are proposed [2]. Computer integrated manufacturing system (CIMS) based on the combination of new production organization principles and concepts is one of new production models [3]. Many examples prove that successful application of CIMS in manufacturing enterprises has brought huge improvement to the production, operation, and management of enterprises [4]. The assembly line scheduling is one of the difficult problems in the application of CIMS [5, 6].In the actual production process, enterprises may achieve the make-to-order (MTO) thought balancing the flexible production planning and controlling the production management. Since an excellent schedule of assembly line is able to meet the need of market, which is also the requirement of JIT, the assembly line planning and scheduling has become an important means for the enterprise to save resources, reduce costs, increase productivity, and improve the overall operational efficiency [7, 8].Assembly line scheduling is a nondeterministic polynomial (NP) complete problem. With the development of heuristic algorithm, many advanced algorithms, such as genetic algorithm and ant colony (AC) algorithm, are applied to solve the scheduling problem [9, 10]. The paper [11] defines the production scheduling as a function of technical process and workpiece delivery from the perspective of production tasks and orders. In order to solve the problem of the production line scheduling in the MTO enterprise, the paper [12] establishes a general model of the MTO enterprise scheduling by applying the theory of linear programming MTO enterprises based on the analysis of its scheduling features and the stipulation of the scheduling. The adaptive genetic algorithms for solving scheduling model are proposed. The paper [13] introduces the concept of advanced planning and scheduling in order to study the problem of the production planning and scheduling which exists in discrete manufacturing. Through analyzing and applying the core ideas of the concept which is comparative advantage of constraints theory, the paper builds the advanced scheduling model based on machine capacity by applying the linear programming algorithm. Although there is a great development in the area of the production scheduling, no systematical methods and theories can solve all the assembly line scheduling application problem because of a huge gap between theoretical research and practical application. Particularly with the widespread adoption of JIT in the scheduling problems, the delivery just-in-time becomes increasingly important. In practical application, the scheduling method can respond to the dynamics of the system, but the result of the method is not guaranteed. Some methods of scheduling can theoretically provide optimal scheduling, but these often can only solve the problem of single target due to its computational complexity.In this paper, a multiobjective optimization function based on equipment utilization and delivery time loss is constructed and a Catfish Effect (CE) Particle Swarm Optimization (PSO) algorithm is applied to solve the assembly line scheduling problem in view of its high solution precision and good robustness [14].


## 2. Related Work

### 2.1. PSO Algorithm

The Particle Swarm Optimization (PSO) is an evolutionary computation developed by Zeng and Cui [15]. It simulated the social swarm behavior of bird group in the early time. PSO treats each individual as a particle which has no weight and volume in n dimensional search space and the particle flies at a certain speed in the search space. The speed is dynamically adjusted based on the flying experience of individual and group [16].In then dimensional search space, Xi=(xi1,xi2,…,xin) express a current position of particle i.V
i
=
(
v
i
1
,
v
i
2
,
…
,
v
i
n
) express the speed; vi is the current speed of particle i.P
i
=
(
p
i
1
,
p
i
2
,
…
,
p
i
n
) express the best experiencing position of particle i; namely, Pi has the smallest fitness.Assume thatf(x) is the minimized objective function; the best position of particle i is calculated as follows [17]:
(1)Pi(t+1)=Pi(t)f(Pi(t))≤f(Xi(t+1))Xi(t+1)f(Pi(t))>f(Xi(t+1)).Assume that the number of particles iss in population; all particles have experienced the best position Pg(t); then [18]
(2)Pgt∈{P0(t),…,Pg(t)}∣f(Pg(t))=min⁡{f(P0(t)),…,f(Ps(t))}.PSO algorithm basic solving equations are as follows [19].Speed and position evolution equations are shown as(3)Vit+1=wVi(t)+c1r1(Pi(t)-xi(t))+c2r2Pgt-Xit,Xi(t+1)=Xi(t)+Vi(t+1).In (3), c1 and c2 are the acceleration constants, which take the value in (0,2). r1 and r2 both are a random number between (0,1); w is inertia coefficient between (0,1) and it has the ability of keeping inertia expansion of particle movement to explore new areas.PSO was developed and used as a useful computation technique to tackle the optimization problem. However, in PSO algorithm, particles seek the optimal solution by its own memory ability and the information shared among particles. At the beginning of PSO algorithm, the particles have quick convergence speed. When most of the particles have similar state with the passage of time, the convergence speed of the particles becomes slow, which maybe leads to the algorithm into a local optimal solution. This is also called “precocious phenomena” [20].As the optimization performance of the original PSO algorithm is not ideal, various revised versions of PSO have been studied to overcome “precocious phenomena.” The related work includes modifying the updating formula, introducing new operator into PSO, and developing hybrid PSO algorithm [21]. Currently, chaos PSO algorithm, genetic PSO algorithm, immune PSO algorithm in adaptive, and bee evolutionary PSO algorithm are studied to improve the diversity of particle population and guide directions to research [22, 23]. With the continuous improvement, PSO algorithm has been used in many fields because of its simple concept, easy implementation, few parameters to tune, and excellent optimization ability.


### 2.2. Catfish Effect PSO

Most of advanced PSO algorithms aim to modify the position coordinates of individual particles, instead of the population. However, Catfish Effect PSO (CE-PSO) algorithm can modify the position coordinates of the population to obtain the noninferior set on behalf of the entire solution space, homogeneous distribution, and immediate Pareto front and improve convergence velocity of PSO algorithm [24].Catfish Effect (CE) refers to the effect that a strong competitor called catfish has in causing the weak sardines to better themselves. CE mechanism is the fact that the algorithm introduces dynamic and competitive individuals into the population to change social loafing and inspire community [25]. In the framework of CE mechanism, three core elements are as follows.(1)
The population has been at a relatively stable level, and the catfish particle needs to be introduced to achieve the population objectives.(2)
The catfish particle has high quality and individual competitiveness in the population.(3)
The catfish particle can use negative incentives to enhance population vitality.Different from PSO algorithm, speed evolution equations of CE-PSO algorithm are shown as(4)Vit+1=wVi(t)+c1r1(Pi(t)-xi(t))+c2r2(Pg(t)-Xi(t)),c1r1=1ϕ(t)≤ϕ1c1r1ϕ(t)>ϕ1,c2r2=1ϕ(t)≤ϕc2r2ϕ(t)>ϕ1.In (4), ϕ1 is a threshold value of population diversity and ϕ(t) is a function which is used to evaluate the population diversity at the time t. If ϕ(t)≤ϕ1, the diversity of the population is poor and catfish particle is introduced into population; if ϕ(t)>ϕ, CE-PSO algorithm and PSO algorithm have the identical definition.The effect of CE to PSO algorithm is shown in Figure1. Compared with PSO algorithm, CE-PSO algorithm monitors the diversity of the population [26]. When the diversity is poor, CE-PSO algorithm introduces the catfish particle with the driving role to encourage population activity and maintain the population diversity [27]. In order to improve the search performance, CE-PSO algorithm can regulate flight mode of sardine particles dynamically according to the convergence of catfish [28].Figure 1
The effect of CE on PSO algorithm.Due to the good performance of CE-PSO algorithm, CE-PSO is applied to solve assembly line scheduling problem.


## 2.1. PSO Algorithm

The Particle Swarm Optimization (PSO) is an evolutionary computation developed by Zeng and Cui [15]. It simulated the social swarm behavior of bird group in the early time. PSO treats each individual as a particle which has no weight and volume in n dimensional search space and the particle flies at a certain speed in the search space. The speed is dynamically adjusted based on the flying experience of individual and group [16].In then dimensional search space, Xi=(xi1,xi2,…,xin) express a current position of particle i.V
i
=
(
v
i
1
,
v
i
2
,
…
,
v
i
n
) express the speed; vi is the current speed of particle i.P
i
=
(
p
i
1
,
p
i
2
,
…
,
p
i
n
) express the best experiencing position of particle i; namely, Pi has the smallest fitness.Assume thatf(x) is the minimized objective function; the best position of particle i is calculated as follows [17]:
(1)Pi(t+1)=Pi(t)f(Pi(t))≤f(Xi(t+1))Xi(t+1)f(Pi(t))>f(Xi(t+1)).Assume that the number of particles iss in population; all particles have experienced the best position Pg(t); then [18]
(2)Pgt∈{P0(t),…,Pg(t)}∣f(Pg(t))=min⁡{f(P0(t)),…,f(Ps(t))}.PSO algorithm basic solving equations are as follows [19].Speed and position evolution equations are shown as(3)Vit+1=wVi(t)+c1r1(Pi(t)-xi(t))+c2r2Pgt-Xit,Xi(t+1)=Xi(t)+Vi(t+1).In (3), c1 and c2 are the acceleration constants, which take the value in (0,2). r1 and r2 both are a random number between (0,1); w is inertia coefficient between (0,1) and it has the ability of keeping inertia expansion of particle movement to explore new areas.PSO was developed and used as a useful computation technique to tackle the optimization problem. However, in PSO algorithm, particles seek the optimal solution by its own memory ability and the information shared among particles. At the beginning of PSO algorithm, the particles have quick convergence speed. When most of the particles have similar state with the passage of time, the convergence speed of the particles becomes slow, which maybe leads to the algorithm into a local optimal solution. This is also called “precocious phenomena” [20].As the optimization performance of the original PSO algorithm is not ideal, various revised versions of PSO have been studied to overcome “precocious phenomena.” The related work includes modifying the updating formula, introducing new operator into PSO, and developing hybrid PSO algorithm [21]. Currently, chaos PSO algorithm, genetic PSO algorithm, immune PSO algorithm in adaptive, and bee evolutionary PSO algorithm are studied to improve the diversity of particle population and guide directions to research [22, 23]. With the continuous improvement, PSO algorithm has been used in many fields because of its simple concept, easy implementation, few parameters to tune, and excellent optimization ability.


## 2.2. Catfish Effect PSO

Most of advanced PSO algorithms aim to modify the position coordinates of individual particles, instead of the population. However, Catfish Effect PSO (CE-PSO) algorithm can modify the position coordinates of the population to obtain the noninferior set on behalf of the entire solution space, homogeneous distribution, and immediate Pareto front and improve convergence velocity of PSO algorithm [24].Catfish Effect (CE) refers to the effect that a strong competitor called catfish has in causing the weak sardines to better themselves. CE mechanism is the fact that the algorithm introduces dynamic and competitive individuals into the population to change social loafing and inspire community [25]. In the framework of CE mechanism, three core elements are as follows.(1)
The population has been at a relatively stable level, and the catfish particle needs to be introduced to achieve the population objectives.(2)
The catfish particle has high quality and individual competitiveness in the population.(3)
The catfish particle can use negative incentives to enhance population vitality.Different from PSO algorithm, speed evolution equations of CE-PSO algorithm are shown as(4)Vit+1=wVi(t)+c1r1(Pi(t)-xi(t))+c2r2(Pg(t)-Xi(t)),c1r1=1ϕ(t)≤ϕ1c1r1ϕ(t)>ϕ1,c2r2=1ϕ(t)≤ϕc2r2ϕ(t)>ϕ1.In (4), ϕ1 is a threshold value of population diversity and ϕ(t) is a function which is used to evaluate the population diversity at the time t. If ϕ(t)≤ϕ1, the diversity of the population is poor and catfish particle is introduced into population; if ϕ(t)>ϕ, CE-PSO algorithm and PSO algorithm have the identical definition.The effect of CE to PSO algorithm is shown in Figure1. Compared with PSO algorithm, CE-PSO algorithm monitors the diversity of the population [26]. When the diversity is poor, CE-PSO algorithm introduces the catfish particle with the driving role to encourage population activity and maintain the population diversity [27]. In order to improve the search performance, CE-PSO algorithm can regulate flight mode of sardine particles dynamically according to the convergence of catfish [28].Figure 1
The effect of CE on PSO algorithm.Due to the good performance of CE-PSO algorithm, CE-PSO is applied to solve assembly line scheduling problem.


## 3. Mathematical Model of Assembly Line Scheduling Problem

### 3.1. The Description of Assembly Line Scheduling Problem

Assume thatN workpieces are scheduled to M machines in the assembly line and the working time for machines is TM. The maximal and minimal working time of machines are TMmax⁡ and TMmin⁡, respectively. So, TMmax⁡≤TM≤TMmin⁡. Ji (i=1,2,…,M) is machine j. The preconcerted delivery time for all the workpiece i  (i=1,2,…,N) is T.The assumptions of assembly line scheduling problem are as follows.(1)
The machining sequence of workpiece is determined in advance; namely, there is a clear constraint on all the machines in each workpiece, which can be expressed asJi1>Ji2>⋯>JiM.(2)
A machine can only realize a single process of a workpiece, and a workpiece can only be machined in a machine at a time.(3)
There is waiting time among the processes of workpieces, and the idle time of the machine is permitted.(4)
For each workpiece, the starting time of the process is equal to or later than the ending time of the preceding process.(5)
The number of machines and workpieces is certain before scheduling.(6)
All the workpieces can be machined from zero time.(7)
The readiness time of machine is negligible.The main parameters of assembly line scheduling problem are represented as follows.


#### 3.1.1. Equipment Utilization

Equipment utilization refers to the percentage of the running machines in all the machines. It reflects the economic and technical indicators of production efficiency. The machines mean a variety of devices in the assembly line. Equipment utilization can be expressed as(5)W1=1-TMmin⁡TMmax⁡.


#### 3.1.2. Delivery Time Loss

In the actual production, there is stock cost if orders are completed ahead of schedule; there is delay cost if orders cannot deliver on time [29]. So delivery time loss is defined to reflect customer satisfaction, which is expressed as
(6)W2=μ1(T-TM)T≥TMμ2(TM-T)T≤TM.In (6), μ1 is stock factor, μ2 is delay factor, T≥TM means that the orders are completed ahead of schedule, and T≤TM means that the orders cannot deliver on time.


#### 3.1.3. Production Efficiency

Production efficiency refers to the percentage of actual output of assembly line in all maximal output. It can be used to measure whether the assembly line is producing as much as possible without wasting precious resources. Theoretically, production efficiency will include all of the points along the production possibility frontier, but it is difficult to measure in practice [30].


### 3.2. A Multiobjective Optimization Model of Assembly Line Scheduling Problem

From the description of assembly line scheduling problem, equipment utilization and delivery time loss can be chosen as optimization goal since production efficiency is hardly applied in the actual production. Due to the correlation between the goals, optimizing a single goal may cause the neglect of the other goal. As a result, the optimization results can often not accord with the actual situation of assembly line scheduling. In this paper, equipment utilization and delivery time loss are chosen as optimization goals. The fitness functionf1 and the objective function min⁡f1 are constructed to realize the comprehensive optimal goals of assembly line scheduling.Fitness function is defined as(7)f1=b1*W1+b2*W2.The constraint conditions include(8)TiJend≥TiJstart≥0,TiJend≥TiJstart+TiJ,TJ≥∑i=1NTiJ.The fitness functionf1 takes advantage of the linear weighted average model of equipment utilization and delivery time loss. b1 and b2 are weight value, and b1+b2=1. Specific values can also be used according to the specific situation.In constraint conditions (8), TiJstart and TiJend are the time when the workpiece i starts and ends to process in the machine J, TiJ is the processing time with the workpiece i on the machine J, and TJ is the working time for machine J.


### 3.3. Solution Strategy

In order to solve the assembly line scheduling problem, the following steps are adopted.(1)
A kind of coding method based on workpiece is proposed and a series of scheduling schemes{Sk∣k=1,2,3,…,m} which meets the idle time arrangement of machines are concluded from workpiece set E={1,2,3,…i…,N}.(2)
According to the scheduling schemesSk in step one above, each value of delivery time losses in scheduling scheme is calculated and {Sk∣k=1,2,3,…,m} with the minimum value of objective function min⁡f1 is taken as the optimal arrangement scheme.


## 3.1. The Description of Assembly Line Scheduling Problem

Assume thatN workpieces are scheduled to M machines in the assembly line and the working time for machines is TM. The maximal and minimal working time of machines are TMmax⁡ and TMmin⁡, respectively. So, TMmax⁡≤TM≤TMmin⁡. Ji (i=1,2,…,M) is machine j. The preconcerted delivery time for all the workpiece i  (i=1,2,…,N) is T.The assumptions of assembly line scheduling problem are as follows.(1)
The machining sequence of workpiece is determined in advance; namely, there is a clear constraint on all the machines in each workpiece, which can be expressed asJi1>Ji2>⋯>JiM.(2)
A machine can only realize a single process of a workpiece, and a workpiece can only be machined in a machine at a time.(3)
There is waiting time among the processes of workpieces, and the idle time of the machine is permitted.(4)
For each workpiece, the starting time of the process is equal to or later than the ending time of the preceding process.(5)
The number of machines and workpieces is certain before scheduling.(6)
All the workpieces can be machined from zero time.(7)
The readiness time of machine is negligible.The main parameters of assembly line scheduling problem are represented as follows.


### 3.1.1. Equipment Utilization

Equipment utilization refers to the percentage of the running machines in all the machines. It reflects the economic and technical indicators of production efficiency. The machines mean a variety of devices in the assembly line. Equipment utilization can be expressed as(5)W1=1-TMmin⁡TMmax⁡.


### 3.1.2. Delivery Time Loss

In the actual production, there is stock cost if orders are completed ahead of schedule; there is delay cost if orders cannot deliver on time [29]. So delivery time loss is defined to reflect customer satisfaction, which is expressed as
(6)W2=μ1(T-TM)T≥TMμ2(TM-T)T≤TM.In (6), μ1 is stock factor, μ2 is delay factor, T≥TM means that the orders are completed ahead of schedule, and T≤TM means that the orders cannot deliver on time.


### 3.1.3. Production Efficiency

Production efficiency refers to the percentage of actual output of assembly line in all maximal output. It can be used to measure whether the assembly line is producing as much as possible without wasting precious resources. Theoretically, production efficiency will include all of the points along the production possibility frontier, but it is difficult to measure in practice [30].


## 3.1.1. Equipment Utilization

Equipment utilization refers to the percentage of the running machines in all the machines. It reflects the economic and technical indicators of production efficiency. The machines mean a variety of devices in the assembly line. Equipment utilization can be expressed as(5)W1=1-TMmin⁡TMmax⁡.


## 3.1.2. Delivery Time Loss

In the actual production, there is stock cost if orders are completed ahead of schedule; there is delay cost if orders cannot deliver on time [29]. So delivery time loss is defined to reflect customer satisfaction, which is expressed as
(6)W2=μ1(T-TM)T≥TMμ2(TM-T)T≤TM.In (6), μ1 is stock factor, μ2 is delay factor, T≥TM means that the orders are completed ahead of schedule, and T≤TM means that the orders cannot deliver on time.


## 3.1.3. Production Efficiency

Production efficiency refers to the percentage of actual output of assembly line in all maximal output. It can be used to measure whether the assembly line is producing as much as possible without wasting precious resources. Theoretically, production efficiency will include all of the points along the production possibility frontier, but it is difficult to measure in practice [30].


## 3.2. A Multiobjective Optimization Model of Assembly Line Scheduling Problem

From the description of assembly line scheduling problem, equipment utilization and delivery time loss can be chosen as optimization goal since production efficiency is hardly applied in the actual production. Due to the correlation between the goals, optimizing a single goal may cause the neglect of the other goal. As a result, the optimization results can often not accord with the actual situation of assembly line scheduling. In this paper, equipment utilization and delivery time loss are chosen as optimization goals. The fitness functionf1 and the objective function min⁡f1 are constructed to realize the comprehensive optimal goals of assembly line scheduling.Fitness function is defined as(7)f1=b1*W1+b2*W2.The constraint conditions include(8)TiJend≥TiJstart≥0,TiJend≥TiJstart+TiJ,TJ≥∑i=1NTiJ.The fitness functionf1 takes advantage of the linear weighted average model of equipment utilization and delivery time loss. b1 and b2 are weight value, and b1+b2=1. Specific values can also be used according to the specific situation.In constraint conditions (8), TiJstart and TiJend are the time when the workpiece i starts and ends to process in the machine J, TiJ is the processing time with the workpiece i on the machine J, and TJ is the working time for machine J.


## 3.3. Solution Strategy

In order to solve the assembly line scheduling problem, the following steps are adopted.(1)
A kind of coding method based on workpiece is proposed and a series of scheduling schemes{Sk∣k=1,2,3,…,m} which meets the idle time arrangement of machines are concluded from workpiece set E={1,2,3,…i…,N}.(2)
According to the scheduling schemesSk in step one above, each value of delivery time losses in scheduling scheme is calculated and {Sk∣k=1,2,3,…,m} with the minimum value of objective function min⁡f1 is taken as the optimal arrangement scheme.


## 4. Assembly Line Scheduling Algorithm Based on CE-PSO

Assembly line scheduling algorithm based on CE-PSO sets the following parameters: population quantityPN, the number of iterations G, inertia weight w, accelerated constant c, the initial position, and velocity of each particle.


### 4.1. Coding of Assembly Line Scheduling Problem

The most important job is to code in order to solve the assembly line scheduling problem using CE-PSO algorithm. Three are many coding methods for the scheduling problem. Among the numerous coding methods, coding based on workpiece, coding based on machine, and coding based on operation are used in the optimization problem frequently [31]. In view of the particularity of assembly line scheduling problem, a coding method based on operation sequence is adopted in this paper. Each particle Xi(i=1,…,PN) has the length of N×M; then Xi=(xi1,…,xiM×N).In the particleXi, each element xij  j∈1,M×N corresponds to a workpiece number. Each workpiece number has M copies in Xi. Workpiece operation sequence is determined by the position of element in the particle.Workpiece operation sequence can be expressed by precedence relation diagram. Assuming there are four machines and three workpieces in the assembly line, its precedence relation diagram is shown in Figure2.Figure 2
Precedence relation diagram with four machines and three workpieces.Each processing time of the workpieces in the machines is shown in Table1.Table 1
Processing time of the workpieces in the machines.
The operation sequence
Step  1
Step  2
Step  3
Step  4
I
1
J
1
(
10
)
J
2
(
20
)
J
3
(
10
)
J
4
(
10
)
I
2
J
1
(
10
)
J
3
(
10
)
J
2
(
20
)
J
4
(
20
)
I
3
J
2
(
20
)
J
1
(
10
)
J
3
(
10
)
J
4
(
20
)In Table1, I1, I2, and I3 are the operation sequence of workpieces 1, 2, and 3:
(9)I1=J1,J2,J3,J4,I2=J1,J3,J2,J4,I3={J2,J1,J3,J4}.The processing time of the workpieces in the machines is marked in the blankets.Assuming the particleXi=2,1,2,1,3,3,1,1,2,2,3,3, the workpiece operation sequence in four machines is shown in Figure 3.Figure 3
The workpiece operation sequence in four machines.


### 4.2. Batching Strategy

Since workpieces can be mass produced in the most situations, batching scheduling can reduce the idle time of machines and improve the equipment utilization. Minimum volume batching principle is applied in the assembly line scheduling algorithm in this paper. Assuming the demand of workpiecei is Qi, minimum volume is Pmin⁡; the batch number mi′ is defined as
(10)mi′=QiPmin⁡.The numberQTi(ξ) of workpieces i in each batch ξ is calculated as
(11)QTi(ξ)=Qimi′+ranξ(0,Qi-mi′×Pmin⁡),∑ξranξ(0,Qi-mi′×Pmin⁡)=Qi-mi′×Pmin⁡.


### 4.3. Population Similarity of CE-PSO Algorithm

In CE-PSO algorithm, population diversityϕ(t) at the time t is defined as(12)f1(XO(t))=min⁡f1(X1(t),…,Xi(t),…,XPN(t)),ϕt=∑i=1PNf1Xit/PN-f1XOtf1XOt.In (12), XO(t) is the optimal particle which has the minimal value of objective function f1 at the time t. According to the definition of population diversity, 0≤ϕ(t)≤1. The smaller the value of ϕ(t) is, the worse the population diversity is. If ϕ(t)<ϕ1, CE-PSO algorithm introduces the catfish particles to enhance the vitality of the population; otherwise, the standard PSO algorithm is applied to produce a new generation of particles.


### 4.4. The Particle Updating Formula of CE-PSO Algorithm

The particle updating formula is defined as(13)Xi(t+1)=g(Xi(t),pBi(t))ϕ(t)<ϕ1∥β<cXi(t)otherwise.p
B
i
(
t
) is the best position of particle i in t iterations:
(14)f1(pBi(t))=min⁡(f1(Xi(1)),…,f1(Xi(t)))t∈[1,G].β is a random number distributed in [0,1] uniformly.The meaning of functiong(Vi(t),pBi(t)) is the adjustment of particles according to their best position in the i iteration. The specific implementation processes are as follows.(1)
An integerθ from 1 to m×n is randomly selected to make pBi(t) be divided into two sets {S(1)i}, {S(2)i}.(2)
zi(t) expresses the new particle i in the iteration t. The element zil(t)l∈[1,M×N] corresponds to a workpiece. Take l=1,j=1.(3)
Ifxij(t)=S(1)ij, zil(t)=xij(t); if pBij(t)=S(2)ij, zil(t)=pBij(t). l=l+1,  j=j+1.(4)
Ifl=M×N, output Xi(t+1)=zi(t); otherwise, go to (3).


### 4.5. The Specific Steps of CE-PSO Algorithm

The specific steps of CE-PSO algorithm are as follows.(1)
The initialization of the algorithm: set initialization parametersw, c, b1, b2, μ1, μ2, T, and ϕ1 and confirm the number of iterations G.(2)
GeneratePN initialized particles based on batching strategy and coding method.(3)
The initialization ofpBi(t) and the global optimal particle gB(t):
(15)f1(gB(t))=min⁡(f1(pBi(t)))i∈[1,PN].(4)
Fort=1:G, calculate the value of ϕ(t), generate a random number β, update each particle’s position according to the particle updating formula, and determine the value of the new pBi(t) and gB(t) according to the fitness function min⁡f1 and complete the update of pBi(t) and gB(t).(5)
End the iteration and output the result afterG iterations.


## 4.1. Coding of Assembly Line Scheduling Problem

The most important job is to code in order to solve the assembly line scheduling problem using CE-PSO algorithm. Three are many coding methods for the scheduling problem. Among the numerous coding methods, coding based on workpiece, coding based on machine, and coding based on operation are used in the optimization problem frequently [31]. In view of the particularity of assembly line scheduling problem, a coding method based on operation sequence is adopted in this paper. Each particle Xi(i=1,…,PN) has the length of N×M; then Xi=(xi1,…,xiM×N).In the particleXi, each element xij  j∈1,M×N corresponds to a workpiece number. Each workpiece number has M copies in Xi. Workpiece operation sequence is determined by the position of element in the particle.Workpiece operation sequence can be expressed by precedence relation diagram. Assuming there are four machines and three workpieces in the assembly line, its precedence relation diagram is shown in Figure2.Figure 2
Precedence relation diagram with four machines and three workpieces.Each processing time of the workpieces in the machines is shown in Table1.Table 1
Processing time of the workpieces in the machines.
The operation sequence
Step  1
Step  2
Step  3
Step  4
I
1
J
1
(
10
)
J
2
(
20
)
J
3
(
10
)
J
4
(
10
)
I
2
J
1
(
10
)
J
3
(
10
)
J
2
(
20
)
J
4
(
20
)
I
3
J
2
(
20
)
J
1
(
10
)
J
3
(
10
)
J
4
(
20
)In Table1, I1, I2, and I3 are the operation sequence of workpieces 1, 2, and 3:
(9)I1=J1,J2,J3,J4,I2=J1,J3,J2,J4,I3={J2,J1,J3,J4}.The processing time of the workpieces in the machines is marked in the blankets.Assuming the particleXi=2,1,2,1,3,3,1,1,2,2,3,3, the workpiece operation sequence in four machines is shown in Figure 3.Figure 3
The workpiece operation sequence in four machines.


## 4.2. Batching Strategy

Since workpieces can be mass produced in the most situations, batching scheduling can reduce the idle time of machines and improve the equipment utilization. Minimum volume batching principle is applied in the assembly line scheduling algorithm in this paper. Assuming the demand of workpiecei is Qi, minimum volume is Pmin⁡; the batch number mi′ is defined as
(10)mi′=QiPmin⁡.The numberQTi(ξ) of workpieces i in each batch ξ is calculated as
(11)QTi(ξ)=Qimi′+ranξ(0,Qi-mi′×Pmin⁡),∑ξranξ(0,Qi-mi′×Pmin⁡)=Qi-mi′×Pmin⁡.


## 4.3. Population Similarity of CE-PSO Algorithm

In CE-PSO algorithm, population diversityϕ(t) at the time t is defined as(12)f1(XO(t))=min⁡f1(X1(t),…,Xi(t),…,XPN(t)),ϕt=∑i=1PNf1Xit/PN-f1XOtf1XOt.In (12), XO(t) is the optimal particle which has the minimal value of objective function f1 at the time t. According to the definition of population diversity, 0≤ϕ(t)≤1. The smaller the value of ϕ(t) is, the worse the population diversity is. If ϕ(t)<ϕ1, CE-PSO algorithm introduces the catfish particles to enhance the vitality of the population; otherwise, the standard PSO algorithm is applied to produce a new generation of particles.


## 4.4. The Particle Updating Formula of CE-PSO Algorithm

The particle updating formula is defined as(13)Xi(t+1)=g(Xi(t),pBi(t))ϕ(t)<ϕ1∥β<cXi(t)otherwise.p
B
i
(
t
) is the best position of particle i in t iterations:
(14)f1(pBi(t))=min⁡(f1(Xi(1)),…,f1(Xi(t)))t∈[1,G].β is a random number distributed in [0,1] uniformly.The meaning of functiong(Vi(t),pBi(t)) is the adjustment of particles according to their best position in the i iteration. The specific implementation processes are as follows.(1)
An integerθ from 1 to m×n is randomly selected to make pBi(t) be divided into two sets {S(1)i}, {S(2)i}.(2)
zi(t) expresses the new particle i in the iteration t. The element zil(t)l∈[1,M×N] corresponds to a workpiece. Take l=1,j=1.(3)
Ifxij(t)=S(1)ij, zil(t)=xij(t); if pBij(t)=S(2)ij, zil(t)=pBij(t). l=l+1,  j=j+1.(4)
Ifl=M×N, output Xi(t+1)=zi(t); otherwise, go to (3).


## 4.5. The Specific Steps of CE-PSO Algorithm

The specific steps of CE-PSO algorithm are as follows.(1)
The initialization of the algorithm: set initialization parametersw, c, b1, b2, μ1, μ2, T, and ϕ1 and confirm the number of iterations G.(2)
GeneratePN initialized particles based on batching strategy and coding method.(3)
The initialization ofpBi(t) and the global optimal particle gB(t):
(15)f1(gB(t))=min⁡(f1(pBi(t)))i∈[1,PN].(4)
Fort=1:G, calculate the value of ϕ(t), generate a random number β, update each particle’s position according to the particle updating formula, and determine the value of the new pBi(t) and gB(t) according to the fitness function min⁡f1 and complete the update of pBi(t) and gB(t).(5)
End the iteration and output the result afterG iterations.


## 5. The Simulation Results and Analysis

### 5.1. Operating Environment

The configuration of computer is CUP Intel Core i7, CPU clock speed 2.60 GHz, internal storage 12.00 GB, and Windows 7 operating system. C language is used to realize the CE-PSO algorithm.


### 5.2. Example 1

Take a simple assembly line with 3 workpieces and 3 machines as an example. The precedence relations diagram is shown in Figure4.Figure 4
Precedence relation diagram with three machines and three workpieces.Each processing time of the workpieces in the machines is shown in Table2.Table 2
Processing time of the workpieces in the machines.
The operation sequence
Step  1
Step  2
Step  3
I
1
J
1
(
30
)
J
2
(
30
)
J
3
(
20
)
I
2
J
1
(
10
)
J
3
(
50
)
J
2
(
30
)
I
3
J
2
(
30
)
J
1
(
20
)
J
3
(
30
)The PSO algorithm and CE-PSO algorithm are used to optimize the assembly line scheduling problem. The parameters used in PSO and CE-PSO algorithm are as follows: populationPN=20, iteration number G=100, w=0.5, c=0.5, b1=20, b2=0.5, T=130, μ1=1, μ2=3, and ϕ1=0.1. The optimization results of assembly line scheduling based on PSO and CE-PSO are shown in Figures 5 and 6.Figure 5
The optimization results of assembly line scheduling based on PSO.Figure 6
The optimization results of assembly line scheduling based on CE-PSO.The results of two algorithms are compared in Table3. From Table 3, the optimization result based on CE-PSO algorithm is better because it has higher equipment utilization and the smaller fitness f1, which shows the effectiveness of CE-PSO algorithm.Table 3
The comparison of assembly line scheduling results in experiment one.
Machine
Based on the PSO algorithm
Based on the CE-PSO algorithm
1
1, 2, 3
2, 1, 3
2
3, 1, 2
3, 1, 2
3
2, 1, 3
2, 1, 3
Delivery time
140
120
Equipment utilization
42.9%
50%
Delivery time loss
10
10
f
1
16.42
15


### 5.3. Example 2

In the assembly workshops of the sheet metal, the assembly line includes 5 machines and produces 3 different types of sheet metal parts. The job element of the sheet metal parts is shown in Table4.Table 4
The job element of the sheet metal parts.
Serial number
Job element
Standard time
1
The punching of the sheet metal
(10, 10, 15)
2
The cutting of the sheet metal
(15, 15, 20)
3
The tapping of the sheet metal
(20, 10, 10)
4
The testing of the sheet metal
(15, 10, 20)
5
The package of the sheet metal
(15, 20, 10)The precedence relations diagram is shown in Figure7.Figure 7
Precedence relation diagram with five machines and three workpieces.Assume the fact that the demands of three partsQ=1007060 and the minimum volume Pmin⁡=20. According to the batching strategy above, the batch number of three parts m′ is calculated as follows:(16)m′=QPmin⁡=543.Each processing time of the workpieces in the machines is shown in Table5.Table 5
Processing time of the workpieces in the machines.
Parts
Machine 1
Machine 2
Machine 3
Machine 4
Machine 5
I
1
J
1
(
10
)
J
2
(
15
)
J
3
(
20
)
J
4
(
15
)
J
5
(
15
)
I
2
J
1
(
20
)
J
3
(
15
)
J
2
(
10
)
J
4
(
10
)
J
5
(
20
)
I
3
J
2
(
15
)
J
1
(
20
)
J
3
(
10
)
J
4
(
20
)
J
5
(
10
)The parameters used in PSO and CE-PSO algorithm are as follows: populationPN=20, iteration number G=500, w=0.5, c=0.5, b1=1500, b2=0.5, T=5000, μ1=0.8, μ2=2, and ϕ1=0.1.The comparison of optimization results of assembly line scheduling based on PSO and CE-PSO is shown in Table6. The comparison of iteration time of two algorithms is shown in Figure 8.Table 6
The comparison of assembly line scheduling results in experiment two.
Machine
Based on the PSO algorithm
Based on the CE-PSO algorithm
1
[122132132311]
[121232133211]
2
[321212112331]
[321212112331]
3
[131212132231]
[132121212312]
4
[133212112231]
[132213121231]
5
[131211322231]
[131312122132]
Delivery time
6500
5900
Equipment utilization
55%
55.93%
Delivery time loss
1500
900
f
1
2238.46
1561.0Figure 8
The comparison of iteration time of two algorithms.From Table6, the optimization result based on CE-PSO algorithm is better than that based on PSO algorithm because it has higher equipment utilization and lower delivery time loss and the smaller fitness f1, which shows the effectiveness of CE-PSO algorithm. From Figure 8, the iteration results of PSO algorithm are similar to those of CE-PSO algorithm at the beginning 70 steps. With the increase of the iteration steps, CE-PSO algorithm achieves the better optimization result.


## 5.1. Operating Environment

The configuration of computer is CUP Intel Core i7, CPU clock speed 2.60 GHz, internal storage 12.00 GB, and Windows 7 operating system. C language is used to realize the CE-PSO algorithm.


## 5.2. Example 1

Take a simple assembly line with 3 workpieces and 3 machines as an example. The precedence relations diagram is shown in Figure4.Figure 4
Precedence relation diagram with three machines and three workpieces.Each processing time of the workpieces in the machines is shown in Table2.Table 2
Processing time of the workpieces in the machines.
The operation sequence
Step  1
Step  2
Step  3
I
1
J
1
(
30
)
J
2
(
30
)
J
3
(
20
)
I
2
J
1
(
10
)
J
3
(
50
)
J
2
(
30
)
I
3
J
2
(
30
)
J
1
(
20
)
J
3
(
30
)The PSO algorithm and CE-PSO algorithm are used to optimize the assembly line scheduling problem. The parameters used in PSO and CE-PSO algorithm are as follows: populationPN=20, iteration number G=100, w=0.5, c=0.5, b1=20, b2=0.5, T=130, μ1=1, μ2=3, and ϕ1=0.1. The optimization results of assembly line scheduling based on PSO and CE-PSO are shown in Figures 5 and 6.Figure 5
The optimization results of assembly line scheduling based on PSO.Figure 6
The optimization results of assembly line scheduling based on CE-PSO.The results of two algorithms are compared in Table3. From Table 3, the optimization result based on CE-PSO algorithm is better because it has higher equipment utilization and the smaller fitness f1, which shows the effectiveness of CE-PSO algorithm.Table 3
The comparison of assembly line scheduling results in experiment one.
Machine
Based on the PSO algorithm
Based on the CE-PSO algorithm
1
1, 2, 3
2, 1, 3
2
3, 1, 2
3, 1, 2
3
2, 1, 3
2, 1, 3
Delivery time
140
120
Equipment utilization
42.9%
50%
Delivery time loss
10
10
f
1
16.42
15


## 5.3. Example 2

In the assembly workshops of the sheet metal, the assembly line includes 5 machines and produces 3 different types of sheet metal parts. The job element of the sheet metal parts is shown in Table4.Table 4
The job element of the sheet metal parts.
Serial number
Job element
Standard time
1
The punching of the sheet metal
(10, 10, 15)
2
The cutting of the sheet metal
(15, 15, 20)
3
The tapping of the sheet metal
(20, 10, 10)
4
The testing of the sheet metal
(15, 10, 20)
5
The package of the sheet metal
(15, 20, 10)The precedence relations diagram is shown in Figure7.Figure 7
Precedence relation diagram with five machines and three workpieces.Assume the fact that the demands of three partsQ=1007060 and the minimum volume Pmin⁡=20. According to the batching strategy above, the batch number of three parts m′ is calculated as follows:(16)m′=QPmin⁡=543.Each processing time of the workpieces in the machines is shown in Table5.Table 5
Processing time of the workpieces in the machines.
Parts
Machine 1
Machine 2
Machine 3
Machine 4
Machine 5
I
1
J
1
(
10
)
J
2
(
15
)
J
3
(
20
)
J
4
(
15
)
J
5
(
15
)
I
2
J
1
(
20
)
J
3
(
15
)
J
2
(
10
)
J
4
(
10
)
J
5
(
20
)
I
3
J
2
(
15
)
J
1
(
20
)
J
3
(
10
)
J
4
(
20
)
J
5
(
10
)The parameters used in PSO and CE-PSO algorithm are as follows: populationPN=20, iteration number G=500, w=0.5, c=0.5, b1=1500, b2=0.5, T=5000, μ1=0.8, μ2=2, and ϕ1=0.1.The comparison of optimization results of assembly line scheduling based on PSO and CE-PSO is shown in Table6. The comparison of iteration time of two algorithms is shown in Figure 8.Table 6
The comparison of assembly line scheduling results in experiment two.
Machine
Based on the PSO algorithm
Based on the CE-PSO algorithm
1
[122132132311]
[121232133211]
2
[321212112331]
[321212112331]
3
[131212132231]
[132121212312]
4
[133212112231]
[132213121231]
5
[131211322231]
[131312122132]
Delivery time
6500
5900
Equipment utilization
55%
55.93%
Delivery time loss
1500
900
f
1
2238.46
1561.0Figure 8
The comparison of iteration time of two algorithms.From Table6, the optimization result based on CE-PSO algorithm is better than that based on PSO algorithm because it has higher equipment utilization and lower delivery time loss and the smaller fitness f1, which shows the effectiveness of CE-PSO algorithm. From Figure 8, the iteration results of PSO algorithm are similar to those of CE-PSO algorithm at the beginning 70 steps. With the increase of the iteration steps, CE-PSO algorithm achieves the better optimization result.


## 6. Conclusion

Assembling line scheduling has become an important means for the enterprises to save resources, reduce costs, increase productivity, and improve the overall operational efficiency. The assembling line scheduling algorithm based on CE-PSO is proposed in this paper. Equipment utilization and delivery time loss are adopted to construct a fitness function and a multiobjective optimization algorithm based on CE-PSO is described to solve the assembly line scheduling problem. The simulation results show that the assembling line scheduling algorithm based on CE-PSO can obtain better scheduling scheme by comparison with the standard PSO algorithm, which proves its feasibility and effectiveness.



---

*Source: 685824-2015-02-01.xml*