Hybrid Multi-Objective Particle Swarm Optimization for Flexible Job Shop Scheduling Problem

Published Online March 2015 in MECS

The job shop scheduling problem (JSSP) is considered the most challenging one which has been the subject of many research studies for consumer demand and development in the production system during the recent decades. The problem is described simply as follows: given n jobs to be processed on m machines. Each job consists of a predetermined sequence of task operations, each of which requires processing without interruption for a given period of time on a given machine. The Flexible Job-shop Scheduling Problem (FJSSP) is an extension of the classical JSSP, which allows an operation to be processed by any machine from a given set or at least one operation may not process on all machines. So, FJSSP is more complex than JSSP because of additional need to determine the assignment of operations to machines [3]. FJSSP is closer to the real production situations, for example, it is used in flexible manufacturing systems. A flexible manufacturing system consists of several CNC machines. A CNC machine is a multi-tasking machine. So flexible job shop scheduling is applicable for flexible manufacturing systems [5].

Job Shop Scheduling (JSSP) is one of the most complex scheduling problems related to manufacturing industries. However, FJSSP is also an NP-hard problem as the number of jobs increases; it becomes more difficult to obtain the optimal schedule in short time. The problem of scheduling jobs in FJSSP could be decomposed into two sub-problems: Assignment Problem is to select a machine from several available machines for each operation. The second sub problem, sequence problem, is to identify a sequence of all operations on each machine. There are two different methods are used to solve this problem. The first approach, Hierarchical approach used to solve two sub problems separately. The Second approach, integrated approach considers two sub problems simultaneously [18].

However, most of the research used one objective or three objectives to be optimized with hierarchical approach. In this paper, we propose an integrated approach based on hybridization of particle swarm optimization and simulated annealing algorithm for solving the flexible job-shop scheduling problem with five objectives optimized simultaneously. Also rescheduling strategy is implemented. PSO allows an extensive search of solution space for global search while the simulated annealing is used for local search a hybrid multi-objective particle swarm optimization (MPSO) and simulated annealing (SA) algorithm is used to identify an approximation of the Pareto front for FJSSP. Hybrid MPSO is significant for global search and SA is used for local search.

The rest of the paper is organized as follows: Literature review is presented in section II, Problem description and formulation is presented in section III, section IV describes the Hybrid MPSO proposed for the problem under discussion with numerical illustration, section V presents the performance comparison and results of the proposed Hybrid MPSO and section VI concludes giving scope for future research.

• II.    Literature Review

Many researches have been done on FJSSP scheduling and several methods that include integrated approach and hierarchical, have been developed to solve FJSSP. Hierarchical approaches consist of decomposing the original problem in order to reduce its complexity. This type of approach is natural for FJSSP since the routing and the scheduling sub-problem can be separated.

Brandimarte [1] was the first to apply the decomposition approach into the FJSSP. He solved the routing sub-problem by using some existing dispatching rules and then focused on the scheduling sub-problem; it was solved by using a tabu search heuristic. Paulli [2] applied hierarchical approach.

Hurink [3] represented the FJSSP as a disjunctive graph model and proposed a hierarchical approach based on TS to solve the problem for minimum makespan time criterion.

Dauzere-Peres and Paulli [4] presented a new disjunctive graph model to represent the FJSSP problem and proposed an integrated approach based on TS to solve FJSSP.

Chen [5] also applied genetic algorithm to solve FJSSP and introduced a new coding for each solution and different crossover and mutation operators to minimize the makespan for all jobs.

Mastrolilli and Gamberdella [6] improved the TS approach proposed by Dauzere-Peres and Paulli and presented two new neighborhood functions to solve FJSP instances.

Most of the above-mentioned research is considered hierarchical or integrated approach with a single objective optimization in FJSSP. However, in modern production systems of FJSSP, more than one objective is required to be optimized simultaneously. Therefore, some researchers have considered the optimization of more than one objective in FJSSP.

Sha, Lin [7] proposed evolutionary PSO technique to solve the JSSP with multiple objectives. They used a diversification strategy with modified the particle position representation, particle movement, and particle velocity.

