Hybrid Heuristic Shifting Bottleneck Procedure for Parallel-Machine Job-Shop Scheduling Using GPU

In this paper, we implement the Parallel-Machine Job Shop Scheduling Problem (JSSP) using the modified shifting bottleneck procedure along with the heuristic Tabu search algorithm. JSSP has several real-time applications such as product manufacturing units, real-world train scheduling problem etc., Since JSSP is an NP hard problem, an optimal solution may not exist hence with the help of heuristic algorithm we try to find the approximate solution. Experimental results demonstrate that the modified shifting bottleneck procedure (SBP) shows better results than the existing SBP. And also with the help of meta-heuristic algorithm, the JSSP for larger instances can be solved easily. Results also demonstrate that GPU based Tabu search is on an average 1.8 times faster than CPU based Tabu search.