Open access

Small World Optimization for Multiple Objects Optimization of Mixed-Model Assembly Sequencing Problem

Written By

Huang Gang, Tian Zhipeng, Shao Xinyu and Li Jinhang

Published: 17 August 2011

DOI: 10.5772/intechopen.84021

From the Edited Volume

Assembly Line - Theory and Practice

Edited by Waldemar Grzechca

Chapter metrics overview

2,149 Chapter Downloads

View Full Metrics

1. Introduction

With the continuously accelerating of economic globalization and subdividing of product demand, the production mode in manufacturing industry is always evolving. As the diversity and rapid changes of customer needs increasing, as the competition among enterprises with unprecedented speed and intensity expanding in global range, with the shorten lifecycle of product technology and market, the large-scale production with the characteristics of single variety, high-volume, continuous, and lacking of flexibility cannot meet the demands of current and future market, and the flexible production of small batch and multi-variety products, which are certain scaled and customer-oriented, have been favored in industry.

The evolution of production mode has generated the mixed assembly line. Products of different types and yields have been produced on the same assembly line by changing the organization of production without changing the existing production conditions and capacity, to meet the personalized demands of different consumers in the shortest possible time and quick response to the changes of market demands, then improve the competitiveness of enterprises.

Sequencing problem is one of the key issues of effectiveness on the mixed model assembly line, which determines the processing order of different products on the assembly line. A reasonable sort of production has important significance to improve production efficiency, reducing waste of resources and increasing competitiveness of enterprise in a market economy.

Sequencing problem is a typical combinatorial optimization problem. Exact approach and Heuristic method (Solnon et al., 2008) have been generally used to solve such problems. Exact approach generally includes Constraint Program, Integer Program and branch and bound algorithm. And Heuristic Approach involves Greedy Approach, Local Search Approach, Genetic Algorithm, Ant Colony Optimization and Particle Swarm Optimization (Chao-Tang & Ching-Jong, 2008). The computational complexity of sequencing problems has often grown exponentially, and the exact solution is difficult to deal with the traditional larger-scale problem, so in recent years Heuristic Approach has been the best approach to solve the sequencing problem.

Johnson's paper (Johnson, 1954) in 1954 is the first research on sequencing problem. Classical sequencing problem has been studied widely in last 30 years. For the production line, this kind of problem is called Flow Shop Problem (FSP). Classic FSP generally has four basic assumptions:

  1. Resource type assumption: the same machine can only process a workpiece at any time and one workpiece only can be processed on one machine at any time;

  2. Determinacy assumption: all input parameters are known in advance and fully identified;

  3. Computability assumption: all parameters can be calculated without regarding how to determine the date of delivery;

  4. Single objective and regularity assumption: Assuming that the goal of sorting is one-dimensional non-decreasing function of job completion time.

The so-called classical sequencing problem is generally difficult to use directly in production practice due to the strict assumptions. In recent years, mixed-model assembly sequencing problem in automotive industry has become a hot spot according to the research literatures and practical applications. The following sections fully described this problem in the automobile industry, proposed a model of general assembly sequencing problem with balancing the assembly load, smoothing the production flow and reducing the operation changeover as goals, and established a multi-objective car sequencing problem. Then we designed the transformation strategy for the discrete problem by the research of small world effect on a continuous problem, and proposed the small world algorithm to solve the discrete sorting problem. Finally, we solved the Car Sequencing Problem considering three objectives by Small World Optimization, found Pareto optimal solution of multi-objective car sequencing problem with actual production data. The result shown a good performance of Small World Optimization algorithm in multi-objective mixed sequencing.


2. The multi-objective mixed-model sequencing problem in automobile assembly workshop

Car Sequencing Problem was first put forward by Parrllo et al. in 1986, but Renault Company was the first one who began to solve the simple car sequencing problem by using the simulation annealing software (Solnon et al., 2008). This problem was focused a lot since it’s coming out, and developed to a classical problem.

2.1. Status of the art of car sequencing problem

The researchers mainly considered two objectives in optimizing the mixed-model assembly sequencing: balancing the assembly load and smoothing the production flow. The objective of balancing the assembly load is to maximize the production capability, but without going beyond its utmost (Kenjiro & Hajime, 1979). The objective of smoothing the production flow was put forward by Toyota Company in JIT environment, and in this objective, the key to organize the mixed-model assembly for multi-product is to level the production line (Miltenburg, 1989). The core problem of heijunka is how to optimize the production order in the mixed-mode assembly line, in order to keep a balanced and steady production.