Xia and Wu [8] developed an easily implemented approach for the multi-objective flexible JSSP based on the combination of PSO and SA. A particle swarm optimization (PSO) is to use assign each operation to appropriate machine and simulated annealing (SA) to sequence of operation on the machine. PSO provides an initial solution for SA during the hybrid search process.

Kacem [9] he has implemented a technique that solves the assignment and job-shop scheduling problems with total or partial flexibility. He has used two approaches, localization (AL) and evolutionary. Localization used to solve the problem of resource allocation and build an ideal assignment model .Evolutionary approach controlled by the assignment model.

Gao [10] developed a hybrid genetic algorithm (GA) for the FJSSP. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. Individuals of GA are first improved by a variable neighborhood descent (VND) which involves two local search procedures: local search of moving one operation and local search of moving two operations.

Li [11] proposed hybrid algorithm combining PSO and tabu search (TS) to solve (JSSP) with fuzzy processing time. PSO used for the global search, i.e. the exploration phase, while TS used for the local search i.e. the exploitation process. The global best particle is used to direct other particles to optimal search space.

Tavakkoli-Moghaddamn [12] proposed new multi objective Pareto archive particle swarm optimization (PSO) algorithm combined with genetic operators as variable neighborhood search (VNS). Character of scatter search (SS) to select new swarm in every iteration order to find Pareto optimal solutions for the given problem. Pareto archive PSO has been combined with genetic operators to update and VNS to improve particles.

Zhang, Shao[13] developed a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSSP with several conflicting and incommensurable objectives.

Saidi-Mehrabad, Fattahi [14] proposed TS algorithm for FJSSP, in this technique the initial feasible solution of jobs and operations sequences is first generated and then the algorithm searches for the best choice of the machine’s alternative for this job and operation sequence.

Carlo, Raquel, Prospero, Naval [15] proposed an approach that extends the Particle Swarm Optimization (PSO) algorithm to handle Multi-objective optimization problems by incorporating the mechanism of crowding distance computation into the algorithm of PSO.

Lie [16] presented a PSO for the multi-objective JSSP with objective minimize makespan and total job tardiness simultaneously. Job-shop scheduling problem can be converted into a continuous optimization problem by constructing the corresponding relationship between a real vector and a chromosome obtained using the priority rule-based representation method. The global best position selection is combined with crowding-measurebased archive maintenance to design a Pareto archive PSO. That algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans.

Li, Pan, Xie, Wang [17] proposed a hybrid Paretobased artificial bee colony (HABC) algorithm for solving the multi-objective flexible job shop scheduling problem.

Sahana, Jain [28] they are analyzed Indian train scheduling from source to destination with the iteration wise conversion process with Ant colony optimization.

Guezouri, Houacine[29] they proposed an algorithm based on the principle of clonal selection and affinity maturation mechanism in an immune response used to solve the Hybrid Flow Shop (FSH) scheduling problem.

Recently, Shao [18] developed a novel hybrid DPSO and SA for FJSSP. The proposed algorithm is based on the integrated approach of multi-objective optimization developed by Shao [18] adding with more objective optimization with rescheduling strategy.

• III.    FJSSP Problem Formulateion

Problem Description:

In flexible job-shop problem, a set of n jobs is considered to process on a set of m machines. Each job, denoted by J i (1 ≤ I ≤ n) has a predefine sequence n j of operations. Each operation O_i j is processed by any one machine from a set M_i j , which is the subset of machines that can perform O ij . The processing time of O ij on machine k (1 ≤ k ≤ m) is fixed and is denoted by P ijk . The FJSSP is designed to assign all the operations of the jobs to available machines to identify their starting and completion time and is aimed to obtain an optimal schedule with some objectives.

Assumptions:

• •    All job released at time 0.

• •    All machines available at time 0.

• •    Only one job can be carried on one machine at one time.

• •    Once an operation starts, it cannot be terminated before it finishes.

• •    Order constrains only exist in operation on the same job.

