Volume 20, Issue 2 (IJIEPM 2009)                   2009, 20(2): 57-75 | Back to browse issues page

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Behroozi M, Eshghi K. A New Hybrid Particle Swarm Optimization for Job Shop Scheduling Problem. Journal title 2009; 20 (2) :57-75
URL: http://ijiepm.iust.ac.ir/article-1-115-en.html
A New Hybrid Particle Swarm Optimization for Job Shop Scheduling Problem
Mehdi Behroozi , Kourosh Eshghi *
, eshghi@sharif.edu
Abstract:   (16550 Views)
The classical Job Shop Scheduling Problem (JSSP) is NP-hard problem in the strong sense. For this reason,   different metaheuristic algorithms have been developed for solving the JSSP in recent years. The Particle Swarm Optimization (PSO), as a new metaheuristic algorithm, has applied to a few special classes of the problem.  In this paper, a new PSO algorithm is developed for JSSP. First, a preference list of the generated solutions is prepared to obtain the feasibility. Then, a new method using factorial base numeral system, called factoradic approach, is developed to satisfy the validity of the generated solutions. This approach permits a one to one mapping of a solution in discrete space to a PSO particle position in continuous space. Since PSO is an evolutionary approach, some modifications are implemented to the algorithm. For examples, a simple greedy algorithm is developed to generate relatively good initial population or every solution obtained by PSO is also improved by a local search operator. To avoid trapping into local optima, a new velocity updating equation is considered. Furthermore, a Simulated Annealing (SA) approach is applied to the final solution obtained by PSO to improve it. Finally, the proposed hybrid algorithm is tested by some job shop benchmark problems. The results indicate the efficiency of the proposed hybrid PSO with respect to other algorithms exist in the literature for the considered problem.
Keywords: Job Shop Scheduling Problem, Particle Swarm Optimization (PSO), Factoradic, Simulated Annealing (SA), GRASP
Full-Text [PDF 880 kb]   (5701 Downloads)    
Type of Study: Research | Subject: Other related Industrial and production reserach subjects in which has direct relation to the state-of-the art of the IE
Received: 2009/11/29 | Published: 2009/08/15
Add your comments about this article : Your username or Email:
CAPTCHA
Send email to the article author

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.