# A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan

Authors: Zhigang Lian
Journal: Discrete Dynamics in Nature and Society
 (2010)

---

## Abstract

The Job-shop scheduling problem (JSSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. Many different approaches have been applied to optimize JSSP, but for some JSSP even with moderate size cannot be solved to guarantee optimality. The original particle swarm optimization algorithm (OPSOA), generally, is used to solve continuous problems, and rarely to optimize discrete problems such as JSSP. In OPSOA, through research I find that it has a tendency to get stuck in a near optimal solution especially for middle and large size problems. The local and global search combine particle swarm optimization algorithm (LGSCPSOA) is used to solve JSSP, where particle-updating mechanism benefits from the searching experience of one particle itself, the best of all particles in the swarm, and the best of particles in neighborhood population. The new coding method is used in LGSCPSOA to optimize JSSP, and it gets all sequences are feasible solutions. Three representative instances are made computational experiment, and simulation shows that the LGSCPSOA is efficacious for JSSP to minimize makespan.


---

## Body

## 1. Introduction

The job-shop scheduling problem (JSSP) is very important in field of production management. The JSSP has been proved to be a difficult task for human planners and schedulers, particularly if optimal solutions are required. With traditional optimization approaches, finding optimal solution to large size combinatorial problems is not a practicable option, because of the vast amount of computer time needed to find such solutions. Predecessors have proposed many different approaches to optimize JSSP and have obtained some harvest, but by current algorithms, even moderately sized problems cannot be solved to guarantee optimality. One of the first attempts to optimize a simple JSSP through application of genetic algorithm can be seen in the research of Davis in 1985. Since then, a significant number of successful applications of GAs to JSSP have appeared in [1–4], and so forth. Gharbi and Haouari have used an approximate decomposition algorithm for scheduling on parallel machines [5]. Xia and Wu presented an effective hybrid optimization approach for multiobjective feasible JSSP in [6]. Many researches show that GAs that are used to solve JSSP are feasible, however, their performance is far from satisfactory. Particle swarm optimization (PSO) is an evolutionary computation technique developed by Eberhart and Kennedy in 1995 [7, 8], inspired by social behavior of bird flocking or fish schooling. Similar to genetic algorithms (GA), PSO is a population-based optimization tool. In recent years, there have been a lot of works focused on the PSO that have been applied widely in the function optimization, artificial neural network training, pattern recognition, fuzzy control, and some other fields where GA can be applied, but PSOA used to solve discrete optimization problem such as JSSP does not have a rich literature. Clerc and Kennedy in [9] have researched the particle swarm stability and convergence in a multidimensional complex space. Goh et al. researched on competitive and cooperative coevolutionary approach to multiobjective particle swarm optimization algorithm design [10]. Eberhart and Shi have researched inertia weights and constriction factors, developments, applications, and resources of particle swarm optimization in [11, 12], at the same time they have presented a modified particle swarm optimizer in [13]. Shi et al. presented an improved GA and a novel PSO-GA-based hybrid algorithm in [14]. Fan has presented a modification to PSOA in [15] and He et al. have put forward a particle swarm optimizer with passive congregation in [16]. Kennedy and Mendes in [17] investigated the impacts of population structures to the search performance of SPSO. Robinson et al. in [18] have investigated particle swarm, genetic algorithm, and their hybrids. Chen and Li [19, 20], Shi and Eberhart [21], and Trelea [22] have researched parameter selection of particle swarm optimization, respectively. Yin and Zhang presented a new heuristic algorithm for solving the JSSP [23]. Lian et al. in [24] presented a similar particle swarm optimization algorithm, and through simulation experiment showed that it was effective to solve optimization problems especially with large size.In this paper, a local and global search combine particle swarm optimization algorithm (LGSCPSOA) is used for JSSP to minimize the makespan. In LGSCPSOA the new coding scheme is used, which gets every particle is feasible scheduling. This work differs from the existing ones at least in three aspects. It firstly proposes LGSCPSOA for JSSP; the second is to investigate the effectiveness of various parameters for different size JSSP; the third, computational experiments are performed to show that the LGSCPSOA is valid for JSSP. The rest of the paper is organized as follows. Section2 gives a definition of the JSSP and formulates its model that is minimum makespan. The LGSCPSOA implementation for JSSP is presented in Section 3. Section 4 discusses experimental results obtained by LGSCPSOA with different parameters on public benchmark JSSP. Finally, Section 5 summarizes the contribution of this paper and conclusions.


## 2. JSSP Description

In the static JSSP, a finite number of jobs are to be processed by a finite number of machines. Each job consists of a predetermined sequence of task operations, each of which needs to be processed without preemption for a given period of time on a given machine. Tasks of the same job cannot be processed concurrently and each job must visit each machine exactly once. Each operation cannot be commenced until the processing is completed, if the precedent operation is still being processed. A schedule is an assignment of operations to time slots on a machine. The makespan of JSSP is maximum completion time of all jobs, and the objective is to find a schedule that minimizes the makespan. A good schedule is one that minimizes the total amount of time machines are idle.The JSSP Description
Letn jobs (j=1,2,…,n) be processed on m machines M1,M2,…,Mm. Job j consists of operations sequence O1j,O2j,…,Oij,…, which must be processed with precedence constraints of the form Oij→Oi+1,j(i=1,2,…,mj-1). Each operation Oij being processed needs Tij(i=1,2,…,m,j=1,2,…,n) time units on one machine of M1,M2,…,Mm. All jobs are available at time zero and the operation of each job on a machine requires an uninterrupted period of time. This problem is called the job-shop scheduling problem (JSSP). Its model is set up as follows.
Let:J={1,2,…,n} for the job set;
pkj=find(Oij==k∣i=1,2,…,m) denote machine number of working procedure order k of job j process;
C(i,j) for the completion time of job j on machine i as follows:
(2.1)C(1,1)=C(p(O11-1)1,1)+T(1,1),C(1,j)=max{C(1,j′),C(P(O1j-1),j)}+T(1,j),C(i,1)=C(p(Oi1-1)1,1)+T(i,1),C(i,j)=max{C(i,j′),C(p(Oij-1)j,j)}+T(i,j).Remark 2.1.
Forj=1,…,n; i=1,…,m, j′ is anterior processing job of job j on machine i.
The relation calculation makespan is as follows:(2.2)Cmax=max1≤i≤mmax1≤j≤nC(i,j).The scheduling problem is to find out the best operation sequences on all machines in order to minimize makespan. In this case, the makespan implies the criterion to be optimized.In follow section, propose LGSCPSOA and use it to find a near optimal schedule whose makespan is the minimum over the set of all possible feasible schedules.


## 3. LGSCPSO Algorithm

### 3.1. Original Particle Swarm Optimization

Particle swarm optimization (PSO) is an evolutionary computation technique mimicking the behavior of flying birds and their means of information exchange. The system of PSO is initialized with a population (named swarm in PSO) of random solutions and searches for optima by updating generations. Each individual or potential solution, named particle, flies with a velocity which is adjusted according to the flying experiences of its own and its colleagues. PSOA has been developing rapidly and has been applied widely since it was introduced, as it is easily understood and realized. In PSOA, the potential solutions are “flown” through the problem space by following the current optimum particles, and the detailed information will be given in following.Suppose that the searching space isN-dimensional and m particles form the colony. The ith particle represents an N-dimensional vector Xi(i=1,2,…,m), and it means that the ith particle locates at Xi=(xi1,xi2,…,xiD) in the searching space. The particle’s fitness could be calculated through putting its position into a designated objective function. The ith particle’s “flying” velocity is also an N-dimensional vector as Vi=(vi1,vi2,…,viD). Denote the best position of the ith particle as Pi=(pi1,pi2,…,piD), and the best position of all colonies as Pg=(pg1,pg2,…,pgD), respectively. The original particle swarm optimization algorithm (OPSOA) could be performed by the following equations [7, 8]:(3.1)vid(k+1)=vid(k)+c1r1(pid(k)-xid(k))+c2r2(pgd(k)-xid(k)),xid(k+1)=xid(k)+vid(k+1),
where k represents the iterative number, c1,c2 are learning factors, usually c1=c2=2.r1, r2 are random numbers between (0, 1). The termination criterion for the iterations is determined according to whether the max generation or a designated value of the fitness of Pg is reached.


### 3.2. LGSCPSOA for JSSP

#### 3.2.1. Coding Scheme in LGSCPSOA for JSSP

OPSOA has been introduced as an optimization technique in real-number space, but many optimization problems in discrete space such as JSSP. OPSOA has a disadvantage tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. This section presents LGSCPSOA to optimize JSSP in discrete space, and develop an effective “problem mapping” and “solution generation” mechanism.In many algorithms for JSSP using the machine coding,  and it gets some sequences are not feasible solutions. In LGSCPSOA the working procedure coding is used,  and it gives birth to all children (sequences) are feasible solutions.SupposeX=[x1,x2,…,xn](xi∈R,i=1,2,…n) be one random particle, following steps make particles able to denote JSSP scheduling and will be used in LGSCPSOA to solve JSSP. (1)
Sorting the weightX=[x1,x2,…,xn] from small to large gets X′=[x1′,x2′,…,xn′], and using yi denotes the position of xi′ in X=[x1,x2,…,xn]. Obtain the new sequence Y=[y1,y2,…,yn]. For example, 3×2 JSSP, X=[0.8637,0.1872,0.8725,0.6442,0.2132,0.6429], sorting X gets X′=[0.1872,0.2132,0.6429,0.6442,0.8637,0.8725], then get the new sequence Y=[2,5,6,4,1,3];(2)
Every weight of sequenceY is divided by machine number M, and then rounded towards plus infinity to get a final one feasible solution sequence. For the above above example Y/2=[2/2,5/2,6/2,4/2,1/2,3/2] then rounded towards plus infinity to obtain a final solution sequence se=[1,3,3,2,1,2];(3)
Working  procedure  coding: Suppose n×m JSSP, randomly give birth to following sequence:
(3.2)se(sequence)=[1,3,…,n,5,3,…,n,…,1,2,…,n],
where the number indicates job and the same number denotes different working procedure of the job according to their order of appearance in se. For example, the 3×2 JSSP, solution sequence se=[1,3,3,2,1,2], which denote in turn process working procedure 1 of job 1, working procedure 1 of job 3, working procedure 2 of job 3, working procedure 1 of job 2, working procedure 2 of job 1, and lastly process working procedure 2 of job 2. Using this working procedure coding scheme  makes every sequences is feasible solutions.


#### 3.2.2. Iterative Model of the LGSCPSOA

In OPSOA, the information of individual best and global best are shared only by next generation particles. Based on OPSOA, in this paper, I firstly present LGSCPSOA, in which it also adequately utilizes information of the best particle of every generation population, at the same time; in every generation, introducing into some best particles displaces random selecting particles in population. The detailed information will be given in the following.Suppose that the searching space isn-dimensional and m particles form the colony. The ith particle represents an n-dimensional vector Xi(i=1,2,…,m), and it means that the ith particle locates at Xi=(xi1,xi2,…,xin) in the searching space. The position of each particle is a potential result. We could calculate the particle’s fitness by putting its position into a designated objective function. When the fitness is lower, the corresponding Xi is “better.” The ith particle’s “flying” velocity is also an n-dimensional vector as Vi=(vi1,vi2,…,vin). Denote the best position of the ith particles as Pi=(pi1,pi2,…,pin), the best position of the kth generation population (local best particle) as Pl=(pl1,pl2,…,pln), and the best position of all colonies (global best particle) as Pg=(p1,p2,…,pn), respectively. Using the best particle of every generation population merges into the local best particle population and displaces random selecting particles in local best generation. After finding three best values, the particle updates its velocity and positions with the following formulas:(3.3)vid(k+1)=wvid(k)+c1r1(α(pid(k)-xid(k))+(1-α)(pld(k)-xid(k)))+c2r2(pgd(k)-xid(k)),(3.4)xid(k+1)=xid(k)+vid(k+1)(i=1,2,…,m;d=1,2,…,n)(3.5)Pl(k+1)=Pl(k-1,k-2,…,1)∪Pl(k),
where w is an inertia weight, which is initialized typically in the range of [0,1]. The local best particle of k generation is u% of the k generation neighborhood particles whole number. α∈[0,1] is weight index that is chosen according to different optimization problems, which reflects relatively important degree of best position of the ith particle and the kth generation population particle. The variables c1 and c2 are acceleration constants, which control how far a particle will move in a single iteration, and other parameters are the same as in (2.1) and (2.2). The termination criterion for the iterations is determined according to whether the end generation or a designated value of the fitness of Pg is reached. In LGSCPSOA, each particle of the swarm shares mutual information and benefits from previous experiences of all other colleagues during the search process.


#### 3.2.3. Pseudo Code of LGSCPSOA

(See Algorithm1).Algorithm 1:Pseudo Code of LGSCPSOA.
Step1: Initialize parameters; including swarm size PS, end of generation G, and otherparameters will be used in LGSCPSOA;Step2: Segment and scheduling;(i)Generate stochastically initialization population and velocity using Section 3.2.1 codingscheme(ii)Evaluate each particle’s fitness(iii)Initialize gbest position with the lowest fitness particle in the swarm(iv)Initialize ibest and lbest position with a copy of particle itself(v)k:=0While (the endG of generation is not met){(i)k:=k+1(ii)Generate next generation particle population by recurrence equations (3.3), (3.4)and (3.5)(iii)Evaluate swarm{(1)Compute each particle’s fitness in the swarm(2)Find new Pg of the swarm, Pl of generation population and Pi of eachparticle by comparison, and updatePi and Pg(3)Update Pl with (3.5)Using the best particle of k generation replace the k-1 generation u%particles which are random selected}}Step3: Output optimization result Pg;End


## 3.1. Original Particle Swarm Optimization

Particle swarm optimization (PSO) is an evolutionary computation technique mimicking the behavior of flying birds and their means of information exchange. The system of PSO is initialized with a population (named swarm in PSO) of random solutions and searches for optima by updating generations. Each individual or potential solution, named particle, flies with a velocity which is adjusted according to the flying experiences of its own and its colleagues. PSOA has been developing rapidly and has been applied widely since it was introduced, as it is easily understood and realized. In PSOA, the potential solutions are “flown” through the problem space by following the current optimum particles, and the detailed information will be given in following.Suppose that the searching space isN-dimensional and m particles form the colony. The ith particle represents an N-dimensional vector Xi(i=1,2,…,m), and it means that the ith particle locates at Xi=(xi1,xi2,…,xiD) in the searching space. The particle’s fitness could be calculated through putting its position into a designated objective function. The ith particle’s “flying” velocity is also an N-dimensional vector as Vi=(vi1,vi2,…,viD). Denote the best position of the ith particle as Pi=(pi1,pi2,…,piD), and the best position of all colonies as Pg=(pg1,pg2,…,pgD), respectively. The original particle swarm optimization algorithm (OPSOA) could be performed by the following equations [7, 8]:(3.1)vid(k+1)=vid(k)+c1r1(pid(k)-xid(k))+c2r2(pgd(k)-xid(k)),xid(k+1)=xid(k)+vid(k+1),
where k represents the iterative number, c1,c2 are learning factors, usually c1=c2=2.r1, r2 are random numbers between (0, 1). The termination criterion for the iterations is determined according to whether the max generation or a designated value of the fitness of Pg is reached.


## 3.2. LGSCPSOA for JSSP

### 3.2.1. Coding Scheme in LGSCPSOA for JSSP

OPSOA has been introduced as an optimization technique in real-number space, but many optimization problems in discrete space such as JSSP. OPSOA has a disadvantage tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. This section presents LGSCPSOA to optimize JSSP in discrete space, and develop an effective “problem mapping” and “solution generation” mechanism.In many algorithms for JSSP using the machine coding,  and it gets some sequences are not feasible solutions. In LGSCPSOA the working procedure coding is used,  and it gives birth to all children (sequences) are feasible solutions.SupposeX=[x1,x2,…,xn](xi∈R,i=1,2,…n) be one random particle, following steps make particles able to denote JSSP scheduling and will be used in LGSCPSOA to solve JSSP. (1)
Sorting the weightX=[x1,x2,…,xn] from small to large gets X′=[x1′,x2′,…,xn′], and using yi denotes the position of xi′ in X=[x1,x2,…,xn]. Obtain the new sequence Y=[y1,y2,…,yn]. For example, 3×2 JSSP, X=[0.8637,0.1872,0.8725,0.6442,0.2132,0.6429], sorting X gets X′=[0.1872,0.2132,0.6429,0.6442,0.8637,0.8725], then get the new sequence Y=[2,5,6,4,1,3];(2)
Every weight of sequenceY is divided by machine number M, and then rounded towards plus infinity to get a final one feasible solution sequence. For the above above example Y/2=[2/2,5/2,6/2,4/2,1/2,3/2] then rounded towards plus infinity to obtain a final solution sequence se=[1,3,3,2,1,2];(3)
Working  procedure  coding: Suppose n×m JSSP, randomly give birth to following sequence:
(3.2)se(sequence)=[1,3,…,n,5,3,…,n,…,1,2,…,n],
where the number indicates job and the same number denotes different working procedure of the job according to their order of appearance in se. For example, the 3×2 JSSP, solution sequence se=[1,3,3,2,1,2], which denote in turn process working procedure 1 of job 1, working procedure 1 of job 3, working procedure 2 of job 3, working procedure 1 of job 2, working procedure 2 of job 1, and lastly process working procedure 2 of job 2. Using this working procedure coding scheme  makes every sequences is feasible solutions.


### 3.2.2. Iterative Model of the LGSCPSOA

In OPSOA, the information of individual best and global best are shared only by next generation particles. Based on OPSOA, in this paper, I firstly present LGSCPSOA, in which it also adequately utilizes information of the best particle of every generation population, at the same time; in every generation, introducing into some best particles displaces random selecting particles in population. The detailed information will be given in the following.Suppose that the searching space isn-dimensional and m particles form the colony. The ith particle represents an n-dimensional vector Xi(i=1,2,…,m), and it means that the ith particle locates at Xi=(xi1,xi2,…,xin) in the searching space. The position of each particle is a potential result. We could calculate the particle’s fitness by putting its position into a designated objective function. When the fitness is lower, the corresponding Xi is “better.” The ith particle’s “flying” velocity is also an n-dimensional vector as Vi=(vi1,vi2,…,vin). Denote the best position of the ith particles as Pi=(pi1,pi2,…,pin), the best position of the kth generation population (local best particle) as Pl=(pl1,pl2,…,pln), and the best position of all colonies (global best particle) as Pg=(p1,p2,…,pn), respectively. Using the best particle of every generation population merges into the local best particle population and displaces random selecting particles in local best generation. After finding three best values, the particle updates its velocity and positions with the following formulas:(3.3)vid(k+1)=wvid(k)+c1r1(α(pid(k)-xid(k))+(1-α)(pld(k)-xid(k)))+c2r2(pgd(k)-xid(k)),(3.4)xid(k+1)=xid(k)+vid(k+1)(i=1,2,…,m;d=1,2,…,n)(3.5)Pl(k+1)=Pl(k-1,k-2,…,1)∪Pl(k),
where w is an inertia weight, which is initialized typically in the range of [0,1]. The local best particle of k generation is u% of the k generation neighborhood particles whole number. α∈[0,1] is weight index that is chosen according to different optimization problems, which reflects relatively important degree of best position of the ith particle and the kth generation population particle. The variables c1 and c2 are acceleration constants, which control how far a particle will move in a single iteration, and other parameters are the same as in (2.1) and (2.2). The termination criterion for the iterations is determined according to whether the end generation or a designated value of the fitness of Pg is reached. In LGSCPSOA, each particle of the swarm shares mutual information and benefits from previous experiences of all other colleagues during the search process.


### 3.2.3. Pseudo Code of LGSCPSOA

(See Algorithm1).Algorithm 1:Pseudo Code of LGSCPSOA.
Step1: Initialize parameters; including swarm size PS, end of generation G, and otherparameters will be used in LGSCPSOA;Step2: Segment and scheduling;(i)Generate stochastically initialization population and velocity using Section 3.2.1 codingscheme(ii)Evaluate each particle’s fitness(iii)Initialize gbest position with the lowest fitness particle in the swarm(iv)Initialize ibest and lbest position with a copy of particle itself(v)k:=0While (the endG of generation is not met){(i)k:=k+1(ii)Generate next generation particle population by recurrence equations (3.3), (3.4)and (3.5)(iii)Evaluate swarm{(1)Compute each particle’s fitness in the swarm(2)Find new Pg of the swarm, Pl of generation population and Pi of eachparticle by comparison, and updatePi and Pg(3)Update Pl with (3.5)Using the best particle of k generation replace the k-1 generation u%particles which are random selected}}Step3: Output optimization result Pg;End


## 3.2.1. Coding Scheme in LGSCPSOA for JSSP

OPSOA has been introduced as an optimization technique in real-number space, but many optimization problems in discrete space such as JSSP. OPSOA has a disadvantage tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. This section presents LGSCPSOA to optimize JSSP in discrete space, and develop an effective “problem mapping” and “solution generation” mechanism.In many algorithms for JSSP using the machine coding,  and it gets some sequences are not feasible solutions. In LGSCPSOA the working procedure coding is used,  and it gives birth to all children (sequences) are feasible solutions.SupposeX=[x1,x2,…,xn](xi∈R,i=1,2,…n) be one random particle, following steps make particles able to denote JSSP scheduling and will be used in LGSCPSOA to solve JSSP. (1)
Sorting the weightX=[x1,x2,…,xn] from small to large gets X′=[x1′,x2′,…,xn′], and using yi denotes the position of xi′ in X=[x1,x2,…,xn]. Obtain the new sequence Y=[y1,y2,…,yn]. For example, 3×2 JSSP, X=[0.8637,0.1872,0.8725,0.6442,0.2132,0.6429], sorting X gets X′=[0.1872,0.2132,0.6429,0.6442,0.8637,0.8725], then get the new sequence Y=[2,5,6,4,1,3];(2)
Every weight of sequenceY is divided by machine number M, and then rounded towards plus infinity to get a final one feasible solution sequence. For the above above example Y/2=[2/2,5/2,6/2,4/2,1/2,3/2] then rounded towards plus infinity to obtain a final solution sequence se=[1,3,3,2,1,2];(3)
Working  procedure  coding: Suppose n×m JSSP, randomly give birth to following sequence:
(3.2)se(sequence)=[1,3,…,n,5,3,…,n,…,1,2,…,n],
where the number indicates job and the same number denotes different working procedure of the job according to their order of appearance in se. For example, the 3×2 JSSP, solution sequence se=[1,3,3,2,1,2], which denote in turn process working procedure 1 of job 1, working procedure 1 of job 3, working procedure 2 of job 3, working procedure 1 of job 2, working procedure 2 of job 1, and lastly process working procedure 2 of job 2. Using this working procedure coding scheme  makes every sequences is feasible solutions.


## 3.2.2. Iterative Model of the LGSCPSOA

In OPSOA, the information of individual best and global best are shared only by next generation particles. Based on OPSOA, in this paper, I firstly present LGSCPSOA, in which it also adequately utilizes information of the best particle of every generation population, at the same time; in every generation, introducing into some best particles displaces random selecting particles in population. The detailed information will be given in the following.Suppose that the searching space isn-dimensional and m particles form the colony. The ith particle represents an n-dimensional vector Xi(i=1,2,…,m), and it means that the ith particle locates at Xi=(xi1,xi2,…,xin) in the searching space. The position of each particle is a potential result. We could calculate the particle’s fitness by putting its position into a designated objective function. When the fitness is lower, the corresponding Xi is “better.” The ith particle’s “flying” velocity is also an n-dimensional vector as Vi=(vi1,vi2,…,vin). Denote the best position of the ith particles as Pi=(pi1,pi2,…,pin), the best position of the kth generation population (local best particle) as Pl=(pl1,pl2,…,pln), and the best position of all colonies (global best particle) as Pg=(p1,p2,…,pn), respectively. Using the best particle of every generation population merges into the local best particle population and displaces random selecting particles in local best generation. After finding three best values, the particle updates its velocity and positions with the following formulas:(3.3)vid(k+1)=wvid(k)+c1r1(α(pid(k)-xid(k))+(1-α)(pld(k)-xid(k)))+c2r2(pgd(k)-xid(k)),(3.4)xid(k+1)=xid(k)+vid(k+1)(i=1,2,…,m;d=1,2,…,n)(3.5)Pl(k+1)=Pl(k-1,k-2,…,1)∪Pl(k),
where w is an inertia weight, which is initialized typically in the range of [0,1]. The local best particle of k generation is u% of the k generation neighborhood particles whole number. α∈[0,1] is weight index that is chosen according to different optimization problems, which reflects relatively important degree of best position of the ith particle and the kth generation population particle. The variables c1 and c2 are acceleration constants, which control how far a particle will move in a single iteration, and other parameters are the same as in (2.1) and (2.2). The termination criterion for the iterations is determined according to whether the end generation or a designated value of the fitness of Pg is reached. In LGSCPSOA, each particle of the swarm shares mutual information and benefits from previous experiences of all other colleagues during the search process.


## 3.2.3. Pseudo Code of LGSCPSOA

(See Algorithm1).Algorithm 1:Pseudo Code of LGSCPSOA.
Step1: Initialize parameters; including swarm size PS, end of generation G, and otherparameters will be used in LGSCPSOA;Step2: Segment and scheduling;(i)Generate stochastically initialization population and velocity using Section 3.2.1 codingscheme(ii)Evaluate each particle’s fitness(iii)Initialize gbest position with the lowest fitness particle in the swarm(iv)Initialize ibest and lbest position with a copy of particle itself(v)k:=0While (the endG of generation is not met){(i)k:=k+1(ii)Generate next generation particle population by recurrence equations (3.3), (3.4)and (3.5)(iii)Evaluate swarm{(1)Compute each particle’s fitness in the swarm(2)Find new Pg of the swarm, Pl of generation population and Pi of eachparticle by comparison, and updatePi and Pg(3)Update Pl with (3.5)Using the best particle of k generation replace the k-1 generation u%particles which are random selected}}Step3: Output optimization result Pg;End


## 4. Experimental Results and Discussion

To analyze the effectiveness and performance of LGSCPSOA for JSSP to minimize makespan, three representative instances taken from the internet based on practical data have been selected to experiment, and through simulation, the best effective parameters of LGSCPSOA for JSSP to minimize makespan are found out.To get the average performance of the LGSCPSOA ten runs on each instance are performed and the solution quality is averaged, and let the best of them be the solution of this algorithm. We use the arithmetic mean, lower, and upper bound of makespan, and obtaining the best solution time four indexes to estimate LGSCPSOA. The computation comparing results of GA, OPSOA, and LGSCPSOA with different operators or parameters are as in Table1.Table 1
The comparisons of GA, OPSOA and LGSCPSOA with different parameters for JSSP.
PBSPSGNAaCMin/Max/Mean/Times0.1 (M2)0.2 (M4)0.3 (M6)0.4 (M8)0.5 (M9)6×655LGCPSO0.155/58/55.8/755/57/55. 2/955/59/56.1/755/59/55.8/855/59/56.3/50.255/58/55.8/755/59/55.7/855/59/8/55.855/59/56.2/755/59/56.4/50.355/58/56.2/555/58/55.8/755/59/55.7/855/59/55.5/855/58/55. 6/80.455/59/55.8/755/59/55.9/755/59/55.8/755/59/56.1/755/58/55.8/70.555/58/55.9/655/58/55.65/855/60/56.15/755/59/56.7/555/59/55.5/91000.655/59/55.9/755/59/55. 9/855/59/56.2/655/59/56.5/555/59/56.2/72000.755/59/55.8/755/59/56.1/755/59/56.3/655/59/55.8/755/59/56.2/70.855/58/55.3/855/59/56.1/755/59/56.3/655/59/55.8/755/59/55.4/80.955/58/55.5/855/59/55.2/955/59/56.3/755/59/55.6/922/59/55.7/7PSO155/59/55.6/955/59/55.7/855/59/55.7/755/59/55.9/755/59/56.1/7GAC155/59/57.45/355/59/57.4/055/59/57.7/155/59/57.3/255/59/57.3/2C255/59/57.9/156/59/58/055/59/57.6/157/60/58.1/057/59/58.3/010×10930LGCPSO0.1946/1078/998.7/0955/1040/1000.4/0946/1072/1004.1/0956/1060/1005.7/0943/1083/1007.3/00.2951/1038/989.6/0930/1049/990.1/1945/1008/990.2/0962/1032/999.6/0967/1067/1013.9/00.3951/1052/993.5/0951/1061/997.5/0968/1067/1023.2/0951/1037/1005.2/0956/1040/1001.2/00.4952/1048/1000.6/0961/1048/1004.9/0955/1064/1004.2/0937/1063/1004.8/0965/1063/1009.3/00.5951/1063/999.8/0946/1045/999.8/0954/1085/1001.7/0948/1032/996.8/0955/1049/1010.3/02000.6951/1044/1001.2/0951/1042/994.2/0957/1051/999/0951/1052/997.5/0937/1039/994/030000.7937/1028/987.5/0946/1072/988.9/0949/1093/1025.4/0951/1032/996.4/0963/1088/1.0076/00.8953/1030/991.8/0937/1076/996.9/0952/1045/997.1/0937/1049/1001.9/0951/1056/1003.5/00.9937/1057/986.8/0951/1030/988.6/0937/1047/995.2/0937/1053/996.7/0960/1054/998.8/0PSO11003/1115/1051.4/0998/1040/1018/0971/1035/1011/0958/1057/1014/0979/1081/1032.2/0GAC11066/1159/1121.2/01066/1169/1125.2/01084/1165/1110.4/01066/1181/1121.2/01074/1170/1115.1/0C21096/1184/1153.9/01108/1200/1160.3/01102/1206/1165/01109/1218/1172.9/01107/1192/1163.5/020×511650.11289/1473/1410.4/01214/1461/1334.4/01207/1405/1274.6/01209/1314/1245.6/01351/1454/1406.6/00.21200/1422/1307/01173/1348/1.2515/01184/1638/1252.4/01201/1289/1244.8/01334/1442/1395.4/00.31285/1469/1411/01211/1430/1313.4/01195/1275/1234.6/01186/1331/1244.4/01282/1427/1375.4/00.41316/1451/1398/01233/1429/1292.8/01178/1290/1232.8/01185/1271/1231.2/01366/1429/1398.4/00.51308/1417/1370.2/01193/1405/1306.4/01199/1311/1255.4/01197/1297/1247/01271/1407/1366.8/02000.61279/1463/1380.6/01185/1267/1219.6/01200/1230/1218.21214/1287/1254.8/01219/1341/1286.4/030000.71302/1457/1375.8/01188/1343/1262/01216/1265/1244/01185/1273/1245.2/01180/1332/1262.4/00.81263/1436/1361/01226/1301/1257.8/01197/1268/1241/01199/1336/1256.6/01215/1262/1241.6/00.91258/1443/1319.8/01195/1306/1258.9/01192/1285/1232.2/01206/1322/1254.4/01198/1264/1233.2/0PSO11264/1296/1281.2/01226/1304/1262.8/01225/1315/1263.6/01232/1287/1253.6/01207/1236/1216.4/0GAC11399/1487/1426.5/01435/1519/1488.3/01367/1494/1444.8/01414/1498/1453.1/01396/1516/1442.6/0C21445/1535/0/1485.61435/1555/1499.9/01444/1522/1491.6/01400/1490/1442.4/01418/1529/1500.3/0Remark 4.1.
In Table1, P (problem) denotes the problem size, and BS (best solution) is this problem’s optimum value, and PS (population size) and GN (generation number) indicate the population size and algorithm terminate generation. In this computing experiment, we let the displaced particles number rN=PS/3;
From the Table1 we can obtain that the LGSCPSOA is clearly better than the OPSOA and GA for JSSP. LGSCPSOA obtains smaller upper bound, arithmetic mean, and lower bound of makespan than OPSOA and GA in run ten times. The best solution found in each category of LGSCPSOA with different parameter is illustrated with bold letters. From Table 1 one can observe that LGSCPSOA with w≈0.2 and α≈0.2 has the highest performance since using these parameter has smaller upper bound, arithmetic mean and lower bound of makespan in relation to the solutions obtained by the other parameters schemes. The convergence figure and GANTT of the best solution of different size problems are shown in Figure 1.Convergence figure and GANTT of OPSO, GA, and LGSCPSOA for JSSP.
(a)(b)(c)(d)(e)(f)From simulation figure, we can see clearly that the convergence rate of LGSCPSOA is faster than the OPSOA and GA. And from above experimenting data, we can testify that the new LGSCPSOA is more efficacious than OPSOA and GA for JSSP to minimize makespan.


## 5. Conclusion and Perspectives

Although there is a huge amount of literature on OPSOA, there are not too many papers focused on solving scheduling of JSSP. In this paper, we have discussed a new approach LGSCPSOA for JSSP to minimize makespan, in whichpi, pl, pg, and Vi give out the information to others, and it is a one-way information sharing mechanism. There are not many parameters needed to be tuned in LGSCPSOA. LGSCPSOA requires only primitive and simple mathematical operators, and is computationally inexpensive in terms of both memory requirements and time. Although it does not guarantee the optimality for 20×5 JSSP, such an approach provides solution with good quality in a reasonable time limit and compared with OPSOA and GA. The performance of the new approach is evaluated in comparison with GA and OPSOA for three representative instances and obtained results show that the effectiveness of the proposed approach is the best. The proposed LGSCPSOA approach in this paper can be considered as effective mechanisms for optimization technique from this point of view.There are a number of research directions that can be considered as useful extensions of this research. Although the LGSCPSOA is tested with three representative instances, a more comprehensive computational study should be made to test the efficiency of proposed solution technique. The LGSCPSOA proposed in this paper for small size JSSP is very efficacious, but for large size problem is not approving. We just simulate the effectiveness whenrN=psize/3 for JSSP, and in the future can research the efficiency of different rN. Applying LGSCPSOA to other discrete combinatorial optimization problems is also possible in further research. The development of OPSOA is still ongoing, and furthermore, there are still many unknown areas in LGSCPSOA research such as the mathematical validation of particle swarm theory.



---

*Source: 838596-2010-08-16.xml*