Particle Swarm Optimization Approach for Scheduling of Flexible Job Shops

Particle Swarm Optimization Approach for Scheduling of Flexible Job Shops

1Srinivas P. S., 2Ramachandra Raju V., 3C.S.P Rao.

1Associate Professor, V. R. Siddhartha Engineering College, Vijayawada

2Professor, Department of Mechanical Engineering, College of Engineering, JNTUK, Vizianagaram,

3Professor, Department of Mechanical Engg, NIT, Warangal

Abstract

Recent developments in research on decision making have linked up the strings of optimization with the social behavior of the insects. There have been a host of complex problems like scheduling, project management, routing etc., that are conveniently mapped with natural environment and solved through the inspiration of the insects. This paper illustrates the application of particle swarm optimization (PSO) approach for solving a simple and flexible job shop problems with an objective of minimizing the maximum completion time of all the jobs. The preliminary results are quite encouraging and motivating for the researchers to use PSO as a powerful tool in real time scheduling problems.

Keywords: Flexible Job Shop, Particle Swarm Optimization, NP-hard, Swarm Intelligence

1. Introduction

   Scheduling is concerned with allocating limited resources to tasks to optimize some performance criterion, such as completion time or production cost. Scheduling of a job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches owing to the high computational complexity. A large number of approaches to the modeling and solution of these scheduling problems have been reported in the Operations Research (OR) literature, with varying degrees of success.

   The flexible job shop scheduling problem (FJSP) is one of the hardest combinatorial problems and very difficult to solve. FJSP is an extension of the classical JSP which allows an operation to be processed by any

   machine from a given set. It incorporates all the difficulties and complexities of its predecessor JSP and is more complex than JSP because of the addition need to determine the assignment of operations to machines. In most of its practical formulations, the FJSP is known to be NP-hard, so exact solution methods are unfeasible for most problem instances and heuristic approaches must therefore be employed to find good solutions with reasonable search time. In this paper, PSO based solution methodology is adopted for solving FJSP.

2. Literature

   Kennedy J, Eberhart R C [3] are the first persons introducing this particle swarm optimization. It is an evolutionary computation technique mimicking the behavior of flying birds and their means of information exchange. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Chandrasekaran. S et al [2] dealt the problem of scheduling in flow shops with the objective of minimizing makespan, total flow time and completion time variation. Rahimi [4] considered a bi-criteria permutation flow shop scheduling problem, where weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in strong sense, an effective multi-objective particle swarm (MOPS), exploiting a new concept of the Ideal Point and a new approach to specify the superior particles position vector in the swarm, is designed and used for finding locally Pareto-optimal frontier of the problem.

   Zhixiong Liu [7] proposed the particle representation based on operation-particle position sequence. In the particle representation, the mapping between the particle and the scheduling solution is

   established through connecting the operation sequence of all the jobs with the particle position sequence. The particle representation can ensure that the scheduling solutions decoded are feasible and can follow the particle swarm optimization algorithm model. Weijun Xia and Zhiming Wu [6] proposed a hybrid optimization approach for multi objective flexible job shop scheduling problems, where they can integrate particle swarm with simulated annealing for solving job shop problems. By reasonably hybridizing these two methodologies, they develop an easily implemented hybrid approach for the multi-objective

   rather than using evolutionary operators (e.g. the crossover and the mutation operators in genetic algorithms). It assumes that socially shared information helps its population evolve. In other words, the population iteratively updates and searches for optima with the shared information. In this paper, PSO is employed to solve the flexible job shop scheduling problem with an objective of minimal make span.

   In this paper we use the global model equations as follows (Shi & Elbert, 1999):

   flexible job-shop scheduling problem (FJSP).

   Sha and Cheng [5] proposed a hybrid particle

   Vid

   W Vid

   C1 Rand pid

   C2 rand pgd

   Xid

   1

   Xid

   swarm optimization (PSO) for the job shop problem. Since the solution space of the JSP is discrete, we modified the particle position representation, particle

   and

   Xid Xid Vid 2

   movement, and particle velocity to better suit PSO for

   the JSP. They modified the particle position based on preference list-based representation, particle movement

   where Vid is called the velocity for particle I, represents the distance to be traveled by this particle

   based on swap operator, and particle velocity based on

   from its current position,

   Xid

   represents the particle

   the tabu list concept in our algorithm. Giffler and Thompsons heuristic is used to decode a particle position into a schedule. Furthermore, they applied tabu search to improve the solution quality.

   Ajith Abraham et al [1] introduced a hybrid metaheuristic, the Variable Neighborhood Particle Swarm Optimization (VNPSO) algorithm, consisting of a combination of the Variable Neighborhood Search (VNS) and Particle Swarm Optimization (PSO). The proposed VNPSO algorithm is used for solving the multi-objective Flexible Job-shop Scheduling Problems (FJSP).