Objective

The objectives are to find an assignment and a schedule to minimize following objective simultaneously.

• 1)    Ms: Makespan, i.e., the maximal completion time of

machines or jobs.

• 2)    Mw: Machine workload, i.e., the maximum processing time spent on any machine; this objective is used to keep the balance of workload among different machines and may help to avoid too much work scheduling on a certain machine.

• 3)    Tw: The total workload of machines, which is defined as total processing time over all machines.

• 4)    Ti: Total idle time, which is defined idle time of machines.

• 5)    Tr : Total Tardiness, which is defined as lateness of jobs.

• IV. Hybrid PSO AND SA FOR FJSSP

• A.    PSO algorithm

PSO is an evolutionary computation technique proposed by Kennedy and Eberhart [20]. A PSO algorithm consists of behavior of flying birds and it means that they exchange of information to solve optimization problems. PSO has been introduced as an optimization technique in real-number spaces. Typical examples include problems that require ordering and route planning in scheduling, to solve FJSSP for multiobjective converting the continuous domain to the discrete domain for PSO. In this strategy the velocity and displacement of particles need to be redefined for FJSSP.

Standard PSO

PSO is similar to the evolutionary algorithm in that the system is initialized with a population (“Swarm”) of random solutions. Each individual or potential solution, called a particle, flies in the D-dimensional problem space with a velocity that is dynamically adjusted according to the flying experience of the individual and its colleagues. Each particle remembers the best position that it has found so far during the search process personal best ( pbest ), and knows the best position of the swarm global best ( gbest ). Therefore, each particle interacts with other and every particle in the swarm tries to gradually move toward the promising areas of the search space and in this way an optimum solution is found.

The global model of equations is given below:

M id =W • M id +C1 •Rand () • (P id - N id )

+C2 • Rand () • (P gd - N id )           (1)

N id = N id + M id                                  (2)

Where, M i d the velocity for particle i represent the distance to be traveled by particle I from its current position. N_id represents the particle position; P_id represents “ pbest ” the local best solution of i th particle’s best previous position. P gd is gbest the global best solution represents the best position among all particles in the swarm.

W is the interia weight it regulates the trade of between the global exploration and local exploitation abilities of the swarm. The acceleration constants C1 and C2 represent the weight of the stochastic acceleration terms that pull each particle toward “ pbest ” and “ gbest ” positions. Rand ( ) are two random functions with range (0, 1).

The first part Eq.1 represents the inertia of previous velocity; the second part is the “cognition” part, which represents individuals thinking independently; and the third part is the “social” part, represents cooperation among the particles.

• B.    Particle representation:

In the FJSSP consist of two sub problem as assignment and sequence problem. So that particle represents in two vector one vector represents the operation permutation solution and second vector represents machine allocation Solution. Both vectors are I -dimensional vector, where I is the total number of all operations in FJSSP.

Permutation vector for Operations:

Operation permutation specifies the sequence of operation all operations from the same job occupy the same index in present vector.

Он О„ Он On On On Ом On Ом

3

1

2

1

3

2

3

1

3

Fig. 1. Operation Allocation Vector

In the above vector first element 3 specifies operation 1 for the job 3 that is O 31. Similarly 1 specifies operation 1 of the job 1 that is O 11.

Allocation Vector for Machines:

Machine allocation vector has same length as operation vector it shows the allocation of specific job on a particular machine as per shortest processing time rule (SPT). In machine allocation vector O11 indicates operation 1 of job 1 processed on machine 3 as per SPT.

O„ o,: O„ On On O„ on 0„ 0„

3

1

1

2

3

3

2

3

2

Fig. 2. Machine Allocation Vector

• C.    Particle Decoding for FJSSP

For FJSSP particle is decoded using active schedule follows. Staring time S i j competition time C ij and processing time p ij , M k denotes completion time of last operation in the schedule.

• 1.    If the operation is the first operation for a job I then S ij =C ij =0

• 2.    Processing time of the next operation consists of C ij =S ij + pig

