A New Hybrid Electromagnetism Algorithm for Job Shop Scheduling

The job shop scheduling (JSS) problem is widely acknowledged as one of the most difficult NP-hard problems encountered in practice. Most of well-known optimization and approximation techniques have been applied to the JSS, including linear programming, branch and bound, constraint satisfaction, local search, and even neural networks and expert systems. In this paper, we present a new meta-heuristic approach for this problem. Our approach is a hybrid of local search and electromagnetism-like method (EM). The 2-Opt neighborhood function and guided local search are used in the hybrid approach and experimental results on a set of standard instances shows that the proposed hybrid method is more effective when the problem size increases.