EGD–ILS: Hybrid Penalty–Energy Gradient Descent Optimization for Job Shop Scheduling
- 1Laboratory of Analysis, Modeling, and Simulation (LAMS), Faculty of Sciences Ben M’Sick, Hassan II University of Casablanca, Casablanca P.O. Box 7955 , Morocco
- 2Laboratory of Industrial Management and Energy and Technology of Plastics and Composites, ENSEM, Hassan II University of Casablanca, Casablanca P.O. Box 7955, Morocco
Abstract
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.
Related
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
- Multiplicative Gradient Method for Log-Homogeneous Optimization: A Unified Mirror-Descent Framework
- An interior penalty nonconforming finite element method for strain gradient elasticity
- Plug-in Optimization Method for Penalty Parameters in Nonparametric GMANOVA model
BibTeX
@article{nohair2026egdils,
title = {{EGD–ILS: Hybrid Penalty–Energy Gradient Descent Optimization for Job Shop Scheduling}},
author = {Lotfi Nohair and Abderrahim El Adraoui and Lahcen Safraoui},
journal = {Mathematics},
year = {2026},
month = nov,
doi = {10.3390/math14214021},
url = {https://www.mdpi.com/2227-7390/14/21/4021},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - EGD–ILS: Hybrid Penalty–Energy Gradient Descent Optimization for Job Shop Scheduling
AU - Lotfi Nohair
AU - Abderrahim El Adraoui
AU - Lahcen Safraoui
PY - 2026
DA - 2026/11/03
JO - Mathematics
DO - 10.3390/math14214021
UR - https://www.mdpi.com/2227-7390/14/21/4021
AB - 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.
SN - 2227-7390
ER -