Studi Komparatif MILP dan Heuristik pada Job Shop Scheduling Problem: Minimasi Makespan dan Total Tardiness

Abstract

This study presents a comprehensive analysis of the Job Shop Scheduling Problem (JSSP) with two commonly used objectives in manufacturing: minimizing makespan and minimizing total tardiness. Two approaches are directly compared: an exact model based on Mixed Integer Linear Programming (MILP) solved using Gurobi, and a fast heuristic based on dispatching rules and local search. The study is conducted on 10 random instances (10 jobs, 5 machines, 5 operations per job). The results show that the heuristic is highly competitive for the makespan objective (average gap of 9.25% with approximately 240 times faster computation than MILP). For the tardiness objective under a balanced configuration, the heuristic yields an average defined gap of 52.39% with a runtime cost about 6.0 times slower than MILP. This paper provides a reproducible baseline, data-driven analysis, and technical directions for improving both the quality and efficiency of tardiness-focused heuristics in future research.