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

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.