Journal of Computer Science

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

R. Thamilselvan and P. Balasubramanie

DOI : 10.3844/jcssp.2012.681.693

Journal of Computer Science

Volume 8, Issue 5

Pages 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.

Copyright

© 2012 R. Thamilselvan and P. Balasubramanie. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.