• [email protected]
  • +971 507 888 742
Submit Manuscript
SciAlert
  • Home
  • Journals
  • Information
    • For Authors
    • For Referees
    • For Librarian
    • For Societies
  • Contact
  1. Information Technology Journal
  2. Vol 12 (4), 2013
  3. 728-734
  • Issues
    Online First Current Issue All Issues
  • Information About
    Aims and Scope Editorial Board Guide to Authors Article Processing Charges
    Submit a Manuscript

Information Technology Journal

Year: 2013 | Volume: 12 | Issue: 4 | Page No.: 728-734
DOI: 10.3923/itj.2013.728.734
crossmark

Facebook Twitter Reddit Linkedin E-mail
Research Article

A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem

Shuai Ma
School of Mechanical Engineering, Dalian University of Technology, Dalian 116024, People`s Republic of China

Zhuang-Cheng Liu
School of Mechanical Engineering, Dalian University of Technology, Dalian 116024, People`s Republic of China

Yan-Jun Shi
School of Mechanical Engineering, Dalian University of Technology, Dalian 116024, People`s Republic of China

ABSTRACT


The facility layout problem is one of the most complex problems in many industries and the Loop-based Station Sequencing Problem (LSSP) is a classical sub-problem. In this study, a dual-system method based on Differential Evolution (DE) and Genetic Algorithm (GA) (DDEGA) was presented to solve the LSSP. The DDEGA duplicates the system P, which represents the original problem, as systems A and B. The systems A and B are solved by DE and GA, respectively. Since the elite migration between two systems can contribute to increasing the diversity and decreasing the premature convergence, the DDEGA can obtain better solutions and robustness. Numerical studies on four different scales showed that the proposed method can obtain a challenging solution.
PDF Abstract XML References Citation

Keywords


  • differential evolution
  • Dual-system
  • genetic algorithm
  • loop-based station sequencing problem

Article History

Received: October 12, 2012;   Accepted: December 22, 2012;   Published: January 22, 2013

How to cite this article

Shuai Ma, Zhuang-Cheng Liu and Yan-Jun Shi, 2013. A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem. Information Technology Journal, 12: 728-734.

DOI: 10.3923/itj.2013.728.734

URL: https://scialert.net/abstract/?doi=itj.2013.728.734

INTRODUCTION


Flexible Manufacturing Systems (FMS) play a crucial role in modern advanced manufacturing. Facility layout problem in FMS is a manufacturing setting designed to satisfy the contemporary market demands, such as productivity, flexibility and on-time delivery (Drira et al., 2007). About 20-50% of the total production cost is allocated to facility layout and materials handling and an appropriate placement of facilities may reduce at least 10-30% of the total operating expenses (Tompkins, 2010). Therefore, facility layout in early design period needs to be schemed with much greater effort.

The facility layout in a FMS is typically determined by the type of the material handling devices used, such as Automated Guided Vehicles (AGVs), conveyors and gantry robots. The most commonly used types of facility layouts are the following, (1) Linear single row layout, (2) Linear double row layout, (3) Cluster layout based on gantry robot, (4) Semi-circular layout and (5) Closed loop layout (Kusiak and Heragu, 1987). Compared with other layout types, the loop layout has been generally studied due to relatively low initial costs and high flexibility (Afentakis, 1989). The original Loop Layout Design Problem (LLDP) is shown in Fig. 1.

This study addresses the unidirectional Loop-based Station Sequencing Problem (LSSP) (Afentakis, 1989), i.e., how to determine an order of facilities to minimize the material-handling costs measured by the total number of times the material cross the loading/unloading station, regardless of the size, shape and orientation.

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
Fig. 1: Loop layout in flexible manufacturing systems

Since LSSP had been proven non-deterministic polynomial-time hard (NP-hard) (Leung, 1992), heuristic algorithms are naturally the most promising methods.

Since, Afentakis (1989) proposed a graph theoretic model for designing a loop network to minimize the average number of machines that all workpieces cross per unit time, many researchers have developed heuristics techniques for LLDP. Leung (1992) solved the MIN-SUM LLDP by using a heuristic which constructed a layout from a solution to the linear-programming relaxation based on a graph-theoretic framework. Kaku and Rachamadugu (1992) addressed the problem of minimizing the material handling costs for linear-track conveyor systems as a Quadratic Assignment Problem (QAP) using a heuristic method. Cheng and Gen (1998) introduced Genetic Algorithm (GA) for both MIN-SUM and MIN-MAX LSSP. Tansel and Bilen (1998) discussed a heuristic algorithm based on moves and 2-way interchanges applied on permutations of facilities. Plaquin and Pierreval (2000) applied an Evolutionary Algorithm (EA) to solve cellular design problems taking into account specific constraints, such as the bounded size of cells, facilities that should stay together or be separated. Adel El-Baz (2004) described a GA for LLDP considering various material flow patterns with multi-products. Nearchou (2006) used subrange coded DE to solve LSSP. Pour and Nosraty (2006) coped LLDP as a QAP with an ant-colony algorithm. Kumar et al. (2008, 2009) solved LSSP using Particle Swarm Optimization (PSO) and Artificial Immune Systems (AIS) and the latter introduced crossover turntables into flow path of the loop layout to enhance the performance of the system. More information about the research status should be referred to the following surveys: classification of the facility layout problems (Drira et al., 2007). State-of-the-art reviews of techniques applied to Facility Layout Design Problem (FLDP) (Singh and Sharma, 2006; Arikaran et al., 2010).

In this study, a dual-system framework integrating Differential Evolution (DE) and GA is proposed to solve LSSP. The numerical experiment shows that the hybrid approach performed well on a problem set consisting of four characteristic test instances ranging from small to large size of LSSPs.

MAPPING APPROACH REVIEW

A candidate solution to LSSP is naturally described as a permutation vector concerning the arrangement of the facilities. In the literature, four mapping approaches prevail in practice.

Random-keys encoding (Bean, 1994) is widely applied to floating point chromosome with permutation property. The components of the chromosome are sorted and the order determines the sequencing of the facilities. For a five sequencing problem, the chromosome (.46, .91, .33, .75, .51) would represent the sequence 2→5→1→4→3, which means that the first facility will be installed at the second position.

Relative position encoding (Zheng and Teng, 2010) is proposed specifically to deal with LSSP or QAP, which is inspired by the procedure of insertion sort algorithm in computer science. The basic idea is explained as follows: the sequence facilities to be sorted are divided into sorted group (f0, f1,..., fi-1) and unsorted group (fi, fi+1,..., fn). Since a0 is initialized at the first position, it does not participate in sorting. For the next facility to be sorted, fi, there are (i+1) vacancies in the sorted group as the relative positions, which are respectively coded as (0, 1,..., I). According to the coding strategy, the chromosome (p1, p2,..., pn) determines the relative position of the facility sequencing (f1, f2,..., fn) correspondingly and piε{0, 1,..., i}. In Fig. 2, for instance, the fifth facility f4 could be placed in five relative positions and these five vacancies are coded as 0, 1, 2, 3 and 4, respectively.

Beside the former two strategies, sequence encoding and subrange encoding are also popular in combinatorial problems with permutation property. Applications of these two coding strategies in LLDP should be referred to Adel El-Baz (2004) and Nearchou (2006), respectively. The pseudo-code of the decoding procedure in MATLAB style is showed in Algorithm 1.

Algorithm 1:
Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem

A DUAL-SYSTEM METHOD USING DE AND GA

The term “dual-system” in algorithm field is firstly mentioned by Teng et al. (2010). The idea of dual-system is inspired by previous researches in numerous fields such as computer security, router in communication and even in biology and it is similar to the multi-island algorithm (Whitley et al., 1998), which often has several populations to preserve genetic diversity and each population can potentially follow a different search trajectory through the search space. Dual-system and multi-island algorithm share the same intrinsic characteristics of parallelism and distributedness since different systems/islands interact with each other in order to achieve a common goal.

Assume that only two populations with individuals’ migration between them in the multi-island algorithm, it turns out to be a dual-system which has system A and system B. In this study, system A executes the DE and system B uses a GA to follow a different search trajectory. The dual-system framework is shown in Fig. 3.

With elite migrations between system A and system B, genetic diversity is hoped to achieve. The interval generation of migrating the elite individuals from A to B is defined as Kab, whereas Kba is the migration interval generation from B to A.

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
Fig. 2: An example of relative position encoding

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
Fig. 3: The dual-system framework

When the elite migration happens, the relatively poor individuals in the objective system are replaced. The migration ratio from A to B and from B to A are denoted as Pab and Pba, respectively. In the experiments, we set Kab = 150, Kba = 200, Pab = 30%, Pba = 10%.

FORMULATION OF THE LSSP

The LSSP concerns a set of machines {1, 2,..., N} arranged in a loop network and materials flow in single direction. The parts enter and leave the system only at the loading/unloading station and each part is characterized by its part-route, the sequence of machines it should visit to complete its processing. For a given part, suppose processing on machines j immediately follows processing on machine i and if the position of machine j is lower than that of machine i, the part must cross the loading/unloading station, which is called a reload. The total number of reloads necessary to complete the processing for all parts constitutes a measure of traffic congestion in the production system (Afentakis, 1989).

A solution to the LSSP corresponds to a permutation of machines by some measures. Usually two measures used for the evaluation of a loop layout design: (a) MIN-SUM, in which the objective is to minimize the total congestion of all the parts, while (b) MIN-MAX is to minimize the maximum reload time among parts of the same system. (a) is preferred here.

The average cost of the generated best loop layouts given by the function:

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem

for the MIN-SUM LSSP, where S is a loop layout solution, i.e., a sequence of facilities and reloadi (I = 1…M) is the summation of the reloads for the ith part in the S layout.

The average percentage Solution Effort (SE) spent by an algorithm to achieve a near optimal solution:

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem

where, neopt is the number of evaluations performed by the algorithm to achieve the best solution and neTotal the total number of evaluations performed by the algorithm.

EXPERIMENT

In order to evaluate the performance of the proposed dual-system framework, an experimental study consisting of four characteristic test instances ranging from small to large size of LSSPs given in Nearchou (2006) is illustrated. Types and routes are set beforehand. The facility number and the part number are (10, 3), (20, 5), (15, 9) and (30, 10) and the corresponding routes are shown in Table 1.

Two heuristics algorithms, DE and GA, are compared with the dual-system whose subsystems are DE and GA (DDEGA) under the same conditions, with two different mapping mechanisms. Specifically, six versions are examined: (1) Random-keys GA (GA_1), (2) Random-keys DE (DE_1), (3) Relative position-coded GA (GA_2), (4) Relative position-coded DE (DE_2), (5) Random-keys DDEGA (DDEGA _1) and (6) Relative position-coded DDEGA (DDEGA _2). The performance of the algorithms is quantified by five performance criteria: (1) The optimal value of the objective function cost(S), (2) The average value of the objective function cost(S), (3) The standard deviation of the objective function Cost(S), (4) The average percentage solution effort (SE) and (5) The processing time of the algorithm measured in second.

SETTING THE CONTROL PARAMETERS

Setting for the control parameters is hard to be perfect since the countless possible choices. In order to determine suitable settings for GA and DE to solve the LSSP, the forth test problem, the 30-machines-10-parts MIN-SUM LSSP, is employed as the test problem for parameters with the population size Np = 2-D = 60. The performance of GA is only depended on the crossover probability (Cr) since Gaussian mutation adopted; the performance of DE is depended on the values of two control parameters: the crossover probability (Pc) and the mutation scale factor (F). In order to determine the suitable settings, various crossover probability Pcε{0.01, 0.05, 0.10,..., 0.95} is tested in GA; Fε{0.4, 0.5,... , 1.0} and Crε{0.01, 0.1, 0.2,..., 1.0} are experimented in DE, since the effective range of F is usually between 0.4 and 1.0 (Das and Suganthan, 2011).

Table 1: The required machine sequence for each part
Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
LSSP: The Loop-based station sequencing problem

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
Fig. 4(a-c): (a) The effect of various Pc on the performance of GA_1 and GA_2, (b) The effect of F and Cr on the performance of DE_1 and (c) The effect of various F and Cr on the performance of DE_2

The algorithms are tested 10 times on each scheme with running for a maximum of 1000 generations. The convergence charts are shown in Fig. 4.

The optimal control parameter values are obtained through the experiments above: Pc = 0.45 for random-keys GA (GA_1), Pc = 0.60 for relative position-coded GA (GA_2), (F, Cr) = (0.5, 0.9) for random-keys DE (DE_1) and (F, Cr) = (0.4, 0.3) for relative position-coded DE (DE_2).

In the dual-system framework, system A is employed as the main system, which conducts the better one between GA and DE with the same encoding mechanism. The dual-system (A and B) are evolved cooperatively, which means elite individual migration is implemented at intervals of some generations.

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
Fig. 5: Convergence curves of different algorithms with random-keys encoding mechanism

In this study, the number of elite individual from system A to system B is 15, the number reversely is 5 and the internal number of generation is 3 and 4, respectively.

COMPARISON RESULTS

A maximum of 3000 generations is set to algorithms with their respective optimal parameter settings and all data are obtained by 50 independent runs. The results obtained by GA, DE and DDEGA with different encoding mechanisms are shown in Table 2, which including the optimal and average reload time with standard deviation, the processing time, the average percentage Solution Effort (SE) and the best order of machines for each family of parts. DDEGA achieves brilliant solutions in some critical indicators such as optimal, average and standard deviation (STD), albeit GA wins on the CPU-time. The convergence curves with different encoding mechanism are showed in Fig. 5 and 6, which show that DDEGA assimilates the merits of DE and GA and gets a better solution.

Figure 4 shows that (1) in GA, the relative position-coded mechanism could get similar results with a relatively wider range of crossover probability (Pc) and the quality of solution deteriorated rapidly when (i) Pc for the random-keys GA level off to 1, (ii) Pc for the relative position-coded GA approaches to 0, (2) in the random-keys DE, the mutation scale factor (F) played a more critical role than the crossover probability (Cr), whereas F and Cr functioned together in the relative position-coded DE.

Table 2: Comparative results for benchmark problems
Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
LSSP: The Loop-based station sequencing problem

Image for - A Dual-system Method with Differential Evolution and Genetic Algorithm for Loop-based Station Sequencing Problem
Fig. 6: Convergence curves of different algorithms with relative position encoding mechanism

It can be easily seen from Table 2 that, though all six algorithms obtained the same objective values for small-scale problem sets, the dual-system framework achieved the highest performance outperforming both DE and GA alone for the largest-scale LSSP, that is because it combined two algorithms and employed the better one as the main system and strengthened the diversity by elite migration. It is worth mentioning that, DDEGA_1 achieved the optimal reload time 49, which was better than any other solutions in other literatures, more specifically, 53 acquired by the sub-ranges keys DE (Nearchou, 2006) and PSO (Kumar et al., 2008); 51 acquired by the relative position-coded DE (Zheng and Teng, 2010) and 50 acquired by the AIS (Kumar et al., 2009).

However, it can be easily noticed that the worst object value (54) found in the relative position-coded DE, which might implicate that the relative position encoding mechanism was not suitable for DE or needed modifying. Generally, algorithms with relative position encoding result to be weak as DE and GA are original.

Since all of the algorithms run for 3000 generations, the processing time in Table 2 represents the speed of algorithm. Obviously GA is the fastest and the dual-system is faster than DE.

CONCLUSION


This study focused on the Loop-based Station Sequencing Problem (LSSP) for flexible manufacturing systems. A dual-system framework which employs DE and GA was proposed. With two different encoding mechanisms, six kinds of algorithms were examined through experimental comparisons over different scales of test problems and the best layout for the largest scale LSSP was achieved by DDEGA with random keys encoding mechanism, which illustrated that the dual-system framework is superior to DE or GA alone.

Further studies could be conducted as follows: (1) The proposed dual-system framework should work better with adjusted opportune moment and the number of elite migration, (2) Since the inherent parallelism, the proposed framework can be easily implemented in parallel in order to be faster, (3) With improved DE and GA the relative position encoding mechanism may achieve better solutions since the dimension of the chromosome is one less than random keys encoding mechanism, (4) The proposed framework should be applied to many other problems even with constraints or multi-objectives.

ACKNOWLEDGMENTS


This study was supported by National Natural Science Foundation (Grant No. 50975039) and National Ministries Project (Grant No. A0920110001) of People’s Republic of China.

REFERENCES


  1. Drira, A., H. Pierreval and S. Hajri-Gabouj, 2007. Facility layout problems: A survey. Ann. Rev. Control, 31: 255-267.
    CrossRef

  2. Tompkins, J.A., 2010. Facilities Planning. John Wiley and Sons, New York, ISBN: 0470444045, Pages: 854.

  3. Kusiak, A. and S.S. Heragu, 1987. The facility layout problem. Eur. J. Operat. Res., 29: 229-251.
    Direct Link

  4. Afentakis, P., 1989. A loop layout design problem for flexible manufacturing systems. Int. J. Flexible Manuf. Syst., 1: 175-196.
    CrossRef

  5. Leung, J., 1992. A graph-theoretic heuristic for designing loop-layout manufacturing systems. Eur. J. Operational Res., 57: 243-252.
    Direct Link

  6. Kaku, B.K. and R. Rachamadugu, 1992. Layout design for flexible manufacturing systems. Eur. J. Operational Res., 57: 224-230.
    Direct Link

  7. Cheng, R. and M. Gen, 1998. Loop layout design problem in flexible manufacturing systems using genetic algorithms. Comput. Ind. Eng., 34: 53-61.
    CrossRef

  8. Tansel, B.C. and C. Bilen, 1998. Move based heuristics for the unidirectional loop network layout problem. Eur. J. Operational Res., 108: 36-48.
    Direct Link

  9. Plaquin, M.F. and H. Pierreval, 2000. Cell formation using evolutionary algorithms with certain constraints. Int. J. Production Econ., 64: 267-278.
    CrossRef

  10. Adel El-Baz, M., 2004. A genetic algorithm for facility layout problems of different manufacturing environments. Comput. Ind. Eng., 47: 233-246.
    CrossRef

  11. Nearchou, A.C., 2006. Meta-heuristics from nature for the loop layout design problem. Int. J. Prod. Econ., 101: 312-328.
    CrossRef

  12. Pour, H.D. and M. Nosraty, 2006. Solving the facility and layout and location problem by ant-colony optimization-meta heuristic. Int. J. Prod. Res., 44: 5187-5196.
    CrossRefDirect Link

  13. Kumar, R.M.S., P. Asokan and S. Kumanan, 2008. Design of loop layout in flexible manufacturing system using non-traditional optimization technique. Int. J. Adv. Manuf. Technol., 38: 594-599.
    CrossRef

  14. Kumar, R.M.S., P. Asokan and S. Kumanan, 2009. Artificial immune system-based algorithm for the unidirectional loop layout problem in a flexible manufacturing system. Int. J. Adv. Manuf. Technol., 40: 553-565.
    CrossRef

  15. Singh, S.P. and R.R.K. Sharma, 2006. A review of different approaches to the facility layout problems. Int. J. Adv. Manuf. Technol., 30: 425-433.
    CrossRef

  16. Arikaran, P., V. Jayabalan and R. Senthilkumar, 2010. Analysis of unequal areas facility layout problems. Int. J. Eng., 4: 44-51.
    Direct Link

  17. Bean, J.C., 1994. Genetics and random keys for sequencing and optimization. ORSA J. Comput., 6: 154-160.
    Direct Link

  18. Zheng, X.J. and H.F. Teng, 2010. A relative position-coded differential evolution for loop-based station sequencing problem. Int. J. Prod. Res., 49: 1235-1236.
    Direct Link

  19. Teng, H.F, Y. Chen, W. Zeng, S. Yan-jun and H. Qing-Hua, 2010. A dual-system variable-grain cooperative coevolutionary algorithm: Satellite-module layout design. IEEE Trans. Evol. Comput., 14: 438-455.
    CrossRef

  20. Whitley, D., S. Rana and R.B. Heckendorn, 1998. The island model genetic algorithm: On separability, population size and convergence. J. Comput. Inf. Technol., 7: 33-47.
    Direct Link

  21. Das, S. and P.N. Suganthan, 2011. Differential evolution: A survey of the State-of-the-art. IEEE Trans. Evol. Comput., 15: 4-31.
    CrossRef

Leave a Comment


Your email address will not be published. Required fields are marked *

Useful Links

  • Journals
  • For Authors
  • For Referees
  • For Librarian
  • For Socities

Contact Us

Office Number 1128,
Tamani Arts Building,
Business Bay,
Deira, Dubai, UAE

Phone: +971 507 888 742
Email: [email protected]

About Science Alert

Science Alert is a technology platform and service provider for scholarly publishers, helping them to publish and distribute their content online. We provide a range of services, including hosting, design, and digital marketing, as well as analytics and other tools to help publishers understand their audience and optimize their content. Science Alert works with a wide variety of publishers, including academic societies, universities, and commercial publishers.

Follow Us
© Copyright Science Alert. All Rights Reserved