Particle swarm optimization applied to job shop scheduling

Dwivedi , Piyush and Vishal , Vivek (2007) Particle swarm optimization applied to job shop scheduling. BTech thesis.

PDF 362Kb

Abstract

In this project we have to apply the particle swarm optimization algorithm to job shop scheduling problem. Job shop scheduling is a combinatorial optimization problem where we have to arrange the jobs which may or may not be processed in every machine in a particular sequence and each machine has a different sequence of jobs. Job shop scheduling is a complex extended version of flow shop scheduling which is a problem where each job is processed through each and every machine and each machine has a same sequence of jobs. Our main objective in both kind of problem is to arrange the jobs in a sequence which gives minimum value of make span. PSO (Particle swarm optimization) helps us to find a combination of job sequence which has the least make span. In PSO a swarm of particles which have definite position and velocity for each job. In PSO, to find the combinations we use a heuristic rule called Smallest Position Value (SPV). According to smallest position value rule jobs are arranged in ascending order of their positions i.e. job having least position value is put first in sequence. In this project PSO is first applied to flow shop scheduling problem. This is done to understand how PSO algorithm can be applied to scheduling problem as flow shop scheduling problem is a simple problem. After Understanding the PSO algorithm, the algorithm is extended to apply in job shop scheduling problem for n jobs and m machines.

Item Type:	Thesis (BTech)
Uncontrolled Keywords:	Swarm optimization, PSO, SPV
Subjects:	Engineering and Technology > Mechanical Engineering
Divisions:	Engineering and Technology > Department of Mechanical Engineering
ID Code:	4160
Deposited By:	Hemanta Biswal
Deposited On:	28 Jun 2012 14:45
Last Modified:	28 Jun 2012 14:45
Supervisor(s):	Mahapatra, S S