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

The JSSP is recognized as one of the most difficult combinatorial optimization problems and is classified as NP-hard. In this study, three metaheuristics are presented and evaluated. The first, EGD–ILS, is a new hybrid metaheuristic. Its first phase constructs a feasible solution via gradient descent on a convex energy function while keeping the operation sequence fixed. We provide a mathematical proof that this phase converges to a feasible solution. The second phase applies 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 the priority-based metaheuristic, uses ILS to construct schedules according to priority scheduling rules. The third metaheuristic, termed the permutational coding-based metaheuristic, is based on encoding the operations as a permutation. In order to evaluate the performance of the three metaheuristics, computational tests are conducted in MATLAB using standard FT and LA benchmarks. The results showed that EGD–ILS achieves competitive results with competitive computation times on the hardware tested. Here, the term energy refers to a differentiable penalty energy that measures constraint violations, not industrial energy consumption.