[4P3-GS-10] AI application:

[4P3-GS-10-01] A Hybrid Approach for Job Shop Scheduling Problems: Problem Decomposition with Metaheuristics and Mathematical Programming Models

〇Kuniaki Satori¹, Nobuyuki Yoshikawa¹ (1. Mitsubishi Electric Corporation)

Keywords:JSP, optimization, meta-heuristics, MIP

In this paper, a novel optimization algorithm for the Job Shop Scheduling Problem (JSP) is proposed. The algorithm employs a metaheuristic-based problem decomposition strategy which assigns jobs into ordered subproblems to reduce the computation cost. Each subproblem is formulated as a Mixed Integer Programming (MIP) model and solved sequentially with considering decisions of the previously solved subproblems. The proposed algorithm with several metaheuristics, Genetic Algorithm (GA), Tabu Search (TS) and Simulated Annealing (SA), are evaluated on the simulation of the actual factorial scheduling problem. The simulation experiments show that the scheduling accuracy and computational efficiency of the proposed algorithm are significantly improved. These results indicate that the proposed algorithm is highly effective for large-scale scheduling problems, which likes real-world applications.