• 3.    If number of operations assigned to the machine, find the idle interval on machine between two successive operations.

• D.    Update of pbest()

In the proposed algorithm, we have taken consideration of Pbest of particle as non-dominated solution which represents a personal best of a particle with no other objective are dominating. Pbest value stored naturally in them without the need of an external archive. The maximal archive size of the proposed algorithm is set equal to the number of all particles in the swarm. For every particle in the swarm, a displacement of a particle generates a new solution Hn+1, and the relationship between Hn+1 and Hpbest determines the update of Hpbest. With the role of domination, there are two cases between Hn+1 and Hpbest after a displacement for each particle has occurred and these different cases are as follows.

• 1)    If Hn+1 dominates Hpbest, Hpbest is replaced by the new solution Hn+1.

• 2)    If Hpbest dominates Hn+1, Hpbest is unchanged

• E.    Selection of gbest()

In single objective optimization there is only one optimal solution where as in multi-objective optimization aim to find the Pareto set instead of a single solution. In the proposed algorithm, gbest is considered as a leader for each particle which is randomly selected from pbest set with the selection probability proportional to the fitness value.

• F.    Fitness Function

Fitness is used as the performance evaluation of particles in the swarm. Fitness is usually represented with a function f: S ^ R (where S is the set of candidate schedules, and R is the set of positive real values). In the current algorithm, the current position Hn and the best position founded so far Hpbest are considered as two attributes of the particle. Each particle in the proposed algorithm is evaluated using Hpbest instead of Hn and the fitness of each particle is computed through the Pareto ranking and crowding distance method.

Crowding distance

The crowding distance is the distance between two particles and it is used to compute the degree of crowd of particles in an objective space.

Rij=|Ms(i)-Ms(j)|+|Mw(i)+Mw(j)|+

||Tw(i)-w(j)||+||Ti(i)-T(j)||+||Tr(i)-Tr(j)|(3)

Pareto Ranking

Ranking of particle consist with non-dominated solution in the objective space.

Fit=exp (-m + n) (rank-1+exp(-m+n)Ed))/I(5)

Where, I is the total number of operations, n is the number of jobs, m is the number of machine and Ed is crowding distance of the particle.

Diversification strategy:

All the particles have the same non-dominated solutions; they will be trapped in local optima, to prevent this displacement of particle to keep the non-dominated solutions differently. Once any new solution is generated by particles, the non-dominating solution set will be updated in these three situations:

• 1)    The solution of the particle dominates the gbest solution, assign the particle solution to the gbest.

• 2)    The solution of the particle equals to any solution in the non-dominated solution set, replace the nondominated solution with the particle solution.

• 3)    The solution of the particle is dominated by the worst non-dominated solution and not equal to any nondominated solution, set the worst non-dominated solution equal to the particle solution.

Displacement of particle:

The displacement of each particle depends on its pbest and gbest, in which the velocity of particle represents the probability of a particle to change towards pbest and gbest . The displacement of each particle contains two parts, i.e., operation permutation and machine allocation.

Procedure MPSO

Begin

Step I Initialization

• 1.    PSO

• a.    Initialize swarm, including swarm size, particle position and velocity.

• b.    calculate the three objects (Ms, Mw, Tw, Ti, Tr), Ranking all particles with Pareto Set concept

• 2.    SA

• c. Determine the initial temperature level. T, Tend, B Step II Computation

PSO

While (T> Tend) for each particle do

• a.    Particle displacement

• b.    Calculate the three objects (Ms, Mw, Tw, Ti, Tr), Ranking all particles with Pareto Set concept. Calculate the Crowding distance Cd according to Eq.

• (3)    on each Pareto Rank. If necessary, update gbest.

• c.    evaluate each particle according Eq. (4).

• 2.    SA begin

Set k=1;

While ( k<=Km ) for each particle do a. Randomly choose a neighbor b. Accepting neighbor if find an optimal solution with respect to the current one, update it k=k+1;

End while

Update T=T Kb;

SA end

Step III:

Output optimization result End While

Table 1. Comparision of hybrid MPSO to other algorithm