3. Particle Swarm Optimization

position, pid which is also called as pbest (local best solution), represents ith particles best previous position, and pgd , which is also called gbest (global best solution), represents the best position among all particles in the swarm. W is the inertial weight. It regulates the trade-off between the global exploration

and local exploitation abilities of the swarm. C1 and C2 represent the weight of the stochastic acceleration terms that pull each particle toward pbest and gbest positions. Rand and rand are two random

functions in the range [0,1].

The inertia weight is set using the following equation

Particle swarm optimization (PSO) is a popular problem solving technique in the swarm intelligence (SI) paradigm. It was first introduced by Kennedy and Eberhart in 1995. They developed simple methods

Where

W Wmax

Wmax Wmin itermax

iter,

which could efficiently optimize continuous nonlinear mathematical functions. Borrowing ideas from artificial life (A-life), social psychology and swarming theory, PSO simulates swarms such as flocks of birds and schools of fish searching for food.

Also, PSO is related to evolutionary computation (EC), but it is somewhat different. Similar to many EC techniques, PSO initializes a problem state to a population of randomly distribted solutions. Unlike many other ECs however, PSO "evolves" solutions based on individual experience and group experience,

Wmax = initial value of the weighting coefficient

Wmin = final value of the weighting coefficient

itermax = maximum number of iterations

iter = current iteration or generation number

The process of implementing the PSO algorithm is as follows.

1. Initialize a swarm of particles with random positions and velocities in the D-dimensional problem space.

   Initialize particles with random position and velocities

2. For each particle, evaluate the desired optimization fitness function.

   Evaluate Fitness

3. Compare particles fitness value with particles pbest. If current value is better than pbest, then set pbest value equal to the current value and the pbest position equal to the current position in D-dimensional space.

   Apply Local Search

4. Compare the fitness evaluation value with the best swarms fitness obtained so far. If current value is better than gbest, then reset gbest to the current particles fitness value.

   Compare / Update fitness value with P Best and G Best

5. Change the velocity and position of the particle according to the equation (1) and (2) respectively.

6. Go back to step (2) until a termination criterion is met, usually a sufficiently good fitness or a specified number of generations.

1. Particle Position and Velocity Initialization and Limitation

   For initialization of particle position, position

   Start

   Meet stopping Criterion

   End

   vector xij is set to the random number from

   xmin

   to xmax

   Update velocity and position

   .During a PSO run, position vector has no limitation

   bound. That is to say, the range [ xmin

   , xmax

   ] is valid

   only for initialization of position, which can assure that position sequence SP and operation sequence SO have the diversity, and then, schedule solutions decoded from the particle swarm have the diversity too. In the

   Figure 1: Particle Swarm Optimization Flow Chart

   following Computation, to 1.

   xmin

   is set to 0, and

   xmax

   is set