In recent years, many scholars have conducted research on the Car Sequencing Problem (CSP). To solve this problem in a precise way, Estellon (Bertrand & Karim, 2007) proposed two different local search methods to solve the real CSP. Prandtstetter Matthias (Matthias & Günter, 2008) proposed that using integer linear programming and mixed variational areas to solve the CSP. In terms of heuristic approach, Nils (Nils & Malte, 2006) and Sara (Sara et al., 2009) proposed a method based on ant colony algorithm, in which the theory of ants find the shortest path was simulated, to solve the CSP. Chul (Chul et al., 1998) used a new genetic algorithm to solve the multi-objective sequencing problem, and proposed a new gene fitness function and selecting rule. In his method, the three objectives considered are minimizing the excessive working time; keeping a uniform consumption speed of accessories and minimizing the adjusting cost. The result shows that this genetic algorithm is better than other genetic algorithm. Jianfeng (Jianfeng, 2006) proposed Pareto result by using genetic algorithm with multi-objective, which consist of the objective of smoothing the logistics and minimizing completion time. Allahverdi(Allahverdi & Al-Anzi, 2006) put forward a model which considered the set-up time and minimum completion time, and proposed an algorithm to solve this model. This algorithm can get the best result faster than PSO and Taboo Search when the size of work-piece is larger than 50.

2.2. Three different objects of sequencing problem in assembly workshop

People in industry area have always been committed to improving the production efficiency; the way they take is improving the equipment and optimizing the production sequence. The cost of optimizing production sequence is very low, so it will get a better effect when put more attention on this way. Usually, there are many different objectives of car sequencing problem, but we only take three of them into consideration: balancing the assembly load, smoothing the production flow and reducing the operation changeover.

The components in the assembly process could be sorted in three types: the current component, i.e. the electronic adapter in the television assembly. Televisions of different model take the same adapter. The second type is the key component, i.e. the kinescope in the television assembly. All the televisions need this component, but different models need different kind of kinescope components. The third type is selected component, i.e. the stereo module. This type is selected only by certain product. For current component, their assembly process will not be influenced by the production sequencing because all the products need the same component. In this paper, we mainly talk about the key component and the selected component in the mix-mode assembly sequencing.

The objective of balancing the assembly load is to reduce the bottleneck in the production line; the objective of smoothing the production flow is to reduce the inventory of work in process.

In order to describe the assembly sequencing problem conveniently, some expressions were defined as follows:

  • V | V |
  • D T | D T |
  • Z v v D T v | Z v | v V | Z v | = | D T |
  • D j j D T j = 1 , 2 , ... , | D T | D j V
  • s j , v v j