Fig. 3. Framework of Hybrid MPSO

Size	Objective	AL+CGA[9]	PSO+SA[8]	SM[21]	HGA[10]	PSO+TS[19]	AIA[17]	HDPSO[18]	Proposed HMPSO	Proposed Rescheduling
	Ms	15,16	15,16	16	14	15	14	14	14	17
8	Mw	-	12,13	13	12	12	12	12	12	16
x	Tw	79,75	75,73	73	77	75	77	77	77	83
8	Ti	-	-	-	-	-	-	-	21	22
	Tr	-	-	-	-	-	-	-	19	37
	Ms	8,7	7	8	7	7	7	7	7	8
10	Mw	7,5	6	7	5	6	6	5	6	8
x	Tw	41,45	44	41	43	43	43	43	43	50
10	Ti	-	-	-	-	-	-	-	11	10
	Tr	-	-	-	-	-	-	-	20	30
	Ms	23.24	12	11	12	11	12	11	11	12
15	Mw	11.11	11	11	11	11	11	11	11	13
X	Tw	95.91	91	91	91	91	91	91	91	97
15	Ti	-	-	-	-	-	-	-	20	27
	Tr	-	-	-	-	-	-	-	38	40

• V. Performance Comparison And Results

Effectiveness and performance of the proposed algorithm are checked on the two benchmark data set of

• G.    SA Algorithm

Starting from an initial solution, SA generates a new solution S’ in the neighborhood of the original solution S. Then, the change of objective function value, Δ = f(S’) -f(S), is calculated. For a minimization problem, if Δ <0, the transition to the new solution is accepted. If Δ ≥ 0, then the transition to the new solution is accepted with probability, usually denoted by the function exp (-Δ/T), where T is a control parameter called the temperature. The SA algorithm generally starts from a high temperature, and then the temperature is gradually lowered. At each temperature, a search is carried out for a certain number of iterations, called the epoch length. When the termination condition is satisfied, the algorithm will stop [21].SA acts as a local search method under the framework of the proposed hybrid MPSO.

In the proposed algorithm, the number of iterations for PSO is defined by the initial temperature level T0, constant Kb and the final temperature (Tend). The framework of the proposed hybrid MPSO algorithm is illustrated in Fig. 3. The temperature decreases with ratio kB in an iteration of the algorithm and the algorithm terminates once the temperature is less than the final temperature (Tend).

• H.    Rescheduling of FJSSP

In the proposed algorithm rescheduling is done. In this method, it finds machine breakdown randomly and shuffle the Workload among available machine. The workload of breakdown machine is transferred to other machines to keep objectives of FJSSP will minimize simultaneously [23].

job-shop instances with different sizes. The proposed algorithm is coded in Java and implemented on a personal computer with 3.2 GHz and 4 GB RAM. The final temperature ( Tend ) is set to 0.01 and Kb is set to0.98.

Population size is set to 100 for 4 ×5,150 for 7×10,200 for 8x8, 300 for10x10 and 400 for 15x10 respectively. The non-deterministic nature of our algorithm makes it necessary to carry out multiple runs on the same problem instance in order to obtain meaningful results. Two benchmark sets are considered.

Firstly, the proposed algorithm is compared with some well-known algorithms in literature on Kacem data. An Instance of P-FJSP that consists of 27 operations. Problem 10×10 and Problem 15×10 belong to T-FJSP it contains 30 and 56 operations respectively. The proposed algorithm is compared with other famous algorithms in literature. These algorithms include “AL+CGA” of Kacem et al. [9], “PSO+SA” of Xia and Wu [8], “hGA” of Gao et al. [10], “SM” of Xing et al. [21], “hybrid PSO-TS” of Zhang et al. [19] , “AIA” of Bagheri et al. [17] and “HDPSO” of Xinku Shao et.al [18].

Brandimarte data set: BR data composed of 10 problems from Brandimarte [1]. In these problems, the number of jobs ranges from 10 to 20, the number of machines ranges from 4 to 20, and the average of available machines for an operation (flex) ranges from 1.43 to 4.10.