2. Particle Swarm Optimization Algorithm

   For initialization of particle velocity, velocity vector vij is set to the random number from vmin to vmax . During a PSO run, velocity vector is limited to the

   Begin

   Step 1. Initialization

   range [ vmin

   , vmax

   ]. In the following computation, vmin

   Initialize parameters, including swarm size,

   is set to -1, and vmax is set to 1.

   maximum of generation, Wmax, Wmin, C1, C2;

   Step 2. Assignment and scheduling Generation=0;

   Initialize particles position and velocity stochastically;

   Evaluate each particles fitness;

   Initialize gbest position with the particle with the lowest fitness in the swarm;

   Initialize pbest position with a copy of particle it self;

   While (the maximum of generation is not met)

   Do {

   generation = generation+1;

   Generate next swarm by equations;

   Evaluate swarm

   {

   Compute each particles fitness;

   Find new gbest and pbest by comparison;

   Update gbest of the swarm and

   pbest of each particle;

   }

   }

   Step 3. Output optimization results.

   End.

3. Particle Representation (Encoding): Based on Operation and Particle Position Sequence

As PSO is used to optimize the problem, one key issue is the encoding, which is called particle representation in this paper. Suitable particle representation should importantly impact the optimization result and performance of PSO. In most applications of PSO, it is applied to the continuous optimization problems. In these optimization problems, particle position xi is directly denoted as the solution, which is continuous value. Velocity vi , acceleration constants C1 and C2 , and inertia weight W are also continuous constants. Because PSO model justly comprises addition, subtraction and multiplication operations, updated particle position and velocity are also continuous value.

Therefore, PSO completes the searching process in the continuous space that limits the use of PSO in the discrete space or combination optimization problem. However, job shop scheduling problem is a

combination optimization problem, and its feasible solutions are the sequence of operations of all jobs.

The authors also solved the classical JSP problem using PSO. In case of JSP, PSO cannot directly employ the particle position as the solution. Certain particle representation should be employed, which can establish the mapping between the scheduling solution and the particle position, and the scheduling solution can be indirectly obtained through decoding of the particle representation. The paper employs the particle representation based on Operation- Particle Position Sequence (OPPS).

The feasible solution of JSP is the operation sequence of all jobs. For the particle position xi=(xi1, xi2 , xij ,, xid ) , all position vectors xij (the total number is equal to d) also have a sequence (increasing sequence or decreasing sequence). So the operation sequence of all jobs and the sequence of the particle position vectors can be linked together, and the mapping is gained between the scheduling solution and the particle position.

Table 1: PSO results in comparison with the best known results of bench mark problems

Figure 2: The mapping, decoding and updating of the particle

Particle swarm optimization algorithm is employed to solve the job shop scheduling problem with an objective of minimizing the maximum completion time of all the jobs. In the particle representation, the mapping between the particle and the scheduling solution is established through connecting the operation sequence of all the jobs with the particle position sequence. According to processing constraints of the problem, each operation in the operation sequence of all the jobs is assigned on each machine in turn to form the scheduling solution. The results of PSO based optimization heuristic are compared against the results of the benchmark problems in Table 1.

1. PSO for FJSP

   The FJSP problem may be formulated as follows. Each instance of the problem is defined by set of jobs, a set of machines and a set of operations. Each job consists of a sequence of operations, each of which requires one machine out of a set of given machines. The problem is thus to determine both assignment and sequence of operations on all the machines that minimize the makespan subjected to the conditions: (i) the precedence of operations given by each job are to be respected. (ii) each machine can perform at most one operation at a time nd (iii) the operations can not be interrupted.

   Let:

   J= {1, 2… n} denotes the set of jobs;

   M= {1, 2 m} denotes the set of machines;

   N= {0, 1, 2 n+1} denotes the set of operations, where 0 and n+1 represents the dummy start and finish operations, respectively.

   The flexible job shop problem (FJSP) consists of a set J of n jobs that must be processed on a set M of m machines. Each job j consists of a sequence of nj operations (routing) i.e. Oj,1, Oj,2, Oj,,nj. The execution of each operation i of a job j (Oj,i) requires one machine out of a set of given machines called Mj,i

   M.

