Variable Neighborhood Programming for Job Shop Scheduling Problems

Abstract

The Job Shop Scheduling Problem is a classic combinatorial optimization problem and one of the most well-studied scheduling problems. Several methodologies, both exact and metaheuristic, have already been proposed for the solution of this computationally difficult problem. This work presents for the first time a solution approach based on Variable Neighborhood Programming for the Job Shop Scheduling Problem. Variable Neighborhood Programming is a recent methodology which constitutes a combination of Genetic Programming and Variable Neighborhood Search. In addition, some encouraging comparative computational results are also shown against the state-of-the-art Gurobi optimization solver using medium- and large-scale benchmark instances. The findings of this work have a plethora of modern applications in Manufacturing-as-a-Service online platforms. All experimental evaluations were performed on the Google Cloud Platform.