Table 2. Performance comparison between proposed hybrid MPSO and MOPSO+LS ,Fl+EA on kacem data.

Size	Objective	FL+EA[9]	MOPSO+Ls[9]	Proposed HMPSO	Proposed Rescheduling
4 x 5	Ms	18,18	16,16	11	14
	Mw	8,7	8,7	9	12
	Tw	32,33	32,33	32	38
	Ti	-	-	10	11
	Tr	-	-	6	16
10 x 7	Ms	16,15	16,15	12	14
	Mw	12,11	12,11	12	14
	Tw	60,61	61,60	63	72
	Ti	-	-	7	7
	Tr	-	-	42	54

Table 3. Performance comparison between proposed hybrid MPSO and (AIA, SM) and hMPSO

	Size	Objective	AIA[17]	SM[27]	HDPSO[18]	Proposed HMPSO	Proposed Rescheduling
MK01	10x6	Ms	40	42	40	40	42
		Mw	36	42	36	36	37
		Tw	171	162	167	163	171
		Ti	-	-	-	33	35
		Tr	-	-	-	72	81
MK01	10x6	Ms	26	28	27	27	29
		Mw	26	28	27	26	32
		Tw	154	155	145	144	149
		Ti	-	-	-	35	46
		Tr	-	-	-	85	91
MK03	15x8	Ms	204	204	210	204	220
		Mw	204	204	210	210	254
		Tw	1207	854	848	852	961
		Ti	-	-	-	90	95
		Tr	-	-	-	145	181
MK04	15x8	Ms	60	68	61	61	65
		Mw	60	67	60	60	74
		Tw	403	372	366	365	401
		Ti	-	-	-	85	89
		Tr	-	-	-	121	135

Table 4. Performance comparison between proposed hybrid MPSO and (AIA, SM) and hMPSO Cont.

MK05	15x4	Ms	173	177	173	175	185
		Mw	173	177	173	173	191
		Tw	686	702	683	682	700
		Ti	-	-	-	80	85
		Tr	-	-	-	111	121
MK06	10x15	Ms	63	75	62	62	68
		Mw	56	67	58	58	64
		Tw	470	431	412	412	451
		Ti	-	-	-	75	78
		Tr	-	-	-	94	101
MK07	20x5	Ms	140	150	141	140	155
		Mw	140	150	141	141	161
		Tw	695	717	692	693	703
		Ti	-	-	-	45	52
		Tr	-	-	-	52	74
MK08	20x10	Ms	214	227	211	211	241
		Mw	203	221	207	207	250
		Tw	2121	1989	1998	1995	2014
		Ti	-	-	-	98	142
		Tr	-	-	-	143	175

• VI. Conclusion

There is a large amount of research into the FJSSP, most of this has focused on minimizing the maximum completion time (i.e. makespan). There exist other objectives in the real world, such as the minimization of machine idle time that might help improve efficiency and reduce production costs, Total Tardiness specify the lateness of the job.

The hybrid MPSO method is used to solve the FJSSP with multiple objectives and rescheduling strategy, PSO algorithm is significant for continuous problems and FJSSP is by discrete nature. Therefore, the displacement of a particle is redefined. In the proposed algorithm, Nondominated solutions are stored naturally by using pbest. Simulated Annealing is used for local search in the algorithm, pbest of particles is used to store the best solutions found from SA. A new selection mechanism is developed based on the Pareto ranking scheme.

Experimental Results show that the proposed algorithm gives better results as compared to the algorithms given in literature. On future scope, researchers can focus on optimizing some other objectives of FJSSP. Furthermore, some other meta- heuristic algorithms could be experimented to solve the FJSSP.

Acknowledgment

The authors are thankful to the anonymous reviewers as well as the editors for their valuable comments and suggestions which have led to improve the quality of the paper. Our special thanks to S. Xinyu, W. Liu, L. Qiong and Z. Chaoyong for their work on Job shop scheduling using particle swarm optimization Algorithm published in various journals and conferences.