EGD-ILS: Hybrid Energy Gradient Descent Optimization for Job Shop Scheduling

Source abstract

The JSSP is recognized as one of the most difficult combinatorial optimization problems because it can be classified as an NP-hard problem. In this study, three metaheuristics are presented and evaluated. The first metaheuristic, EGD-ILS, is a new hybrid metaheuristic. The first phase uses Gradient Descent on a convex energy function to quickly construct a feasible solution by fixing the operations sequence. We provide a mathematical proof of convergence for this phase to a feasible solution. The second phase applies an Iterated Local Search to explore the solution space and minimize the makespan. This separation of objectives guarantees convergence of the initial phase and simplifies parameter tuning. The second metaheuristic, termed Priority-based Metaheuristic, constructs schedules according to priority scheduling rules based on ILS. On the other hand, the third metaheuristic, which is termed Permutational Coding-based Metaheuristic, is built on the idea of coding each operation as a permutation of the operations. In order to test the performance of the three metaheuristics, computational tests are conducted in MATLAB using the standard benchmark to investigate the performance of the problems solved. Experiments on standard FT and LA benchmarks show that EGD-ILS achieves competitive results with reduced computation time.