2. Assumptions made in this work

   Each job is an entity: Although the job is composed of distinct operations, no two operations of the same job may be processed simultaneously. Thus we exclude from our discussion certain practical problems, e.g. those in which components are manufactured simultaneously prior to assembly into the finished product.

   No Pre-emption: Each operation once started, must be completed before another operation may be started on that machine.

   Each job has m distinct operations on one machine: we do not allow for the possibility that a job might require processing twice on the same machine.

   Setup times of machines and move time between operations are negligible.

   No machine may process more than one operation at a time.

   There is no randomness: in particular,

   The number of jobs is known and fixed. The number of machines is known and fixed.

   The processing times are known and fixed.

3. Encoding

The most important issue in applying PSO successfully to FJSP is to develop an effective

problem mapping' and 'solution generation' mechanism. If these two mechanisms are devised successfully, it is possible to find good solutions for a given optimization problem in acceptable time. To find

a suitable mapping between problem solution and PSO particle, we first sequence the capable machines of an operation according to the increasing order of processing time. If one machine's processing time is equal to another, the lower order number of machine has priority. After this, we get different priority levels for all machines which process the same operation. Then the particle position can be generated stochastically according to the order of operations of different jobs.

The problem shown in Table 2 is to execute three jobs on four machines. Table 3 gives the order of priority of machines corresponding to each operation (priority 1>2>3>4).

Table 2: Flexible job shop

Table 3: Priority order of machines.

In general, initial particles' positions and initial particles' velocities in the swarm are generated at random. According to this approach to generate initial particles' positions, search space can be reduced and improves the search speed.

The PSO algorithm using the above encoding procedure is developed and tested for the FJSP and the results obtained after 200 iterations are as follows.

gbest initial sequence is 1 1 2 2 2 3 3

gbest machine sequence is 3 1 0 1 2 2 3

gbest ptime sequence is 1 1 1 3 1 3 2

gbest sequence is 2 2 3 1 1 2 3 Makespan (gbest) = 5

1. Conclusions

   This paper discussed the Particle Swarm Optimization algorithm for FJSP problems. Although there is a huge literature on classical JSP, the FJSP does not have a rich literature. Therefore there is a need to develop effective approach for this complex problem. In this paper the authors have attempted JSP by using PSO and the experimental results show that Particle Swarm Optimization algorithm for JSP is very effective, and can find the best known solution for the cited benchmark instances. The preliminary results obtained by the implementation of PSO for FJSP in this paper are quite encouraging and motivating for the researchers to use PSO as a powerful tool in real time scheduling problems.

2. References

1. Ajith Abraham, Hongbo Liu, Tae-Gyu Chang, Variable Neighborhood Particle Swarm Optimization Algorithm.

2. Chandrasekaran. S, Ponnambalam. S.G, Suresh. R.K, Vijayakumar. N, An Application of Particle Swarm Optimization Algorithm to Permutation Flowshop Scheduling Problems to Minimize Makespan, Total Flowtime and Completion Time Variance.

3. Kennedy J, Eberhart R C., Particle Swarm Optimization, Proceedings of IEEE International Conference on Neutral Networks, Perth, Australia, 1995, pp. 1942-1948.

4. Rahimi-Vahed A.R, Mirghorbani S.M, A multi-objective particle swarm for a flow shop scheduling problem , J Comb Optim (2007) 13:79102 DOI 10.1007/s10878-006-9015-7.

5. Sha D.Y, Cheng-yu Hsu, A hybrid particle swarm optimization for job shop scheduling problem. Computers & Industrial Engineering 51 (2006) 791808

6. Weijun Xia, Zhiming Wu, An effective hybrid optimization approach for multi- objective flexible job-shop scheduling problems. Computers & Industrial Engineering 48 (2005) 409425.

7. Zhixiong Liu, Investigation of Particle Swarm Optimization for Job Shop Scheduling Problem.