Research Article Open Access

Integration of Genetic Algorithm with Tabu Search for Job Shop Scheduling with Unordered Subsequence Exchange Crossover

R. Thamilselvan1 and P. Balasubramanie1
  • 1 ,
Journal of Computer Science
Volume 8 No. 5, 2012, 681-693

DOI: https://doi.org/10.3844/jcssp.2012.681.693

Submitted On: 2 December 2011 Published On: 24 February 2012

How to Cite: Thamilselvan, R. & Balasubramanie, P. (2012). Integration of Genetic Algorithm with Tabu Search for Job Shop Scheduling with Unordered Subsequence Exchange Crossover. Journal of Computer Science, 8(5), 681-693. https://doi.org/10.3844/jcssp.2012.681.693

Abstract

Problem statement: The problem of scheduling n jobs on m machines with each job having specific machine route has been researched over the decade. The Job Shop Scheduling (JSS) is one of the hardest combinatorial optimization problems. Each resource can process at most one job at a time. Approach: This study proposes a new approach to solve a Job Shop Scheduling problem with the help of integrating Genetic Algorithm (GA) and Tabu Search (TS). After an initial schedule is obtained the GA, the result is given as an input to TS to improve the status of the initial schedule. The objective of this study is to minimize the makespan, process time and the number of iterations. This approach achieves a better result with the help of efficient chromosome representation, powerful crossover strategies and neighborhood strategies. Results: This research resolves the allocation of operation to different machine and the sequence of operation based on machine sequence. Job Scheduling is the process of completing jobs over a time with allocation of shared resources. It is mainly used in manufacturing environment, in which the jobs are allocated to various machines. Jobs are the activities and a machine represents the resources. It is also used in transportation, services and grid scheduling. Conclusion/Recommendations: The result and performance of the proposed work is compared with the other conventional algorithm and it is also testing using standard benchmark problems.

  • 1,025 Views
  • 2,566 Downloads
  • 2 Citations

Download

Keywords

  • Job Shop Scheduling (JSS)
  • Genetic Algorithm (GA)
  • Tabu Search (TS)
  • Simulated Annealing (SA)
  • Tabu List (TL)
  • Aspiration Criteria (AC)