In addition, v V , s j , v = { 0 p r o d u c t v i s n o t p r o d u c e d i n p o s i t i o n j 1 p r o d u c t v i s p r o d u c e d i n p o s i t i o n j = 1 , 2 , ... , | D r | . It’s obvious that v V s j , v = 1 .

2.2.1. Sequencing aimed at balancing the assembly load

In the automobile’s final assembly line, the automobile in process was put on a transmitting belt which moving with a fixed speed, and several working stations were distributed on both sides of the transmitting belt based on the assembly sequence. Each working station has an assembly group which must finish the stated task during the period from the automobile moving into this working station to its leaving. If the working station cannot finish the assembly in this period, production on the flow line would be influenced.

The main reason lead to the assembly unfinished is the unbalance of assembly load. For example, when there are too many selected components should be assembled continuously, the task would be hard to finish since operator’s heavy working load. Therefore, in real production, the selecting frequency of each selected component should have an upper limit, which usually expressed as H x : N x , that means in the N x products, only H x products select the component x at most. For example, if there is a selected component A, and its selecting frequency H A : N A is 2:3, that is to say, in any three discretional products in the production sequence only 2 products need to assemble component A. If more than 2 products select this component, the operator will not have enough time to assemble the component for the third product. In that way, the production line would be stopped.

Take one product’s assembly for example, based on the requirement of the assembly load, the selecting frequency of each selected component was shown as Table 1, and the production plan was shown as Table 2. In table 2, the number in the first row stands the assembly order, and number in the second row stands the type of product. For example, 1 means type 1, 2 means type2, etc. In table 2, the number 1 in the data part means component type 1 need to be assembled, if nothing in the data part, that means no component need to be assembled.

Selected component H x : N x
O[1] 2:3
O[2] 2:4
O[3] 3:5
O[4] 2:6

Table 1.

The selecting frequency of each selected component

Production sequence 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Selected component H x : N x 1 6 3 4 5 1 2 6 1 3 4 5 6 1
O[1] 2:3 1 1 1 1 1 1 1 1
O[2] 2:4 1 1 1 1
O[3] 3:5 1 1 1
O[4] 2:6 1 1 1 1 1 1

Table 2.

Production sequence plan to be scheduled

In these two tables, there are 14 products be produced ( | D T | = 14 ); 6 different types ( | V | = 6 ) and 4 selected components( O[1],O[2],O[3],O[4]) included. It’s obvious that the production sequence in Table 2 disobey the restriction of selecting frequency in Table 1. Table 3 shows a production sequence meet the objective of balancing the assembly load:

Production sequence 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Selected component H x : N x 1 1 2 3 5 3 1 4 6 5 6 6 1 4
O[1] 2:3 1 1 1 1 1 1 1 1
O[2] 2:4 1 1 1 1
O[3] 3:5 1 1 1
O[4] 2:6 1 1 1 1 1 1

Table 3.

A production sequence meets the objective of balancing assembly load

The objective of balancing the assembly load is setting the selected component’s assembling frequency reasonably. This objective offers a new idea to solve the bottleneck problem resulted from the unsmooth load.

In order to describe the model of sequencing problem about balancing the assembly load vividly and conveniently, some symbols are defined as follows:

E The set consists of selected components.

a v , x The notation indicates if the component be selected or not. a v , x = { 1 i f p r o d u c t v n e e d s e l e c t e d c o m p o n e n t x 0 o t h e r , x E .

H x : N x In the N x continuous products, there are only H x products select the component x , x E .

According to the description above, the formula below can describe a Constraints Satisfaction Problem (Kenjiro & Hajime, 1979):

v V s j , v = 1 j = 1 , 2 , ... , | D T | E1
j = 1 | D T | s j , v = | Z v | v V E2
m = j j + N x v V a v , x s j , v | H x | j = 1 , 2 , ... , ( | D T | | N x | E3
s j , v = { 0 , 1 } j = 1 , 2 , ... , | D T | , v V E4

2.2.2. Sequencing aimed at smoothing the production flow

Sequencing aimed at smoothing the production flow was rooted from the automobile industry. In order to describe the model of sequencing problem about smoothing the production flow vividly and conveniently, some symbols are defined as follows:

k The k th producing step

The moment when the former k products are finished was called the k th producing step. k = 1 , 2 , ... , | D T |

r i The ideal output ratio of the i th product, i = 1 , 2 , ... , | V |

That is to say, the ratio of i th product’s output and the overall output. r i = d i | D T |

g i , k The i th product’s output till the k th step. Obviously, g i , k = j = 1 k s i , j , d i = g i , | D T |

The understanding of these notations could be referenced as Table 4:

The real production sequence
k = 1 k = 2 …… k = | D T |
Production’s type i = 1 s i , j = { 0 , 1 } j = 1 | D T | s 1 , j = g 1 , | D T | = d 1
i = 2 j = 1 | D T | s 2 , j = g 2 , | D T | = d 2
j = 1 | D T | s i , j = g i , | D T | = d i
i = | V | j = 1 | D T | s | V | , j = g | V | , | D T | = d | V |
i = 1 | V | s i , j 1 1 …… 1 i = 1 | V | j = 1 | D T | s i , j = | D T |

Table 4.

The model of sequencing problem on smoothing the production flow

According to the requirement of smoothing the production flow, the ideal numerical model of sequencing problem of smoothing the production flow is as follows:

m i n . f l = k = 1 | D T | i = 1 | V | | g i , k k r i | s . t . i = 1 | V | g i , k = k k = 1 , 2 , ... , | D T | , g i , k i s n o n n e g a t i v e i n t e g e r E5

Still taking Table as an example, it’s obvious that | D T | = 14 . Choosing step k | D T | , such as k = 10 , the objective of smoothing the production flow is for every k, the value of object function in formula(5 could be as small as possible. That is to say, it’s required that in any step, the products’ output in different types could be close to the overall products’ output.

2.2.3. Sequencing aimed at reducing the operation changeover

The objectives of these two models are the same according to their definition: balancing the production. The former one requires balancing the assembly line’s load, and the latter one requires balancing the output of products and smoothing the production flow.

With the diversification of customer’s requirement, more and more enterprises take the order-oriented production strategy, which lead the fact that more and more different types of products be produced in the same assembly line, and also lead more and more components have to be assembled in the same working station. However, according to Table 3, if the two objectives mentioned before have to be realized, it will bring a great discrepancy between two continuous products in the one working station. Since the production sequence determinate the component’s assembly order, the frequent change of product’s type always means the frequent switching of component assembled in the working station.

For one same working station on the assembly line, if a production sequence lead the component assembled in this working station switching less, obviously, the set-up time will decrease a lot, and the efficiency of the assembly will increase a lot. Therefore, in terms of ergonomics, it’s significant to schedule the production sequence and decrease the switching component’s type. This paper proposed a sequencing problem which aimed at decreasing the switching frequency of work-in-process’s type and increasing the similarity of product.

Symbols are introduced to describe the sequencing problem which based on the product’s similarity in the assembly line:

v n The n th assembly procedure of v th product

C ( v n , v n ' ) The similarity value of v n and v n ' , if v n and v n ' have the same type,

C ( v n , v n ' ) is 0, otherwise, C ( v n , v n ' ) is 1, i.e. C ( v n , v n ' ) = { 0 , i f v n = v n ' 1 , i f v n v n '

The model aimed at reducing the operation changeover could be expressed as follows:

m i n . f p = j = 1 | D T | 1 C ( v n , v n ' ) s . t . C ( v n , v n ' ) = { 0 , i f v n = v n ' 1 , i f v n v n ' , n = 1 , 2 , ... , | D T | 1 E6

Obviously, when all the products in the production sequence are the same type, f p has its minimum value: 0.

In addition, the key component influences the efficiency and quality in the assembly process greatly. Therefore, for simplicity, the paper only considered the key component in the assembling process when definite the product’s changeover.


3. Small world optimization for discrete sequencing problem

There are many proven algorithms to solve discrete sequencing problem and we commonly use the heuristic algorithms such as Ant Colony Algorithm and Genetic Algorithm. When solving the discrete sequencing problem, the Ant Colony Algorithm may be convergence to local optimum and the Genetic Algorithm has low solving efficiency as producing a lot of redundancy iteration by using insufficient feedback information. Therefore, we need an algorithm which has a strong capability of global searching and fast convergence speed. Small World Optimization just meets our requirements.

The research on small world firstly originates in 1929 by a Hungarian writer F.Karinthy. He put forward the theory “Any two people on earth can be contacted through a chain composed by five other persons” (Braun, 2004). In 1967, S.Milgram confirmed the small world phenomenon through the famous letters delivery experiments and proposed six degrees of separation theory (Travers & Milgram, 1969). With the study on small world effect by Watts and Strogatz (Watts & Strogatz, 1998; Strogatz, 2001), small world phenomenon was gradually valued and quickly became a hot spot of complex system and complexity theory research.

This paper designed a fast search algorithm called Small World Optimization (SWO) which was inspired by the hierarchical categorization tree model and multi categories method based on small world theory. The solution space can be divided into the hierarchical categorization tree model using hamming distance. Two bijective mapping solution spaces were adopted to establish multi categories method. Small World Optimization evaluated the relationship between nodes of the short and long distance neighbors in the two spatial networks and put the envelopes to the target, and then found the optimal solution.

3.1. Designing small world optimization

3.1.1. Basic idea of small world optimization

The basic ideas of Small World Optimization: simulating Milgram’s letters delivery experiments (J.Travers & S.Milgram, 1969), first deliver several envelopes from different places in the solution space and regard each envelope holder (node called in this paper) as a candidate solution; then find out each node’s best node which is estimated by objective function and deliver the envelope to this node; at last, each envelope will be closer to the object node through multiple delivery in the small world network.

The extensive research on small world effect also makes Small World Optimization achieve excellent results in solving actual problem. Huang (Huang et al., 2011) made a deep research on Small World Optimization and designed a fast search algorithm for continuous problem. With some test of standard continuous problems for Small World Optimization, Small World Optimization has fast convergence ability. Inspired by the Small World Optimization on continuous problem, we study the solving strategy of Small World Optimization in discrete problem.

3.1.2. Definition of short and long neighbors

For problems of continuous type, we can easily use network address division method to solve the hierarchical structure of the solution space. The relationships between the different addresses of the same subnet network are short neighbors. But the addresses of different subnet networks have long neighbor relationships.

However, sequencing problem is a kind of discrete problem for which we can’t apply Internet Protocol division rules in continuous problem because each solution is a sequence. Normally, hamming distance is used to express the distance between different sequences of discrete problem. So the two sequences between which the hamming distance is 2 are defined as short neighbor relationship. The number of short neighbors of a sequence node is C n 2 in a sequence of length n. Such as sequence 1 2 3 4 5 and sequence 1 3 2 4 5 have short neighbor relationship. If hamming distance of two sequences is greater than 2, they have long neighbor relationship.

Acquaintance probability of any two long nodes is expressed by index function e α d i j , α is acquaintance index and d i j is the hamming distance of two long nodes. From the function, we realize that the smaller the hamming distance, the greater the acquaintance probability, and vice versa.

3.1.3. Construction of multiple space conversion

The highlight of small world optimization algorithm is multiple space synchronization search, solving multiple space mapping is a key problem. According to the above discussion, Small World Optimization can find the best solution through searching in double spaces which combine two bijective mapping solution spaces with original solution spaces.

  1. Discrete space similar conversion rules of gray yards

For discrete problem, sequence is usually described as real integer. Such as, for a Flow shop problem with 5 workpieces, workpieces sequence A, B, C, D, E is corresponded with 1, 2, 3, 4, 5 respectively.

Adjusting the workpieces sequence will get a new solution; we define all the solution as the first heavy solution space. The second heavy solution space is from the first heavy space through some conversion rules. According to the conversion rules of binary gray yards for continuous space, we design a similar conversion rule for discrete space, the conversion code rules are as follows:

Conversion rules. For a sequence X = { 1 2 3 4 5 } , its length M = 5 , conversion procedure below:

  1. According to the conversion rules of gray yards, first consider shifting the sequence coding, circularly shift N byte rightward. If N = 2 , the sequence will be X 1 = { 4 5 1 2 3 } .

  2. In order to increase the differences between the original sequence and new sequence and enlarge its hamming distance length, we can reverse the original sequence, and the sequence will be X 2 = { 3 2 1 5 4 } .

  3. According to the two sequences which take exclusive by bitwise operation in gray yards conversion, we can do the same operation in discrete sequence. For sequence 3 2 1 5 4, if overall add m , then take more to the sequence length M . G i = ( X i + m 1 ) % M + 1 . If m = 1 , the sequence will be G = { 4 3 2 1 5 } .

Figure 1.

The procedure of conversion rules

  1. The conversion of gray yards for discrete space

In order to make discrete sequence fully meet the conversion of gray yards, first the real integer will be converted to binary coding. For a sequence 2 5 4 3 1, respectively convert the real integer sequence to binary coding of which length is 3. As Fig. 2 (a) describes.

Then we get a new binary coding sequence by conversion of gray yards to the binary coding sequence. At last, convert the binary coding to integer coding and get the final sequence as Fig. 2(b):

Figure 2.

The binary conversion of Real integer

Usually we can correct the sequence by Smallest Order Value rule, the sequence will be: 3 5 4 2 1.In fact, we don’t have to correct the final sequence, because we only get the second heavy space for finding short neighbor nodes. So, for the sequence 3 7 6 2 1, we can do nothing. The sequence 6 7 3 2 1 is a short neighbor node, which will be 4 5 2 3 1 after converting to the first heavy space.

3.1.4. Updating of the envelope node

According to above definition, for a sequence whose length is N , the number of its short neighbor node is C N 2 and the number of its long neighbor nodes is A N N C N 2 1 .

Each envelope holder will search part of its short neighbor nodes and long neighbor nodes in double space and find a better envelope by some rules to update it. General selection rules have two kinds: the first is only finding a better envelope to update; the second is searching specific number of long and short neighbor nodes in double space and finding the best envelope to update.

3.2. Summarizing the procedure of small world optimization

The process of Small World Optimization is as follows:

  1. Set iterative counter c = 0 ;

  2. Create initial envelope population Q ( t 0 ) : build the mapped relationship between solution space and coding style according to the constraint definition, randomly select envelopes as the initial nodes.

  3. Inquire the neighbor nodes: A certain number of short and long neighbor nodes n are inquired for each envelope node. The inquired neighbor nodes include the nodes coming from the original solution space and the mapping space.

  4. Evaluate the neighbor nodes of each node: calculate the evaluation function for each neighbor node, and sort them.

  5. Deliver envelope: select a envelope node which better than the current envelope node, then delete the current envelope node. The selection strategy have two kinds: one is calculating all the selected neighbor nodes and selecting the node with best evaluation value. The other one is calculating the evaluation value of each node from this space, and delivering the current envelope node since it’s easy to find high quality nodes in the mapping space. When appearing a better node, stop calculation.

  6. Determine whether meet the terminal conditions: if it meets, stop searching and print the result; else, keeping seaching.

  7. Update all envelope nodes: when all envelope nodes have compete their dilivering, the nodes compose a new envelope group, and can get Q ( t + 1 ) .

  8. c = c + 1

The parameters needed in Small World Optimization: the length of coding is n ; the number of short neighbor nodes is m c ; the acquaintance index of two long neighbor nodes is α ; the number of envelope nodes is m .

Here, n is equal with the length of sequence and the problem will be more complex when n largen. The number of short neighbor nodes decides the efficiency and quality of search. α is an important parameter to select long neighbor nodes and generally the range from 0.4 to 0.6. Usually the number of envelope nodes is range from 10 to 40.

Figure 3.

The flowchart of Small World Optimization algorithm


4. Numerical experiments with small world optimization on the multi-objective car sequencing problem

By the multi-objective mixed-model sequencing problem in automobile assembly workshop Established in section 2, we use the Small World Optimization, which is introduced in section 3, to solve a practical example of automotive industry production.

4.1. Simplifying the mixed-model sequencing problem of multi-objective

In section 2.2, we analyzed three types of car sequencing problem in the current assembly workshop. The three goals are shown as below:

  • f c
  • f l
  • f p

Here, we get a Pareto solution set by considering these three objectives simultaneously to optimize the car sequencing problem. According to section 2.2.1, balancing the assembly load can describe as a Constraints Satisfaction Problem, and just needs to be satisfied. In addition, for an actual auto enterprise, the imbalance of the assembly load may lead the line stopping running. Therefore, we’ll regard the goal f c as the primary goal and put the balance of the assembly load as the constraint conditions.

After conversion, the three-objective problem changed into a two-objective problem with a constraint satisfaction. Minimize the goal of balancing the assembly load and minimize the goal of reducing operation changeover have the same importance.

m i n . f l = k = 1 | D T | i = 1 | V | | g i , k k r i | m i n . f p = j = 1 | D T | 1 n = 1 Θ C ( v n , v n + 1 ) E7
s . t . m = j j + N x v V a v , x s j , v | H x | j = 1 , 2 , ... , ( | D T | | N x | ) E8
i = 1 | V | g i , k = k k = 1 , 2 , ... , | D T | , g i , k  is Nonnegative integer E9
C ( v n , v n + 1 ) = { 0 , i f v n = v n + 1 1 , i f v n v n + 1 , n = 1 , 2 , ... , | D T | 1 E10

In addition, formula (7)is the final two objects, formula (8)is the constraint that balancing the assembly load and the formula (10)expresses the switching times of parts use.

4.2. Preparing the actual production data for numerical experiments

A certain assembly workshop produces Multi-Purpose Vehicles. According to the different configurations can be divided into models, and each batch has 20 vehicles. The major plan as Table 5 below:

Product NO 1 2 3 4 5 6 7 8 9 10 11 12
Product model a b c d e f g h i j k l
number 1 2 1 2 1 1 3 3 1 1 2 2

Table 5.

The major plan of actual production data

Model 1 concern the balance of assembly load. Here, we consider five selected options (O [1], O [2], O [3], O [4], O [5]). In discussing smoothing the production flow, in order to simplify the solution, we only consider these product parts (K [1], K [2], K [3], K [4], K [5]) which switch frequently and are more critical. The selected options and critical parts of each product model list as Table 6 below:

Product O[1] O[2] O[3] O[4] O[5] K[1] K[2] K[3] K[4] K[5]
a 1 0 0 1 1 1 1 1 1 1
b 1 1 0 0 0 1 2 2 2 2
c 1 0 1 1 0 1 2 3 2 2
d 0 1 0 0 1 2 2 1 1 3
e 0 0 1 0 0 3 3 2 1 3
f 0 1 0 1 1 4 2 2 2 1
g 0 1 1 0 1 3 3 3 1 2
h 0 1 0 1 0 4 1 2 2 2
i 1 0 0 0 1 1 3 2 1 1
j 0 0 1 1 0 1 2 3 1 1
k 0 0 0 0 1 4 2 2 2 2
l 0 0 0 1 1 3 3 1 1 2

Table 6.

The selected options and critical parts of each product model

The selecting frequency of each selected component in Table 6 shows in Table 7 below:

The selected component in O[1] O[2] O[3] O[4] O[5]
H x : N x 3:4 4:7 3:5 2:3 2:3

Table 7.

The selecting frequency of each selected component

4.3. Solving the multi-objective CSP by small world optimization

The multi-objective model considers smoothing the production flow and reducing the operation changeover in this paper and we use Small World Optimization to solve it. According to the major plan, each production batch has 12 kinds of vehicles and 20 vehicles. In order to code the vehicles, use the integer to coding them, as Table 8 below:

Product type a b b c d d e f g g g h h h i j k k l l
Coding style 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Table 8.

The coding style of each product model

Initialize the envelope nodes. Randomly generate sequences whose coding length is 20, and then compute each target of the sequences. Select 100 envelope nodes, which meet the balance of assembly load, as initial nodes. The initial solution space is shown as Fig. 4 :

Figure 4.

The initialization of 100 envelope nodes

Consider the single object. According to the initial envelope nodes, when smoothing the production flow is the unique goal, 27 is the minimum value. The final envelope nodes after optimizing are shown as Fig. 5(a)and (124, 27) is the right margin of the Pareto solution set.

When only thinking about the goal of smoothing the production flow, the minimum value is 67. The final envelope nodes after optimizing are shown as Fig. 5 (b)and (67, 54) is the left margin of the Pareto solution set.

Figure 5.

Concerning the single goal

Consider two objectives simultaneously. Considering the goal of smoothing the production flow and the goal of reducing the operation changeover in the condition of that the balance of product load meets the requirements. In optimization process of Small World Optimization, for the target of each envelope nodes G o a l i = ( f l , i , f p , i ) , only when f l , i + 1 f l , i and f p , i + 1 f p , i , the envelope nodes begin updating, G o a l i + 1 = ( f l , i + 1 , f p , i + 1 ) .

The parameters in Small World Optimization are set as follows: the number of envelope nodes is 100; each envelope node select 20 short neighbor nodes; the acquaintance index of two long neighbor nodes α = 0.4 ; the iteration times is 400; and we optimize the problem in two space.

Finally, we get the Pareto solution set of multi-object Car Sequencing Problem by Small World Optimization. The all Pareto solutions are shown as Table 9. The upper and lower boundary in Table 9 is according with the result of single objective. To a certain extent, it also proves that Small World Optimization has a strong global searching capability.

Pareto solutions 1 2 3 4 5 6 7 8 9
the similarity of product goal 27 29 30 31 35 37 38 39 41
the equilibrium of logistics goal 124 118.1 102.7 85.9 80.6 77.7 77 74.2 71.6
Pareto solutions 10 11 12 13 14 15 16 17
the similarity of product goal 42 43 44 45 46 47 51 54
the equilibrium of logistics goal 71.4 68.7 68.4 68.2 67.8 67.7 67.2 67

Table 9.

The All Pareto solution

The optimization of Small World Optimization keeps the envelopes delivering and updating, thus the initial envelope node is always changing its position. The final envelope nodes distribute as Fig.6. The red line connects all the Pareto solutions, and the red dots indicate the Pareto solution. It can be seen that when two objectives have to be met, no other nodes are better than Pareto best solution.

The final envelope nodes distribute as Fig. 6. The final envelope nodes are close to the Pareto solution nodes which reflect that Small World Optimization algorithm has good convergence ability. And the global distribution of the envelope nodes reflects the superiority of multidimensionality space synchronous searching ability of Small World Optimization.


5. Discussion and conclusions

In this paper, we offer three main contributions to the multiple objects car sequencing problem, in the areas of modeling, solution engine, and to the quality of numerical results for real industrial problems.

On modeling: This paper mainly discusses the problem of production line in assembly workshop and establishes an all-sided model. Based on the actual production, we put forward a model which considers the goals of balancing the assembly load, smoothing the production flow and reducing the operation changeover. Thus, the problem which we discuss is a multi-object Car Sequencing Problem.

The solving model was improved and revised in order to simplify the calculation process. The goal of balancing the assembly load is the highest-level objective since the unbalance of production load will stop the production line. To simplify the solving process, it was regarded as a constraint that has to be satisfied in the multi-objective model.

Figure 6.

The final distribution of the envelope and the Pareto solution set

On the solution engine: We present a new and powerful solution engine for the multiple objects car sequencing problem. This paper designed a fast search algorithm called Small World Optimization (SWO) which was inspired by the small world effect in nature.

According to the characteristic of “Six Degrees of Separation” in small world, we can optimize the current solutions by distributed searching in the original solution space and the mapping space synchronously. Small World Optimization fully displays its good search performance and global searching capability by solving the multi-object Car Sequencing Problem in section 4.

The result of solving multi-object Car Sequencing Problem reflects the excellent overall searching performance of Small World Optimization algorithm. Small World Optimization realizes the multi-point searching based on the envelope transmission system. Each envelope records the node with best value in the search process and each envelope has its independence. This search mechanism in solving multi-objective question has better searching performance. It can record many Pareto best solutions synchronously and get a better Pareto solution set in solving multi-object sequencing problem.

On the numerical results: For an actual industrial problem of real dimensions, we present computational results that show that the Small World Optimization approach has the ability rapid convergence and global optimization characteristic. For the multi-object Car Sequencing problem which belongs to NP-Hard problem, Small World Optimization can get a good solution by solving with its superior calculation performance.

Our work also suggests extensions that would broaden the range of the models presented, but that were not included in this paper because they would not have allowed direct comparisons to available results from current practice.

Firstly, as the production batch and the constraints of assembly load are little, there are so many solutions when the constraint of balancing the assembly load is satisfied. So we can convert the three goals optimization problem to two goals optimization problem. However, when the scale of sequencing problem enlarges and the number of constraints increases, the balance of assembly load may not be satisfied. In this case, we have to regard it as a three-goal problem.

The objective of balancing the assembly load is to minimize the times of violating the balance principle; the model was described as below:

m i n . f c = 1 2 i = 1 | E | j = 1 | D T | + | N x | r e p i , j s . t . r e p i , j = { 0 , i f | H x | k = 0 | N x | 1 v V a v , x s j + k , v 0 1 , o t h e r , s j , v = { 0 , 1 } , j = 1 , 2 , ... , | D T | v V , x E E11

Secondly, we could also consider other requirements in the car assembly workshop, like the balancing of working time in different workstation. The equilibrium of working time of each working station can also optimize the production tact time.

Finally, for Small World Optimization algorithm, the research in this paper is not mature enough. However it also achieved an excellent effect on the dispersing problem by designing the relative algorithm, the searching method and the updating strategy. What’s more, the Small World Optimization algorithm has more strength on the multi-objective problem, since the global searching of multi-node will help to find the Pareto optimal solution. Small World Optimization will have a better development when more and more scholars doing research on it.



The research reported in this chapter is supported by the National Natural Science Foundation of China (NSFC) under Grant No. 50775089, 50825503, 50875101.


  1. 1. Allahverdi, Ali & Al-Anzi, F.S 2006 Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize make span with setup times. International Journal of Production Research, 44 22 December, 2006), 4713 4735 , 0020-7543
  2. 2. Bertrand, Estellon & Karim, Nouioua 2007 Two local search approaches for solving real-life car sequencing problems. European Journal of Operational Research, 191 3 December, 2008), 928 944 , 0377-2217
  3. 3. Braun T. (2004). Hungarian. priority in. network theory.. Science 304 304 5678 June, 2004), 1745 0036-8075
  4. 4. Chao-Tang, Tseng & Ching-Jong, Liao 2007 A discrete particle swarm optimization for lot-streaming flow shop scheduling problem. European Journal of Operational Research, 191 2 1(December, 2008), 360 373 , 0377-2217
  5. 5. Chul J. H. Yeongho K. Yeo K. K. 1998 A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines. Computers & Operations Research, 25 7-8 (July, 1998), 675 690 , 0305-0548
  6. 6. Huang Gang; Li Jinhang & Jia Yan 2011 Small World Optimization: A fast search algorithm based on small world effect. Computer Science, (July, 2011), 0100-2137 1002 137 X
  7. 7. Jianfeng Yu. Yue Hong. Yin Zhaoneng Chen. 2006 Scheduling of an assembly line with a multi-objective genetic algorithm. The International Journal of Advanced Manufacturing Technology, 28 5-6 (2006), 551 555 , 0268-3768
  8. 8. Johnson, S.M 1954 Optimal two-and three-stage production schedule with setup times included. Naval Research Logistics Quarterly, 1 1 1954), 61 68
  9. 9. Kenjiro, Okamura & Hajime, Yamashina 1979 Heuristic algorithm for the assembly line model-mix sequencing problem to minimize the risk of stopping the conveyor. International Journal of Production Research, 17 3 1979), 233 247 , 0020-7543
  10. 10. Matthias Prandtstetter. Günter R. Raidl 2008 An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. European Journal of Operational Research, 191 3 December, 2008), 1004 1022 , 0377-2217
  11. 11. Miltenburg, G.J 1989 Level schedules for mixed-model assembly lines in just-in-time production systems. Management Science, 35 1989), 192 207 , 0025-1909
  12. 12. Nils, Boysen & Malte, Fliedner 2006 Comments on “Solving real car sequencing problems with ant colony optimization”. European Journal of Operational Research, 182 1 October, 2007), 466 468 , 0377-2217
  13. 13. Sara Morin. Caroline Cagne. Marc Gravel. 2008 Ant colony optimization with a specialized pheromone trail for the car-sequencing problem. European Journal of Operational Research, 197 3 September, 2009), 1185 1191 , 0377-2217
  14. 14. Solnon, Christine; Cung, Van Dat & Nguyen, Alain 2007 The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem. European Journal of Operational Research, 191 3 December, 2008), 912 927 , 0377-2217
  15. 15. Strogatz S. H. 2001 Exploring complex networks. Nature, 410 March, 2001), 268 276 , 0036-8075
  16. 16. Travers J. Milgram S. 1969 An experimental study of the small-world problem. Journal of Information Storage and Processing systems, 32 1969), 1099-8047
  17. 17. Watts D. J. Strogatz S. H. . November 1997 Collective dynamics of ‘small-world’ networks. Nature, 393 June, 1998), 440 442 , 0036-8075

Written By

Huang Gang, Tian Zhipeng, Shao Xinyu and Li Jinhang

Published: 17 August 2011